运筹学作业-王程130404026

运筹学作业

王程 信管1302 130404026

目录

运筹学作业 .................................................................................. 1 第一章 线性规划及单纯形法 ................................................... 3 第二章 线性规划的对偶理论与灵敏度分析 ......................... 24 第三章第四章第五章第六章第七章第八章第九章

运输问题 ................................................................... 53 ..................................................................... 63 整数规划 ................................................................... 73 ................................................................. 85 动态规划 ................................................................... 94 ............................................................. 97 ..................................................................... 99 目标规划 非线性规划 图与网络分析 网络计划第一章 线性规划及单纯形法

1.1分别用图解法和单纯形法求下列线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

（1）minz?2x1?3x2（2）maxz?3x1?2x2?4x1?6x2?6?2x1?x2?2?? s.t.?3x1?2x2?4 s.t.?3x1?4x2?12

?x1,x2?0?x1,x2?0??（3）maxz?10x1?5x2（4）maxz?5x1?6x2?3x1?4x2?9?2x1?x2?2? s.t.?5x1?2x2?8 s.t.??2x1?3x2?2

??x1,x2?0?x1,x2?0?? 解：⑴图解法：

x2212(6/5 1/5).3OO3x1x1

2161x1?z经过点（，）时，z最小，且有无穷多个最优解。

5533 ⑵图解法：

当x2?x232O124x1

该问题无可行解。 ⑶图解法：

x24A(0,9/4)B(1,3/2)OC(5/8,0)3x1

13（，）1 当x2??2x1?z经过点时，z取得唯一最优解。

25 单纯形法：

在上述问题的约束条件中分别加入松弛变量x3,x4， 化为标准型：

maxz?10x1+5x2?0x3?0x4?3x1?4x2?x3?9?s.t.?5x1?2x2?x4?8?x,x,x,x?0?1234

由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：

CjCB00XBx3x4cj -zj010x3x1cj -zj510x2x1cj -zj3/2121/58/5b9810 5 0 0 x13x24x31x40θi38/5520110 5 0 00114/52/510-3/51/53/240 1 0 -20101005/14-1/7-5/14-3/142/7-25/1433单纯形表的计算结果表明：X*?(,1,0,0)T,Z*?10??5?1?2022单纯形表迭代的第一步得X（0）?(0,0,9,8)T，表示图中原点O（0,0）821

单纯形表迭代的第二步得X（1）?(,0,,0)T，表示图中C点553单纯形表迭代的第三步得X（2）?(1,,0,0)T，表示图中B点2⑷图解法：

以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表： cj 2 3 1 0 0 θi CB XB b x1 x2 x3 x4 x5 3 2 x2 x1 9/5 4/5 0 1 0 1 0 0 3/5 -2/5 0 -3/10 1/5 1/2 1/10 -2/5 1/2 Tcj-zj ?49?由表中计算可知，原线性规划问题的最优解X*??，，0，0，0，0，0?，目标函数的

?55?49最优值z*?2??3??7，由于存在非基变量检验数?3=0，故该线性规划问题

55有无穷多最优解。

（2）解：大M法： 在上述线性规划问题的约束条件中加上松弛变量x4,x5,减去剩余变量x6,再加上 人工变量x7,得 maxz?10x1+15x2?12x3?0x4?0x5?0x6?Mx7?5x1?3x2?x3?x4?9??5x?6x?15x?x?15?1235 s.t.??2x1?x2?x3?x6?x7?5??x1,x2,x3,x4,x5,x6,x7?0 其中M是一个任意大的正数，据此可列出单纯形表如下： cj 10 15 12 0 CB XB b x1 x2 x3 x4 0 x4 9 0 x5 15 -M x7 5 cj-zj 10 x1 9/5 0 x5 24 -M x7 7/5 cj-zj [5] -5 2 10+2M 1 0 0 0 0 x5 0 1 0 0 0 1 0 0 0 x6 0 0 -1 -M 0 0 -1 -M x7 θi 3 6 1 15+M 3/5 9 -1/5 M9? 51 15 1 12+M 1/5 [16] 3/5 310+M5 1 0 0 0 1/5 1 -2/5 2?2?M 50 9/5 0 - 1 5/2 0 0 9 0 3/2 1 7/3 ?M 0 10 x1 3/2 12 x3 3/2 -M x7 1/2 cj-zj 1 0 0 0 39/80 9/16 -43/80 2743?M 8800 1 0 0 3/16 1/16 -7/16 ?-1/80 1/16 -3/80 0 0 -1 0 0 1 21753?M ??M ?M 0 816880 由单纯性表的最终表可以看出，所有非基变量检验数?j?0 ，且存在人工变量

