卫生管理运筹学课件.pptxVIP

*第一节??基本概念 *第二节 线性规划问题的图解法 *第三节 线性规划模型的解及性质 *第四节 单纯形法 第五节 对偶规划 第六节 运输问题及表上作业法; ; （2）检验、确定进基变量 如果任何一个非基变量的值增加都不能使目标函数值增加，即所有检验数非正，则当前的基本可行解就是最优解，计算结束。 若存在检验数大于0 ，那么绝对值最大者对应的非基变量xj称为“进基变量”，转（3）。; 这个基变量xr称为出基变量。转（4）。 如果进基变量的值增加时，所有基变量的值都不减少，即所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束。; （4）迭代运算 将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。; 注意：单纯形法中 1.每一步运算只能用矩阵初等行变换； 2.表中第3列(b列)的数总应保持非负（≥0） 3.当所有检验数均非正（≤0）时，得到最优单纯形表。 4.可能出现的特殊情况 ;单纯形法求解中的特殊情况 ;例 用单纯形法求解下列规划问题 ;单纯形表迭代;最优解为：;2．当枢列（进基变量所在列）中的每一项系数不是0就是负值时，说明所有约束条件对进基变量的增加都无约束作用，因此目标函数可以无限地增加．这种情况我们称为无有限最优解（或称有无界解或无最优解）．但在现实中，不可能有此情况，往往是模型建立错误，遗漏了一些约束条件所致． ;单纯形法求解中的特殊情况 ;4．出现相同的最小比值，此时可从具有相同最小比值所对应的基本变量中，选择下标最大的那个基本变量为出基变量．这时有可能出现退化的基本可行解，即至少有一个基本变量为零（见规划教材例2-8中的表2-6和表2-7）．出现退化的基本可行解对运算带来麻烦，理论上可能出现单纯形法陷入循环或闭环，在每次迭代中值保持不变，不能使解趋向最优解．但幸运的是，在实际应用中从未遇到或发生过这种情况．尽管如此，人们还是对如何防止出现循环作了大量研究。提出了各种避免循环的方法。 ; ;五、一般情况的处理--人工变量法;;考虑一般问题： 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+m ≥ 0 ;1． 两阶段法：; 引入人工变量 xn+i ≥ 0，i = 1 ,…, m； 构造:Min Ｚ＝ xn+1 ＋ xn+2 ＋ … ＋ xn+m MaxＺ = - xn+1 - xn+2 - … - 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; ;第二步：求解原问题： 以第一步得到的基本可行解为初始基本可行解，用单纯形法求解原问题。在表格计算过程中，这一步的初始单纯形表可这样产生 （1）由第一步的最优单纯形表删去xn＋1 ，xn＋2 ，… ，xn+m 列； （2）把第一行的目标函数系数行换为原问题目标函数的系数； （3）检验数行直接用前文介绍的方法在表格上计算得到，即用xj的价值系数cj减去cB列的各元素与xj列各对应元素的乘积，把计算结果填入xj列的最后一行，得到检验数σj 。;例1：Max Z = 5x1 + 2