第一章线性规划与单纯形法 图1-7 max=2x1+5.x2+0x+0x+0x 2x2+x4=12 s.t. 13x1+2.x2+x3=18 x1,x2,x3,x4,x3≥0 由线性规划问题的标准型可列出初始单纯形表逐步迭代，计算结果如表1一5所示。 表1一5 2 12 0 「21 一 2 0 0 0 4 0 5 [3 0 0 0 0 -5/2 0 1/3 0 1/2 0 0 13 1/3 0 0 -11/6-2/3 单纯形表的计算结果表明：X·=(2,6,2,0,0)T,=2×2+5×6=34 单纯形表迭代的第一步得X)=(0,0,4,12,18)T,表示图中原点(0,0) 单纯形表迭代的第二步得X”=(0,6,4,0,6)T,表示图中A:点。 单纯形表迭代的第三步得X2)=(2,6,2,0,0)T,表示图中Ag点。 小结单纯形法是求解线性规划问题最有效的方法之一，要求熟练掌握。 ○1.5以1.4题(1)为例，具体说明当目标函数中变量的系数怎样改变时，使满足约束条 件的可行域的每一个顶点，都有可能使目标函数值达到最优。 解由目标函数ax十可得：一4十-k十名其中=一号 (1)当k>0时，若c>0,则目标函数在A,点(0,3)取得最大值：若2<0，则目标函 ·15·
A*B !"#$%&’() E!8? %&’!*#&!2;+&$2+&/2+&; ,"-" &!2&$*/ #&/*!# $&!2#&;*!> &!$&#$&$$&/$&;$ % & ’ + gMN@OPQp&<=Y¿wI/¯ ¢$¹º©%$¯!8;µ’ ¯!8; %# # ; + + + 98 18 ) &! &# &$ &/ &; "( + &$ / ! + ! + + ) + &/ !# + /#0 + ! + = + &; !> $ # + + ! < %#8!# # ; + + + + &$ / ! + ! + + / ; &# = + ! + !-# + ) + &; = /$0 + + 8! ! # %#8!# # + + 8;-# + + &$ # + + ! !-$ 8!-$ ; &# = + ! + !-# + # &! # ! + + 8!-$ !-$ %#8!# + + + 8!!-= 8#-$ I/¯p¹º©%¯é#12 *!#$=$#$+$+"3$!2 *#:#2;:=*$/ I/¯¢pÒ- ¸ 1!+" *!+$+$/$!#$!>"3$¯E3sD!+$+"’ I/¯¢pÒg ¸ 1!!" *!+$=$/$+$="3$¯E37/ D’ I/¯¢pÒE ¸ 1!#" *!#$=$#$+$+"3$¯E37$ D’ OP I/G¥LFMN@OPQ}jªpGë-$:L«¬®’ *!$& Z!B/Q!!"4¯$°èéh%&’(3#$p7(±J²#R$Ñõö)*+ ,pYp+-©D$çjY0Ñ%&’(;}B’ ; g%&’( %&’!*%!&!2%#&# Y¸#&#*8%! %# &!2! %# *+&!2! %# $23+*8%! %# !!"h+(+R$¢%#(+$¤%&’(\7$ D!+$$"a¸}ä;&¢%#1+$¤%&’ (!%(
运筹学同步辅导及习题全解 数在A点(4,0)取得最大值。 (2)当一÷<k<0时，若c>0,则目标函数在A,点(0,3)取得最大值：若c2<0,则 日标函数在原点(0,0)取得最大值。 (3)当-3<k<-三时，若c>0,则目标函数在A:点(15/4,3/4)取得最大值：若 c2<0,则目标函数在原点(0,0)取得最大值。 (4)当k<一3时，若c>0,则日标函数在A:点(4,0)取得最大值：若c2<0,则日标 函数在原点(0,0)取得最大值。 ●1.可分别用单纯形法中的大M法和两阶段法求解下述线性规划问题，并指出属哪一类 解。 (1)maxx=2x1+3r2-5 x1+x2+x3=7 s.t.2x1-5x2+x3≥10 x1,x2,x1≥0 (2)min之=2x1+3x2+x1 1+42+2≥8 s.t.3x1+2x 三6 1x2,x3≥0 (3)maxx=10x1+15.x2+12x f5x1+3x2+ ≤9 -5x1+6x2+15x,≤15 2x1+x2+ x≥5 x2,x≥0 (4)max之=2.x1-x2+2x3 x1+x2+x≥6 -2x 十x≥2 s.t. 2x-x≥0 x2x≥0 分析本题考查了单纯形法中的大M法，两阶段法以及解的类型的概念。 解(1)解1：大M法。 在上述线性规划问题的约束条件中加上人工变量x4,x6,减去剩余变量x,得 max z=2x1+3x:-5x3-Mr+0rs-Mrs x1十x2+x1+x4 =7 s.t.2x1-5x十x -x5十x6=10 I1x2,x3,x4,x5,6≥0 其中M是一个任意大的正数。据此可列出单纯形表表1一6： ·16
0123456789:; (\7! D!/$+"a¸}ä;’ !#"h8$ ;1+1+R$¢%#(+$¤%&’(\ 7$ D!+$$"a¸}ä;&¢%#1+$¤ %&’(\sD!+$+"a¸}ä;’ !$"h8$1+18$ ;R$¢%#(+$¤%&’(\7# D!!;-/$$-/"a¸}ä;&¢ %#1+$¤%&’(\sD!+$+"a¸}ä;’ !/"h+18$R$¢%#(+$¤%&’(\7! D!/$+"a¸}ä;&¢%#1+$¤%& ’(\sD!+$+"a¸}ä;’ 3!5’ àUeI/G3pä / G3ÚÛÜGLF¾;MN@OPQ$ÔwNL-³ F’ !!"%&’!*#&!2$&$ ,"-" &!2 &$*? #&!8;&$$!+ &!$&#$&$$ % & ’ + !#"%()!*#&!2$&$ ,"-" &!2/#&$ $> $&!2#&# $= &!$&#$&$$ % & ’ + !$"%&’!*!+&!2!;!#&$ ;&!2$ &$#< 8;&!2=!;&$#!; #&!2  &$$; &!$&#$&$$ % & ’ + !/"%&’!*#&!8#&$ ,"-" &!2&# 2&$$= 8#&! 2&$$# #&# 8&$$+ &!$&#$&$$ % & ’ + KL rQFoI/G3pä / G$ÚÛÜGZ¬Fp³=p´µ’ ; !!"F!#ä / G’ \_;MN@OPQp)*+,3Ý_Þ5#$&/$&=$¶ñ·Ó#$&;$¸ %&’!*#&!2$&$8/&/2+&;8/&= ,"-" &!2 &$2&/ *? #&!8;&$ 8&;2&=*!+ &!$&#$&$$&/$&;$&=$ % & ’ + 23 7 ¥-þäpí(’ÁbY¿wI/¯¯!8=# (!&(
第一章线性规划与单纯形法 表1-6 2 3 -5-M0-M X b -M 1 1 1 0 0 7 -M [2] -5 0 -1 1 3M+2 3-4M 2M-5 0 -M 0 0 [7/2] 1/2 1/2 -1/2 4/7 5 -5/2 1/2 0 -1/2 1/2 0 3M/2+8M/2-6 0 M/2+1-3M/2-1 1 n 2/7 1/7 -1/n 45/7 6/7 5/7 -1/ 1/7 0-3 0 -50/7 -M-16/7 -1/7 -M+1/7 由单纯形表的计算结果得 最优解X=(，号，0,0,00严，目标函数的最优值=2×与+3×号-192。 解2：两阶段法。 先在上述线性规划问题的约束条件中加入人工变量x4,x6,减去剩余变量x,得 第一阶段的数学模型 ninw=x4十x6 f+x2十xa+x =7 s.t.2x1-5x2+x3 -x5+x6=10 x1,x2x3,4x5x6≥0 据此可列出单纯形表表1一7： 表1一7 0 0 0 0 1 b 7 1 0 0 10 [2 -1 1 -3 -2 0 1 0 「7/21 1/2 1/2 -1/2 4/7 0 -5/2 1/2 0 -1/2 1/2 (一新 0 -7/2 -1/2 0 -1/2 3/2 0 4/7 2/ -1/n 45/7 6/7 5/7 -1/7 1/7 G-3 0 0 0 0 1 第一阶段求得的最优解X=(,号，0,0,0,0),目标函数的最优值w=0。 因人工变量=，=0，所以（，号，0,00,0）是原线性规划问题的基可行解 ·17·
A*B !"#$%&’() ¯!8= %# # $ 8; 8/ + 8/ 98 18 ) &! &# &$ &/ &; &= "( 8/ &/ ? ! ! ! ! + + ? 8/ &= !+ /#0 8; ! + 8! ! ; %#8!# $/2# $8// #/8; + 8/ + 8/ &/ # + /?-#0 !-# ! !-# 8!-# /-? # &! ; ! 8;-# !-# + 8!-# !-# ) %#8!# + $/-#2> /-#8= + /-#2! 8$/-#8! $ &# /-? + ! !-? #-? !-? 8!-? # &! /;-? ! + =-? ;-? 8!-? !-? %#8!# + + 8;+-? 8/8!=-? 8!-? 8/2!-? gI/¯p¹º©%¸# }BF 12 *!/; ?$/ ?$+$+$+$+"3$%&’(p}B;!2 *#:/; ?2$:/ ?*!+# ? ’ F##ÚÛÜG’ ¸\_;MN@OPQp)*+,3ÝÃÞ5#$&/$&=$¶ñ·Ó#$&;$¸ Ò-ÛÜp(VW= %().*&/2&= ,"-" &!2 &$2&/ *? #&!8;&$ 8&;2&=*!+ &!$&#$&$$&/$&;$&=$ % & ’ + ÁbY¿wI/¯¯!8?# ¯!8? %# + + + ! + ! 98 18 ) &! &# &$ &/ &; &= "( ! &/ ? ! ! ! ! + + ? ! &= !+ /#0 8; ! + 8! ! ; %#8!# 8$ / 8# + ! + ! &/ # + /?-#0 !-# ! !-# 8!-# /-? + &! ; ! 8;-# !-# + 8!-# !-# ) %#8!# + 8?-# 8!-# + 8!-# $-# + &# /-? + ! !-? #-? !-? 8!-? + &! /;-? ! + =-? ;-? 8!-? !-? %#8!# + + + ! + ! Ò-ÛÜL¸p}BF 12 *!/; ?$/ ?$+$+$+$+"3$%&’(p}B; .2 *+’ QÞ5#$&/*&=*+$µZ!/; ?$/ ?$+$+$+$+"3 ¥sMN@OPQpqYF’ (!’(
运筹学同步辅导及习题全解 于是可以进行第二阶段运算，将第一阶段的最终表中的人工变量取消，并填入原 问题的目标函数的系数，进行第二阶段的运算，见表1一8。 表1一8 -5 0 C X b 4/7 1/7 1/7 2 45/7 6/n -1/ cj- -50/7 -1/7 由表中计算可知，原线性规划问题的最优解X=(5,号，0,0,0,0)，目标函数 的最优值：=2×5+3×号=102。 (2)解1：大M法。 在上述线性规划问题的约束条件中减去剩余变量x4,再分别加上人工变量x6,得 min z=2x1+3x:+x+0x+0rs+Mrs+Mr: （x十4x+2x3-x4+x6 =8 s.t.3x1+2x2 -Ts +x=6 x1,x,x,x4,x,x6,x≥0 其中M是一个任意大的正数。据此可列出单纯形表表1一9： 表1-9 2 3 10 0 M M C M 8 [4] M 2-4M3-6M 1-2M 2 1/4 1/2 -1/A M [s/2] 1/2 1/2 4/5 一 - 0 M- -M= 0 39/5 0 1 3/5 -3/10 1/10 3/10 -1/10 24/5 0 -2/5 1/5 -/5 -1/5 2/5 一 0 0 0 1212 M-1/2M-1/2 由单纯形表的计算结果得：最优解X·-(号，号，0,00,0,0)，目标函数的最优 值：=2X4+3×号=7。X存在非基变量检验数1=0，故该线性规划问题有 无穷多最优解。 解2：两阶段法。 先在上述线性规划问题的约束条件中减去剩余变量x4,再分别加上人工变量 x6,x,得第一阶段的数学模型 minw=x6十x, ·18
0123456789:; f¥YZÍÒgÛÜɺ$UÒ-ÛÜp}Ù¯3pÞ5#$a¹$ÔºÃs PQp%&’(p7($ÍÒgÛÜpɺ$¯!8>’ ¯!8> %# # $ 8; + 98 18 ) &! &# &$ &; "( $ &# /-? + ! !-? !-? # &! /;-? ! + =-? 8!-? %#8!# + + 8;+-? 8!-? g¯3¹ºY$sMN@OPQp}BF 12 *!/; ?$/ ?$+$+$+$+"3$%&’( p}B;!2 *#:/; ?2$:/ ?*!+# ? ’ !#"F!#ä / G’ \_;MN@OPQp)*+,3¶ñ·Ó#$&/$&;$ÄàUÝ_Þ5#$&=$&?$¸ %()!*#&!2$&$2+&/2+&;2/&=2/&? ,"-" &!2/#&$8&/ 2&= *> $&!2#&# 8&; 2&? *= &!$&#$&$$&/$&;$&=$&?$ % & ’ + 23 / ¥-þäpí(’ÁbY¿wI/¯¯!8<# ¯!8< %# # $ ! + + / / 98 18 ) &! &# &$ &/ &; &= &? "( / &= > ! //0 # 8! + ! + # / &? = $ # + + 8! + ! $ %#8!# #8// $8=/ !8#/ / / + + $ &# # !-/ ! !-# 8!-/ + !-/ + > / &? # /;-#0 + 8! !-# 8! 8!-# ! /-; %#8!# ; / 8 ; # / + /8 ! # $ / 8 ! # / / $ # /8 $ / + $ &# <-; + ! $-; 8$-!+ !-!+ $-!+ 8!-!+ # &! /-; ! + 8#-; !-; 8#-; 8!-; #-; %#8!# + + + !-# !-# /8!-# /8!-# gI/¯p¹º©%¸#}BF 12 *!/ ;$< ;$+$+$+$+$+"3$%&’(p}B ;!2 *#:/ ;2$:< ;*?’1 £\´q#$°±(!$ *+$i/MN@OPQj ~}BF’ F##ÚÛÜG’ ¸\_;MN@OPQp)*+,3¶ñ·Ó#$&/$&;$ÄàUÝ_Þ5#$ &=$&?$¸Ò-ÛÜp(VW= %().*&=2&? (!((
第一章线性规划与单纯形法 x1十4x2十2x1-x4 十x6 =8 s.t.3x+2x2 -I: +x,=6 x2,x3,x4x,x6,x7≥0 据此可列出单纯形表1一10： 表1-10 0 0 [4] 9 6 3 2 0 0 -1 0 1 0 0 1/4 1/2 1/4 2 「5/21 1 1/2 -1/2 4/5 )一 -5/2 0 -1/2 0 9/5 0 3/5 -3/10 1/10 3/10 -1/16 0 4/5 1 0 -2/5 1/5 -2/5 -1/5 2/5 0 0 0 0 0 1 1 第一阶段求得的最优解X·=(号，号0,0,00,0)，目标函数的最优值0=0。 因人工变量，-，-0，所以（兮号0.0,00,0）是原线性规划同题的基可行 解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并 填入原问题的目标函数的系数，进行第二阶段的运算，见表1一11。 表1-11 2 3 0 0 Cu 红 I3 r 9/5 0 1 -3/10 1/10 2 4/5 1 0 -2/5 1/5 -2/5 00 01/21/2 由表中计算可知，原线性规划问题的最优解X·=(号，号，0,00,0,0)，日标函 数的最优值：”=2×专十3×兰=7由于存在非基变量检验数=0，故该线性规 划问题有无穷多最优解。 (3)解1.大M法。 在上述线性规划问题的第一、二个约束条件中分别加上松弛变量x4,在第三个约 束条件中减去剩余变量x6,再加上人工变量x,得 maxz=10x1+15x2+12x3+0x4+0.x3十0x6-Mx ·19·
A*B !"#$%&’() ,"-" &!2/#&$8&/ 2&= *> $&!2#&# 8&; 2&? *= &!$&#$&$$&/$&;$&=$&?$ % & ’ + ÁbY¿wI/¯!8!+# ¯!8!+ %# + + + + + ! ! 98 18 ) &! &# &$ &/ &; &= &? "( ! &= > ! //0 # 8! + ! + # ! &? = $ # + + 8! + ! $ %#8!# 8/ 8= 8# ! ! + + + &# # !-/ ! !-# 8!-/ + !-/ + > ! &? # /;-#0 + 8! !-# 8! 8!-# ! /-; %#8!# 8;-# + ! 8!-# ! $-# + + &# <-; + ! $-; 8$-!+ !-!+ $-!+ 8!-!+ + &! /-; ! + 8#-; !-; 8#-; 8!-; #-; %#8!# + + + + + ! ! Ò-ÛÜL¸p}BF 12 *!/ ;$< ;$+$+$+$+$+"3$%&’(p}B; .2 *+’ QÞ5#$&=*&?*+$µZ!/ ;$< ;$+$+$+$+$+"3 ¥sMN@OPQpqY F’f¥YZÍÒgÛÜɺ’UÒ-ÛÜp}Ù¯3pÞ5#$a¹$Ô ºÃsPQp%&’(p7($ÍÒgÛÜpɺ$¯!8!!’ ¯!8!! %# # $ ! + + 98 18 ) &! &# &$ &/ &; "( $ &# <-; + ! $-; 8$-!+ !-!+ # &! /-; ! + 8#-; !-; 8#-; %#8!# + + + !-# !-# g¯3¹ºY$sMN@OPQp}BF 12 *!/ ;$< ;$+$+$+$+$+"3$%&’ (p}B;!2 *#:/ ;2$:< ;*?gf£\´q#$°±(!$*+$i/MN@ OPQj~}BF’ !$"F!#ä / G’ \_;MN@OPQpÒ-,g)*+,3àUÝ_§¨#$&/$&;$\ÒE) *+,3¶ñ·Ó#$&=$ÄÝ_Þ5#$&?$¸ %&’!*!+&!2!;!#&$2+&/2+&;2+&=8/&? (!)(