第一部分线性规划问题的求解。
—重要算法：**法、单纯形迭代、大m法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，最小元素法；最优性检验：
闭回路法，位势法；）、目标规划：**法、整数规划：分支定界法（次重点），匈牙利法（重点）、
第二部分动态规划问题的求解。
—重要算法：图上标号法。
第三部分网络分析问题的求解。
—重要算法：破圈法、tp标号法、寻求网络最大流的标号法。
第一部分线性规划问题的求解。
一、两个变量的线性规划问题的**法：
概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
**法：**法采用直角坐标求解：x1——横轴；x2——竖轴。
1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在a、b、c三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
此题也可用“单纯形法”或化“对偶问题”用大m法求解）
解：设x1、x2为生产甲、乙产品的数量。
max z = 70x1+30x2
可行解域为oabcd0，最优解为b点。
由方程组。解出x1=75，x2=15
x*==75，15）t
max z =z*= 70×75+30×15=5700
例2：用**法求解。
max z = 6x1+4x2
可行解域为oabcd0，最优解为b点。
由方程组。解出x1=2，x2=6
x*==2，6）t
max z = 6×2+4×6=36
例3：用**法求解。
min z =－3x1+x2
解：可行解域为bcdefb，最优解为b点。
由方程组解出x1=4，x2=
x*==4，）t
min z =－3×4+=－11
二、标准型线性规划问题的单纯形解法：
一般思路：1、用简单易行的方法获得初始基本可行解；
2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；
3、根据θl规则确定改进解的方向；
4、根据可能改进的方向进行迭代得到新的解；
5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。
具体做法（可化归标准型的情况）：
设已知。max z = c1x1+ c2x2+…+cnxn
对第i个方程加入松弛变量xn+i，i =1，2，…，m，得到。
列表计算，格式、算法如下：
注①： zj =cn+1 a1j+ cn+2 a2j +…cn+m amj=，（j=1，2，…，n+m）
j =cj－zj ,当σj ≤0时，当前解最优。
注②：由max确定所对应的行的变量为“入基变量”；
由θl=确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。
例1：用单纯形法求解（本题即是本资料p2“**法”例1的单纯形解法；也可化“对偶问题”求解）
max z =70x1+30x2
解：加入松弛变量x3，x4，x5，得到等效的标准模型：
max z =70x1+30x2+0 x3+0 x4+0 x5
列表计算如下：
x*=（75，15，180，0，0）t
max z =70×75+30×15=5700
例2：用单纯形法求解。
max z =7x1+12x2
解：加入松弛变量x3，x4，x5，得到等效的标准模型：
max z =7x1+12x2+0 x3+0 x4+0 x5
列表计算如下：
x*=（20，24，84，0，0）t
max z =7×20+12×24=428
三、非标准型线性规划问题的解法：
1、一般地，对于约束条件组：
若为“≤”则加松弛变量，使方程成为“＝”
若为“≥”则减松弛变量，使方程成为“＝”
我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：
由目标函数min z=变成等价的目标函数max（－z）=
令－z=z/，∴min z=－max z/
2、等式约束——大m法：
通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为－m，m是很大的正数，从原理上理解又称为“惩罚系数”。（课本p29）
类型一：目标函数仍为max z，约束条件组≤与＝。
例1：max z =3x1+5x2
解：加入松弛变量x3，x4，得到等效的标准模型：
max z =3x1+5x2
其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到： max z =3x1+5x2－mx5
单纯形表求解过程如下：
x*=（2，6，2，0）t
max z =3×2+5×6=36
类型二：目标函数min z，约束条件组≥与＝。
例2：用单纯形法求解。
min z =4x1+3x2
解：减去松弛变量x3，x4，并化为等效的标准模型：
max z/ =4x1－3x2
增加人工变量x5、x6，得到：
max z/ =4x1－3x2－mx5－mx6
单纯形表求解过程如下：
x*=（2，3，0，0）t
min z =－max z/ =17）=17
四、对偶问题的解法：
什么是对偶问题？
1、在资源一定的条件下，作出最大的贡献；
2、完成给定的工作，所消耗的资源最少。
引例（与本资料p2例1 “**法”、p7例1 “单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在a、b、c三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：
问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
《运筹学》复习参考
资料加工 整理人 杨峰 函授总站高级讲师 要求掌握的各部分知识点。第一部分线性规划问题的求解 相当于教材的第一章 重要算法 单纯形迭代 大m法单纯形迭代 表上作业法 匈牙利法。第二部分动态规划问题的求解 相当于教材的第三章 重要算法 图上标号法。第三部分网络分析问题的求解 相当于教材的第四章 重要算...
运筹学参考习题
运筹学 参考习题。说明 1.期末考试共两个题型，分别是判断题 2分 题，共10题 应用 计算题 共6题，80分 2.考试范围不超过课堂讲授范围。判断题参考习题 1 线性规划的可行域为无界，则此线性规划为无界解。2 有5个产地5个销地的平衡运输问题，则它的基变量有9个。3 在资源优化的线性规划问题中，...
运筹学复习
有四项工作要甲 乙 丙 丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如下表所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少？最优方案为 甲 工作1，乙 工作4，丙 工作3，丁 工作2例试将下面线性规划问题。min z x1 2x2 3x...