第 1 页 共 29 页 《运筹学》复习参考资料
资料加工、整理人——杨峰（函授总站高级讲师）
要求掌握的各部分知识点
第一部分 线性规划问题的求解（相当于教材的第一章）
——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法
第二部分 动态规划问题的求解（相当于教材的第三章）
——重要算法：图上标号法
第三部分 网络分析问题的求解（相当于教材的第四章）
——重要算法：破圈法、TP标号法、寻求网络最大流的标号法
第四部分 存储论简介（相当于教材的第七章）
※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。
非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
运筹学线性规划案例 生产组织与计划问题
解
某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？
目标函数： Min Z= 2x1 + 3 x2
约束条件：s.t. x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
解：目标函数： Min Z= 2x1 + 3 x2
约束条件：
s.t. x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
采用图解法。如下图：得Q点坐标（250，100）为最优解。
100 200 300 400 500 600 100 200 300 400 600
500 x1 =125
x1+x2 =350 2x1+x2 =600
x1 x2
Q
课内实验报告
课 程 名： 运 筹 学
任课教师： 邢 光 军
专 业：
学 号：
姓 名：
2012/2013学年 第 2 学期
南京邮电大学 经济与管理学院
《 运筹学 》课程实验第 1 次实验报告
实验内容及基本要求：
实验项目名称：线性规划实验
实验类型： 验证
每组人数： 1
实验内容及要求：
内容：线性规划建模与求解
要求：能够写出求解模型、运用软件进行求解并对求解结果进行分析
实验考核办法：
实验结束要求写出实验报告。实验报告的形式可以包括以下3点：
1.问题的分析与建立模型,阐明建立模型的过程。
2.计算过程,包括采用什么算法，使用什么软件以及计算详细过程和结果。
3.结果分析,将结果返回到实际问题进行分析、讨论、评价和推广。
实验结果：（附后）
实验背景：某商场是个中型的百货商场，它对售货人员的需求经过统计分析如表1所示。
表1
时间 所需售货人数（人）
星期日 28
星期一 15
星期二 24
星期三 25
星期四 19
星期五 31
星期六 28
为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员人数最少？
1.问题的分析与建立模型:
首先题目要求售货人员每周工作5天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员人数最少，根据题目要求我们可以设7个决策变量，分别表示从周一到周日开始休息的人数分别为x1,x2,x3,x4,x5,x6,x7
目标函数：min w=x1+x2+x3+x4+x5+x6+x7
约束条件：x1+x2+x3+x4+x5>=28
x2+x3+x4+x5+x6>=15
2004年运筹学试题
题目大概：
1、简答3道：中国邮路问题；存贮问题概念；？
2、线性规划（简单）
3、运输问题（简单，一步到位的那种）
4、动态规划（书上例题） （可惜我做错了，20分啊，想起来都心疼）
5、图论：最小截集最大流定理证明（较难）
6、论述：运筹学的应用 2005年运筹学试题
六道大题
1.利用对偶理论和互不松弛理论解一个线性规划问题，单纯形法也应该
可以做，但是过于复杂。
2.矩阵对策问题，悲观主义决策准则，乐观主义决策准则
3.一个建模问题，比较简单
4.一个简单的求最短路问题
5.动态规划问题，很简单
6.非线性规划，类似清华大学出版社出版的《运筹学》第七章例一
总体感觉偏基础原理 2006年运筹学试题
1.不记得了
2.分支定界问题（真正算起来还是比较麻烦的）
3.动态规划问题（书上的原题）
4.最大流最小截定理的证明（这个比较麻烦，貌似以前考过的）
5.运输问题（比较容易）
6.对偶问题的优缺点，写对偶单纯形的算法（麻烦）
7.图论里一笔划问题的证明，是书上的定理连通图是欧拉图的充要条件
的证明。这个比较麻烦，然后还要写一个欧拉圈的找法，写出步骤，这个比较麻烦。
8.还有一个kt条件的题，这个不是最后一题，是中间的一题,很容易～
2007年运筹学试题:
2007年的运筹学试题出题思路与往年不是很一样,在基础题上,多加了一
点难度,还考了两道考试范围之外的题，一共是七大题：
基础题: 难度和书上的例题还有课后题差不多。
1.用单纯形法解线性规划问题：很基础，但有一定的计算量；
2.两维Kt条件问题：感觉同上
偏难的一些题：在基础上更大难度，难度和那本“运筹学习题集”一样。
3.求最短路问题，是“运筹学习题”上的一个原题：不记得是哪道了，书
也没有了。大家可以去找找：已知有几个村，村村之间的距离dij，每个
村的学生数，求找一个村建学校，以解得上学的总路（每个学生走的路
程之和）最小。
4.动态规划问题：我一直没有找到原题，但可以记得是两维的，两种资
