线性规划模型的单纯形法PPT学习教案

1、会计学1线性规划模型的单纯形法线性规划模型的单纯形法cj c1 c2 cnCBXB x1 x2 xn b ci1ci2cimxi1xi2xima11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm 1 2 m-z R1 R2 Rn-Z0可行基的基变量与基变量对应的目标函数中的价值系数约束方程的右边常数变量的价值系数约束系数确定入基变量后，按规则计算检验数行其系数列向量为单位矩阵其检验数为0单纯形表的定义第1页/共57页单纯形表的特点：基变量对应的约束方程系数矩阵为单位矩阵I；基变量对应的检验数均等于0；基可行解不同，反映在原表中该基可行解对应的基B不同。第2页/共5

2、7页第3页/共57页 第4页/共57页)0,.0 ,.,(21)0(mbbbXnmjj,.,1, 0)0(X（2）唯一最优解判别定理：若所有 则存在唯一最有解。 nmjj,.,1 0第5页/共57页nmjj,.,1, 00的kkx（4）无界解判定定理：若 有某一个非基变量 并且对应的非基变量的系数 则具有无界解。0的kmkmxmiakmi,.2,1,0,第6页/共57页出基变量所在的行称为主元行。出基变量所在的行称为主元行。第7页/共57页优性检验。优性检验。第8页/共57页线性规划问题0.maxXbAXtsCXz化为标准型，引入松弛变量sX0, 0. .0maxsssXXbIXAXtsXCX

3、z第9页/共57页基变基变量量基变量对应的基变量对应的目标函数系数目标函数系数xBxNxSRHSXS0BNIb检验检验数行数行cj-zjCBCN0表3-3 初始单纯形表0, 0. .0maxsssXXbIXAXtsXCXz 在迭代若干步之后，当检验数行全部非正时，就得到最优单纯形表最优基变量松弛变量第10页/共57页基变基变量量基变量对应的基变量对应的目标函数系数目标函数系数xBxNxSRHSXS0BNIb检验检验数行数行cj-zjCBCN0基变基变量量基变量对应的基变量对应的目标函数系数目标函数系数xBxNxSRHSXBCBIB-1NB-1B-1b检验检验数行数行cj-zjCB -CBCN-

4、CBB-1N0 -CBB-1-CBB-1表3-3 初始单纯形表表3-4 最优单纯形表第11页/共57页 对于一般的线性规划问题，在用单纯形法求解之前，总是先化为标准型。如果在系数矩阵中有一个单位阵，则可以作为初始可行基。 问题：线性规划问题化为标准形时，如果约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？ 第12页/共57页【例3-7】 用大M法求解线性规划模型 121211212min233501252600,0Zxxxxxxxx x其标准型如下：1212314125max2335012526000,1,2,5jZxxxxxxxxxxxj 第13页/共57页1 1 -1 0 01 0

5、 0 -1 02 1 0 0 1A 在标准型的约束方程的系数矩阵里，找不到3阶单位矩阵或者3个不同的3维单位向量。1212314125max2335012526000,1,2,5jZxxxxxxxxxxxj 如果不存在单位矩阵，则可以通过添加人工变量的方法，在标准型的约束方程的系数矩阵中人为地构造一个单位阵，从而获得初始可行基，再作进一步迭代。 第14页/共57页 分别在第一式中加入人工变量x6，第二式中加入人工变量x7。人工变量的作用： 使约束条件系数矩阵中含有一个单位矩阵。121236147125max2335012526000,1,2,7jZxxxxxxxxxxxxxj 1 1 -1 0

6、 0101 0 0 -1 0012 1 0 0 100A第15页/共57页 其基变量为x6， x7， x5，令非基变量等于0，可得一个基可行解X=（0，0，0，0，600，350，125）T。不是原问题的可行解121236147125max2335012526000,1,2,7jZxxxxxxxxxxxxxj 121211212min233501252600,0Zxxxxxxxx x 人工变量是人为添加到原约束方程的虚拟变量，若人工变量不等于0 ？原问题约束方程无可行解第16页/共57页 在单纯形迭代过程中，要求人工变量逐步从基变量被替换出，变为非基变量，最后，基变量中不含有人工变量。 如何能

7、做到这一点？ 为使人工变量被替换出成为非基变量，有1.大M法2.两阶段法第17页/共57页基本思路： 添加人工变量后，用单纯形法求解时，要求人工变量在迭代后为0，即希望人工变量全部变为非基变量。 在目标函数求最大值的线性规划问题中，设人工变量在目标函数中的系数为-M，M为任意大的正数。如何实现这一目的？若人工变量不为0，目标函数能否达到最优？3.8.1 大M法 只要人工变量不为零，目标函数最大值就是一个任意小的数。第18页/共57页如【例3-7】，引入人工变量x6， x7后， 目标函数为：12345671236147125max2300035012526000,1,2,7jZxxxxxMxMx

8、xxxxxxxxxxxj 若人工变量x6， x7不等于0，则目标函数不可能实现极大化 目标函数中添加“惩罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量0，则目标函数不可能实现最优。第19页/共57页cj -2 -3 0 0 0 -M -MCBXBx1x2x3x4x5x6x7b-Mx611-10010350-Mx7100-10011250 x52100100600cj-zj-2+2M -3+M-M -M000475M12345671236147125max2300035012526000,1,2,7jZxxxxxMxMxxxxxxxxxxxxj 1 1 -1 0 0101 0 0

9、-1 0012 1 0 0 100A表3-10 初始单纯形表0第20页/共57页-Mx601-1101-1225100-10011250 x5010210-2350cj-zj0-3+M-MM-2002-2M225M+250cj -2 -3 0 0 0 -M -MCBXBx1x2x3x4x5x6x7b-Mx611-10010350350-Mx7100-10011251250 x52100100600300cj-zj-2+2M -3+M-M -M000475M第21页/共57页cj -2 -3 0 0 0 -M -MCBXBx1x2x3x4x5x6x7b-Mx601-1101-1225225100

10、-10011250 x5010210-2350175cj-zj0-3+M-MM-200 2-2M225M+250-Mx601/2-10-1/2105011/2001/20030001/2011/20 -1175cj-zj01/2M-2-M0-1/2M+10 -M 50M+600表3-11 换基迭代后的单纯形表1第22页/共57页cj -2 -3 0 0 0 -M -MCBXBx1x2x3x4x5x6x7b-Mx601/2-10-1/2105011/2001/20030001/2011/20-1175cj-zj01/2M-2-M0-1/2M+10-M 50M+600表3-12 换基迭代后的单纯形

11、表2第23页/共57页cj -2 -3 0 0 0 -M -MCBXBx1x2x3x4x5x6x7b-301-20-120100-210101-10250000111-1-1125cj-zj0 0-40-14-M-M800表3-13 最优单纯形表3最优解：x1=250,x2=100,x3=0,x4=125,x5=0, Z*= 800第24页/共57页第25页/共57页无可行解在大M法中判断:检验数全部小于等于零且有人工变量为基变量，则此线性规划模型无可行解。引入松弛变量x3，x4，剩余变量x5，人工变量a，可得上述标准型。 121211212max203031015030. .40,0zxxx

12、xxstxxx x例如：121231412512345max203031015030. .40,0zxxMaxxxxxstxxxax x x x x a由此得到初始单纯形表第26页/共57页2030000-MCBXBx1x2x3x4x5ab 0 x33101000150 150 x410010030-Ma1100-114040cj-zj20+M 30+M00-M030 x2010.1-0.300620 x110010030-Ma00-0.1-0.7-114cj-zj00-3-0.1M-11-0.7M-M0由检验数全部0，可判定但前解应为最优解，但在基变量中，有不为0 的人工变量，说明没有可行解

13、。第27页/共57页12121230,640, (3063640)xxLPxxxx代入可行域，但不满足不等式。0102030504010203040D1D2x2x13x1+10 x2=150 x1+x2=40 x1=300,300,4021121xxxxx0,3015010321121xxxxx第28页/共57页3.8.2 两阶段法 第一阶段：希望人工变量等于0，为此，构造只含人工变量的目标函数，并要求实现最小化。1312312323123max3421. .39,0Zxxxxxxxxstxxx x x 【例3-8】 用两阶段法求解线性规划模型M在计算机上处理困难。分阶段处理先求初始基，再求解

14、。第29页/共57页 用单纯形法求解上述模型，若得到W=0,则必有x6=x7=0。说明原问题存在基可行解，可以进行第二阶段计算，否则原问题无可行解，应停止计算。1312312323123max3421. .39,0Zxxxxxxxxstxxx x x 67123412356237min421. .390,1,2,7jWxxxxxxxxxxxstxxxxj第30页/共57页 第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目标函数换为原问题的目标函数，作为第二阶段计算的初始表，继续单纯形法 ，直至求得最优解。仍以【例3-8】来说明两阶段法。其运算过程如下：第一阶段：671234123562

15、37min421. .390,1,2,7jWxxxxxxxxxxxstxxxxj第31页/共57页cj 0 0 0 0 0 -1 -1CBXBx1x2x3x4x5x6x7b0 x411110004-1x6-21-10-1101-1x703100019cj-zj-2 400-100 104130 x430211-103-21-10-1101-1x760403-316cj-zj6 0403-40 6表3-14 第一阶段单纯形法求解过程第32页/共57页cj 0 0 0 0 0 -1 -1CBXBx1x2x3x4x5x6x7b0 x430211-103-21-10-1101-1x760403-316

16、cj-zj6 0403-40 61-10 x40000-1/2 1/2-1/20011/30001/33102/301/2 -1/21/61cj-zj0 0000-1-1 0 第一阶段有最优解，原问题有基可行解。第33页/共57页cj 0 0 0 0 0-1-1CBXBx1x2x3x4x5x6x7b0 x40000-1/2 1/2-1/200011/30001/330102/301/2 -1/21/61cj-zj0 0000-1-1 第二阶段，将表中的人工变量x6，x7除去，目标函数改为12345max3000Zxxxxx 第34页/共57页cj 0 0 0 0 0-1-1CBXBx1x2x3

17、x4x5x6x7b0 x40000-1/2 1/2-1/200011/30001/330102/301/2 -1/21/61cj-zj0 0000-1-1 第二阶段初表cj-3 0 1 0 0 CBXBx1x2x3x4x5b0 x40000-1/200011/3003-3102/301/21cj-zj0 0303/2 3第35页/共57页cj-3 0 1 0 0 CBXBx1x2x3x4x5b0 x40000-1/200 x2011/3003-3x1102/301/21cj-zj0 0303/2 30 x40001-1/200 x2-1/2100-1/45/213/20103/43/2cj-z

18、j-9/2 000-3/4 -3/2 最优解：X=（0，5/2，3/2，0，0）T，Z*= 3/293/2第36页/共57页【例】 用两阶段法求解线性规划模型12123123123min221. .26,0Zxxxxxstxxxx x x 无可行解在两阶段法中判断:如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原LP问题无可行解。第37页/共57页12123123123min221. .26,0Zxxxxxstxxxx x x 121234123512345max221. .26,0Zxxxxxxstxxxxx x x x x 转换一般的线性规划模型

19、为标准型第一阶段：构造辅助线性规划问题 6712346123571234567min21. .26,0Wxxxxxxxstxxxxxx x x x x x x第38页/共57页因为所有检验数全为非正，而minw=7 0, 所以原问题无可行解，从而没有最优解。C00000-1-1bCBXBX1X2X3X4X5X6X7-1X6 -1 2-1-10101-1X7-1 -2 1 0-101 6-200-1-100-7第39页/共57页第4章 对偶模型第40页/共57页4.1 对偶模型的提出4.1.1 实际角度对偶模型的提出 产品产品资源资源A B资源限制资源限制甲甲1190乙乙52490丙丙26240

20、利润利润/元元68 【例4-1】某厂用甲、乙、丙三种原料生产A和B两种产品，每种产品耗用的各种原料、利润以及原料库存如表4-1所示，如何安排生产使得在现有条件下获得利润最多?第41页/共57页1212121212max68905249026240,0Zxxxxxxxxx x求解得：x1=75，x2=15。最优值为570。 现在从另一个角度讨论这一问题，假设该企业决策者决定不生产这两种产品，而将其资源出租，问题是对每种资源如何定价？出让代价应不低于用同等数量的资源自己生产的利润。第42页/共57页 生产一单位A产品所用的甲、乙、丙资源出让所得的净收入（售价扣除资源的买入价）应不低于生产一单位A产

21、品的利润，有123526yyyy1 y2 y3 设用y1,y2,y3分别表示出让甲、乙、丙三种资源的附加额。做定价策略时，应比较： 产品产品资源资源A B资源限制资源限制甲甲1190乙乙52490丙丙26240利润利润/元元68第43页/共57页 同理，生产一单位B产品所用的甲、乙、丙资源出让所得的净收入应不低于生产一单位B产品的利润，123268yyyy1 y2 y3 产品产品资源资源A B资源限制资源限制甲甲1190乙乙52490丙丙26240利润利润/元元68第44页/共57页把企业甲、乙、丙资源都出让，其收入为：12390490240Wyyy企业能接受的条件：123123526268y

22、yyyyy支付方的意愿：123min90490240Wyyy从支付者看,越少越好 只能在满足所有产品的利润的条件下,其总收入尽可能少,才能成交.第45页/共57页【例4-1】称为原问题。称为【例4-1】的对偶问题。 原问题 对偶问题1212121212max68905249026240,0Zxxxxxxxxx x123123123min904902405262680,1,2,3iWyyyyyyyyyyi123123123min904902405262680,1,2,3iWyyyyyyyyyyi第46页/共57页设原问题：max4 10ZCXAXbX加入松弛变量：max,0SSZCXAXIXbX

23、 X00NBCCbINBXB XN XSbBCBCNBCCbBBNBIBBBN1111110 XB XN XS当检验数11104 204 3004 4BBBNNBSBRCC B BRCC B NRC B 表示线性规划问题已得到最优解.4.1.2 理论角度对偶模型的提出第47页/共57页令,BCYB1称它为单纯形乘子。0Y由(4-2)和(4-3),有,ABCCB01故有CYA 11104 204 3004 4BBBNNBSBRCC B BRCC B NRC B 则由(4-4)有第48页/共57页因为1,BZC B bYb而Y的上限无限大,所以只存在最小值。由上讨论,可得另一个线性规划问题:min

24、450WYbYACY 称为原线性规划问题 的对偶规划问题。0X,bAXCXZmax第49页/共57页 由式(4-1) 、(4-5)可看出，原线性规划模型和它的对偶模型的系数矩阵A、C、b就之间有紧密的联系。max0ZCXAXbXmin0WYbYACY原问题：对偶问题：min450WYbYACYmax4 10ZCXAXbX一对对偶问题第50页/共57页4.2 原模型与对偶模型的线性规划模型之间的关系定义1 具有下列特点的线性规划模型称为对称形式的线性规划模型，变量均具有非负约束，其约束条件为当目标函数求最大时取“”、目标函数求最小时取“”。4.2.1 对称形式线性规划模型的对偶模型第51页/共57页1 12211 112