运筹学26988.ppt

运筹学Operational Research 运筹帷幄，决胜千里 ?史记《张良传》 目录 第一章 线性规划问题及单纯型解法 第二章 线性规划的对偶理论及其应用 第三章 运输问题数学模型及其解法 第四章 整数规划 第五章 动态规划 第六章 图与网路分析 第七章 随机服务理论概论 第八章 生灭服务系统 第九章 特殊随机服务系统 第十章 存储理论 绪论 一、运筹学的起源与发展 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 四、运筹学与其它学科之间的关系 第一章 线性规划问题及单纯型解法 1.1 线性规划问题及其一般数学模型 1.1.1 线性规划问题举例 例1、多产品生产问题（Max, ?） 设x1, x2 分别代表甲、乙两种电缆的生产量， 例2、配料问题（min, ?) 设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量 例3、合理下料问题 设 xj 分别代表采用切割方案1~8的套数， 1.1.2 线性规划数学模型的一般表示方式 1、和式 2、向量式 3、矩阵式 1.1.3 线性规划的图解法 线性规划问题的几个特点： 线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的 最优解只可能在凸集的极点上，而不可能发生在凸集的内部 变换的方法： 目标函数为min型，价值系数一律反号。令 f?(x) = -f(x) = -CX, 有 min f(x) = - max [- f(x)] = - max f ?(x) 第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向 第i 个约束为 ? 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0 第i 个约束为 ? 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0 若xj ?0，令 xj= -xj? ，代入非标准型，则有xj? ? 0 若xj ?不限，令 xj= xj? - xj?， xj? ? 0，xj? ? 0，代入非标准型 变换举例： 关于标准型解的若干基本概念： 关于标准型解的若干基本概念： 线性规划标准型问题解的关系 可行解、基础解和基础可行解举例 1.2.2 单纯型法的基本思路 1.2.3 单纯型表及其格式 例1.2.2 试列出下面线性规划问题的初始单纯型表 关于检验数的数学解释 设 B 是初始可行基，则目标函数可写为两部分(1) 约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数 把 XB 代入目标函数，整理得到(3)式 第 j 个非基变量的机会成本如(4)式 若有cj?zj0, 则未达到最优 1.2.4 标准型的单纯型算法 找初试基础可行基 对于(max,?)，松弛变量对应的列构成一个单位阵 若有 bi0，则单位阵也不能构成一个可行基 检验当前基础可行解是否为最优解 所有检验数 cj? zj?0，则为最优解，否则 确定改善方向 从 (cj? zj) 0 中找最大者，选中者称为入变量， xj* 第j*列称为主列 确定入变量的最大值和出变量 最小比例原则 1.2.4 标准型的单纯型算法 确定入变量的最大值和出变量 设第 i* 行使 ? 最小，则第 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 ? zj 6、返回步骤 2 表1.2.4 例1.2.2 单纯型表的迭代过程 单纯型表中元素的几点说明 任何时候，基变量对应的列都构成一个单位矩阵 当前表中的 b 列表示当前基变量的解值，通过变换 B ?1 b 得到 (资源已变成产品) 当前非基变量对应的向量可通过变换 B ?1 AN 得到， 表示第 j 个变量对第 i 行对应的基变量的消耗率 非基变量的机会成本由