x7?1 ，故原线性规划问题无可行解。 2两阶段法：在上述线性规划问题的约束条件中加上松弛变量x4,x5,减去剩余变量x6,再加上人工变量x7,得第一阶段的数学模型 min w=x7?5x1?3x2?x3?x4?9??5x?6x?15x?x?15?1235 s.t.??2x1?x2?x3?x6?x7?5??x1,x2,x3,x4,x5,x6,x7?0据此可列出单纯初始形表如下： cj 0 0 CB XB b x1 x2 0 0 1 x4 x5 x7 9 15 5 [5] -5 2 -2 1 0 0 0 1 0 0 0 *0 x3 1 15 1 -1 1/5 [16] 3/5 3/5 0 1 0 0 T0 x4 1 0 0 0 1/5 1 -2/5 -2/5 3/16 1/16 -7/16 7/16 0 x5 0 1 0 0 0 1 0 0 -1/80 1/16 -3/80 3/80 0 x6 0 0 -1 1 0 0 -1 1 0 0 -1 1 1 x7 0 0 1 0 0 0 1 0 0 0 1 0 θi 9/5 - 5/2 9 3/2 7/3 3 6 1 -1 3/5 9 -1/5 -1/5 39/80 9/16 -43/80 43 80cj-zj 10 x1 9/5 0 x5 24 1 x7 7/5 cj-zj 0 0 1 x1 x3 x7 cj-zj 3/2 3/2 1/2 11??33第一阶段求得最优解X??，0，0，0，0，?，因人工变量x7??0 ，且非基变

22??22量检验数?j?0，所以原线性规划问题无可行解。 1.5 考虑下述线性规划问题：

maxz?c1x1?c2x2

?a11x1?a12x2?b1?s.t.?a21x1?a22x2?b2

? x,x?012?式中，1?c1?3,4?c2?6,?1?a11?3,2?a12?5,8?b1?12,2?a21?4,4?a22?6,10?b2?14，试确定目标函数最优值的下界和上界。解：（1）上界对应的模型如下（c，b取大，a取小）

maxz?3x1?6x2??1x1?2x2?12 s.t.?2x?4x?14

?12?x,x?0?12 最优值（上界）为：21；

（2）下界对应的模型如下（c，b取小，a取大）

maxz?x1?4x2?3x1?5x2?8 s.t.?4x?6x?10

?12?x,x?0?12 最优值（下界）为：6.4。

1.7 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数a?l的值。

表 1-21 项目 x1 x2 x3 x4 x5x4 6 (b) (c) (d) 1 0 x5 1 -1 3 (e) 0 1cj -zj (a) -1 2 0 0x1 (f) (g) 2 -1 1/2 0x5 4 (h) (i) 1 1/2 1cj -zj 0 -7 (j) (k) (l)

解：a b c d e f g h i j k l3 2 4 -2 2 3 1 0 5 -5 -3/2 01.8 若X⑴,X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。

证明：设X(1)和X(2)满足：maxz?CTX?AX?b ??X?0 对于任何0?a?1，两点连线上的点 X满足：X?aX(1)?(1?a)X(2)也是可行解，且 CTX?CTaX(1)?CT(1?a)X(2) ?CTaX(1)?aCTX(2)?CTX(2) ?CTX(2) 所以X也是最优解。 1.9 考虑线性规划问题

maxz??x1?2x2?x3?4x4? x1?x2 ?x4?4?2? (i)? s.t.?2x1?x2?3x3?2x4?5?7? (ii)

?x,x,x,x?0?1234模型中?，?为参数，要求：

⑴ 组成两个新的约束(i)'=(i)+(ii),(ii)'=(ii)-2(i)，根据式(i)'和式(ii)'，以

x1,x2为基变量，列出初始单纯形表；

(i) x1?x3?x4?3?2?解：

(ii) x2?x3?1??Cj→ CB 基 b α x1 3+2β2 x2 1-βcj-zj

α 2 1 -4 x1 x2 x3 x4 1 0 1 -10 1 -1 00 0 3-α α-4

