运筹学总复习课件

1、一、 1.建立线性规划数学模型 2.线性规划基本定理、性质（不必证明） 3.线性规划解法 图解法 单纯形法(大M法、两阶段法)、对偶单纯形法 二、 线性规划对偶问题（求法） 线性规划对偶理论性质（不必证明） 对偶问题的经济解释 灵敏度分析,三、运输问题 包括产销平衡问题与不平衡问题及求最大值和最小值问题 不平衡问题平衡问题的方法：增加虚产地或销地(注意单位运价是0或M,或库存费用) 四、整数规划 分枝定界法与割平面法思路 指派问题（包括求最小值和最大值，人数和工作数相等和不相等情况、其它特殊要求的情况） 人数和工作数不相等相等的方法：增加一行或一列 五、动态规划 用动态规划方法解静态规划问题（

2、划分阶段、确定状态变量、决策变量、状态转移方程、递推关系式、逆序和顺序解法） 六、图与网络分析 最短路问题（正权数） 最大流问题（包括可行流已知和未知两种情况） 网络计划绘制网络图，工序时间参数、工序总时差、确定关键路线,例2,MaxZ=3X1+4X2 -X1+2X2 8 X1+2X2 6 2X1+X2 8 X1，X20,O,A,B,C,最优解为B（10/3，4/3）,例:已知LP问题,1.写出其对偶问题 2.应用图解法判断对偶问题解的类型 3.利用对偶理论证明原问题无最优解,解1.对偶问题为,2.图解法见右图:无可行解 3.据对偶问题性质:反证法 若原对偶问题一个有最优解,则另一问题也有最优

3、解,且目标值相等,例:已知LP问题,解:,最优解为(6,0,0,0,10),MaxZ=2*6=12,最终表,3.保持最优基不变时的变化范围,2.当=0时,约束右端项由 最优解有何变化,2.当=0时,约束右端项由 最优解有何变化,所以最优基不变,最优解为(3,0,0,0,7),-6,例：已知求极大化问题线性规划问题的初始表和最终表，X4，X5为松弛变量,约束条件为形式 1.将表中空白处填上数字 2.给出对偶问题的最优解 3.C3在什么范围变化时最优解不变 4.b1增加到12时,最优解有何变化,若有变化求出新的最优解,1,2,-1,2,-1,-5/3,-1/3,1.将表中空白处填上数字,2.给出对

4、偶问题的最优解 Y1=5/3，Y2=1/3,3.C3在什么范围变化时最优解不变,4.b1增加到12时，最优解有何变化，若有变化求出新的最优解,因此最优解发生变化,3,1,4,6,3,3,运输问题 求初始基本可行解,最小元素法,行 差 额,列 差 额,0,1,1,2,5,1,3,6,0,1,2,3,2,1,3,0,1,2,1,2,3,7,6,1,2,5,2,1,2,伏格尔法,位势法求检验数判别,4,3,3,1,6,3,0,3,10,-1,-5,9,2,1,2,1,-1,10,12,最优解调整,5,2,1,3,6,3,0,3,10,-2,3,-5,9,0,2,2,1,9,12,B5,0,0,0,4

5、,4,2,3,3,3,2,2,ui,vj,0,2,4,0,-2,3,0,3,8,0,8,2,5,7,7,2,不平衡运输问题,例：求下表效率矩阵的指派问题最优解,A B C D E,甲 乙 丙 丁 戊,12 7 9 7 9,8 9 6 6 6,7 17 12 14 9,15 24 6 6 10,4 10 7 10 9,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,7 0 2 0 2,4 3 0 0 0,0 8 3 5 0,11 8 0 0 4,0 4 1 4 3,当n较大时，可用标号法确定： 用标号法确定覆盖所有零元素的最小直线数方法：,5

6、 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,求最小值指派问题： 人数M、工作数N不等 A：MN 虚增人数，由于其不创造价值（或不消耗时间），价值系数为0，目标函数不变 B：MN 增加虚工作，由于工作为虚拟，价值为0，目标函数不变 有特殊要求时（某人不做某事）价值系数为M,有四人、五项工作 虚增1人,正权数的最短路问题，求V1到V9的最短路线,最短路线: V1 V2 V6 V9,V1 V2 V3 V4 V5 V6 V7 V8 V9,4,*,6,5,6,*,V1,0,3,*,V2,V4,7,*,V5,*,V3,11,*,V6,8.5,V7,7

