运筹学单纯形法迭代原理.pptx
三三.单纯形法的基本思想单纯形法的基本思想1、顶点的逐步转移顶点的逐步转移 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。第1页/共29页 根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？第2页/共29页 转移条件？转移结果？使目标函数值得到改善 得到LP最优解，目标函数达到最优值 2需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优 判断标准是什么？第3页/共29页解解LPLP问题单纯形法的基本思路：问题单纯形法的基本思路：初始可行基：设法在约初始可行基：设法在约束矩阵束矩阵 中中 构造出一个构造出一个mm阶阶单位阵单位阵初始基本可行解初始基本可行解检验数检验数进基进基变量：检验数变量：检验数离基离基变量：最小比值准则变量：最小比值准则第4页/共29页1.1.确定初始基本可行解确定初始基本可行解 LP:？希望在化希望在化LPLP的标准形的标准形式时，式时，A A中都含有一中都含有一个个mm阶单位阵。阶单位阵。第5页/共29页观察法观察法观察系数矩阵中观察系数矩阵中是否含有是否含有现成的单位阵？现成的单位阵？LPLPLPLP限制条件中限制条件中全部是全部是“”“”“”“”类型的约束类型的约束 将将新新增增的的松松弛弛变变量量(+)作作为为初初始始基基变变量量，对对应应的的系数列向量构成单位阵；系数列向量构成单位阵；LPLPLPLP限制条件限制条件有有“”“”“”“”类型的约束类型的约束左端新增左端新增剩余变量剩余变量(-)后，再加上一个非负的新后，再加上一个非负的新变量变量人工变量人工变量。LPLPLPLP限制条件限制条件有有“=”=”=”=”类型的约束类型的约束直接在左端加上直接在左端加上人工变量人工变量。第6页/共29页在引入人工变量后，与原先的约束方程在引入人工变量后，与原先的约束方程不完全等价不完全等价，为此，为此，需要在需要在目标函数目标函数上做些上做些“修正修正”大大MM法法或或两阶段法两阶段法A 非基变量取0，算出基变量，搭配在一起构成初始基本可行解：第7页/共29页2.2.建立判别准则判断：判断：初始初始基本可行解基本可行解或或经过若干次迭代后得到的经过若干次迭代后得到的新新基基本可行解本可行解当前解当前解是否是否为最优解？为最优解？一般（经过若干次迭代），对于基B，用用非非基变量基变量表出表出基变量基变量的表达式的表达式 为：典式若 第8页/共29页用用非基变量非基变量表示表示目标函数目标函数的表达式：的表达式：典式检验数第9页/共29页其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理 第10页/共29页3 3、进行基变换进行基变换（1 1）进进基基变变量量的的确确定定原则：正正检检验验数数（或或最最大大正正检检验验数）所对应的变量进基数）所对应的变量进基，目的是使目标函数得到改善。目的是使目标函数得到改善。（2 2）离基变量的确定）离基变量的确定在在保持解的保持解的可行性可行性的前提下，的前提下，使目标函数使目标函数较快增大较快增大。第11页/共29页 =当当 时，为使时，为使 ，需要，需要从而，最大可取到最小比值原则则该LP无最优解。第12页/共29页离基变量：是可行解！是否还是基本解？是第13页/共29页从而，目标函数得到了改善。第14页/共29页第四节 单纯形表第15页/共29页（1 1）建立初始单纯形表，假定）建立初始单纯形表，假定B=IB=I，b0b0 设设maxZ=cmaxZ=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n将目标函数改写为：将目标函数改写为：-Z+c-Z+c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n=0=0写成增广矩阵的形式写成增广矩阵的形式 第16页/共29页-Zx1x2xmxm+1xn右端检验数行-Z0-ZXBcjx1x2xmxm+1xnc1c2cmcm+1cnCB最后一行是检验数行，标出了对应决策变量xj的检验数第一行是价值系数行，标出了决策变量xj的价值系数cj第二行是标示行，标出了表中主体各行的含义。第一列标出了基变量的价值系数。第二列标出了当前基变量的名称。第三列是右端项，前m个元素是当前基本可行解的基变量的取值最小比值准则第17页/共29页-Z0-ZXBcjx1x2xmxm+1xnc1c2cmcm+1cnCB将初始数据填入上表，可得到初始单纯形表。观察检验数行，若所有的 ，则停止计算。否则进行下一步。1.1.检验当前基本可行解是否为最优解？检验当前基本可行解是否为最优解？最最优优性性判判别别定定理理第18页/共29页2.2.检验是否为无界解？检验是否为无界解？则该LP无最优解。3.3.选择进基变量选择进基变量从而从而x xm+tm+t是进基变量，是进基变量，p pm+tm+t为进基向量，并称表中为进基向量，并称表中p pm+tm+t所在的列为所在的列为主列主列。4.4.选择离基变量选择离基变量最小比值准则从而从而x xl l是离基变量，是离基变量，并称表中离基变量所在的行为并称表中离基变量所在的行为主行主行。5.5.基变换基变换主行和主列的交叉元素主行和主列的交叉元素称为主元素主元素a al,m+tl,m+t第19页/共29页-Z0-ZXBcjx1x2xmxm+1xnc1c2cmcm+1cnCBnmmnmmnmnmaaaaaass.0.00.1.00.0.10.0.0111,21,211,1+mmmbxcbxcbxc:222111c cl l x xl l b bl l 0 0 .0 a0 0 .0 al,m+1 l,m+1 .a .alnln 主行同除以al,m+t,即将主元素化为1将新的主行的(-ai,m+t)倍分别加到第i行，即将主列的其他元素化为0.将新的主行的 倍分别加到最后一行，即将xm+t的检验数化为0.第20页/共29页-Z0-ZXBcjx1x2xmxm+1xnc1c2cmcm+1cnCBnmmnmmnmnmaaaaaass.0.00.1.00.0.10.0.0111,21,211,1+mmmbxcbxcbxc:222111c cm+t m+t x xm+t m+t bbm+t m+t 0 0 .0 a0 0 .0 al,m+1 l,m+1 .a .alnln6.6.回到回到1,1,对新解作最优性检验。对新解作最优性检验。第21页/共29页例：用单纯形法求解线性规划问题解：标准化：以以对应的系数列向量对应的系数列向量构成一单位矩阵，取初始基构成一单位矩阵，取初始基为基变量，为基变量，为非基变量。为非基变量。第22页/共29页建立初始单纯行表 基变换 确定为离基变量，而为进基变量，以为主元素。第23页/共29页基变换 确定为离基变量，而为进基变量，以为主元素。第24页/共29页基变换 确定为离基变量，而为进基变量，以为主元素。第25页/共29页上表中检验数满足最优性条件，得到最优解：及最大值：第26页/共29页说 明用单纯形法从当前解迭代到下一个基本可行解时，两者之间只有一个基变量不同（从而也有一个非基变量不同），称两者为相邻的基本可行解（即相邻的顶点）。第27页/共29页 作 业P441.4 分别用图解法和单纯形法求解下述线性规划问题。第28页/共29页感谢您的观看！第29页/共29页
