对偶与对偶单纯形法的应用

关于对偶与对偶单纯形法的应用第一页，共五十六页，2022年，8月28日一、对偶问题的提出每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。原问题：某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、C台时如表所示，该工厂每生产一单位产品可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？第二页，共五十六页，2022年，8月28日解：设x1为产品I的计划产量，x2产品Ⅱ的计划产量，则有Maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0第三页，共五十六页，2022年，8月28日假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？对原厂：租金收入≥自己组织生产的收入对租借厂：总租金最低变量改变——产品——设备设备不再是约束条件，必须从产品入手设y1，y2，y3是A、B、C每小时的出租价格对于产品I：每件I自行生产的收入是50元，租金收入是y1+2y2元。对于产品Ⅱ来说，自行生产收入100元，租金收入是y1+y2+y3元第四页，共五十六页，2022年，8月28日Minw=300y1+400y2+250y3（设备租用总收入）

S.Ty1+2y2≥50y1+y2+y3≥100其中y1，y2，y3均≥0比较一下与原线性规划问题的不同？1、目标函数

2、变量

3、约束条件第五页，共五十六页，2022年，8月28日这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。矩阵形式比较：解1：MaxZ=CXAX≤bX≥0

解2：minW=b`YA`

Y≥C`Y≥0第六页，共五十六页，2022年，8月28日二、原问题和对偶问题的转化1、目标函数MAX——Min2、约束条件——变量约束条件n个——变量n个约束条件≥0——变量≤0约束条件≤0——变量≥0约束条件=0——变量无约束要点：max为反向关系（约束条件——变量）第七页，共五十六页，2022年，8月28日3、变量——约束条件变量m个——约束条件m个变量≥0——约束条件≥0变量≤0——约束条件≤0变量无约束——约束条件=04、目标函数中变量的系数C为对偶问题中约束条件的右端常数项b，个数对等变动。第八页，共五十六页，2022年，8月28日记忆要点：1、把握“三要素”，目标函数、约束条件——变量、C-b的转化。2、把握重点——变量与约束条件的关系。（1）约束条件=0的情况，变量无约束。（2）在约束条件≠0时候，看原问题目标函数。1）max：约束条件——变量，反向；变量——约束条件，正向。（反正）2）min：约束条件——变量，正向；变量——约束条件，反向。（正反）第九页，共五十六页，2022年，8月28日记忆宝典：1、Max——Min2、C——b3、无约束等于0，个数m变n。4、max就反正，min就正反。（约束条件——变量）第十页，共五十六页，2022年，8月28日示例：转化为对偶问题第十一页，共五十六页，2022年，8月28日第一种做法：按照定义来第十二页，共五十六页，2022年，8月28日其中第三个条件用两个式子替代。第十三页，共五十六页，2022年，8月28日第十四页，共五十六页，2022年，8月28日第十五页，共五十六页，2022年，8月28日第十六页，共五十六页，2022年，8月28日用所学原则写一次？第十七页，共五十六页，2022年，8月28日示例2：写出下列问题的对偶问题：minz=7x1+4x2-3x3S.T-4x1+2x2-6x3≤24-3x1-6x2-4x3≥155x2+3x3=30其中，x1≤0，x2无约束，x3≥0第十八页，共五十六页，2022年，8月28日Maxz=24y1+15y2+30y3S.T-4y1-3y2≥72y1-6y2+5y3=4-6y1-4y2+3y3≤-3y1≤0，y2≥0，y3取值无约束第十九页，共五十六页，2022年，8月28日三、对偶问题的性质

（一）对称性。对偶问题的对偶问题是原问题。（类似于“负负得正”）Minw=300y1+400y2+250y3S.Ty1+2y2≥50y1+y2+y3≥100其中y1，y2，y3均≥0其对偶问题是？第二十页，共五十六页，2022年，8月28日Maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0第二十一页，共五十六页，2022年，8月28日（二）若原问题为（弱对偶性定理）maxZ=CXAX≤bX≥0其对偶问题为Minw=YbYA≥CY≥0若X为原问题任一可行解，Y为对偶问题任一可行解，则必有CX≤Yb第二十二页，共五十六页，2022年，8月28日弱对偶性定理的意义：原问题任一个可行解是对偶问题最优目标函数值的一个下界。反过来说：对偶问题的任一个可行解是原问题目标函数值的一个上界。理解：（1）很多个界。（2）看目标函数的类型判断。第二十三页，共五十六页，2022年，8月28日（三）若原问题为（无界性定理）maxZ=CXAX≤bX≥0其对偶问题为Minw=YbYA≥CY≥0若原问题有可行解，则目标函数为无界解的充要条件是对偶问题无可行解。第二十四页，共五十六页，2022年，8月28日（四）若X和Y分别为原问题和对偶问题的可行解，当CX=Yb（目标函数值相同）时，则X和Y分别为原问题和对偶问题的最优解。（最优性定理）一般情况下是：CX≤Yb，当取=时，Yb最小，CX最大。第二十五页，共五十六页，2022年，8月28日（五）若原问题和对偶问题具有可行解，若原问题或对偶问题之一有最优解，则另一个对偶问题也必有最优解，且最优值相同。（主对偶性定理）证明含义：若原问题有一个对应于基B的最优解，则CBB-1为对偶问题的最优解。第二十六页，共五十六页，2022年，8月28日（六）若X，Y为原问题和对偶问题的的可行解，则X，Y为最优解的充要条件是V*X=0，Y*U=0，其中V是对偶问题的剩余变量，U是原问题的松弛变量。（互补松弛性定理）第二十七页，共五十六页，2022年，8月28日（七）原问题在单纯性法迭代过程中的检验数对应于对偶问题的一个基本解。（对应性定理）原问题XBXNXS

对应基B检验数0CN-CBB-1BN–CBB-1对偶问题的变量-YS1-YS2-Y第二十八页，共五十六页，2022年，8月28日原问题：maxZ=12x1+8x2+5x33x1+2x2+x3≤20x1+x2+x3≤1112x1+4x2+x3≤5x1，x2，x3≥0标准化：maxZ=12x1+8x2+5x33x1+2x2+x3+x4=20x1+x2+x3+x5=1112x1+4x2+x3+x6=5x1，x2，x3，x4，x5

，x6≥0第二十九页，共五十六页，2022年，8月28日Minw=20y1+11y2+5y33y1+y2+12y3

≥122y1+4y2+y3

≥8y1+y2+y3

≥5y1，y2，y3≥0Maxf=-20y1-11y2-5y33y1+y2+12y3–y4=122y1+4y2+y3-y5=8y1+y2+y3-y6

=5y1，y2，y3，y4，y5，y6≥0第三十页，共五十六页，2022年，8月28日原问题的松弛变量（XS）=对偶问题的变量原问题的变量=对偶问题的剩余变量（YS）第三十一页，共五十六页，2022年，8月28日X（1）=（0,0,0,20,11,48）Y（1）=（0,0,0，-12，-8，-5）X（2）=（4,0,0,8,7,0）Y（2）=（0,0,1，0，-4，-4）X（3）=（4/3,8,0,0,5/3,0）Y（3）=（4,0,0，0，0，-1）X（4）=（2,5,4,0,0,0）Y（4）=（12/5,12/5,1/5，0，0，0）第三十二页，共五十六页，2022年，8月28日对偶问题性质的启示原问题对偶问题有最优解有最优解无可行解无可行解有可行解无上界无有限最优解无有限最优解有可行解但无下界第三十三页，共五十六页，2022年，8月28日四、对偶问题经济学含义——影子价格因为Z*=Y*=Yb所以：ΔZ/Δb=Yb——资源的量Z——目标函数经济学含义：资源每变动一个单位，目标函数（利润、总产值等）变动的大小。资源对生产做出的贡献。（影子价格）是对现有资源实现最大效益的一个评价，叫机会成本。第三十四页，共五十六页，2022年，8月28日五、对偶单纯形法思路：单纯性法的解题思路：从可行域的一个顶点（基本可行解）通过迭代（初等行变换）换到另一个顶点（基本可行解），保持顶点的最优性不变（每一个顶点所取得的目标函数值处于增加（max）或者减少（min）的情况，直到取得最优解（目标函数值不可能继续增大（减少）=所有变量的检验数全部≤0。第三十五页，共五十六页，2022年，8月28日按照对偶问题的性质7来说，当原问题获得一个基本可行解（顶点）时，对偶问题获得一个基本解。当对偶问题获得基本解，同时也为可行解时，原问题的检验数全部≤0，即原问题获得最优解。第三十六页，共五十六页，2022年，8月28日作业题中原问题与对偶问题解之间的关系。x1x2x3x4x5x6y1y2y3y4y5y60002011480000004008700-4-40014/38005/3000-140025400000012/512/51/5从顶点1迭代到顶点4，对偶问题一直是基本解，当为基本可行解的时候，原问题和对偶问题共同取得最优解。第三十七页，共五十六页，2022年，8月28日对偶单纯性法的思想：根据原问题对偶问题的特性（主对偶定理、最优性定理、对应性定理），用单纯性法求解线性规划问题（单纯性法的一种）。解题思路：每次迭代中，保持对偶问题的解是可行解，不管原问题的基本解是否为基本可行解，当原问题取得基本可行解时，则这个解是原问题的最优解。第三十八页，共五十六页，2022年，8月28日二、例题例:用对偶单纯性法求解线性规划问题。Minw=12y1+16y2+15y32y1+4y2≥22y1+5y3≥3y1，y2，y3≥0在不用对偶单纯性法之前，用什么方法，请写出初始单纯性表？第三十九页，共五十六页，2022年，8月28日用“大M”法，或者二阶段法。（必须用“人工变量法”）MaxZ=-12y1-16y2-15y3+0y4+0y5-My6-My72y1+4y2-y4+y5=22y1+5y3-y6+y7=3y1，y2，y3，y4，y5，y6，y7≥0第四十页，共五十六页，2022年，8月28日用对偶单纯性解题：第一步：化成“标准型”Maxz=-12y1-16y2-15y3+0y4+0y5-2y1-4y2+y4=-2-2y1-5y3+y5=-3y1,y2,y3,y4,y5≥0bi≤0添加的人工变量不一样。第四十一页，共五十六页，2022年，8月28日初始对偶单纯性表ci-12-16-1500CBBby1y2y3y4y50y4-2-2-40100y5-3-20-501

δ-12-16-1500确定出基变量：bk=min{bi,bi<0}=min{-2，-3}=-3;确定进基变量：θ=min{δ/akj,akj<0}={-15/-5}从而确定主元素akr，以此为中心做初等行变换。第四十二页，共五十六页，2022年，8月28日对偶单纯性表2ci-12-16-1500CBBby1y2y3y4y50y4-2-2-4010-15y33/52/5010-1/5

δ-6-1600-3确定出基变量：bk=min{bi,bi<0}=min{-15}=-15;确定进基变量：θ=min{δ/akj,akj<0}={-6/-2,-16/-4}=3确定主元素是akr=-2。第四十三页，共五十六页，2022年，8月28日对偶单纯性表3ci-12-16-1500CBBby1y2y3y4y5-12y1

1120-1/20-15y3

1/50-4/511/5-1/5

δ0-40-3-3因为所有bi>0，此时，原问题取得基本可行解，即目标函数值达到最优。第四十四页，共五十六页，2022年，8月28日对偶单纯性法和一般单纯性法的区别：相同点：解题步骤一样建立初始单纯性表——判断是否最优——选定进出基变量——初等行变换（迭代）——单纯性表最优。不同点：思路不同，步骤不同。一般单纯性法：原问题保持基本可行解不变，直到对偶问题由基本解取得基本可行解。第四十五页，共五十六页，2022年，8月28日对偶单纯性法的要点1、单纯性法的一种（利用原问题对偶问题的性质求解），并不是求解原问题的对偶问题的单纯性法。（针对的还是原问题）2、适用的范围（适用条件很苛刻）：（1）原问题约束条件有≥0；（2）目标函数价值系数max函数，且Ci≤0（原问题的对偶问题是基本可行解）。不必引入人工变量，简化计算。第四十六页，共五十六页，2022年，8月28日对偶单纯性法：保持对偶问题为基本可行解，直到原问题由基本解变成基本可行解。解题思路正好相反。2、具体解题步骤（1）判断最优性的标准一般单纯性法：当前表中所有变量的检验数（主要指非基变量）≤0。相当于对偶问题取得基本可行解。对偶单纯性法：当前表中所有bi≥0。相当于原问题取得基本可行解。第四十七页，共五十六页，2022年，8月28日（2）确定主元素（进出基变量）1）次序不一样。一般单纯性法：先确定进基变量——再确定出基变量。（先进后出——先纵向后横向）对偶单纯性法：先确定出基变量——再确定进基变量。（先出后进——先横向后纵向）2）确定进基变量一般单纯性法：max(бj＞0)=σk，确定xk为进基变量。（首先进行——横向对比）对偶单纯性法：min{δ/akj,akj<0}=ө，确定akj为进基变量。（第二步进行——横向对比）第四十八页，共五十六页，2022年，8月28日3）确定出基变量一般单纯性法：min{bi/aik,aik>0}=ө，确定ajk为出基变量。（第二步进行——纵向对比）对偶单纯性法：min{bj<0}=bk

，确定bk为出基变量。（首先进行——纵向对比）进基都是横向对比，出基都是纵向对比第四十九页，共五十六页，2022年，8月28日对偶单纯性法步骤记忆要点1、最优看Bi（≥0）；2、先出后进；3、出基纵向比bi；进基横向比δ（aik>0）；4、进出基最小化原则；第五十页，共五十六页，2022年，8月28日练习：P125页minf=x1+2x2+3x2x1-x2+x3≥4x1+x2+2x3≤8x2-x3≥2X1，x2，x3≥0第五十一页，共五十六页，2022年，8月28日第一步：化成“标准型”minz=-x1-2x2-3x2-x1+x2-x3+x4=-4x1+x2+2x3+x5=8-x2+x3+x6=-2X1，x2，x3，x4，x5，x6≥0第五十二页，共五十六页，2022年，8月28日初始对偶单纯性表ci-1-2-3000CBBbx1x2x3x4x5x60x4

-4

-11-11000x581120100x6-20-11001-Z0-1