《二章线规划.ppt》由会员分享,可在线阅读,更多相关《二章线规划.ppt(35页珍藏版)》请在三一文库上搜索。
1、第二章 线性规划,第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 单纯形法 第四节 线性规划的对偶问题 第五节 线性规划在卫生管理中的应用,第三节 单纯形法,一、单纯形法的基本原理,二、单纯形解法,三、大 M 法,(一) 人工变量,(二) 大 M 法求解,一、单纯形法的基本原理,(一)典型方程组规范型,(二)基本变量,(三)基本解,(四)基本可行解,(五)单纯形法原理,目标求极大值 变量非负 右端项非负 全部等式约束,单纯形法要求 线性规划模型,标准形式,规范形式,系数矩阵中包含 一个单位子矩阵,每个约束方程中要有 一个变量的系数, 而这个变量在其余方 程中不出现。,得
2、到最优解或 证明最优解不存在,标准型,从可行域某个顶点开始,检查该点 是否最优解,不是,取一个“相邻”、 “更好”的顶点,单纯形法的基本原理,规范型,例8 某制药厂生产甲、乙两种药品,它们均须在A、B、C三种设备上加工,每种设备的使用时间,每吨药品的加工时间以及所获利润见下表,甲、乙药品各生产多少吨,可使该厂所获利润最大?,表15 药品生产有关数据,二、单纯形解法,解:设甲、乙分别生产x1 、x2吨,该厂所获利润为 Z百元。建立数学模型如下:,第二步:建立初始单纯形表并进行表的迭代 (见表16),第一步:化线性规划模型为标准规范型 (见上面右边),表16 单纯形法表格计算过程,由表得最优解,相
3、应的最优值 Z5700,例8的最优解是,最优值是 Z5700,单纯形法的基本步骤:,1建立初始单纯形表 -确定初始基本可行解 确定基变量、非基变量以及初始基本可行解和目标函数的值。,()求出相应的检验数 在用非基变量表达的目标函数表达式中,我们称非基变量 xj 的系数为检验数,2最优性检验,()最优解判别,如果任何一个非基变量的值增加都不能使目标函数值增加,即所有检验数非正,则当前的基本可行解就是最优解,计算结束。,()无有限最优解判别,如果有一个检验数大于,且其所在的列的所有 aij 非正,则表示可行域是不封闭的,且目标函数值随进基变量的增加可以无限增加,此时,不存在有限最优解(或称有无界解
4、或无最优解),计算结束。,基本可行解的改进 ()确定进基变量 若存在检验数大于0 ,那么绝对值最大者对应的非基变量 xj 称为进基变量;,单纯形法的基本步骤:,这个基变量xr 称为出基变量;,()确定出基变量,满足,单纯形法的基本步骤:,()确定枢元,进基变量所在的列称为枢列,出基变量所在的行称为枢行,枢行与枢列交点处元素称为枢元。,()迭代运算,围绕主元进行初等变换 ,确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复。,注意:单纯形法中 1.每一步运算只能用矩阵初等行变换; 2.表中第3列(b列)的数总应保持非负(0) 3.当所有检验数均非正(0)时,得到最优单
5、纯形表。 4.可能出现的特殊情况,单纯形法求解中的特殊情况,1最终产生最优值的单纯形表中,某一非基本变量的检验数0,意味着作任何增大,目标函数的最优值不变此时线性规划问题的最优解并不唯一,有多重最优解 (见下面例题),例 用单纯形法求解下列规划问题,单纯形表迭代,最优解为:,最优值为:,2当枢列(进基变量所在列)中的每一项系数不是0就是负值时,说明所有约束条件对进基变量的增加都无约束作用,因此目标函数可以无限地增加这种情况我们称为无有限最优解(或称有无界解或无最优解)但在现实中,不可能有此情况,往往是模型建立错误,遗漏了一些约束条件所致,单纯形法求解中的特殊情况,单纯形法求解中的特殊情况,3在
6、选取进基变量时,有2个及2个以上变量的检验数具有相同的最大正值(极小化问题为相同的最小负值),这时可任选其中一个变量进基选择进基变量的不同,可能在达到最优解前迭代的次数也不同,但事先无法预测,4出现相同的最小比值,此时可从具有相同最小比值所对应的基本变量中,选择下标最大的那个基本变量为出基变量这时有可能出现退化的基本可行解,即至少有一个基变量为零(见规划教材例2-8中的表2-6和表2-7),单纯形法求解中的特殊情况,出现退化的基本可行解对运算带来麻烦,理论上可能出现单纯形法陷入循环或闭环,在每次迭代中值保持不变,不能使解趋向最优解但幸运的是,在实际应用中从未遇到或发生过这种情况尽管如此,人们还
7、是对如何防止出现循环作了大量研究。提出了各种避免循环的方法。,单纯形法求解中的特殊情况,在选择进基变量和出基变量时作以下规定: 在选择进基变量时,在所有 j 0的非基变量中选取下标最小的进基; 当有多个变量同时可作为出基变量时,选择下标最大的那个变量出基。这样就可以避免出现循环,当然,这样可能使收敛速度降低。,避免循环的方法,单纯形法的基本过程,#,三、大M法,一般情况的处理:主要是讨论初始基本可行解不明显时,常用的方法。,(一)人工变量,消去第一个方程中的x1: 第二个方程乘以2加到第一个方程中去,把第二个方程直接加一个变量(人工变量),考虑一般问题:,Max Z = c1 x1 + c2
8、x2 + + cn xn a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1+ am2 x2+ amn xn = bm x1 ,x2 , ,xn 0,bi 0 , i = 1 , , m,引入人工变量 xn+i 0,i = 1 , m; a11 x1+ a12 x2+ + a1n xn+ xn+1 = b1 a21 x1+ a22 x2+ + a2n xn + xn+2 = b2 am1 x1+ am2 x2+ + amn xn + xn+m = bm x1, x2 ,., xn , xn+1, , xn
9、+m 0,引入人工变量 xn+i 0 (i = 1 , , m)及充分大正数 M 。得到:,Max Z = c1 x1 + c2 x2 + cn xn - M xn+1 - - M xn+m a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ,x2 , ,xn ,xn+1 , ,xn+m 0,(二) 大 M 法求解,Max Z = 5x1+ 2x2+ 3x3-x4 -M x5-M x6 x1+ 2x 2+
10、3 x3+ x5 =15 2 x1+ x2+ 5 x3+ x6 = 20 x1+ 2 x2+ 4 x3+ x4 = 26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 0,例1:Max Z = 5x1 + 2x2 + 3x3 - x4 x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 0,得到最优解:(25/3,10/3,0,11)T ,最优目标值:112/3,在用大法求解时,如果得到人工变量不为零的最优解,则说明原问题不可行,即原问题无解另外,若极小比值相等,则人工变量先出基,
11、规划教材第十三章介绍了用 Excel 以电子表格的形式建立与求解线性规划模型的方法,注意,#,一、单纯形法的基本步骤:,本次课小结,1建立初始单纯形表-确定初始基本可行解,2最优性检验,()求出相应的检验数,()最优解判别,()无有限最优解判别,基本可行解的改进,()确定进基变量,()确定出基变量,()确定枢元,()迭代运算,二、 大 M 法:,引入 人工变量 xn+i 0(i = 1 , m)及充分大正数M,Max Z = c1 x1 + c2 x2 + cn xn - M xn+1 - - M xn+m,本次课小结,a11 x1+ a12 x2+ + a1n xn+ xn+1 = b1 a21 x1+ a22 x2+ + a2n xn + xn+2 = b2 am1 x1+ am2 x2+ + amn xn + xn+m = bm x1, x2 ,., xn , xn+1, , xn+m 0,作 业 规划教材 P51 6(2)(5),
链接地址:https://www.31doc.com/p-3106486.html