7、,*,9,*,（0，+）,（Vs，4）,（-V1，1）,（-V2，1）,（V2，1）,（V3，1）,增广链为VsV1V2V3Vt，调整量L（Vt）=1,用标号法求下面网络图中最大流,（0，）,（Vs，3）,练习 画出网络图，计算各工序最早开始、最早结束、最迟开始、最迟结束时间及各工序总时差，确定关键路线。,A,4,B,6,C,6,D,7,E,5,G,7,F,9,H,4,I,8,关键路线：由总时差为零的工序构成 B D G I,A 4 0 4 3 7 3,B 6 0 6 0 6 0,C 6 4 10 7 13 3,D 7 6 13 6 13 0,E 5 6 11 19 24 13,F 9 13

8、22 15 24 2,G 7 13 20 13 20 0,H 4 22 26 24 28 2,I 8 20 28 20 28 0,用动态规划解下面问题： Maxz=4X1+9X2+2X32 X1+ X2+ X3 =10 Xi0 ; i=1,2,3,顺序解法: 设S1.S2,S3分别为各阶段终点状态状态,并记S3=10 fk(sk)表示k阶段结束状态为Sk时从1阶段到k阶段的最大值,状态转移方程为 S3=10, S2=S3-X3 , S1=S2-X2 S0=S1-X1=0 允许决策集合 0X3S3 0 X2 S2 X1 =S1 f1(S1)=max4X1 =4S1 X1 *=S1,X1=S1,f

9、2(S2)=max9X2+f1(S1),=max9X2 +4 S1= max9X2 + 4(S2-X2)=9 S2,0 X2 S2,X2 * =S2,f3(S3)=max2X32+f2(S2) =max2X32 +9 S2 =max2X32 +9( S3-X3 ) = maxh3（ S3，X3 ) ,反推算: S3=10, X3 * = S3 =10 , S2=S3-X3 * =0 , X2 * =S2 =0 , S1=S2-X2 * =0 , X1 =S1 * =0 S0=S1-X1=0,0 X3S3,=4X3-9=0 极值点为 X3=9/4,=40 X3=9/4 为极小值点,比较两段点指标

10、值,当X3=0, h3( S3，X3 ) =9 S3 当X3= S3 , h3( S3，X3 ) = 2S32,X3 * = S3 ,f3(S3)= = 2S32 =200,解：k=1,2,3,4 状态变量Sk表示K阶段初用来分配给第K至4个工厂的货物箱数 决策变量Xk表示k阶段分配给第k个商店的货物箱数 状态转移方程Sk+1=Sk-Xk，0Xk Sk 且为整数 最优值函数fk（Sk）表示将Xk箱货物分配给第K至4个商店采取最优策略可获得的最大赢利。 基本方程fk（Sk）=maxVk（ Sk ，Xk）+ fk+1（Sk+1） f5（S5）=0,K=4,f4（S4）=maxV4（S4，X4）+f

11、5（S5），S4=0,1,2,3,4,5,6,K=3,K=2,K=1,f1（S1）=maxV1（S1，X1）+f2（S2），S1=6,S1 =6, X1*=1; S2 =5, X2*=1, 2,3; S3 =4, 3,2, X3*=3, 2,1 ; S4 =1, X4*=1 ; S5 =0, X5*=0; S6 =0 最优解（1，1，3，1，0，0）；（1，3，1，1，0，0）；（1，2，2，1，0，0） S1 =6, X1*=2; S2 =4, X2*=0,1, 2; S3 =4, 3,2, X3*=3, 2,1 ; S4 =1, X4*=1 ; S5 =0, X5*=0; S6 =0 最优

