运筹学试卷及答案(1)
- 格式：doc
- 大小：126.50 KB
- 文档页数：7
一、填空题：（每空格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=1003/20.3/1312
(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=
611401102
二、计算题（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分）。 3 / 7
销地
产地 B1 B2 B3 产量
A1 5 9 2 15
A2 3 1 7 11
A3 6 2 8 20
销量 18 12 16
解：初始解为
计算检验数
由于存在非基变量的检验数小于0，所以不是最优解，需调整
调整为：
重新计算检验数
所有的检验数都大于等于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 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
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 答最优解为：
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分） 5 / 7
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)对偶问题为
Minw=9y1+8y2
6y1+3y2≥3
3y1+4y2≥1
