运筹学讲义-单纯形方法

1、运筹学讲义-单纯形方法l（一）单纯形方法的初步讨论1、单纯形方法的基本思想 从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。 从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。3/27/20222l（一）单纯形方法的初步讨论2、单纯形方法：消去法例求解线性规划模型 解：第一步，将线性规划模型标准化： Max Z=50 x1+30 x2+0 x3+0 x4 st 4x1+3x2+x3 =120 2x1+x2+ +x4 =50

2、x1 , x2 , x3 , ,x403/27/20223 2、单纯形方法：消去法 第二步，寻找初始可行解。变量x3 、,x4对应的列 向量A3、A4 可作为初始可行基，那么X3、X4为基 变量，X1、X2为非基变量，用非基量表示基变量， 则有： Max Z=50 x1+30 x2+0 x3+0 x4 st x3 =120- 4x1-3x2 x4 =50 -2x1-x2 x1 , x2 , x3 , ,x40 令x1 、 x2 =0，得到基本可行解 X=（0，0，120，50）。3/27/202242、单纯形方法：消去法第三步，判断目标函数是否达到了最优。第四步，选取入基变量。确定x1 为 基

3、变量， x2仍为非基变量。第五步，选取出基变量。 x3 =120- 4x1-3x20 x4 =50 -2x1-x20解不等式得：x125 ，只有当x1=25时， x4恰好等于0，所以x4确定为出基变量。于是新的典则方程为： x1 =25 - 0.5x2 - 0.5 x4 x3 =20 - x2 + 2 x43/27/20225第六步，产生新的基本可行解及目标函数值。令x2 、 x4等于0，得到x1 =25， x3 =20，于是新的基本可行解为X=（25，0，20，0），目标函数值为Z=1250。第七步，判定目标函数值是否得到了最优。根据分析目前的方案还不是最优的。重复第四、五、六步， x2入基

4、， x3 出基，建立新的典则方程： x1 =15+ 0.5 x3 -1.5 x4 x2 =20 - 2 x3 + 2 x4令非基变量x3 、 x4等于0，得到新的基本可行解X=（15，20，0，0），目标函数值为1350。问题求解完成。3/27/20226l（二）单纯形方法的矩阵描述1、线性规划的典则形式： Max Z=CBB-1b+(CN-CBB-1N)XN St XB=B-1b-B-1NXN XB , XN 02、判别向量与判别数：（a）=CN- CBB-1A为对应基B的所有X的判别向量，其中任一分量j=cj-CBB-1Aj 为变量xj关于基B的判别数，j=1,2, -, n。3/27/2

5、02272、判别向量与判别数：（b）N=CN-CBB-1N为对应基B的所有非基变量XN的判别向量，其中任一分量j=cj-CBB-1Aj 为非基变量xj关于基B的判别数，j=m+1,m+2, -, n。（c）所有基变量的判别向量是零向量，所有基变量的判别数是0（为什么？）。3、最优解的判定：（a）如果所有的检验数都小于0，则当前解为最优解。3/27/202283、最优解的判定：（b）如果至少存在一个检验数大于0，且该检验数对应的列向量中至少有一个正分量，则需要继续进行迭代寻找最优解。（c）如果至少存在一个检验数大于0，且该检验数对应的列向量的所有分量都小于0，则线性规划问题不存在有界最优解。3/

6、27/20229l（三）单纯形方法：表上作业法1、单纯形表的构造方法1：C-CBB-1A=(CB,CN)-CBB-1(B,N) =(0,CN-CBB-1N) 两边同乘上X得： （C-CBB-1A）X= (0,CN-CBB-1N)X，化简得： Z=CBB-1b+(CN-CBB-1N) XN 构造联立方程： Z+(CBB-1A- C) X =CBB-1b B-1AX =B-1b3/27/2022101、单纯形表的构造 这样得到单纯形表： 3/27/2022111、单纯形表的构造方法2： XB=B-1b-B-1NXN，则有： XB+B-1N XN =B-1b 又 Z=CBB-1b+(CN-CBB-1

7、N)XN，于是： Z+（CBB-1N-CN）XN=CBB-1b，这样得： Z+（CBB-1N-CN）XN=CBB-1b XB +B-1N XN=B-1b 构造单纯形表：3/27/202212l（三）单纯形方法：表上作业法1、表上作业的步骤：第一步，将线性规划问题进行标准化处理。第二步，确定初始基本可行解与初始可行基。第三步，编制单纯形计算表。第四步，计算检验数，判断线性规划问题是否有最优解。第五步，确定入基变量。一是最大检验数准则，二是最 小下标准则。第六步，确定出基变量。最小检验数对应的基变量出基。第七步，编制新的单纯形表。重复以上的第四七步， 直到能够确定线性规划问题是否有最优解为止。 3

