[清华大学]运筹学(第三版)课后习题答案-全17章完整版

1、运筹学课后习题答案（清华大学第三版）全17章完蓬版他切T/awm cfociti. co加加兀旬 65第一章线性规划与单纯形法内容提要一、线性规划的实际模型1. 规划问题数学模型三个要素（1）决策变虽（2）目标甬数（3）约束条件2. 线性规划问题的数学模型（1）一般形式n目标函数:max（或min）z=另中，n（=（£ = 192 > 9m）约束条件JxjQ（j = l,2,山）其中巧G = l,2,曲）为决策变量，创G=l,2,，叫j = l,2,，Q为工艺系数,介（£ = 1,2,祝）为资源系数，巧0 = 1,2,皿）为价值系数。（2）标准型式（也称规范形式）ma

2、x z = 2cixiA另如孙=bi（£ = 1，2,祝）7=1Xj NO（/ = 1,2厂皿）运筹学同步辅导及习题全解二、线性规划的求解方法1. 图解法(1) 优缺点： 图解法：图解法简单直观，求解线性规划问题时不需将数学模型化为标准型, 可以直接在平面上作图，但此法只适用于二维问题，故有一定局限性。 用图解法求解，冇助于了解线性规划问题求解的基本原理。它可以宜接看出线 性规划问题解的几种情况：1°有惟一最优解；2°有无穷多组最优解；3°无可行解；4°无有限最优解(即为无界解)。(2) 图解法的步骤： 建立平面直角坐标系； 图示约束条件，找出

3、可行域； 图示目标函数，即为一条直线； 将目标函数直线沿其法线方向在可行域内向可行域边界平移直至目标函数。2. 单纯形法(1) 单纯形法原理 基本思想:从可行域中的某个基本可行解开始到另一个基本可行解，宜到目标 函数达到最优。 理论基础：定理1若LF问題可行域存在，则可行域是个凸集。定理2 LP问题的基可行解与可行域的顶点一一对应。定理3若LP问题存在绘优解，则一定存在一个基可行解是最优解。(2) 单纯形法的步骤及解法 找出初始可行基，确定初始基本可行解,建立初始单纯形表。 检验此基本可行解是否为最优解.即检验各非基变量巧的检验数巧,若所有 aXO(j = m + l,-»n)则已经

4、得到最优解，计算停止;否则转下一步。 在巧00 =加+1,山)中若有某个检验数矶对应的非基变量如的系数列向 量则此问题为无界解，停止计算；否则转下一步。 根据maxG0)=6,确定非基变量亦为换入变量;再根据0法则0=min(2 | a。)= 确定基变量竝为换出变量。实施枢轴运算，即以为主元素进行枢轴运算(亦即进行矩阵的行变换)，使 P*变换为第1行的元素为1,其余的元素为0;并将Xb列中的也换为工&,从而 得新的单纯形表;重复，直到终止。3第一章线性规划与单纯形法3. 两阶段法、大M法以及运用人工变量法求解非规范型的线性规划问题(1) 两阶段法原理:此方法是将加入人工变量后的线性规划

5、问题分成两个阶段来求解。第一阶段:其目的是为原问题求初始基本可行解。为此，对于求极大化(或 极小化)的线性规划问题,建立一个新的人工变量的目标函数 人工变虽 的系数均为一1或(+1),对新的问题：max s=匚卄1 工卄2 龙卄班或min w=xn+1 +工卄2 8+炳auXi HaHxM + 九+1=孤 *a,xHm=bmxi，攵”玄0,攵卄1 ,，攵卄”玄。用单纯形法求解.若3=0,即所有的人工变量都变换为非基变量，说明原问 题已得到了初始基本可行解；反之，若目标函数3的值为负(或为正)，则人 工变量中至少有一个为正，这表示原问题无可行解，应停止计算。第二阶段:将第一阶段求得的基本可行解对

6、原问题的目标甬数进行优化，即 将目标函数换成原目标函数，以第一阶段得到的最终单纯形表除去人工变 量的列后作为第二阶段计算的初始表,继续用单纯形法以求得问题的最优 解。计算方法:单纯形法。(2) 大M法 原理:人工变量在目标函数中的系数确定:若目标甬数为max z,则系数为 M；否则为M。 计算方法:单纯形法。三、了解线性规划的解及其几何意义1. 可行解：凡满足线性规划约束条件的解称为可行解。2. 最优解:使目标函数达到最大的可行解称为最优解。3. 基:设A是约束方程组mXn维系数矩阵，其秩为是矩阵A中mXn阶非奇异 子矩阵，则称B是线性规划问题的一个基。4. 解的几何意义：(1) 若线性规划问

