1、1 1上节小结：利用大上节小结：利用大M法和两阶段法求解线性规划法和两阶段法求解线性规划试用：试用：(一一)大大M法、法、(二二)两阶段法求解上述线性规划模型两阶段法求解上述线性规划模型0,46278102132121321xxxxxxxxxxZMin线性规划2 2n 化线性规划模型为标准型化线性规划模型为标准型线性规划minZ=10 x1+8x2+7 x3 2x1+x2 6 x1 +x2+x3 4 x1,x2,x30S.t.maxZ=10 x1 8x2 7x32x1+x2 x4+x5=6+0 x4Mx5x1 +x2+x3 x6+x7=4+0 x6Mx7x1,x2,x3,x4,x5,x6,x7
2、 03 300-7-8-10401116-1012 -M010-10-M 1 010M-M -7+M -8+2M-10+3M401116-1012001-M-100 1 01/2M-5 -7+M -3+1/2M 011/211/203-1/201/21 5-3/2M-1/21/2-M-100 1 0M+30线性规划4 4-3/2 0 1/2 011/211/203-1/201/21 3/2-M-1/21/2-7-107-M 1 037-2 -1 0 0212102-1-1012-M-11-6-216-M 2-136线性规划5 5 这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行
3、求解。0 x,x,x1xx23x2xx411xx2xxxx3ZMin3213132132132176 xxZMin第一阶段3213xxxZMax第二阶段0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax第一阶段是先求以人工变量等于0为目标的线性规划问题第二阶段利用已求出的初始基可行解来求原问题最优解。无解目的未达到：则原问题原问题的可行解目的达到：则所求解为线性规划6 6解：先划线性规划模型为标准型 0 x,x,x1xx23x2xx411xx2xxxx3ZMin3213132132132176xxWMax化为标准型76 x
4、xZMin第一阶段0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax0,1232411271731653214321xxxxxxxxxxxxxx线性规划7 70-10000-W11010-2030021-4011011-21000-10-10100,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin40031-6-W11010-2030021-4011011-210-10-100010-Z x1 x2 x3 x4 x5 x6 x7 b线性规划8 80-10000-W 1
5、1010-20 1-200100 12-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。321xxx3ZMin3213xxxMaxZ化为标准型 3 -1 -1 0 0 3 0 -1 0 -1 1 1 0 0 0 -1 2 令令x5=x6=x7=0，得最优解，得最优解X=(0,1,1,12,0)T，minW=0。因人工变。因人工变量量 x6=x7=0,所以是原问题的基可行解。
6、于是可以开始第二阶段的计所以是原问题的基可行解。于是可以开始第二阶段的计算。算。-Z-Z线性规划9 90-10000-W 11010-20 1-200100 12-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。321xxx3ZMin3213xxxMaxZ化为标准型3 -1 -1 0 0 3 0 -1 0 -1 1 1 0 0 0 -1 2 令令x5=x6=x7=0，得最优
7、解，得最优解X=(0,1,1,12,0)T，minW=0。因人工变。因人工变量量 x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计所以是原问题的基可行解。于是可以开始第二阶段的计算。算。-Z-Z线性规划10102-30001-Z11010-201-20010012-110030-10-1-20010-2-3-1/3000-Z912/310001-2001004-11/30010-1/3-4/3-1-2/30010线性规划1111MinZ=10 x1+8x2+7 x3 2x1+x2 6 x1+x2+x3 4 x1,x2,x3 0S.t.maxZ=10 x1 8x2 7 x3 M
8、x5 M x7 2x1+x2 x4+x5=6 x1+x2+x3 x6+x7=4 x1,x2,x3,x4,x5,x6,x7 0线性规划12120,4627176321542175xxxxxxxxxxxxxZMin00000-Z4011106-10120 -1010-10-1 1 010-1 1 2 3-Z4011106-10120001-1-100 1 01/2 1 1/2 0-Z11/211/2003-1/201/210-3/2-1/21/2-1-100 1 0175xxMaxZ第一阶段规划求解第一阶段规划求解线性规划 13130 00 0-Z11/211/2003-1/201/210-1-1
9、/21/20-10-1 1 00-Z -10 -8 -7 0 -3/2 0 1/2 0 -Z11/211/2003-1/201/2101/2-1/21/2-7-10-1 1 037-2-1 0 0 -Z2121002-11-10101/2-1/21/2-6-21-1 1 036321x7x8x10ZMin321x7x8x10 ZMax第二阶段规划求解第二阶段规划求解第一阶段规划最优第一阶段规划最优线性规划1414单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取为换入变量；单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为
10、0，称这种情况为。选取其中下标做为换出变量。多重最优解：多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：无界解：在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解。无无可行解：可行解：最终表中存在人工变量是基变量。线性规划1515 解的判别：情况解的判别：情况1无穷最优解无穷最优解Cj比值CBXBb检验数j0 x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Max z=2x1+4x2 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1,
11、x2,x3 0标准化标准化 Max z=2x1+4x2+0 x3+0 x4+0 x5+0 x6 2x1+2x2+x3 =12 x1+2x2+x4 =8 4x1 +x5 =16 4x2 +x6=12 x1,x600400012400001281612线性规划1616 迭代结果迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-200.5 1 0 0 1 0-0.5X3X1X5X20204000-4124-432010000.25000-2002288j0线性规划1717 再次迭代结果再次迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x62400000
12、01-1-0.25 0 1 0000.25 0X3X1X6X20204000-20.5 1 0 100.5-0.125 0000-1.50 00447j0线性规划1818 解的判别：情况解的判别：情况2 解无界解无界maxZ=2x1+3x2+0 x3 4x1 +x3 =16 x1,x2,x30Cj比值CBXBb检验数jx1x2x323016401230 x30确定x2进基，但x2所在列的系数为0，x2可以任意增大，解无界Max z=2x1+3x2 4x1 16 x1,x2 0线性规划1919 另例另例maxZ=5x1+6x2+0 x3 Mx4+0 x5 2x1-x2-x3+x4 =2 -2x1
13、+3x2 +x5=2 x1,x2,x3,x4,x50Cj比值CBXBb检验数jx1x2x3x4x5560-M022-1-1102-23001X4X5-M0Max z=5x1+6x2 2x1-x2 2-2x1+3x2 2 x1,x2 0560-M0检验数j5+2M6-M-M0011-1/2-1/21/20402-11 1-5017/25/2-M+5/20线性规划2020Cj比值CBXBb检验数jx1x2x3x4x5560-M0210-3/4 3/41/42 01-0.50.50.5X1X256560-M00 0 27/4-M+27/4-17/4确定x3进基，但x3所在列的系数为负，此时解无界线性
14、规划 2121 解的判别：情况解的判别：情况3无解无解maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.标准化标准化 maxZ=3x1+2 x2-M x5-M x6-2x1+x2-x3 +x5=2 x1-3 x2 -x4+x6=3 x1,x2,x3,x4 0Cj比值CBXBb检验数j3200-M-Mx5x6-M-M 此时检验数j00计算计算q qi i=b=bi i/a/aikik令令q q=min(=min(q qi i)所有所有 j j0 0是是否否计算非基变量计算非基变量各列的检验数各列的检验数 j j否否某非基变量某非基变量检验数为零检验数为零否
15、否唯一唯一最优解最优解对任一对任一 j j00有有P Pj j0是是无界解无界解无可行解无可行解是是是是无穷多最优解无穷多最优解是是迭代运算迭代运算线性规划2626六、用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变
16、量的单元格为可变单元格，建立约束条件。（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。线性规划2727 利用EXCEL求线性规划的步骤线性规划2828 利用EXCEL求线性规划的步骤 maxZ=3x1+5x2 x1 8 2x2 12 3x1+4 x2 36 x1、x2 0线性规划2929 利用EXCEL求线性规划的步骤注：注：sumproductsumproduct表示对应乘积之和表示对应乘积之和调用函数调用函数sumproductsumproduct定义实际值定义实际值 （E2E2：E5E5）线性规划3030 利用EXCEL求线性规划的步骤线性规划313
17、1 利用EXCEL求线性规划的步骤线性规划3232 利用EXCEL求线性规划的步骤最优解为：最优解为：x x1 1=4,x=4,x2 2=6=6 maxZmaxZ=42=42线性规划3333由下表数据，列出使总利润最大的生产计划模型，并求利润最大的生产方案kg/件材料A材料B材料C利润产品甲52412元/件产品乙2328元/件资源量150kg100kg80kgmaxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0令产品甲的产量为x1,产品甲的产量为x2,得如下线性规划模型线性规划3434maxZ=12 x1+8 x2 5x1
18、+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0maxZ=12 x1+8 x2 5x1+2 x2+x3 =150 2 x1+3 x2 +x4 =100 4x1+2 x2 +x5=80 x1,x2,x3,x4,x50答案：答案：x1=5，x2=30，max z=300提示：可在提示：可在EXCEL上模拟单纯形法的迭代过程上模拟单纯形法的迭代过程线性规划3535练习：利用练习：利用EXCEL求解线性规划求解线性规划0,46278102132121321xxxxxxxxxxZMin线性规划无限制321321321321321x,0 x,x)3(5x2xx3)2(2xxx)1(7xxxx3x2xZMin
