运筹学1至6章习题参考答案
第1章 线性规划
1.1 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1-23所示.
310和130.试建立该问题的数学模型,使每月利润最大.
【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量,则数学模型为
1231231
23123123max 1014121.5 1.2425003 1.6 1.21400
150250260310120130,,0
Z x x x x x x x x x x x x x x x =++++≤??++≤??≤≤??
≤≤??≤≤?≥?? 1.2 建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架.两种窗架所需材料规格
及数量如表1-24所示:
【解设x j (j =1,2,…,10)为第j 种方案使用原材料的根数,则 (1)用料最少数学模型为
10
1
12342567368947910
min 2800212002600223900
0,1,2,,10
j
j j Z x x x x x x x x x x x x x x x x x x j ==?+++≥?
+++≥??
+++≥??+++≥??≥=?∑ (2)余料最少数学模型为
2345681012342567368947910
min 0.50.50.52800
212002*********
0,1,2,,10
j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++?+++≥?
+++≥??
+++≥??+++≥??≥=?
1.3某企业需要制定1~6月份产品A 的生产与销售计划。已知产品A 每月底交货,市场需求没有限制,由于仓库容量有限,仓库最多库存产品A1000件,1月初仓库库存200件。1~6月份产品A 的单件成本与售价如表1-25所示。
(2)当1月初库存量为零并且要求6月底需要库存200件时,模型如何变化。 【解】设x j 、y j (j =1,2,…,6)分别为1~6月份的生产量和销售量,则数学模型为
(1)
1122334
45566
1
112
11223
1122334
112233445
11223344556
max300350330340320350360
420360410300340
800
800
800
800
800
Z x y x y x y x y x y x y
x
x y x
x y x y x
x y x y x y x
x y x y x y x y x
x y x y x y x y x y x
=-+-+-+-+ -+-+
≤
-+≤
-+-+≤
-+-+-+≤
-+-+-+-+≤
-+-+-+-+-+≤
11
1122
112233
11223344
1122334455
112233445566
800
200
200
200
200
200
200
,0;1,2,,6
j j
x y
x y x y
x y x y x y
x y x y x y x y
x y x y x y x y x y
x y x y x y x y x y x y
x y j
?
?
?
?
?
?
?
?
?
?
-+≤
?
?-+-+≤
?
?-+-+-+≤
?
-+-+-+-+≤
?
?-+-+-+-+-+≤
?
-+-+-+-+-+-+≤
?
?≥=
?
(2)目标函数不变,前6个约束右端常数800改为1000,第7~11个约束右端常数200改为0,第12个约束“≤200”改为“=-200”。
1.4 某投资人现有下列四种投资机会, 三年内每年年初都有3万元(不计利息)可供投资:方案一:在三年内投资人应在每年年初投资,一年结算一次,年收益率是20%,下一年可继续将本息投入获利;
方案二:在三年内投资人应在第一年年初投资,两年结算一次,收益率是50%,下一年可继续将本息投入获利,这种投资最多不超过2万元;
方案三:在三年内投资人应在第二年年初投资,两年结算一次,收益率是60%,这种投资最多不超过1.5万元;
方案四:在三年内投资人应在第三年年初投资,一年结算一次,年收益率是30%,这种投资最多不超过1万元.
投资人应采用怎样的投资决策使三年的总收益最大,建立数学模型.
数学模型为
1121311223341112112123122131341223
34max 0.20.20.20.50.60.3300001.230000
1.5 1.2300002000015000100000,1,,3;1,4
ij Z x x x x x x x x x x x x x x x x x x x i j =+++++?+≤?
-++≤??--++≤??
≤??≤??≤?≥==??
最优解X=(30000,0,66000,0,109200,0);Z =84720
1.5 炼油厂计划生产三种成品油,不同的成品油由半成品油混合而成,例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合,辛烷值不低于94,每桶利润5元,见表1-26。
表1-27
解 设x ij 为第i (i =1,2,3,4)种成品油配第j (j =1,2,…,7)种半成品油的数量(桶)。 总利润:
11121321222334353637444546475() 4.2()3() 1.5()
Z x x x x x x x x x x x x x x =+++++++++++++高级汽油和一般汽油的辛烷值约束
111213212223
111213212223
801151058011510594,8494x x x x x x x x x x x x ++++≥≤≤++++
航空煤油蒸气压约束
34353637
34353637
1.50.60.051x x x x x x x x ++≤++++
一般煤油比例约束
44454647:::10:4:3:1x x x x =
即
4546444546471043,,431
x x x x x x === 半成品油供应量约束
1121122213233444354536463747200010001500120010001000800
x x x x x x x x x x x x x x +≤+≤+≤+≤+≤+≤+≤ 整理后得到
111213212223343536374445464711121321222321222335363744
45
4546464max 555 4.2 4.2 4.23333 1.5 1.5 1.5 1.5142111014211104312100.50.40.9504100
3403Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =+++++++++++++-++≥-++≤-++≥--≤-=-=-711211222
1323344435453646374702000100015001200100010008000;1,2,3,4;1,2,,7
ij x x x x x x x x x x x x x x x i j ??
???
?????
=??
+≤??+≤??+≤?
+≤??+≤?
+≤??+≤?≥==??
1.6 图解下列线性规划并指出解的形式:
(1) 12
121212max 5228
35,0
Z x x x x x x x x =++≤??≤??
≤??≥?
【解】最优解X =(3,2);最优值Z=19
(2) 12
12121212max 4453224,0
Z x x x x x x x x x x =++≤??+≥??
+≤??≥?
【解】有多重解。最优解X
(1)
=(0,5/4);X
(2)
=(3,1/2)最优值
Z=5
(3)121212
1212
12min 32211410
2731
,0
Z x x x x x x x x x x x x =-++≤??-+≤??
-≤??-≤??≥?
【解】最优解X =(4,1);最优值Z=-10,有唯一最优解
(4) 12
1212212min 4628830,0
Z x x x x x x x x x =++≥??+≤??
≤??≥≥?
【解】最优解X =(2,3);最优值Z=26,有唯一最优解
(5) ??????
?≥≤≥≥-+=0
,6322max 2121212
1x x x x x x x x Z
【解】无界解。
(6)
12 12
12
12
min25
26
2
,0
Z x x x x
x x
x x
=-
+≥
?
?
+≤
?
?≥
?
【解】无可行解。
1.7 将下列线性规划化为标准形式 (1) 123123123123123min 631557432103650,0,Z x x x x x x x x x x x x x x x =+-++≥??-+≤??
++≥-??≥≥?无限制
【解】(1)令654'
'3'33,,,x x x x x x -=为松驰变量 ,则标准形式为 '''1233
'''12334'''
12335'''
12336'''1233456max 63315574432103665
,,,,,,0Z x x x x x x x x x x x x x x x x x x x x x x x x x x =--+-?++--=?-+-+=??---++=??≥? (2) 123
123112123min 935|674|205880,0,0
Z x x x x x x x x x x x x =-++-≤??
≥??
+=-??≥≥≥?
【解】(2)将绝对值化为两个不等式,则标准形式为
1231234123516
12
123456max 9356742067420
588
,,,,,0
Z x x x x x x x x x x x x x x x x x x x x x '=-+-+-+=??--++=??-=??--=??≥? (3)121121
2max 2315
10,0
Z x x x x x x x =+≤≤??
-+=-??≥≥?
【解】方法1:
12
1314
121234max 231
5
1,,,0
Z x x x x x x x x x x x x =+-=??+=??
-=??≥? 方法2:令1
11111,1,514x x x x x '''=-+≤-=有= 1
21
1
212
max 2(1)34(1)1,0Z x x x x x x x '=++'≤??
'-++=-??≥?
则标准型为
121
31
2123
max 22340,,0Z x x x x x x x x x '=++'+=??
'-+=??'≥?
(4) 12123123123123123max min(34,)
2304215965,0Z x x x x x x x x x x x x x x x x x =+++++≤??
-+≥??
++≥-??≥?
无约束、
【解】令1212311134,,y x x y x x x x x x '''≤+≤++=-,线性规划模型变为
1
12112311231
12311231
123max 3()42304()2159()65,,0Z y
y x x x y x x x x
x x x x x x x x x x x x x x x x ='''≤-+??'''≤-++??'''-++≤??
'''--+≥??'''-++≥-?'''≥??、 标准型为
1
124112351123611237112381
12345678max 33400
230442159965,,,,,,,,0Z y
y x x x x y x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ='''-+-+=??'''-+--+=??'''-+++=??
'''--+-=??'''-+--+=?'''≥??
1.8 设线性规划
12123124
max 522240
42600,1,,4j
Z x x x x x x x x x j =+?++=?
-+=??≥=? 取基1221204021B B ????
=????-????、=,分别指出B B 12和对应的基变量和非基变量,求出基本解,并说明B B 12、是不是可行基.
【解】B 1:x 1、x 3为基变量,x 2、x 4为非基变量,基本解为X=(15,0,10,0)T ,B 1是可行基。B 2:x 2、x 4是基变量,x 1、x 3为非基变量,基本解X =(0,20,0,100)T ,B 2是可行基。
1.9分别用图解法和单纯形法求解下列线性规划,指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点.
(1)12
121212
max 322
2312,0Z x x x x x x x x =+-+≤??
+≤??≥?
【解】图解法
最优解4
),2,4(==Z X
(2)
12 12
12
12
12
min35
26
410
4
0,0
Z x x x x
x x
x x
x x
=--
+≤
?
?+≤
?
?
+≤
?
?≥≥
?
【解】图解法
该题是退化基本可行解,5个基本可行解对应4个极点。
1.10用单纯形法求解下列线性规划
(1)123
123123max 342342230,1,2,3j
Z x x x x x x x x x x j =++?++≤?
++≤??≥=?
(2) 1234
123412341234max 23553730310
264200,1,,4j Z x x x x x x x x x x x x x x x x x j =+-+++-≤??
-++≤??
--+≤??≥=?
【解】单纯形表:
因为λ7=3>0并且a i 7<0(i =1,2,3),故原问题具有无界解,即无最优解。
(3)1123812313123123max 32234421238410,,0
Z x x x x x x x x x x x x x x =+--++≤??-≤??
++≤??≥?
原问题具有多重解。 基本最优解(1)
(2)1273427237(3,,0,,0)(,0,,,0);841111114
T X
X Z ===及,最优解的通解可表
示为)2()1()1(X a aX X -+=即
3411227272
(
,,,,0),(01)1111811111111
T X a a a a a =---≤≤
(4)123
123123max 3254625863240,1,2,3j
Z x x x x x x x x x x j =++?++≤?++≤??≥=?
1.11 分别用大M 法和两阶段法求解下列线性规划:
(1) 123
123123max 1055310510150,1,2,3j
Z x x x x x x x x x x j =-+?++=?
-+-≤??≥=?
【解】大M 法。数学模型为
123512351234max 1055310510150,1,2,,5j
Z x x x Mx x x x x x x x x x j =-+-?+++=?
-+-+=??≥=
最优解X =(2,0,0);Z=20 两阶段法。
第一阶段:数学模型为
5
12351234min 5310
510150,1,2,,5j
w x x x x x x x x x x j =?+++=?
-+-+=??≥=
最优解X=(2,0,0);Z=20
(2) 123
123123123min 567531556102050,1,2,3j Z x x x x x x x x x x x x x j =--+-≥??
-+≤??
++=??≥=?
【解】大M 法。数学模型为
123131231112321233min 56753155610205Z x x x
MA MA x x x S A x x x S x x x A =--+++--+=??-++=??
+++=??所有变量非负
第一阶段:数学模型为
13
123111232
1233min 5315561020
5w A A x x x S A x x x S x x x A =++--+=??-++=??
+++=??
所有变量非负
最优解:(0,
,),444
T X Z ==-
(3)12121212123max 10155395615250
Z x x x x x x x x x x x =++≤??-+≤??
+≥??≥?、、
【解】大M 法。数学模型为
1261231241256max 1015539
5615250,1,2,,6j Z x x Mx x x x x x x x x x x x j =+-++=??-++=??
+-+=??≥=
因为两阶段法
第一阶段:数学模型为
6
123124
1256min 5395615
250,1,2,,6j Z x x x x x x x x x x x x j =++=??-++=??
+-+=??≥=