管理运筹学课后答案.docx
- 文档编号:3401039
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:33
- 大小:238.21KB
管理运筹学课后答案.docx
《管理运筹学课后答案.docx》由会员分享,可在线阅读,更多相关《管理运筹学课后答案.docx(33页珍藏版)》请在冰点文库上搜索。
管理运筹学课后答案
2.2将下列线性规划模型化为标准形式并列出初始单纯形表。
minz=x1'2x24x3
-3x^2x2+2x^^19
(°-4%+3x2+4x3兰14
s.t彳
5为一2x2—4x3=-26
人込0,x2亠0,x3无约束
M为一个任意大的正
解:
(1)令Xi'=_Xi,X3k'_x3”Z=_z,则得到标准型为(其中
数)
maxz'--2x1'2x24x3-4x3"0x40x5-Mx6-Mx7
‘3捲'+2x2+2怡'—2x3"+x4=19
s.t
4X/+3X2+4x3'—4x3"—x5+疋=14
5x1'2x24x3'-4x3"x7二26
X1',X2,X3‘,X3“,X4,X5,X6,X7
_0
c
-2
2
4
-4
0
0
-M
-M
0
Cb
Xb
b
X1'
X2
X3'
X3''
X4
X5
X6
X7
0
X4
19
3
2
2
-2
1
0
0
0
19/3
-M
X6
14
[4]
3
4
-4
0
-1
1
0
14/4
-M
X7
26
5
2
4
-4
0
0
0
1
26/5
-z
-2+9M
2+5M
4+8M
-4-8M
0
-M
0
0
初始单纯形表如表2-1所示:
表2-1
2.3用单纯形法求解下列线性规划问题。
maxz=2片_x2x3
_L3x1x2x3_60
(1)为—X22x3—10
(2)
s.ti
N+x2-2x3兰20
X1,X2,X3_0
解:
(1)最优解为X*=(15,5,0)T,z*=25。
(2)最优解为C=(0,1.5,0,0)K--3。
minz=5捲-2x23x32x4
x12x23x34x4_7s.t《2人+2x2+x3+2x4兰3
X1,X2,X3,兀—0
2.4分别用大M法和两阶段法求解下列线性规划问题。
max^2x13x2—5怡
X1X2X3=7
s.t<2为—5x2+x3生10
X1,X2,X3-0
minz=4为x2
3x1X2=3
(2)4x13x2-x3=6
s.t«
x12x2X4=4
X,X2,X3,X4—0
解:
(1)最优解为x*=(6.429,0.571,0)T,z*=14.571。
*t*
(2)最优解为x=(0.4,1.8,1,0),z=3.4。
2.6已知线性规划问题
minZ=2为3x25x32x43x5
Xx22x3x43x^_4
s.t£2人一x2+3x3十為+x533
XjKO,j=1,2,山,5
其对偶问题最优解为y;=4/5,y;=3/5;Z*=5。
试用对偶理论找出原问题最优解。
解:
先写出它的对偶问题
maxw=4y;3y2”y;+2y2兰2y;_y2兰3|2y;+3y2兰5
s.t彳y;竹2兰23y;+y2兰3
y;,y2-0
**
将y1=4/5,y2=3/5代入约束条件可知,第2、3、4个约束为严格不等式,因此,由互补松弛性得x;=x3=x;=0。
又因为y;,y2,所以原问题的两个约束条件应取等式,因此有
-■**>■*
x;3x5=4x;=;
<**=<*
|2x;x5=3x5=;
故原问题最优解为X*=(;,O,O,O,;)T,Z*=5。
2.12现有线性规划问题
maxz--5x;5x2;3x3
-x;x23x3_20①
s.t X;,X2,X3一0 先用单纯形法求出最优解,然后分析在下列各种条件下,最优解分别有什么变化? (;)约束条件①的右端项系数由20变为30; (2)约束条件②的右端项系数由90变为70; (3)目标函数中x3的系数由;3变为8; (4)X;的系数列向量由(-;,;2)丁变为(0,5)丁; (5)将原约束条件②改变为;0x;5x2;0x3_;00; (6)增加一个约束条件2x;3X25x^50。 X4,X5得 解: 在上述LP问题的第①、②个约束条件中分别加入松弛变量 maxz=-5x;5x2;3x30x40% -X;X23X3X4 ;2x;4x2;0x3 X;,X2,X3,X4,X5—0 列出此问题的初始单纯形表并进行迭代运算,过程如表2-11所示。 由表2-11中的计算结果可知,LP问题的最优解X*=(0,20,0,0,10)丁,z*=5*20=100。 (1)约束条件①的右端项系数由20变为30,则有 B」bJ0I[30L[30l 卜41丄90H-30 列出单纯形表,并利用对偶单纯形法求解,过程如表2-12所示。 表2-11 Cj -5 5 13 0 0 6i Cb Xb b X1 X2 X3 X4 X5 0 X4 20 -1 1 [3] 1 0 20/3 0 X5 90 12 4 10 0 1 9 Cj-Zj -5 5 13 0 0 13 X3 20/3 -1/3 [1/3] 1 1/3 0 20 0 X5 70/3 46/3 2/3 0 -10/3 1 35 Cj-Zj -2/3 2/3 0 -13/3 0 5 X2 20 -1 1 3 1 0 0 X5 10 16 0 -2 -4 1 Cj-Zj 0 0 -2 -5 0 表2-12 Cj -5 5 13 0 0 Cb Xb b X1 X2 X3 X4 X5 5 X2 30 -1 1 3 1 0 0 X5 -30 16 0 [-2] -4 1 Cj-Zj 0 0 -2 -5 0 5 X2 -15 23 1 0 [-5] 3/2 13 X3 15 -8 0 1 2 -1/2 Ci-Zj -16 0 0 -1 -1 0 X4 3 -23/5 -1/5 0 1 -3/10 13 X3 9 6/5 2/5 1 0 1/10 Cj-Zj -103/5 -1/5 0 0 -13/10 由表2-12中计算结果可知,LP问题的最优解变为X*=(0,0,9,3,0)T,z*=13疋9=117。 (2)约束条件②的右端常数由90变为70,则有 1M0丫20"『20" B^b=1II=1 H1人70丿「10丿 列出单纯形表,并利用对偶单纯形法求解,结果如表2-13所示。 表2-13 Cj -5 5 13 0 0 Cb Xb b X1 X2 X3 X4 X5 5 X2 20 -1 1 3 1 0 0 X5 -10 16 0 [-2] -4 1 Cj-Zj 0 0 -2 -5 0 5 X2 5 23 1 0 -5 3/2 13 X3 5 -8 0 1 2 -1/2 Cj-Zj -16 0 0 -1 -1 由表2-13结果知,LP问题的最优解变为X*=(0,5,5,0,0)T,z*=55135=90。 (3)目标函数中X3的系数由13变为8,由于X3是非基变量,其检验数变为 二=8-53-0(—2)=—7: : : 0 所以LP问题的最优解不变。 (4)Xi的系数列向量由(-1,12)t变为(0,5)T,则Xi在最终单纯形表中的系数列向量变为b"10阳异1 _-4155 从而Xi在最终单纯形表中的检验数变为 巧=C|_CbB」R=—5_(5,0)[]=—5<0 H5 所以LP问题的最优解保持不变。 (5)将原约束条件②改变为10X1+5X2+10X3w100则X1在最终单纯形表中系数列向量变 为R=B千1=(—1,14)丁,检验数5—CbB」R=—5—(5,0)(—1,14)丁=0 X2在最终单纯形表中系数列向量变为P2二B」Fb=(1,1T,检验数6二c-CbBR=5-(5,0)(1,1)T=0。 又因1020=20的各分量均大于0,故LP问题的最优解不变。 IH1||100||20 (6)增加一个约束条件2X1+3X2+5X3<50则在此约束条件中加入松弛变量X6,并将此 约束加入到最终单纯形表中,继续迭代,过程如表2-14所示。 由表2-14中计算结果可知,LP问题的最优解变为X*=(0,25/2,5/2,0,15「0) z*=525/2135/2=95。 表2-14 Ci -5 5 13 0 0 0 Cb Xb b X1 X2 X3 X4 X5 X6 5 X2 20 -1 1 3 1 0 0 0 X5 10 16 0 -2 -4 1 0 0 x6 50 2 3 5 0 0 1 5 X2 20 -1 1 3 1 0 0 0 X5 10 16 0 -2 -4 1 0 0 X6 -10 5 0 [-4] -3 0 1 Cj-Zj 0 0 -2 -5 0 0 5 X2 25/2 11/4 1 0 -5/4 0 3/4 0 X5 15 27/2 0 0 -5/2 1 -1/2 13 X3 5/2 -5/4 0 1 3/4 0 -1/4 Cj-Zj -5/2 0 0 -7/2 0 -1/2 3.1分别用分支定界法和割平面法求解下列整数规划模型。 (〔)minz--4xi-3x2 (2)maxz=xiX2 4x1-^x2_1012捲x2_6 s.t^2x1+3x2<8s.t4x x1,x2_0,且为整数儿公2_0,且为整数 解: (1)求解得到最优解x;=2,x;=1,z*二-11。 (计算步骤略) (2)仅写出利用割平面法求解的过程。 在原IP问题约束条件中加入松弛变量刈淤4,化为标准型,可得 maxz=人x20x30x4 2x1x2x3=6 s.t24%+5x2++x4=20 X1,X2,X3,x4丄0且为整数 不考虑整数条件,用单纯形法求解原问题的松弛问题,计算结果如表3-1所示。 表3-1 cj 1 1 0 0 6 Cb Xb b X1 X2 X3 X4 0 X3 6 2 1 1 0 6 0 X4 20 4 [5] 0 1 4 Cj-zj 1 1 0 0 0 X3 2 [6/5] 0 1 -1/5 5/3 1 X2 4 4/5 1 0 1/5 5 Cj-zj 1/5 0 0 -1/5 1 X1 5/3 1 0 5/6 -1/6 1 X2 8/3 0 1 -2/3 1/3 Ci-Zi 0 0 -1/6 -1/30 因此,松弛问题的最优解为Xi=5/3,X2=8/3,X3=0,X4=0;z=13/3。 由于X2不为整数,因此在最终单纯形表中根据X2所在的行作割平面 2/3—1/3(X3X4)乞0 即 _X3-X4乂一2 将它作为约束条件,引入松弛变量后加到最终单纯形表中,并采用对偶单纯形法继续迭代,计算过程如表3-2所示。 表3-2 Cj 1 1 0 0 0 Cb Xb b X1 X2 X3 X4 X5 1 X1 5/3 1 0 5/6 -1/6 0 1 X2 8/3 0 1 -2/3 1/3 0 0 X5 -2 0 0 -1 [-1] 1 C-Zj 0 0 -1/6 -1/30 0 1 X1 2 1 0 1 0 -1/6 1 X2 2 0 1 -1 0 1/3 0 X4 2 0 0 1 1 -1 Cj-Zj 0 0 0 0 -1/6 由于Xi,X2的值均为整数,所以得到原问题的最优解为X=(2,2)t,z=4 3.4某厂新购4台不同类型机器,可以把它们安装在4个不同的地点。 由于对特定的机器而言,某些地方可能安装起来特别方便且合适,所以不同的机器安装在不同的地点费用是 不同的。 估计的费用见表3-3,试制定使得总安装费用最小的安装方案。 表3-3(费用单位: 元) 地点 机器 1 2 3 4 机器总数 1 10 9 8 7 1 2 3 4 5 6 1 3 2 1 1 2 1 4 4 3 5 6 1 需要量 1 1 1 1 机器i安装在地点j所需的费用。 建立该问题的数学模型如下: 目标函数: 44 minzfj/jXj 约束条件: 4 ⑴每一部机器只分配在一个地点,即zyXj=1i=1,2,3,4 4 ⑵每一个地点只能有一台机器,即7yXj=1j=1,2,3,4 (3)为=0或1 工作指派问题可以看成是一类特殊的运输问题,每个供应点的供应量为1,每个需求点 的需求量也为1。 因此,本题可以采用表上作业法进行计算,也可以利用匈牙利法进行计算。 计算得到的最佳安装方案为: 机器1安装在地点4、机器2安装在地点1、机器3安装在地 点3、机器4安装在地点2,最小总安装费为14元。 3.9设有三个化肥厂供应四个地区的农用化肥。 假定等量的化肥在这些地区使用的效果 相同。 各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表 3-17所示。 试确定使总运费最少的化肥调拨方案。 表3-仃 需求 产地 I II III IV 产量(万吨) A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 50 最低需求(万吨) 30 70 0 10 最高需求(万吨) 50 70 30 不限 解: 这是一个产销不平衡的运输问题,总产量为160万t,四个地区的最低需求为110 万t,最高需求为无限。 根据现有产量,第IV个地区每年最多能分配到60万t,这样最高 需求就为210万t,大于产量。 为了求得平衡,在产销平衡表中增加一个假想的化肥厂D, 其年产量为50万t。 由于各地区的需求量包含两部分,如地区I,其中30万t是最低需求, 故不能由假想化肥厂D供给,令相应的单位运价为M(任意大的正数);而另一部分20万 t满足或不满足均可以,因此可以由假想化肥厂D供给,按前述,可令相应的单位运价为0。 对凡是需求分两种情况的地区,实际上可按照两个地区看待。 这样可以写出这个问题的产销 平衡表(表3-18)和单位运价表(表3-19)。 并根据表上作业法,可以求得这个问题的最优解,如表3-20所示。 表3-18 50 60 C 50 D 50 销量 30 20 70 30 10 50 表3-19 销地 产地 I I' II III IV IV' A 16 16 13 22 17 17 B 14 14 13 19 15 15 C 19 19 20 23 M M D M 0 M 0 M 0 表3-20 销地产地r I I' II III IV IV' 产量 A 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 销量 30 20 70 30 10 50 4.2利用单纯形法求解下列目标规划模型。 (〔)minz=R(d「+dj+P2d3— r+ 人+2x2—dr=50 2%+x2+d厂-d2+=40 s.t彳. 2xr+2x2+d3—-d3十=80 K,X2,di=di+兰0,i=1,2,3 解: (1)本题的三个约束条件都是目标约束,有三个负偏差变量,因此选择负偏差变量为初始基变量。 并计算出各非基变量的检验数,得到初始的单纯形表如表4-1所示。 非基变量xr,x2的检验数分别为闵=-Pr-2P2和92=-2Pr-2P2,它们的最高优先级的系数都 小于零,但9中Pi的系数等于-2,其绝对值等于2,大于叼中Pi的系数的绝对值1,因此X2应当进基。 用最小比值法确定d1■应当出基。 换基后,通过计算求得新的基本可行解,如 表4-2所示。 表4-1 Cj 0 0 P1 0 0 P1 P2 0 e Cb Xb b X1 X2 dr d2" d2+ d3- d3+ P1 dr 50 1 [2] 1 -1 0 0 0 0 25 0 P2 d2_ d3- 40 80 2 2 1 2 0 0 0 0 1 0 -1 0 0 1 0 -1 40 40 q Pi -1 -2 0 1 0 1 0 0 P2 -2 -2 0 0 0 0 0 1 表4-2 Cj 0 0 P1 0 0 P1 P2 0 e Cb Xb b X1 X2 d「 d/ d2_ d2+ d3- d3+ 0 X2 25 1/2 1 1/2 -1/2 0 0 0 0 50 0 d2一 15 [3/2] 0 -1/2 1/2 1 -1 0 0 10 P2 d3- 30 1 0 -1 1 0 0 1 -1 30 P1 0 0 1 0 0 1 0 0 q P2 -1 0 1 -1 0 0 0 1 尽管xi与①•具有相同的负检验数,但根据前面讨论的原则,由于xi是决策变量,选择 X1进基,用最小比值法确定d2■出基,换基后,计算所得新的基本可行解如表4-3所示。 表4-3 Ci 0 0 P1 0 0 P1 P2 0 e Cb Xb b X1 X2 d- d/ d2_ d2+ d3- d3+ 0 X2 20 0 1 2/3 -2/3 -1/3 1/3 0 0 — 0 X1 10 1 0 -1/3 [1/3] 2/3 -2/3 0 0 30 P2 d3- 20 0 0 -2/3 2/3 -2/3 2/3 1 -1 30 P1 0 0 1 0 0 1 0 0 q P2 0 0 2/3 -2/3 2/3 -2/3 0 1 首项系数小于零的检验数只有dl•的为_2/3P2,因此d;应当进基,由于存在两个最小 比值,取下标最小的变量出基,因此xi出基,换基后,再计算新的基本可行解,如表4-4 所示。 表4-4 Cj 0 0 P1 0 0 P1 P2 0 e Cb Xb b X1 X2 d/ d1+ d2 d2+ d3- d3+ 0 X2 .+ 40 2 1 0 0 1 -1 0 0 0 d1 30 3 0 -1 1 2 -2 0 0 P2 d3- 0 -2 0 0 0 -2 2 1 -1 q P1 0 0 1 0 0 1 0 0 P2 2 0 0 0 2 -2 0 1 此时所有变量的检验数的首项系数都已经大于等于零,因此获得了满意解如下: Xi=0,X2 =40,d,=30,其他偏差变量都等于零。 4.3某厂生产A、B、C三种产品,装配工作在同一生产线上完成,三种产品时的工时消耗分别为6、&10小时,生产线每月正常工作时间为200小时;三种产品销售后,每台 可获利分别为500、650和800元;每月销售量预计为12、10和6台。 该厂经营目标如下: (1)利润指标为每月16000元,争取超额完成; (2)充分利用现有生产能力;(3)可以适当加班,但加班时间不得超过24小时;(4)产量以预计销售量为准。 试建立目标规划模型。 解: 该问题的数学模型如下: minZ工卩^-P2d2一Psds P4(d^d/d^d/d^d6) 500x^650x 6洛+8冷+10冷+d2—-d2+=200 d/+d^-d/=24 s.t.为d4_—d4=12 X2+d5_"5十=10x^d^-d/=6为必压_0©一0_0(i=1,2,l|),6) 5.2计算从A到B、C和D的最短路。 已知各段路线的长度如图5-1所示。 解: 求从A到B、C和D的最短路等价于求从B、C和D到A的最短路。 设阶段变量k=1,2,3,4,依次表示4个阶段选路得过程,第1阶段从B、C或D出发到 B3、C3或D3,第2阶段从B3、C3或D3出发到B2、C2或。 2,第3阶段从B2、C2或D2出发到C1或D1,第4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理 运筹学 课后 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)