大连理工大学运筹学习题与答案
线性规划习 题 一
1．1试述LP 模型的要素、组成部分及特征。判断下述模型是否LP 模型并简述理由。（式中x,y 为变量；θ为参数；a,b,c,d,e 为常数。） （1）max z=2x 1-x 2-3x 3
s.t.123123123121
35824350,0
x x x x x x x x x x x ++=??-+≤??-+≥??≥≤?
(2)min z=
1
n
k
k kx
=∏
s.t.
1
,1,2...,0,1,2...,n
ik k i k k
a x
b i m
x k m =?≥=???≥=?∑ (3)min z=
1
1
n n
i i
j
j
i j a x b y
==+∑∑
s.t.
,1,2,...,,1,2,...i i j j i i ij
x c i m y d j n x y e ?≤=?
≤=??
+≥? (4)max z=
1
n
j j
j c x
=∑
s.t.
1
,1,2,...,0,1,2,...n
ij j i i j j
a x
b d i m
x j n θ=?≤+=???≥=?∑ 1.2试建立下列问题的数学模型： （1）设备配购问题
某农场要购买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。
问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？ （2）物资调运问题
甲乙两煤矿供给A，B，C三个城市的用煤。各矿产量和各市需求如下表所示：
各矿与各市之间的运输价格如下表示：
问应如何调运，才能既满足城市用煤需求，又使运输的总费用最少？
（3）食谱问题
某疗养院营养师要为某类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病人每周所需各种养分的最低数量如下表所示：
另外为了口味的需求，规定一周内所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人每周需14份蔬菜，问选用每种蔬菜各多少份？
（4）下料问题
某钢筋车间要用一批长度为10米的钢筋下料制作长度为三米的钢筋90根和长度为四米的钢筋60根，问怎样下料最省？
用图解法求解下列LP问题：
（1）min z=6x1+4x2
s.t.
12
12
12
21 34 1.5
0,0
x x
x x
x x
+≥
?
?
+≥
?
?≥≥
?
(2) max z=2.5x1+x2
s.t.
12
12
12 3515 5210
0,0 x x
x x
x x
+≤?
?
+≤?
?≥≥?
(3) max z=2x1+2x2
s.t.
12
12
12
1 0.52
0,0
x x
x x
x x
-≥-?
?
-+≤?
?≥≥
?
(4) max z=x1+x2
s.t.
12
12
12
0 33
0,0 x x
x x
x x
-≥?
?
-≤-?
?≥≥?
(5) min z=2x1-10x2
s.t.
12
12
12
55
0,0 x x
x x
x x
-≥?
?
-≥-?
?≥≥?
(6) min z=-10x1-11x2
s.t.
12
12
12
12 3410 528
22
0,0 x x
x x
x x
x x
+≤?
?+≤?
?
-≤?
?≥≥?
1.4 把1.3题的（3）-（6）化成标准形.
1.5 把下列LP问题化成标准形。
(1) min z=2x1+3x2+5x3
s.t.
123
123
123
12
5 67915 197513
0,0
x x x
x x x
x x x
x x
--≥-?
?-+-=
?
?
++≤
?
?≥≤
?
(2) min z=3x1+4x2+2x3+x4
s.t.
123
123
1234
12
37 466
4 1,0
x x x
x x x
x x x x
x x
++≤
?
?++≥
?
?
--++=-?
?≥≥
?
1.6 证明下述LP问题的可行域是一个空集：min z=x1-2x2+2x3+x4
s.t.
1234
1234
1234
4
6 ,,,0
x x x x
x x x x
x x x x
+++=?
?
+--=?
?≥
?
1.7 已知LP问题如下：min w=x1+2x2-3x3+4x4
s.t.
23412341234
47,,,0x x x x x x x x ?
+++=??≥? 判断下述各点：X 1=(8,2,7,-4)T
,X 2=(1,0,2,1)T
,X 3=(2,0,5,0)T
X 4=(0,0,-1,2)T
,X 1=(3,1,0,0)T
,X 1=(2,1/2,1,1/2)T
是不是该LP 问题的可行解、基本解、基本可行解？试从中找出一个较优解。 1.8 设某线性规划问题的可行域如下：
123
12
4123451234522533047285,,,,0
x x x x x x x x x x x x x x x x +-=??+-=??
+---=??≥? 试判断下述各点：
X 1=(5,15,0,20,0)T
,X 2=(9,7,0,0,8)T
,X 3=(15,5,10,0,0)T
是否为该可行域的极点并说明理由。 1.9 设一标准形LP 问题的系数阵为 A=
102316??????
X 0=(1,2,1)T
是一可行解。试按性质4证明中的方法，构造出另一个可行解。 1.10 试证明：若LP 问题有两个不同的最优基本解，则必有无穷多个最优解。 1.11 设R 1,R 2 n E ?
为凸集，则
(1) R 1+R 2={Z|Z=X+Y,X ∈R 1 ,Y ∈R 2} (2) R 1-R 2={Z|Z=X-Y,X ∈R 1 ,Y ∈R 2} (3) λR 1={Z|Z=λX, X ∈R 1,λ∈E 1
} 均为凸集。 1.12 设R i n E ?为凸集,i=1,2,…,则R=i
?i R
也为凸集。
1.13 试举出下述某一类型的LP 问题的实例：产品配比问题，配料问题，物资调运问题，食谱问题，下料问题及其它LP 问题，然后建模并化标准形，再设法找出一个基本可行解。 1.14 用枚举法求解下述LP 问题： （1）min w=12
34x x x ++
s.t.
1231
31
2322410,0,0
x x x x x x x x -+=??
-=??≥≥≥? （2）min w=
123
23x x x -+
s.t.
1231231
23234100,0,0
x x x x x x ?
++=??≥≥≥? (3)1.3题之（2） (4)1.3题之（6）
1.15 某农户年初承包了40亩土地，并备有生产专用资金2500元。该户劳动力情况为：春夏季4000工时，秋冬季3500工时。若有闲余工时则将为别的农户帮工，其收入为： 春夏季0.5.元/工时， 0.40元/工时。该户承包的地块只适宜种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每年每头奶牛需投资400元，每只鸡需投资3元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季0.3工时和秋冬季0.6工时，每年净收入10元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况如下表所示。问该农户应如何拟订经营方案才能使当年净收入最大？试建立该问题的数学模型。
1.16 某罐头食品长用A,B
两个等级的西红柿加工成整番茄、番茄汁、番茄酱三种罐头。A,B 原料质量评分分别为90，50分。为保证产品质量，该厂规定三种罐头的品格（所用原料的质量平均分）如下表所示：
该厂现以0.5公斤6分的价格购进1500吨西红柿，其中可挑出A 等西红柿20%，其余为B 等。据市场预测，三种罐头的最大需求量为：整番茄800万罐，番茄汁50万罐，番茄酱80万罐。原料耗量为：整番茄0.75公斤/罐，番茄汁1.0公斤/罐，番茄酱1.25公斤/罐。三种罐头的价格及生产费用（其中不包括西红柿原料费）如下表所示。问该厂应如何拟订西红柿罐头的生产计划才能获利最大？试建立数学模型。
1.17 某厂生产甲、乙两种产品，每种产品都要在A,B 两道工序加工。其中B 工序可由或B 2完成，但乙产品不能用B 1加工。生产这两种产品都需要C,D,E 三种原材料，有关数据如下表所示。又据市场预测，甲产品每天销售不超过30件。问应如何安排生产才能获利最大？试建立数学模型。
1.18 制造某机床需要A,B,C 三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立数学模型。
1.19 某木材公司经营的木材储存在仓库中，最大贮存量为20万米3。由于木材价格随季节变化，该公司于每季初购进木材，一部分当季售出，一部分贮存以后出售。贮存费为a+bu, 其中a=7元/米3，b=10元/米3 /季，u 为贮存的季度数。由于木材久贮易损，因此当年所有库存木材应于秋末售完。各季度木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立数学模型。
单纯型法习题二
2.1 分别用图解法和单纯形法求解下述LP 问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点相互对应。
（1）max z=10x 1+5x 2
s.t.
12121
23495280,0
x x x x x x +≤??
+≤??≥≥? (2) max z=2x 1+x 2
s.t.
212
1212515622450,0
x x x x x x x ≤?
?+≤??
+≤??≥≥? 2.2 用单纯形法求解1.7题。 2.3 用单纯形法求解下述LP 问题： （1）max z= x 1+2x 2+3x 3+4x 4 s.t.
12341234
1
,,,0x x x x x x x x +++=??
≥? （2）第一章例4 （3）max z= x 1+x 2+x 3+x 4