运筹学第二章

2020/5/11,1,运筹学,成都信息工程学院应用数学学院梅志红zhmei,2020/5/11,2,Chapter2单纯形法,单纯形法的基本思想单纯形法的计算过程人工变量法单纯形法补遗,本章主要内容：,2020/5/11,Mathematicalexperiment,3,单纯形法(SimplexMethod)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法单纯形法的求解线性规划问题,解决了三个技术问题:给出第一个基可行解;检验一个基可行解是否是最优解;转换到另一个基可行解。,2020/5/11,Mathematicalexperiment,4,2.1单纯形法求解线性规划的思路：,一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。,2020/5/11,Mathematicalexperiment,5,2020/5/11,Mathematicalexperiment,6,例1试以例1来讨论如何用单纯形法求解。例1的标准型为：,2020/5/11,Mathematicalexperiment,7,约束方程(1-12)式的系数矩阵,从(1-12)式中可以看到x3,x4,x5的系数列向量,2020/5/11,Mathematicalexperiment,8,P3,P4,P5是线性独立的，这些向量构成一个基对应于B的变量x3,x4,x5为基变量.,从(1-12)式中可以得到（1-13）,2020/5/11,Mathematicalexperiment,9,将(1-13)式代入目标函数(1-11),得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T这个基可行解表示：工厂没有安排生产产品、；资源都没有被利用，所以工厂的利润指标z=0。,2020/5/11,Mathematicalexperiment,10,从分析目标函数的表达式(1-14)可以看到,非基变量x1,x2(即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。,2020/5/11,Mathematicalexperiment,11,如何确定换入，换出变量,一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x50。,2020/5/11,Mathematicalexperiment,12,当x1=0,由(1-13)式得到,2020/5/11,Mathematicalexperiment,13,x2取何值时，才能满足非负要求,从(1-15)式中可以看出，只有选择x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。,2020/5/11,Mathematicalexperiment,14,以上数学描述说明了每生产一件产品，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。,2020/5/11,Mathematicalexperiment,15,为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换。得到,2020/5/11,Mathematicalexperiment,16,用高斯消去法,将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：,2020/5/11,Mathematicalexperiment,17,再将(1-17)式代入目标函数(1-11)式得到,2020/5/11,Mathematicalexperiment,18,从目标函数的表达式(1-18)中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：z=14-1.5x3-0.125x4(1-19),2020/5/11,Mathematicalexperiment,19,再检查(1-19)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件，工厂才能得到最大利润。,2020/5/11,Mathematicalexperiment,20,通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。,原例1的线性规划问题是二维的，即两个变量x1,x2；当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体(凸集)。,2020/5/11,Mathematicalexperiment,21,这凸多面体上的顶点，就是基可行解。,初始基可行解X(0)=(0,0,8,16,12)T就相当于图1-2中的原点(0，0)，X(1)=(0,3,2,16,0)T相当于图1-2中的Q4点(0，3)；,2020/5/11,Mathematicalexperiment,22,X(2)=(2，3，0，8，0)T相当于图1-2中的Q3点(2，3)，最优解X(3)=(4，2，0，0，4)T相当于图1-2中的Q2点(4，2)。从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)。这相当于图1-2中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。下面讨论一般线性规划问题的求解。,2020/5/11,Mathematicalexperiment,23,单纯形计算方法(SimplexMethod)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。,当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。,【例1.15】用单纯形法求下列线性规划的最优解,2.2普通单纯形法,2020/5/11,Mathematicalexperiment,24,【解】化为标准型，加入松驰变量x3、x4则标准型为,系数矩阵A及可行基B1,r(B1)=2，B1是一个初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0,0,40,30)T,2020/5/11,Mathematicalexperiment,25,以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作j,j=1,2,n。,本例中1=3,2=4,3=0,4=0。参看表1.4（a）。,最优解判断标准当所有检验数j0（j=1，n）时，基本可行解为最优解。,当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。,检验数目标函数用非基变量表达时的变量系数,2020/5/11,Mathematicalexperiment,26,进基列,出基行,bi/ai2，ai20,i,表1-4,基变量,1,10,0,0,1/3,0,1/3,10,5/3,1,-1/3,40,5/3,0,-4/3,30,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,将3化为1,乘以1/3后得到,30,18,2020/5/11,Mathematicalexperiment,27,最优解X=(18，4，0，0)T，最优值Z=70,O,20,30,10,40,(3,4),X(3)=(18,4),最优解X=(18,4),最优值Z=70,X(1)=(0,0),20,10,x2,x1,30,X(2)=(0,10),2020/5/11,Mathematicalexperiment,28,单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1.4）。,计算步骤：,1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；,2.判断：（a）若j（j，n）得到最解；（b）某个k0且aik（i=1，2,m）则线性规划具有无界解。（c）若存在k0且aik(i=1,m)不全非正，则进行换基；,2020/5/11,Mathematicalexperiment,29,第个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素；,(c）求新的基可行解：用初等行变换方法将aLk化为,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。,（b）选出基变量，求最小比值：,3.换基：（a）选进基变量设k=maxj|j0,xk为进基变量,2020/5/11,Mathematicalexperiment,30,【例2】用单纯形法求解,【解】将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，单纯法计算结果如表1.所示。,2020/5/11,Mathematicalexperiment,31,表15,1/3,1,5,0,1,20,3,0,17,1,3,75,1/3,0,9,0,2,M,20,25,60,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解X=(25，35/3，0，0，0)T，最优值Z=145/3,2020/5/11,Mathem