运筹学课后习题二.doc

习题二
2.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.2写出下列线性规划的对偶问题
（1） 【解】
（2） 【解】
（3） 【解】
（4） 【解】
对偶问题为：
2.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)。

2.4证明下列线性规划问题无最优解

证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为

由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。

2.5已知线性规划

的最优解，求对偶问题的最优解．
【解】其对偶问题是：

由原问题的最优解知，原问题约束③的松弛变量不等于零()，x1、x3不等于零，则对偶问题的约束①、约束③为等式，又由于知y3＝0；解方程

得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5
2.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
1
0
0
 －1/3
5
Cj－Zj
2/3
0
0
0
4/3

最优解X=(0，5)；Z＝20

【解】将模型化为

Cj
2
3
5
6
0
0
b
XB
CB
X1
X2
X3
X4
X5 
 X6
X5
0
-1
[-2]
-3
-4
1
0
-2
X6
0
-2
1
-1
3
0
1
-3
Cj－Zj
2
3
5
6
0
0

X2
3
1/2
1
3/2
2
-1/2
0
1
X6
0
-5/2
0
[-5/2]
1
1/2
1
-4
Cj－Zj
1/2
0
1/2
0
3/2
0

X2
3
[-1]
1
0
13/5
-1/5
3/5
-7/5
X3
5
1
0
1
-2/5
-1/5
-2/5
8/5
Cj－Zj
0
0
0
1/5
8/5
1/5

X1
2
1
-1
0
-13/5
1/5
-3/5
7/5
X3
5
0
[1]
1
11/5
-2/5
1/5
1/5
Cj－Zj
0
0
0
1/5
8/5
1/5

X1
2
1
0
1
-2/5
-1/5
-2/5
8/5
X2
3
0
1
1
11/5
-2/5
1/5
1/5
Cj－Zj
0
0
0
1/5
8/5
1/5

原问题有多重解：X(1)＝(7/5，0，1/5，)；最优解X(2)＝(8/5，1/5，0)；Z＝19/5
如果第一张表X6出基，则有
Cj
2
3
5
6
0
0
b
XB
CB
X1
X2
X3
X4
X5 
 X6
X5
0
-1
-2
-3
-4
1
0
-2
X6
0
[-2]
1
-1
3
0
1
-3
Cj－Zj
2
3
5
6
0
0

X5
0
0
[-5/2]
-5/2
-11/2
1
-1/2
-1/2
X1
2
1
-1/2
1/2
-3/2
0
-1/2
3/2
Cj－Zj
0
2
4
9
0
1

X2
3
0
1
1
11/5
-2/5
1/5
1/5
X1
2
1
0
1
-7/5
-1/5
-2/5
8/5
Cj－Zj
0
0
2
23/5
4/5
3/5

7．某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表2-23．
表2-23
产品
材料消耗
原材料
A
B
C
每月可供原材料（Kg）
甲
乙
丙
2
1
1
200
1
2
3
500
2
2
1
600
每件产品利润
4
1
3

（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的月生产量，数学模型为

最优单纯形表：
C(j)
4
1
3
0
0
0
R.H.S.
Ratio
XB
CB
X1
X2
X3
X4
X5
X6
X1
4
1
1/5
0
3/5
-1/5
0
20

X3
3
0
3/5
1
-1/5
2/5
0
160

X6
0
0
0
0
-1
0
1
400

C(j)-Z(j)
0
-8/5
0
-9/5
-2/5
0
Z=560

最优解X=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。
（2）由最优表可知，影子价格为,故增加利润1.8元。
（3）因为y2=0.4，所以叫价应不少于1.6元。
（4）依据最优表计算得

（5）依据最优表计算得

（6）变化后的检验数为λ2=1,λ4=-2,λ5=0。故x2进基x1出基,得到最最优解X=(0,200,0)，即只生产产品B 200件,总利润为600元。
C(j)
4
3
2
0
0
0
R.H.S.
Ratio
XB
CB
X1
X2
X3
X4
X5
X6
X1
4
1
[1/5]
0
3/5
-1/5
0
20
100
X3
2
0
3/5
1
-1/5
2/5
0
160
800/3
X6
0
0
0
0
-1
0
1
400
M
C(j)-Z(j)
0
1
0
-2
0
0
560