8、/27/202213l2、单纯形方法：表上作业法l应用举例 求解下列线性规划问题： Min Z=X1-3X2 S.t. 2X1+4X2 6 -X1+3X25 X1 , X20 解： 第一步，将上述问题进行标准化处理：3/27/202214l应用举例 Max Z=-X1+3X2 S.t. 2X1+4X2+X3 =6 -X1+3X2 + X4 =5 X1,X2,X3,X4 0第二步，确定初始基本可行解与初始基本可行基。 初始可行基： B=（A3,A4） 初始可行解： X=（0，0，6，5）3/27/202215l应用举例第三步，构造单纯形表：-1300CBXB B-1bX1 X2 X3X4检验数0

9、X3624103/20X45-13015/3检验数0-13003/27/202216l应用举例第四步，计算检验数并判断是否是最优解。检验数列在初始单纯形表中的最后一行。第五步，确定入基变量。 对应的检验数最大，所以确定X2为入基变量。第六步，确定出基变量。计算的检验数列在初始单纯形表中的最后一列。根据出基变量的判别准则，应确定X3出基。3/27/202217-1300CBXB B-1bX1 X2 X3X4检验数3X21.50.510.2500X40.5-2.50-0.751检验数4.5-2.5-0.750第七步，构造新的单纯形表：3/27/202218l应用举例第八步，判定迭代到这一步是否应该

10、停止。 因为所有的非基变量的检验数都为负数，因此可以判断迭代到此步的基是最优基，目标函数值为Z=4.5，最优解为X=（0，1.5，0，0）。原问题的最优解为X=（0，1.5，0，0），目标函数值为Z=-4.5。3/27/202219l（四）确定初始基本可行解的方法1、对于约束方程中都是小于等于0，并且约束方程右边项皆大于0的情况，只要引进松弛变量即可得到单位阵的初始可行基。2、如果约束方程都是等于某些值的情况，此时需要引进人工变量才能构造出单位阵的初始可行基和初始可行解。3、如果约束方程中有大于某些值的情况，则需要引进剩余变量并同时引进人工变量，才能构造出单位阵的初始可行基和初始可行解。3/2

11、7/202220l（一）人工变量消除法M法1、M法的含义： 通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。3/27/202221l（一）人工变量消除法M法2、M法的辅助线性规划问题： 原问题： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn=bm x1,x2, ,xn 03/27/202222l（一）人工变量消除法M法2、M法的辅助线性规划问题： Max z=c1

12、x1+c2x2+cnxn-MXn+1-MXn+2-MXn+m s.t. a11x1+a12x2+a1nxn+Xn+1 =b1 a21x1+a22x2+ +a2nxn + Xn+2 =b2 am1x1+am2x2+ +amnxn +Xn+m=bm x1,x2, ,xn 03/27/202223l3、M法的解题步骤（1）把原线性规划问题进行标准化处理。（2）引进人工变量，构造辅助线性规划问题。（3）运用单纯形方法，把人工变量全部剔除出基变量。（4）在得到的原问题的初始可行基的基础上，运用单纯形方法进行迭代。（5）直到能够判断原问题有无最优解时为止。3/27/202224l4、M法解的判定（1）经过

13、若干次迭代后，基变量中无人工变量，则说明原问题有基本可行解。（2）经过若干次迭代后，基变量中仍有人工变量，并且全部检验数皆小于0，则表明原问题无可行解。3/27/202225l（二）人工变量消除法两阶段法1、含义：在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为0，人工变量的系数为1，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数为0时为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以

14、求出原来问题的解。3/27/202226l（二）人工变量消除法两阶段法2、两阶段法的辅助问题： 原问题： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn =b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn =bm x1,x2, ,xn 03/27/202227l（二）人工变量消除法两阶段法2、两阶段法的辅助问题： 辅助问题： Min Z/=Xn+1+Xn+2+Xn+ms.t. a11x1+a12x2+a1nxn+Xn+1 = b1 a21 x1+ a22x2+ +a2nxn + Xn+2 =b2 am1x1+a

