熊伟编《运筹学》习题二详细解答.doc
文本预览下载声明
习题二
1.某人根据医嘱,每天需补充A、B、C三种营养,A不少于80单位,B不少于150单位,C不少于180单位.此人准备每天从六种食物中摄取这三种营养成分.已知六种食物每百克的营养成分含量及食物价格如表2-22所示.(1)试建立此人在满足健康需要的基础上花费最少的数学模型;(2)假定有一个厂商计划生产一中药丸,售给此人服用,药丸中包含有A,B,C三种营养成分.试为厂商制定一个药丸的合理价格,既使此人愿意购买,又使厂商能获得最大利益,建立数学模型.
表2-22
含量 食物
营养成分
一
二
三
四
五
六
需要量 A 13 25 14 40 8 11 ≥80 B 24 9 30 25 12 15 ≥150 C 18 7 21 34 10 0 ≥180 食物单价(元/100g) 0.5 0.4 0.8 0.9 0.3 0.2 【解】(1)设xj为每天第j种食物的用量,数学模型为
(2)设yi为第i种单位营养的价格,则数学模型为
2.写出下列线性规划的对偶问题
(1) 【解】
(2) 【解】
(3) 【解】
(4) 【解】
对偶问题为:
3.考虑线性规划
(1)说明原问题与对偶问题都有最优解;
(2)通过解对偶问题由最优表中观察出原问题的最优解;
(3)利用公式CBB-1求原问题的最优解;
(4)利用互补松弛条件求原问题的最优解.
【解】(1)原问题的对偶问题为
容易看出原问题和对偶问题都有可行解,如X=(2,1)、Y=(1,0,1),由定理2.4知都有最优解。
(2)对偶问题最优单纯形表为
C(j) 4 2 7 0 0 R. H. S. Basis C(i) y1 y2 y3 y4 y5 y3 7 0 -1/5 1 4/5 -1/5 28/5 y1 4 1 7/5 0 -3/5 2/5 4/5 C(j)-Z(j) 0 -11/5 0 -16/5 -1/5 w=42.4 对偶问题的最优解Y=(4/5,0,28/5),由定理2.6,原问题的最优解为X=(16/5,1/5),Z=42.4
(3)CB=(7,4),,
(4)由y1、y3不等于零知原问题第一、三个约束是紧的,解等式
得到原问题的最优解为X=(16/5,1/5)。
4.证明下列线性规划问题无最优解
证明:首先看到该问题存在可行解,例如x=(2,1,1),而上述问题的对偶问题为
由约束条件①②知y1≤0,由约束条件③当y2≥0知y1≥1,对偶问题无可行解,因此原问题也无最优解(无界解)。
5.已知线性规划
的最优解,求对偶问题的最优解.
【解】其对偶问题是:
由原问题的最优解知,原问题约束①等于零,x1、x2不等于零,则对偶问题的约束①、约束③为等式,y1=0;解方程
得到对偶问题的最优解Y=(5/2,5/2,0);w=55/2=27.5
6.用对偶单纯形法求解下列线性规划
【解】将模型化为
对偶单纯形表:
cj 3 4 5 0 0 CB XB X1 X2 X3 X4 X5 b 0
0 X4
X5 -1
[-2] -2
-2 -3
-1 1
0 0
1 -8
-10 C(j)-Z(j) 3 4 5 0 0 0 0
3 X4
X1 0
1 [-1]
1 -5/2
1/2 1
0 -1/2
-1/2 -3
5 C(j)-Z(j) 0 1 7/2 0 3/2 0 5
3 X2
X1 0
1 1
0 5/2
-2 -1
1 1/2
-1 3
2 C(j)-Z(j) 0 0 1 1 1 b列全为非负,最优解为x=(2,3,0);Z=18
【解】将模型化为
3 4 0 0 b XB CB X1 X2 X3 X4 X3 0 [-1] -1 1 0 -4 X4 0 2 1 0 1 2 Cj-Zj 3 4 0 0 X1 3 1 1 -1 0 4 X4 0 0 [-1] 2 1 -6 Cj-Zj 0 1 3 0 X1 3 1 0 1 1 -2 X2 4 0 1 -2 -1 6 Cj-Zj 0 0 5 1 出基行系数全部非负,最小比值失效,原问题无可行解。
【解】将模型化为
cj 2 4 0 0 0 b XB CB X1 X2 X3 X4 X5 X3 0 2 3 1 0 0 24 X4 0 -1 -2 0 1 0 -10 X5 0 -1 [-3] 0 0 1 -15 Cj-Zj 2 4 0 0 0 X3 0 1 0 1 0 1 9 X4 0 -1/3 0 0 1 -2/3 0 X2 4 1/3
显示全部