第1章 线性规划
本章介绍了什么是线性规划，线性规划数学模型的概念及其建立数学模型方法；阐述了线性规划的图解法、解的概念及解的形式；详细介绍了普通单纯形法、人工变量单纯形法及单纯形法计算公式。 1．考核知识点
（1） 基本概念：数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法。 （2） 建立简单的线性规划数学模型。 （3） 求解线性规划的图解法。 （4） 基、可行基及最优基的定义。
（5） 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。 （6） 有唯一解、有无穷多解、无界解、无可行解的判断。 （7） 求解线性规划的单纯形法。 （8） 求解线性规划的人工变量法。 （9） 单纯形法中的5个计算公式。 2．学习要求
（1） 深刻领会线性规划的各种基与解的基本概念，它们之间的相互关系。
（2）掌握图解法的计算步骤，注意怎样将目标函数表达成一条直线，这条直线如何平移使得目标函数值上升或下降。
（3） 熟练掌握单纯形法计算的全过程，特别应注意如何列出单纯形表，如何由一个基可行解换到另一个基可行解，基可行解是最优解、无界解或多重解的判断准则。
（4） 理解在什么情况下加入人工变量，人工变量起何作用，用大M法计算时目标函数的变化，两阶段法计算时目标函数的构成，掌握这两种计算方法的全过程，在什么情形下线性规划无可行解。 （5） 理解用矩阵形式代替单纯形表，并用矩阵公式求解线性规划。 3．重点
建立线性规划数学模型，有关线性规划解的概念、解的形式，单纯形法计算、大M法、两阶段法。
4．难点解析
（1）建立线性规划数学模型
建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。 （2）图解法
图解法要掌握好3个步骤：画出满足每个约束的区域，其交集就是可行域；画出目标函数增加的矢量，与矢量垂直的直线就是目标函数直线；将目标函数直线平行移动到可行域，如果求最大值就沿着矢量方向平移到可行域的边界，如果求最小值就沿着矢量的反方向平移到可行域的边界，直线与可行域边界的交点对应的坐标就是最优解，如果交点无界，则线性规划无界解。
（3）线性规划有关解的关系
要掌握解的关系首先要理解解的概念。例如，要判断“可行解是基本解”这个命题的正确性，就应知道可行解和基本解的定义，然后分析两者之间的关系。可行解的定义是满足所有约束的解，包括等式约束、变量非负约束，基本解是令非基变量等于零、基变量满足等式约束的解，可行解没有区分基变量和非基变量，基本解不一定满足变量非负条件。因此，两个解没有必然的包含关系，可以理解为一个解可能包含也可能不包含另一个解。由此，该命题是错错误的。
（4）单纯形法
第一章讲的所有方法统称为单纯形法，其中分不加人工变量的普通单纯形法和加人工变量时的大M单纯形法、两阶段单纯形法。通常对不加人工变量能通过观察找到一个可行基，列出单纯形表计算的方法，称为普通单纯形法，而不能观察找到可行基，只能通过加入人工变量寻找原问题的可行基的计算方法，称为人工变量法，具体地是大M单纯形法和两阶段单纯形法，人工变量法是帮我们寻找原问题的一个可行基，当基变量全部是原问题的变量时，人工变量的任务也就完成，退出单纯形表。大M单纯形法和两阶段单纯形法是将人工变量作为过渡变量，是一种技术处理，两种方法没有本质区别。
5．考核目标
（1）识记有关基本概念、定义及公式。
（2）掌握求解线性规划的单纯形法、人工变量法。 （3）理解不同算法的条件和过程。
第2章 线性规划的对偶理论
本章介绍了对偶问题的经济含义及有关对偶理论，阐述了原问题与对偶问题的对应关系，对偶单纯形法，灵敏度分析的基本思想及具体方法。 1．考核知识点
(1)基本概念：对偶变量、对偶模型、对偶问题与原问题的模型关系、对偶问题与原问题解的对应关系、可行性条件、最优性条件、对偶单纯形法的条件、灵敏度分析、参数的变化、影子价格。 (2)由一个已知的线性规划写出它的对偶线性规划。 (3)原问题与对偶问题的模型对应关系。 (4)原问题与对偶问题解的对应关系。 (5)对偶单纯形法求解线性规划。
(6)参数Cj及bi在什么范围内变化时最优解不变或最优基不变的计算方法。 (7)当参数或条件发生变化时利用灵敏度分析方法求最优解。 (8)影子价格的经济含义及其应用的理解。 2．学习要求
(1)理解对偶问题的产生，掌握写出对偶问题的方法。
(2)深刻领会对偶性质，从几个定理中了解原问题与对偶问题有关解的对应关系。 (3)领会互补松弛定理，掌握由一个问题的最优解求出另一个问题最优解的方法。 (4)了解对偶单纯形法的应用条件，掌握用对偶单纯形法求解线性规划的运算。 (5)了解灵敏度分析的内容及其作用，掌握具体分析方法。
3．重点
写对偶模型，对偶性质，影子价格，对偶单纯形法，灵敏度分析。
4．难点解析
(1)对偶问题与原问题解的对应关系 首先掌握规范型对偶模型的对应关系，即
maxz=CX⎧AX≤b⎨
⎩X≥0
⇔
minw=Yb⎧YA≥C⎨
⎩Y≥0
式中：Y的符号“≥”由约束AX ≤b中的“≤”符号决定；反之，约束AX ≤b中的“≤”符号由Y的符号“≥”来决定。
式中：约束YA ≥C中的“≥”符号由X的符号“≥”决定，X的符号“≥”由约束YA ≥
C的“≥”符号来决定。
关键口诀：对偶问题约束符号由原问题变量符号确定，对偶问题变量符号由原问题约束符号确定。 非规范型模型的对偶关系关键在这里的“非”字，由规范型的定义，对于极大值模型，这里的“非”无非有4个方面:
①约束条件是“≥”符号 ②约束条件是“＝”符号 ③变量x≤0 ④变量x无约束
4种非规范形式就是原问题符号不满足定义，其对偶问题的符号也就不满足定义，对应关系是： ②约束条件是“＝”符号 ⇒对偶变量y无约束
④变量x无约束 ⇒对偶约束是“＝”符号
同理，若原问题是求极小值，非规范形式的对应关系是： ①约束条件是“≤”符号 ⇒对偶变量y≤0 ③变量x≤0 ⇒对偶约束是“≥”符号 ④变量x无约束 ⇒对偶约束是“＝”符号
参看下例对应关系。 ②约束条件是“＝”符号 ⇒对偶变量y无约束 ③变量x≤0 ⇒对偶约束是“≤”符号 ①约束条件是“≥”符号 ⇒对偶变量y≤0
(2)对偶性质
对偶性质主要研究原问题与对偶问题解的对应关系。学习对偶性质主要掌握下例有关结论。 ①互为对偶的两个问题要么都有最优解，要么都没有最优解。 ②一个问题无界，另一个问题不可行。
③一个问题无可行解，另一个问题可能无可行解，也可能有可行解(这时一定具有无界解)。 ④极大值问题的目标值不超过极小值问题的目标值。 ⑤两个问题都有可行解，则都有最优解。
⑥如果有最优解，则最优值相等。注意，不是最优解相等。 ⑦已知原问题最优基B，则对偶问题的最优解为Y＝CBB－1。
⑧一个问题的松弛变量大于零，另一个问题的决策变量等于零，一个问题的决策变量大于零，另一个问题的松弛变量等于零。注意，一个问题的松弛变量（决策变量）等于零，另一个问题的决策变量（松弛变量）不一定大于零。
⑨对于规范形式模型，极大值问题松弛变量的检验数乘以“－1”后是其对偶问题决策变量的基本解，决策变量的检验数乘以“－1”后是其对偶问题松弛变量的基本解。对于极小值问题则不乘以“－1”。
⑩对于资源约束，影子价格就是对偶变量的最优解，当某种资源有剩余（松弛变量大于零）时，对应的影子价格等于零。
（3）影子价格
yi=
影子价格是对偶理论中一个非常重要的概念。由公式知，影子价格是资源对目标值的边际贡献，不仅是随着bi变化而变化，而且还与其它资源量的变化有关。影子价格不等于市场价格，但与市场价格有关。
（4）对偶单纯形法
对偶单纯形法是求原问题最优解的一种特殊方法，而不是直接求对偶问题的最优解。单纯形法的条件是原问题初始解可行，对偶单纯形法的条件是对偶问题初始解可行，由性质2.6知，对偶问题初始解可行
∂Z∂bi
就是满足初始单纯形表的检验数非正（极小值时非负）。因此，对偶单纯形法的求解对象是原问题不可行而对偶问题可行的线性规划模型。
对偶单纯形法是先选出基变量后选进基变量，顺序与单纯形法相反；比值规则是检验数与出基行的负数求比值后的绝对值取最小。
如果最小比值不存在，说明原问题无可行解，对偶问题无界解。
因为对偶单纯形法的条件是对偶问题可行，因此对偶单纯形法不可能出现原问题无界解。
（5）灵敏度分析
对线性规划进行灵敏度分析的难点主要是分析参数变化后最优单纯形表中哪些数据会发生变化，变化后又如何求解。
①用单纯形法5个计算公式分析。参数cj变化后，单纯形表中检验数发生变化；参数bj变化后,基变量（常数项）的值发生变化；参数aij变化后,j列的系数（包括检验数）发生变化，如果aij是基矩阵的元素，则整个单纯形表会发生变化。
②多个参数组合变化。掌握某个参数变化分析，就能分析多个参数一起变化情形。例如，cj、bj同时变化，则检验数和常数都发生变化。增加或减少约束条件、变量也属于这种情形。
③变化后的分析。单纯形表变化后有4种情形：
第一种是满足最优性，得到最优解；注意，最优解可能变化；
第二种情形是原问题可行对偶问题不可行（λj>0及bi≥0）,这时用单纯形法继续求解；，这时用对偶单纯形法求解； 第三种情形是对偶问题可行原问题不可行（λj≤0及bi＜0）第四种情形是原问题和对偶问题都不可行（λj>0及bi＜0）,这时需要加入人工变量寻求初始基可行解，用大M法或两阶段法求解。
5．考核目标
(1)识记有关基本概念、定理结果。
(2)写对偶问题，理解对偶变量的经济含义及其应用。 (3)运用对偶单纯形法求解线性规划。 (4)灵敏度分析方法及其用
第3章 整数规划
本章介绍了整数规划的类型及数学模型，阐述了求解整数规划的分枝定界法、割平面法及0－1规划的隐枚举法。 1.考核知识点
（1）基本概念：纯整数规划、混合整数规划、背包问题、固定费用、可变费用、Gomory切割方程、分枝、定界、隐枚举法。
(2)各类整数规划数学模型的特征、建立及应用。
(3)求解整数规划的分枝定界法。 (4)求解整数规划的割平面算法。 (5)求解0－1整数规划的隐枚举算法。 2．学习要求
(1)了解整数规划数学模型及其解的特点。
(2)通过投资决策、固定成本及多重约束的选择等实例，提高对整数规划的应用能力。 (3)掌握分枝定界法的计算，注意如何分枝和剪枝，解的判断。 (4)掌握割平面法求解的运算过程，求Gomory切割方程。 (5)理解隐枚举法的基本思路，掌握整个运算过程。
3.重点
建立整数规划数学模型，分支定界法，割平面法，隐枚举法。
4.难点解析
（1）0-1变量的运用
右端常数是k个值中的一个时，约束条件为
n
k
k
∑a
j=1
ij
xj≤∑biyi，
i=1
∑y
i=1
i
=1
m组条件中有k（≤m）组起作用时，约束条件写成
n
k
∑a
j=1
ij
xj≤bi+Myi，
∑y
i=1
i
=1
这里yi=1表示第i组约束不起作用，yi=0表示第i个约束起作用。当约束条件是“≥”符号时右端常数项应为
bi−Myi,下同。
对于m个条件中有k（≤m）个起作用时，约束条件写成
n
k
∑a
j=1
ij
xj≤bi+Myi，
∑y
i=1
i
=m−k
（2）分枝定界法
分枝定界法求解整数规划要比单纯形法求解线性规划复杂得多，尤其变量较多的大型整数规划问题，人工计算几乎不可行。对于变量较少的整数规划问题，分枝定界法还是一种有效方法。 所谓分枝，是对非整数变量的取值加以限制，将一个线性规划分成两个线性规划。
所谓定界，当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。
分枝定界法关键是如何掌握“分枝”和“定界”，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。
(3)割平面算法
割平面法的关键是求Gomory切割方程。设xi不为整数，变量。
xi+∑aikxk=bi
k
， xk为非基
将
bi及aik分离成一个整数与一个非负真分数之和
bi=[bi]+fi,
则有
aik=[aik]+fik，0 k k xi−[bi]+∑[aij]xk=fi−∑fikxk k k 上式两边都为整数,则有 fi−∑fikxk≤fi<1 k fi−∑fikxk≤0 k 加入松弛变量si(非负整数)得 si−∑fikxk=−fi k 上式称为以xi行为源行（来源行）的割平面，或分数切割式，或高莫雷约束方程。将高莫雷约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。 (4)求解0－1整数规划的隐枚举算法 隐枚举法是枚举法的一种特殊求解方法，是枚举法的一种改进方法。计算量取决于初始可行解的目标值的大小。计算过程中，可以对初试目标值进行动态移动，以减少检验约束条件的工作量。 5．考核目标 (1)识记有关基本概念。 (2)建立有关整数规划的数学模型。 (3)求解整数规划的割平面法和分枝定界法。 (4)求解0－1整数规划的隐枚举法。 第4章 目标规划 本章介绍了线性目标规划的基本概念和数学模型，阐述了相同等级、优先等级和赋权优先等级目标规划的图解法和单纯形法。 1.考核知识点 (1)基本概念：目标、优先等级、赋权、正偏差变量、负偏差变量、系统约束、目标约束、满意解、单纯形表。 (2)偏差变量的含义及其设置。 (3)恰好达到、不超过和不低于目标值三种情形下目标函数的表示方法。 (4)有优先等级和有赋权优先等级情形下目标函数的表示方法。 (5)系统约束和目标约束的区别及其正确表达。 (6)两个决策变量的目标规划的图解法。 (7)求解目标规划的单纯形计算方法。 2．学习要求 (1) 理解目标规划的特征及其应用，目标规划与线性规划的区别。 (2) 理解偏差变量的含义和用途。 (3) 掌握目标函数的表达方式，正确列出约束条件，建立数学模型。 (4) 运用单纯形法求解目标规划，注意检验数的表达及满意解的检验标准。 3.重点 建立目标规划数学模型，图解法，单纯形法 4.难点解析 (1)正负偏差变量与目标函数 目标规划模型除了有决策变量外，还有非负的偏差变量，正是模型中有了偏差变量才有目标规划。偏差变量是用来调节约束条件的，当一个约束条件中包含了一对偏差变量时，则这个约束条件就是一个平面（或超平面）。以两个变量为例，约束条件 2x1+x2+d−−d+=4 是一个平面，对x1和x2没有任何约束，因为x1和x2取任意值都满足条件。如果没有对两个偏差变量进行限制，其约束条件也就没有任何意义。目标规划模型往往与约束条件一起伴随着有一个求最小值的目标函数，这个函数就是决策者的期望。这时x1和x2就不能任意取值。当 d−=0时，有2x1+x2≥4是半个平面；当 d＋=0时，有2x1+x2≤4是另外半个平面； −+ 当 d=d=0时，有2x1+x2=4是一条直线。 决策者的期望有3个方面： − 第一，期望2x1+x2的值不低于4，取目标函数minZ=d + 第二，期望2x1+x2的值不超过4，取目标函数minZ=d −+2x+xminZ=d+d12第三，期望的值恰好等于4，取目标函数 一次决策中，3个期望只能取其中之一，并且不能直接令偏差变量等于0。例如第一个期望中，令 d−=0，其含义是2x1+x2≥4，是一个硬约束，不允许2x1+x2<4。而目标规划是允许有偏差的， 2比4小，但又不能小得太多，即 d不能太大，因此有目标函数minZ=d。 即允许1 （2）图解法 目标规划的图解法比线性规划要复杂一点点。这一点点就是约束中多了两个偏差变量。图解法的关键是掌握如何将约束中的两个偏差变量在坐标中表示清楚。如图（1）所示。 2x+x −− 图（1） 直线将平面分割成两部分，箭头所指的区域表示当X取值这个区域时 d或d大于零，而不是 d或d的取值区域。 （3）单纯形法 目标规划的单纯形法与线性规划比较主要有两点不同。 第一，目标规划是按优先次序顺序求解，逐个满足最优（检验数大于等于零）； 第二，不一定所有检验数都能满足大于等于零，如果某个检验数小于零，所在列存在检验数大于零时，则认为得到满意解。 计算方法和基本原理与线性规划类似。 5．考核目标 (1) 识记有关基本概念。 (2) 建立目标规划数学模型。 (3)目标规划的求解运算方法。 − + − + 第5章运输与指派问题 本章介绍了运输问题数学模型的建立，平衡与不平衡运输问题最优解的求解方法，指派问题的数学模型及其求解运算。 1.考核知识点 (1) 基本概念：运输模型、表上作业法、闭回路、基变量、最小元素法、Vogel近似法、闭回路法、位势法、调整量、指派模型、匈牙利法、效率矩阵。 (2) 建立运输问题的数学模型。 (3) 基变量数与产地、销地数之间的关系。 (4) 表上作业法求解运输问题(max, min)的运算过程。 (5) 不平衡问题转化为平衡问题。 (6) 建立指派问题的数学模型。 (7) 匈牙利法求解指派问题的运算过程。 2.学习要求 (1) 理解运输问题数学模型的构成及其特征，变量数、约束数、产地数、销地数、基变量数之间的关系。 (2) 掌握表上作业法的基本步骤，包括求初始基可行解和检验数、最优解的判断和运量的调整。 (3) 掌握当产大于销或销大于产时，将其转化为平衡问题并求解的方法。 (4) 了解指派问题是整数规划的一种特殊规划，它的求解可以用一种特殊方法—匈牙利法。熟练掌握匈牙利法的原理及其运算方法。 3.重点 运输问题与指派问题的模型及其特征，运输单纯形法，匈牙利法 4.难点解析 （1）运输模型的特征与性质 运输问题的数学模型的特征有：具有m个产地n个销地的平衡运输模型有mn变量，m+n个约束。 运输问题的基本性质 ① 任何运输问题都存在可行解和最优解 ② m个产地n个销地的平衡运输问题的基变量个数:m+n-1 ③ m+n-1个变量构成一组基变量的充要条件是它们不包含任何闭回路 ④ 产量与销量均为整数的运输问题必存在整数最优解 （2）运输单纯形法 运输单纯形法或称表上作业法，一般分为3个步骤。 第一步，求初始基本可行解（初始方案）。其方法很多，常用的有最小元素法、Vogel近似法、西北角法。 第二步，求检验数，用闭回路法和位势法 这里的闭回路是以某个非基变量为起点，以基变量为其它顶点组成的闭回路。位势法是用公式求解，先求位势再求检验数。 对应关系：运输问题的位势是对偶问题的对偶变量，运输问题的检验数是对偶问题的松弛变量。 第三步，调整运量，用闭回路法。确定进基变量、确定出基变量、调整运量。 检验数的含义：检验数λij表示变量xij增加一个单位时目标函数的改变量。因此，当检验数全部大于等于零时得到最优解（min）。 （3）运输模型的变异 运输模型有3种变异：不平衡问题、需求量不确定问题、极大值问题。都可以这3种变异转化为基本运输模型（平衡、求极小值），然后用运输单纯形法求解，但极大值问题也可以不必要转化为极小值，直接改变检验数的判断标准即可。 （4）匈牙利法 匈牙利法的条件：平衡（人数与工作数相等）、求极小值及效率非负3个条件。求解方法的基本思想是基于两个定理。 第一个定理告诉我们如何将效率表中的元素转换为有m个独立的零元素的方法，第二个定理告诉我们效率表中有多少个独立的“0”元素判别方法． 如果指派问题不满足匈牙利法的条件，则先转化再求解。 5．考核目标 (1) 识记有关基本概念、定理结果。 (2) 掌握求解各种运输模型，包括平衡与不平衡问题。 (3) 运用匈牙利法求解指派问题。 第6章网络模型 本章介绍了图的基本概念及图的几个极值问题。阐述了最小支撑树的Kruskal算法和Prim算法，最短路的Dijkstra算法和Floyd算法，最大流的Ford-Fulkerson标号算法，旅行售货员问题。 1．考核知识点 (1) 树、支撑树、最小支撑树、赋权有向图、网络、最短链、最短路、容量、流量、可行流、最大流、前向弧、后向弧、增广链、截集、截量。 (2) 最小支撑树的应用及其两种算法。 (3) 最短路的Dijkstra算法和Floyd算法。 (4) 网络最大流的Ford-Fulkerson算法。 2．学习要求 (1) 了解图论中图的定义及其有关的基本概念。 (2) 掌握求最小支撑树的两种算法。 (3) 掌握求最短路的Dijkstra算法。 (4) 掌握求网络最大流的基本步骤及标号算法。 3．重点 求最小支撑树，求最短路，求最大流。 （1） 最小支撑树的应用及其两种算法。 （2） 网络最大流的Ford-Fulkerson算法。 4.难点解析 （1）最短路的Dijkstra算法和Floyd算法 Dijkstra算法是一种在网络图上标号算法。关键掌握两个标号的含义，一个是点的标号b(i)，其含义是从图的发点开始到点vi的最短路长，另一个是边的标号k(i,j)，其含义是点vi的标号加上边(i,j)的长度，是用来寻找下一个标号是在哪个点的依据。Dijkstra算法对求两点间的最短路和具有正权网络图问题简单有效，对于任意两点和含有负权的最短路问题的计算，Dijkstra算法不是一种有效的算法。 Floyd算法是一种通用算法，用来求任意两点包括含有负权的最短路的一种迭代算法，通常用“距离矩阵”迭代，看起来该方法很复杂，其实非常有规律，并且很容易在计算机上实现。 （2）网络最大流的Floyd－Fulkerson算法 Floyd－Fulkerson算法的主要步骤是求增广链，如果存在从发点到收点的增广链，说明网络还能增加流量，否则已达到最大流。 求增广链是通过标号实现的，标号过程中关键要分清楚前向弧和后向弧，因为它们的标号方法不一样。前向弧的标号是cij-fij>0,后向弧上的标号是fij>0。 如果对所有点都标号，找到增广链后求调整量，只有增广链上的标号有用。因此，标号可以只沿着一条路向收点进行，当中途发生“此路不通”时再回头走其它路线，这样可以节省计算量。 5.考核目标 (1)识记有关基本概念、定理结果。 (2) 掌握3种网络模型的求解方法。 有关说明与实施要求 1.考试方式 闭卷、笔试，时间为120分钟 2.题型结构（1）填空题 （2）判断题 （3）单项选择题 （4）计算题 （5）综合应用题 3.难度结构 本课程考试主要测试学生对运筹学的基本概念、基本原理和基本算法的理解、掌握程度，运用这些基础知识分析问题和建立管理中简单的数学模型和运算能力。其中较易的占30％，中等难度的占30％，较难的占25％，难的占15％。 4．采用百分制，60分为及格。 因篇幅问题不能全部显示，请点此查看更多更全内容