运筹学试卷及答案(1).doc

一、填空题：（每空格2分，共16分）
1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。
2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。
3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错
4、如果某一整数规划：
MaxZ=X1+X2 X1+9/14X2≤51/14 -2X1+X2≤1/3 X1,X2≥0且均为整数
所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X1进行分枝，应该分为 X1≤1 和 X1≥2 。
5、在用逆向解法求动态规划时，fk(sk)的含义是： 从第k个阶段到第n个阶段的最优解 。
6. 假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关系为 D 包含 B
7. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X3,X4,X5为松驰变量。
XB
b
X1
X2
X3
X4
X5
X4
3
0
0
-2
1
3
X1
4/3
1
0
-1/3
0
2/3
X2
1
0
1
0
0
-1
Cj-Zj
0
0
-5
0
-23
问：（1）写出B-1=
(2)对偶问题的最优解： Y＝（5，0，23，0，0）T
8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；
9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________；
10. 若整数规划的松驰问题的最优解不符合整数要求，假设Xi=bi不符合整数要求，INT（bi）是不超过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1 和 Xi≤INT（bi） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。
11. 知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X4,X5,X6为松驰变量。
XB
b
X1
X2
X3
X4
X5
X6
X1
2
1
1
0
2
0
1
X3
2/3
0
0
1
1
0
4
X5
1
0
-2
0
1
1
6
Cj-Zj
0
0
0
-4
0
-9

问：(1)对偶问题的最优解： Y＝(4,0,9,0,0,0)T
（2）写出B-1=

二、计算题（60分）
1、 已知线性规划（20分）
MaxZ=3X1+4X2
X1+X2≤5
2X1+4X2≤12
3X1+2X2≤8
X1,X2≥0
其最优解为：
基变量

X1
X2
X3
X4
X5
X3
3/2
0
0
1
-1/8
-1/4
X2
5/2
0
1
0
3/8
-1/4
X1
1
1
0
0
-1/4
1/2
σj

0
0
0
-3/4
-1/2
1） 写出该线性规划的对偶问题。
2） 若C2从4变成5，最优解是否会发生改变，为什么？
3） 若b2的量从12上升到15，最优解是否会发生变化，为什么？
4） 如果增加一种产品X6，其P6=(2,3,1)T，C6=4该产品是否应该投产？为什么？
解：
1)对偶问题为
Minw=5y1+12y2+8y3
y1+2y2+3y3≥3
y1+4y2+2y3≥4
y1,y2≥0
2)当C2从4变成5时，
σ4=-9/8
σ5=-1/4
由于非基变量的检验数仍然都是小于0的，所以最优解不变。
3）当若b2的量从12上升到15
X＝ 9/8
29/8
1/4
由于基变量的值仍然都是大于0的，所以最优解的基变量不会发生变化。
4）如果增加一种新的产品，则
P6’=(11/8,7/8，－1/4)T
σ6=3/8>0
所以对最优解有影响,该种产品应该生产

2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共15分）。
销地
产地
B1
B2
B3
产量
A1
5
9
2
15
A2
3
1
7
11
A3
6
2
8
20
销量
18
12
16

解：初始解为

B1
B2
B3
产量/t
A1

15
15
A2

11

11
A3
18
1
1
20
销量/t
18
12
16

计算检验数

B1
B2
B3
产量/t
A1
5
13
0
15
A2
－2
0
0
11
A3
0
0
0
20
销量/t
18
12
16

由于存在非基变量的检验数小于0，所以不是最优解，需调整
调整为：

B1
B2
B3
产量/t
A1

15
15
A2
11

11
A3
7
12
1
20
销量/t
18
12
16

重新计算检验数

B1
B2
B3
产量/t
A1
5
13
0
15
A2
0
2
2
11
A3
0
0
0
20
销量/t
18
12
16

所有的检验数都大于等于0，所以得到最优解
3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示：
（15分）
项目
投标者
A
B
C
D
甲
15
18
21
24
乙
19
23
22
18
丙
26
17
16
19
丁
19
21
23
17
答最优解为：
X= 0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
总费用为50
4. 考虑如下线性规划问题（24分）
Max z=-5x1+5x2+13x3
s.t. -x1+x2+3x3≤20
12x1+4x2+10x3≤90
x1，x2， x3≥0
回答以下问题：
1）求最优解
2）求对偶问题的最优解
3）当b1由20变为45，最优解是否发生变化。
4）求新解增加一个变量x6，c6=10，a16=3，a26=5，对最优解是否有影响
5）c2有5变为6，是否影响最优解。
答：最优解为
1)
Cj
-5
5
13
0
0
θ
CB
XB
b
X1
X2
X3
X4
X5

0
X4
20
-1
1
3
1
0
20/3
0
X5
90
12
4
10
0
1
9
Cj-Zj
-5
5
13
0
0

13
X3
20/3
-1/3
1/3
1
1/3
0
20
0
X5
70/3
46/3
22/3
0
-10/3
1
70/22
Cj-Zj
-2/3
2/3
0
-13/3
0

13
X3
185/33
-34/33
0
1
2/11
-1/22

5
X2
35/11
23/11
1
0
-5/11
3/22

-68/33
0
0
-1/11
-1/11

最优解为X1=185/33, X3=35/11
2)对偶问题最优解为
Y＝（1/22,1/11,68/33,0,0）T
3)
当b1=45时
X= 45/11
-11/90
由于X2的值小于0，所以最优解将发生变化
4）P6’=(3/11,-3/4)T
σ6=217/20>0
所以对最优解有影响。
5）当C2=6
σ1=-137/33
σ4=4/11
σ5=-17/22
由于σ4大于0所以对最优解有影响
5. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（15分）