15、m2x2+amnxn + Xn+m=bm x1,x2, ，,xn 0 Xn+1，Xn+2 ， ，Xn+m 03/27/202228l（二）人工变量消除法两阶段法3、解的判断：（1）辅助问题的目标函数值Z/ 0。（2）假定B为辅助问题最优基，此时若辅助问题的目标函数值Z/ 0，则原问题无解。 证明（请同学们自己做一做）。 （3）辅助问题在最优基B下目标函数的值Z/=0，此时有两种情况：第一种情况，若辅助问题的最优基B对应的基变量中无人工变量，则该最优基也是原问题的可行基，这时候只要在单纯形表中去掉人工变量所在的列和最后一行，即可得到原问题的初始可行单纯形表。3/27/202229l（二）人工变量

16、消除法两阶段法3、解的判断：（3）第二种情况，若辅助问题最优基B对应的基变量中还有人工变量，即存在： yr+a/rkyk+a/rjxj=0这时需要进行讨论：第一，若a/rj=0，即有： yr+a/rkyk=0 则表明原问题中的第r个约束是多余的，可以从辅助问题单纯形表中，直接划掉这一行。第二，若a/rj中至少有一个不等于0，则需要以之为转轴元素再进行迭代，直到化为第一种情况为止。3/27/2022301、退化问题 在约束系数矩阵A=(aij)mn, （ mn）中，若R（A） m，则称该线性规划问题是退化的。2、退化迭代的特点（1）退化解的基变量中至少有一个取值为0。（2）退化迭代中基在不断变化

17、但解始终不变。（3）退化迭代不会引起目标函数值的改进。3、防止循环迭代的方法（1）摄动法（2）字典顺序法（3）最小下标法3/27/202231l4、退化问题的单纯形摄动方法（1）原理 对退化的线性规划问题的右边项作微小的扰动，以避免因退化而引起的循环。（2）应用举例3/27/202232见Excel中的演示3/27/2022333/27/202234l第一节 线性规划建模的几个问题l第二节 常见的线性规划模型l第三节 案例讨论3/27/202235l一、线性规划建模的要求与思路1、要求：繁简适当，要能够反映实际问题的主要因素，得出结论和产生效益。2、思路：首先将实际问题简化得能比较容易地建立一

18、个粗略的、可以使用的模型；在这个基础上考虑加进先前被省略掉的一些因素，改进已建立的模型；重复这个过程直到能建立符合要求的模型为止。 3/27/202236l二、线性规划建模的一般过程 1、明确决策变量 2、确定目标函数 3、确立约束方程 4、给出变量取值的限制3/27/202237l三、参数资料的来源 1、统计资料 2、会计核算资料 3、工程分析 4、实验研究 5、合理规定等3/27/202238l一、配料问题 假设有n种原料，已知每种原料都含有m种成分，又已知每种原料的单位成分含量为aij（i=1,2, ,m,j=1,2, ,n）。现欲用这n种原料配制成一种产品，要求单位产品的各种成分的含量

19、为bi ，如果每种原料的单价为cj。问如何配料才能使产品的生产成本最低。3/27/202239l二、资源利用问题 生产n种产品，每种产品都要经过m道工序，其中，第j种产品在第i道工序上加工所需要的工时为aij （i=1,2, ,m,j=1,2, ,n）,第i道工序可提供的工时最多为bi ，第j种产品的单位利润为cj 。问如何规划各种产品的数量，使获得的利润最大。3/27/202240l三、运输问题:某种物资有m个产地、n个需地，产地产量、需地的需求量及由产地到需地的单位运价如下： 运价（C） 需求地（B） 产量（a）12n产地111121n1221222n2mm1m2mnM需求量（b）12n3

20、/27/202241l三、运输问题：问如何设计运输方案，才能使运输成本达到最小。（1）产销平衡 （2）产大于销（3）产小于销 （4）运力限制等3/27/202242l四、投资问题： 设有n个投资项目可供选择，Cj表示第j个投资项目的收益率，a表示第i种资源用于第j个项目的投资数量，b表示第i种资源的数量，问如何进行投资才能使投资总收益率最大。3/27/202243l五、混合问题：某石油公司用A、B、C三种原料混合成普通汽油（R）、高级汽油（P）和低铅汽油（L）3种成品出售。3种原料的单位成本及每月最大购入量： 原料 单位成本 最大购入量 A a 100 B b 150 C c 503/27/2

