运筹学 单纯形法1

2020/1/161第4节单纯形法计算步骤2020/1/162Step1化为标准型，找出初始可行基，并列出初始单纯形表•上述初始单纯形表中，最后一行称为检验数σj2020/1/163基基向量x1x2x3x4x5Z可行解图中点B1P3P4P500816120√OB2P2P4P504016-412╳AB3P2P3P500无解B4P2P3P40321609√Q4B5P1P4P5800-161216╳CB6P1P3P54040128√Q1B7P1P3P400无解B8P1P2P54200414√Q2B9P1P2P42308013√Q3B10P1P2P343-20017╳B5,,1,012416482x32max524132121jxxxxxxxxxzjx2x1O11223344Q1Q2Q3Q4ABC2020/1/164•Step2：检查非基变量所对应的检验数σj，若所有的σj≤0，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。•否则，转入下一步。•Step3：若存在一个σk0，σk所对应的变量xk的系数列向量Pk≤0(即Pk中每一个分量aik≤0)，则该LP无有限最优解，停止计算。•否则，转入下一步。•Step4：进行可行基的迭代。•重复以上步骤2020/1/165•例7用单纯形法求解例6。•maxz=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12xj≥0，j=1,2,…,52020/1/166练习：•分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。MaxZ=10x1+5x23x1+4x2≤95x1+2x2≤8x1，x2≥02020/1/167解：cj10500CBXBbix1x2x3x4θ0x3934100x485201σj10500[]38/5[]0X310x18/512/501/521/5014/51-3/5x1入,x4出σj010-2[]x2入,x3出3/245X210x1σj110-1/72/73/2015/14-3/1400-5/14-25/14所以：X*=(x1,x2)T=(1,3/2)TZ*=35/2[]0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2对应0对应A对应B2020/1/168回顾：单纯形法求解步骤：2020/1/169第5节单纯形法的进一步讨论2020/1/1610第5节单纯形法的进一步讨论一、人工变量法（大M法）约束条件：“≤”→加一个松弛变量“≥”→减一个剩余变量后，再加一个人工变量“＝”→加一个人工变量目标函数：人工变量的系数为“－M”，即罚因子若线性规划问题有最优解则人工变量必为0。2020/1/1611MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7标准化及变形2020/1/1612练习：列出初始单纯形表，并求解第2小题的最优解1.P55，2.2（1）2.2020/1/1613cj-30100-M-MCBXBbix1x2x3x4x5x6x7θ0x441111000-Mx61-21-10-110-Mx790310001单纯形表σj-3-2M4M100[]3x2入，x6出-M041[]0x40x2-Mx7330211-10σj6M-304M+10-4M[]-x1入，x7出3M01-21-10-1101660403-311[]0x40x2-3x100001-1/21/2-1/2σj0030-M-3/2[]9x3入，x1出3/2-M+1/23011/30001/33/21102/301/2-1/21/6-[]0x40x21x300001-1/21/2-1/2σj-9/2000-M+3/4-3/4-M-1/45/2-1/2100-1/41/41/43/23/20103/4-3/41/4所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/22020/1/1614二、两阶段法•第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。•当第一阶段中目标函数的最优值＝0，即人工变量＝0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。•第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。2020/1/1615求解辅助问题，得到辅助问题的最优解引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化MaxW=0?原问题没有可行解。把辅助问题的最优解作为原问题的初始基础可行解用单纯形法求解原问题，得到原问题的最优解否是两阶段法的算法流程图MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3MaxW=-x6-x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,72020/1/1616cj00000-1-1CBXBbix1x2x3x4x5x6x7θ0x441111000-1x61-21-10-110-1x790310001(第一阶段）单纯形表1σj-24000[]3x2入，x6出-1041[]0x40x2-1x7330211-10σj6040-4[]－x1入，x7出301-21-10-1101660403-311[]0x40x20x100001-1/21/2-1/2σj0000-10-13011/30001/31102/301/2-1/21/6所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。2020/1/1617（第二阶段）单纯形表2cj-30100CBXBbix1x2x3x4x5θ0x400001-1/20x23011/300-3x11102/301/2σj00303/2[]-93/2[]0X40X21x35/2-1/2100-1/400001-1/23/23/20103/4x3入，x1出σj-9/2000-3/4所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/22020/1/1618单纯形法小结•给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：取值右端项等式或不等式极大或极小新加变量系数xj无约束xj≤0bi0≤=≥minZxsxa令xj=xj′-xj″xj′≥0xj″≥0令xj′=-xj约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去剩余变量xs加入人工变量xa令z′=-ZminZ=-maxz′0-M2020/1/1619第5节单纯形法的进一步讨论人工变量法（大M法）和两阶段法约束条件：“≤”→加一个松弛变量“≥”→减一个剩余变量后，再加一个人工变量“＝”→加一个人工变量若线性规划问题有最优解则人工变量必为0。2020/1/1620•目标函数极小化时解的最优性判别；•无可行解的判别；•无界的判别；•无穷多最优解的判别；•唯一最优解的判别.三、单纯形法计算中的几个问题当所有非基变量的σj≥0时为最优解；最优解中人工变量为非0的基变量时；存在某个σk0，且所有的aik≤0时；得最优解时，有检验数为0的非基变量；得最优解时，所有非基变量检验数为负；2020/1/1621cj40452500CBXBbix1x2x3x4x5θ0x4100231100x512033201σj4045025100/340[3]45X225x380/31/3102/3-1/320101-11x2入，x4出σj000-5因为全σj≤0,且σ1=0,则有无穷多最优解。所以：其中一个最优解为X*=(0,80/3,20,0,0)T,Z*=1700例1:012023310032254540321321321321xxxxxxxxxtsxxxZ,,..max0-10……思考：无穷多最优解的一般形式？2020/1/16220x,x50xx100x2xs.t.xxmaxZ21212121cj1100CBXBbix1x2x3x4θ0x3100-21100x4501-101σj1100-50[]0X31x12000-112501-101x1入，x4出σj020-1因为σ2=2,且ai2全≤0所以：无界例2:2020/1/1623例3:下表为一极大化问题对应的单纯形表讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：唯一最优解；无穷多最优解；无界；无可行解；非最优，继续换基：X3换入，x2换出x1x2x3x4x5bix110a10a2a6x20110-22x400-21a33σj00a40a5•a40,a50,a6≥0•a6≥0,a4≤0,a5≤0,a4=0或a5=0•a6≥0,a50,a2≤0,a3≤0•a4≤0,a5≤0,x4或x2为人工变量，a6≥0；x1为人工变量，a60•a40,a4a5;a6/a12→a10a6≥0→a1≤02020/1/1624复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中a~L的值及各变量下标m~t的值；45,xx2020/1/1625第6节应用举例•一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。•⑴.要求解问题的目标函数能用数值指标来反映，且为线性函数；•⑵.存在着多种方案；•⑶.要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。2020/1/1626建模步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。•决策变量的非负要求可以根据问题的实际意义加以确定。2020/1/1627一般的产品计划问题举例例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两种产品的产量，使工厂总的利润最大。2020/1/1628数学模型：设：x1——产品A的产量，x2——产品B的产量，x3——产品C的销售量，x4——产品C的报废量。依题意，可得0,,,5224431232..231044321343221214321xxxxxxxxxxxxtsxxxxMaxZ2020/1/1629例2合理下料问题。–现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。根数方案需要根数长度IIIIIIIVVVIVIIVI