⑵ 在表中，假定?=0 ，则? 为何值时，x1,x2为问题的最优基； 解：如果?=0，则当3???4时，x1,x2为问题的最优基变量。 ⑶ 在表中，假定?=3 ，则? 为何值时，x1,x2为问题的最优基。 解：如果?=3，则当-1???1时，x1,x2为问题的最优基变量。 1.10 试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性的假设将被违背。

答：线性的含义：一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一实数；四是确定性，指模型中的参数cj,aij,bi 均为确定的常数。

很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购买就可以得到折扣优惠。

1.11 判断下列说法是否正确，为什么？

m ⑴ 含n个变量m个约束的标准型的线性规划问题，基解数恰好为Cn个；

m?C 答：错误。基本解的个数=基的个数n

⑵ 线性规划问题的可行解如为最优解，则该可行解一定为基可行解；

答：错误。当有唯一最优解时，最优解是可行域顶点，对应基本可行解；当

表 1-26调查对象大学生商界人士电话调查周一至周五 周六、日3.02.53.53.0元/人次问卷调查5.05.0解：设x11,x21为周一至周五对大学生和商界人士电话调查人数，x12,x22为双休日对上述人员电话调查人数，x13,x23分别为问卷调查人数，则数学模型为 minz?3.0x11?2.5x12?5.0x13?3.5x21?3.0x22?5.0x23??x?x?x?x?x?x?600?111213212223?x11?x12?x13?250??x?x?180 s.t.?1323?x12?0.8?x11?x12??x21?0.8?x?x?2112最优解x11?0,x12?350,x13?0,x21?58,x22?11,x23?180,z*?20141.17 生产存储问题。某厂签订了5种产品（i=1，?，5）上半年的交货合同。已知各产品在第j月（j=1，?，6）的合同交货量Dij ，该月售价sij 、成本价cij 及生产1件时所需工时aij 。

该厂第j月的正常生产工时为tj，但必要时可加班生产，第j月允许的最多加班工时不超过tj＇，并且加班时间内生产出来的产品每件成本增加额外费用cij＇元。若生产出来的产品当月不交货，每件库存1个月交存储费pi元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。

'解：设xij为i种产品j月正常时间生产数，xij为加班时间生产数，模型为j6??''' maxz???[(sij?cij)xij?(sij?cij?cij)xij]??pi???(xik?xik?Dik)?i?1j?1c?1?j?1k?1?565?5??aijxij?tj (j?1,?,6)?c?1?5''ax?t??ijijj (j?1,?,6) s.t.?i?1j?j'??(xik?xik)??Dik (j?1,?,6)?k?1k?1?x?0?ij1.18 宏银公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额贷款：2003年—100万元，2004年—150万元，2005年—120万元，2006年—110万元。以上贷款资金均需于2002年年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目：

⑴ 于2003年年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元；

⑵ 于2003年年初购买B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元；

⑶ 于2004年年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元；

⑷ 于每年年初将任意数额的资金存放于银行，年息4%，于每年年底取出。 求宏银公司应如何运用好这笔筹集到的资金，使2002年年底需筹集到的资金数额为最少。

