一、填空题：（每空格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 ??2?-1
问：（1）写出B=??1/3?0?1.003??2/3? ?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 / 8
问：(1)对偶问题的最优解： Y＝(4,0,9,0,0,0)T
-1
（2）写出B=
?2? ?1?1?0011??4? 6??
二、计算题（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，最优解是否会发生变化，为什么？
T
4）如果增加一种产品X6，其P6=(2,3,1)，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 / 8
2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共15分）。 销地 B1 B2 B3 产量 产地 A1 5 9 2 15 A2 3 1 7 11 A3 6 2 8 20 销量 18 12 16 解：初始解为 A1 A2 A3 销量/t 计算检验数
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所示：
3 / 8
B1 18 18 B2 11 1 12 B3 15 1 16 产量/t 15 11 20
（15分） 项目 投标者 甲 乙 丙 丁 A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 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 4 / 8
由于X2的值小于0，所以最优解将发生变化
T
4）P6’=(3/11,-3/4) σ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 5 / 8
运筹学试题及答案11
