运筹学试题及答案
一、填空题：（每空格2分，共16分）
1、线性规划的解有唯一最优解、无穷多最优解、无界解
和无可行解四种。
2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明如果在该空格中增
加一个运量运费将增加4。
3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？错
4、如果某一整数规划：
MaxZX1X2X1914X2≤5114
2X1X2≤13X1X2≥0且均为整数所对应的线性规划（松弛问题）的最优解为X132，X2103，MaxZ629，我们现在要对X1进行分枝，
应该分为X1≤1和X1≥2。
5、在用逆向解法求动态规划时，fksk的含义是：从第k个阶段到第
个阶段的最优解。6假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关
系为D包含B
7已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等
式）其中X3X4X5为松驰变量。
XB
b
X1
X4
3
0
X1431
X2
1
0
CjZj
0
X2
X3
X4
X5
0213
013023
1001
05023
213
问：（1）写出
B1


1
3
0
23
001
2对偶问题的最优解：Y＝（5，0，23，0，0）T
8线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数
为0______；
9极大化的线性规划问题为无界解时，则对偶问题_无解_____；
10若整数规划的松驰问题的最优解不符合整数要求，假设Xibi不符合整数要求，INT（bi）是不超
过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1和Xi≤INT（bi）
，分别
将其并入上述松驰问题中，形成两个分支，即两个后继问题。
11知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）
其中X4X5X6为松驰变量。
XB
b
X1
X2
X3
X4
X5
X6
X1
2
1
1
0
2
0
1
X3230
0
1
1
0
4
X5
1
020
1
1
6
CjZj
000409
f问：1对偶问题的最优解：Y＝409000T（2）写出B1
201104116
二、计算题（60分）1、已知线性规划（20分）
MaxZ3X14X2
X1X2≤5
2X14X2≤12
3X12X2≤8
X1X2≥0
其最优解为：
基变量
X1
X2
X3
X4
X5
X3
32
0
0
1
1814
X2
52
0
1
0
38
14
X1
1
1
0
0
1412
σj
0
0
0
3412
1）写出该线性规划的对偶问题。
2）若C2从4变成5，最优解是否会发生改变，为什么？3）若b2的量从12上升到15，最优解是否会发生变化，为什么？4）如果增加一种产品X6，其P6231T，C64该产品是否应该投产？为什么？解：
1对偶问题为
Mr