第一章线性规划与单纯形法0000100cj0.XB6CBX7rix2x34rsts52111100-15/2X70-2-1-1001cj-zj9/51903/51/51/5000312493/200[16]1100ts10017/53/52/5-17/3-1/5X7010-1/53/5-2/50cj-zj03/21039/8003/16-1/800X103/209/1611/161/1600t311/200-7/161043/803/8017043/8007/163/8010cj-xj1331T第一阶段求得最优解X*二（因人工变量二,0,0,0,0，且非0元22基变量检验数>0，所以原线性规划问题无可行解。（4）解1：大M法在上述线性规划问题的约束条件中分别减去剩余变量4，工，工，再加上人工变量fs,1,ag,得max2=2ri-r2+2r+0ri-Mrs+0r-Mr,+0rs-Mrg++-+=62+—+=2s.t.22-1—1g十g=011,12,as,4,a5,16,r7,ag,1g≥0其中M是一个任意大的正数。据此可列出单纯形表表1一14：表1-142-120-M00-M-Mcj0:CXBb24xs31223ast6X7xtg-M6111-1100006xs2010010-M-2-10-T00[2]0000-110-M-1xs-M-M2-M3M-12+M0-M00c-sj13/211/21/2-M60-1004xs22-2.0[1]00100-M-1X71-1001/200001/21/2-X2M3M5M+311-M2-M00-M0cj-zj222222[4] -113/23/21/2-1/23/4-M3.00xs·21
A*B !"#$%&’() %# + + + + + + ! 98 18 ) &! &# &$ &/ &; &= &? "( ! &? ; # ! ! + + 8! ! ;-# %#8!# 8# 8! 8! + + ! + + &! <-; ! $-; !-; !-; + + + < + &; #/ + < /!=0 ! ! + + $-# ! &? ?-; + 8!-; $-; 8#-; + 8! ! ?-$ %#8!# + 8!-; $-; 8#-; + ! + + &! $-# ! $<->+ + $-!= 8!->+ + + + &$ $-# + <-!= ! !-!= !-!= + + ! &? !-# + 8/$->+ + 8?-!= 8$->+ ! + %#8!# + /$->+ + ?-!= $->+ ! + Ò-ÛÜL¸}BF 12 *!$ #$+$$ #$+$+$+$! #"3’QÞ5#$&?*! #4+$k´ q#$°±(!#(+$µZsMN@OPQ~YF’ !/"F!#ä / G’ \_;MN@OPQp)*+,3àU¶ñ·Ó#$ &/$&=$&>$ÄÝ_Þ5#$ &;$&?$&<$¸ %&’!*#&!8#&$2+&/8/&;2+&=8/&?2+&>8/&< ,"-" &!2&$8&/2&;*= 8#&!2&$8&=2&?*# #&$8&>2&<*+ &!$&#$&$$&/$&;$&=$&?$&>$&<$ % & ’ + 23 / ¥-þäpí(’ÁbY¿wI/¯¯!8!/# ¯!8!/ %# # 8! # + 8/ + 8/ + 8/ 98 18 ) &! &# &$ &/ &; &= &? &> &< "( 8/ &; = ! ! ! 8! ! + + + + = 8/ &? # 8# + ! + + 8! ! + + ) 8/ &< + + /#0 8! + + + + 8! ! + %#8!# #8/ $/8! #2/ 8/ + 8/ + 8/ + 8/ &; = ! + $-# 8! ! + + !-# 8!-# / 8/ &? # 8# + /!0 + + 8! ! + + # 8! &# + + ! 8!-# + + + + 8!-# !-# ) %#8!# #8/ + ;/ # 2 $ # 8/ + 8/ + / # 8 ! # ! # 8$/ # 8/ &; $ //0 + + 8! ! $-# 8$-# !-# 8!-# $-/ ("!(
运筹学同步辅导及习题全解22-10-M0-M0-Mcj0.CXBbr2x1x3a4ssX7xstg2-20100-1100x31000-1/21/2-1/21/2-1-1X2-3M,3M13M15M_34M+500-M0ci-zj222222100-1/41/43/81/81/823/4-3/8X127/20011/21/21/41/4-1/41/4x3101/41/87/40-1/4-1/8-3/83/8-13253905/43/800-M--M9/8Mcj-zj848由单纯形表的计算结果可以看出，4>0且ai<0(i=1,2,3)，所以该线性规划问题有无界解。解2：两阶段法。先在上述线性规划问题的约束条件中分别减去剩余变量14，r6，rs，再加上人工变量s，，，，得第一阶段的数学模型min w-rs+r, +xg+++=6-2+-+,-2s.t.2r2——rg+g=0T1,12,s,1.5,16,17,1s,1g≥0据此可列出单纯形表表1一15：表1-15.000110001cj0.CBXB6rr2r4rsxtX3X53stg11116-1100006as112-2000100-1-X7[2]010100-1000-1X91-3-1101010cj-2j1.03/210016-11/21/24xs12-2[1]0100200-1701-1/200001/200-1/2/X210-5/210-1/23/2-10ci-zj11[4]00-13/23/21/2-1/23/43xs2-2.0100-11000x31/201000-1/21/2-1/2X2-122
0123456789:; %# # 8! # + 8/ + 8/ + 8/ 98 18 ) &! &# &$ &/ &; &= &? &> &< "( # &$ # 8# + ! + + 8! ! + + ) 8! &# ! 8! ! + + + 8!-# !-# 8!-# !-# ) %#8!# //2; + + 8/ + $/ # 2 $ # 8;/ # 8 $ # / # 8 ! # ! # 8$/ # # &! $-/ ! + + 8!-/ !-/ $-> 8$-> !-> 8!-> # &$ ?-# + + ! 8!-# !-# 8!-/ !-/ !-/ 8!-/ 8! &# ?-/ + ! + 8!-/ !-/ 8!-> !-> 8$-> $-> %#8!# + + + ;-/ 8/8 ; / 8$-> $ > 8/ 8<-> < > 8/ gI/¯p¹º©%YZvw$!/(+k’(/1+!(*!$#$$"$µZ/MN@OPQj ~F’ F##ÚÛÜG’ ¸\_;MN@OPQp)*+,3àU¶ñ·Ó#$&/$&=$&>$ÄÝ_Þ5#$ &;$&?$&<$¸Ò-ÛÜp(VW= %().*&;2&?2&< ,"-" &!2&$8&/2&;*= 8#&!2&$8&=2&?*# #&$8&>2&<*+ &!$&#$&$$&/$&;$&=$&?$&>$&<$ % & ’ + ÁbY¿wI/¯¯!8!;# ¯!8!; %# + + + + ! + ! + ! 98 18 ) &! &# &$ &/ &; &= &? &> &< "( ! &; = ! ! ! 8! ! + + + + = ! &? # 8# + ! + + 8! ! + + ) ! &< + + /#0 8! + + + + 8! ! + %#8!# ! 8$ 8! ! + ! + ! + ! &; = ! + $-# 8! ! + + !-# 8!-# / ! &? # 8# + /!0 + + 8! ! + + # + &# + + ! 8!-# + + + + 8!-# !-# ) %#8!# ! + 8;-# ! + 8! + 8!-# $-# ! &; $ //0 + + 8! ! $-# 8$-# !-# 8!-# $-/ + &$ # 8# + ! + + 8! ! + + ) + &# ! 8! ! + + + 8!-# !-# 8!-# !-# ) (""(
第一章线性规划与单纯形法00000011cj0X:CBb42xgt1x3a4xsxettts15/23/2-4000-3/2-1/2cj-zj3/41.001/41/8-1/80-1/43/83/8xi7/20011/21/21/41/41/41/40a7/40101/41/80-1/4-1/8-3/83/8X01100010c-30773第一阶段求得的最优解X2.0,0.0,0.0.0)T，目标函数的最优值NAw*=0。因人工变量，,,=0,所以（，0，00，0,0,0）T是原线性规划问题的基442可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见表1一16。表1-1622000-1cjCeX8bt1x234rsts21001/83/41/43/8327/20011/21/43-1/4001-17/4-1/4-1/8-3/8x20005/4-9/8-3/8cj-2j由表中计算可知，>0且a<0（i=1,2,3），所以原线性规划问题有无界解。小结大M法和两阶段法都是人工变量法。01.7求下述线性规划问题目标函数的上界和下界maxz=ciri+cr2(anab)a+ab1,≥0其中1c3，4c68b121014，-1am3,2a5.2a2≤4,4≤a22≤6分析先求出与和相对应的线性规划模型，再用单纯形法求解。解的上界可由如下的线性规划模型求得max=3r+6r2+2≤122r+4≤14r.≥0在上述问题的第一个约束条件中加人松弛变量工3，第二个约束条件左右两边同时除·23
A*B !"#$%&’() %# + + + + ! + ! + ! 98 18 ) &! &# &$ &/ &; &= &? &> &< "( %#8!# 8/ + + ! + 8$-# ;-# 8!-# $-# + &! $-/ ! + + 8!-/ !-/ $-> 8$-> !-> 8!-> + &$ ?-# + + ! 8!-# !-# 8!-/ !-/ !-/ 8!-/ + &# ?-/ + ! + 8!-/ !-/ 8!-> !-> 8$-> $-> %#8!# + + + + ! + ! + ! Ò-ÛÜL¸p } B F 12 * !$ /$? /$? #$+$+$+$+$+$+"3$% & ’ ( p } B ; .2 *+’ QÞ5#$&;*&?*&<*+$µZ!$ /$? /$? #$+$+$+$+$+$+"3 ¥sMN@OPQpq YF’f¥YZÍÒgÛÜɺ’UÒ-ÛÜp}Ù¯3pÞ5#$a¹$Ô ºÃsPQp%&’(p7($ÍÒgÛÜpɺ$¯!8!=’ ¯!8!= %# # 8! # + + + 98 18 ) &! &# &$ &/ &= &> "( # &! $-/ ! + + 8!-/ $-> !-> # &$ ?-# + + ! 8!-# 8!-/ !-/ 8! &# ?-/ + ! + 8!-/ 8!-> 8$-> %#8!# + + + ;-/ 8$-> 8<-> g¯3¹ºY$!/(+k’(/1+!(*!$#$$"$µZsMN@OPQj~F’ OP ä / G3ÚÛÜGç¥Þ5#$G’ +!$( L¾;MN@OPQ%&’(!p_!2 3¾!2 %&’!*%!&!2%#&# ’!!&!2’!#&##)! ’#!&!2’##&##)# &!$&#$ % & ’ + 23#!#%!#$$/#%##=$>#)!#!#$!+#)##!/$8!#’!!#$$##’!##;$## ’#!#/$/#’###= KL ¸Lw¨!2 3!2 ª«pMN@OW=$ÄeI/GLF’ ; !p_!2 Yg$¾pMN@OW=L¸ %&’!*$&!2=&# 8&!2#&##!# #&!2/&##!/ &!$&#$ % & ’ + \_;PQpÒ-)*+,3Ýç¨#$&$$Òg)*+,»eÚRð ("#(
运筹学同步辅导及习题全解以2再加人松弛变量，得该线性规划问题的标准型max=3r1+6r+0r+0x—+2+=12+2+=70由线性规划问题的标准型可列出初始单纯形表逐步迭代，计算结果如表1一17所示。表1-173600cj0:CaXBbx1X2X32412-12601043071[2]0I7/2x43060cj-zj500-21-1X367/21/211/20x2o0-30cj-zj7由表中计算可知，该线性规划问题的最优解X=（O，5，0）T，目标函数的上界27*-=6X=21。由于存在非基变量检验数61=0.故该线性规划问题有无穷多2最优解。的下界可由如下的线性规划模型求得max=r,+4r23+5≤8s.t.34+6≤10,≥0在上述问题的第一个约束条件中加人松弛变量工3，第二个约束条件左右两边同时除以2再加人松弛变量工，得该线性规划问题的标准型max2=ri+4r2+03+0r4=83+5+3s.t.32r1+3r2+r=5g0由线性规划问题的标准型可列出初始单纯形表逐步送代，计算结果如表1一18所示。表1-181004cj6.XsCB0aix4x2X383[5]1008/5ra052301r45/31400G-zj·24
0123456789:; Z#ÄÝç¨#$&/$¸/MN@OPQp&<= %&’!*$&!2=+&$2+&/ 8&!2#&$*!# &!2#&/*? &!$&#$&$$&/$ % & ’ + gMN@OPQp&<=Y¿wI/¯ ¢$¹º©%$¯!8!?µ’ ¯!8!? %# $ = + + 98 18 ) &! &# &$ &/ "( + &$ !# 8! # ! + = + &/ ? ! /#0 + ! ?-# %#8!# $ = + + + &$ ; 8# + ! 8! = &# ?-# !-# ! + !-# %#8!# + + + 8$ g¯3¹ºY$/MN@OPQp}BF 12 *!+$? #$;$+"3$%&’(!p_ !2 *!2 *=:? #*#!’gf£\´q#$°±(!!*+$i/MN@OPQj~ }BF’ !p¾!2 Yg$¾pMN@OW=L¸ %&’!*&!2/&# ,"-" $&!2;&##> /&!2=&##!+ &!$&#$ % & ’ + \_;PQpÒ-)*+,3Ýç¨#$&$$Òg)*+,»eÚRð Z#ÄÝç¨#$&/$¸/MN@OPQp&<= %&’!*&!2/+&$2+&/ ,"-" $&!2;&$ *> #&!2$&# 2&/*; &!$&#$&$$&/$ % & ’ + gMN@OPQp&<=Y¿wI/¯ ¢$¹º©%$¯!8!>µ’ ¯!8!> %# ! / + + 98 18 ) &! &# &$ &/ "( + &$ > $ /;0 ! + >-; + &/ ; # $ + ! ;-$ %#8!# ! / + + ("$(
第一章线性规划与单纯形法1400cj0;XabCea1x2x3r44108/53/51/5r201/51/503/51x4-7/50-4/50c-3j8.)T，目标函数的下界由表中计算可知，该线性规划问题的最优解X*=（0，.0.558_322=2-4X551.8表1一19是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1、a2asd、c1vc2为待定常数。试说明这些常数分别取何值时，以下结论成立。（1)表中解为惟一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4)表中解非最优，为对解改进，换人变量为1，换出变量为16。表1-19基bri123rtsr6410d0aisa202-301-1-1r4301-50-4as16000-3C1C2cj-2,分析分别根据各种类型的解的概念进行求解。解（1)当解为惟一最优解时，必有d≥0,G<0.C<0。（2）当解为最优解，但存在无穷多最优解时，必有d≥0，c≤0，c2=0或d≥0，C1=0，C2≤0。(3）当该问题为无界解时，必有d≥0ci≤0,c2>0且a≤0。（4)当解为非最优，为对解进行改进，当换人变量为1，换出变量为r，必有d≥0，G>0,且G≥c2,a,>0,3<兴,4as01.9某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：班次时间所需人数1606:00~10:0027010:00~14:0036014:00~18.0045018:00~22:00·25
A*B !"#$%&’() %# ! / + + 98 18 ) &! &# &$ &/ "( / &# >-; $-; ! !-; + + &/ !-; !-; + 8$-; ! %#8!# 8?-; + 8/-; + g¯3¹ºY$/MN@OPQp}BF 12 *!+$> ;$+$! ;"3$%&’(!p¾ !2 *!2 */:> ;*$# ;’ +!5) ¯!8!<¥LãäXMN@OPQ¹º¸pI/¯’¯3~Þ5#$$ ’!,’#,’$,=,%!,%#4¼k½(’BèéïM½(àUaý;R$Z¾© á’ !!"¯3F4|-}BF& !#"¯3F4}BF$a£\~}BF& !$"/MN@OPQj~F& !/"¯3F´}B$4ªF²Í$ÂÃ#$4&!$Âw#$4&=’ ¯!8!< q ) &! &# &$ &/ &; &= &$ = / ’! ! + ’# + &/ # 8! 8$ + ! 8! + &= $ ’$ 8; + + 8/ ! %#8!# %! %# + + 8$ + KL àUÀÁ³y³=pFp´µÍLF’ ; !!"hF4|-}BFR$#j=$+$%!1+$%#1+’ !#"hF4}BF$a£\~}BFR$#j=$+$%!#+$%#*+1=$+$%!*+$ %##+’ !$"h/PQ4~FR$#j=$+$%!#+$%#(+k’!#+’ !/"hF4´}B$4ªFͲÍ$hÂÃ#$4&!$Âw#$4&=$#j=$+$ %!(+$k%!$%#$’$(+$$ ’$ 1= /’ +!5* ¾¿ÀÁpÂMÃ+u³RÄ"ܵTÅÆ3ÁÞÇ($¾# È£ R Ä µTÞ( ! =#++&!+#++ =+ # !+#++&!/#++ ?+ $ !/#++&!>#++ =+ / !>#++&###++ ;+ ("%(