运筹学 单纯形法VIP

08.06.2020,1,第4节单纯形法计算步骤,08.06.2020,2,Step1化为标准型，找出初始可行基，并列出初始单纯形表,上述初始单纯形表中，最后一行称为检验数j,08.06.2020,3,08.06.2020,4,Step2：检查非基变量所对应的检验数j，若所有的j0，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。否则，转入下一步。Step3：若存在一个k0，k所对应的变量xk的系数列向量Pk0(即Pk中每一个分量aik0)，则该LP无有限最优解，停止计算。否则，转入下一步。Step4：进行可行基的迭代。重复以上步骤,08.06.2020,5,例7用单纯形法求解例6。maxz=2x1+3x2,s.t.,x1+2x2+x3=84x1+x4=164x2+x5=12xj0，j=1,2,5,08.06.2020,6,练习：,分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。,MaxZ=10 x1+5x23x1+4x295x1+2x28x1，x20,08.06.2020,7,解：,j,10,5,0,0,3,8/5,x1入,x4出,j,0,1,0,-2,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2)TZ*=35/2,对应0,对应A,对应B,08.06.2020,8,回顾：单纯形法求解步骤：,08.06.2020,9,第5节单纯形法的进一步讨论,08.06.2020,10,第5节单纯形法的进一步讨论,一、人工变量法（大M法）约束条件：“”加一个松弛变量“”减一个剩余变量后，再加一个人工变量“”加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。,08.06.2020,11,MaxZ=-3x1+x3x1+x2+x34-2x1+x2-x313x2+x3=9xi0,j=1,2,3,增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi0,j=1,7,标准化及变形,08.06.2020,12,练习：列出初始单纯形表，并求解第2小题的最优解P55，2.2（1）2.,08.06.2020,13,单纯形表,j,-3-2M,4M,1,0,0,3,x2入，x6出,-M,0,4,1,j,6M-3,0,4M+1,0,-4M,-,x1入，x7出,3M,0,1,1,j,0,0,3,0,-M-3/2,9,x3入，x1出,3/2,-M+1/2,3/2,-,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/2,08.06.2020,14,二、两阶段法第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，即人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,08.06.2020,15,求解辅助问题，得到辅助问题的最优解,引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,MaxW=0?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3x1+x2+x34-2x1+x2-x313x2+x3=9xi0,j=1,2,3,MaxW=-x6-x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi0,j=1,7,08.06.2020,16,(第一阶段）单纯形表1,j,-2,4,0,0,0,3,x2入，x6出,-1,0,4,1,j,6,0,4,0,-4,x1入，x7出,3,0,1,1,j,0,0,0,0,-1,0,-1,所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。,08.06.2020,17,（第二阶段）单纯形表2,j,0,0,3,0,3/2,-,9,3/2,x3入，x1出,j,-9/2,0,0,0,-3/4,所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/2,08.06.2020,18,单纯形法小结,给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：,08.06.2020,19,第5节单纯形法的进一步讨论,人工变量法（大M法）和两阶段法约束条件：“”加一个松弛变量“”减一个剩余变量后，再加一个人工变量“”加一个人工变量若线性规划问题有最优解则人工变量必为0。,08.06.2020,20,目标函数极小化时解的最优性判别；无可行解的判别；无界的判别；无穷多最优解的判别；唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解；,最优解中人工变量为非0的基变量时；,存在某个k0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,08.06.2020,21,j,40,45,0,25,100/3,40,3,x2入，x4出,j,0,0,0,-5,因为全j0,且1=0,则有无穷多最优解。所以：其中一个最优解为X*=(0,80/3,20,0,0)T,Z*=1700,例1:,0,-10,思考：无穷多最优解的一般形式？,08.06.2020,22,j,1,1,0,0,-,50,x1入，x4出,j,0,2,0,-1,因为2=2,且ai2全0所以：无界,例2:,08.06.2020,23,例3:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：唯一最优解；无穷多最优解；无界；无可行解；非最优，继续换基：X3换入，x2换出,a40,a20,a30a40,a50,x4或x2为人工变量，a60；x1为人工变量，a60a40,a4a5;a6/a12a10a60a10,08.06.2020,24,复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中aL的值及各变量下标mt的值；,08.06.2020,25,第6节应用举例,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。.要求解问题的目标函数能用数值指标来反映，且为线性函数；.存在着多种方案；.要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。,08.06.2020,26,建模步骤：,第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。,08.06.2020,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两种产品的产量，使工厂总的利润最大。,08.06.2020,28,数学模型：,设：x1产品A的产量，x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得,08.06.2020,29,例2合理下料问题。现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。,解：依题意，在排除明显不合理的方案后。可以列出8种套裁方案，前5种更合理。,08.06.2020,30,例3,08.06.2020,31,练习1：,练习2：P57，T2.9,08.06.2020,32,08.06.2020,33,例4.连续投资问题。P53,2-13,08.06.2020,34,练习：,设某投资者有30000元可供为期四年的投资，现有五个投资机会可供选择：A:可在每年年初投资，每年每元投资可获0.2元。B:第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。C:第一年初投资，三年后每元投资获利0.8元。这项投资最多不超过20000元。D:第二年年初投资，两年后每元投资可获利0.6元。这项投资最多不超过15000元。E:第一年年初投资，四年后每元获利1.7元，这项投资最多不超过20000元。投资者应如何投资，使他在四年后所拥有资金总额最大？,08.06.2020,35,第一章总结,基本概念：可行解，基，基解，基可行解，可行基，凸集，顶点基本定理：可行域为凸集；基可行解顶点；最优解一定在顶点上取得。,08.06.2020,36,基本问题：,什么是线性规划问题的