运筹学4单纯形法迭代原理教学课件

单纯形法

迭代原理1单纯形法

迭代原理1三.单纯形法的基本思想

1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。2三.单纯形法的基本思想

1、顶点的逐步转移

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？3根据线性规划问题的可行域是凸多边形或凸多面体转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值

2．需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优——判断标准是什么？

4转移条件？解LP问题单纯形法的基本思路：

初始可行基：设法在约束矩阵中构造出一个m阶单位阵初始基本可行解检验数进基变量：检验数离基变量：最小比值准则5解LP问题单纯形法的基本思路：初始可行基：设法在约束矩阵1.确定初始基本可行解

LP:？希望在化LP的标准形式时，A中都含有一个m阶单位阵。61.确定初始基本可行解LP:？希望在化LP的标观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束

——将新增的松弛变量(+)作为初始基变量，对应的系数列向量构成单位阵；LP限制条件有“≥”类型的约束——左端新增剩余变量(-)后，再加上一个非负的新变量—人工变量。LP限制条件有“=”类型的约束——直接在左端加上人工变量。7观察法7在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目标函数上做些“修正”——大M法或两阶段法

非基变量取0，算出基变量，搭配在一起构成初始基本可行解：8在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目2.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的新基本可行解—当前解—是否为最优解？一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式

为：典式若92.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的用非基变量表示目标函数的表达式：

典式检验数10用非基变量表示目标函数的表达式：典式检验数10其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理

11其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理3、进行基变换（1）进基变量的确定——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善。（2）离基变量的确定——在保持解的可行性的前提下，使目标函数较快增大。123、进行基变换（1）进基变量的确定——原则：正检验数（或最大>

=

<当时，为使，需要从而，最大可取到最小比值原则则该LP无最优解。13>=<当时，为离基变量：是可行解！是否还是基本解？是14离基变量：是可行解！是否还是基本解？是14从而，目标函数得到了改善。15从而，目标函数得到了改善。15第四节单纯形表16第四节单纯形表16（1）建立初始单纯形表，假定B=I，b≥0设maxZ=c1x1+c2x2+…+cnxn将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0写成增广矩阵的形式

17（1）建立初始单纯形表，假定B=I，b≥0将目标函数改写为：-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是检验数行，标出了对应决策变量xj的检验数第一行是价值系数行，标出了决策变量xj的价值系数cj第二行是标示行，标出了表中主体各行的含义。第一列标出了基变量的价值系数。第二列标出了当前基变量的名称。第三列是右端项，前m个元素是当前基本可行解的基变量的取值最小比值准则18-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBc-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB将初始数据填入上表，可得到初始单纯形表。观察检验数行，若所有的，则停止计算。否则进行下一步。1.检验当前基本可行解是否为最优解？最优性判别定理19-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc2.检验是否为无界解？则该LP无最优解。3.选择进基变量从而xm+t是进基变量，pm+t为进基向量，并称表中pm+t所在的列为主列。4.选择离基变量最小比值准则从而xl是离基变量，并称表中离基变量所在的行为主行。5.基变换主行和主列的交叉元素称为主元素al,m+t202.检验是否为无界解？则该LP无最优解。3.选择进基变量从而-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnmaaaaaass...0...00...1...00............0...10...0...0111,21,211,1++++mmmbxcbxcbxc:::222111clxlbl00...0al,m+1...aln[]主行同除以al,m+t,即将主元素化为1将新的主行的(-ai,m+t)倍分别加到第i行，即将主列的其他元素化为0.将新的主行的倍分别加到最后一行，即将xm+t的检验数化为0.21-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnma'a'a'a'a'a'ss...0...00...1...00............0...10...0...0111,21,211,1++++mmmb'xcb'xcb'xc:::222111cm+txm+tb'm+t00...0a'l,m+1...a'ln''6.回到1,对新解作最优性检验。22-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cm例：用单纯形法求解线性规划问题解：

标准化：以对应的系数列向量构成一单位矩阵，取初始基为基变量，为非基变量。

