运筹学-单纯形法.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/4/23,#,2024/11/19 周二,1,第,4,节 单纯形法计算步骤,2024/11/19 周二,2,Step 1,化为标准型，找出初始可行基，并列出初始单纯形表,上述初始单纯形表中，最后一行称为检验数,j,2024/11/19 周二,3,基,基向量,x,1,x,2,x,3,x,4,x,5,Z,可行解,图中点,B,1,P,3,P,4,P,5,0,0,8,16,12,0,O,B,2,P,2,P,4,P,5,0,4,0,16,-4,12,A,B,3,P,2,P,3,P,5,0,0,无解,B,4,P,2,P,3,P,4,0,3,2,16,0,9,Q,4,B,5,P,1,P,4,P,5,8,0,0,-16,12,16,C,B,6,P,1,P,3,P,5,4,0,4,0,12,8,Q,1,B,7,P,1,P,3,P,4,0,0,无解,B,8,P,1,P,2,P,5,4,2,0,0,4,14,Q,2,B,9,P,1,P,2,P,4,2,3,0,8,0,13,Q,3,B,10,P,1,P,2,P,3,4,3,-2,0,0,17,B,x,2,x,1,O,1,1,2,2,3,3,4,4,Q,1,Q,2,Q,3,Q,4,A,B,C,2024/11/19 周二,4,Step2,：,检查非基变量所对应的检验数,j,，若所有的,j,0,，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。,否则，转入下一步。,Step3,：,若存在一个,k,0,，,k,所对应的变量,x,k,的系数列向量,P,k,0(,即,P,k,中每一个分量,a,ik,0),，则该,LP,无有限最优解，停止计算。,否则，转入下一步。,Step4,：,进行可行基的迭代。,重复以上步骤,2024/11/19 周二,5,例,7,用单纯形法求解例,6,。,max z=2x,1,+3x,2,s.t.,x,1,+2x,2,+x,3,=8,4x,1,+x,4,=16,4x,2,+x,5,=12,x,j,0,，,j=1,2,5,2024/11/19 周二,6,练习：,分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。,Max Z=10 x,1,+5x,2,3x,1,+4x,2,9,5x,1,+2x,2,8,x,1,，,x,2,0,2024/11/19 周二,7,解：,cj,10,5,0,0,CB,XB,bi,x1,x2,x3,x4,0,x3,9,3,4,1,0,0,x4,8,5,2,0,1,j,10,5,0,0,3,8/5,0,X3,10,x1,8/5,1,2/5,0,1/5,21/5,0,14/5,1,-3/5,x1,入,x4,出,j,0,1,0,-2,x2,入,x3,出,3/2,4,5,X2,10,x1,j,1,1,0,-1/7,2/7,3/2,0,1,5/14,-3/14,0,0,-5/14,-25/14,所以：,X*=(x,1,x,2,),T,=(1,3/2),T,Z*=35/2,0:(0,0),C:(0,9/4),A:(8/5,0),B:(1,3/2),x1,x2,对应,0,对应,A,对应,B,2024/11/19 周二,8,回顾：单纯形法求解步骤：,2024/11/19 周二,9,第,5,节 单纯形法的进一步讨论,2024/11/19 周二,10,第,5,节 单纯形法的进一步讨论,一、人工变量法（大,M,法）,约束条件：,“,”,加一个松弛变量,“,”,减一个剩余变量后，再加一个人工变量,“,”,加一个人工变量,目标函数：,人工变量的系数为,“,M,”,，即罚因子,若线性规划问题有最优解则人工变量必为,0,。,2024/11/19 周二,11,MaxZ=-3x,1,+x,3,x,1,+x,2,+x,3,4,-2x,1,+x,2,-x,3,1,3x,2,+x,3,=9,x,i,0,j=1,2,3,增加人工变量后，线性规划问题中就存在一个,B,为单位矩阵，,后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x,1,+x,3,-Mx,6,-Mx,7,x,1,+x,2,+x,3,+x,4,=4,-2x,1,+x,2,-x,3,-x,5,+x,6,=1,3x,2,+x,3,+x,7,=9,x,i,0,j=1,7,标准化及变形,2024/11/19 周二,12,练习：,列出初始单纯形表，并求解第,2,小题的最优解,P55,，,2.2,（,1,）,2.,2024/11/19 周二,13,cj,-3,0,1,0,0,-M,-M,CB,XB,bi,x1,x2,x3,x4,x5,x6,x7,0,x4,4,1,1,1,1,0,0,0,-M,x6,1,-2,1,-1,0,-1,1,0,-M,x7,9,0,3,1,0,0,0,1,单纯形表,j,-3-2M,4M,1,0,0,3,x2,入，,x6,出,-M,0,4,1,0,x4,0,x2,-M,x7,3,3,0,2,1,1,-1,0,j,6M-3,0,4M+1,0,-4M,-,x1,入，,x7,出,3M,0,1,-2,1,-1,0,-1,1,0,1,6,6,0,4,0,3,-3,1,1,0,x4,0,x2,-3,x1,0,0,0,0,1,-1/2,1/2,-1/2,j,0,0,3,0,-M-3/2,9,x3,入，,x1,出,3/2,-M+1/2,3,0,1,1/3,0,0,0,1/3,3/2,1,1,0,2/3,0,1/2,-1/2,1/6,-,0,x4,0,x2,1,x3,0,0,0,0,1,-1/2,1/2,-1/2,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,5/2,-1/2,1,0,0,-1/4,1/4,1/4,3/2,3/2,0,1,0,3/4,-3/4,1/4,所以：,X*=(x,1,x,2,x,3,),T,=(0,5/2,3/2),T,Z*=3/2,2024/11/19 周二,14,二、两阶段法,第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为,1,，约束条件和原问题的一样。,当第一阶段中目标函数的最优值,0,，即人工变量,0,，则转入第二阶段；若第一阶段中目标函数的最优值不等于,0,，即人工变量不等于,0,，则判断原问题为无解。,第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,2024/11/19 周二,15,求解辅助问题，得到辅助问题的最优解,引进人工变量,x,6,，,x,7,，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,Max W=0?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x,1,+x,3,x,1,+x,2,+x,3,4,-2x,1,+x,2,-x,3,1,3x,2,+x,3,=9,x,i,0,j=1,2,3,Max W=-x,6,-x,7,x,1,+x,2,+x,3,+x,4,=4,-2x,1,+x,2,-x,3,-x,5,+x,6,=1,3x,2,+x,3,+x,7,=9,x,i,0,j=1,7,2024/11/19 周二,16,cj,0,0,0,0,0,-1,-1,CB,XB,bi,x1,x2,x3,x4,x5,x6,x7,0,x4,4,1,1,1,1,0,0,0,-1,x6,1,-2,1,-1,0,-1,1,0,-1,x7,9,0,3,1,0,0,0,1,(,第一阶段）单纯形表,1,j,-2,4,0,0,0,3,x2,入，,x6,出,-1,0,4,1,0,x4,0,x2,-1,x7,3,3,0,2,1,1,-1,0,j,6,0,4,0,-4,x1,入，,x7,出,3,0,1,-2,1,-1,0,-1,1,0,1,6,6,0,4,0,3,-3,1,1,0,x4,0,x2,0,x1,0,0,0,0,1,-1/2,1/2,-1/2,j,0,0,0,0,-1,0,-1,3,0,1,1/3,0,0,0,1/3,1,1,0,2/3,0,1/2,-1/2,1/6,所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。,2024/11/19 周二,17,（第二阶段）单纯形表,2,cj,-3,0,1,0,0,CB,XB,bi,x1,x2,x3,x4,x5,0,x4,0,0,0,0,1,-1/2,0,x2,3,0,1,1/3,0,0,-3,x1,1,1,0,2/3,0,1/2,j,0,0,3,0,3/2,-,9,3/2,0,X4,0,X2,1,x3,5/2,-1/2,1,0,0,-1/4,0,0,0,0,1,-1/2,3/2,3/2,0,1,0,3/4,x3,入，,x1,出,j,-9/2,0,0,0,-3/4,所以：,X*=(x,1,x,2,x,3,),T,=(0,5/2,3/2),T,Z*=3/2,2024/11/19 周二,18,单纯形法小结,给定,LP,问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第,1.3,节内容分,7,种情况：,取 值,右端项,等式或不等式,极大或极小,新加变量系数,x,j,无约束,x,j,0,b,i,0,，且所有的,a,ik,0,时；,得最优解时，有检验数为,0,的非基变量；,得最优解时，所有非基变量检验数为负；,2024/11/19 周二,21,cj,40,45,25,0,0,CB,XB,bi,x1,x2,x3,x4,x5,0,x4,100,2,3,1,1,0,0,x5,120,3,3,2,0,1,j,40,45,0,25,100/3,40,3,45,X2,25,x3,80/3,1/3,1,0,2/3,-1/3,20,1,0,1,-1,1,x2,入，,x4,出,j,0,0,0,-5,因为全,j,0,且,1=0,则有无穷多最优解。所以：其中一个最优解为,X*=(0,80/3,20,0,0),T,Z*=1700,例,1:,0,-10,思考：无穷多最优解的一般形式？,2024/11/19 周二,22,cj,1,1,0,0,CB,XB,bi,x1,x2,x3,x4,0,x3,100,-2,1,1,0,0,x4,50,1,-1,0,1,j,1,1,0,0,-,50,0,X3,1,x1,200,0,-1,1,2,50,1,-1,0,1,x1,入，,x4,出,j,0,2,0,-1,因为,2,=2,且,a,i2,全,0,所以：无界,例,2:,2024/11/19 周二,23,例,3:,下表为一极大化问题对应的单纯形表,讨论在,a1,a2,a3,a4,a5,a6,取何值的情况下，该表中的解为：,唯一最优解；,无穷多最优解；,无界；,无可行解；,非最优，继续换基：,X3,换入，,x2,换出,x,1,x,2,x,3,x,4,x,5,b,i,x,1,1,0,a,1,0,a,2,a,6,x,2,0,1,1,0,-2,2,x,4,0,0,-2,1,a,3,3,j,0,0,a,4,0,a,5,a40,a50,a20,a30,a40,a50,x4,或,x2,为人工变量，,a60,；,x1,为人工变量，,a60,a40,a4a5;a6/a12a10,a60 a1 0,2024/11/19 周二,24,复习题,：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中,aL,的值及各变量下标,mt,的值；,2024/11/19 周二,25,第,6,节 应用举例,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,.,要求解问题的目标函数能用数值指标来反映，且为线性函数；,.,存在着多种方案；,.,要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。,2024/11/19 周二,26,建模步骤,：,第一步：设置要求解的决策变量,。,决策变量选取得当，不仅能顺利地建立模型而且能方便地求解,，否则很可能事倍功半。,第二步：找出所有的限制,，即约束条件，,并用决策变量的线性方程或线性不等式来表示,。,第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。,决策变量的非负要求可以根据问题的实际意义加以确定。,2024/11/19 周二,27,一般的产品计划问题举例 例,1,：,某工厂生产,A,、,B,两种产品，均需经过两道工序，每生产一吨产品,A,需要经第一道工序加工,2,小时，第二道工序加工,3,小时；每生产一吨产品,B,需要经第一道工序加工,3,小时，第二道工序加工,4,小时。可供利用的第一道工序为,12,小时，第二道工序为,24,小时。,生产产品,B,的同时产出副产品,C,，每生产一吨产品,B,，可同时得到,2,吨产品,C,而毋需外加任何费用；副产品,C,一部分可以盈利，剩下的只能报废。,出售产品,A,每吨能盈利,400,元、产品,B,每吨能盈利,1000,元，每销售一吨副产品,C,能盈利,300,元，而剩余要报废的则每吨损失,200,元。经市场预测，在计划期内产品,C,最大销量为,5,吨。试列出线性规划模型，决定,A,、,B,两种产品的产量，使工厂总的利润最大。,2024/11/19 周二,28,数学模型：,设：,x,1,产品,A,的产量，,x,2,产品,B,的产量，,x,3,产品,C,的销售量，,x,4,产品,C,的报废量。依题意，可得,2024/11/19 周二,29,例,2,合理下料问题。,现要截取,2.9,米、,2.1,米和,1.5,米的圆钢各,100,根。而现在仅有一批长,7.4,米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。,根数,方案,需要,根数,长度,I,II,III,IV,V,VI,VII,VIII,2.9,1,2,0,1,0,1,0,0,100,2.1,0,0,2,2,1,1,3,0,100,1.5,3,1,2,0,3,1,0,4,100,合计,7.4,7.3,7.2,7.1,6.6,6.5,6.3,6,料头,0,0.1,0.2,0.3,0.8,0.9,1.1,1.4,解：依题意，在排除明显不合理的方案后。可以列出,8,种套裁方案，前,5,种更合理。,2024/11/19 周二,30,例,3,2024/11/19 周二,31,练习,1,：,练习,2,：,P57,，,T2.9,2024/11/19 周二,32,2024/11/19 周二,33,例,4.,连续投资问题。,P53,2-13,项目,第,1,年,第,2,年,第,3,年,第,4,年,第,5,年,投资回报率,投资额限制,A,x,1A,x,2A,x,3A,x,4A,115%,B,x,3B,125%,4,万元,C,x,2C,140%,3,万元,D,x,1D,x,2D,x,3D,x,4D,x,5D,公债利息,6%,投资总额：,10,万元,2024/11/19 周二,34,练习：,设某投资者有,30 000,元可供为期四年的投资，现有五个投资机会可供选择：,A:,可在每年年初投资，每年每元投资可获,0.2,元。,B:,第一年年初或第三年年初投资，每两年每元投资可获利润,0.5,元，两年后获利。,C:,第一年初投资，三年后每元投资获利,0.8,元。这项投资最多不超过,20 000,元。,D:,第二年年初投资，两年后每元投资可获利,0.6,元。这项投资最多不超过,15 000,元。,E:,第一年年初投资，四年后每元获利,1.7,元，这项投资最多不超过,20 000,元。,投资者应如何投资，使他在四年后所拥有资金总额最大？,2024/11/19 周二,35,第一章 总结,基本概念：,可行解，基，基解，基可行解，可行基，凸集，顶点,基本定理：,可行域为凸集；,基可行解 顶点；,最优解一定在顶点上取得。,2024/11/19 周二,36,基本问题：,什么是线性规划问题的数学模型结构？,如何用图解法及单纯形法判断解的情况？,什么是线性规划问题的标准型，如何化标准型？,如何求线性规划的基解，基可行解及最优解？,单纯形法的计算步骤？,什么情况要加入人工变量？,两阶段法的基本步骤？,2024/11/19 周二,37,单纯形法小结,给定,LP,问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第,1.3,节内容分,7,种情况：,取 值,右端项,等式或不等式,极大或极小,新加变量系数,x,j,无约束,x,j,0,b,i,0,=,minZ,x,s,x,a,令,x,j,=,x,j,-,x,j,x,j,0,x,j,0,令,x,j,=-,x,j,约束条件两端同乘以,-1,加松弛变量,x,s,加入人工变量,x,a,减去剩余变量,x,s,加入人工变量,x,a,令,z,=-,Z,minZ,=-,max,z,0,-M,2024/11/19 周二,38,添加松弛变量、人工变量列出初始单纯形表,所有,基变量中有,非零人工变量,某非基变量,检验数为零,唯一最优解,无穷多最优解,无可行解,对任一,有,换基继续,Y,Y,Y,Y,N,N,N,无界解,N,计算非基变量各列的,检验数,2024/11/19 周二,39,对任一,有,N,换基继续,令,计算所有非基变量的检验数,