V1
(5,0) (3,3)
(3,3)
VS （4,1） V2

(4,0)
(9,3) (8,4)
V3 Vt
(6,0)
最大流为：14
V1
(5,3) (3,3)
(3,0)
V2
Vs (4,4)
(4,1)
(9,7) (8,8)
Vt
V3 (6,6)

6. 考虑如下线性规划问题（20分）
Max z=3x1+x2+4x3
s.t. 6x1+3x2+5x3≤9
3x1+4x2+5x3≤8
x1，x2， x3≥0
回答以下问题：1）求最优解； 2）直接写出上述问题的对偶问题及其最优解；
3）若问题中x2列的系数变为（3，2）T，问最优解是否有变化；
4）c2由1变为2，是否影响最优解，如有影响，将新的解求出。

Cj
3
1
4
0
0
CB
XB
b
X1
X2
X3
X4
X5

0
X4
9
6
3
5
1
0
0
X5
8
3
4
5
0
1
Cj-Zj
3
1
4
0
0
0
X4
1
3
-1
0
1
-1
4
X3
8/5
3/5
4/5
1
0
1/5
Cj-Zj
3/5
-11/5
0
0
-4/5
3
X1
1/3
1
-1/3
0
1/3
-1/3
4
X3
7/5
0
1
1
-1/5
2/5
Cj-Zj
0
-2
0
-1/5
-3/5
最优解为X1=1/3,X3=7/5,Z=33/5
2)对偶问题为
Minw9y1+8y2
6y1+3y2≥3
3y1+4y2≥1
5y1+5y2≥4
y1,y2≥0
对偶问题最优解为y1=1/5,y2=3/5
3) 若问题中x2列的系数变为（3，2）T 则P2’=(1/3,1/5)T σ2=-4/5＜0
所以。对最优解没有影响
4）c2由1变为2 σ2=-1＜0
所以。对最优解没有影响
7. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（10分）
V1 (4,4 ) V3
(9,5) (6,3)

VS (3,1) (3,0) (4,1) Vt

(5,3) (7,5)
V2 (5,4) V4
解：

V1 (4,4) V3
(9,7) (6,4)
(3,2) (4,0)
Vs Vt
(5,4) (7,7)

V2 (5,5) V4
最大流＝11
8. 某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表：

Ⅰ Ⅱ Ⅲ
设备能力(台.h)

A
B
C
1 1 1
10 4 5
2 2 6
100
600
300
单位产品利润(元)
10 6 4

1)建立线性规划模型，求获利最大的产品生产计划。(15分)
2)产品Ⅲ每件的利润到多大时才值得安排生产？如产品Ⅲ每件利润增加到50/6元，求最优计划的变化。(4分)
3)产品Ⅰ的利润在多大范围内变化时，原最优计划保持不变。(2分)
4)设备A的能力在什么范围内变化时，最优基变量不变。(3分)
5)如有一种新产品，加工一件需设备A、B、C的台时各为1、4、3h，预期每件为8元，是否值得生产。(3分)
6)如合同规定该厂至少生产10件产品Ⅲ，试确定最优计划的变化。(3分)
解：1）建立线性规划模型为：
MaxZ=10x1+6x2+4x3
x1+x2+x3≤100
10x1+4x2+5x3≤600
2x1+2x2+6x3≤300
xj≥0,j=1,2,3
获利最大的产品生产计划为：X*=(x1,x2,x3,x4,x5,x6)’=(100/3,200/3,0,0,0,100)’ Z*=2200/3
2）产品Ⅲ每件利润到20/3才值得生产。如果产品Ⅲ每件利润增加到50/6元，最优计划的变化为：Xx1,x2,x3,x4,x5,x6)’=(175/6,275/6,25,0,0,0)’ Z*=775
3）产品Ⅰ的利润在[6,15]变化时，原最优计划保持不变。
4）设备A的能力在[60,150]变化时，最优基变量不变。
5）新产品值得生产。
6）最优计划的变化为：X*=(x1,x2,x3,x4,x5,x6)’=(190/6,350/6,10,0,0,60 )’ Z*=706.7
9. 给出成性规划问题：(15分)
Min z=2x1+3x2+6x3

x1+2x2+x3≥2
-2x1+x2+3x3≤-3
xj≥0 j=1,…，4
要求：
(1)写出其对偶问题5分) (2)利用图解法求解对偶问题。(5分)
(3)利用(2)的结果，根据对偶问题性质写出原问题最优解。(5分)
解：1）该问题的LD为：
MaxW=2y1-3y2
y1-2y2≤2
2y1+y2≤3
y1+3y2≤6
y1≥0,y2≤0
2)用图解法求得LD的最优解为：Y*=(y1,y2)’=(8/5,-1/5)’ W*=19/5
3)由互补松弛定理：
原问题的最优解为：X*=(x1,x2,x3)’=(8/5,1/5,0)’
10. 销
产
某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量，各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于下表中，要求研究产品如何调运才能使总运量最小？(10分)

B1
B2
B3
B4
产量

A1
4
12
4
11
32
A2
2
10
3
9
20
A3
8
5
11
6
44
销量
16
28
28
24
96╲96
解：最优调运方案为：
A1-B3和B4 28t和4t
A2-B1和B4 16t和4t
A3-B2和B4 28t和16t
最小总运费为：460元
11. 求解下列0-1规划问题
maxz=3x1+2x2-5x3-2x4+3x5

x1+x2+x3+2x4+x5≤4
7x1+3x3-4x4+3x5≤8
11x1-6x2+3x4-3x5≥3
xj=0或1 (j=1,…，5)
解：最优解为：x1=x2=1，其他为0 ，最优目标函数值为5

7 / 7