最新单纯形法大M法求解线性的规划问题教学讲义ppt课件.ppt

《最新单纯形法大M法求解线性的规划问题教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单纯形法大M法求解线性的规划问题大M法大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。以后的计算与单纯形表解法相同，Ｍ只

2、需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。2两阶段法两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤：求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题

3、没有可行解，可停止计算。求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解3无界解无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系

4、数都为负数或零，则该线性规划问题无最优解，可以可以7例2、试用单纯形法求解下列线性规划问题：解：引入松弛变量x3,x4化为标准型C2200θCXBBx1x2x3x40X31-11100X42-1/2101Z02200因但所以原问题无最优解8退化解当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此

5、得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。9例3、求解下述线性规划问题：解：引入松弛变量化标准型10000-242-8030Z-5-60-420-805Z10001001x3212060-2411x13321300-803x

6、500-30-425-800Z11001001x700106-1-2410x130-1130-3-800x50-11001001x7000106-1-2410x60000136-4-3210x50x7x6x5x4x3x2x1bXBCB000-242-803Cθ第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。可得最优解，目标函数值maxZ=５，11无穷多最优解无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例4：最优表：非基变量检验数　　　，所

7、以有无穷多最优解。最优解集为可行域两个顶点的凸组合：C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-112ThenEnd13止痛药的研究与应用讲授王绪前共37幅14疼痛是临床极为常见的病症。从部位来分，有头痛、胸痛、胃痛、胁痛、腹痛、肢体疼痛、痛经、跌打损伤疼痛。在中医理论指导下，通过祛除各种致痛原因，以达到减轻疼痛程度或完全缓解疼痛为目的的药物，均可以称为止痛药物。从广义的范围而言，中药均有直接或间接程度上的止痛作用。15从止痛的途径来看又有行气止痛：如木香；化瘀止痛

8、：如桃仁；通经止痛：如益母草；通络止痛：如马钱子；散寒止痛：如附子；温中止痛：如高良姜；解毒止