运筹学练习参考答案.doc

线性规划问题
1、某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表：

I
II
III
设备能力（台时）
A
B
C
1
10
2
1
4
2
1
5
6
100
600
300
单位利润（元）
10
6
4

（1） 求获利最大的产品生产计划；
（2） 产品III每件的利润增加到多大时才值得安排生产；
（3） 如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。
解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：
用单纯形法求上述线性规划问题。化为标准形式：

10
6
4
0
0
0

b

0

100
1
1
1
1
0
0
100
0

600
[10]
4
5
0
1
0
60
0

300
2
2
6
0
0
1
150

0
10
6
4
0
0
0

0

40
0
[0.6]
0.5
1
-0.1
0
200/3
10

60
1
0.4
0.5
0
0.1
0
150
0

180
0
1.2
5
0
-0.2
1
150

-600
0
2
-1
0
-1
0

6

200/3
0
1
5/6
5/3
-1/6
0

10

100/3
1
0
1/6
-2/3
1/6
0

0

100
0
0
4
-2
0
1

-2200/3
0
0
-8/3
-10/3
-2/3
0

所以最优解为x* =(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z* =2200/3
（2）设产品III每件的利润为c3

产品III每件的利润增加到20/3时才值得安排生产。

（3）设x7为新产品的产量。

10
6
4
0
0
0
8

b

6

200/3
0
1
5/6
5/3
-1/6
0
[1]
200/3
10

100/3
1
0
1/6
-2/3
1/6
0
0
-
0

100
0
0
4
-2
0
1
1
100

-2200/3
0
0
-8/3
-10/3
-2/3
0
2

8

200/3
0
1
5/6
5/3
-1/6
0
1

10

100/3
1
0
1/6
-2/3
1/6
0
0

0

100/3
0
-1
19/6
-11/3
1/6
1
0

-2600/3
0
-2
-13/3
-20/3
-1/3
0
0

所以最优解为x* =(100/3，0，0，0，0，200/3)T，即产品I的产量：100/3，新产品的产量：200/3；最优解目标函数值z* =2600/3

2、已知下列线性规划问题：

求：（1）用单纯形法求解，并指出问题属于哪一类解；
（2）写出该问题的对偶问题，并求出对偶问题的最优解；

解：（1）将原问题划为标准形得：

6
-3
3
0
0
0

b

0

60
3
1
1
1
0
0
20
0

20
[2]
-2
4
0
1
0
10
0

60
3
-3
3
0
0
1
20

0
6
-3
3
0
0
0

0

30
0
4
-5
1
-3/2
0
15/2
6

10
1
-1
2
0
1/2
0
-
0

30
0
[6]
-9
0
-3/2
1
5

-60
0
3
-9
0
-3
0

0

10
0
0
1
1
-1/2
-2/3

6

15
1
0
1/2
0
1/4
1/6

-3

5
0
1
-3/2
0
-1/4
1/6

-75
0
0
-9/2
0
-9/4
-1/2

最优解为x* =(15，5，0，10，0，0)T 最优解目标函数值z* =75
非基变量的检验数<0, 为唯一最优解.
（2）该问题的对偶问题为：

对偶问题的最优解：y* =(0，9/4，1/2)

3、已知线性规划问题：

求：（1）用图解法求解；
（2）写出其对偶问题；
（3）根据互补松弛定理，写出对偶问题的最优解。
解：（1）图解法
由上图可知：在B(2,4)处，目标函数达到最大值。
即最优解为x*=(2,4)T 最优解目标函数值z*=10 为唯一最优解
（2）该问题的对偶问题为：

（3）原问题的最优解x*=(2,4)T代入约束条件，可知约束条件取等式，因为x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，
即
对偶问题的最优解及最优目标函数值为：
运输问题
1、某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到销地之间的单位运价见下表：
销地
产地
B1
B2
B3
B4
产量
A1
4
12
4
11
16
A2
2
10
3
9
10
A3
8
5
11
6
22
销量
8
14
12
14

（1）用表上作业法求该运输问题的最优调运方案。（15分）
（2）该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一个最优调运方案来。（5分）
解：（1）先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。
①求初始基可行解（Vogel法）
销地
产地
B1
B2
B3
B4
产量
差额
A1

4

12
12
4
4
11
16
0 0 0 7 0
A2
8
2

10

3
2
9
10
1 1 1 6 0
A3

8
14
5

11
8
6
22
1 2
销量
8
14
12
14

差额
2
2
2
5
1
1
1
1
3
3
2
2
2

初始解为：x13=12, x14=4, x21=8, x24=2, x32=14, x34=8，其余变量为0；
相应的目标函数值 z= 4×12+11×4+2×8+9×2+5×14+6×8= 244
②最优性检验（位势法）
根据基变量的检验数为0，即sij= cij –ui – vj =0
s13= c13 –u1– v3 = 4 –u1– v3 =0 s14= c14 –u1– v4 = 11 –u1– v4 =0
s21= c21 –u2– v1 = 2 –u2– v1 =0 s24= c24 –u2– v4 = 9 –u2– v4 =0
s32= c32 –u3– v2 = 5 –u3– v2 =0 s34= c34 –u3– v4 = 6 –u3– v4 =0
u1 =0 易得：u2= –2，u3= –5，v1=4，v2=10，v3=4，v4=11
计算非基变量的检验数：
s11= c11 –u1– v1 = 4 –0– 4=0 s12= c12 –u1– v2 = 12 –0– 10=2
s22= c22 –u2– v2 = 10 –(–2)– 10=2 s23= c23 –u2– v3 = 3 –(–2)– 4=1
s31= c31 –u3– v1 = 8 –(–5)– 4=9 s33= c33 –u3– v3 = 11 –(–5)– 4=12
所有非基变量xij的检验数sij≥0，即得最优解。
最优解为：x*13=12, x*14=4, x*21=8, x*24=2, x*32=14, x*34=8，其余变量为0；
最优目标函数值 z* = 244
（2）因为非基变量x11的检验数s11=0，所以该问题有多个最优调运方案。
从非基变量x11出发找一条闭回路（见下表）：
销地
产地
B1
B2
B3
B4
产量
A1
(+)
4

12
12
4
(-)4
11
16
A2
8
2(-)

10

3
2
9 (+)
10
A3

8
14
5

11
8
6
22
销量
8
14
12
14

闭回路调整后得到另一最优解：
销地
产地
B1
B2
B3
B4
产量
A1
4
4

12
12
4

11
16
A2
4
2

10

3
6
9
10
A3

8
14
5

11
8
6
22
销量
8
14
12
14

即最优解为：x*11=4, x*13=12, x*21=4, x*24=6, x*32=14, x*34=8，其余变量为0
2、一个运输网络有4个发点和4 个收点，发点的发量，收点的收量与单位运价如下表所示∶

B1
B2
B3
B4
供应量
A1
20
80
10
20
100
A2
10
25
20
50
200
A3
20
30
20
40
100
A4
40
20
10
30
100
需求量
150
50
100
100

求使总运费最小的运输方案。

解：产量〉销量，假想一个销地B5，销量为100
先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。
①求初始基可行解（Vogel法）
销地
产地
B1
B2
B3
B4
B5
供应量
差额
A1

20

80
0
10
100
20

0
100
10 10 10
A2
150
10
50
25

20

50

0
200
10 10 10 10 5 0 0
A3

20
0
30

20

40
100
0
100
20 0 0 0 10 0 0
A4

40
0
20
100
10

30

0
100
10 10 10 10 10 0
需求量
150
50
100
100
100

差额
10
10
10
10
5
5
5
5
5
5
5
0
0
0
10
10
10
10
0

初始解x13=0, x14=100, x21=150, x22=50, x32=0, x35=100, x42=0, x43=100,其余变量为0
②最优性检验（位势法）：根据基变量的检验数为0，即sij= cij –ui – vj =0
s13= c13 –u1– v3 = 10 –u1– v3 =0 s14= c14 –u1– v4 = 20 –u1– v4 =0
s21= c21 –u2– v1 = 10 –u2– v1 =0 s22= c22 –u2– v2 = 25 –u2– v2 =0
s32= c32 –u3– v2 = 30 –u3– v2 =0 s35= c35 –u3– v5 = 0 –u3– v5 =0
s42= c42 –u4– v2 = 20 –u4– v2 =0 s43= c43 –u4– v3 = 10 –u4– v3 =0
u1 =0 易得：u2= 5，u3= 10，u4= 0，v1=5，v2=20，v3=10，v4=20，v5= -10
计算非基变量的检验数：
s11= c11 –u1– v1 = 20 –0– 5=15 s12= c12 –u1– v2 = 80 –0– 20=60
s15= c15 –u1– v5 = 0 –0– (-10)=10 s23= c23 –u2– v3 = 20 –5–10=5
s24= c24 –u2– v4 = 50 –5– 20 =25 s25= c25 –u2– v5 = 0 –5– (-10) =5
s31= c31 –u3– v1 = 20 –10– 5 =5 s33= c33 –u3– v3 = 20 –10– 10 =0
s34= c34 –u3– v4 = 40 –10– 20 =10 s41= c41 –u4– v1 = 40 –0– 5 =35
s44= c44 –u4– v4 = 30 – 0– 20=10 s45= c45 –u4– v5 = 0 –0– (-10)=10
所有非基变量xij的检验数sij≥0，即得最优解。
最优解为：x*13=0, x*14=100, x*21=150, x*22=50, x*32=0, x*35=100, x*42=0, x*43=100,其余变量为0；最优目标函数值 z* = 5750

目标规划
某工厂计划生产A、B两种产品，需要消耗甲、乙、丙三种资源、单位产品利润及资源限量如表所示：
产品
资源
A
B
资源限制
甲
2
1
140
乙
1
0
60
丙
0
1
100
产品利润（元/件）
30
12

该厂的经营目标是：
首先要求总利润必须超过2500元；
然后考虑到产品受市场影响，为避免积压，A、B的产量不超过60件和100 件；
由于甲资源供应比较紧张，不要超过现有量140。
试建立目标规划模型。
解：设x1，x2 为产品A、B产量，以产品 A、B 的单件利润比 2.5：1 为权系数，目标规划模型如下：

整数规划
1、在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用见下表，假定每一项已经批准的工程要在整个3年内完成，目标是要选出使总收入达到最大的那些工程，试将这个问题表示成0-1整数规划模型。

工程
费用（千元）
收入（千元）
第一年
第二年
第三年
1
5
1
8
20
2
4
7
10
40
3
3
9
2
20
4
7
4
1
15
5
8
6
10
30
最大可用资金（千元）
25
25
25
-

解：设
该问题的0-1整数规划模型为：

2、分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。（10分） (表中单位：小时)
任务
人数

A B C D E
甲
乙
丙
丁
戊
25 28 31 41 38
40 38 26 26 33
35 27 28 40 32
24 42 37 23 45
30 29 26 20 32
已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。

解：若不可能完成任务，则效率矩阵相应的元素为M，变换效率矩阵：

得到初始分配方案：

因为独立0元素个数m=4，不等于矩阵的阶数n=5，转入下步。

此时独立0元素个数有5个，得到最优解，相应的解矩阵为：

即分配方案为：甲→A，乙→E，丙→B，丁→C，戊→D，
总时间为：25+33+27+37+20=142小时

3、有五个车队将分赴五个地区，各车队去各地区的收入如下表：
地区
纯收入
车队
B1 B2 B3 B4 B5
A1
A2
A3
A4
A5
9 4 6 8 5
8 5 9 10 6
9 7 3 5 8
4 8 6 9 5
10 5 3 6 8
每个车队去一个地区，每个地区有一个车队去。求使总收入最大的指派方案。
解：非标准型指派问题（极大化问题）先转换，变换效率矩阵：

得到初始分配方案：

因为独立0元素个数m=4，不等于矩阵的阶数n=5，转入下步。

此时独立0元素个数有5个，得到最优解，相应的解矩阵为：

即分配方案为：A1→B4，A2→B3，A3→B5，A4→B2，A5→B1
总收入为：8+9+8+8+10=43

12