21、02244l五、混合问题： 每千克成品油的售价为：普通汽油为d元，高级汽油为e元，低铅汽油为f元。 低铅汽油每月最多销售50吨。 各种汽油的规格如下： 普通汽油R：A少于20%、C不多于30%； 高级汽油P：A不少于40%、B不少于己于10%且不多于20%、C不多于10%； 低铅汽油：B不少于30%。试建立线性规划模型。 3/27/202245l六、下料问题： 用某种材料切割m种毛坯，根据经验，单位材料上有n种不同的下料方案，每种下料方案可得各种毛坯数量及每种毛坯的需求量为： C 下料方案需求量B1B2.Bn毛坯名称A1A2Am1112.1nb12122.2nb2.m1m2.mnbm3/27/

22、202246l六、下料问题： 问应该怎样安排下料方案，才能是材料的消耗最省。3/27/202247l七、分派问题： 设有n件工作B1，B2，.，Bn，分 派给n个人A1，A2，An去做，每 人只做一件工作且每件工作只安排一人 做，Ai完成Bj的工时为Cij。问应如何分 派才能使总工时最省。3/27/202248l八、生产进度问题： 某企业生产一种季节性很强的产品，产品只能在k个月内销售，同时生产也要在这些月内进行。除正常生产时间生产外，也可以加班生产，产品在正常生产时间每月最多能生产A个单位，单位成本为a元，加班生产每月最多能生产B个单位，单位成本为b元。当月生产未及时销售出去的需贮存，库存容

23、量为C，贮存费为单位产品c元，k个月的需求量分别为O1、O2,.,Ok。试建立线性规划模型，使得总的生产费用最低。3/27/202249l第一节 线性规划的对偶问题l一、问题的提出l二、原问题与对偶问题的关系：（1）原问题求极大（小）对偶问题求极小（大）（2）原问题目标函数的系数变成对偶问题的约束方程的右边项，同样，对偶问题目标函数的系数是原问题的约束方程的右边项（3）原问题的变量的个数、主约束的个数分别等于对偶问题的主约束个数和变量的个数（4）原问题的约束系数矩阵与对偶问题的约束系数矩阵存在转置关系3/27/202250l二、原问题与对偶问题的关系（5）在原极小问题中的“大于等于”、“小于等

24、于”、“等于”约束，分别与对偶问题中变量的“大于等于0”、“小于等于0”、“无约束”相对应。反之，在原极小问题中的变量“大于等于0”、“小于等于0”、“无约束”分别对应着对偶问题约束中的“小于等于”、“大于等于”、“等于”。3/27/202251l三、原问题与对偶问题的转换 举例说明。3/27/202252l一、原问题与对偶问题是相互对称的。l二、弱对偶定理： 原问题的目标函数值以对偶问题的目标函数值为上界，对偶问题的目标函数值以原问题的目标函数值为下界。l三、无界性定理：若原问题（对偶问题）为无界解，则对偶问题（原问题）无可行解。3/27/202253l四、最优解性质定理： X*、Y*分别是

25、原问题与对偶问题的可行解，若有CX*=Y*b存在，则X*、Y*分别是原问题与对偶问题的最优解。l五、对偶定理： 若原问题有最优解，那么对偶问题也有最优解，且目标函数的值相等。l六、互补松弛性定理： X*、Y* 分别是原问题和对偶问题的可行解，若Y* Xs=Ys X* ，当且仅当X*、Y*为最优解。3/27/202254l一、关于互补松弛性定理的几个重要的推论l二、互补松弛定理的应用应用举例 Max 2X1+4X2+X3+X4 St X1+3X2 +X4 8 2X1+X2 6 X2+X3+X46 X1+X2+X3 9 X1、X2、X3、X403/27/202255l二、互补松弛定理的应用 其最优

26、解为X=（2，2，4，0），目标函数值为16。试运用互补松弛定理求对偶问题的最优解。3/27/202256l三、对偶解的解释1、对偶解与影子价格2、检验数与边际贡献3/27/202257l一、对偶单纯形方法的基本思想 从对偶问题的可行解和原问题的不可行解出发，进行换基迭代，一旦当原问题的解也变成可行解时，这时的解就是原问题的最优解。l二、对偶单纯形方法与原单纯形方法的区别1、原单纯形方法从可行解和对偶问题不可行解出发，直到所有的检验数皆小于等于0，而对偶单纯形方法则从对偶可行解和原问题不可行解出发，直到原问题的解也变成可行。3/27/202258l二、对偶单纯形方法与原单纯形方法的区别2、最优