X2
2
5
1
0
3
-1
0
100
M
X3
3
-3
0
1
-2
[1]
0
100
100
X6
0
0
0
0
-1
0
1
400
M
C(j)-Z(j)
-5
0
0
-5
1
0

X2
2
2
1
1
1
0
0
200

X4
0
-3
0
1
-2
1
0
100

X6
0
0
0
0
-1
0
1
400

C(j)-Z(j)
-2
0
-1
-3
0
0

(7)设产品D的产量为x7, 单件产品利润为c7，只有当时才有利于投产。

则当单位产品D的利润超过4.4元时才有利于投产。

8．对下列线性规划作参数分析
（1）
【解】μ＝0时最优解X=(4,3,0)；最优表：
C(j)
3
5
0
0
0
R. H. S.
Basis
C(i)
X1
X2
X3
X4
X5
X1
3
1
0
1
0
0
4
X2
5
0
1
0
0.5
0
3
X5
0
0
0
-3
-1
1
0
C(j)-Z(j)
0
0
-3
-2.5
0
27
将参数引入到上表：
C(j)
3＋2μ
5－μ
0
0
0
R.H.S.
Basis
C(i)
X1
X2
X3
X4
X5
X1
3＋2μ
1
0
1
0
0
4
X2
5－μ
0
1
0
0.5
0
3
X5
0
0
0
-3
-1
1
0
C(j)-Z(j)
0
0
－3－2μ
-2.5＋0.5μ
0
27
当－3－2μ≤0及-2.5＋0.5μ≤0时最优基不变，有－1.5≤μ≤5。当μ<－1.5时X3进基X1出基；μ>5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下表所示。

From
To
From
To

Leaving
Entering
Range
(Vector)
(Vector)
OBJ Value
OBJ Value
Slope
Variable
Variable
1
0
5
27
52
5
X2
X4
2
5
M
52
M
8

3
0
-1.5
27
19.5
5
X1
X3
4
-1.5
-M
19.5
M
-3

目标值变化如下图所示。

（2）
【解】μ＝0时最优解X=(4,3,0)，Z＝27；最优表：
C(j)
3
5
0
0
0
R. H. S.
Basis
C(i)
X1
X2
X3
X4
X5
X1
3
1
0
1
0
0
4
X2
5
0
1
0
0.5
0
3
X5
0
0
0
-3
-1
1
0
C(j)-Z(j)
0
0
-3
-2.5
0
27

替换最优表的右端常数，得到下表。
C(j)
3
5
0
0
0
R.H.S.
Basis
C(i)
X1
X2
X3
X4
X5
X1
3
1
0
1
0
0
4＋μ
X2
5
0
1
0
0.5
0
3
X5
0
0
0
[-3]
-1
1
－5μ
C(j)-Z(j)
0
0
-3
-2.5
0

①μ<－4时问题不可行，－4≤μ<0时最优基不变。μ＝－4时Z＝15。
②μ>0时X5出基X3进基得到下表：
C(j)
3
5
0
0
0
R.H.S.
Basis
C(i)
X1
X2
X3
X4
X5
X1
3
1
0
0
-1/3
1/3
4-2/3μ
X2
5
0
1
0
1/2
0
3
X3
0
0
0
1
1/3
-1/3
5μ/3
C(j)-Z(j)
0
0
0
-3/2
-1

0≤μ≤6时为最优解。μ＝6时Z＝15。
③μ>6时X1出基X4进基得到下表：
C(j)
3
5
0
0
0
R.H.S.
Basis
C(i)
X1
X2
X3
X4
X5
X4
0
-3
0
0
1
-1
-12+2μ
X2
5
3/2
1
0
0
1/2
9-μ
X3
0
1
0
1
0
0
4+μ
C(j)-Z(j)

μ＝9时最优解X=(0，0，13，6，0)，Z=0；μ>9时无可行解。
综合分析如下表所示。

From
To
From
To

Leaving
Entering
Range
(Vector)
(Vector)
OBJ Value
OBJ Value
Slope
Variable
Variable
1
0
0
27
27
3
X5
X3
2
0
6
27
15
-2
X1
X2
3
6
9
15
0
-5
X2

4
9
Infinity
Infeasible

5
0
-4
27
15
3
X1

6
-4
-Infinity
Infeasible

目标值变化如下图所示。