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

单纯形法

迭代原理运筹学4单纯形法迭代原理三.单纯形法的基本思想

1、顶点的逐步转移

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

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

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？运筹学4单纯形法迭代原理

转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值

2．需要解决的问题：

(1)为了使目标函数逐步变优，怎么转移？

(2)目标函数何时达到最优——

判断标准是什么？

运筹学4单纯形法迭代原理解LP问题单纯形法的基本思路：

初始可行基：设法在约束矩阵中构造出一个m阶单位阵初始基本可行解检验数进基变量：检验数离基变量：最小比值准则运筹学4单纯形法迭代原理1.确定初始基本可行解

LP:？希望在化LP的标准形式时，A中都含有一个m阶单位阵。运筹学4单纯形法迭代原理观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束

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

非基变量取0，算出基变量，搭配在一起构成初始基本可行解：运筹学4单纯形法迭代原理2.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的新基本可行解—当前解—是否为最优解？一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式

为：典式若运筹学4单纯形法迭代原理用非基变量表示目标函数的表达式：

典式检验数运筹学4单纯形法迭代原理其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理

运筹学4单纯形法迭代原理3、进行基变换（1）进基变量的确定——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善。（2）离基变量的确定——在保持解的可行性的前提下，使目标函数较快增大。运筹学4单纯形法迭代原理>

=

<当时，为使，需要从而，最大可取到最小比值原则则该LP无最优解。运筹学4单纯形法迭代原理离基变量：是可行解！是否还是基本解？是运筹学4单纯形法迭代原理从而，目标函数得到了改善。运筹学4单纯形法迭代原理第四节单纯形表运筹学4单纯形法迭代原理（1）建立初始单纯形表，假定B=I，b≥0

设maxZ=c1x1+c2x2+…+cnxn将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0写成增广矩阵的形式

运筹学4单纯形法迭代原理-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是检验数行，标出了对应决策变量xj的检验数第一行是价值系数行，标出了决策变量xj的价值系数cj第二行是标示行，标出了表中主体各行的含义。第一列标出了基变量的价值系数。第二列标出了当前基变量的名称。第三列是右端项，前m个元素是当前基本可行解的基变量的取值最小比值准则运筹学4单纯形法迭代原理-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB将初始数据填入上表，可得到初始单纯形表。观察检验数行，若所有的，则停止计算。否则进行下一步。1.检验当前基本可行解是否为最优解？最优性判别定理运筹学4单纯形法迭代原理2.检验是否为无界解？则该LP无最优解。3.选择进基变量从而xm+t是进基变量，pm+t为进基向量，并称表中pm+t所在的列为主列。4.选择离基变量最小比值准则从而xl是离基变量，并称表中离基变量所在的行为主行。5.基变换主行和主列的交叉元素称为主元素al,m+t运筹学4单纯形法迭代原理-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.运筹学4单纯形法迭代原理-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,对新解作最优性检验。运筹学4单纯形法迭代原理例：用单纯形法求解线性规划问题解：

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

运筹学4单纯形法迭代原理建立初始单纯行表[]基变换[]确定为离基变量，而为进基变量，以为主元素。运筹学4单纯形法迭代原理基变换[][]确定为离基变量，而为进基变量，以为主元素。运筹学4单纯形法迭代原理基变换[]确定为离基变量，而为进基变量，以为主元素。运筹学4单纯形法迭代原理上表中检验数满足最优性条件，得到最优解：及最大值：运筹学4单纯形法迭代原理说明用单纯形法从当前解迭代到