第 1 页 共 29 页 《运筹学》复习参考资料
资料加工、整理人——杨峰（函授总站高级讲师）
要求掌握的各部分知识点
第一部分 线性规划问题的求解（相当于教材的第一章）
——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法
第二部分 动态规划问题的求解（相当于教材的第三章）
——重要算法：图上标号法
第三部分 网络分析问题的求解（相当于教材的第四章）
——重要算法：破圈法、TP标号法、寻求网络最大流的标号法
第四部分 存储论简介（相当于教材的第七章）
※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。
非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
1. 简答题
（1） 运筹学的工作步骤
提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；
建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；
求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂模型的求解需用计算机，解得精度要求可有决策者提出；
解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；
解的控制：通过控制解的变化过程决定对解是否做一定的改变；
解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2） 退化产生原因及解决办法
单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：
1.选取cj-zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj-zj＞0)
2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释
• 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。
• 对偶变量 yi在经济上表示原问题第i种资源的边际价值。
• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 njmiiijjybxcZ11iiybZ若原问题的价值系数Cj表示单位产值，则yi 称为影子价格；
若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤
a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解，
b) 若求得的最优解符合整数要求，则是原IP的最优解；
c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
运筹学动态规划
运筹学是一门综合运筹学、优化学、决策学和统计学等多学科知识的学科，它的核心内容是对决策问题进行建模和分析，并通过数学方法进行求解和优化。动态规划是运筹学中的一种重要方法，它通过将问题划分为相互重叠的子问题，并通过解决子问题的最优解来求解原问题的最优解。下面将详细介绍运筹学中的动态规划方法。
动态规划方法的核心思想是将原问题分解为若干个相互重叠的子问题，并通过求解子问题的最优解来求解原问题的最优解。为了可以使用动态规划方法，必须满足以下两个条件：子问题的最优解可以作为原问题的最优解的一部分；子问题之间必须具有重叠性，即一个子问题可以被多次使用。
动态规划方法的具体步骤如下：首先，将原问题分解为若干个子问题，并定义出每个子问题的状态和状态转移方程；其次，通过迭代求解每个子问题的最优解，直到求解出原问题的最优解；最后，根据子问题的最优解和状态转移方程，得到原问题的最优解。
动态规划方法的应用非常广泛，可以用于求解各种各样的优化问题。例如，在物流配送中，可以使用动态规划方法求解最短路径问题；在生产计划中，可以使用动态规划方法求解最优生产计划；在股票投资中，可以使用动态规划方法求解最优投资策略等。
动态规划方法的优点是可以通过求解子问题的最优解来求解原问题的最优解，避免了穷举法的复杂性。此外，动态规划方法还可以通过引入一定的约束条件，来对问题进行更精确的建模和求解。
然而，动态规划方法也存在一些局限性。首先，动态规划方法要求问题能够满足子问题的最优解可以作为原问题的最优解的一部分，这限制了动态规划方法的应用范围。其次，动态规划方法通常需要建立较为复杂的状态转移方程，并进行复杂的计算，使得算法的实现和求解过程比较困难。
综上所述，动态规划是运筹学中的一种重要方法，通过将问题划分为相互重叠的子问题，并通过解决子问题的最优解来求解原问题的最优解。动态规划方法的优点是可以高效地求解优化问题，但同时也存在一些局限性。运筹学中的动态规划方法可以广泛应用于各种优化问题的建模和求解中，是运筹学领域的一项重要工具和方法。
第五章 动态规划
1、用动态规划方法求下面交通图由A到B的最短时间。
图1
注：各点之间的连线旁边数字，表示时间。
2、设有三种机器，使用也分三个时期。第一个时期使用三种机器的耗费分别为6，8，9；第二个时期使用三种机器的耗费分别为10，12，8；第三个时期使用三种机器的耗费分别为2，5，6。但是机器的使用不是任意的，只能按图的顺序使用。问题是如何安排机器使总耗费最小？（化为网络最短路问题求解）
图2
3、某工厂进行甲、乙、…………………………………………………………………表1丙三种新产品的试制，估计这些新产品试制成功的概率分别为0.6，0.4和0.3。由于工厂急于推出新产品，故厂方领导决定再拨2万元的研制费，以期提高新产品研制的概率。据有关专家估计，把增加的研制费用于各种新产品试制时，试制成功概率如表1所示。试把这批研制费分配给各新产品试制项目（不分配，分配给1万元或分配给2万元），以使这三种新产品均研制成功的概率最大。 增加研制费
（万元） 新产品成功的概率
甲 乙 丙
0 0.60 0.40 0.30 1 0.80 0.70 0.60
2 0.85 0.90 0.70 Q L O B
P
N M I E
C
A D G K J F
时期1 时期2 时期3
机器1
机器2
机器3 4、用动态规划方法求 表2
12max()910fxxx
约束条件：
1121232515,0xxxxx
5、某厂生产一种产品，该产品在未来四个月的销售量估计如表2所示。该项产品的生产准备费用为每批5百元，每件的生产费用1元，每件的存储费用每月为1元。假定1月初的存货为1百件。5月初的存货为0。试求该厂在四个月内的最优生产计划。
6、现有一批资金，总额为5万元拟投资于改造三个工厂。先对三个工厂拟订了几个不同的技术改造方案，其所需资金和投产后新增收益如表3所示。
