填空题
1．线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。
2．线性规划模型有三种参数，其名称分别为价值系数、___和___。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。 4．求最小生成树问题，常用的方法有：避圈法和 ___。
5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。
6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。
7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。
8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。
判断题：
1、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大还是极小，原问题可行解的目标函数值一定超过其对偶问题可行解的目标函数值。 （ ）
2、如线性规划问题存在可行域，则可行域一定包含坐标的原点。 （ ） 3、含n个变量m个约束的标准型线性规划问题，基解数恰好为Cm
n个。 （ ）
4、若X1,X2分别是某一线性规划的最优解，则X??X1?(1??)X2也是该线性规划问题的最优解，其中0???1。 （ ） 5、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 （ ） 6、任何线性规划问题具有唯一的对偶问题。 （ ） 7、单纯形法计算中选取最大正检验数?k对应的变量xk作为换入基的变量，将使迭代后的目标函数得到最快的增长。 （ ）
8、如果线性规划的对偶问题无可行解，则原问题也一定无可行解。 （ ）
9、原问题求最大值，第i个约束是“≥”约束，则该约束条件对应的对偶变量yi ≤0 。 （ ） 10、对取值无约束的变量 xj，通常令xj?x??j?x?j?，其中
x?j?0,x?j??0，在用单纯形法求
得的最优解中，有可能同时出现x?j?0,x?j??0 （ ）
第 1 页 共 8 页 11、线性规划问题标准形式的数学模型的目标函数是求最小值。 （ ） 2、如线性规划问题存在可行域，则可行域是一个凸集。 （ ） 3、对偶单纯形法就是求解对偶问题的单纯形法。 （ ） 4、构成运输问题初始方案的基变量的个数是m个。 （ ） 5、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 （ ） 6、运输问题中的非基变量的闭回路是存在而且是唯一的。 （ ） 7、在互为对偶的一对原问题与对偶问题中，如果一问题的变量取值非0，则其对偶问题的约束条件取严格的不等式。 （ ）
8、分配问题效率表中某一行元素分别加上（减去）一个常数，则最优解不变。 （ ） 9、原问题求最大值，某约束是“≥”约束，则该约束条件对应的对偶变量 ≤0。 （ ） 10、目标规划问题中的约束条件有刚性约束和柔性约束。 （ ）
单项选择题：
1、互为对偶的两个线性规划问题的解存在关系 （ ） A、原问题具有无界解，则对偶问题无可行解 B、对偶问题无可行解，原问题具有无界解 C、若最优解存在，则最优解相同
D、一个问题无可行解，则另一个问题也无可行解
2、线性规划具有唯一最优解是指 （ ） A、最优表中存在常数项为零 B、最优表中非基变量检验数全部非零 C、最优表中存在非基变量的检验数为零 D、可行解集合有界
3、原问题有6个变量4个约束，其对偶问题 （ ） A、有4个变量6个约束 B、有6个变量4个约束 C、有6个变量6个约束 D、有4个变量4个约束
4、具有n个顶点的树的边数恰好为 （ ）
A、(n-1) 条 B、n 条 C、(n+1)条 D、(n+2) 条
5、有4个产地5个销地的平衡运输问题模型具有特征 （ ）
第 2 页 共 8 页
A、有9个变量 B、有20个约束 C、有8约束 D、有8个基变量
6、X是线性规划的基本可行解则有 （ ） A、X中的基变量非零，非基变量为零 B、X不一定满足约束条件 C、X中的基变量非负，非基变量为零 D、X是最优解
1、互为对偶的两个线性规划问题的变量存在关系 （ ） A、在一个问题中是变量，则在另一问题中也是变量 B、在一问题中是基变量，则在另一问题中也是基变量 C、在一问题中是非基变量，则在另一问题中也是非基变量 D、在一问题中是基解变量，则在另一问题中是非基解变量
2、线性规划具有多个最优解是指 （ ） A、最优表中存在常数项为零 B、最优表中非基变量检验数全部非零 C、最优表中存在非基变量的检验数为零 D、可行解集合有界
3、原问题有5个变量4个约束，其对偶问题 （ ） A、有4个变量4个约束 B、有5个变量5个约束 C、有4个变量5个约束 D、有5个变量4个约束
4、μ是关于可行流f的一条增广链，则在μ上有 （ ） A、对任意 B、对任意
?C、对任意
D、.对任意
(i,j)??,有fij?0
5、关于树的性质，不正确的有 （ ）
A、树图是连通图 B、具有n个顶点的树图的边数恰好为（n-1）条 C、具有n个顶点的树图的边数恰好为n条 D、任何树图中必存在次为1的点 6、有4个产地4个销地的平衡运输问题模型具有特征 （ ） A、有8个变量 B、有16个约束 C、有4个约束 D、有7个基变量
7、互为对偶的两个线性规划若存在最优解，则存在关系 （ ）
A、Z > W B、Z = W
C、Z≥ W D、Z≤W
第 3 页 共 8 页 8、线性规划的约束条件为
则初始基可行解为 （ ）
A、(0, 2, 3, 2) B、(3, 0, -1, 0) C、(0, 0, 5, 6) D、(2, 0, 1, 2) 9、
（ ）
A、无可行解 B、有唯一最优解 C、有多重最优解 D、有无界解
10、X是线性规划的基本可行解则有 （ ） A、X中的基变量非零，非基变量为零 B、X不一定满足约束条件 C、X中的基变量非负，非基变量为零 D、X是最优解 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人
工变量，表明该线性规划问题 【 】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解
10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 【 】 A．b列元素不小于零 B．检验数都大于零
C．检验数都不小于零 D．检验数都不大于零
11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为 【 】
A．3 B．2 C．1 D．以上三种情况均有可能
12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 】
13．在运输方案中出现退化现象，是指数字格的数目 【 】 A．等于 m+n B．等于m+n-1
C．小于m+n-1 D．大于m+n-1
第 4 页 共 8 页
16．关于线性规划的原问题和对偶问题，下列说法正确的是 【 】 A．若原问题为元界解，则对偶问题也为无界解
B．若原问题无可行解，其对偶问题具有无界解或无可行解 c．若原问题存在可行解，其对偶问题必存在可行解 D．若原问题存在可行解，其对偶问题无可行解 18．下列说法正确的是 【 】
A．线性规划问题的基本解对应可行域的顶点
也必是该问题的
可行解
D．单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解 简答题：
1、 简述单纯形法的基本思路。 2、简述对偶单纯形法的基本思路。 3、简述运输问题求解的基本思路。 4、写出下列线性规划问题的对偶问题。 MaxZ?2x1?3x2 ?2x1? s.t.?2x2?12??4x1?16?5x?15
?2?x1,x2?05、将下列线性规划问题化为标准形式 MinW?12y1?16y2?15y3 ? s.t.?2y1?4y2?2??2y1?5y3?3
?y1，y2，y3?0??第 5 页 共 8 页 四、计算题：
1、有份说明书，要分别译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成，应如何分配，使四个人分别完成这四项任务总的时间为最小？
人 工作 甲 乙 丙 丁 译英 2 10 9 7 译日 15 4 14 8 译德 13 14 16 11 译俄 4 15 13 9 2、请用破圈法或避圈法求下图的最小部分树。
3、 已知线性规划（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该产品是否应该投产？为什么？ 4、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。
第 6 页 共 8 页
销地 B1 B2 B3 产量 产地 A1 5 9 2 15 A2 3 1 7 11 A3 6 2 8 20 销量 18 12 16 4、、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且
必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示： 项目 A B C D 投标者 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17
5、求解下列线性规划问题。
6、用匈牙利法求解下列分配问题。
7、用标号法算法求下图中s至t的最大流量，并找出该网络的最小割。（每弧旁的数字是（cij ,（fij））。
8、请用破圈法或避圈法求下图的最小部分树。
第 7 页 共 8 页
9、已知运输问题的产销地的供需量与单位运价表（如表所示），试用表上作业法求出其最优解。 Bj B1 B2 B3 B4 B5 产A量 i A1 5 7 2 4 1 5 A2 9 1 3 5 6 7 A3 2 4 8 1 3 6 需量 2 2 5 4 5 18
利用对偶理论证明其目标函数值无界。
第 8 页 共 8 页
运筹学复习题库
