第一章线性规划与单纯形法 1 4 0 0 Ca Xa x: 3 x 4 8/5 3/5 1 1/5 0 0 1/5 1/5 -3/5 1 c-3 -7/5 0 -4/5 0 由表中计算可知，该线性规划问题的最优解X·=(0,各，0，三)，目标函数x的下界 三-4×8-号。 ⊙1.8表1一19是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量， a1、a2、aa、d、1、c2为待定常数。试说明这些常数分别取何值时，以下结论成立。 (1)表中解为惟一最优解： (2)表中解为最优解，但存在无穷多最优解： (3)该线性规划问题具有无界解： (4)表中解非最优，为对解改进，换入变量为x1,换出变量为x。 表1-19 基b 3 0 2 -3 -1 3 as -5 0 0 -4 0 0 -3 0 分析分别根据各种类型的解的概念进行求解。 解(1)当解为惟一最优解时，必有d≥0，G<0,c<0 (2)当解为最优解，但存在无穷多最优解时，必有d≥0，G1≤0，c2=0或d≥0，G1=0, c,0。 (3)当该问题为无界解时，必有d≥0，G1≤0，c2>0且a1≤0。 (4)当解为非最优，为对解进行改进，当换入变量为工1，换出变量为x6,必有d≥0， 6>0且6≥4>0<号 ⊙1.习某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 班次 时间 所需人数 1 6:00~10:00 60 10:0014:00 70 3 14:0018:00 60 4 18:00~22:00 50 ·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Þ( ! =#++&!+#++ =+ # !+#++&!/#++ ?+ $ !/#++&!>#++ =+ / !>#++&###++ ;+ ("%(
运筹学同步辅导及习题全解 班次 时间 所需人数 22:00~2:00 20 6 2:00~6:00 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公 交线路至少配备多少名司机和乘务人员。列出这个问题的线性规划模型 分析本题考查了线性规划模型的建立。 解设x(k=1,2,3,4,5,6)表示x名司机和乘务人员第k班次开始上班。由题意，有 minz=x1+x2十xa+x4十x+x6 x6十x1≥60 1十x2≥70 x2十x≥60 s.t.Jx1+x≥50 x+x5≥20 xs+x6≥30 ,xx,3,x6≥0 O1.10某糖果厂用原料A、B,C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖 果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加 工费及售价如表1一20所示。 表1-20 原料 内 原料成本 每月限制用量 (元/千克) (千克) A ≥60% ≥15% 2.00 2000 B 1.50 2500 ≤20% ≤60% ≤50% 1.00 1200 加工费（元/千克） 0.50 0.40 0.30 售 价 3.40 2.85 2.25 问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立这个问 题的线性规划的数学模型。 解 设工1，x,x分别为甲糖果中A,B,C的成份：x4,x,x6分别为乙糖果中A,B,C的 成份：x,x,x,分别为丙糖果中A,B,C的成份。由题意，有 maX之=(3.40-0.50)X(x,+x,+x.)+(2.85-0.40)X(x.十x-+x.) +(2.25-0.30)×(x+x+x)-2.00×(x1+x+x) -1.50X(x2+x+x)-1.00×(xa+x6+x) ·26·
0123456789:; È£ R Ä µTÞ( ; ###++&##++ #+ = ##++&=#++ $+ ÷ÅÆ3ÁÞÇàU\³RÄ"Ü-R_È$ÔÉó5‘ÊåR$P/ ÂMÃîËÌîÍÅÆ3ÁÞÇ’¿wïPQpMN@OW=’ KL rQFoMN@OW=p’ ; ÷&+!+*!$#$$$/$;$="¯&+ ÍÅÆ3ÁÞÇÒ+ È£_È’gQþ$j %()!*&!2&$2&/2&;2&= ,"-" &=2&!$=+ &!2&#$?+ &$$=+ &$2&/$;+ &/2&;$#+ &;2&=$$+ &!$&#$&$$&/$&;$&=$ % & ’ + *!5!+ Î%-es~7,8,9 Ý5áEySÏÐpÎ%Ñ,Ò,Ó’¶³yÏÐÎ %37,8,9 $$s~ár$³ys~p+*mÔe$$EyÏÐÎ%pImÝ 5@¬Õ:$¯!8#+µ’ ¯!8#+ s~ Ñ Ò Ó s~ár !Ë-Öv" +*mÔe$ !Öv" 7 $=+> $!;> #5++ #+++ 8 !5;+ #;++ 9 ##+> #=+> #;+> !5++ !#++ Ý5@!Ë-Öv" Õ : +5;+ $5/+ +5/+ #5>; +5$+ #5#; P/-+*«.(ïEyÏÐÎ%³îÖv$Ñ/-×Ø}ä. BïP QpMN@Op(VW=’ ; ÷&!$&#$&$ àU4ÑÎ%3 7$8$9 páR&&/$&;$&= àU4ÒÎ%3 7$8$9 p áR&&?$&>$&< àU4ÓÎ%3 7$8$9 páR’gQþ$j %&’!*!$5/+8+5;+":!&!2&$"2!#5>;8+5/+":!&/2&;2&=" 2!#5#;8+5$+":!&?2&>2&<"8#5++:!&!2&/2&?" 8!5;+:!&;2&>"8!5++:!&$2&=2&<" ("&(
第一章线性规划与单纯形法 ++≥0.6 4++石0.2 五++石≥0.15 s.t 五+x+五≤0.6 ++3≤0.5 x1+x+x≤2000 x2十x3十x,≤2500 x+x6十x≤1200 对上式进行整理得到所求问题的线性规划模型 maxx=0.9x1+1.4x2+1.9x+0.45x4+0.95.xs+1.45.x6-0.05x,+0.45x+0.95.xg -0.4x1+0.6x2十0.6x≤0 -0.2x1-0.2x2+0.8x3≤0 -0.85x4+0.15+0.15x≤0 -0.6x4-0.6.x5+0.4x6≤0 s.tJ-0.5x7-0.5x8+0.5x≤0 xm1+x4+x,≤2000 xm2+x3+x3≤2500 x十x6十x≤1200 O1.11某厂生产三种产品I,Ⅱ，Ⅲ，每种产品要经过A,B两道工序加工。设该厂有两 种规格的设备能完成A工序，它们以A,A:表示；有三种规格的设备能完成B工 序，它们以B,B2,B,表示。产品I可在A,B任何一种规格设备上加工。产品Ⅱ 可在任何规格的A设备上加工，但完成B工序时，只能在B,设备上加工；产品川 只能在A与B,设备上加工。已知在各种机床设备的单件工时，原材料费，产品 销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表（表 1一21)，要求安排最优的生产计划，使该厂利润最大。 表1-21 设备 设备有效台时 满负荷时的 设备费用（元） A 10 6000 300 10000 321 4000 250 7000 B 4000 200 原料费（元/件） 0.25 0.35 0.50 单价（元/件） 1.25 2.00 ·27·
A*B !"#$%&’() ,"-" &! &!2&$ $+5= &$ &!2&$ #+5# &/ &/2&;2&= $+5!; &= &/2&;2&= #+5= &< &?2&>2&< #+5; &!2&/2&?##+++ &;2&>##;++ &$2&=2&<#!#++ &!$&#$&$$&/$&;$&=$&?$&>$&<$ % & ’ + ª_0ÍÙt¸µLPQpMN@OW= %&’!*+5<&!2!5/!5<&$2+5/;&/2+5<;&;2!5/;&=8+5+;&?2+5/;&>2+5<;&< ,"-" 8+5/&!2+5=+5=&$#+ 8+5#&!8+5#+5>&$#+ 8+5>;&/2+5!;&;2+5!;&=#+ 8+5=&/8+5=&;2+5/&=#+ 8+5;&?8+5;&>2+5;&<#+ &!2&/2&?##+++ &;2&>##;++ &$2&=2&<#!#++ &!$&#$&$$&/$&;$&=$&?$&>$&<$ % & ’ + *!5!! -.(Ey()’$($*$+y():·5 7$8 Ú5ÚÝ5’÷/-jÚ y@p÷Ì0Ûá7 5Ú$uÜZ7!$7# ¯&jEy@p÷Ì0Ûá8 5 Ú$uÜZ8!$8#$8$ ¯’()’Y\7$8 ý-y@÷Ì_Ý5’()( Y\ý@p7 ÷Ì_Ý5$aÛá8 5ÚR$c0\8! ÷Ì_Ý5&()* c0\ 7#¨8# ÷Ì_Ý5’¶\³yÆÝ÷ÌpI,5R$sÞ~@$() ßÕ:$³ y ÷ Ì j ª à R Z ¬ õ ì á â ‘ R Æ Ý ÷ Ì p @ e $ ¾ ¯ !¯ !8#!"$:LCD}Bp.(¹O$Ñ/-Øã}ä’ ¯ !8#! ÷ Ì ( ) ’ ( * ÷ÌjªàR õìáRp ÷Ì@e!Ë" 7! ; !+ =+++ $++ 7# ? < !# !++++ $#! 8! = > /+++ #;+ 8# / !! ?+++ ?>$ 8$ ? /+++ #++ s~@!Ë-," +5#; +5$; +5;+ I:!Ë-," !5#; #5++ #5>+ ("’(
运筹学同步辅导及习题全解 解对产品I来说，设以A1,A2完成A工序的产品分别为x1,2件，转入B工序时，以 B,B,B完成B工序的产品分别为x,x4,件：对产品Ⅱ来说，设以A,A:完成 A工序的产品分别为x6,x,件，转入B工序时，以B,完成B工序的产品为x。件： 对产品Ⅲ来说，设以Az完成A工序的产品为x。件，则以B2完成B工序的产品也 为x,件。由上述条件可得： x十x=十x十x x6十x=x 由题目所给的数据可得到解此问题的数学模型为： maxz=(1.25-0.25)×(x1+x2)+(2.00-0.35)×(x6十x7) +20-0.50X,0×(5+10 321 050 000X(7+9,+12)4000×(6x,+8, -7×4+1-06×1n 200 5.x1+10x6≤6000 7x2+9x?+12xg≤10000 6x1+8x.≤4000 4x4+11,≤7000 s.t. 7x5≤4000 1十x2=x十x4十x xs十x,=xg 23x6,x6,x7,xg,≥0 解之得最优解为： x=1200. x=230 x=0， x=859, x=571. x6=0, x7=500, xg=500, xg=324。 最优值为1147元。 ·28·
0123456789:; ; ª()’âè$÷Z7!$7# Ûá7 5Úp()àU4&!$&# ,$½Ã8 5ÚR$Z 8!$8#$8$ Ûá8 5Úp()àU4&$$&/$&; ,&ª()(âè$÷Z 7!$7# Ûá 7 5Úp()àU4&=$&? ,$½Ã 8 5ÚR$Z 8! Ûá 8 5Úp()4&> ,& ª()*âè$÷Z7# Ûá 7 5Úp()4&< ,$¤Z8# Ûá8 5Úp()> 4&< ,’g_;+,Y¸# &!2&# *&$2&/2&; &=2&? *&> gQ%µäp(ÁY¸FbPQp(VW=4# %&’!*!!5#;8+5#;":!&!2&#"2!#5++8+5$;":!&=2&?" 2!#5>+8+5;+":&<8 $++ =+++:!;&!2!+&=" 8 $#! !++++:!?<&?2!#&<"8 #;+ /+++:!=&$2>&>" 8 ?>$ ?+++:!/&/2!!&<"8 #++ /+++:?&; ,"-" ;&!2!+&=#=+++ ?<&?2!#&<#!++++ =&$2 >&>#/+++ /&/2!!&<#?+++ ?&;#/+++ &!2&#*&$2&/2&; &=2&?*&> &!$&#$&$$&/$&;$&=$&?$&>$&<$ % & ’ + Fë¸}BF4# &2 ! *!#++$ &2 # *#$+$ &2 $ *+$ &2 / *>;<$ &2 ; *;?!$ &2 = *+$ &2 ? *;++$ &2 > *;++$ &2 < *$#/’ }B;4!!/?Ë’ ("((
第二章 对偶理论和灵敏度分析 内容提要 一、原问题与对偶问题的关系 若某线性规划（原问题）约束系数矩阵为A,约束条件右端为向量b,目标函数中的价值 系数向量为C,则其对偶问题形式如表2-1所示。 表2-1 原问题（对偶问题） 对偶问题（原问题） 目标函数maxx= g,(j=1,.,m) 有n个(=1,.,n》 变，≥0 2≥6 约 量z,<0 工，无约束 -6 有m个(i=1,.,m） y(i=1,.,m) y≥0 变 ≥6 y≤0 y无约束 ·29·
!$# QR@STUVWKL !"#$ *!XY9%QRY9+Z[ ¢MN@O!sPQ")*7(ÏÐ4"$)*+,eå4$#$%&’(3p:; 7($4$$¤2ªæPQ/0$¯#%!µ’ ¯#A! sPQ!ªæPQ" ªæPQ!sPQ" %&’( %&’!* " " #$! %#&# # $ &#!#*!$%$"" &#$+ &##+ &# % & ’ ~)* %().* " * ($! )(3( j"!#*!$%$"" " * ($! ’(#3( $%# " * ($! ’(#3( #%# " * ($! ’(#3( $% 5 6 # 7 ) * + , ) * + , j * !(*!$%$*" " " #$! ’(#&# #)( " " #$! ’(#&# $)( " " #$! ’(#&# $) % & ’ ( 3(!(*!$%$*" 3($+ 3(#+ 3( 5 6 ~)* 7 # $ (")(