解：用xij(i为第1,2,3年年初，j?1,2,3,4分别为A,B,C,D四类投资数）min z?480?(x11?x12?x13?x14)?(x21?x22?x23?x24)?(x31?x32?x33?x34)?x11?(1?140%)?110??x11?60?x12(1?125%)?120??x12?90?s.t.?x23(1?130%)?110?x?50?23?(x11?x12?x13?x14)(1?4%)?100??(x21?x22?x23?x24)(1?4%)?150??(x31?x32?x33?x34)(1?4%)?120

1.19 红豆服装厂新推出一款时装，据经验和市场调查，预测今后6个月对该款时装的需求为：1月—3000件，2月—3600件，3月—4000件，4月—4600件，5月—4800件，6月—

5000件。生产每件需熟练工人工作4h，耗用原材料150元，售价为240元/件。该厂1月初有熟练工80人，每人每月工作160h。为适应生产需要，该厂可招收新工人培训，但培训一名新工人需占用熟练工人50h用于指导操作，培训期为一个月，结束后即可上岗。熟练工人每月工资2000元，新工人培训期间给予生活补贴800元，转正后工资与生产效率同熟练工人。又熟练工人（含转正一个月后的新工人）每月初有2%因各种原因离职。已知该厂年初已加工出400件该款时装作为库存，要求6月末存库1000件。又每月生产出来时装如不在当月交货，库存费用为每件每月10元。试为该厂设计一个满足各月及6月末库存要求，又使1～6月总收入为最大的劳动力安排方案。

解：设该厂每月初拥有熟练工人数xt(t?1,?,6),每月招收培训的新工人数为yt,该厂月末库存为It，一月初库存为Io，Rt为各月对时装的需求数，则数学模型为 maxz??(每月销售收入?熟练工人工资?培训工人补助?原材料费?库存费）i?16?It?1?40xt?12.5yt?Rt?I?I?40x?40y?12.5y?R?tt?1tt?1tt s.t.??xt?1?0.98xt?yt??xt,yt?0解得z*=875122元，各月有关数字如下：txt1 2 3 4 5 6804.07559.3482.4725.800106.6226.450130.930637.38128.320970.02125.7501000ytIt

第二章 线性规划的对偶理论与灵敏度分析

2.1 写出下列线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的对偶问题。

(1) min z?2x1?2x2?4x3?x1?3x2?4x3?2?2x?x?3x?3?123 s.t.??x1?4x2?3x3?5?x1,x2?0,x3无约束?解：对偶问题：maxw?2y1?3y2?5y3?y1?2y2?y3?2?3y?y?4y?2?123 s.t.? 4y?3y?3y?423?1?y1?0,y2?0,y3无约束? 对偶的对偶问题：minv?2m1?2m2?4m3?m1?3m2?4m3?2?2m?m?3m?3?123 s.t.??m1?4m2?3m3?5?m1,m2?0,m3无约束 ?(2) maxz?5x1?6x2?3x3?x1?2x2?2x3?5??x?5x?x?3?123 s.t.? 4x?7x?3x?823?1?x1无约束，x2?0,x3?0?解：对偶问题：minw?5y1?3y2?8y3?y1?y2?4y3?5?2y?5y?7y?6?123 s.t.??2y1?3y2?3y3?3?y1无约束，y2?0,y3?0? 对偶的对偶问题：maxv?5m1?6m2?3m3?m1?2m2?2m3?0??m?5m?3m?0?123 s.t.??4m1?7m2?3m3?0?m1无约束，m2?0,m3?0 ?(3) minz???cijxiji?1j?1mn?n??xij?ai (i?1,?,m)?j?1?m s.t.??xij?bj (j?1,?,n)?i?1?xij?0 (i?1,?,m,j?1,?,n)??解：对偶问题：maxw??aiyi??bjyj?mi?1j?1mn??yi?yj?m?cij (i?1,?,m,j?1,?,n) s.t.???yi无限制，i?1,?,n?m 对偶的对偶问题： minv???cijxiji?1j?1mn?n??xij?ai (i?1,?,m)?j?1?m s.t.??xij?bj (j?1,?,n) ?i?1?xij?0 (i?1,?,m,j?1,?,n)??

(4) maxz??cjxjj?1n?n??aijxj?bi (i?1,?,m1?m)?j?1n??ax?b (i?m?1,m?2,?,m) s.t.??ijji11?j?1?xj?0 (j?1,?,n1?n)???xj无约束 (j?n1?1,?,n)解：对偶问题：minw?b1y1?b2y2??bmym?m??aijyi?cj (j?1,2,?,n1)?i?1?m s.t.??aijyi?cj (j?n1?1,n1?2,?,n)?i?1?yi?0 (i?1,?,m1)??yi无约束 (j?m1?1,?,m) 对偶的对偶问题：maxz??cjxjj?1n?n??aijxj?bi (i?1,?,m1?m)?j?1 n?? s.t.??aijxj?bi (i?m1?1,m1?2,?,m)?j?1?xj?0 (j?1,?,n1?n)???xj无约束 (j?n1?1,?,n)

2.2 判断下列说法是否正确，并说明为什么。

⑴如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错误。如果原问题是无界解，则对偶问题无可行解。

⑵如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错误。如果对偶问题无可行解，也可能是因为原问题是无界解。

⑶在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； 答：错误。如果原问题是求极小，则结论相反。 ⑷任何线性规划问题具有唯一的对偶问题。 答：正确。

2.5 已知某求极大线性规划问题用单纯形法求解时的初始单纯形表及最终单纯

形表如表2-30所示，求表中各括号内未知数(a)～(l)的值。

cj → CB 基 b000x4x5x6cj-zj?3x11(a)232x211(c)22x31212?0x4100000x60010x50100(b)1520032x4x1x2cj-zj5/425/45/20100001(k)(d)(e)(f)(g)(l)000-1/43/4(h)-5/4-1/4(i)1/2(j)

解：l=1，k=0，a=2，c=3，h=-1/2，b=10，e=5/4，f=-1/2，d=1/4， g=-3/4，i=-1/4，j=-1/4. 2.6 给出线性规划问题

minz?2x1?3x2?5x3?6x4

?x1?2x2?3x3?x4?2?s.t.??2x1?x2?x3?3x4??3

?x?0 (j?1,?,4)?j⑴写出其对偶问题；⑵用图解法求解对偶问题；⑶利用⑵的结果及根据对偶问题性质写出原问题最优解。

解：⑴其对偶问题为：

minw?2y1?3y2?y1?2y2??2?2y?y??312?? s.t.?3y1?y2??5

?y?3y??62?1??y1?0,y2?0⑵图解法求解：

y2y18119 求得最优解为y1??,y2?,z*??

555（3）根据互补松弛型性质可以得到最优解X*?(7/5,0,1/5,0) 2.7 给出线性规划问题

maxz?3x1?2x2?5x3?x1?2x2?x3?500?3x ?2x?460?13 s.t.??x1?4x2 ?420?? x1,x2,x3?0⑴写出其对偶问题；⑵利用对偶问题性质证明原问题目标函数值z?1360 。 解：⑴其对偶问题为：

minw?500y1?460y2?420y3?y1?3y2?y3?3?2y ?4y?2?13s.t.??y1?2y2 ?5??y1,y2,y3?0

51 ⑵易得y1?0,y2?,y3? 是对偶问题的一个可行解，带入目标函数得

22w?1360 ，故原问题的目标函数值z?1360。

2.8 已知线性规划问题

maxz?x1?x2??x1?x2?x3?2 s.t.???2x1?x2?x3?1

?x,x,x?0?123试根据对偶问题性质证明上述线性规划问题目标函数值无界。

解：x1?2,x2?x3?0是原问题的一个可行解，原问题的对偶问题为： minw?2y1?y2??y1?2y2?1 (1)? y? y?1 (2) ?12 s.t.?? y1? y2?0 (3)?? y1,y2?0 (4)由于(1)和(4)是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。2.9 给出线性规划问题

maxz?2x1?4x2?x3?x4?x1?3x2 ?x4?8??2x1?x2 ?6 ?s.t.? x2?x3?x4?6?x?x?x ?923?1??xj?0 (j?1,?,4)

2，4，0),试根据对偶要求：⑴写出其对偶问题；⑵已知原问题最优解为X?(2，理论，直接求出对偶问题的最优解。

解：⑴其对偶问题为：

*minw?8y1?6y2?6y3?9y4?y1?2y2 ?y4?2??3y1?y2?y3?y4?1 s.t.? y?y?1?34? y?y?113???yj?0(j?1,?,4)*

2，4，0)，带入原问题，第4个约束不等式 ⑵已知原问题最优解为X?(2，成立，故y4?0。又由于x1,x2,x3大于0，上面对偶问题前3个约束取等号，故

43得到最优解：Y*=（，,1,0）。

552.10 已知线性规划问题A和B如下： 问题Amaxz??cjxj 影子价格j?1n

?n??a1jxj?b1 y1?j?1?n??a2jxj?b2 y2s.t.?j?1?n??a3jxj?b3 y3?j?1?x?0 (j=1,?,n)?j 问题Bmaxz??cjxj 影子价格j?1n

?n?1??5a1jxj?5b1 y?j?1?n11?2??a2jxj?b2 y5s.t.?j?15?n??(a3j?3a1j)xj?b3?3b1 y?3?j?1?x?0 (j?1,?,n)?j

试分别写出

?i同yi(i?1,2,3)间的关系式。 y?1?解：y11?2?5y2,y?3?y3?y1 . y1,y53（2） minz?5x1?2x2?4x3

2.11 用对偶单纯形法求解下列线性规划问题。

（）1 minz?4x1?12x2?18x3?x1 ?3x3?3? s.t.? 2x2?2x3?5?x,x,x?0?123解：⑴先将问题改写为：

?3x1?x2?2x3?4? s.t.?6x1?3x2?5x3?10

?x,x,x?0?123

maxz'??4x1?12x2?18x3?0x4?0x5??x1?3x3?x4??3 s.t.??2x?2x?x??5?235?x,x,x,x,x?0?12345

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：

cj → CB 基 b00x4x5cj-zj0-12x4x2cj-zj-18-12x3x2cj-zj13/2-35/2-3-5-4x1-10-4-10-41/3-1/3-2-12x20-2-12010010-18x3-3-2-18-31-61000x4100100-1/31/3-20x501001/2-60-1/2-6

3由上表可得原问题最优解为X*=(0,,1)，代入目标函数得 z?36。

2⑵先将问题改写为：

maxz'??5x1?2x2?4x3?0x4?0x5??3x1?x2?2x3?x4??4 s.t.??6x?3x?5x?x??10?1235?x,x,x,x,x?0?12345

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：

cj → CB 基 b00x4x5cj-zj0-2x4x2cj-zj-5-2x1x2cj-zj2/32-2/310/3-4-10-5x1-3-6-5-12-1100-2x2-1-3-2010010-4x3-2-5-4-1/35/3-2/31/31-1/30x4100100-12-10x50101/31/32/3-1/34/31/3

2由上表可得原问题最优解为X=(,2,0)，代入目标函数得 z?3*22。 3

2.12 考虑如下线性规划问题：

minz?60x1?40x2?80x3?3x1?2x2?x3?2?4x?x?3x?4?23 s.t.?1?2x1?2x2?2x3?3??x1,x2,x3?0

要求：⑴写出其对偶问题；⑵用对偶单纯形法求解原问题；⑶用单纯形法求解

其对偶问题；⑷对比⑵与⑶中每步计算得到的结果。 解：⑴其对偶问题为：

maxw?2y1?4y2?3y3?3y1?4y2?2y3?60?2y?y?2y?40123 s.t.? ??y1?3y2?2y3?80??y1,y2,y3?0⑵先将问题改写为

maxz'??60x1?40x2?80x3?0x4?0x5?0x6??3x1?2x2?x3?x4??2??4x?x?3x?x??41235 s.t.????2x1?2x2?2x3?x6??3??x1,x2,x3,x4,x5,x6?0

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：

cj → CB 基 b000x4x5x6cj-zj?-60x1-3-4-2-60-40x2-2-1-2-40-80x3-1-3-2-80?0x4100000x60010x50100-2-4-30-60-40x4x1x2cj-zj11/65/62/3010000105/32/31/3-80/310001/31/3-1/3-20/3-5/61/6-2/3-50/352由上表可得原问题最优解为X=(,,0)，代入目标函数得 z?63*230。 3 ⑶用单纯形法求解其对偶问题：

cj → CB 基 b000x4x5x6cj-zj?2x132124x241343x32223?0x4100000x60010x50100604080430x2x3x6cj-zj20/350/3 80/31/35/6-5/3-11/6100001001/3-1/6-2/3-5/6-1/3 2/3-1/3-2/300102050,)，代如目标函数w?由上表可得对偶问题最优解为X=(0,33*230。 3

2.13 已知线性规划问题：

maxz?2x1?x2?x3?x1?x2?x3?6?s.t.??x1?2x2?4?x,x,x?0?123⑴ 目标函数变为maxz

先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。

?2x1?3x2?x3;

?6??3?⑵ 约束右端项由??变为??；

?4??4?⑶ 增添一个新的约束条件?x1?2x3解：先用单纯形法计算如下：

?2。

cj → CB 基 b00x4x5cj-zj0-1x1x5cj-zj610642x11-12100-1x212-113-31x310111-10x410011-20x5010010

由上表可得最优解为x1?6,x2?0,x3?0,z*?12

⑴ 当目标函数变为maxz?2x1?3x2?x3时，反映到最终单纯形表上如下表所示：

cj →CB20基 b23100x1100x2131x31-1-1x411-2x5010

x1 6 x5 10cj-zj因变量x2 的检验数大于零，故需继续用单纯形法迭代计算得下表：

cj →CB23基 b23100x1100x2010x32/31/30x42/31/3-3x5-1/31/3-1

x1 8/3 x2 10/3cj-zj

81046由上表可得最优解变为x1?,x2?,x3?0,z*?

333??3??10???3???3?⑵ 因有?b???,?b'?B?1?b????? ????0??11??0???3?将其反映到最终单纯形表中如下表所示：

cj →CB20基 b23100x1100x2131x31-1-1x411-2x5010

x1 3 x5 7cj-zj由表可得最优解为x1?3,x2?0,x3?0,z*?6

⑶先将原问题的最优解x1?6,x2?0,x3?0带入新增约束条件?x1?2x3中，因?6?2?0??6?2故原问题最优解发生改变。

给新增约束条件中加入松弛变量并规范化得： x1?2x3?2?x6??2

以x6 为基变量，将上式反映到最终单纯形表中得下表：

cj → CB 基 b200x1x5x6cj-zj610-22x11010-1x2130-31x311-2-10x4110-200x60010

x50100因上表中x1列不是单位向量，故需进行变换，得下表：

cj → CB 基 b200x1x5x6cj-zj610-82x11000-1x213-1-31x311-3-10x411-1-200x60010

x50100因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯性法迭代计算得下表：

cj → CB 基 b200x110/3x522/3x3cj-zj8/32x11000-1x22/38/31/3-8/31x3001 00x42/32/31/3-5/300x61/31/3-1/3-1/3

x50100由上表可得最优解为x1?2.14 给出线性规划问题

10828,x2?0,x3?,z*? 333maxz??1,?2??(2??1)x1?(3??1)x2?(1??1)x311?1?3x1?3x2?3x3?1??2?47?1s.t.?x1?x2?x3?3??233?3?x1,x2,x3?0??当?1

??2?0时用单纯形法求解得最终单纯形表见表2-31。

表 2-31cj →CB23基 b23100x1100x2010x3-12-3x44-1-5x5-11-1

x1 1x2 2cj-zj试分析

⑴ 当?2?0时，?2??1?2范围内变化时z??1,?2?的变化； ⑵ 当?1?0时，?1??2?3范围内变化时z??1,?2?的变化。 解：⑴将?C*反映到最终单纯形表中得下表：

cj →CB基 b2+λ13-λ11+λ100x1100x2010x3-124+10λ1x44-1-5-5λ1x5-11-1+2λ1

3-λ1 x1 12+λ1 x2 2cj-zj在上表中，当?1??1?当?1?1时，表中解为最优，且z??1,?2?=8??1 21时，变量x5的检验数>0，用单纯形法迭代计算得下表： 2cj →CB3-λ10基 b2+λ13-λ11+λ100x1100x2111-2λ1x3126-6λ1x43-1-6+3λ1x5010

x1 3x5 2cj-zj在上表中，当

1??1?2时，表中解为最优，且z??1,?2?=6+3?1 2在第一个表中，当?1??1时，变量x4的检验数>0，用单纯形法迭代计算得下表：

cj →CB基 b2+λ13-λ11+λ100x1100x24-1-4-7λ1x3-9-2-4-4λ1x4010x53-1-6-3λ1

2+λ1x1 90x5 -2cj-zj在上表中，当?2??1??1时，表中解为最优，且z??1,?2?=?4?1???2??5?2?⑵因有?b'?B?b??????????2?? ?11???2??2??1279??1 44将其反映到最终单纯形表中得下表：

cj →CB23基 b23100x1100x2010x3-12-3x44-1-5x5-11-1

x1 1+5λ2x2 2-2λ2cj-zj1在上表中，当???2?1时，表中解为最优，且z??1,?2?=8+4?2

5当?2?1时，表中基变量x2?0，这时可用对偶单纯形法继续迭代计算得下表：

cj →CB20基 b23100x1100x24-1-5x37-2-13x4010x53-1-6

x1 9-3λ2x4 -2+2λ2cj-zj在上表中，当1??2?3时，表中解为最优，且z??1,?2?=18-6?2

1在第一个表中，当?2??时，表中基变量x1?0，这时可用对偶单纯形法继续

5迭代计算得下表：

cj →CB20基 b23100x1-11-1x2010x311-2x4-43-9x5100

x1 -1-5λ2x5 3+3λ2cj-zj1在上表中，当?1??2??时，表中解为最优，且z??1,?2?=9+9?2

52.15 分析下列线性规划问题中，当?变化时???0?最优解的变化，并画出

z???对?的变化关系图。

maxz????(8??)x1?(24?2?)x2（1）minz?x1?x2??x3?2?x4（2）?x1 ?x3?2x4?2? s.t.?2x1?x2 ?3x4?5?x?0(j?1,?,4)?j

?x1?2x2?10? s.t.?2x1?x2?10?x,x?0?12

本文来源：https://www.bwwdw.com/article/qc56.html