第 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) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
第一章
线性规划及单纯形法
2本章主要内容
线性规划概述绪论
一般线性规划问题的数学模型
线性规划问题的图解法
线性规划的基本定理
单纯形法
用计算机软件求解线性规划问题
线性规划的应用举例
3【开篇案例】
某旅行社为了迎接旅
游黄金周的到来，对一日
游导游人员的需求经过统
计分析如表所示。为了保
证导游充分休息，导游每
周工作5天，休息两天，
并要求休息的两天是连续
的。问应该如何安排导游
人员的作息，既满足工作
需要，又使配备的导游人
数最少？一、人力资源分配的问题线性规划
时间所需导游人数
星期日40
星期一34
星期二32
星期三35
星期四28
星期五46
星期六42
4【开篇案例】
明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工
和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自
行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：
公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、
乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？二、生产计划的问题
甲乙丙资源限制
铸造工时(小时/件)51078000
机加工工时(小时/件)64812000
装配工时(小时/件)32210000
自产铸件成本(元/件)354
外协铸件成本(元/件)56--
机加工成本(元/件)213
装配成本(元/件)322
产品售价(元/件)231816线性规划
5【开篇案例】
某工厂要用三种原料1、2、3混合调配出三种不同规格
的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，
使利润收入为最大？三、配料问题产品名称规格要求单价（元/kg）
甲原材料1不少于50%，原材料2不超过25%50
乙原材料1不少于25%，原材料2不超过50%35
丙不限25
原材料名称每天最多供应量单价（元/kg）
110065
210025
36035线性规划
6【开篇案例】
某部门现有资金200万元，今后五年内考虑给以下的项目投资。
已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回
1 基本要求
一、将线性规划化为标准型和写出相应的对偶规划；
二、用图解法求解具有两个决策变量的线性规划问题；
三、用单纯形方法及人工变量法求解线性规划问题；
四、灵敏度分析；
五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题
六、求解产销平衡的运输问题和产销不平衡的运输问题；
七、动态规划与求解。
例题选讲
例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。
设备
产品 A B C D
Ⅰ 2 1 4 2
Ⅱ 3 2 1 4
解 设生产产品Ⅰ和Ⅱ分别为1x和2x件，则由条件可得关系
max 12 23zxx
121212122312284162412xxxxxxxx
0,1,2ixi
⑴标准型的概念：
①目标函数为极大化；
②资源常数0ib；
③约束条件关系为等式；
④决策变量0ix。
例： 将下面的线性规划化为标准型 2 min 12343425zxxxx
1234123412344223142322xxxxxxxxxxxx
123400,,0,xxxx无非负限制
解 max 7193834255zzxxxxx
