运筹学课后习题二要点Word下载.docx
《运筹学课后习题二要点Word下载.docx》由会员分享,可在线阅读,更多相关《运筹学课后习题二要点Word下载.docx(18页珍藏版)》请在冰点文库上搜索。
0.8
0.9
0.3
0.2
【解】
(1)设Xj为每天第j种食物的用量,数学模型为
minZ=05jl+Mx2+08z5+09巧+0+02^e
13xj+25xa+14也+4Q码+8码+llx6>
80
24咼十+30z3+25z4+12心十15x6>
1跖+7xa+21x3+34x4+10巧>
町、孟旷毛、兀r>
(2)设,y为第i种单位营养的价格,则数学模型为
maxw=SOjj4-150y3+180y5
13^+2472+18^<
25^+9^+?
^<
14”+30兀+21乃<
=40^+25^+34y3<
8^+12^2+10乃<
llyL+15j5+^0.2
必必小工°
2.2写出下列线性规划的对偶问题
minxv-9”+6儿-纨+切+10兀
划1+6旳-些+凡+旳之弋
-2y^2y3=3
7i+»
2—丹=6
_6”-旳+2乃二-7
对偶问题为:
2.3考虑线性规划
nunZ二12五+20x2
鼻1+4冷工4
Xj+5xa>
2
2西+3xa>
7
血,xa>
0
(1)说明原问题与对偶问题都有最优解;
⑵通过解对偶问题由最优表中观察出原问题的最优解;
⑶利用公式CbB「1求原问题的最优解;
(4)利用互补松弛条件求原问题的最优解.
(1)原问题的对偶问题为
”无约東:
儿刘,>
0,几兰6^>
maxvp=4y14-2y2+7”
乃+乃+2乃兰12
空伽+5旳+3必乞20
[yj^Qj=12,3
容易看出原问题和对偶问题都有可行解,女口X=(2,1)、Y=(1,0,1),由定理2.4知都有
最优解。
(2)
对偶问题最优单纯形表为
C(j)
4
2
R.H.S.
Basis
C(i)
y1
y2
y4
y5
y3
-1/5
1
4/5
28/5
7/5
-3/5
2/5
C(j)-Z(j)
-11/5
-16/5
w=42.4
对偶问题的最优解Y=(4/5,0,28/5),由定理2.6,原问题的最优解为X=(16/5,1/5),Z=42.4
(4)由y1、y不等于零知原问题第
三个约束是紧的,解等式
珂+4亏=4
2x}+3x2=7
得到原问题的最优解为X=(16/5,1/5)。
2.4证明下列线性规划问题无最优解
minZ=xL-2x2-2x3
2码+冷一2心=3
<
Jr】-2勺+3x3>
201內>
0,^无约東
证明:
首先看到该问题存在可行解,例如x=(2,1,1),而上述问题的对偶问题为
max神=物+6
2^+^2<
-2”+3y2=-2
K之0J无约東
由约束条件①②知y1<
0,由约束条件③当y2>
0知y1>
1,对偶问题无可行解,因此原问题也无最优解(无界解)。
2.5已知线性规划
+5x2+码<
5
5旺+6心+西兰63&
+10光+忌三7內20,花2Q西无约東
【解】其对偶问题是:
minm=5jj4-6y3+7ys
71+5^+3.73>
羽+6兀+10j3>
20
7i+ya+?
3=5
XH0由原问题的最优解知,原问题约束③的松弛变量不等于零(X」),X1、X3不等于零,
则对偶问题的约束①、约束③为等式,又由于•:
知y3=0;
解方程
儿+”2=15川+乃二5
得到对偶问题的最优解Y=(5/2,5/2,0);
w=55/2=27.5
2.6用对偶单纯形法求解下列线性规划
(1)minZ=3x1+4xa+5巧\L+2x2+3
«
2xl*2乃+x310如%”為NO
【解】将模型化为
minZ=3xt+4xj+5x3
-x1-2^_3码+為二一2
£
_2画_2冷_码+冷=-10丐W1234上
对偶单纯形表:
Cj
3
Cb
Xb
Xi
X2
X3
X4
X5
b
-1
-2
-3
-8
[-2]
-10
0X4
[-1]
—5/2
—1/2
—3
3X
1/2
7/2
3/2
5X
5/2
—1
3Xi
—2
b列全为非负,
最优解为
x=(2,3,
0);
Z=18
(2)minZ=+4叼
+^2>
4«
2iV]十殆童2
Xj>
0,-0
minZ-3码+4x3
_两_问+禺二一4
X1
-4
Cj—Zj
-6
6
出基行系数全部非负,最小比值失效,原问题无可行解。
⑶min7二2西+4x?
2aj+3乜<
24
可+2x3>
10
Tx+3xj>
15
九乃王°
mixkZ二2尊+4巫
I2xl+3x2+x3=24
2奄+些=_1Q
_X]—3花+阳=-15
x.>
0J=172,3t<
[-3]
-15
-1/3
—2/3
1/3
—1/3
2/3
4/3
最优解X=(0,5);
Z=20
(4)minZ-2^+3z2+5^+6z4
xL+2x:
+3陆+x4>
*_2珂+x2-x3+3x4<
x;
>
OJ=1/-X
minZ=2xl+3x2+5码+6兀
~2x、—3兀3-兀彳+Xj=^2
I-2xj+%-x3+3盂*+坷-_乡亏>
0,八1.…,6
X6
-1/2
-5/2
[-5/2]
13/5
3/5
-7/5
-2/5
8/5
1/5
-13/5
[1]
11/5
Cj-Zj
-11/2
-3/2
23/5
7•某工厂利用原材料甲、乙、丙生产产品A、B、C,有关资料见表2-23.
表2-23
每月可供原材料
(Kg)
产
品
材料消耗
原材料
甲
200
乙
500
丙
600
每件产品利润
(1)怎样安排生产,使利润最大.
(2)若增加1kg原材料甲,总利润增加多少.
(3)设原材料乙的市场价格为1.2元/Kg,若要转卖原材料乙,工厂应至少叫价多少,为什么?
(4)单位产品利润分别在什么范围内变化时,原生产计划不变.
(5)原材料分别单独在什么范围内波动时,仍只生产A和C两种产品.
(6)由于市场的变化,产品B、C的单件利润变为3元和2元,这时应如何调整生产计划.
(7)工厂计划生产新产品D,每件产品D消耗原材料甲、乙、丙分别为2kg,2kg及1kg,
每件产品D应获利多少时才有利于投产.
(1)设X1、X2、X3分别为产品A、B、C的月生产量,数学模型为
maxZ=4x}+x2+?
也
2码+1心+码<
200
+2xa+3xs<
2两+心+两<
0,^>
0,^>
最优单纯形表:
R.H.S.
Ratio
20
160
400
-8/5
-9/5
Z=560
最优解X=(20,0,160),Z=560。
工厂应生产产品A20件,产品C160种,总利润为560丿元。
92n
(2)由最优表可知,影子价格为_■j,故增加利润1.8元。
因为y2=o.4,所以叫价应不少于依据最优表计算得
-3<
2,-1<
A£
:
3<
屮[1,6],CaCf-oo.y],^€[2,12]
—罟期乞4叭「机叱他<
100P-400<
Ah]
^et^/OO],^€[100/00],^€[200,+®
).
(6)
只生产产品B200件,总利润为600元。
变化后的检验数为01,4=-2,5=0。
故X2进基%出基,得到最最优解X=(0,200,0),即
[1/5]
100
800/3
M
560
-5
⑺设产品D的产量为X7,单件产品利润为C7,只有当->■'
-时才有利于投
产。
则当单位产品D的利润超过4.4元时才有利于投产。
&
对下列线性规划作参数分析
maxZ=(3+2/z)^+(5-
[咔4
3xj+2花<18
(1)h从°
【解】卩=0时最优解X=(4,3,0);
最优表:
-2.5
27
将参数引入到上表:
3+23
5—3
—3—23
-2.5+0.53
当一3-20及-2.5+0.5卩<0时最优基不变,有一1.5<卩<5。
当卩<—1.5时X3进基
X1出基;
卩>5时X4进基X2出基,用单纯形法计算。
参数变化与目标值变化的关系如下表所示。
From
To
Leaving
Entering
Range
(Vector)
OBJ
Value
OBJValue
Slope
Variable
52
-1.5
19.5
-M
帀《4+”
z2<
6
3xj+2xa<
18-2//
每,xa>
卩=0时最优解X=(4,3,0),Z=27;
maxZ=3x1-h5x2
"
4"
T
古二&
f+护二
+
J8_
b=月T©
+护#)=矿知+亍扩乂
才
_1
00_
_1-
=
0.50
_0_
厂2
-11
一耳
■■
'
1_
_u_
替换最优表的右端常数,得到下表。
4+i
卜3]
—5i
1卩<
—4时冋题不可行,一4W(1<
0时最优基不变。
(1=—4时Z=15。
2卩>
0时X5出基X3进基得到下表:
4-2/3i
51/3
OWiw6时为最优解。
1=6时Z=15。
③1>
6时X1出基X4进基得到下表:
-12+2i
9-i
4+i
1=9时最优解X=(0,0,13,6,0),Z=0;
i>
9时无可行解。
综合分析如下表所示。
(Vector)(V
ector)
Infinity
Infeasible
-Infinity