1
运筹学
2 第一章 绪论
第二章 线性规划
如何建立线性规划的数学模型；
线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？
如何用图解法求解两个变量的线性规划问题？线性规划问题的解有哪些性质？
如何用单纯形方法、两阶段算法 求解线性规划问题？
如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）
对偶单纯形方法适合解决什么样的问题？如何求解？
对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？
3 1、建立线性规划的数学模型：
特点：
（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；
（3）有一个需要优化的目标，它也是变量的线性函数。
2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？
目标求极小；约束为等式；变量为非负。
min
b 0TzCXAXX
例：把下列线性规划化为标准形式：
121212112max 2328 1 20,0zxxxxxxxxx
3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？
例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）
线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）
定理1 线性规划的可行域是凸集。 4 定理2 X是线性规划基可行解的充分必要条件是X是可行域的顶点。
定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。
4、如何用单纯形方法求解线性规划问题？（单纯形表）
表上作业法
什么是表上作业法
表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。是线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。
[编辑]
表上作业法的步骤[1]
1、找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；
（1）西北角法：
从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。
（2）最小元素法：
从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。
注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。
2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；
运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，据此：
σij = cij − (ui + vj) ,其中前m个计为,前n个计为 由单纯形法可知，基变量的σij = 0
cij − (ui + vj) = 0因此ui,vj可以求出。
3、改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；
（因为目标函数要求最小化）
案例. 石华建设监理公司监理工程师配置问题
1问题重述
石华建设监理公司 ( 国家甲级 ) 侧重于国家大中型项目的监理，仅在河北省石家庄市就曾同时监理七项工程，总投资均在 5 000 万元以上．由于工程开工的时间不同，各工程工期之间相互搭接，具有较长的连续性， 1998 年监理的工程量与 1999 年监理的工程量大致相同．每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定的．监理工程师的配置数量随之变化．由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的．有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地．因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建 ( 结构 ) 专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源．为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分．通常标准施工期需求的人数较容易确定．但高峰施工期就比较难确定了，原因有两点： (1) 高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题． (2) 各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的．因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围．另经统计测算得知，全年平均标准施工期占 7 个月，人均年成本 4 万元；高峰施工期占 5 个月，人均年成本 7 万元．标准施工期所需监理工程师如下表所示．
运输问题的求解方法
——表上作业法
产销平衡表与单位运价表
表上作业法
一、产销平衡表与单位运价表
运输问题还可用产销平衡表与单位运价表进行描述。
假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。
表5.3.1 产销平衡表与单位运价表
二、表上作业法
运输这一类特殊问题可用更加简便的求解方法———表上作业法求解，实质仍是单纯形法，步骤如下：
（1）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。
（2）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。
（3）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。
(4）重复（1）～（2），直到求出最优解为止。
（一）确定初始可行基的方法
最小元素法
从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。
伏格尔法
采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。 （二）最优解的判别
计算非基变量（空格）的检验数,当所有的检验数 时，为最优解。
求空格检验数的方法有：
闭回路法
以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。
