阿21世纪高等院校象典救材同步辅号 ERSHIYISHIJIGAODENGYUANXIAOJINGDIANJIAOCAITONGBUFUDAO 运筹学 全程导学及习题全解 清华大学第三版 张晋东孙成功主编 ◆知识归纳抗理上线重点难点 ◆习题详解精所解答乳材习题 ◆提高陈习巩周知识迈向更高 ◆中国时代经济出版社
第一章 线性规划与单纯形法 内容提要 一、线性规划的实际模型 1.规划问题数学模型三个要素 (1)决策变量 (2)目标函数 (3)约束条件 2.线性规划问题的数学模型 (1)一般形式 目标函数：max(或min)= 约束条件： 2gx,≤(=，≥bi=12.m x,≥0 (j=1,2,.,n) 其中x,(=1,2,.,n)为决策变量，a5(i=1,2,.,mj=1,2,.,n)为工艺系数， b:(i=1,2,.,m)为资源系数，c,(=1,2,.,n)为价值系数。 (2)标准型式（也称规范形式） max之=， =1 (i=1,2,.,m) (≥0 (j=1,2,.,n) ·1
书 !"# !"#$%&’() !"#$ *!!"#$+,-./ !"!"#$%&’()*+, !!"!"#$ !#"%&’( !$")*+, #"-.!"#$/%&’( !!"-./0 %&’(#%&’!1 %()"!* " " #$! %#&# )*+,# " " #$! ’(#&##!*$$")( !(*!$#$%$*" &#$+ !#*!$#$%$" % & ’ " 23&#!#*!$#$%$""4!"#$$’(#!(*!$#$%$*&#*!$#$%$""4567($ )(!(*!$#$%$*"4897($%#!#*!$#$%$""4:;7(’ !#"&<=0!>?@A/0" %&’!$ " " #$! %#&# ,"-" " " #$! ’(#&# $)( !($!$#$%$*" &# $+ !#$!$#$%$" % & ’ " (!(
运筹学同步辅导及习题全解 二、线性规划的求解方法 1.图解法 (1)优缺点： ①图解法：图解法简单直观，求解线性规划问题时不需将数学模型化为标准型， 可以直接在平面上作图，但此法只适用于二维问题，故有一定局限性。 ②用图解法求解，有助于了解线性规划问题求解的基本原理。它可以直接看出线 性规划问题解的几种情况： 1°有惟一最优解； 2°有无穷多组最优解： 3°无可行解： 4°无有限最优解（即为无界解）。 (2)图解法的步骤： ①建立平面直角坐标系： ②图示约束条件，找出可行域： ③图示目标函数，即为一条直线； ④将目标函数直线沿其法线方向在可行域内向可行域边界平移直至日标函数。 2.单纯形法 (1)单纯形法原理 ①基本思想：从可行域中的某个基本可行解开始到另一个基本可行解，直到目标 函数达到最优。 ②理论基础： 定理1若LP问题可行域存在，则可行域是个凸集。 定理2LP问题的基可行解与可行域的顶点一一对应。 定理3若LP问题存在最优解，则一定存在一个基可行解是最优解】 (2)单纯形法的步骤及解法 ①找出初始可行基，确定初始基本可行解，建立初始单纯形表。 ②检验此基本可行解是否为最优解.即检验各非基变量x,的检验数σ，若所有 g,≤0(=m十1，n)则已经得到最优解，计算停止：否则转下一步。 ③在g,>0(=m十1，n)中若有某个检验数对应的非基变量x.的系数列向 量P。=(au,aa,.,a)T≤0，则此问题为无界解，停止计算：否则转下一步 ④根据max(a,>0)=o,确定非基变量x:为换入变量；再根据0法则 】a 确定基变量工，为换出变量。 ⑤实施枢轴运算，即以α为主元素进行枢轴运算（亦即进行矩阵的行变换），使 P。变换为第1行的元素为1，其余的元素为0：并将Xs列中的x1换为x,从而 得新的单纯形表：重复②一⑤，直到终止。 。2
0123456789:; <!!"#$+=;>) !"012 !!"BCD# ! EFG#EFGHIJK$LFMN@OPQRSTU(VW=X4&<=$ YZJ[\]^_‘E$abGcdefghPQ$ij-klmN’ "eEFGLF$jnfoFMN@OPQLFpqrst’uYZJ[vwM N@OPQFpxyz{# !. j|-}BF& #. j~}BF& $. ~YF& /. ~jm}BF!4~F"’ !#"EFGp # ! ]^J&7& " E)*+,$wY& # E%&’($4-+JM& $ U%&’(JM2GM\YY]J%&’(’ #"3452 !!"I/Gst !qr#Y3pqrYF-qrYF$J%& ’(}B’ "t q¡# ?@! ¢ 01PQY£\$¤Y¥¦§’ ?@" 01PQpqYF¨Yp©D-ª«’ ?@# ¢ 01PQ£\}BF$¤-k£\-qYF¥}BF’ !#"I/Gp ¬FG ! wYq$®kqrYF$I/¯’ "°±bqrYF¥²4}BF"°±³´q#$&# p°±(!#$¢µj !##+!#**2!$%$""¤¶·¸}BF$¹º»¼&²¤½¾- ’ #\!#(+!#**2!$%$""3¢j°±(!+ ª«p´q#$&+ p7(¿ $,+*!’!+$’#+$%$’"+"3#+$¤bPQ4~F$»¼¹º&²¤½¾- ’ $ ÀÁ %&’!!#(+"*!+$®k´q#$&+ 4ÂÃ#$&ÄÀÁ"G¤ "*%()( )( ’(+ ! )’(+ (+"*)- ’-+ ®kq#$&- 4Âw#$’ % ÅÆÇÈɺ$Z’-+4ÊËÌÍÇÈɺ!ÎÍÏÐp#Â"$Ñ ,+ #Â4Ò4pËÌ4!$2ÓpËÌ4+&ÔU56 ¿3p&- Â4&+$Õ ¸ÖpI/¯&×Ø"&%$JÙ¼’ ("(
第一章线性规划与单纯形法 3.两阶段法、大M法以及运用人工变量法求解非规范型的线性规划问题 (1)两阶段法 ①原理：此方法是将加入人工变量后的线性规划问题分成两个阶段来求解。 第一阶段：其目的是为原问题求初始基本可行解。为此，对于求极大化（或 极小化)的线性规划问题，建立一个新的人工变量的日标函数一人工变量 的系数均为一1或（十1），对新的问题： maXu=一x+1一xw+2一.一x+ 或 min=xw+1十xnt2十.+xtn an+.十a1xn十x+ =b s.t. am1x1十.十amxw 十x.+n=bn x1,x≥0，x+1,.,x+n≥0 用单纯形法求解.若=0，即所有的人工变量都变换为非基变量，说明原问 题已得到了初始基本可行解：反之，若目标函数心的值为负（或为正），则人 工变量中至少有一个为正，这表示原问题无可行解，应停止计算。 第二阶段：将第一阶段求得的基本可行解对原问题的目标函数进行优化，即 将目标函数换成原目标函数，以第一阶段得到的最终单纯形表除去人工变 量的列后作为第二阶段计算的初始表，继续用单纯形法以求得问题的最优 解 ②计算方法：单纯形法。 (2)大M法 ①原理：人工变量在目标函数中的系数确定：若目标函数为maxc,则系数为 一M:否则为M。 ②计算方法：单纯形法。 三、了解线性规划的解及其几何意义 1.可行解：凡满足线性规划约束条件的解称为可行解。 2.最优解：使目标函数达到最大的可行解称为最优解。 3.基：设A是约束方程组mXn维系数矩阵，其秩为m,B是矩阵A中m×n阶非奇异 子矩阵，则称B是线性规划问题的一个基。 4.解的几何意义： (1)若线性规划问题有可行解，其所有可行解构成的区域称为可行域，则此可行域 D=(X1∑ag5=6i=1,2,.m4≥0 必是一个凸集。 (2)线性规划问题的基本可行解与可行域D的顶点一一对应。 (3)如果线性规划问题有有限的最优解，则其目标函数的最优值一定可以在可行域的 顶点上达到。 ·3·
A*B !"#$%&’() $"6782!9 7 2:;<=>?@A2B1C!D(/-.!"#$ !!"ÚÛÜG ! st#bG¥UÝÃÞ5#$ßpMN@OPQàáÚÛÜâLF’ Ò-ÛÜ#2%p¥4sPQLqrYF’4b$ªfLãäX!1 ãåX"pMN@OPQ$-ÖpÞ5#$p%&’()))Þ5#$ p7(æ48!1!2!"$ªÖpPQ# %&’.*8&"2!8&"2#8%8&"2* 1 %().*&"2!2&"2#2%2&"2* ,"-" ’!!&!2%2’!"&"2&"2! *)! % ’*!&!2%2’*"&" 2&"2* *)* &!$%$&"$+$&"2!$%$&"2* $ % & ’ + eI/GLF"¢ .*+$µjpÞ5#$ç#Â4´q#$$èésP Q¶¸oqrYF&êë$¢%&’( . p;4ì!14í"$¤Þ 5#$3îj-4í$ï¯sPQ~YF$«»¼¹º’ ÒgÛÜ#UÒ-ÛÜL¸pqrYFªsPQp%&’(ÍBX$ U%&’(Âás%&’($ZÒ-Ûܸp}ÙI/¯ðñÞ5# $p¿ß‘4ÒgÛܹºp¯$òóeI/GZL¸PQp}B F’ " ¹ºG#I/G’ !#"ä 7 G ! st#Þ5#$\%&’(3p7(®k#¢%&’(4 %&’!$¤7(4 8/&²¤4 /’ " ¹ºG#I/G’ C!D;!"#$+;7EFGHI !"YF#ôõöMN@O)*+,pF?4YF’ #"}BF#Ñ%&’(}äpYF?4}BF’ $"q#÷ 9 ¥)*ø %:)h7(ÏÐ$2ù4 %$6¥ÏÐ 9 3 %:)Û´úû üÏÐ$¤? 6¥MN@OPQp-q’ /"Fpxýþÿ# !!"¢MN@OPQjYF$2µjYF!áp"?4Y$¤bY 0 $ *12" " #$! ’(#&# $)($($!$#$%$*&&# $++ #¥-¦§’ !#"MN@OPQpqrYF¨Y 0 p©D-ª«’ !$"$%MN@OPQjjmp}BF$¤2%&’(p}B;-kYZ\Yp ©D_’ (#(
运筹学同步辅导及习题全解 典型例题与解题技巧 【例1】市场对1、Ⅱ两种产品的需求量为：产品1在1~4月每月需10000件，5~9月每 月30000件，10~12月为每月150000件：产品Ⅱ在3~9月每月15000件，其他月 每月50000件。某厂生产这两种产品成本为：产品1在1~5月内生产每件5元 6~12月内生产每件4.50元：产品Ⅱ在1~5月内生产每件8元，6~12月内生产每 件7元。该厂每月生产两种产品能力总和应不超过120000件。产品【容积每件 0.2m3,产品Ⅱ每件0.4m3,而该厂仓库容积为15000m3,要求：(a)说明上述问题无 可行解；(b)若该厂仓库不足时，可从外厂租借。若占用本厂每月每m3库容需1 元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂 应如何安排生产，使总的生产加库存费用为最少（建立模型，不需求解）。 解题分析要建立线性规划的数学模型，需从三个方面进行考虑：第一，决策变量是什么 第二，要达到什么样的目标，即目标函数的表达式：第三，如果要达到目标，受哪 些条件约束。此题属供求问题，供求问题需从供应和需求人手」 解题过程(a)因10~12月份需求总计450000件，这三个月最多只能生产360000件，故 需10月初有90000件的库存，超过该厂最大仓库容积，故按上述条件，本 题无解 (b)考虑到生产成本、库存费用和生产能力，该厂10~12月份需求的不足只需 在7一9月份生产出来留用即可，故设 x,—第i个月生产的产品1数量， -第i个月生产的产品Ⅱ数量， ,地，分别为第i个月末产品I、Ⅱ库存数 s:,s2分别为用于第(i+1)个月库存的原有及租借的仓库容积(m)。则可 建立如下模型 min之=】 45，+7w+2+15% x-30000= y,-15000= xg十x1-30000=8 y%十-15000=s x,十6-30000=9 3y+-15000=% 10十2，-100000=10 y1十0，-50000=10 x11+x10-100000=1 y11十10-50000= s.t. x12+:=100000 y1z+e1=50000 x,十y,≤120000 (7≤i≤12) 0.2+0.4e,=s十s2 (7≤i≤11) s,≤15000 (7≤i≤12) ·4·
0123456789:; %&’()*(+, "J!# &’ª’,(Úy()pTL$4#()’\!&/*+*T!++++,$;&<*+ *$++++,$!+&!#*4+*!;++++,&()(\$&<*+*!;+++,$2,* +*;++++,’-.(ïÚy()ár4#()’\!&;*.(+,;Ë$ =&!#*.(+,/";+Ë&()(\!&;*.(+,>Ë$=&!#*.(+ ,?Ë’/-+*.(Úy()0123«S45!#++++,’()’67+, +"#%$$()(+,+"/%$$Õ/-89674!;+++%$$:L#!&"èé_;PQ~ YF&!@"¢/-89SöR$Y<-=>’¢?er-+*+ %$ 96T! Ë$Õ=e<-89R_;@eAÝ4!";Ë$BP\õö&’TLz{¾$/- «$ýCD.($Ñ2p.(Ý9£@e4}î!W=$STLF"’ ;9KL :MN@Op(VW=$TE^ÍFG#Ò-$!"#$¥HI& Òg$:HIJp%&$%&’(p¯0&ÒE$$%:%&$KL M+,)*’bQNOLPQ$OLPQTO«3TLÃP’ ;9MN !&"Q!+&!#*RTL2¹/;++++,$ïE*}c0.($=++++,$i T!+*j<++++,p9£$45/-}ä8967$iS_;+,$r Q~F& !@"FG.(ár,9£@e3.(01$/-!+&!#*RTLpSöcT \?&<*R.(wâTeY$i÷ &()))Ò(*.(p()’($$ 3()))Ò(*.(p()(($$ !($.( àU4Ò(*V()’,(9£($ 4!($4#(àU4efÒ!(2!"*9£psj¬=>p8967!%$"’¤Y $¾W= %()!* " !# #$? !/5;&( 6?3("6 " !! ($? !4!( 6!5;4#(" ,"-" &?8$++++*!? 3?8!;+++*.? &>2!?8$++++*!> 3>2.?8!;+++*.> &<2!>8$++++*!< 3<2.>8!;+++*.> &!+2!<8!+++++*!!+ 3!+2.<8;++++*.!+ &!!2!!+8!+++++*!!! 3!!2.!+8;++++*.!! &!#2!!!*!+++++ 3!#2.!!*;++++ &(23(#!#++++ !?#(#!#" +5#!(2+5/.(*4!(24#( !?#(#!!" 4!(#!;+++ !?#(#!#" &($3($!($.($4!($4#($ % & ’ + ($(