目录 内容简介 目 录 第 1 章 运筹学概论 1 复习笔记 2 课后习 1.3 考研真题详解 第 2 章 线性规划与目标规划 1 复习笔记 2 课后习 2.3 考研真题详解 第 3 章 对偶理论与灵敏度分析 1 复习笔记 2 课后习 3.3 考研真题详解 第 4 章 运输问题 1 复习笔记 2 课后习 4.3 考研真题详解 第 5 章 目标规划 1 复习笔记 2 课后习 5.3 考研真题详解 第 6 章 整数规划 1 复习笔记 2 课后习 6.3 考研真题详解 第 7 章 无约束问题 1 复习笔记 2 课后习 7.3 考研真题详解
第 8 章 约束极值问题 1 复习笔记 2 课后习 8.3 考研真题详解 第 9 章 动态规划的基本方法 1 复习笔记 2 课后习 9.3 考研真题详解 第 10 章 动态规划应用举例 1 复习笔记 2 课后习 10.3 考研真题详解 第 11 章 图与网络优化 1 复习笔记 2 课后习 11.3 考研真题详解 第 12 章 网络计划 1 复习笔记 2 课后习 12.3 考研真题详解 第 13 章 排队论 1 复习笔记 2 课后习 13.3 考研真题详解 第 14 章 存储论 1 复习笔记 2 课后习 14.3 考研真题详解 第 15 章 对策论基础 1 复习笔记 2 课后习 15.3 考研真题详解 第 16 章 单目标决策
1 复习笔记 2 课后习 16.3 考研真题详解 第 17 章 多目标决策 1 复习笔记 2 课后习 17.3 考研真题详解 第 18 章 启发式方法 1 复习笔记 2 课后习 18.3 考研真题详解
第 第 1 章
运筹学概论 1.1
复习笔记 1．运筹学简史 运筹学由英国人在 20 世纪 30 年代末首次提出，英文简写 OR，我国于 1957 年正式将其定名为运筹学。1951 年由莫尔斯（P.M.Morse）与金博尔（G.E.Kimball）出版的《运筹学方法》是早期运筹学的重要著作。20 世纪 50 年代中期，钱学森、许国志等教授将运筹学由西方引入我国，并结合我国的特点在国内推广应用。我国已于 1982 年加入由英、美、法三国的运筹学会于 1959 年成立的国际运筹学联合会（IFORS）。
2．运筹学的性质和特点 运筹学是一种以量化为基础，多学科交叉，以求得最优决策方案为目的的科学方法。为了有效运用运筹学，前英国运筹学学会会长托姆林森提出了六条原则: （1）合伙是指运筹学工作者要和各方面人，尤其是同实际部门工作者合作。
（2）催化原则。在多学科共同解决某问题时，要引导人们改变一些常规的看法 （3）互相渗透原则。要求多部门彼此渗透地考虑问题，而不是只局限于本部门。
（4）独立在研究问题时，不应受特殊政策所左右，应独立从事工作。
（5）宽容解决问题的思路要宽，方法要多，而不是局限于某种特定的方法。
（6）平衡原则。要考虑各种矛盾的平衡，关系的平衡。
3．运筹学的步骤 运筹学在解决大量实际问题过程中形成了自己的工作步骤。
（1）提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料； （2）建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来； （3）求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出 （4）解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题； （5）解的控制。通过控制解的变化过程决定对解是否要作一定的改变；
（6）解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
4．运筹学的模型 运筹学在解决问题时，按研究对象不同可构造不同的模型。模型主要有三种基本形式：形象模型；模拟模型；符号或数学模型。其构造方法主要包括以下五种：直接分析法；类比法；数据分析法；试验分析法；想定（构想）法等。模型的一般数学形式可表述为：
目标的评价准则
U=f（x i ，y i ，ξ k ）
约束条件 g（x i ，y i ，ξ k ）≥0 其中：x i ——可控变量； y i ——已知参数； ξ k ——随机因素。
1.2
课后习题详解 本章无课后习题。
1.3
考研真题详解 本章只是对本课程的一个简单介绍，不是考试重点，所以基本上没有学校的考研试题涉及到本章内容，因此，读者可以简单了解，不必作为复习重点，本部分也就没有可选用的考研真题。
第 第 2 章
线性规划与目标规划 2.1
复习笔记 1．线性规划模型的概念及其一般形式 线性规划问题的共同特征：
（1）每一个问题都用一组决策变量 表示某一方案，这组决策变量的某一确定值就代表一个具体方案。一般这些变量的取值是非负且连续的。
（2）存在有关的数据，如资源拥有量、消耗资源定额、创造新价值量等，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数在决策变量取值范围内实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：
目标函数
（2-1）
（2-2）
（2-3）
在上述模型中，式（2-1）称为目标函数 为价值系数；式（2-2）、式（2-3）称为约束条件； 称为技术系数， 称为限额系数；式（2-3）也称为变量的非负约束条件。
2．线性规划问题的标准型及标准化 （1）线性规划的标准型
或
（2-4）
（2-5）
线性规划的标准型要求：目标函数是 Max 型；约束条件是等式约束；决策变量非负。
（2）线性规划的标准化方法 ①若要求目标函数实现最小化，即 ，则只需将目标函数最小化变换为求目标函数最大化，即令 ，于是得到 。
②约束方程为不等式。这里有两种情况：一种是约束方程为“≤”不等式，则可在“≤”不等式的左端加入非负松弛变量，把原“≤”不等式变为等式；另一种是约束方程为“≥”不等式，则可在“≥”不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件。
③若决策变量 为无约束变量，则令 ，其中 ， ≥0。
④若原模型中某决策变量 有下界或上界，即 或 ，则在标准型中，令 ，即用 取代原 ，其中 ；或 ，即用 取代 ，其中 。
3．线性规划问题解的概念 （1）可行解：满足约束条件（2-4）式、（2-5）式的解 ，称为线性规划问题的可行解。
（2）最优解：使目标函数达到最大值的可行解称为最优解。
（3）基：若 A 是约束方程组的 （m＜n）维系数矩阵，其秩为 。B 是矩阵 A 中阶非奇异子矩阵（|B|≠0），则称 B 是线性规划问题的一个基。
（4）基向量、非基向量：基中的列向量称为基向量，系数矩阵中基以外的其余个列向量就称为非基向量。
（5）基变量与非基变量：与基向量对应的变量称为基变量；与非基向量相对应的变量称为非基变量，显然，基变量有 个，非基变量有 个。
（6解：令所有非基变量为 0，求出满足约束条件式（2-4）的解称为基解。
（7）基可行解：满足（2-5）式的基解称为基可行解。
（8）可行基：对应于基可行解的基，称为可行基。
非可行解、可行解、基解、基可行解之间的关系如图 2－1 所示：
图 2－1 4．线性规划问题解的几何意义 （1）凸集的概念：设 是 维欧氏空间中的一点集，若任意两点 的连线上的所有点 ，则称 为凸集。
（2）关于线性规划的几个定理 定理 1
若线性规划问题存在可行域 D，则 D 是凸集。
引理 1
线性规划问题的可行解 为基可行解的充要条件是 的正分量所对应的系数列向量是线性独立的。
定线性规划问题的基可行解 对应于可行域 的顶点。
引理 2
若 K 是有界凸集，则任何一点 X∈K 可表示为 K 的顶点的凸组合。
定理 3
若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。
定理 4
若线性规划问题在至少两个顶点上到达最优，则该问题有无穷多最优解，最优解即是这些顶点的凸组合。
5．线性规划问题的求解方法 （1）图解法 图解法是一种使用作图的方法直接在图上找到线性规划问题的最优解的方法，简单直观，有助于了解线性规划问题求解的基本原理，仅适用于决策变量为二维的情况。
图解法的求解步骤为：
①建立平面直角坐标系； ②根据约束条件画出约束直线，找出可行域； ③图示出目标函数，作出一条直线； ④将目标函数直线沿其法线方向在可行域中平移至边界，直至找到使目标函数达到最优的边界点为止，该边界点即为线性规划的最优解。
注意：
①有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。
②无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。
③若可行域为空集，即无可行解，也不存在最优解。
（2）单纯形法 单纯形法求解线性规划的思路：一般线性规划问题线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，并决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。
单纯形法的基本步骤为：
①根据线性规划模型确定初始可行基和初始基可行解，建立初始单纯形表。
②计算各非基变量 的检验数 ，若所有 ，则已经得到最优解，计算停止；否则，转下一步。
③在 中若有某个检验数 对应的非基变量 的系数列向量 ，则此问题为无界解，停止计算；否则，转下一步。
④根据 ，确定非基变量 为换入变量，再根据 法则
可以确定 为换出变量，转下一步。
⑤以 为主元素进行迭代（即用高斯消去法或旋转运算进行矩阵的行变换），使变换为第 行的元素为 1，其余元素为 0 的列向量；并将基 B 对应的基变量 列中的换为 ，从而得到新的单纯形表；重复步骤②～⑤，直到计算停止。
（3）单纯形法的进一步讨论——人工变量法 分别给（1-4）中每一个约束方程加入人工变量 ，可得到
①大 M 法 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值没有影响，则当目标函数为极大化时，人工变量在目标函数中的系数为 ，其中 为任意大的正数；反之，当目标函数为极小化时，人工变量在目标函数中的系数为 ，即
或
②两阶段法 第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。
然后用单纯形法求解上述模型，若得到 ，这说明原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。
第二阶段：将第一阶段计算得到的最终单纯形表，除去人工变量。将目标函数行的系数，换为原问题的目标函数的系数，作为第二阶段计算的初始单纯形表。继续使用单纯形法求解，以得到最优解。
6．线性规划问题解的情况及解的判别 （1）线性规划问题解的几种情况 ①有惟一最优解； ②有无穷多最优解； ③无可行解； ④无限最优解（即无界解）。
（2）解的判别 ①最优解的判别定理：若 为对应于基 B 的一个基可行解，且对于一切 ，有检验数 ，则 为最优解。
②无穷多最优解的判别定理：若 为一个基可行解，对于一切 ，有检验数 ，且存在某个非基变量的检验数 ，则线性规划问题有无穷多最优解。
③无界解的判别定理：若 为一基可行解，有一个 ，并且对 ，有 ，那么该线性规划问题具有无界解（或称无最优解）。
7．求解线性规划问题时应注意的几个问题 （1）在极大化问题中，若令 ，则 为解的判别准则；若令 ，则 为解的判别准则；
（2）在极小化问题中，若令 ，则 为解的判别准则；若令 ，则 为解的判别准则； （3）在极大化问题中，若有几个检验数 且最大，则取其下标最小的非基变量作为换入变量，极小化问题对应成立； （4）在极大化问题中，若按 法则计算时存在两个或两个以上的最小比值，则应选其中下标最小的基变量 为换出变量，极小化问题对应成立。
2.2
课后习题详解 2.1
用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、无界解还是无可行解? （1）
解：如图 2-2 所示，该问题的可行域为有界域。目标函数 在点 A 3 处取得最大值，求解方程组 可得 A 3 的坐标为（2，4），所以 ，该线性规划问题具有惟一最优解。
图 2-2
（2）
解：如图 2-3 所示，该线性规划问题的可行域无界。目标函数 在点 A 处取得最小值，求解方程组 得 A 点的坐标为 ，所以 ，，该问题具有惟一最优解。
图 2-3 （3）
解：如图 2-4 所示，该问题的可行域无界。目标函数可以增加到无穷大，因此该问题具有无界解。
图 2-4 （4）
解：如图 2-5 所示，该问题的可行域为空集，因此该线性规划无可行解。
图 2-5 2.2
将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）
解：令 ，且 ；在第一个约束条件两边同时乘以-1 后引入人工变量 ，在第二个约束条件右端加上松弛变量 ；在第三个约束条件右端减去剩余变量 ，同时加入人工变量 ，将目标函数最小化变换为最大化，得该线性规划的标准型
其中，M 为充分大的正数，对应的初始单纯形表如表 2-1 所示：
表 2-1
（2）
解：在上述约束条件两边同时乘以-1，然后分别引入人工变量 ，得该线性规划的标准型
其中，M 为充分大的正数。对应的初始单纯形表如表 2-2 所示：
表 2-2
2.3
在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
（1）
解：在第二个约束条件两边同时乘以-1，得到该线性规划问题的系数矩阵
①因为 、 线性无关，故有
令非基变量 ，解得 ，故有基可行解 ， 。
②因为 、 线性无关，故有
令非基变量 ，解得 ，故 ，不是可行解。
③因为 、 线性无关，故有
令非基变量 ，解得 ，故有基可行解 ，。
④因为 、 线性无关，故有
令非基变量 ，解得 ，故有基可行解 ，。
⑤因 、 线性无关，故有
令非基变量 ，解得 ，不是可行解。
⑥因 、 线性无关，故有
令非基变量 ，解得 ，不是可行解。
在 中， 为最大值，所以最优解 ， 。
（2）
解：其系数矩阵为
①因为 、 线性无关，故有
令非基变量 ，解得 ，不是可行解。
②因为 、 线性无关，故有
令非基变量 ，解得 为基可行解， 。
③因为 、 线性无关，故有
令非基变量 ，解得 ，不是可行解。
④因为 、 线性无关，故有
令非基变量 ，解得 为基可行解， 。
⑤因为 、 线性无关，故有
令非基变量 ，解得 为基可行解， 。
⑥因为 、 线性相关，故 不能构成基变量。
在 中， 为最大值，所以最优解 ， 。
2.4
用单纯形法求解习题 2.1 中的线性规划问题。
解（1）标准型为 max z=x 1 +3x 2 +0x 3 +0x 4 +0x 5
s.t.
使用单纯形法求解，得到单纯形表：
表 2-3
c j
1
3
0
0
0
θ i
C B
X B
b
x 1
x 2
x 3
x 4
x 5
x 3
50
5
10
1
0
5
x 4
-1
-1
[-1]
1
0
1
0
x 5
4
0
1
0
0
1
4
1
3
0
0
0
x 3
40
-5
0
1
10
4
3
x 2
1
1
1
-1
0
－
0
x 5
3
-1
0
0
[1]
1
3
-2
0
0
3
0
0
x 3
10
[5]
0
1
-10
2
3
x 2
4
0
1
0
0
x 4
3
-1
0
0
1
1
－
1
0
0
-3
1
x 1
2
1
0
1／5
-2
3
x 2
4
0
1
0
0
1
0
x 4
5
0
0
1／5
1
-1
0
0
-1／5
0
-1
由表 2-3 得最优解 X*=（2，4，0，5，0）
T ，max z=14。
（2）标准型为：
min z=x 1 +1.5x 2 +0x 3 +0x 4 +Mx 5 +Mx 6 ，M 为无穷大正数。
s.t.
使用单纯形法求解，得到单纯形表，如表 2-4 所示。
表 2-4
c j
1
1.5
0
0
M
M
θ i
C B
X B
b
x 1
x 2
x 3
x 4
x 5
x 6
x 5
3
［3］
－1
0
1
0
1
M
x 6
2
1
1
0
－1
0
1
2
－5M
1－2M
1.5－4M
M
M
0
1.5
x 2
1
1/3
1
－1/3
0
1/3
0
3
M
x 2
1
[ ]
0
1/3
－1
－1/3
1
3/2
－M－1.5
0
M
0
1.5
x 2
1 0
1
－1/2
1/2
1/2
－1/2
1
x 1
3/2
1
0
1/2
－3/2
－1/2
3/2
－9/4
0
0
1/4
3/4
由表 2-4 得最优解 X*=（3／2，1／2，0，0，0，0），min z=9／4。
（3）标准型为：
max z=2x 1 +2x 2 +0x 3 +0x 4
s.t.
使用单纯形法求解，得到单纯形表如表 2-5 所示：
表 2-5
c j
2
2
0
0
θ i
C B
X B
b
x 1
x 2
x 3
x 4
x 3
1
[1]
1
0
1
0
x 4
2
-1/2
1
0
1
2
2
2
0
0
2
x 2
-1
1
1
0
－
0
x 4
1
[1／2]
0
-1
1
2
4
0
-2
0
x 2
3
0
1
-1
2
x 1
2
1
0
-2
2
－
0
0
6
-8
由表 2-5 可知，非基变量 x 3 的检验数为 6>0，但其系数均小于 0，因此线性规划问题为无界解。
（4）标准型为：
max z=x 1 +x 2 +0x 3 +0x 4
s.t.
使用单纯形法求解，得到单纯形表：
表 2-6
c j
1
1
0
0
θ i
C B
X B
b
x 1
x 2
x 3
x 4
x 3
0
—1
[1]
1
0
0
0
x 4
-3
3
-1
0
1
3
0
1
1
0
0
1
x 2
0
[-1]
1
0
0
0
x 4
-3
2
0
1
1
－
-1
2
0
-1
0
1
x 1
0
1
[-1]
-1
0
0
0
x 4
-3
0
2
3
1
－
-1
2
0
1
x 2
0
-1
1
0
0
x 4
-3
2
0
1
1
-1
2
0
-1
0
由表 2-6 可知，此线性规划问题无解。
2.5
以
为例用图解法，具体说明当目标函数中变量的系数怎样改变时，使满足约束条件的可行域的每一个顶点，都有可能使目标函数值达到最优。
解：（1）当 时，目标函数 ，令
①若 ，则当 时，目标函数在点 A 3 （4，0）处取得最大值；当 时，目标函数在原点（0，0）处取得最大值； ②若 ，则当 时，目标函数在点 A 2 处取得最大值，其中时，在线段 A 2 A 3 上的任一点取得最大值；当 时，目标函数在原点处取得最大值； ③若 ，则当 时，目标函数在点 A 1 （0，3）处取得最大值，其中时，在线段 A 1 A 2 上的任一点取得最大值；当 时，目标函数在坐标原点处取得最大值； ④若 ，则当 时，目标函数在点 A 1 （0，3）处取得最大值；当 时，目标函数在点 A 3 （4，0）处取得最大值。
（2）当 时，目标函数
①当 时，目标函数在点 A 3 （4，0）处取得最大值； ②当 时，目标函数在可行域 OA 1 A 2 A 3 中的任一点处均可取得最大值； ③当 时，目标函数在线段 OA 1 上的任一点取得最大值。
2.6
分别用单纯形法中的大 法和两阶段法求解下述线性规划问题，并指出属哪一类解。
（1）
解：①大 法 在上述问题的第二个约束条件中减去剩余变量 ，再加入人工变量 ，得
其中， 是一个任意大的正数，应用单纯形法迭代计算如表 2-7 所示：
表 2-7
2
3
-5
-M
0
-M
C B
X B
b
x 1
x 2
x 3
x 4
x 5
x 6
x 4
7
1
1
1
0
0
7
-M
x 6
10
[2]
-5
1
0
-1
1
5
3M+2
3-4M
2M-5
0
-M
0
-M
x 4
2
0
[7]
1
1/2
-1/2
4/7
2
x 1
5
1
-5/2
1/2
0
-1/2
1/2
－
0
7M/2+8
M/2-6
0
M/2+1
-3M/2-1
3
x 2
4/7
0
1
1 2 1/7
－1/7
2
x 1
45/7
1
0
6/7
5/7
-1/7
1/7
0
0
-50/7
-M-16/7
-1/7
-M+1/7
求得该问题最优解 ，最优目标函数值 。
②两阶段法
在上述问题的第二个约束条件中减去剩余变量 ，再加入人工变量 ，得第一阶段的模型为
第一阶段模型求解过程如表 2-8 所示：
表 2-8
求得最优解为 ，其目标函数最优值 ，此时人工变量，故 为原线性规划问题的基可行解。
将第一阶段最终单纯形表中的人工变量去除，并换成原问题目标函数的系数，进行第二阶段的运算，如表 2-9 所示：
表 2-9
可得问题的最优解 ，最优目标函数值 。
（2）
解：①大 法 在上述两个约束条件中分别减去剩余变量 ，再加入人工变量 ，得
其中， 是一个任意大的正数，应用单纯形法进行计算如表 2-10 所示：
表 2-10
可得问题的最优解 ，最优目标函数值 。因为非基变量的检验数中
，所以该线性规划问题有无穷多最优解。
②两阶段法 在上述线性规划问题的约束条件中分别减去剩余变量 ，再加上人工变量 ，得第一阶段的数学模型为：
第一阶段的求解过程如表 2-11 所示：
表 2-11
上述线性规划问题最优 ，其目标函数最优值 ，可以继续进行计算。
第二阶段初始单纯形表如表 2-12 所示：
表 2-12
已满足所有检验数非负，可得问题的最优解 ，最优目标函数值 。因为非基变量的检验数中 ，故此线性规划问题有无穷多最优解。
2.7
求下述线性规划问题目标函数 z 的上界 和下界 。
其中: 。
解：（1）要求 z 的上界 ，则 应取其最大值； 应取其最小值，此时，得到的线性规划问题为
在上述问题的第一个约束条件中加入松弛变量 ，第二个约束条件左右两边同时除以2 再加入松弛变量 ，得到该线性规划问题的标准型
单纯形法的计算过程如表 2-13 所示：
表 2-13
解得最优解 ，目标函数 z 的上界 。
（2）要求 z 的下界 ，则 应取其最小值； 应取其最大值，此时，得到的线性规划问题为
在上述问题的第一个约束条件中加入松弛变量 ，第二个约束条件左右两边同时除以2 再加入松弛变量 ，得到该线性规划问题的标准型
单纯形法的计算过程如表 2-14 所示：
表 2-14
解得最优解 ，目标函数 z 的下界
2.8
表 2-15 是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，为待定常数。试说明这些常数分别取何值时，以下结论成立。
（1惟一最优解； （2）表中解为最优解，但存在无穷多最优解； （3）该线性规划问题具有无界解； （4）表中解非最优，为对解改进，换入变量为 ，换出变量为 。
表 2-15
解：（1）当 时，表中解为惟一最优解； （2）当 且 =0 时，表中的解为最优解，且原问题有无穷多个最优解； （3）当 时，该线性规划问题具有无界解； （4）当 时，表中的解非最优，对解进行改进，换入变量为 ，换出变量为 。
2.9
某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如表 2-16 所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作 8h，问该公交线路至少需配备多少名司机和乘务人员。列出这个问题的线性规划模型。
表 2-16
解：设 为从第 班次开始上班的司机和乘务员的人数，则可建立数学模型为：
2.10
某糖果厂用原料 A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中 A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表 2-17 所示：
表 2-17
原料
甲
乙
丙
原料成本（元/千克）
每月限制用量（千克）
A
≥60%
≥15%
2.00
2000
B
5 25 C
≤20%
≤60%
≤50%
1.00
1200
加工费（元/千克）
0.50
0.40
0.30
售价（元/千克）
3.40
2.85
2.25
问该厂每月应生产这三种牌号糖果各多少千克，才能使该厂获利最大?试建立该问题的线性规划模型。
解：设甲糖果中原料 A、B、C 的含量分别为 ；乙糖果中原料 A，B，C 的含量分别为 ，丙糖果中原料 A、B、C 的含量分别为 ，则生产甲糖果千克，乙糖果 千克，丙糖果 ，可建立如下数学模型：
对上式进行整理得到所求问题的线性规划模型：
max z=0.9x 1 +1.4x 2 +1.9x 3 +0.45x 4 +0.95x 5 +1.45x 6 -0.05x 7 +0.45x 8 +0.95x 9
2.11
某厂生产三种产品Ⅰ，Ⅱ，Ⅲ。每种产品要经过 A，B 两道工序加工。设该厂有两种规格的设备能完成 A 工序，它们以 A 1 ，A 2 表示；有三种规格的设备能完成 B 工序，它们以 B 1 ，B 2 ，B 3 表示。产品Ⅰ可在 A，B 任何一种规格设备上加工。产品Ⅱ可在任何规格的 A 设备上加工，但完成 B 工序时，只能在 B 1 设备上加工；产品Ⅲ只能在 A 2 与 B 2 设备上加工。已知各种设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时设备的费用如表 2-18 所示。要求安排最优的生产计划，使该厂利润最大。
表 2-18
设备
产品
设备有效台时
满负荷时的设备费用（元）
Ⅰ
Ⅱ
Ⅲ
A 1
5
10
6 300
A 2
7
9
12
10
321
B 1
6
8
4 250
B 2
4
11
7 783
B 3
7
4000
200
原料费（元/件）
00.35
0.5
单价（元/件）
1.25
2.00
2.80
解：设 为分别用 A 1 ，A 2 加工产品Ⅰ的件数， 分别用 B 1 ，B 2 ，B 3 加工产品Ⅰ的件数； 为分别为用 A 1 ，A 2 加工产品Ⅱ的件数，则 为用 B 1 加工产品Ⅱ的件数； 为用 A 2 及 B 2 加工产品Ⅲ的件数。由题意，可建立数学规划模型：
得：
。即用A 1 加工产品Ⅰ1200 件，用 A 2 加工产品Ⅰ230 件，用 B 1 加工产品Ⅰ0 件，用 B 2 加工产品Ⅰ859 件，用 B 3 加工产品Ⅰ571 件，用 A 1 加工产品Ⅱ0 件，用 A 2 加工产品Ⅱ500 件，用B 1 加工产品Ⅱ500 件，用 A 2 及 B 2 加工产品Ⅲ324 件，可获得最大利润 1147 元。
2.3
考研真题详解 一、判断题 1．线性规划问题的每一个基解对应可行域的一个顶点。（
）（北京交通大学2010 年研）
【答案】× 【解析】基解不一定是可行解，基可行解对应着可行域的顶点。
2．对自由变量 ，通常令 ，其中 ， 在用单纯型法求得的最优解中不可能同时出现 ， 。（
）（暨南大学 2011 年研）
【答案】√ 【解析】因为 ，所以 不能同时为基变量，即至少有一个为 0。故最优解中不可能同时出现 ， 。
3．若 、 分别是某一线性规划问题的最优解，则 也是该线性规划问题的最优解，其中 、 为正的实数。（
）（北京交通大学 2010 年研）
【答案】× 【解析】必须规定 ，且 。当某一线性规划问题存在两个最优解时，则它一定存在无数个最优解，最优解为 。
4．对于一个有 个变量， 个约束方程的标准线性规划 SLP，其基可行解的数目恰好是 个。（
）（暨南大学 2011 年研）
【答案】× 【解析】其基解的个数最多是 个，且一般情况下，基可行解的数目小于基解的个数。
二、选择题 1．单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（
）。（北京交通大学 2010 年研）
A．可控变量
B．环境变量 C．人工变量 D．松弛变量 【答案】D 【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
2．单纯形法中，关于松弛变量和人工变量，以下说法正确的是（
）。（中山大学 2008 年研）
A必须不必0 B．在最后的解中，松弛变量不必为 0，人工变量必须为 0 C．在最后的解中，松弛变量和人工变量都必须为 0 D．在最后的解中，松弛变量和人工变量都不必为 0 【答案】B 【解析】松弛变量不必为 0，而如果人工变量不为 0，则原问题无可行解。
三、计算题 1．某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等有关数据如下：每件产品Ⅰ分别需要劳动力和原材料 6 个小时和 3 公斤，每件产品Ⅱ分别需要劳动力和原材料为 3 小时和 4 公斤，每件产品Ⅲ分别需要劳动力和原材料为 5 小时和 5 公斤；拥有的劳动力和原材料总数分别为 45 小时和 30 公斤；又知Ⅰ、Ⅱ、Ⅲ三种产品的单件利润分别为 3、1、4 元。
要求：（1）写出该厂获利最大的生产计划问题的线性规划模型并求出最优解； （2）写出该线性规划问题的对偶问题，并求对偶问题的最优解； （3）产品Ⅰ的利润在什么范围内变化时，上述最优计划不变？ （4）如果设计一种新产品Ⅳ，单件产品消耗劳动力 8 小时，原材料 2 公斤，每件可获利 3 元，问该产品是否值得生产？ （5）如果劳动力数量不变，原材料可以从市场购买，每公斤 0.4 元，问该厂是否购买原材料来扩大生产，以购买多少为宜？（北京交通大学 2010 年研）
解：（1）设三种产品的产量分别为 。则可建立如下线性规划模型：
将上述线性规划模型化为标准型，并用单纯形法计算如表 2-19 所示：
表 2-19
3
1
4
0
0
C B
X B
b
x 1
x 2
x 3
x 4
x 5
x 4
45
6
3
5
1
0
9
0
x 5
30
3
4
[5]
0
1
6
3
1
4
0
0
x 4
15
[3]
-1
0
1
-1
5
4
x 3
6
3/5
4/5
1
0
1/5
10
3/5
-11/5
0
0
-4/5
3
x 1
5
1
-1/3
0
1/3
-1/3
4
x 3
3
0
1
1
-1/5
2/5
0
-2
0
-1/5
-3/5
于是得到最优解 ，即分别生产Ⅰ、Ⅲ，5 件和 3 件。
（2）上述线性规划问题的对偶问题为：
由 及上述最终单纯形表可知， 。
（3）要保持最优计划不变，即保持各非基变量的检验数非正，则
解得
所以，产品Ⅰ的利润在[2.4，4.8]范围内变化时，上述最优计划不变。
（4）设新产品的产量为 ，则约束矩阵多一个列向量 ，在最终单纯形表中为：
其检验数为 ，故新产品值得生产。
（5）从最终单纯形表可知，原材料的影子价格为 0.6，而其市场价格为 0.4，故可以通过购买原材料来扩大生产。
设购买 ，则
所以 ，即购买 15 公斤时可获得最大效益。
2．现有一求最大值的线性规划问题，对应下列含有未知变量的表（表 2-20），试讨论表中 ， ， ， ， 为何范围值时，表现为表 2-20 所示情况。
表 2-20
（1的解为惟一； （2无穷多最优解之一； （3）表中解为退化的可行解； （4）下一步迭代将以 代替基变量 ； （5具有无界解； （6）该线性规划问题无可行解。（北京理工大学 2008 年研）
解：（1）
且 ， 。
（2）
； ， 或 ， 。
（3）d=0。
（4）
（5）
。
（6）
为人工变量，且 。
3．南京某高校为学生宿舍搭建床架，需要做 100 套钢架，每套用长为 2.9m、2.1m和 1.5m 的圆钢各一根。假设采购到的圆钢长度为 7.4m，请问应该如何下料，使用的原材料最省。请建立线性规划模型。（南京大学 2010 年研）
解：最简单做法是，在每一根原材料上截取 2.9m、2.1m 和 1.5m 的元钢各一根组成一套，每根原材料剩下料头 0.9m。为了做 100 套钢架，需用原材料 100 根，有 90m 料头。若改为用套裁，这可以节约原材料。表 2-21 有几种套裁方案，都可以考虑采用。
表 2-21
为了得到 100 套钢架，需要混合使用各种下料方案。设按 I 方案下料的原材料根数为 ，Ⅱ方案为 ，Ⅲ方案为 ，Ⅳ方案为 ，Ⅴ方案为 。根据表 2-21 中的方案，列出以下数学模型：
第 第 3 章
对偶理论与灵敏度分析 3.1
复习笔记 1．单纯形法的矩阵描述 设线性规划问题为 。在该线性规划问题的约束条件中加入松弛变量 后，得到标准型：
。该标准型的矩阵表示为：
目标函数：
约束条件：
非负条件：
其中 B，N 分别表示对应基变量、非基变量的系数矩阵。
进一步分析可得到：
， 。
令非基变量 ，可得到一个基可行解 ，这时目标函数 。
注意：重点要搞清楚哪些是行向量，哪些是列向量， 为列向量， 为行向量。
2．单纯形表与矩阵表示的关系 上述基可行解、目标函数的表达式可改写为如表 3-1 所示的矩阵列表：
表 3-1
基变量 X B
非基变量 X N
等式右边 RHS
系数矩阵
B -1 B=I
B -1 N
B -1 b
检验数
C B -C B B -1 B=0
C N -C B B -1 N
-C B B -1 b
3．原问题与对偶问题之间的关系
原问题的标准形式：
对偶问题的标准形式：
线性规划的原问题与对偶问题的关系，其变换形式可归纳如表 3-2 所示：
表 3-2
记忆方法：
极大化转化为极小化，变不反约反；极小化转化为极大化，变反约不反。
注：变指变量，约指约束条件。反指大于变小于，小于变大于。不反指大于变大于，小于变小于。注意等号总是变无约束，无约束总是变等号。
4．对偶问题的基本性质 （1）对称性：对偶问题的对偶是原问题。
（2）弱对偶性：若 是原问题的可行解， 是对偶问题的可行解。则存在 。
注意，由弱对偶性可以推出：
①max 问题任一可行解的目标值为对偶 min 下界； ②min 问题任一可行解的目标值为对偶 max 问题目标值的一个上界。
（3）无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
注：这个问题的性质不存在逆命题。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。
（4）可行解是最优解时的性质：设 是原问题的可行解， 是对偶问题的可行解，当， 是最优解。
（5）对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。
要记住一点：原问题、对偶问题均存在可行解，则存在最优解。
（6）互补松弛性：若 分别是原问题和对偶问题的可行解。那么 和 ，当且仅当 为最优解。
（7）设原问题是 ，它对应的对偶问题是 ；
，则原问题单纯形表的检验数行对应其对偶问题的一个基解。
记忆方法：
①非最优，检验数的负值为对偶问题的一个基解。
②原问题最优，检验数的负值为对偶问题的最优解。
③原问题检验数行，其松弛变量的检验数的绝对值对应其对偶问题的各个变量的解。
5．对偶问题的经济解释——影子价格 （1）影子价格的定义 设 B 是 的最优基，则 。由此求偏导数得：
变量 的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数最优值的变化。
的值代表对第 种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。
（2）影子价格的经济意义 影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于该企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。
要记住：市场价格低于影子价格，可以买进（然后用灵敏度分析进行计算），若市场价格高于影子价格，不买进。
6．对偶单纯形法 对偶单纯形法的思想：在单纯形表中进行迭代时，在 b 列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，此时已得到最优解。根据对偶问题的对称性，也可以这样考虑：若保持对偶问题的解是基可行解，即 ，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。
对偶单纯形法的计算步骤如下：
（1）对线性规划问题进行变换，使列出的初始单纯形表中所有检验数 ，，即对偶问题为基可行解。
（2）检查 b 列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查 b 列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。
（3）确定换出变量 按 对应的基变量 为换出变量。
（4）确定换入变量 在单纯形表中检查 所在行的各系数 。若所有 ，则无可行解，停止计算。若存在
，计算
按 规则所对应的列的非基变量 为换入变量，这样才能保持得到的对偶问题解仍为可行解。
（5）以 为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。
重复步骤（2）～（5）。
注意：
（1）对偶单纯形法不是解对偶问题的单纯形法，而是应用对偶原理求解原问题最优解的一种方法。当然，当求解得到原问题的最优解的同时，也就得到了其对偶问题的最优解。
（2）在具体计算中，不另外构造单纯形表格，而是在原问题的单纯形表格基础上进行对偶处理。
对偶单纯形法的特点：
（1）简化计算。不需引入人工变量将线性规划化成标准型，构造初始单纯形表（初始解是非可行解），只要检验数非正（最优检验数），就可以进行基的转换。
（2）适于变量多于约束条件情形，当变量少于约束方程的个数时，可考虑变成对偶问题后，再用对偶单纯形法求解。
（3）局限性：多数问题很难找到检验数为负（最优检验数）的初始可行解。但可用于灵敏度分析中以简化计算。
7．灵敏度分析 灵敏度分析主要研究两个问题：
（1）当线性规划问题的系数 中有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。
（2）若当线性规划问题的系数中有一个或几个发生变化时，已求得的线性规划问题的最优解不再是最优解时，如何用最简单的办法找到新的最优解。
灵敏度分析可能遇到的情况及其处理方法如表 3-3 所示：
表 3-3
原问题
对偶问题
结论或继续计算的步骤
可行解
可行解
非可行解
非可行解
可行解
非可行解
可行解
非可行解
表中的解仍为最优解
用单纯形法继续迭代求最优解
用对偶单纯形法继续迭代求最优解
引进人工变量，编制新的单纯形表，求最优解
各类灵敏度分析：
（1）资源数量 的变化分析 当其他系数不变，仅资源数量 发生变化，即 时。
若 的变化范围为 ，最优基不变，最优解的值发生变化，求出变化后的最优解即可。其中， 。
若 的值超出上述范围，则据此求得的最优基为不可行解，但由于 的变化不影响检验数，故所有的检验数仍满足 ，即满足对偶可行性。因此，需要在最终单纯形表的基础上换上新的右端项，利用对偶单纯形法继续迭代求最优。
（2）目标函数中价值系数 的变化分析 ①若 是非基变量 的系数，它所对应的检验数是 ，当 变化 后，其所对应的检验数变为 ，若 则 ，已求得的最优解仍为最优解，否则继续采用单纯形法进行迭代直至求得最优解。
②若 是基变量 的系数。因 ，当 变化 时，就引起 的变化。若 满足：
，则已求得的最优解仍为最优解；否则，需将原最终单纯形表换上变化后的价值系数和检验数，继续迭代计算直至求得最优解。
（3）技术系数 的变化分析 ①增加一个决策变量 。首先计算变化后的检验数 以及。若 ，则原最优解不变；若 ，则按单纯形法继续迭代计算至最优。
②原决策变量 的技术系数 变化。若变量 在最终单纯形表中为非基变量，分析步骤参考情况①；若变量 在最终单纯形表中为基变量，其技术系数 变化将使相应的和 发生变化，有可能出现原问题和对偶问题均为非可行解的情况，此时，需要引入人工变量先将原问题的解转化为可行解再用单纯形法求解。
（4）新增加一个约束条件的分析 增加一个新的约束条件的分析方法是先将原问题最优解的变量值代入新增的约束条件，如满足，则原最优解不变。否则，将新增的约束条件直接反映到最终单纯形表中再进一步分析。
8．参数线性规划 参数线性规划是研究 中某一参数连续变化时，使最优解发生变化的各临界点的值。仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：
（1）对含有某参变量 t 的参数线性规划问题。先令 t=0，用单纯形法求出最优解； （2）用灵敏度分析法，将参变量 t 直接反映到最终表中（注意看清 t 的变化范围，然后看清楚是 b 列变化还是 c 行变化）； （3）当参变量 t 连续变大或变小时，观察 b 列和检验数行各数字的变化。若在 b 列首先出现某负值时，则以它对应的变量为换出变量；用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则以它对应的变量为换入变量，用单纯形法迭代一步； （4）在经迭代一步后得到的新表上，令参变量 t 继续变大或变小，重复步骤（3），直到 b 列不再出现负值，检验数行不再出现正值为止。
3.2
课后习题详解 3.1
用改进单纯形法求解以下线性规划问题。
（1）
解：在上述线性规划的约束条件中分别引入松弛变量 ，并化为标准型：
得到初始基 ，初始基变量 ，对应的系数 ；非基变量，对应的系数 。非基变量的检验数，则 为换入变量。
，所以对应的换出变量为 。
由此得到新的基 、基变量 及系数 、非基变量 及系数 分别为：
，
计算换入变量 的系数向量 及 为：
计算非基变量的检验数为：
由 可确定 为换入变量，再由 知 为换出变量。
得到新的基 、基变量 及系数 、非基变量 及系数 分别为：
计算换入变量 的系数向量 及 为：
， ，
非基变量的检验数向量为 。
此时，非基变量的检验数均为负，最优解为 即，最优目标函数值为 。
（2）
解：在第二个约束条件中减去剩余变量 ，再分别在第一、二个约束条件中加入人工变量 ，在第三个约束条件中加入松弛变量 ，得该线性规划的标准型：
得到初始基 ，初始基变量 ，对应的系数 ；非基变量 ，对应的系数 。非基变量的检验数 ，则 为换入变量。
，所以对应的换出变量为 。
由此得到新的基 、基变量 及系数 、非基变量 及系数 分别为：
， ， ， ，
计算换入变量 的系数向量 及 为：
计算非基变量的检验数为：
由 可确定 为换入变量，再由 知 为换出变量。
得到新的基 、基变量 及系数 、非基变量 及系数 分别为：
，
计算换入变量 的系数向量 及 为：
非基变量的检验数向量为
因为非基变量的检验数均大于 0，故问题的最优解为:
最优目标值为 。
3.2
已知某线性规划问题，用单纯形法计算时得到的中间某两步的计算如表 3-4 所示，试将表中空白处数字填上。
表 3-4
解：先求 ，由上表中的上一部分知
所以 ，解得
再求 ：
表中空缺的系数矩阵为迭代后的基变量对应的系数，所以表 3-4 中要填写的数字如表3-5 所示：
表 3-5
3.3 写出下列线性规划问题的对偶问题，再写出对偶问题的对偶，并验证其即为原问题。
（1）
解：设对应于各约束条件的对偶变量为 ，则其对偶问题为：
则其对偶问题的对偶问题为：
易知其与原问题等价。
（2）
解：设对应于各约束条件的对偶变量为 ，则其对偶问题为：
则其对偶问题的对偶问题为：
其与原问题等价。
（3）
解：设对应于各约束条件的对偶变量为 ，则其对偶问题为：
则其对偶问题的对偶问题为
其与原问题等价。
（4）
解：设对应于各约束条件的对偶变量为 ，则其对偶问题为：
则其对偶问题的对偶问题为
其与原问题等价。
3.4
判断下列说法是否正确，为什么? （1原问题存在其对偶问题也一定存在可行解； （2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；
（3）如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。
解：（1）错误。线性规划的原问题存在可行解，其对偶问题不一定存在可行解。当原问题存在可行解，且是无界解时，对偶问题无可行解。
例：对于线性规划问题
易知该线性规划问题存在可行解，如 ，该问题的对偶问题为
由第三个约束条件知，对偶问题无可行解。
（2）错误。当线性规划问题的对偶问题无可行解时，原问题可能具有无界解或者是无可行解。
（3）错误。当线性规划的原问题和对偶问题都具有可行解时，该线性规划问题可能存在有限最优解，也可能存在无界解。
3.5
设线性规划问题 1 是
（ ）是其对偶问题的最优解。
又设线性规划问题 2 是
其中 是给定的常数，求证 。
证明：问题 1 的矩阵表示为
设 为它的一个可行解，其对偶问题的最优解为 。
问题 2 的矩阵表示为
其中 。
设 为它的一个可行解，其对偶问题的最优解为 。
问题 1 的对偶问题为
问题 2 的对偶问题为
由此可知，问题 1 的对偶问题与问题 2 的对偶问题有相同的约束条件，所以问题 1的对偶问题的最优解 一定是问题 2 的对偶问题的一个可行解。
又因为 是问题 2 对偶问题的最优解，所以，
因为原问题与对偶问题的最优值相等，所以
3.6
已知线性规划问题 max z=CX，AX=b，X≥0，分别说明发生下列情况时，其对偶问题的解的变化：
（1）问题的第 k 个约束条件乘上常数 λ（λ≠0）； （2）将第 k 个约束条件乘上常数 λ（λ≠0）后加到第 r 个约束条件上； （3）目标函数 max z=λCX（λ≠0）； （4）模型中 X=（x 1 ，x 2 ，…，x n ）
T ，用 X"=（3x" 1 ，x 2 ，…，x n ）
T 代换。
解（1）因为对偶变量 Y=C B B -1 ，第 k 个约束条件乘上 λ（λ≠0），即 b -1 的 k 列将为变化前的 ，则对偶问题变化后的解为 。
（2）与前类似，对偶问题变化后的解为 。
（3 （i=1，2，…，m）。
（4）对偶问题变化后的解为 （i=1，2，…，m）。
3.7
已知线性规划问题
用单纯形法求解，得到最终单纯形表如表 3-6 所示：
表 3-6
（1）求 的值； （2）求 的值。
解：（1）由题意可设初始单纯形表的增广矩阵为
最终单纯形表的增广矩阵为
对矩阵 作初等行变换，使其第 4，5 列组成单位矩阵
由单纯形运算法则可知， ， 所以， 。
（2）由检验数的计算式可知
求解上述方程组得：
。
3.8
已知线性规划问题
其对偶问题的最优解为 ，试应用对偶问题的性质，求原问题的最优解。
解：原问题的对偶问题为
将 分别代入对偶问题的各约束条件中，可知，式①和式②为严格不等式，由互补松弛性可知 。又因为 ，所以根据互补松弛性知，原问题的两个约束条件应取等号，即
解得， 。于是原问题的最优解为 ，最优目标函数值为 。
3.9
试用对偶单纯形法求解下列线性规划问题。
（1）
解：在两个约束条件两边同乘以-l，再分别加入松弛变量 得到如下形式
列出初始单纯形表，并利用对偶单纯形法进行求解，求解过程如表 3-7 所示：
表 3-7
得线性规划问题的最优解为 ，目标函数值为 。
（2）
解：先将上述线性规划问题化成如下形式，以便得到对偶问题的初始可行基
建立此问题的初始单纯形表，并利用对偶单纯法进行计算，如表 3-8 所示：
表 3-8
c j
-3
-2
-1
-4
0
0...
相关热词搜索： 运筹学 笔记 课后