韩伯棠教授管理运筹学第三习总复习.docx

一、管理运筹学的定义
运筹学（OperationalResearch，简称OR)，英文直译为“运作研究”。
管理运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
——《中国企业管理百科全书》
绪论
二、管理运筹学Ⅰ的主要分支
线性规划(LinearProgramming，简称LP)
整数规划(IntegralProgramming，简称IP)
目标规划(ObjectiveProgramming，简称OP)
动态规划(DynamicProgramming，简称DP)
图与网络(GraphandNetwork)

三、管理运筹学的工作步骤
提出问题、分析问题

建立模型

求解

解的检验、控制、实施

四、运筹学方法的特点
1.最优化方法
2.定量的方法

线性规划(LP)
一、问题的提出
1.生产计划安排问题：
合理利用人力、物力、财力等，在资源有限的约束条件下,寻求使得获利最大的最优生产计划方案。
2.人力资源分配的问题：
在满足工作的需要的条件下，寻求使用最少的劳动力的最优分配方案。
3.套裁下料问题：
在保证正常生产，完成生产任务的条件下，寻求使用原料最省的最优下料方案。
4.投资问题：在投资额限制的条件下，从多个投资项目中选取使得投资回报最大的最优投资方案。
5.运输问题：寻求使得总运费最小的最优调运方案。

二、建模
1.一般步骤:
分析问题，设出决策变量

根据所提问题列出目标函数

根据已知条件列出所有约束条件

2.LP数学模型的一般形式
★矩阵形式：假设有n个决策变量，m个约束条件。
目标函数：Max（Min）z=CX
约束条件：
AX≤（=,≥）b
s.t.
X≥0
其中，C=(c1,c2,…,cn)(价值向量)
X=(x1,x2,…,xn)T(决策变量向量)
b=(b1,b2,…,bm)T(限定向量)
a11a12…a1n
a21a22…a2n(约束条件系数矩阵)
Am×n=……
am1am2…amn

3.LP数学模型的特点
（1）由目标函数和约束条件构成；
（2）目标函数只有两种情况：求极小或求极大。
（3）双线性
①目标函数是关于决策变量的线性函数;
②所有约束条件是关于决策变量的线性函数。

三、求解
1.方法一：图解法
（1）适用条件
有且仅有两个决策变量X1，X2。
（2）基本概念
可行解；可行域；最优解
（3）基本思路：先求出可行解（即找出可行域），再在可行解的基础上（即在可行域内）求出最优解。
（4）基本步骤作图找出可行域作出目标函数等值线，判断其平移的方向
平移目标函数等值线，在可行域内找出最优点，计算最优解。
（5）图解法解的情况
①唯一最优解②无穷多最优解
③无可行解④无界解
注意：能够区分无可行解和无界解的情况。

（6）图解法的灵敏度分析
①灵敏度分析的含义；
②目标函数中的系数ci的灵敏度分析；
③约束条件右端常数项bj的灵敏度分析；
对偶价格：约束条件右端常数b增加一个单位而使目标函数最优值得到改进的数量，称之为该约束条件的对偶价格。
对偶价格=△z/△b

2.方法二：单纯型法
(1)基本概念
基；基向量,非基向量；基变量,非基变量；基本解,基本可行解,基本最优解；可行基，最优基
(2)重要定理及性质
①若LP的可行域存在，则可行域为凸多边形。
②若LP存在最优解，则最优解一定可在可行域凸多边形的顶点上取得。
③LP问题的一个基本可行解对应于可行域的一个顶点。
可行域的一个顶点一个基本可行解
④以单位矩阵Im×m做基，其基本解的特点是：所有非基变量xj=0，所有基变量xi=bi（标准型中规定b≥0），故单位矩阵可做可行基。

规定:
LP数学模型的标准型:
目标函数：MaxZ=CX
约束条件：
AX=b
s.t.
X≥0
要求:能够将任意模型标准化。
3.方法三：对偶单纯型法
（1）原问题与对偶问题的数学模型
①对称形式的对偶
(对偶定义)设有原问题：LP:
则对偶问题为：DP:
要求：掌握二者模型之间的对应关系。

②非对称形式的对偶
方法：先将原问题化为对称形式(注:无需处理等式约束及自由变量)，再由对偶定义直接写出对偶问题即可。
等式约束自由变量
要求：能够根据任意模型（原问题）写出其对偶问题模型。

（2）对偶规划的基本性质
①对称性
②弱对偶性
③最优性
④强对偶性
（3）对偶单纯型法
①适用条件（极大化问题）：
a.初始单纯形表中，检验数行所有σj≤0；
b.初始单纯形表中，常数列中至少存在一个负值(bk<0)
②基本步骤：
从与单纯型法的比较中掌握此方法。

4.求解运输问题的表上作业法
（1）适用条件：产销平衡的运输问题。
（2）基本步骤
注意：
假设有