《运筹学资料1线性规划优秀课件》由会员分享，可在线阅读，更多相关《运筹学资料1线性规划优秀课件（88页珍藏版）》请在金锄头文库上搜索。
1、 1-4 1-4 线性规划线性规划- -单纯形进一步讨论（单纯形进一步讨论（2 2）三、无初始可行基求最优解三、无初始可行基求最优解人工变量法人工变量法大大M M法法两阶段法两阶段法运筹学资料1线性规划优秀大大M M法法 大大M M法是一种惩罚方法，它是处法是一种惩罚方法，它是处理人工变量的一种简便方法。理人工变量的一种简便方法。 在通过人工变量构造初始基本变在通过人工变量构造初始基本变量以后，假定人工变量在目标函数中量以后，假定人工变量在目标函数中的系数为的系数为M M（M M为任意大的正数）作为为任意大的正数）作为对基变量中存在人工变量的惩罚，迫对基变量中存在人工变量的惩罚，迫使人工变量成
2、为非基变量，即取值为使人工变量成为非基变量，即取值为零。原问题才能达到最优。零。原问题才能达到最优。运筹学资料1线性规划优秀例例1-16 用大用大M法求下列问题法求下列问题 min z = -3x1 + x2 + x3 s.t. X1-2x2 + x3 11 -4x1+ x2 + 2x3 3 - 2x1 + x3 = 1 x1,x2 , x3 0运筹学资料1线性规划优秀解：将问题化成标准形式解：将问题化成标准形式max S = 3x1 - x2 - x3 - M x6 - M x7 s.t. X1-2x2 + x3 + x4 = 11 -4x1+ x2 + 2x3 x5 + x6 = 3 -
3、2x1 + x3 + x7 = 1 x1,x2 , x3 , x4 , x5, x6 , x7 0 M是任意大的正数是任意大的正数运筹学资料1线性规划优秀初始基本可行解：初始基本可行解：X（0）=（0，0， 0，11，0，3，1）tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-20100011 -4M运筹学资料1线性规划优秀B1=（P4，P6，P7）=IC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-20100011 -4M运筹学资料1线
4、性规划优秀检验数检验数 3=3M-10,X3为进基变量为进基变量C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-21100011-MX6-4120-1103-MX7-201000113-6M M-1 3M-1 0 -M 0 0 -4M运筹学资料1线性规划优秀计算最小比值：计算最小比值：X7为出基变量，为出基变量，主元为主元为（1）C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X41-2110001111-MX6-4120-11033/2-MX7-20(1)0001113-6M M-1 3M-1 0 -M 0 0 -4M运筹学资料1线性规划优秀第一行加上
5、第三行的（第一行加上第三行的（-1）倍）倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110 -MX6-4120-1103 -1X3-20(1)00011 运筹学资料1线性规划优秀第二行加上第三行的（第二行加上第三行的（-2）倍）倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110 -MX60100-11-21 -1X3-20(1)00011 运筹学资料1线性规划优秀得到新的基本可行解：得到新的基本可行解：X（1）=（0，0，1，10，0，1，0）tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X
6、43-20100-110 -MX60100-11-21 -1X3-20(1)00011 -M-1 运筹学资料1线性规划优秀计算检验数计算检验数C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43-20100-110- -MX60(1)00-11-211 -1X3-20(1)00011- 1 M-1 0 0 -M 0 1-3M -M-1 运筹学资料1线性规划优秀 第一行加第二行第一行加第二行2倍倍C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43001-22-512 -1X20 1 00-11-21 -1X3-20 1 00011 运筹学资料1线性规划优秀得
7、到新的基本可行解：得到新的基本可行解：X（2）=（0，1，1，12，0，0，0）tC3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X43001-22-512 -1X20 1 00-11-21 -1X3-20 1 00011 1 0 0 0 -1 1-M -M-1 -2运筹学资料1线性规划优秀C3-1-100-M-MCBXBX1X2X3X4X5X6X7b0X4(3)001-22-5124 -1X20 1 00-11-21- -1X3-20 1 00011- 1 0 0 0 -1 1-M -M-1 -2运筹学资料1线性规划优秀C3-1-100-M-MCBXBX1X2X3X4X5X6
8、X7b3X1(3)001-22-512 -1X20 1 00-11-21 -1X3-20 1 00011 1 0 0 0 -1 1-M -M-1 -2第一行乘1/3运筹学资料1线性规划优秀C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X1(1)001/3-2/32/3-5/34 -1X20 1 00-11-21 -1X3-20 1 00011 1 0 0 0 -1 1-M -M-1 -2第一行乘1/3运筹学资料1线性规划优秀C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X1(1)001/3-2/32/3-5/34 -1X20 1 00-11-21 -1X30
9、0 1 2/3-4/34/3-7/39 第三行加第一行第三行加第一行2倍倍运筹学资料1线性规划优秀C3-1-100-M-MCBXBX1X2X3X4X5X6X7b3X11001/3-2/32/3-5/34 -1X20 1 00-11-21 -1X300 1 2/3-4/34/3-7/39 0 0 0 -1/3 -1/3 1/3-M 2/3-M 2 得到新的基本可行解：得到新的基本可行解：X（3）=（4，1，9，0，0，0，0）t最优值最优值 S=2 Z = -2运筹学资料1线性规划优秀例例1-17 用大用大M法求下列问题法求下列问题 max S = 6x1 +4x2 s.t. 2x1+3x2 1
10、00 4x1+2x2 120 x1 = 14 x2 22 x1,x2 0运筹学资料1线性规划优秀解：将问题化成标准形式解：将问题化成标准形式max S = 6x1 + 4x2 s.t. 2x1+3x2 +x3 = 100 4x1+2x2 +x4 = 120 x1 = 14 x2 - x5 = 22 x1,x2 , x3,x4 ，x5 0运筹学资料1线性规划优秀解：引入人工变量解：引入人工变量, x6 0， x7 0max S = 6x1 + 4x2 -Mx6 -Mx7 s.t. 2x1+3x2 +x3 = 100 4x1+2x2 +x4 = 120 x1 +x6 = 14 x2 - x5 +x
11、7 = 22 x1,x2 , x3,x4 , x5 , x6 ,x7 0B1=（P3，P4，P6，P7）=I运筹学资料1线性规划优秀初始基本可行解：初始基本可行解：X（0）=（0，0，100，120，0，14，22）tC64000-M-MCBXBX1X2X3X4X5X6X7b0X323100001000X44201000120-MX6100001014-MX70100-10122 -36M运筹学资料1线性规划优秀B1=（P3，P4，P6，P7）=IC64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100 0X44201000120 -MX6100001014 -MX
12、70100-10122 运筹学资料1线性规划优秀检验数检验数 1=6+M0,X1为进基变量为进基变量C64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100 0X44201000120 -MX6(1)00001014 -MX70100-10122 6+M4+M00-M00-36M运筹学资料1线性规划优秀计算最小比值：计算最小比值：X6为出基变量，为出基变量，主元为主元为（1）C64000-M-MCBXBX1X2X3X4X5X6X7b0X32310000100 50 0X44201000120 30 -MX6(1)0000101414 -MX70100-10122-
13、6+M4+M00-M00-36M运筹学资料1线性规划优秀第一行加上第三行的（第一行加上第三行的（-2）倍）倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072 0X44201000120 6X1(1)00001014 -MX70100-10122 -36M运筹学资料1线性规划优秀第二行加上第三行的（第二行加上第三行的（-4）倍）倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072 0X402010-4064 6X1 1 00001014 -MX70100-10122 运筹学资料1线性规划优秀得到新的基本可行解：得到新的基本可行
14、解：X（1）=（14，0，72，64，0，0，22）tC64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-2072 0X402010-4064 6X1 1 00001014 -MX70100-10122 运筹学资料1线性规划优秀X2的检验数大于零，的检验数大于零， X2进基变量进基变量X7为最小比值，为最小比值，X7为出基变量，主元为出基变量，主元（1）C64000-M-MCBXBX1X2X3X4X5X6X7b0X303100-207224 0X402010-406432 6X1 1 00001014- -MX70(1)00-1012222 0 4+M 0 0 -M -
15、M-60 运筹学资料1线性规划优秀第一行加上第四行的（第一行加上第四行的（-3）倍）倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36 0X402010-4064 6X1 1 00001014 4X20(1)00-10122 运筹学资料1线性规划优秀第二行加上第四行的（第二行加上第四行的（-2）倍）倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36 0X400012-4-220 6X1 1 00001014 4X20 1 00-10122 172运筹学资料1线性规划优秀主元运算，得到新的基本可行解：主元运算，得到新的基本可
16、行解：主元运算，得到新的基本可行解：主元运算，得到新的基本可行解：X X（2 2）= =（1414，2222，6 6，2020，0 0，0 0，0 0）t tC64000-M-MCBXBX1X2X3X4X5X6X7b0X300103-2-36 0X400012-4-220 6X1 1 00001014 4X20 1 00-10122 172运筹学资料1线性规划优秀X5的检验数大于零，的检验数大于零， X5进基变量进基变量X3为最小比值，为最小比值，X3为出基变量，主元为出基变量，主元（3）C64000-M-MCBXBX1X2X3X4X5X6X7b0X30010(3)-2-362 0X40001
17、2-4-22010 6X1 1 00001014- 4X20 1 00-10122- 0 0 0 0 4 -M-6 -M-4 172运筹学资料1线性规划优秀第一行除以第一行除以3C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12 0X400012-4-220 6X1 1 00001014 4X20 1 00-10122 运筹学资料1线性规划优秀第二行加上第一行的（第二行加上第一行的（-2）倍）倍C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12 0X400-2/310-8/3016 6X1 1 00001014
18、 4X20 1 00-10122 运筹学资料1线性规划优秀第四行加上第一行第四行加上第一行C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12 0X400-2/310-8/3016 6X1 1 00001014 4X20 1 1/300-2/3024 180 运筹学资料1线性规划优秀 主元运算，得到新的基本可行解：主元运算，得到新的基本可行解：主元运算，得到新的基本可行解：主元运算，得到新的基本可行解：X X（3 3）= =（1414，2424，0 0，1616，2 2，0 0，0 0）t t为最优解，最优值为最优解，最优值为最优解，最优值为最优解，最优
19、值S= S= 180180C64000-M-MCBXBX1X2X3X4X5X6X7b0X5001/301-2/3-12 0X400-2/310-8/3016 6X1 1 00001014 4X20 1 1/300-2/3024 0 0 -4/3 0 0 -10/3-M -M 180 运筹学资料1线性规划优秀例例1-18 用大用大M法求下列问题法求下列问题 max S = x1 +x2 s.t. x1-x2 0 3x1-x2 -3 x1,x2 0运筹学资料1线性规划优秀解：将问题化成标准形式解：将问题化成标准形式 max S = x1 +x2 s.t. -x1 +x2 +x3 = 0 -3x1
20、-x2 -x4= 3 x1,x2 , x3 , x4 0运筹学资料1线性规划优秀解：引入人工变量解：引入人工变量, x5 0 max S = x1 +x2 - Mx5 s.t. -x1+x2 +x3 = 0 -3x1+x2 -x4 +x5 = 3 x1,x2 , x3,x4 , x5 0 B1=（P3，P5）=I运筹学资料1线性规划优秀B1=（P3，P5）=IX X（0 0）= =（0 0，0 0，0 0，0 0，3 3）t t运筹学资料1线性规划优秀计算检验数：计算检验数：运筹学资料1线性规划优秀计算检验数：最大的为计算检验数：最大的为X2，进基，进基变量变量运筹学资料1线性规划优秀计算最小
21、比值为计算最小比值为X3，出基变量，出基变量主元主元（1）运筹学资料1线性规划优秀第二行加上第一行的（第二行加上第一行的（-1）倍）倍运筹学资料1线性规划优秀主元运算：得到基础可行解主元运算：得到基础可行解X X（1 1）= =（0 0，0 0，0 0，0 0，3 3）t t运筹学资料1线性规划优秀计算检验数全小于零，但计算检验数全小于零，但 X X（1 1）= =（0 0，0 0，0 0，0 0，3 3）t t 人工变量不等人工变量不等于零，原问题无可行解。于零，原问题无可行解。运筹学资料1线性规划优秀两阶段法两阶段法第一阶段：引进人工变量，构造第一阶段：引进人工变量，构造辅助问题用单纯形法
22、求解，得到辅助问题用单纯形法求解，得到原问题的可行基。原问题的可行基。运筹学资料1线性规划优秀两阶段法两阶段法第一阶段：引进人工变量，构造第一阶段：引进人工变量，构造辅助问题用单纯形法求解，得到辅助问题用单纯形法求解，得到原问题的可行基。原问题的可行基。第二阶段：在第一阶段得到可行第二阶段：在第一阶段得到可行基对应的单纯形表上，去掉人工基对应的单纯形表上，去掉人工变量所在的行和列，再用单纯形变量所在的行和列，再用单纯形求解，得到原问题的最优解，或求解，得到原问题的最优解，或无最优解。无最优解。运筹学资料1线性规划优秀例例1-19 用两阶段法求下列用两阶段法求下列数学数学模型模型 min z=
23、-3x1 + x2 + x3 s.t. x1 -2x2 + x3 11 -4x1 +x2 +2x3 3 -2x1 + x3 = 1 x1,x2 , x3 0运筹学资料1线性规划优秀问题的数学模型标准型问题的数学模型标准型 max z= 3x1 - x2 - x3 s.t. x1 -2x2 + x3 + x4 = 11 -4x1 +x2 +2x3 x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0运筹学资料1线性规划优秀 第一阶段：第一阶段：构造辅助线性规划问题构造辅助线性规划问题 max = - x6 x7 s.t. x1 -2x2 + x3 + x4 = 11 -4x1
24、+x2 +2x3 x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0 x6, x7是人工变量。是人工变量。运筹学资料1线性规划优秀最大检验数最大检验数X3 进基变量进基变量计算最小比值计算最小比值X7出基变量出基变量主元为主元为（1）C C0 00 00 00 00 0-1-1-1-1 C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 41 1-2-21 1 1 10 00 00 011111111 -1-1X X6 6-4-41 1 2 2 0 0-1-11 10 03 33/2 3/2 -1
25、-1X X7 7 -2 -2 0 0(1)(1)0 00 00 01 11 1 1 1 -6-6 1 1 3 3 0 0 -1 -1 0 0 0 0 -4 -4 运筹学资料1线性规划优秀第一行加上第第一行加上第 三行的（三行的（-1）倍）倍C C0 00 00 00 00 0-1-1-1-1 C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 43 3-2-20 0 1 10 00 0-1-11010 -1-1X X6 6-4-41 1 2 2 0 0-1-11 10 03 3 0 0X X3 3 -2 -2 0 0
26、(1)(1)0 00 00 01 11 1 运筹学资料1线性规划优秀第二行加上第三行的（第二行加上第三行的（-2）倍）倍C C0 00 00 00 00 0-1-1-1-1 C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 43 3-2-20 0 1 10 00 0-1-11010 -1-1X X6 60 01 1 0 0 0 0-1-11 1-2-21 1 0 0X X3 3 -2 -2 0 0(1)(1)0 00 00 01 11 1 运筹学资料1线性规划优秀C C0 00 00 00 00 0-1-1-1-1
27、 C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 43 3-2-20 0 1 10 00 0-1-11010- - -1-1X X6 60 0(1(1) ) 0 0 0 0-1-11 1-2-21 11 1 0 0X X3 3 -2 -2 0 01 10 00 00 01 11 1 - - 0 0 1 1 0 0 0 0 -1 -1 0 0 -3 -3 -1 -1 运筹学资料1线性规划优秀计算检验数，确定进基变量计算检验数，确定进基变量X2，出基变量，出基变量X6 ，主元主元（1）C C0 00 00 00 00
28、 0-1-1-1-1 C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 43 3-2-20 0 1 10 00 0-1-11010- - -1-1X X6 60 0(1(1) ) 0 0 0 0-1-11 1-2-21 11 1 0 0X X3 3 -2 -2 0 01 10 00 00 01 11 1 - - 0 0 1 1 0 0 0 0 -1 -1 0 0 -3 -3 -1 -1 运筹学资料1线性规划优秀第一行加上第二行的第一行加上第二行的2倍倍 C C0 00 00 00 00 0-1-1-1-1 C CB
29、 BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7b b0 0X X4 43 30 00 0 1 1-2-22 2-5-51212 0 0X X2 20 0 1 1 0 0 0 0-1-11 1-2-21 1 0 0X X3 3 -2 -2 0 01 10 00 00 01 11 1 0 0 运筹学资料1线性规划优秀第一阶段求得最优解第一阶段求得最优解 =0X*=（0，1，1，12，0，0，0）是原问题）是原问题的基础可行解。的基础可行解。C C0 00 00 00 00 0-1-1-1-1b b C CB BX XB BX X1 1X X2
30、2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 43 30 00 0 1 1-2-22 2-5-51212 0 0X X2 20 0 1 1 0 0 0 0-1-11 1-2-21 1 0 0X X3 3 -2 -2 0 01 10 00 00 01 11 1 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 运筹学资料1线性规划优秀第二阶段：第二阶段：第一阶段最优表中去掉人第一阶段最优表中去掉人工变量所在的行和列，目标函数的系工变量所在的行和列，目标函数的系数填入原问题的系数，继续求解。数填入原问题的系数，继续求解。C C3 3-1-1-1
31、-10 00 0 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 43 30 00 0 1 1-2-2 1212 -1-1X X2 20 0 1 1 0 0 0 0-1-1 1 1 -1-1X X3 3 -2 -2 0 01 10 00 0 1 1 运筹学资料1线性规划优秀X1为进基变量，为进基变量，X4出基变量，主元出基变量，主元（3）C C3 3-1-1-1-10 00 0 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 4
32、(3)(3)0 00 0 1 1-2-2 12124 4 -1-1X X2 20 0 1 1 0 0 0 0-1-1 1 1- - -1-1X X3 3 -2 -2 0 01 10 00 0 1 1 - - 1 1 0 0 0 0 0 0 -1 -1 -2 -2 运筹学资料1线性规划优秀第一行乘以（第一行乘以（1/3）C C3 3-1-1-1-10 00 0 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 73 3X X1 1(1)(1)0 00 0 1/31/3 -2/3-2/3 4 4 -1-1X X2 20 0 1 1 0
33、 0 0 0-1-1 1 1 -1-1X X3 3 -2 -2 0 01 10 00 0 1 1 -2 -2 运筹学资料1线性规划优秀第三行加上第一行的（第三行加上第一行的（2）倍）倍C C3 3-1-1-1-10 00 0 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 73 3X X1 1 1 1 0 00 0 1/31/3 -2/3-2/3 4 4 -1-1X X2 20 0 1 1 0 0 0 0-1-1 1 1 -1-1X X3 3 0 0 0 01 12/32/3 -4/3-4/3 9 9 2 2 运筹学资料1线性规
34、划优秀计算检验数全部小于零，最优解计算检验数全部小于零，最优解X*=（4，1，9，0，0，0，0）C C3 3-1-1-1-10 00 0 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 73 3X X1 1 1 1 0 00 0 1/31/3-2/3-2/3 4 4 -1-1X X2 20 0 1 1 0 0 0 0-1-1 1 1 -1-1X X3 3 0 0 0 01 12/32/3-4/3-4/3 9 9 0 0 0 0 0 0 - -1/3 1/3 -1/3 -1/3 2 2 运筹学资料1线性规划优秀检验数全为非正，得
35、到原问题最优解：检验数全为非正，得到原问题最优解：X*=（4，1，9，0，0）t 最优值最优值 min z = -2运筹学资料1线性规划优秀例例1-20 用两阶段法求下列用两阶段法求下列数学数学模型模型 的解的解 min S= 2x1 + 8x2 s.t. 5x1+10x2 = 150 x1 20 x2 14 x1,x2 0运筹学资料1线性规划优秀问题的数学模型标准型问题的数学模型标准型 max S = -2x1 - 8x2 s.t. 5x1+10x2 = 150 x1 +x3 = 20 x2 - x4 = 14 x1,x2 , x3,x4 0运筹学资料1线性规划优秀 第一阶段：第一阶段：构造
36、辅助线性规划问题构造辅助线性规划问题 max = - x5 x6 s.t. 5x1+10x2 + x5 = 150 x1 + x3 = 20 x2 - x4 + x6 = 14 x1 , x2 , x3 , x4 , x5 , x6 0 x5 , x6是人工变量。是人工变量。运筹学资料1线性规划优秀C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5 5 5 5 10100 0 0 01 10 0 150150 0 0X X3 31 1 0 0 1 1 0 00 00 0 20
37、20 -1-1X X6 6 0 0 1 10 0-1-10 01 1 1414 运筹学资料1线性规划优秀最大检验数最大检验数X2，进基变量进基变量计算最小比值计算最小比值X6出基变量出基变量主元为主元为（1）C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5 5 5 5 10100 0 0 01 10 0 1501501515 0 0X X3 31 1 0 0 1 1 0 00 00 0 2020- - -1-1X X6 6 0 0 1 10 0-1-10 01 1 1414
38、1414 5 511110 0-1-10 00 0- -164164运筹学资料1线性规划优秀第一行减去第三行的第一行减去第三行的10倍倍C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5 5 5 5 0 00 0 10101 1-10 -10 10100 0X X3 31 1 0 0 1 1 0 00 00 0 20200 0X X2 2 0 0 1 10 0-1-10 01 1 1414 -10-10运筹学资料1线性规划优秀计算检验数计算检验数C C0 00 00 00 0
39、-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5 5 5 5 0 00 0 10101 1-10 -10 10100 0X X3 31 1 0 0 1 1 0 00 00 0 20200 0X X2 2 0 0 1 10 0-1-10 01 1 1414 5 50 00 010100 0-11-11-10-10运筹学资料1线性规划优秀C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5
40、5 5 5 0 00 0 10101 1-10 -10 10101 10 0X X3 31 1 0 0 1 1 0 00 00 0 2020- -0 0X X2 2 0 0 1 10 0-1-10 01 1 1414- - 5 50 00 010100 0-11-11-10-10运筹学资料1线性规划优秀C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-1-1X X5 5 1/2 1/2 0 00 0 1 11/101/10 -1 -1 1 10 0X X3 31 1 0 0 1 1 0 0
41、0 00 0 20200 0X X2 2 0 0 1 10 0-1-10 01 1 1414 第一行除以第一行除以10运筹学资料1线性规划优秀C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 60 0X X4 4 1/2 1/2 0 00 0 1 11/101/10 -1 -1 1 10 0X X3 31 1 0 0 1 1 0 00 00 0 20200 0X X2 2 1/2 1/2 1 10 00 01/101/100 0 1515 0 0第三行加第一行第三行加第一行运筹学资料1线性规划
42、优秀此时此时 Z=0 （0，15，20，1，0，0）是原问题的可行解。）是原问题的可行解。 C C0 00 00 00 0-1-1-1 -1 b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 60 0X X4 4 1/2 1/2 0 00 0 1 11/101/10 -1 -1 1 10 0X X3 31 1 0 0 1 1 0 00 00 0 20200 0X X2 2 1/2 1/2 1 10 00 01/101/100 0 1515 0 0运筹学资料1线性规划优秀第二阶段：第二阶段：去掉人工变量所在的去掉人工变量所在的行和列，继续求解。
43、行和列，继续求解。C C-2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 60 0X X4 4 1/21/2 0 00 0 1 11 12 20 0X X3 31 1 0 0 1 1 0 020202020-8-8X X2 2 1/2 1/2 1 10 00 015153030 2 20 00 00 0- -120120运筹学资料1线性规划优秀第一行乘第一行乘2C C-2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 60 0X X4 4
44、 1 1 0 00 0 2 22 20 0X X3 31 1 0 0 1 1 0 02020-8-8X X2 2 1/2 1/2 1 10 00 01515 运筹学资料1线性规划优秀第二行减第一行第二行减第一行C C-2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 60 0X X4 4 1 1 0 00 0 2 22 20 0X X3 30 0 0 0 1 1 -2-21818-8-8X X2 2 1/2 1/2 1 10 00 01515 运筹学资料1线性规划优秀第三行减第一行的第三行减第一行的1/2倍倍C C-
45、2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-2-2X X1 1 1 1 0 00 0 2 22 20 0X X3 30 0 0 0 1 1 -2-21818-8-8X X2 2 0 0 1 10 0-1-11414 - -116116运筹学资料1线性规划优秀计算检验数计算检验数C C-2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-2-2X X1 1 1 1 0 00 0 2 22 20 0X X3 30 0 0 0 1 1
46、 -2-21818-8-8X X2 2 0 0 1 10 0-1-11414 0 00 00 0-4-4- -116116运筹学资料1线性规划优秀检验数全为非正，得到最优解：检验数全为非正，得到最优解：X*=（2，14）t 最优值最优值S=-116 S = 116C C-2-2-8-80 00 0b b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6-2-2X X1 1 1 1 0 00 0 2 22 20 0X X3 30 0 0 0 1 1 -2-21818-8-8X X2 2 0 0 1 10 0-1-11414 0 00 00 0-4-
47、4- -116116运筹学资料1线性规划优秀例例1-21 用两阶段法求下列用两阶段法求下列数学数学 模型模型 min S= -x1 +2x2 s.t. x1- 2x2 +x3 -1 x1+2x2 - x3 -6 x1,x2 ,x3 0运筹学资料1线性规划优秀解：解： 把数学模型化成标准型：把数学模型化成标准型： max S = x1 - 2x2 s.t. -x1+2x2 - x3 -x4 = 1 -x1- 2x2 +x3 -x5 = 6 x1 , x2 , x3 , x4 , x5 0运筹学资料1线性规划优秀第一阶段：第一阶段：构造辅助线性规划问题构造辅助线性规划问题 max = - x6 x
48、7 s.t. -x1+ 2x2 - x3 -x4 +x6 = 1 -x1- 2x2 +x3 -x5 + x7 = 6 x1 , x2 , x3 , x4 , x5 , x6 , x7 0 x6 , x7是人工变量。是人工变量。 运筹学资料1线性规划优秀因为所有检验数全为非正，而因为所有检验数全为非正，而max = -7 0, 所以原问题无可行解，从而没有所以原问题无可行解，从而没有最优解。最优解。C C0 00 00 00 00 0-1-1-1-1b bC CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7-1-1X X6 6 -1 -1 2 2-1-1-1-10 01 10 01 1-1-1X X7 7-1-1 -2 -2 1 1 0 0-1-10 01 1 6 6 -2-20 00 0-1-1-1-10 00 0-7-7运筹学资料1线性规划优秀 运筹学资料1线性规划优秀
