运筹学复习考点PPT课件

在全部以数字格为顶点的闭回路。 • 正确。
2021
31
二、已知运输问题的产销平衡表，单位运价表及某一调运方案如下：
• 产销平衡表及调运方案 单位运价表
2021
32
第4章 整数规划与分配问题
• 一、判断题 • （1）整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标
函数值；
• 错误。 • （2）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的
• A.必须为“-1”，其余变量系数为“0”； • B.可取某一负的常数，其余变量系数为“0”； • C.取值为零，其余变量系数为原目标函数中系数Cj值； • D.为某一正的常数值，其余变量取值为“0”。 • 答案：D
2021
10
•
2021
11
•
2021
12
• 六、已知某线性规划问题单纯形法迭代时得到中间某两步的单纯 形表如下表所示，试将表中空白处的数字填上。
5 3 6 -6 0
0
801001
5
14 1 2 0 0 0
-6
4 0 1 -1 1 0
0 -1 0 0 0
2021
21
•
2021
22
• 三、
2021
23
• 四、某厂生产Ⅰ、Ⅱ、
Ⅰ ⅡⅢ
Ⅲ三种产品，分别经过 A、B、C三种设备加工，
A
1 11
已知生产单位各种产品
B
10 4 5
所需要的设备台时，设
1
0
0
25 0
0
1
0
0
0
0
0
0
1
0
0
2021
27
第3章 运输问题
2021
28
•
2021
29
• （4）如果运输问题单位运价表的某一行（或某一列）元素分别 加上一个常数k，最优调运方案将不会发生变化。
• 正确。 • （5）如果运输问题单位运价表的某一行（或某一列）元素分别
乘上一个常数k，最优调运方案将不会发生变化。
用表上作业法求解；
• 正确。 • （6）用割平面法求解来自百度文库数规划时，构造的割平面有可能切去一
些不属于最优解的整数。
• 错误。
2021
34
• （7）分枝定界法在需要分枝时必须满足：一是分枝后的各子问 题必须容易求解；二是各个子问题解的集合必须覆盖原问题的解。
• 正确。 • （8）一个整数规划问题如果存在两个以上的最优解，则该问题
相应列的数字可以从单纯形表中删除，而不影响计算结果。
• 正确。 • 人工变量一般是为取得对应的初始基基向量而引入的，它一旦成
为出基变量，其地位已被对应的入基变量取代，删除单纯形表中 该变量及相应列的数字，不影响计算结果。
2021
5
•
2021
6
• （11）线性规划问题的可行解如为最优解，则该可行解一定是基本可 行解。
这样就有了无穷多的最优解。
2021
7
• (13)若线性规划问题的可行域可以伸展到无限，则该问题一定具 有无界解。
• 错误。 • （14）如果某线性规划模型的一个最优解不是基可行解，则可以
断定该问题有无穷多最优解。
• 正确
2021
8
•
2021
9
二、选择题
• 1.用单纯形法求解线性规划问题采用两阶段法计算时，第一阶段 计算的单纯形表中人工变量系数取值（）
运筹学复习
《运筹学》
2021
1
第1章 线性规划及单纯形 法
2021
2
• 一、判断题 • （1）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者
是一致的。 • 正确。 • （2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，
减少一个约束条件，可行域的范围一般将扩大。 • 正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会
5
1
0
0
0
0
0
5
1
0
0
0
4
0
1
0
4
0
1
检验数：(0,0,0,-45/240211,-24/41,-11/41)
13
第2章 线性规划的对偶理论
2021
14
• 一、判断题 • （1）任何线性规划问题存在并具有唯一的对偶问题。 • 正确。 • （2）对偶问题的对偶一定是原问题。 • 正确。 • （3）根据对偶问题的性质，当原问题为无界解时，其对偶问
一定有无穷多最优解。 • 错误。
C
2 26
备的现有加工能力以及 单位产品利润/元 10 6 4 每件产品的预期的利润
如下表：
设备能力/台•h 100 600 300
2021
24
•
6 10 0
10 6
4
0
0
0
0
1
1
0
100 0
0
4
0
0
0
0
0
1
0
2021
25
•
2021
26
10 6
0
0
0
6
0
1
10
1
0
0
100 0
0
4
0
0
6
0
1
0
10
题无可行解；反之，当对偶问题无可行解时，其原问题具有无界 解。
• 错误。
2021
15
•
2021
16
•
2021
17
•
2021
18
•
2021
19
•
2021
20
• 二、已知线性规划问题：
• （a）写出其对偶问题；
• （b）已知原问题用两阶段法求解时得到的最终单纯形表如下,试写出其
对偶问题的最优解。
目标函数值是该问题目标函数值的下界；
• 正确。 • （3）用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可
行解时，通常可任取其中一个作为下界值，再进行比较剪枝。
• 错误。
2021
33
• （4）指派问题效率矩阵的每个元素都乘上同一个常数k，将不影 响最优指派方案；
• 错误。 • （5）指派问题数学模型的形式同运输问题十分相似，故也可以
• 错误。 • （6）如果运输问题单位运价表的全部元素乘上一个常数k
（k>0），最优调运方案将不会发生变化。
• 正确。
2021
30
• （7）用位势法求运输问题某一调运方案的检验数时，其结果可 能同闭回路法求得的结果有异。
• 错误。 • （8）运输问题初始方案的基本要求:（m+n-1）个数字格，不存
变小。
• （3）线性规划问题的每一个基解对应可行域的一个顶点。
• 错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于
可行域的顶点。
2021
3
•
2021
4
• （7）单纯形法计算中，如不按最小比值原则选取换出变量，则 在下一个解中至少有一个基变量的值为负。
• 正确。 • （8）一旦一个人工变量在迭代中变为非基变量后，则该变量及
• 错误。
• 唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优 解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可 行域的顶点。
• （12）若线性规划问题具有可行解，且其可行域有界，则该线性规划 问题最多具有有限个数的最优解。
• 错误。
• 如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，