第一章线性规划与单纯形法内容提要一、线性规划的实际模型1.规划问题数学模型三个要素（1）决策变量（2）目标函数（3）约束条件2.线性规划问题的数学模型(1)一般形式目标函数：max（或min）一Cjrj-Nagtj≤(=,≥)bi(i=1,2,,m)约束条件：-(r≥0(i=1.2....,n)其中r（j=1,2,,n）为决策变量.a,i=1,2,,m；j=1,2,…,n）为工艺系数，b（i=1,2,.,m）为资源系数.c,Gj=12,n）为价值系数。（2）标准型式（也称规范形式）max=cjr,j-1(i=1,2,...,m)ayr=b,(r≥0(j=1,2,"",n)
书 !"# !"#$%&’() !"#$ *!!"#$+,-./ !"!"#$%&’()*+, !!"!"#$ !#"%&’( !$")*+, #"-.!"#$/%&’( !!"-./0 %&’(#%&’!1 %()"!* " " #$! %#&# )*+,# " " #$! ’(#&##!*$$")( !(*!$#$%$*" &#$+ !#*!$#$%$" % & ’ " 23&#!#*!$#$%$""4!"#$$’(#!(*!$#$%$*&#*!$#$%$""4567($ )(!(*!$#$%$*"4897($%#!#*!$#$%$""4:;7(’ !#"&<=0!>?@A/0" %&’!$ " " #$! %#&# ,"-" " " #$! ’(#&# $)( !($!$#$%$*" &# $+ !#$!$#$%$" % & ’ " (!(
运筹学同步辅导及习题全解二、线性规划的求解方法1.图解法（1）优缺点：①图解法：图解法简单直观，求解线性规划问题时不需将数学模型化为标准型，可以直接在平面上作图，但此法只适用于二维问题，故有一定局限性。2用图解法求解，有助于了解线性规划问题求解的基本原理。它口以直接看出线性规划问题解的几种情况：1°有惟一最优解；2°有无穷多组最优解；3°无可行解；4°无有限最优解（即为无界解）。（2)图解法的步骤：①建立平面直角坐标系；②图示约束条件，找出可行域；③图示目标函数，即为一条直线；④将目标函数直线沿其法线方向在可行域内向可行域边界平移直至目标函数。2.单纯形法(1)单纯形法原理①基本思想：从可行域中的某个基本可行解开始到另一个基本可行解，直到目标函数达到最优。②理论基础：定理1若LP问题可行域存在，则可行域是个凸集。定理2LP问题的基可行解与可行域的顶点一一对应。定理3，若LP问题存在最优解，则一定存在一个基可行解是最优解。（2）单纯形法的步骤及解法①找出初始可行基，确定初始基本可行解，建立初始单纯形表。②检验此基本可行解是否为最优解.即检验各非基变量工，的检验数。，，若所有,≤0(j=m十1，，n）则已经得到最优解，计算停止；否则转下一步。③在c,>0(j=m十1，""，n)中若有某个检验数对应的非基变量r的系数列向量P=（a，a2，，am）T≤0，则此问题为无界解，停止计算：否则转下一步。④根据max（o,>0）=，确定非基变量x为换人变量：再根据6法则0=min(lax>0)-aiaa确定基变量工，为换出变量。实施枢轴运算，即以a为主元素进行枢轴运算（亦即进行矩阵的行变换），使P.变换为第1行的元素为1，其余的元素为0：并将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），对新的问题：maxw=-2,+1-1.+2...—7+m或minw=1u++1+2+.+1u+m=banr+...+ant++)s, t..+r+m=bmama+..+amr.i,.,r.>0,r.+i,,r.+m>0用单纯形法求解.若=0，即所有的人工变量都变换为非基变量，说明原问题已得到了初始基本可行解：反之，若目标函数的值为负（或为正），则人工变量中至少有一个为正，这表示原问题无可行解，应停止计算。第二阶段：将第一阶段求得的基本可行解对原问题的目标函数进行优化，即将目标函数换成原目标函数，以第一阶段得到的最终单纯形表除去人工变量的列后作为第二阶段计算的初始表，继续用单纯形法以求得问题的最优解。②计算方法：单纯形法。（2）大M法①原理：人工变量在目标函数中的系数确定：若目标函数为max之，则系数为一M；否则为M。②计算方法：单纯形法。三、了解线性规划的解及其几何意义1.可行解：凡满足线性规划约束条件的解称为可行解。2.最优解：使目标函数达到最大的可行解称为最优解。3.基：设A是约束方程组mXn维系数矩阵，其秩为m，B是矩阵A中mXn阶非奇异子矩阵，则称B是线性规划问题的一个基。4.解的几何意义：（1）若线性规划问题有可行解，其所有可行解构成的区域称为可行域，则此可行域1D-(Xagr,-bi.i=1,2,",mr,≥0-1必是一个凸集。（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】市场对I、Ⅱ两种产品的需求量为：产品在1～4月每月需10000件，5～9月每月30000件，10～12月为每月150000件；产品Ⅱ在3～9月每月15000件，其他月每月50000件。某厂生产这两种产品成本为：产品1在1～5月内生产每件5元，612月内生产每件4.50元；产品Ⅱ在1～5月内生产每件8元，6～12月内生产每件7元。该厂每月生产两种产品能力总和应不超过120000件。产品I容积每件0.2m2.产品Ⅱ每件0.4m，而该厂仓库容积为15000m，要求：（a）说明上述问题无可行解；（b）若该厂仓库不足时，可从外厂租借。若占用本厂每月每m库容需1元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂应如何安排生产，使总的生产加库存费用为最少（建立模型，不需求解）。解题分析要建立线性规划的数学模型，需从三个方面进行考虑：第一，决策变量是什么；第二，要达到什么样的目标，即目标函数的表达式；第三，如果要达到目标，受哪些条件约束。此题属供求问题，供求问题需从供应和需求入手。（a）因10~12月份需求总计450000件，这三个月最多只能生产360000件，故解题过程需10月初有90000件的库存，超过该厂最大仓库容积，故按上述条件，本题无解；（b）考虑到生产成本、库存费用和生产能力，该厂10～12月份需求的不足只需在7～9月份生产出来留用即可，故设;——第i个月生产的产品I数量，yi——第；个月生产的产品IⅡI数量，，分别为第i个月末产品I、Ⅱ库存数，S1i，S2i分别为用于第（i十1）个月库存的原有及租借的仓库容积（m）。则可建立如下模型1211E(s +1. 5s2i)min=(4.5r+7y)+2-(1-30000=2-15000=ys+-15000=wg1十2-30000=28yg+wg-15000=s1g十z8-30000=2gT10+2g—100000=210y10+wg50000=wioyn+wo-50000-wm111+210-100000=21s. t..T12+2=100000y2+wu=50000+≤120000(7≤i≤12)0.2z,+0.4w;=81/+s2i(7≤i<1)S1/≤15000(7≤i≤12)Ti.yi.zi,wi,s1i,s2≥0.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#($ % & ’ + ($(
第一章线性规划与单纯形法【例2】max=2r+4r26+2≤8s. t.12<311,12≥0解题分析题目中只有两个变量，故可用单纯形方法求解外还可用图解法求解。而图解法比单纯形法简单直观，故用图解法求解。解题过程图解法求解：①建立平面直角坐标系，确定决策变量的可行域。如图1一1（a）所示，区域OABCD为可行域。图1-1(a)图1-1(b)②画出目标函数等值线，确定优化方向。目标函数为=2r1十4x2是斜率为一1/2，在纵轴上的截距为/4的平行直线族。若取为一确定的值，如令=0，则得一条等值线0=2i十42，即2=一r/2；如令=12，则得另一条等值线12=2十4x2，即32=一11/2十3，如图1-1（b）所示。容易看出，沿着目标函数的法线方向向右上方平行移动，是它等值线的优化方向。③确定最优解。在可行域0ABCD中找令之值达到最大的点。由图1-1（b)容易看出，当等值.5
A*B !"#$%&’() "J"# %&’!*#&!2/&# ,"-" &!2 &##= &!2#&##> &##$ &!$&#$ % & ’ + ;9KL Q%3cjÚ#$$iYeI/GLF<WYeEFGLF’ÕEFG XI/GHIJK$ieEFGLF’ ;9MN EFGLF# ! ]^J&7$®k!"#$pY’$E !8!!&"µ$" +7890 4Y’ E!A!!&" E!A!!@" " Yw%&’(Z;M$®kBX’ %&’(4!*#&!2/&# ¥[\48!-#$\]È_p^_4!-/p]J M‘’¢a!4-®kp;$$b!*+$¤¸-+Z;M+*#&!2/&#$&# *8&!-#&$b!*!#$¤¸-+Z;M!#*#&!2/&#$ &#*8&!-#2$$$E!:!!@"µ’6cvw$d%&’(pGM e_]f$¥uZ;MpBX’ # ®k}BF’ \Y+7890 3b! ;}äpD’gE!:!!@"6cvw$hZ; (%(