资源描述
第 2 章 线性规划的对偶理论Duality 对偶Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划Dual Theory 对偶理论2.1 问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?1.最大生产利润模型设 企业生产甲产品为X1件，乙产品为X2件，则 max z=2 X1+3 X2 s.t 2 X1+2 X2 12 X1+2 X2 8 4 X1 16 4 X2 12 X1 0,X2 02.资源最低售价模型(原问题)(对偶问题)设第i种资源收购价格为yi,（i=1,2,3,4,）则有min w=12y1+8y2+16y3+12 y4s.t 2y1+y2+4y3+0 y4 2 2y1+2y2+0y3+4 y4 3yi 0,(i=1,2,3,4)y1y2y3y42.2 原问题与对偶问题一般表示式：（m种资源，n种产品）原问题：max z=c1 X1+c2 X2+cn Xn s.t a11 X1+a12 X2+a1n Xn b1 a21 X1+a22 X2+a2n Xn b2 am1 X1+am2 X2+amn Xn bm xj 0，j=1,2,n 对偶问题：min w=b1 y1+b2 y2+bm ym s.t a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn yi 0，(i=1,2,m)max z=C X s.t AX b X 0min w=Y b s.t YA C Y 0 对偶问题原问题对偶问题也可从数学的角度导出：约束条件标准化：AX+IXs=b检验数：A=C-CBB-1A -Y=S=-CBB-1I=-CBB-1 当存在所有检验数小于等于0，即有：C-YA 0 -Y 0又有 z=CX=CBb=CBB-1b=Yb于是得对偶问题。原模型对应对偶结构矩阵表示（1）max z=C X s.t AX b X 0min w=Y b s.t YA C Y 0 对偶问题原问题max w=-Y b s.t -YA -C Y 0 min w=-CX s.t -AX -b X 0 例2例1对偶模型其它结构关系（2）若模型为 max z=C X s.t AX b X 0max z=C X s.t -AX -b X 0变形min w=Y b s.t YA C Y 0 min w=Y(-b)st.Y(-A)CY 0令 Y=-Y 对偶问题对偶变量Y（3）max z=C X s.t AX b X 0变形设X=-Xmax z=-CX st.-AX b X 0min w=Y b s.t YA C Y 0则有min w=Y b s.t -YA-CY 0对偶问题典式：用矩阵形式表示：（1）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （2）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （3）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0原问题与对偶问题关系表（例3）原问题(对偶问题)对偶问题(原问题)目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数向量 A约束条件系数向量 AT 变量个数约束条件个数max min 变量 x j:约束方程 j:x j 0 x j 无约束 =x j 0 约束方程 i:变量 y i :y i 0 =y i 无约束 y i 0 2.3 对偶问题的基本性质 Max z=CXMin w=Y b s t.AX b s t.YA C X 0Y 0(1)弱对偶性：若 X0原问题可行解，Y0对偶问题可行解则 CX0 Y0b证明：Y0 0，AX0 b，Y0 AX0 Y0 b，而 Y0 A C，Y0AX0 CX0，CX0 Y0 AX0 Y0 b（2）最优性：若 X0原问题可行解，Y0对偶问题可行解，且 CX0=Y0b 则 X0原问题最优解，Y0对偶问题最优解证明：设 X*原问题最优解，Y*对偶问题最优解 则 CX0 CX*Y*b Y0b 但 CX0=Y0 b，CX0=CX*=Y*b =Y0 b X0=X*，Y0=Y*即 X0原问题最优解，Y0对偶问题最优解证毕。（3）无界性若原问题（对偶问题）最优解无界，则对偶问题（原问题）无可行解 证：由性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b。（证：由性质1，C X0 Y0 b，当 Y0 b -时，则不可能存在X0，使得 C X0 Y0 b。）注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。（4）强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且有 z max=w min证：由 =C-CB B-1 A 0 令 CBB-1=Y*，得 Y*A C-Y*=-CBB-1 0，Y*0 因此，Y*是对偶问题的可行解，又 CX*=CB(B-1 b)=CB B-1b=Y*b Y*是对偶问题的最优解。（性质2）（5）互补松弛性 n 若 y i*0,则 aij xj*=bi j=1 n 若 a ij xj*0,a ij xj*-bi=0,即 a ij xj*=bi 当 a ij xj*-bi 0,y i*=0j=1j=1j=1 n n n（6）单纯形表中的对应关系(例4)-y4 -y5 -y1 -y2 -y3 原问题变量原问题松弛变量对偶问题变量对偶问题剩余变量 -x3 -x4 -x5 -x1 -x2 原问题的解：X=(7/2,3/2,15/2,0,0)对偶问题的解：Y=(0,1/4,1/2,0,0)2.4 影子价格(Shadow price)取决于企业对资源使用的状况，受生产任务、产品结构差异、管 理效率等因素影响。边际利润的概念：增加单位资源对利润的贡献。对资源使用决策的参考依据：买进、卖出 对资源使用状况的估算：互补松弛性 机会成本：j=cj-CB B-1pj=cj-Ypj=cj-aijyi，aijyi 为生产xj而放弃其它产品生产的利润。制定内部结算价格的参考2.5 对偶单纯形法由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例5：min w=15y1+24y2+5y3 max w=-15y1-24y2-5y3+0y4+0y5 s.t 6y2+y32 标准化 s.t 6y2+y3-y4=2 5y1+2y2+y3 1 5y1+2y2+y3-y5=1 y1,y2,y3 0 yj 0,(j=1,2,3,4,5)max w=-15y1-24y2-5y3+0y4+0y5 s.t -6y2-y3+y4=-2 -5y1-2y2-y3+y5=-1 yj 0,(j=1,2,3,4,5)Cj y1y2y3y4XBbCB0 -6 -1 1 0 -5 -2 -1 0 1-15 -24 -5 0 0-2-1y4 y500cj-zj-15-24-50y2 y51/3-1/3cj-zj-15 0 -1 -4 0-24 0y2 y3cj-zj-15/2 0 0 -7/2 -3/2列单纯表计算：y500 1 1/6 -1/6 0 -5 0 -2/3 -1/3 1-5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2-24 -51/4 1/2对偶单纯形法步骤：1.列初始单纯形表，使得所有检验数j 0；2.出基变量：取min bi0=bl y(l)3.入基变量：min|alk1 时则用对偶单纯形法继续迭代到最优。当1时，迭代得最终单纯形表如下：cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x5 -1+2x1 31x2 30 0 -2/15 -1/6 1 1 0 -1/15 1/6 0 0 1 1/5 0 0 cjzj0 0 -1/15 -1/3 0 所以当1 时，z()=2*3+3=9最后将z这个函数图像画出。Z()018.59例13：某文教用品厂利用原材料白坯纸生产原稿纸，日记本和练习本三种产品。该厂现有工人100人，每天白坯纸供应限量为30000kg。如果单独生产各种产品时，每个工人每天生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg。又知每生产一捆原稿纸可获利2元，每生产一打日记本可获利3元，每生产一箱练习本可获利1元。试决定：（1）在现有生产条件下工厂获利最大的生产方案；（2）如果白坯纸的供应数量不变，当工人人数不足时可以招临时工，临时工工资支出为每人每天40元，问该厂要不要招收临时工，最多招多少人？解：设该厂每天生产计划为：原稿纸x1捆，日记本x2打，练习本x3箱，又设为临时工数量，则(1)=0，即为现有条件问题，单纯形法可解决。(2)0，即为招临时工问题。即右端项变化的灵敏度分析。
展开阅读全文