运筹学基础线性规划.ppt

1上节小结：利用大M法和两阶段法求解线性规划试用：(一)大M法、(二)两阶段法求解上述线性规划模型0,46278102132121321xxxxxxxxxxZMin线性规划2（一）大M法求解线性规划模型化线性规划模型为标准型线性规划minZ=10x1+8x2+7x32x1+x2≥6x1+x2+x3≥4x1,x2,x3≥0S.t.maxZ’=－10x1－8x2－7x32x1+x2－x4+x5=6+0x4－Mx5x1+x2+x3－x6+x7=4+0x6－Mx7x1,x2,x3,x4,x5,x6,x7≥03试用大M法求解～～00-7-8-10401116-1012-M010-10-M1010M-M-7+M-8+2M-10+3M401116-1012001-M-100101/2M-5-7+M-3+1/2M011/211/203-1/201/215-3/2M-1/21/2-M-10010M+30线性规划maxZ’=－10x1－8x2－7x32x1+x2－x4+x5=6+0x4－Mx5x1+x2+x3－x6+x7=4+0x6－Mx7x1,x2,x3,x4,x5,x6,x7≥04～-3/201/2011/211/203-1/201/213/2-M-1/21/2-7-107-M1037-2-100212102-1-1012-M-11-6-216-M2-136～令x3=x4=x5=x6=x7=0得x1=2,x2=2,即X0=(2,2,0,0,0,0,0)Tσj0此解最优max（-Z’）=36，从而得minZ=36线性规划5（二）两阶段法这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。0x,x,x1xx23x2xx411xx2xxxx3ZMin3213132132132176xxZMin第一阶段3213'xxxZMax第二阶段0,,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax第一阶段是先求以人工变量等于0为目标的线性规划问题第二阶段利用已求出的初始基可行解来求原问题最优解。无解目的未达到：则原问题原问题的可行解目的达到：则所求解为线性规划6试用两阶段法求解如下线性规划问题解：先划线性规划模型为标准型0x,x,x1xx23x2xx411xx2xxxx3ZMin3213132132132176xxWMax化为标准型76xxZMin第一阶段0,,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax0,,1232411271731653214321xxxxxxxxxxxxxx线性规划7初等变换0-10000-W11010-2030021-4011011-21000-10-1010～0,,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin40031-6-W11010-2030021-4011011-210-10-100010-Z’x1x2x3x4x5x6x7b线性规划8～～0-10000-W11010-201-20010012-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010进行第二阶段的计算将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。321xxx3ZMin3213'xxxMaxZ化为标准型3-1-10030-10-111000-12此时求解不是最优，继续迭代令x5=x6=x7=0，得最优解X=(0,1,1,12,0)T，minW=0。因人工变量x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计算。-Z’线性规划9～～0-10000-W11010-201-20010012-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010进行第二阶段的计算将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。321xxx3ZMin3213'xxxMaxZ化为标准型3-1-10030-10-111000-12此时求解不是最优，继续迭代令x5=x6=x7=0，得最优解X=(0,1,1,12,0)T，minW=0。因人工变量x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计算。-Z’线性规划10～2-30001-Z’11010-201-20010012-110030-10-1-20010接上表-2-3-1/3000-Z’912/310001-2001004-11/30010-1/3-4/3-1-2/30010～σj0，x4=0,x5=0,x1=4,x2=1,x3=9,即X0=(4,1,9,0,0)T，此时最优解–Z’=-2而maxZ’=2则minZ=-2线性规划11【另例】试用两阶段法求解MinZ=10x1+8x2+7x32x1+x2≥6x1+x2+x3≥4x1,x2,x3≥0S.t.maxZ=－10x1－8x2－7x3－Mx5－Mx72x1+x2－x4+x5=6x1+x2+x3－x6+x7=4x1,x2,x3,x4,x5,x6,x7≥0线性规划12～0,,4627176321542175xxxxxxxxxxxxxZMin～00000-Z’4011106-10120-1010-10-11010-1123-Z’4011106-10120001-1-100101/211/20-Z’11/211/2003-1/201/210-3/2-1/21/2-1-10010175'xxMaxZ第一阶段规划求解线性规划13～0000-Z11/211/2003-1/201/210-1-1/21/20-10-1100～令x3=x4=x6=0得x1=2,x2=2,此解最优max-Z’=36σj0-Z’-10-8-70-3/201/20-Z’11/211/2003-1/201/2101/2-1/21/2-7-10-11037～-2-100-Z’2121002-11-10101/2-1/21/2-6-21-11036从而得minZ=36321x7x8x10ZMinσj0321x7x8x10'ZMax第二阶段规划求解第一阶段规划最优线性规划14四、单纯形法补遗进基变量相持：–单纯形法运算过程中，同时出现多个相同的j最大。–在符合要求的j(目标为max：j＞0，min：j＜0)中，选取下标最小的非基变量为换入变量；离基变量相持：–单纯形法运算过程中，同时出现多个相同的最小θ值。–继续迭代，便有基变量为0，称这种情况为退化解。–选取其中下标最大的基变量做为换出变量。多重最优解：–最优单纯形表中，存在非基变量的检验数j=0。–让这个非基变量进基，继续迭代，得另一个最优解。无界解：–在大于0的检验数中，若某个k所对应的系数列向量Pk′≤0，则此问题是无界解。无可行解：–最终表中存在人工变量是基变量。线性规划15解的判别：情况1—无穷最优解Cj比值CBXBb检验数j0x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Maxz=2x1+4x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2,x3≥0标准化Maxz=2x1+4x2+0x3+0x4+0x5+0x62x1+2x2+x3=12x1+2x2+x4=84x1+x5=164x2+x6=12x1,…,x6≥00400012400001281612线性规划16迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-200.510010-0.5X3X1X5X20204000-4124-432010000.25000-2002288j0令x4=0，x6=0，得x1=2，x2=8，x3=2，x5=8即X0=(2,8,2,0,8,0)T此时Z＝2×2+4×8=36是最优解线性规划17再次迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-1-0.25010000.250X3X1X6X20204000-20.510100.5-0.1250000-1.5000447j0令x4=0，x5=0，得x1=4，x2=7，x3=0，x6=4即X0=(4,7,0,0,0,4)T此时Z＝2×4+4×7=36也是最优解结论：非基变量检验数有为0的，此线性规划有无穷多个解两最优解对应可行域两顶点，两点间连线上的点都是最优解线性规划18解的判别：情况2—解无界maxZ=2x1+3x2+0x34x1+x3=16x1,x2,x3≥0Cj比值CBXBb检验数jx1x2x323016401230x30确定x2进基，但x2所在列的系数为0，x2可以任意增大，解无界Maxz=2x1+3x24x1≤16x1,x2≥0说明此线性规划解无界线性规划19另例maxZ=5x1+6x2+0x3–Mx4+0x52x1-x2-x3+x4=2-2x1+3x2+x5=2x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数jx1x2x3x4x5560-M022-1-1102-23001X4X5-M0Maxz=5x1+6x22x1-x2≥2-2x1+3x2≤2x1,x2≥0560-M0检验数j5+2M6-M-M0011-1/2-1/21/20402-111-5017/25/2-M+5/20线性规划20Cj比值CBXBb检验数jx1x2x3x4x5560-M0210-3/43/41/4201-0.50.50.5X1X256560-M00027/4-M+27/4-17/4确定x3进基，但x3所在列的系数为负，此时解无界结论：入基变量系数均≤0的，该问题目标函数无界线性规划21解的判别：情况3—无解maxZ=3x1+2x2-2x1+x2≥2x1-3x2≥3x1,x2≥0S.t.•标准化maxZ=3x1+2x2-Mx5-Mx6-2x1+x2-x3+x5=2x1-3x2-x4+x6=3x1,x2,x3,x4≥0Cj比值CBXBb检验数j3200-M-Mx5x6-M-M此时检验数j0，无进基变量,但x5,x6还没有替换出去。Z不能达到最优说明此线性规划无解x1x2x3x4x5x62-21-101031-30-1013200-M-M检验数jx5x62-21-101031-30-1012M3-2M2+M-M00-M5M3-M2-2M-M-M0000结论：人工变量仍为基变量的，该问题无解线性规划22图示：无解maxZ=3x1+2x2-2x1+x2≥2x1-3x2≥3x1,x2≥0S.t.x1x22462460说明此线性规划无解线性规划23五、单纯形法的矩阵计算求解用矩阵描述的线性规划的标准形式为：0maxXbAXCXZ求解bBb1'pBp1'或NBCCBNN1'问题：B和B-1是什么？，待后讨论线性规划24单纯形法小结1、由实际问题给出数学模型，列出初始单纯形表，进行标准化变量xj≥0xj≤0xj无约束不需要处理令xj'=-xj；xj'≥0令xj=-xj'-