运筹学－北京邮电大学-1PPT模板|运筹学－北京邮电大学-1PPT模版(幻灯片模板|Powerpoint模板)

运筹学Operational Research
运筹帷幄，决胜千里
%26#61630;史记《张良传》

目录
第一章 线性规划问题及单纯型解法
第二章 线性规划的对偶理论及其应用
第三章 运输问题数学模型及其解法
第四章 整数规划
第五章 动态规划
第六章 图与网路分析
第七章 随机服务理论概论
第八章 生灭服务系统
第九章 特殊随机服务系统
第十章 存储理论
绪论
一、运筹学的起源与发展
二、运筹学的特点及研究对象
三、运筹学解决问题的方法步骤
四、运筹学与其它学科之间的关系
第一章 线性规划问题及单纯型解法
1.1 线性规划问题及其一般数学模型
1.1.1 线性规划问题举例
例1、多产品生产问题（Max, %26#61603;）
设x1, x2 分别代表甲、乙两种电缆的生产量，
例2、配料问题（min, %26#61619;)
设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量
例3、合理下料问题 设 xj 分别代表采用切割方案1~8的套数，
1.1.2 线性规划数学模型的一般表示方式
1、和式
2、向量式
3、矩阵式
1.1.3 线性规划的图解法
线性规划问题的几个特点：
线性规划问题的可性解的集合是凸集
线性规划问题的基础可行解一般都对应于凸集的极点
凸集的极点的个数是有限的
最优解只可能在凸集的极点上，而不可能发生在凸集的内部

变换的方法：
目标函数为min型，价值系数一律反号。令 f%26#61602;(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f %26#61602;(x)
第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向
第i 个约束为 %26#61603; 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0
第i 个约束为 %26#61619; 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0
若xj %26#61603;0，令 xj= -xj%26#61602; ，代入非标准型，则有xj%26#61602; %26#61619; 0
若xj %26#61617;不限，令 xj= xj%26#61602; - xj%26#61618;， xj%26#61602; %26#61619; 0，xj%26#61618; %26#61619; 0，代入非标准型
变换举例：
关于标准型解的若干基本概念：
关于标准型解的若干基本概念：
线性规划标准型问题解的关系
可行解、基础解和基础可行解举例
1.2.2 单纯型法的基本思路
1.2.3 单纯型表及其格式
例1.2.2 试列出下面线性规划问题的初始单纯型表
关于检验数的数学解释
设 B 是初始可行基，则目标函数可写为两部分(1)
约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数
把 XB 代入目标函数，整理得到(3)式
第 j 个非基变量的机会成本如(4)式
若有cj%26#61485;zj%26gt;0, 则未达到最优
1.2.4 标准型的单纯型算法
找初试基础可行基
对于(max,%26#61603;)，松弛变量对应的列构成一个单位阵
若有 bi%26lt;0，则单位阵也不能构成一个可行基
检验当前基础可行解是否为最优解
所有检验数 cj%26#61485; zj%26#61603;0，则为最优解，否则
确定改善方向
从 (cj%26#61485; zj) %26gt; 0 中找最大者，选中者称为入变量， xj*
第j*列称为主列
确定入变量的最大值和出变量
最小比例原则
1.2.4 标准型的单纯型算法
确定入变量的最大值和出变量
设第 i* 行使 %26#61553; 最小，则第 i* 行对应的基变量称为出变量，第 i* 行称为主行
迭代过程
主行 i* 行与主列 j* 相交的元素ai*j* 称为主元，迭代以主元为中心进行
迭代的实质是线性变换，即要将主元 ai*j*变为1，主列上其它元素变为0，变换步骤如下：
(1)变换主行
1.2.4 标准型的单纯型算法
迭代过程
(2)变换主列
除主元保留为1，其余都置0
(3)变换非主行、主列元素 aij (包括 bi)
四角算法公式：
1.2.4 标准型的单纯型算法
5、迭代过程
(4)变换CB，XB
(5)计算目标函数、机会成本 zj 和检验数 cj %26#61485; zj
6、返回步骤 2
表1.2.4 例1.2.2 单纯型表的迭代过程
单纯型表中元素的几点说明
任何时候，基变量对应的列都构成一个单位矩阵
当前表中的 b 列表示当前基变量的解值，通过变换 B %26#61485;1 b 得到 (资源已变成产品)
当前非基变量对应的向量可通过变换 B %26#61485;1 AN 得到，
表示第 j 个变量对第 i 行对应的基变量的消耗率
非基变量的机会成本由 给出
注意基变量所对应的行
1.3 人工变量的引入及其解法 1.3.1 当约束条件为“%26#61619;”型，引入剩余变量和人工变量
由于所添加的剩余变量的技术系数为%26#61485;1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量
由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定
两种方法
大M法
二阶段法
1.3.2 大M法的求解过程 例1.3.1
表1.3.1 例1.3.1的单纯型表迭代过程
大M法的一些说明
大M法实质上与原单纯型法一样，M 可看成一个很大的常数
人工变量被迭代出去后一般就不会再成为基变量
当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解
大M法手算很不方便
因此提出了二阶段法
计算机中常用大M法
二阶段法手算可能容易

1.3.3 二阶段法的求解过程
第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解
第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解
若第一阶段结束时，人工变量仍在基变量中，则原问题无解
为了简化计算，在第一阶段重新定义价值系数如下：

表1.3.2 用二阶段法求解例1.3.1的第一阶段
表1.3.2 用二阶段法求解例1.3.1的第二阶段
1.5 单纯型法的一些具体问题
1.5.1 关于无界解问题
可行区域不闭合(约束条件有问题)
单纯型表中入变量 xj* 对应的列中所有
表1.5.1 例1.5.1 的单纯型表及其迭代过程
1.5.2 关于退化问题
退化问题的原因很复杂，当原问题存在平衡约束时
当单纯型表中同时有多个基变量可选作出变量时
退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法
1.5.3 关于多重解问题
多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行
最优单纯型表中有非基变量的检验数为0
最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1
表1.5.3 例1.5.3 的单纯型表及其迭代过程
1.5.4 关于无可行解问题
约束条件互相矛盾，无可行域
单纯型表达到最优解检验条件时，人工变量仍在基变量中
表1.5.4 例1.5.4 第一阶段的单纯型表
1.4 修正单纯型法
原单纯型法迭代所需存储量大
原单纯型法有不必要的计算量
1.4.1 修正单纯型的原理
1.4.1 修正单纯型的原理
关键是求当前基的逆矩阵 B%26#61485;1
当前基的逆矩阵 B%26#61485;1 在原单纯型表的什么位置上？
在初始可行基向量位置上
( AN | I ) %26#61662; ( I | AN%26#61485;1 )