23例：用单纯形法求解线性规划问题解：标准化：以对应的系数列向建立初始单纯行表[]基变换[]确定为离基变量，而为进基变量，以为主元素。24建立初始单纯行表[]基变换[]确定为离基变量基变换[][]确定为离基变量，而为进基变量，以为主元素。25基变换[][]确定为离基变量，而为进基变基变换[]确定为离基变量，而为进基变量，以为主元素。26基变换[]确定为离基变量，而为进基变量，以为主元素上表中检验数满足最优性条件，得到最优解：及最大值：27上表中检验数满足最优性条件，得到最优解：及最大值：27说明用单纯形法从当前解迭代到下一个基本可行解时，两者之间只有一个基变量不同（从而也有一个非基变量不同），称两者为相邻的基本可行解（即相邻的顶点）。28说明28

作业P441.4分别用图解法和单纯形法求解下述线性规划问题。29

单纯形法

迭代原理30单纯形法

迭代原理1三.单纯形法的基本思想

1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。31三.单纯形法的基本思想

1、顶点的逐步转移

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？32根据线性规划问题的可行域是凸多边形或凸多面体转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值

2．需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优——判断标准是什么？

33转移条件？解LP问题单纯形法的基本思路：

初始可行基：设法在约束矩阵中构造出一个m阶单位阵初始基本可行解检验数进基变量：检验数离基变量：最小比值准则34解LP问题单纯形法的基本思路：初始可行基：设法在约束矩阵1.确定初始基本可行解

LP:？希望在化LP的标准形式时，A中都含有一个m阶单位阵。351.确定初始基本可行解LP:？希望在化LP的标观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束

——将新增的松弛变量(+)作为初始基变量，对应的系数列向量构成单位阵；LP限制条件有“≥”类型的约束——左端新增剩余变量(-)后，再加上一个非负的新变量—人工变量。LP限制条件有“=”类型的约束——直接在左端加上人工变量。36观察法7在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目标函数上做些“修正”——大M法或两阶段法

非基变量取0，算出基变量，搭配在一起构成初始基本可行解：37在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目2.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的新基本可行解—当前解—是否为最优解？一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式

为：典式若382.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的用非基变量表示目标函数的表达式：

典式检验数39用非基变量表示目标函数的表达式：典式检验数10其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理

40其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理3、进行基变换（1）进基变量的确定——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善。（2）离基变量的确定——在保持解的可行性的前提下，使目标函数较快增大。413、进行基变换（1）进基变量的确定——原则：正检验数（或最大>

=

<当时，为使，需要从而，最大可取到最小比值原则则该LP无最优解。42>=<当时，为离基变量：是可行解！是否还是基本解？是43离基变量：是可行解！是否还是基本解？是14从而，目标函数得到了改善。44从而，目标函数得到了改善。15第四节单纯形表45第四节单纯形表16（1）建立初始单纯形表，假定B=I，b≥0设maxZ=c1x1+c2x2+…+cnxn将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0写成增广矩阵的形式

46（1）建立初始单纯形表，假定B=I，b≥0将目标函数改写为：-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是检验数行，标出了对应决策变量xj的检验数第一行是价值系数行，标出了决策变量xj的价值系数cj第二行是标示行，标出了表中主体各行的含义。第一列标出了基变量的价值系数。第二列标出了当前基变量的名称。第三列是右端项，前m个元素是当前基本可行解的基变量的取值最小比值准则47-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBc-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB将初始数据填入上表，可得到初始单纯形表。观察检验数行，若所有的，则停止计算。否则进行下一步。1.检验当前基本可行解是否为最优解？最优性判别定理48-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc2.检验是否为无界解？则该LP无最优解。3.选择进基变量从而xm+t是进基变量，pm+t为进基向量，并称表中pm+t所在的列为主列。4.选择离基变量最小比值准则从而xl是离基变量，并称表中离基变量所在的行为主行。5.基变换主行和主列的交叉元素称为主元素al,m+t492.检验是否为无界解？则该LP无最优解。3.选择进基变量从而-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnmaaaaaass...0...00...1...00............0...10...0...0111,21,211,1++++mmmbxcbxcbxc:::222111clxlbl00...0al,m+1...aln[]主行同除以al,m+t,即将主元素化为1将新的主行的(-ai,m+t)倍分别加到第i行，即将主列的其他元素化为0.将新的主行的倍分别加到最后一行，即将xm+t的检验数化为0.50-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmc-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnma'a'a'a'a'a'ss...0...00...1...00............0...1