单纯形法大M法求解线性规划问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,班级：物流113,队员：陈祥娟 冯雪萍,张献献 李起平,线性规划各种解的情况,1,大,M,法,大,M,法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵,I,，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。,为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数,-,。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。,以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。,2,两阶段法,两阶段法引入人工变量的目的和原则与大,M,法相同，所不同的是处理人工变量的方法。,两阶段法的步骤：,求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。,如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。,求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解,3,单纯形表与线性规划问题的讨论,无可行解,通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。,人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。,4,例,1,、求解下列线性规划问题,解：,首先将问题化为标准型,令，则,故引入人工变量，,并利用大,M,法求解,5,C,-3 -2 -1 0 0 0 -M -M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,0,-M,-M,x,4,x,7,x,8,6,4,3,1 1 1 1 0 0 0 0,1 0 -1 0 -1 0 1 0,0 1 -1 0 0 -1 0 1,6/1,-,3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0,-M,-2,x,4,x,7,x,2,3,4,3,1 0 2 1 0 1 0 -1,1 0 -1 0 -1 0 1 0,0 1 -1 0 0 -1 0 1,3/1,4/1,-,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3,-M,-2,x,1,x,7,x,2,3,1,3,1 0 2 1 0 1 0 -1,0 0 -3 -1 -1 -1 1 1,0 1 -1 0 0 -1 0 1,0 0 3-3M 3-M -M 1-M 0 -1,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量,x,7,=1,为基变量，所以原线性规划不存在可行解。,6,无,界,解,无最优解与无可行解时两个不同的概念。,无可行解是指原规划不存在可行解，从几何的角度解释是指,线性规划问题的可行域为空集；,无最优解则是指线性规划问题存在可行解，但是可行解的目,标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。,判别方法：,无最优解判别定理,在求解极大化的线性规划问题过程中，若某单纯形表的检验,行存在某个大于零的检验数，但是该检验数所对应的非基变量,的系数列向量的全部系数都为负数或零，则该线性规划问题,无最优解，,可以,可以,7,例,2,、试用单纯形法求解下列线性规划问题：,解：引入松弛变量x,3,x,4,化为标准型,C,2 2 0 0,C,X,B,B,x,1,x,2,x,3,x,4,0,X,3,1,-1,1,1,0,0,X,4,2,-1/2,1,0,1,Z,0,2,2,0,0,因,但,所以原问题,无最优解,8,退化解,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。,产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值,，那么在下次迭代中就会出现一个甚至多个基变量等于零。,遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，,解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,9,例,3,、求解下述线性规划问题：,解：,引入松弛变量,化标准型,10,0,0,0,-24,2,-80,3,0,Z,-5,-6,0,-42,0,-8,0,5,Z,1,0,0,0,1,0,0,1,x,3,2,1,2,0,6,0,-24,1,1,x,1,3,3,2,1,30,0,-8,0,3,x,5,0,0,-3,0,-42,5,-8,0,0,Z,1,1,0,0,1,0,0,1,x,7,0,0,1,0,6,-1,-24,1,0,x,1,3,0,-1,1,30,-3,-8,0,0,x,5,0,-,1,1,0,0,1,0,0,1,x,7,0,0,0,1,0,6,-1,-24,1,0,x,6,0,0,0,0,1,36,-4,-32,1,0,x,5,0,x,7,x,6,x,5,x,4,x,3,x,2,x,1,b,X,B,C,B,0,0,0,-24,2,-80,3,C,第一次迭代中使用了摄动法原理，选择下标为,6,的基变量,x,6,离基。,可得最优解 ，目标函数值,maxZ=,，,11,无穷多最优解,无穷多最优解判别原理：,若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。,例,4,：最优表：,非基变量检验,数，所以有无穷多,最优解。,最优解集为可行域两个顶点的凸组合：,C,1 2 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,2,1,x,3,x,2,x,1,2,3,2,0 0 1 2 -1,0 1 0 1 0,1 0 0 -2 1,2/2,3/1,-,Z,8,0 0 0 0 -1,12,Then End,13,