7、题有可行解，其所有可行解构成的区域称为可行域，则此可行域nD = X £<2尹,=bi 9i = 1,2,"口，$ 0;=i必是一个凸集。(2) 线性规划问题的基本可行解与可行域D的顶点一一对应。如果线性规划问题有有限的最优解，则其目标函数的最优值一定可以在可行域的 顶点上达到。 5 第一章线性规划与单纯形法运筹学同步辅导及习题全解典型例题与解题技巧【例1】市场对I、II两种产品的需求量为:产品I在14月每月需10 000件，59月每 月30 000件，1012月为每月150000件；产品d在39月每月15 000件,其他月 每月50 000件。某厂生产这两种产品成本

8、为：产品丄在15月内生产每件5元, 612刀内生产每件4. 50元;产品II在15刀内生产每件8元,612刀内生产每件7元。该厂每月生产两种产品能力总和应不超过120 000件。产品I容积每件 0. 2m3, 品U每件0. 4n?,而该厂仓库容积为15 000m3，要求：（a）说明上述问题无 可行解；（b）若该厂仓库不足时，可从外厂租借。若占用本厂每月每n?库容需1 元,而租用外厂仓库时上述费用增加为1. 5元，试问在满足市场需求情况下，该厂 应如何安排生产，使总的生产加库存费用为最少（建立模型，不需求解）。解题分析 要建立线性规划的数学模型，需从三个方面进行考虑：第一，决策变量是什么； 第二

9、,要达到什么样的目标，即目标函数的表达式;第三，如果要达到目标，受哪 些条件约束。此题属供求问题，供求问题需从供应和需求入手。解题过程（a）因1012月份需求总计450 000件，这三个月最多只能生产360 000件，故 需10月初有90 000件的库存，超过该厂最大仓库容积，故按上述条件，本 题无解；（b）考虑到生产成本、库存费用和生产能力，该厂1012月份需求的不足只需 在79月份生产岀来留用即可，故设不第分个月生产的产品I数量，M第i个月生产的产品n数址，益,3分别为第i个月末产品I、n库存数，皿,仏分别为用于第G+D个月库存的原有及租借的仓库容积（n?）。则可 建立如下模盘12 11m

10、in z= £ (4. 5益 + 7y ) + 工(sn + 1. 5s2l )>-7x730 000 =场氐+习一30 000 = z8+z8 30 000 =勺 Qo+zg 100 000 = 10 4i+zio 100 000 = Zn z】z+zii = 100 000ooo0. 2z<+0SiiWlo 000Hi 9 yi >，九4-7y715 000=w7 必+37 15 000 = 5 y9 +w8 15 000 = sJF10 4"Wg50 000 = Wio yn +wi<>50 000 = wn 312+11=50 000(

