2
8'
1' 2' 3' 4'
1 0 0 0 0
0 1 0 2
2线性规划习题答案
1、试述线性规划数学模型的组成部分及其特性
答:线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。 线性规划数学模型特征:
(1)
(2) 24小时全天候营业,在各时间段中所需要的服务员数量分别为:
2 : 00~6: 00
3 人 6
:00~10: 00 9 人
10: 00~14: 00 12 人 14 :00~18:
00 5 人
18: 00~22: 00
18
人
22
:00~ 2 : 00 4 人
设服务员在各时间段的开始时点上上班并连续工作八小时, 员,才能满足各个时间段对人员的需要。试构造此问题的数学模型。
解:用决策变量 X i , X 2, X 3, X 4, X 5, X 6分别表示 2: 00~6: 00, 6 : 00~10: 00,10: 00~14:
X 1,X 2,X 3,X 4,X 5,X 6 0
3、现要截取2.9米、2.1米和1.5
如何下料,才能使所消耗的原材料最省。试构造此问题的数学模型。
用0表示每种切割方案的剩余材料。其切割方案如下所示:
用一组决策变量表示某一方案,这组决策变量均为非负的连续变量;
存在一定数量(m )的约束条件,这些约束条件可以用关于决策变量的一组线性 等式或者不等式来加以表示;
有一个可以用决策变量加以表示的目标函数,而该函数是一个线性函数。
2、一家餐厅 问该餐厅至少配备多少服务 00 , 14: 00~18: 00, 18: 00~22:
00, 22 : 00~ 2 : 00时间段的服务员人数。
其数学模型可以表述为:
min
X 1 X 2 X 3 X 4 X 5 X 6 X 1 X 6 X 1 X 2
X
2
X
3
12 X 3 X 4
X
4
X
5
18
X 5 X 6
米的元钢各100根,已知原材料的长度是
7.4米,问应
方法一
解:圆钢的截取有不同的方案,
目标函数为求所剩余的材料最少,即
X i ,X 2,X 3,X 4,X 5,X 6, X 7,X 8
方法二
解:由题意,因为所有套裁方案有
21种,全部写出需考虑因素太多,故需先做简化。
又由于目标是使所用原材料最少,所以,仅需考虑最省的五个方案即可。 设X i 是第i 种套裁方案所用的原材料根数,
Min z= 0 X 1 +0.1 X 2 +0.2 X 3
x 1 +2X 2
+ x 4 100 2X 3 +2X 4 + X 5
100
3x 1 +x 2 + 2X 3
+3X
5
100
X j 00=1,2, ,5)
五种套裁方案实施后,可得的 米钢筋的根数。
五种套裁方案实施后,可得的 米钢筋的根数。
五种套裁方案实施后,可得的
米钢筋的根数。
X 1=30, ,X 2=10, X 3=0, X
4
=50, X
5
=0
只需90根原材料,目标函数值最小为 90即可。
4、某糖果厂用原料 A
A 、
B
C 三种原料的含量要求、
各种原料的单位成本、各种原料每月的限制用量、三种牌号 糖果的单位加工费及售价如表 1所示。问
该厂每月生产这三种牌号糖果各多少千克, 才能使
该厂获利最大试建立这个问题的线性规划模型。
min Z 0.9x 1
0.1X
2
0.3X 3 0X 4 0.8X 5 1.4X 6 0.2X 7 1.1X 8
2X 2 X 3 X 4
100
2x 3
X
5
2X
7
3X
8
100
X 2 3X 4 3X
5 4X
6 2X
7 100
建立数学模型如下:
(料头最省)
+0.3 X 4 +0.8 X 5
B C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中
X i x
i X i
表1
QX i ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9 0
方法一
解:设X 1, X 2, X 3分别为甲糖果中 A,B,C 的成分;X 4, X 5, X 6分别为乙糖果中A,B,C 的成 分;X 7, X 8, X 9分别为丙糖果中 A,B,C 的成分。 由题意,有
maxz (3.40 0.50)(X 1 X 2 X 3)
(2.85 0.40)(X 4 X 5 X 6) I X 1, X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9
max z 0.9x-i 1.4x 2 1.9x 3 0.45x 4
0.05 x 7 0.45X 8 0.95X 9
0.4X , 0.6X 2 0.6 X 3 0 0.2X
,
0.2 x 2 0.8X 3 0 0.85X 4 0.15X 5 0.15X 6 0
0.6x 4 0.6x 5 0.4X 6 0 0.5 x 7 0.5X 8 0.5X 9 0
X 1 X 4 X 7 2000
X 2 X 5 x 8 2500
X 3 X 6 X 9 1200
对上式进行整理得到所求问题的线性规划模型:
r 0.95X 5 1.45x 6
(2.25 0.30)(X 7 X 8 X 9) 1.50(X 2 X 5
2.00(x 1 x 4 x 7)
X 8) 1.00(x
X
6
X 9)
X 1
0.6 X 1 X 2 X 3
X 3
0.2
X 1 X 2 X 3
X 4
0.15
X 4 X 5 X 6
X 6
0.6
X 4 X 5 X 6
X 9
0.5
X
7 X 8
X
9
X
1
X
4 X
7 2000 X
2
X 5
X
8
2500
X 3
X 6 X 9 1200
方法二
在约束条件中共有 9个变量,为方便计算,分别用 x 1, x 2 ... x 9表示,
%2=甲 B , X 3=甲 C , %4=乙 A , X 5 =乙 B , X 6=乙 C , X 7 =丙 A , X g =丙 B , X 9 =丙 C
由此约束条件可以表示为:
2
-3X 1
X 2 X 3 0 -X 1-X 2 4X 3 0 17
- = X 4 X 5 X6 3
2
-X 4-X 5 -X 6 0
3
-X 7-X 8 X 9 0 X 1+X 4 X 7 2000
X 2+X 5 X 8 2500 X 3+X 6 X 9 1200
X l ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9
我们的目的是使利润最大,即产品售价减加工费再减去原材料的价格为最大。 目标函数为
MaxZ 0.9x , 1.4x 2 1.9x 3 0.45x 4 0.95疋 1.45x 6 0.05x 7 0.45x 8 0.95x 9
5、某厂在今后4个月内需租用仓库存放物资,已知各个月所需的仓库面积如表
2所示。租 金与租借合同的长短有关,租用的时间越长,享受的优惠越大,具体数字见表 3。租借仓库
的合同每月初都可办理, 每份合同具体规定租用面积数和期限。
因此该厂可根据需要在任何
一个月初办理租借合同,且每次办理时,可签一份,也可同时签若干份租用面积和租借期限
解:以甲A 表示甲产品中的 A 成分,
甲B 表示甲产品中的 B 成分,甲C 表示甲产品中的 C
成分,依此类推。据表
2-16 , 3 1
甲A 3甲,甲C 1甲 5 5
有:
討乙C
1
—丙 ......... ①
2
其中:甲A +甲
B
甲C 甲
,乙A +乙
B
丙A +丙 B 丙C
把②逐个代入①并整理得:
3 甲 A +甲B 甲C
3 甲A -甲B
乙A +乙B
-乙 A - 乙B 2 乙C
原材料的限制,有以下不等式成立:
-丙A -丙B
甲A +乙A 丙A
2000 ,甲B +乙B 2500,甲c +乙C 丙C
1200
即令
X
1 =
甲A ,
不同的合同,总的目标是使所付的租借费用最小。 试根据上述要求,建立一个线性规划的数
学模型。 表2
表
解:设X ij (i = 1,2,3,4;j=1,2 ... 4-i+1 )为第i 个月初签订的租借期限为
j 个月的合同租
借面积(单位:100m
2
); r i 表示第i 个月所需的面积(j 表示每
600
0(X 13 X 23) 7300X 14
广
X 11
X 12 X 13 X 14
15
X 12 X 13 X 14 X 21
X
22
X
23
10
X 13 X 14
X
22 X
23 X
31
X
32
20
X 14 X 23
X 32 +X 41 12
X ij
0, i,
j 1 ,2,3,4, i j 5
4 i 1
ex
匕八ij
j 1
k 4 i 1
X 八ij
i 1 j k i 1
X ij 0(i
1,2,3,4; j 1,2...4 i 1)
6、某农场有
人日,春夏季
6000人日,如劳
动力本身过剩可外出打工,
季12元/人日。该农场种植三种作物:大豆、玉米和小麦,并饲养奶牛和鸡。种作物不需 要专门投资,而饲养动物时每头奶牛投资
8000元,每只鸡投资2元。养奶牛时每头需拨出 1.5公顷土地种饲草,并占用人工秋冬季为
100人日,春夏季为50人日,年净收入3000元
/每头奶牛。养鸡不占土地,需人工为每只鸡秋冬季人日,春夏季人日,年净收入为每只
8
元。农场现有鸡舍允许最多养 5000只鸡,牛栏允许最多养 50头奶牛,三种作物每年需要的 人工及收入情况如表 4所示。试决定该农场的经营方案,使年净收入最大。
100 m 2
仓库面积租借期为
j 个月的租借费);则线性规划模型为:
min z 2800(x 11 X 21 X 31 X t1)
4500(X 12 X 22
MinZ r k (k 123,4)
100公顷土地及25万元资金可用于发展生产。农场劳动力情况为秋冬季
4500
春夏季收入为20元/人日,秋冬
表4
解:设X i , X 2, X 3分别代表大豆、玉米、麦子的种植数(公顷) ;X 4, X 5分别代表奶牛和鸡 的饲养数;X 6, X 7分别代表秋冬季和春夏季多余的劳动力(人.日数)则有 MaxZ 1100x 1 厂 X 1 X 2
1.5x 4 8000x 4 2X 5
1500x 2 900x 3 3000x 4 8x 5 12x 6
20x 7 20x 1 50x 1 X 4 100(土地限制)
250000资金限制) 10x 3 100x 4 0.3X 5 40X 3 50X 4 35冷 75X 2 50(牛栏限制)
5000(鸡栏限制) 0.1x
5
x 6
x
7
4500(劳动力限
制)
4500(劳动力限制)
J X 1,X 2,X 3,X 4,X 5,X 6,X 7 0
用图解法求解下列线性规划问题
(1) max Z 2x 1 x 2 (2) max z 3x 1 2x 2
(4X 1 3X 2
12 广 x 1 2x 2
4
2x 1 X 2
8 3x 1 2x 2
14
彳
4x 1 x 2 8
x 1 x 2 3
X 1, X 2 0
< X 1,X 2
(3
) max z 2x 1 3x 2
(4) max z x 1 x 2
"X 1 X 2
2 广
X 1 X 2 0
Y 3x 1 x 2
4
Y 3x 1 x 2
3
X 5 0
7、 X i ,X 2
X i , X 2 0
*
T
中一个是X (4,1)T
找不到可行域,此题为无 可行解
解: (1)
X
i + X 2 + X 3 + X 4 =5
X i +
X 2
+
X 5
= 2
2x 1 +
X 2 + X 3 +
X 6 = 6
X i , ,X 6 0
2x i X 2 X 3 X 4
8、考虑线性规划:
max z