12、解（2，0，3，1，0，0）；（2，1，2，1，0，0）；（2，2，1，1，0，0）,一、判断下列说法是否正确 1.图解法和单纯形法虽然求解的形式不同，但从几何意义理解，两者是一致的。() 2.线性规划增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。() 3.线性规划每一个基解对应可行域的一个顶点。() 4.如果一个线性规划存在最优解，则最优解一定对应可行域边界上一个点。() 5.对取值无约束的变量Xj，通常令Xj= Xj -Xj ，其中Xj0， Xj 0，在用单纯形法求解的最优解中有可能同时出现Xj0 ， Xj 0 。( pj +pj =0) () 6.用

13、单纯形法求解标准形式的线性规划时，与j 0对应的 变量都可以作换入变量。() 7.单纯形法计算中，如不按最小比值原则选出换出变量，则在下一个解中至少有一个基变量的值为负。(),8.单纯形法计算中，选取最大正检验数k对应的变量Xk作为换入变量，将使目标函数值得到最快的增长（最大最小）() 9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。() 10.线性规划的任一个可行解都可以用全部基可行解的线性组合表示() 11.若X1、X2分别是某一线性规划问题的最优解， 则X= 1X1+ 2 X2，也是该线性规划问题的最优解，其中 1、 2为正的实数。

14、() 12.本章例9用两阶段法计算的例子中，第一阶段目标函数也可以写成min=k1x6+k2x7，其中k1、k2均为大于零的常数() 13.对一个有n个变量m个约束条件的标准型线性规划问题，可行解的顶点恰好为Cnm个。() 14.单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解(),二、1.任一线性规划问题存在并具有唯一的对偶问题() 2.对偶问题的对偶一定是原问题() 3.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解。反之，当对偶问题无可行解时，其原问题具有无界解(),分别为标准形式的原、对偶问题的可行解，(),4.设,X*，Y*分别为其最优解，则恒有,5.若

15、线性规划的原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。() 6.已知Yi*为线性规划对偶问题的最优解，若Yi*0，说明在最优生产计划 中，第I种资源已完全耗尽。() 7.已知Yi*为线性规划对偶问题的最优解，若Yi*=0，说明在最优生产计划 中，第I种资源一定有剩余。(),8.若某种资源影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k。() 9.若线性规划问题中的bi，Cj同时变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解情况。() 10.在线性规划问题的最优解中，若某一变量Xj为非基变量 ，则在原来问题中，无论改变它在

16、目标函数系数Cj或在各约束中的相应系数aij，反映到最终单纯形表中，除了该列数字有变化外，将不会引起其它列数字变化。() 三、1.运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解() 2.表上作业法实际上就是求解运输问题的单纯形法() 3.按最小元素法给出的初始基可行解，从每一空格出发可以找出唯一闭回路() 4.如果运输问题单位运价表某行（列），同加（减）一个常数k，最优调运方案不变() 5.如果运输问题单位运价表某行（列），同乘一个常数k，最优调运方案不变(),5.如果运输问题产地产量、销地销量都是整数，则运输问题最优解

17、也为整数解() 四、1.整数规划解的目标函数值一般优于其相应的线性规划问题的解目标函数值() 2.用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解，通常可任取一个作为下界值，再进行比较剪枝() 3.用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是 该问题目标函数值的下限。() 4.用割平面法求解整数规划问题，要求包括松弛变量在内的所有变量必须取整数() 5.用割平面法求解纯整数规划问题，建立的割平面有可能切去一些不属于最优解的整数解() 6.指派问题效率矩阵的每个元素都同乘一个常数k，将不影响最优指派方案() 7.指派问题数学模型的形式与运输问题十分相似，故

18、也可以用表上作业法求解() 8.求0-1规划的表上作业法是分枝定界法的特例() 9.分枝定界法在进行分枝时必须满足，一是分枝后的各子问题必须容易求解，二是各子问题解的集合必须覆盖原问题的解(),八、1.在动态规划模型中，问题的阶段数等于问题中的子问题的数目() 2.在动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性() 3.在动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前所做的决策() 4.对于一个动态规划问题，用顺推解法和逆推解法可能会得出不同的最优解() 十、 1.图论中的图不仅反映研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点的连线长短曲直都严格要求() 2.在任一图G中，当点集V确定后，树是G中边数最小的连通图() 3