运筹学课件线性规划问题及单纯型解法ppt.ppt

1、运筹学Operational Research,运筹帷幄，决胜千里 史记张良传,2,目 录,绪 论 第一章 线性规划问题及单纯型解法 第二章 线性规划的对偶理论及其应用 第三章 运输问题数学模型及其解法 第四章 整数规划 第五章 动态规划 第六章 图与网路分析 第七章 随机服务理论概论 第八章 生灭服务系统 第九章 特殊随机服务系统 第十章 存储理论,3,绪 论,一、运筹学的起源与发展 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 四、运筹学的发展趋势,4,一、运筹学的起源与发展,起源于二次大战的一门新兴交叉学科 与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深

2、度、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research 战后在经济、管理和机关学校及科研单位继续研究 1952年，Morse 和 Kimball出版运筹学方法 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS，并于1999年8月组织了第15届大会,5,二、运筹学的特点及研究对象,运筹学的定义 为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse 和 Kimball 运筹学是把科学方法应用在指导人员、工商企

3、业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science,6,二、运筹学的特点及研究对象,运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等 图论与网路理论 随机服务理论：排队论 存储理论 决策理论 对策论 系统仿真：随机模拟

4、技术、系统动力学 可靠性理论 金融工程,7,三、运筹学解决问题的方法步骤,明确问题 建立模型 设计算法 整理数据 求解模型 评价结果,明确问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,8,四、运筹学的发展趋势,运筹学的危机 脱离实际应用，陷入数学陷阱 IT对运筹学的影响 MIS, DSS, MRP-II, CIMS, ERP OR Dept. - Dept. Of OR & IS 运筹学与行为科学结合 群决策和谈判 对策理论 多层规划 合理性分析 服务行业中的应用 金融服务业 信息、电信服务业 医院管理,9,四、运筹学的发展趋势,软计算 面向强复杂

5、系统的计算、实时控制、知识推理 智能算法：模拟退火、遗传算法、人工神经网络、戒律算法等 系统仿真 面向问题 后勤(Logistics) 全球供应链管理 电子商务：集成特性 随机和模糊 OR 问题本身的不确定性 人类知识的局限性,10,第一章 线性规划问题及单纯型解法,1.1 线性规划问题及其一般数学模型 1.1.1 线性规划问题举例 例1、多产品生产问题（Max, ） 设x1, x2 分别代表甲、乙两种电缆的生产量，,11,例2、配料问题（min, ),设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量,12,例3、合理下料问题 设 xj 分别代表采用切割方案18的套数，,13,1.1.2

6、 线性规划数学模型的一般表示方式,14,1、和式,15,2、向量式,16,3、矩阵式,17,1.1.3 线性规划的图解法,f(x)=36,18,线性规划问题的几个特点：,线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的 最优解只可能在凸集的极点上，而不可能发生在凸集的内部,19,1.2 线性规划问题的单纯型解法 1.2.1 线性规划问题的标准形式 为了使线性规划问题的解法标准，就要把一般形式化为标准形式,20,变换的方法：,目标函数为min型，价值系数一律反号。令 f(x) = -f(x) = -CX, 有 min f(x) = - m

7、ax - 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，代入非标准型,21,变换举例：,22,关于标准型解的若干基本概念：,标准型有 n+m 个变量， m 个约束行 “基”的概念 在标准型中，技术系数矩

8、阵有 n+m 列，即 A = ( P1, P2 , , Pn+m ) A中线性独立的 m 列，构成该标准型的一个基，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为基向量 与基向量对应的变量称为基变量，记为 XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = XB + XN 最多有 个基,23,关于标准型解的若干基本概念：,可行解与非可行解 满足约束条件和非负条件的解 X 称为可行解，满足约束条件但不满足非负条件的解 X 称为非可行

9、解 基础解 令非基变量 XN = 0，求得基变量 XB的值称为基础解 即 XB = B1 b XB 是基础解的必要条件为XB 的非零分量个数 m 基础可行解 基础解 XB 的非零分量都 0 时，称为基础可行解，否则为基础非可行解 基础可行解的非零分量个数 m 时，称为退化解,24,线性规划标准型问题解的关系,约束方程的 解空间,基础解,可行解,非可行解,基础 可行解,退化解,25,可行解、基础解和基础可行解举例,26,1.2.2 单纯型法的基本思路,27,1.2.3 单纯型表及其格式,28,例1.2.2 试列出下面线性规划问题的初始单纯型表,29,关于检验数的数学解释,设 B 是初始可行基，则

10、目标函数可写为两部分(1) 约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数 把 XB 代入目标函数，整理得到(3)式 第 j 个非基变量的机会成本如(4)式 若有cjzj0, 则未达到最优,30,1.2.4 标准型的单纯型算法,找初始基础可行基 对于(max,)，松弛变量对应的列构成一个单位阵 若有 bi 0 中找最大者，选中者称为入变量， xj* 第j*列称为主列 确定入变量的最大值和出变量 最小比例原则,31,1.2.4 标准型的单纯型算法,确定入变量的最大值和出变量 设第 i* 行使 最小，则第 i* 行对应的基变量称为出变量，第 i* 行称为主行

11、迭代过程 主行 i* 行与主列 j* 相交的元素ai*j* 称为主元，迭代以主元为中心进行 迭代的实质是线性变换，即要将主元 ai*j*变为1，主列上其它元素变为0，变换步骤如下： (1)变换主行,32,1.2.4 标准型的单纯型算法,迭代过程 (2)变换主列 除主元保留为1，其余都置0 (3)变换非主行、主列元素 aij (包括 bi) 四角算法公式：,33,1.2.4 标准型的单纯型算法,5、迭代过程 (4)变换CB，XB (5)计算目标函数、机会成本 zj 和检验数 cj zj 6、返回步骤 2,34,表1.2.4 例1.2.2 单纯型表的迭代过程,答：最优解为 x1=20, x2=20

12、, x3=0, OBJ=1700,35,单纯型表中元素的几点说明,任何时候，基变量对应的列都构成一个单位矩阵 当前表中的 b 列表示当前基变量的解值，通过变换 B 1 b 得到 (资源已变成产品) 当前非基变量对应的向量可通过变换 B 1 AN 得到， 表示第 j 个变量对第 i 行对应的基变量的消耗率 非基变量的机会成本由 给出 注意基变量所对应的行,36,1.3 人工变量的引入及其解法 1.3.1 当约束条件为“”型，引入剩余变量和人工变量,由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变

13、量 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法 大M法 二阶段法,37,1.3.2 大M法的求解过程 例1.3.1,38,表1.3.1 例1.3.1的单纯型表迭代过程,答：最优解为 x1=2, x2=2, x3=0, OBJ=36,39,大M法的一些说明,大M法实质上与原单纯型法一样，M 可看成一个很大的常数 人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M

14、法 二阶段法手算可能容易,40,1.3.3 二阶段法的求解过程,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无解 为了简化计算，在第一阶段重新定义价值系数如下：,41,表1.3.2 用二阶段法求解例1.3.1的第一阶段,42,表1.3.2 用二阶段法求解例1.3.1的第二阶段,最优解对应的B1在哪？,43,1.5 单纯型法的一些具体问题,1.5.1 关于无界解问题 可行区域不闭合(约束条件有问题) 单纯型表中入变量 xj* 对应的列中所有,44,表1.5.1 例1.5.1 的单纯型表及其迭代过程,45,1.5.2 关于退化问题,退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法,46,1.5.3 关于多重解问题,多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1,47,表1.5.3 例1.5.3 的单纯型表及其迭代过程,48,1.5.4 关于无可行解