27、解的判定标准不一样。3、确定出入基变量的顺序不同。原单纯形方法，先确定入基变量后再确定出基变量，而对偶单纯形方法先确定出基变量后确定入基变量。4、确定出入基变量的方法不同。3/27/202259l三、对偶单纯形方法的解的判定1、B-1b0，表明已求出了原问题的最优解。2、 B-1b中至少有一个负分量，且该负分量所在行的各元素都是非负数，则问题无最优解。3、 B-1b中至少有一个负分量，且该负分量所在行的元素中存在负数，则需要继续迭代。3/27/202260l四、对偶单纯形算法的过程1、对问题进行标准化处理2、确定一个初始的对偶可行解3、编制对偶单纯形表4、判定目标函数是否达到最优5、换基迭代，

28、直到能判定问题有无最优解时为止。l五、应用举例3/27/202261l一、敏感性分析的含义 由于受到政策、价格、工艺水平、资源贮备、设备更新等若干因素的影响，线性规划模型中的参数C、A、b经常会发生变化，那么C、A、b在什么样的范围内变化，才不会导致已求出的最优基的改变，这就是敏感性分析所要解决的问题。3/27/202262l二、目标函数系数C变化的敏感性分析1、单个目标函数系数Cj变化的情况（1）Cj为非基变量的目标函数系数（2） Cj为基变量的目标函数系数2、多个目标函数系数变化的情况（1）变化的目标函数系数都是非基变量（2）变化的目标函数系数中有一个是基变量，其他的是非基变量（3）变化的

29、目标函数系数中有多于一个基变量3/27/202263l三、右边项发生变化的敏感性分析1、单个右边项发生变化 2、多个右边项发生变化l四、增加新变量的敏感性分析 在原问题中增加新变量，会导致约束系数矩阵的列向量增加，同时也会增加检验数的个数。如果增加新变量后，新变量的检验数仍小于0，则最优解保持不变，否则最优解会发生变化。l五、增加新约束的敏感性分析1、如果原问题的最优解满足新约束条件，则最优解保持不变。2、如果原问题的最优解不满足新约束条件，则需要寻找新的最优解。3/27/202264l第一节 概述l一、概念 对决策变量的取值有整数限制的规划问题，称为整数规划。l二、整数规划的分类1、线性整数

30、规划与非线性整数规划2、纯整数规划与混合整数规划3/27/202265l三、线性整数规划的模型 Max Z=CX St AX(=、)b X0,且取整数3/27/202266l四、整数线性规划与一般线性规划的关系1、对整数线性规划的整数约束的放松，便得到一般的线性规划，反之，对一般线性规划增加变量取整的要求，则便变成整数线性规划。因此，整数线性规划的约束比一般线性规划的约束更紧。2、整数线性规划的可行域是一般线性规划问题可行域的子集。3、整数线性规划问题的目标函数值以一般线性规划问题目标函数值为界，即整数线性规划问题的最优值，不可能优于一般线性规划问题的最优值。3/27/202267l一、背包问

31、题 一个背包的容积为V，现有n种物品待装，物品的重量为wj，体积为vj,j=1,2, ,n，问如何配装才能使得既不超过背包的容量，又能装入的物品重量最大。l二、工厂的选址问题 有n城市1,2, ,n，需要某种物资的数量分别为d1, d2, ,dn，现欲打算建造m座工厂，假设在城市j建厂，规模为sj，需要投资为fj，从城市i到城市j的单位运输费用为cij，问m座工厂应分设在何处比较合适。3/27/202268l三、加工问题 有m台同类型的机床，有n种零件要在这些机床上进行加工，设加工的时间分别是a1,a2,an，问如何分配才能使各机床的总加工任务相等，或尽可能均衡。l四、旅游推销问题 一个旅游推销商从家门口A0出发，经过预先确定的村子A1，A2，An，然后回到家，假定村子Ai到村子Aj的距离为dij,问如何确定一条行走路线，经过所有要去的村庄，且使总的行走路程最短。3/27/202269l一、“公理”1、对一个整数线性规划问题，如果不考虑变量取整的要求