2.3-对偶问题的提出

对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。例如：（1）周长一定，面积最大的矩形是正方形。（2）面积一定，周长最短的矩形是正方形。这是互为对偶关系的表述。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义对偶性是线性规划问题的最重要的内容之一对偶问题概念：任何一个线性规划问题都有一个与之相对应的另一个线性规划问题，如果前者称为原问题，后者就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述。其最优解与原问题的最优解有着密切的联系:在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。【例1】最优生产计划问题。某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?ⅠⅡ设备原料A原料B1402048台时16kg12kg一对偶问题的提出数学模型maxz=2x1+3x2s.t.x1+2x284x1164x2≤12x1,x20设Ⅰ产量–––Ⅱ产量–––1x2x如何安排生产，使获利最多？厂家原问题设：出租设备--y1元／台时出让原材料A--y2元/kg出让原材料B--y3元／kg收购方付出的代价最小，且厂家能接受。厂家出让代价应不低于用同等数量的资源自己生产的利润。假设该厂家决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。工厂的决策者就要考虑给每种资源如何定价的问题。现从另一角度来讨论这个问题。设y1,y2和y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额1242yyω=8y1+16y2+12y3出售资源对偶问题收购方的意愿：总的收购价越小越好厂家能接受的条件：出售资源后所得不应比生产产品所得少13243yy3,2,1,0iyi..ts目标函数min单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于3元12121212maxz2328416..412,0xxxxxstxxx原问题对偶问题原问题收购厂家12121212maxz2328416..412,0xxxxxstxxx121342..2430,1,2,3iyystyyyi32112168minyyy一对对偶问题这表明：从不同角度考虑同一问题可得到相互联系的线性规划模型，这就是线性规划的对偶问题。两个模型既有区别又有联系：联系在于它们都是LP模型并且使用相同的数据，区别在于模型反映的实质内容是不同的模型(1)是站在厂家经营者立场,追求销售收入最大;模型(2)则是站在厂家的对手收购者的立场,追求所付的租金最少。特点：1．2．资源向量b价值向量C3．一个约束一个变量。4．的LP约束“”的LP是“”的约束。5．变量都是非负限制。6.AATminmaxzmaxzmin12121212maxz2328416..412,0xxxxxstxxx3,2,1,034224..3121iyyyyytsi32112168minyyyy1y2y3x1x20XbXA.t.sCXzmax加入松驰变量化为标准形0XbXA.t.sCXzmaxXS将以上公式运用于初始单纯形表和迭代后以B为基的单纯形表中得到如下表格：设松弛变量对应的系数列向量占据A的后m列，可行基B占据A的前m列，其余子块仍用N来表示。二根据矩阵描述讨论对偶问题则有：A=（A,I)=(B,N,I),C=(CB,CN,0)初始矩阵单纯形表将B化为I（I为m阶单位矩阵）,CB化为零,求基可行解和检验数。用B－1左乘表中第二行,得到迭代后的表格：cjCBCN0系数基变量解向量XBXNXS0XSbBNICj-ZjCBCN0cjCBCN0系数基变量解向量XBXNXSCBXBB-1bIB-1NB-1Cj-Zj-CBB-1b0CN-CBB-1N-CBB-1LP问题取得最优σN=CN-CBB-1N≤0非基变量中存在松弛变量时检验数：σs=-CBB-1≤0（1）令Y=CBB-1为单纯形乘子（2-9）（2-10）由(2-10)可得：-CBB-1=-Y≤0Y≥0（2）所有变量的检验数：σA=C-CBB-1A=C-YA≤0YA≥C对偶问题的约束条件非基变量的检验数：(2-9)式及(2-10)式是作为得到最优解的判断条件。对偶变量的非负条件cjCBCN0系数基变量解向量XBXNXSCBXBB-1bIB-1NB-1Cj-Zj-CBB-1b0CN-CBB-1N-CBB-1（4）得新的LP问题（3）由Y=CBB-1，两边右乘b得：YA≥CYb=CBB-1b=Z称为原有LP问题minω=YbY≥0Yb取值的上限不受限制，只有取极小值时，LP问题才有意义.0,|maxXbAXCXZ的对偶问题.对偶问题的目标函数12121212maxz2328416..412,0xxxxxstxxx例:400421A)3,2(C12168b它的对偶问题是：YA≥Cminω=YbY≥012168Y)3,2(400421YY=（y1，y2，y3）3,2,1,034224..3121iyyyyytsi32112168minyyy对偶的定义原始问题minf(x)=CTXs.t.AX≥bX≥0对偶问题maxz(y)=bTYs.t.ATY≤CY≥0≥minbACTCATbT≤maxmnmn0minbAX0X..CXzmaxYCs.t.YAYbwts),(21ccC21xxX)(ijaA),y,y(yY321321bbbb3个约束2个变量2个约束3个变量原问题对偶问题一般规律