11、7<£<12)(7<£<12; # 第一章线性规划与单纯形法【例 2 max z=2x)+4观X + x26X +2工2=8s. I.«“观=3xj 皿二0解题分析题目中只有两个变量，故可用单纯形方法求解外还可用图解法求解。而图解法 比单纯形法简单宜观，故用图解法求解。解题过程图解法求解：建立平面直角坐标茶，确定决策变量的可行域。如图l l(a)所示，区域 OABCD为可行域。图 l-l(a)图 l-l(b) 画出目标函数等值线，确定优化方向。目标函数为z=2g+4d是斜率为一1/2,在纵轴上的截距为n/4的平行直 线族。若取z为一确定的值

12、，如令2=0,则得一条等值线0 = 2q +4氐，即Q = q/2；如令z=12,则得另一条等值线12 = 2q+4.2,即工2 = 无】/2 + 3,如图l-l(b)所示。容易看出，沿着目标函数的法线方向向 右上方平行移动，是它等值线的优化方向。 确定最优解。在可行域QABCD中找令？值达到最大的点。由图l-l(b)容易看出，当等值 7 运篡学同步辅导及习题全解线平移到C点时，如呆继续向上移，就离开可行域，而且此时等值线的最佳 位胃与可行域边界CB垂合，因此C点、E点以及线段CB上所有的点，都是 使目标函数值达到最大值的点，是最优解求得C点Xe = （2,3）T与B点Xp = （4,2）T此

13、时求得max z=16a目标函数 z = 2m+4“2 的通解可表示为 X=aXc+（l a）Xn,0=2=1。历年考研真题评析【题】（2005年华南理工大学）设某种动物每犬至少需要700克蛋白质、30克矿物质J00 毫克维生素u现有5种饲料可供选择，每种饲料每公斤营养成份的含量及中价如下 表所示：试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型C表1-1询料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310.50.2220,510.7310.20.20.446220.35180.50.80.8解题分析 这是一道较简单的数学规划模型问题，根据题意写出约束即可。 解

14、题过程 min z=0. 2xi +0. 7© +0. 4x3 +0.+0. 8x$+2龙 2 +竝+6龙.+18xs70OXj +0. 5 x.2 +0. 2xj+2x4 +0. 5亦$30 缶t. y0.+ 无2 +° 23+2如 +0. 8氐豪 100无1 9Z3 9，力5鼻0课后习题全解O K1 用图解法求解卜列线性规划问题，并指IU问题是具有惟一最优解、无穷多最优解、无界解还是无可行解?()max z=X +3x2(2)min十 1.z5 Xi I 10 監=50Xi 皿 AOmax z=2工i+2龙2严1十3血$3 $ t.丿4 +如鼻2bi 皿$0(4) ma

15、x z=x +x2s. t. J 0- 5*i +九=2,xirs. t> 丿 3xi 血 M 3Xi "2 鼻0解（1）图1 2中的阴影部分为此线性规划问题的可行域，日标函数？ = d十3乜，即型第一章线性规划与单纯形法=一討+专是斜率为一寺的一族平行线，易知心=3,比=0为可行解，由线性 规划的性质知，其最值在可行域的顶点取得,将直线心+3血=3沿其法线方向 逐渐向上平移，直至A点,A点坐标为(2,4)。图1一2所以max z=2 + 3X4 = 14此线性规划问题有惟一最优解。 图1一3中的阴影部分为此线性规划问题的可行域，目标函数z = q+1.5工2,即 工2 = 紀

16、+辛是斜率为一令的一族平行线，易知z】=3,d= 0为可行解，由 线性规划的性质知，其最值在可行域的顶点取得。将直线q + 1. 5匚2 =3沿其法线方向逐渐向下平移，直至B点，B点坐标为 (R)所以minz=J + 1.5X* = #此线性规划问题有惟一最优解。图1一3(3) 图1一4中阴影部分为线性规划问题的可行域，目标函数z=2劝+2乜，艮卩x2 = -xr+y是斜率为一1的一族平行线，易知刃=0®= 0为可行解。在将 直线2心+2血=0沿A其法线方向逐渐向上平移的过程中发现：目标函数的值 可以増加到无穷大。故此线性规划问题为无界解。图14图1一5(4) 如图丄一5所示，此问题

17、的可行域为空集，故此线性规划问题无可行解. 12|将下列线性规划问题变换成标准型，并列岀初始单纯形表。(1) min z= 3q+4j：22工3十5工4'41 “2+2対一竝=2X| +“2+3 尤 3 比 <M142x +3xx氐+2也乂】心2二0 口c无约束(2) max 5=zk/pk* r=l > = 1m'：XA - 1 1(/!, ,FZ)A =：|无诫耳0(£ = 1，用必=1 ,n)分析本题考查了线性规划问题的标准形式和初始单纯形表。 解CD将此线性规划问题化为标准型。令 4 =4 工6=Z其中口6 A。所以max z = min (2 )

18、 = min z则得到标准型为max 2 = 344业+2心一5(址)+0 右+0 ©Mr?Afrxl>，4 X + 2 X3 + X5 -+xio=2x + x2 +3 x3 x5+x7=14S. t« v2 X +3x2 x3 +2xs 2x6 j：fi +j：9 =2Xj »X2 9无3> X7r X10 0其中M是一个任意大的正数。初始单纯形表见表1一2。表1一2CL342-5500-M-MnGXbbXxt工3工5Xt29=10VRio2-41-21-1000120x714113-11100014工92-23-12-20-1102一£

19、4M36M4M42-3M3M55-3M0-M003(2) 在上述问题的约束条件中加入人工变量得 ftmmax s = /；处口一Mr Mr?一Mr尺仇占十丄另為=1(£ = l,2, ,n)Xft 0(2=1,2,皿必= 1,2,9 祝)其中M是一个任意大的正数。初始单纯形表见表1一3。表1一3MJ-Mail Pian Pk<Zlm77 a讥774277770C3XbbQXmXlm 竝i龙心龙-M刃1100111 000工21010000 000 _w1001000 111snM000牛+MPk乎+M Pk丑+M Ph 学+M Pk学+M Pk+M Pk 9 运筹学同步辅导及习

20、题全解 1.3在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解,并代人目标函数，确立哪一个是最优解。 (1) max z=2©+3j：2+畑+7夂4(2 ”1十3血一如一 4如=8t v Xt 2工2 + 6.7；3 7.77.4 = 3max龙=5d 2么2+3如一6如X +2 比+3 劝 +4xd =72q十观+ 如十2©=二3分析本題考査了线性规划问題的基木解的计算。 1Q 运筹学同步辅导及习题全解解(丄)在第二个约束条件两边同时乘以一1,则第二个约束条件转化为X +2 尤26丸 + 7丄4 = 3从而口的系数列向MP.='-1°

21、，竝的系数列向量2_ 1Q 运筹学同步辅导及习题全解 1Q 运筹学同步辅导及习题全解p3 =-T，益的系数列向量已=一4，_67 因为严、巳线性独立，故冇(2文 1 +3x2 =8+尤)+424 m +2 血=3 + 6g7禺令非空变量工3=工召=0,得八 呼=2从而得到一个基本可行解X= CU2,0,0)Tr】=2X1+3X2 = 8 因为几、巴线性独立，故有2x- =8 3血 +4 如列一63 3 2叼7些45X1_13令非基变量為=g=0,得彳从而得到一个基本解因为心=一 i|vo,所以该解是非可行解。 因为P】、匕线性独立，故有 1Q 第一章线性规划与单纯形法令非基变量刀2=工3=0,

22、得=_347从而得到一个基可行解X=（晋,0,0,£）T,Z3=2X + 7X# = ¥ 因为Pz.Py线性独立，故有3他3 =8 2© +4龙42无2 6x3 3 十 q 7x_45令非基变量Q=g=O,得X2 = 16从而得到一个基可行解 A 45 7 c、T 刁 45 | y/ 7 163X =(0*16,0) ,Z4=3Xi6+4Xi6=_i? 因为P2、R线性独立，故有3x2 4x< =8 2zi +42xt +7x4 =3十© +6工3_68令非基变虽xl=x3=0.得“T229_7卫=_看从而得到一个基本解X =(。路0，-p7囲为耳

23、=一右所以该解是非可行解。 因为P"巴线性独立，故有(匕4x4 =8 2z 3x2i 6x3 + 7x4 = 3 +zi 2x2令非基变量xi=x2=O,得*683145从而得到一个基本解X =(0,0,霁霁T因为=-|<o,x4=-|<o,所以该解是非可行解。比较sws可知轨=爭为垠大值，故最优解为X- =X3 =(警，0,0, 11 运筹学同步辅导及习题全解右）T,目标函数最优值为/=117因为P2.P3线性独立，故有 # 运筹学同步辅导及习题全解因为P2.P3线性独立，故有 # 运筹学同步辅导及习题全解（2）易知,Q的系数列向量的系数列向量P2 =的系数列向融R=;

24、皿的系数列向量匕=31因为R、P2线性独立，故有（X +2x2 =7 3xj4x< （2xi +匚2 = 3 工3 2x<1X1 = T11X2=T令非基变量无3=工4=0,得从而得到一个基本解X = （_*，¥，0,J）T因为 = -j<0,所以该解是非可行解。因为P】、P3线性独立，故有Xj +3xa =7 2x2 4x< 2x）+工3 = 3 工2 2x<2劝=丁11临=亏令非基变:& x2=x4=0,得.从而得到一个基可行解91 1乡炉）=（#o¥，0）t,z2=5X2 + 3X u00因为只、巴线性独立，故冇=43T令非基变量

25、怎=乂3 =0 ,得v丄 311益=石从而得到一个基本解X = （_*,0,0，¥）t因为刊=扌<0,所以该解是非可行解。因为P2.P3线性独立，故有 13 第一章线性规划与单纯形法(2尤2 +3工？ =7龙4尤41 兀2+力 3 =3 2xi 2x4令卄:基变灵2】=如=0，得严=丫 (Xs=l从而得到一个基町行解X=(0,2,l,0)T，w = 2X2+3Xl = T 因为几、巴线性相关，故，不能构成基变量， 因为匕、巴线性独立，故有(+4x，i = 7 X 22 xir2x 3 2xi x2令非基变量竝=0/昭址一f(4=1从而得到-个基可行解X=(0,0 J ,1)T，

26、N=3X l+(-6)Xl = -3比较匕9上4山6 9可知=单为最大值故最优解为X* =X“> =(纟，0,m,0)T,冃标5o o函数最优值为/=专。¥T7|分别用图解法和单纯形法求解下列线性规划问题并指出单纯形法迭代的每一步相当于图形上哪一个顶点。(1) max 乂=2+刀r3jci5可£15s. t. J 6心十2比£24% .±2 幺0(2)max z=2z】+5j：2攵i£42观12s. t. v3j：i +2x318谢1-6 分析 对单纯形表的铮次迭代要认真计算。解(1)解1:图解法。图1一3中的阴影区域为可行域，可见目标函

27、数上=2小+比在点A?处达到最 大，求解方程组产】：5 = 15可知A2的坐标为(芋冷),所以X* =(芋吕)S(6工1+2比=244444£ =2X芋+务=聲444解2：单纯形法。在上述问题的约束条件中分别加人松弛变註X3，得该线性规划问题的标准母max n=2q +如 +0z +0匕3xi +5血+竝 =156xi +2x2 +耳=24由线性规划问题的标准型可列出初始单纯形表逐步迭代，计算结果如下表所示。 表1一42100&CBXbh力比工3015351050242014c, 一町21000x33041-1/23/42X1411/301/6125一勺01/30-1/31.

28、3/4011/4-1/82Xi15/410-1/125/2400-1/12-7/24单纯形表的计算结果表明 X =(苧,#,O,O)T,z=2X字+寻=芋单纯形表迭代的第一步得X")= (0,0,15,24)T,表示图中原点(0,0)。 单纯形表迭代的第二步得X=(4,0,3,0)丁，表示图中Ax点。单纯形表迭代的第三步得 0 =(字,寻,0,0)丁,表示图中A?点。(2)解1：图解法。图1 7中的阴影区域为可行域，可见目标函数z = 2q+5工2在点人处达到最 r3xi +2工2 = 18大，求解方程组°“可知仏的坐标为(2,6)l2x2 = 12所以X，=(2,6)T,

29、" =2X2+5X6 = 34解2:单纯形法。图1-7max z=2x + 5x2 + 0x3 + 0x4 4-Ox56+d=42x2+x4=12s. t3xi +2x2 +氐=18口2山3皿心MO由线性规划问题的标准型可列出初始单纯形表逐步迭代，计算结果如表1-5所示。表1-5Cj25000ftCbxBbXi业竝埶竝0410100一0Xk12020106018320019勺一右2500004101004560101/200Xs6300-112勺一右200-5/20020011/3-1/3560101/202Xi2100-1/31/3cizi000-11/6-2/3单纯形表的计算结果

30、表明=(2,6,2,0,0)T," =2X2 + 5X6 = 34单纯形表迭代的第一步得X= (0,0,4,12,18)T,表示图中原点(0,0)。单纯形表迭代的第二步得X=(0,6,4,0,6)丁,表示图中儿点。单纯形表迭代的第三步得X = (2,6,2,0,0)丁,表示图中A3点。小结单纯形法是求解线性规划问题最有效的方法之一，要求熟练学握。O 1.5以1M题(1)为例，具体说明当目标函数中变量的系数怎样改变时，使满足约束条 件的可行域的每一个顶点，都有可能使目标函数值达到疑优。解 由目标函数 max z=cxxx+c2x2 可得 zx2 = x1 = kxx + ,其中 k=

31、SCzCiCz当k>0时，若C2>0,则目标函数在点(0,3)取得最大值;若c2<0,则目标函 15 第一章线性规划与单纯形法数征人点(4,0)取得摄大值。当一时，若e2>0,则冃标函数在Aa点(0取得最大值;若G<0,则 冃标函数在原点(0,0)取得最大值。当一3< k<-j-吋，若C2>0,则目标函数在儿点(15/4,3/4)取得最大值;若 G<0,则目标函数在原点(0,0)取得最大值。 当k<3时，若q>0,则口标函数在 久 点(4,0)取得最大值;若c2<0,则目标 函数在原点(0,0)取得最大值。L6分别用单纯形

32、法中的大M法和两阶段法求解F述线性规划问题，并指出属哪一类 解。(1) niax ±=2工1+3才?一5工3 Xi I Xz I Xj = 7s. t. v 2 Xi 5x2 + 竝 $ 10® 皿 $0(2) min 乂=2如十3怎十业 Xi +45:2+2x3 $8s. l Q 3 Xi 2xz$6(3) max纟二口刊+吒呂+辽九'5龙1+3血+ 切壬9+ 6 怎+15氐 gl 52m十如十 心5如,乂2心心°(4) max z=2xif 为+工2 +如M62“i+血2s. t. y2xz 竝 $0分析本题考査了单纯形法中的大M法，两阶段法以及解的类

33、型的概念。解(D解1：大“法。在上述线性规划问题的约束条件中加上人工变量g，禺，减去剩余变量公，得max z =2x +3力2 5易Mx4 +0近/ 4十<2十氏十Q=7s. t. v 2 Xi5匕+*5+掩=10、龙,久彳，広2 J «4，上5，匕6:2 °具中M是一个任意大的正数据此可列出单纯形表表1 6表1-6C$23-s一 M0-MQiCbXbbxzxjx$氐-MX471111007-M工6102010-1153M十23-4M2M 50M0_M工4207/21/211/2一 1/24/72Xl51一5/21/20一 1/21/2c厂利03M/2+8M/2-60

34、M/2+1-3M/2-13X24/7011/72/71/7一 1/72Xl45/7106/75/7一1/71/700-50/7-M 16/7一1/7一 M+l/7由单纯形表的计算结果得：最优解X-=(y,y,0,0,0,0)T,目标函数的最优值灯=2X字+ 3X# =字。 解2：两阶段法。先在上述线性规划问题的约束条件中加入人工变量8，说，减去剩余变量氐，得 第一阶段的数学模型min w=j：4 +x6'X匚2+匚3 + 攵4=7s. t. J 5x2+x3x5+x6 = 10“1 3X2 93，工4，氐，工6 2°据此可列出单纯形表表1一7：表1一7Cj000101aCbX

35、bbxi勿ZJ4x$乂61711110071工6102_510115Cj窃-34-20101207/21/211/2一 1/24/70Xl51-5/21/20一1/21/20-7/2一 1/20一 1/23/204/7011/72/71/7-1/70Xl45/7106/75/7一1/71/7巧一右000101第一阶段求得的最优解X=(爷,*,0,0,0,0)T,目标函数的最优值W- =0。 因人工变虽4=弧=0,所以(y,y,O,O,O,O)T是原线性规划问题的基可行解。19第一章线性规划与单纯形法 # 第一章线性规划与单纯形法于是可以进行第二阶段运算，将第一阶段的扳终表中的人工变量取消，并填

36、人原 问题的目标函数的系数,进行第二阶段的运算，见表1一8。表1一8Cj23-500iCbXbbX1工2工53工24/7011/71/72工】45/7106/7-1/75 巧00一50/7-1/7由表中计算可知，原线性规划问题的疑优解X=(,*,O,O,O,O)T,目标函数 的最优值=2X学+3X* =爭。(2)解1：大M法。在上述线性规划问题的约束条件中减去剩余变量X4，石，再分别加上人工变量N “7，得min Z=2j； +3无2+无3+0a：4 +0工5+M7：6+M7：7Xi +4x2 +2x3 +龙6=83 Xi +2xzxs十 re? =69X2 8 皿皿，工6 口7二0其中M是一

37、个任意大的正数。据此可列出单纯形表表1一9：表1一923100MAfftCbXbbXLX2xjX4zsXBXTM工68142一10102Mxr63200_1013巧一场2-4M3-6M1-2MMM003xt21/411/2-1/401/408MX725/20-11/2-1-1/214/SCj 一冇0M-r42“M丄M-丄2 "403垃9/5013/5-3/101/103/10-1/102XI"510-2/S1/S-2/S-1/S2/SCj 一可0001/21/2Af-1/2M-l/2由单纯形表的计算结果得:最优解X=(y,y,0,0,0,0,0)T,目标函数的最优 值

38、63; =2x4 + 3x4 = 7<> X存在非基变量检验数穴=0,故该线性规划问题有 0u无穷多最优解。解2：两阶段法。先在上述线性规划问题的约束条件中碱去剩余变量耳，卷，再分别加上人工变量 竝山7,得第一阶段的数学模型无1+4观+23 m+乂6=83X1 +2x205+*7 =6龙】Tz 9匚3，公4 9工5，工6工7$0据此可列出单纯形表1 一10：表 1-1000000110<CBXbb工工2工$工4工5工6工71工68142-101021XI63200-1013C, 一刁_4-6_21100021/411/2-1/401/408125/2011/2_1一1/214

39、/5-5/201-1/213/200工29/5013/5-3/101/103/10-1/100XI4/510一 2/51/5一 2/5-1/52/5勺一巧0000011A Q第一阶段求得的最优解x=(¥¥，o,ooo,o)t,目标函数的最优值奶=0。0 0因人工变量氐=工7=0.所以(£,?,0,00,0,0厂是原线性规划问题的基可行 0 o解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并 填入原问题的目标函数的系数,进行第二阶段的运算，见表1 一11。表1T123100OiCbx«b工】工2上4工539/5013/5-3/101/1

40、02X14/510-2/51/5-2/5勺一夠0001/21/2由表中计算可知，原线性规划问题的最优解X=(£,2,0,0,0,0,0)T,目标函 数的最优值£ =2X| + 3X| = 7由于存在非基变量检验数m=0,故该线性规 划问题有无穷多最优解。(3) 解1：大M法。在上述线性规划问题的第一、二个约束条件中分别加上松弛变量如，氐，在第三个约 束条件中减去剩余变量矶，再加上人工变量工7，得max z 10x 4-15x2 + 12x3 +0中 +。命 +0x$ Mx75xi +3x2 + d+m=9 5xi +6x2 + 15x3+x$=152. Xi + 力？ +天

41、 +勿=5X1 yXz，攵3，乂4，攵5 “6 山7 M0其中M是一个任意大的正数。据此可列出单纯形表表1 12： 表1T2勺101512000MCbXbb2】xz龙4无5工6XI0工493:10009/50X?1556150100MXI521100-115/25一引10 + 2M15 + M12 + M00-M010X19/S13/51/51/500090血24091611003/2M工77/50一1/53/5一2/50117/3勺一巧09哼10+響2aJ2 0M010XI3/2139/8003/16-1/800012X33/209/1611/161/1600MX?1/2043/800-7/

42、16一 3/80-1102743M021 7MS 3M 而-M0c) TAROa B由单纯形表的最终表可以看出，所有非基变量检验数巧0,且存在人工变爭5=寺，故原线性规划问题无可行解。解2：两阶段法。在上述线性规划问题的第一、二个约束条件中分别加上松弛变量斗，竝，在第三 个约束条件中减去剩余变量乙，再加上人工变量工7，得第一阶段的数学模型： min w=X7'5xi +3x2 + g+m=9 5xi +6x2 + 15x3+zs= 15s. t.2xj + x2 +x7 = 5据此可列出单纯形表表1 13：表 1-1350000001仇CbXbbXl血xa令亦龙70953110009/

43、50工515_561501000000001A.CbXbbXI工2工3工4X5工6工71工7521100115/2勺一巧-2T_】00100XI9/S13/51/51/500090XS24091611003/21X77/S0-1/53/5 2/50-117/3c厂利0T/53/5-2/50100工】3/2139/8003/161/80000工83/209/1611/161/160011/2043/800一7/16-3/80100 一叼043/8007/163/8010第一阶段求得最优解X=(多,0冷,0,0,0,*)T。因人工变量帀=*工0,且非基变量检验数6>0,所以原线性规划问题无可行解。(4) 解1：大M法。在上述线性规划问题的约束条件中分别减去剩余变嵐亞，氐，益，再加上人工变量 龙5 5，力9，得max z=2xi 观 + 2g +0q Mxs +0x5 Mx7 +0如一Mr?x +氐 +m R4 +n = 6 2xi +工3 工6 +© =2S. t v2x2 工3 工8 +匚9 =021 92 93，力4 工乂 ,乞6 yXy 5X5其中M是一个任意大的正数。据此可列出单纯形表表1 14：表1T