第三章线性规划的对偶理论精选PPT.ppt

第三章线性规划的对偶理论1 1第1页，本讲稿共117页第一节第一节 对偶规划问题对偶规划问题一、对偶问题的基本概念一、对偶问题的基本概念 1.对偶现象：事物的两面性。对偶现象：事物的两面性。例如：例如：（1）“在周长一定的四边形中，以正方形的在周长一定的四边形中，以正方形的面积最大。面积最大。”（2）“在面积一定的四边形中，以正方形的在面积一定的四边形中，以正方形的周长最小。周长最小。”这是一个现象的两个提法，我们称这两这是一个现象的两个提法，我们称这两种情况互为对偶，其中一个问题为原问题，种情况互为对偶，其中一个问题为原问题，另外一个问题为原问题的对偶问题。另外一个问题为原问题的对偶问题。第2页，本讲稿共117页例例例例1-1 1-1 1-1 1-1 某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产A A A A、B B B B两种药物。每种药物要经过两两种药物。每种药物要经过两两种药物。每种药物要经过两两种药物。每种药物要经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两周内，甲、乙道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两周内，甲、乙道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两周内，甲、乙道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两周内，甲、乙两台机器的使用时间分别不得超过两台机器的使用时间分别不得超过两台机器的使用时间分别不得超过两台机器的使用时间分别不得超过40404040小时和小时和小时和小时和30303030小时，生产每公斤药物小时，生产每公斤药物小时，生产每公斤药物小时，生产每公斤药物A A A A的利的利的利的利润是润是润是润是30303030元，元，元，元，B B B B是是是是25252525元。生产每公斤药物所需的加工时间如表所示：元。生产每公斤药物所需的加工时间如表所示：元。生产每公斤药物所需的加工时间如表所示：元。生产每公斤药物所需的加工时间如表所示：试问，如何安排这两周的生产，能使工厂利润最大？试问，如何安排这两周的生产，能使工厂利润最大？试问，如何安排这两周的生产，能使工厂利润最大？试问，如何安排这两周的生产，能使工厂利润最大？2.对偶问题：对偶问题：Max Max Max Max z z z z=30=30=30=30 x x x x1 1 1 1+25+25+25+25x x x x2 2 2 2 s.t.2 s.t.2 s.t.2 s.t.2x x x x1 1 1 1+4+4+4+4x x x x2 2 2 2 40 40 40 40 3 3 3 3x x x x1 1 1 1+2+2+2+2x x x x2 2 2 2 30 30 30 30 x x x x1 1 1 1,x x x x2 2 2 2 0 0 0 0药物药物（公斤）（公斤）甲加工时间甲加工时间（小时）（小时）乙加工时间乙加工时间（小时）（小时）利润利润（元）（元）A A2 23 33030B B4 42 22525限制时间限制时间40403030A：x1公斤；B：x2公斤。第3页，本讲稿共117页 设设设设 y y1 1 ，y y2 2 分别为出租资源设备甲分别为出租资源设备甲分别为出租资源设备甲分别为出租资源设备甲、乙、乙、乙、乙每工时收取的费用。每工时收取的费用。每工时收取的费用。每工时收取的费用。Min w=40Min w=40y y1 1+30+30y y2 2 (租金额最小）租金额最小）s.t.2s.t.2y y1 1+3+3y y2 2 30 30（药物（药物A A的租金不少于药物的租金不少于药物A A的的利润）利润）4 4y y1 1+2+2y y2 2 25 25（药物（药物B B的租金不少于药物的租金不少于药物B B的的利润）利润）y y1 1,y y2 2,0,0若若若若第二章例第二章例第二章例第二章例1 1 1 1中制药厂的中制药厂的中制药厂的中制药厂的设备都用于外协加工，即设备都用于外协加工，即设备都用于外协加工，即设备都用于外协加工，即该厂的决策者该厂的决策者该厂的决策者该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，接受外来加工任务，接受外来加工任务，接受外来加工任务，工厂工厂工厂工厂只收取加工费。只收取加工费。只收取加工费。只收取加工费。试问：设备甲试问：设备甲试问：设备甲试问：设备甲、乙、乙、乙、乙每工每工每工每工时各应如何收费才最有竞争力？时各应如何收费才最有竞争力？时各应如何收费才最有竞争力？时各应如何收费才最有竞争力？下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：分析问题：分析问题：1.1.每种资源收回的费用不能低于自己生产时的可获利润；每种资源收回的费用不能低于自己生产时的可获利润；2.2.定价又不能太高，要使对方能够接受。定价又不能太高，要使对方能够接受。第4页，本讲稿共117页 Max Max z z=30=30 x x1 1+25+25x x2 2 s.t.2 s.t.2x x1 1+4+4x x2 2 40 40 3 3x x1 1+2+2x x2 2 30 30 原问题原问题 x x1 1,x x2 2 0 0 Min w=40Min w=40y y1 1+30+30y y2 2 s.t.2 s.t.2y y1 1+3+3y y2 2 3030 4 4y y1 1+2+2y y2 2 2525 对偶问题对偶问题 y y1 1,y y2 2 0 0线性规划的对偶线性规划的对偶每一个线性规划（每一个线性规划（LP ）必然有与之相伴而生的另一个线性规）必然有与之相伴而生的另一个线性规划问题，其中的一个问题叫划问题，其中的一个问题叫“原问题原问题”，记为，记为“L“LP”，另一个，另一个称为称为“对偶问题对偶问题”，记为，记为“DP”。第5页，本讲稿共117页3.影子价格影子价格 在上例中，对偶问题的最优解为原问题约在上例中，对偶问题的最优解为原问题约束条件的影子价格，解束条件的影子价格，解yi称为第称为第i种资源（设备）种资源（设备）的影子价格。的影子价格。影子价格并非市场上的真实价格，而是企影子价格并非市场上的真实价格，而是企业根据本企业的具体生产过程，为使药物业根据本企业的具体生产过程，为使药物A、B实现最大利润而得到的一种估计价格。为了实现最大利润而得到的一种估计价格。为了与市场价格相区别，我们称它为影子价格。影与市场价格相区别，我们称它为影子价格。影子价格是厂家对所拥有的资源的稀缺程度的一子价格是厂家对所拥有的资源的稀缺程度的一种度量，是相对于具体厂家而言的。种度量，是相对于具体厂家而言的。影子价格提供了一个价格的标准，如果市影子价格提供了一个价格的标准，如果市场上某种资源的价格低于影子价格，那么应当场上某种资源的价格低于影子价格，那么应当购进这种资源，增加生产，提高利润；反之就购进这种资源，增加生产，提高利润；反之就应该售出这种资源，求得更高的利润。应该售出这种资源，求得更高的利润。第6页，本讲稿共117页 对称形式：互为对偶 (LP)Max z=c x (DP)Min f=bT y s.t.Ax b s.t.AT y cT x 0 y 0 “Max-”“Min-”二、对称形式的对偶线性规划二、对称形式的对偶线性规划第7页，本讲稿共117页 一一一一对对对对对对对对称称称称形形形形式式式式的的的的对对对对偶偶偶偶规规规规划划划划之之之之间间间间具具具具有有有有下下下下面面面面的的的的对对对对应应应应关关关关系。系。系。系。(1)(1)(1)(1)若若若若一一一一个个个个模模模模型型型型为为为为目目目目标标标标求求求求“极极极极大大大大”，约约约约束束束束为为为为“小小小小于于于于等等等等于于于于”的的的的不不不不等等等等式式式式，则则则则它它它它的的的的对对对对偶偶偶偶模模模模型型型型为为为为目目目目标标标标求求求求“极极极极小小小小”，约约约约束束束束是是是是“大大大大于于于于等等等等于于于于”的的的的不不不不等等等等式式式式。即即即即“max“max“max“max，”和和和和“min“min“min“min，”相对应。相对应。相对应。相对应。(2)(2)(2)(2)从从从从约约约约束束束束系系系系数数数数矩矩矩矩阵阵阵阵看看看看：一一一一个个个个模模模模型型型型中中中中为为为为，则则则则另另另另一一一一个个个个模模模模型型型型中中中中为为为为A A A AT T T T。一一一一个个个个模模模模型型型型是是是是m m m m个个个个约约约约束束束束，n n n n个个个个变变变变量量量量，则则则则它它它它的的的的对对对对偶模型为偶模型为偶模型为偶模型为n n n n个约束，个约束，个约束，个约束，m m m m个变量。个变量。个变量。个变量。(3)(3)(3)(3)从从从从数数数数据据据据b b b b、C C C C的的的的位位位位置置置置看看看看：在在在在两两两两个个个个规规规规划划划划模模模模型型型型中中中中，b b b b和和和和C C C C的的的的位置对换。位置对换。位置对换。位置对换。(4)(4)(4)(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。第8页，本讲稿共117页 11 对偶规划问题对偶规划问题 P.44 任一任一L.P.问题，都有一个与之密切相关的问题，都有一个与之密切相关的L.P.问题，问题，叫对偶问题。叫对偶问题。给定一个给定一个L.P.问题，如何引出其对偶问题？见问题，如何引出其对偶问题？见P.52.表表 31。x1 x2.xn 原关系原关系 Min y1 a 11 a 12.a 1n b b1 1 y2 a 21 a 22.a 2n b b2 2 .ym a m1 a m2.a mn b bm m 对偶关系对偶关系 .(X0,Y0,)(X0,Y0,)Max Z c Max Z c1 c c2 .cn 横向组合得原问题：横向组合得原问题：Max Z=c c1 x1+c c2 x2+.+c cn xn a 11 x1+a 12x2+.+a 1n xnbb1 1 a 21 x1+a 22x2+.+a 2n xnbb2 2 .a m1 x1+a m2x2+.+a mn xnbbm m X 0X 0纵向组合得对偶问题：纵向组合得对偶问题：Min =b1y1+b2y2+.+bmym a 11 y1+a 21 y2+.+a m1 ym c c1 1 a 12 y1+a 22 y2+.+a m2 ym c c2 2 .a 1n y1+a 2n y2 +.+a mn ym c cn n Y 0 Y 0若写成矩阵形式，可得：若写成矩阵形式，可得：原问题：原问题：对偶问题：对偶问题：Max Z=CX Min =bTY AX b Ab AT T Y Y CCT T X 0 YX 0 Y 00注意：其中注意：其中C C是行向量，是行向量，X X、Y Y与与b b是列向量，是列向量，AmnAmn为为a aijij所构成的矩阵。所构成的矩阵。2341第9页，本讲稿共117页其矩阵形式为：其矩阵形式为：对偶（原）问题为对偶（原）问题为:以下举例说明对偶问题的作法，见以下举例说明对偶问题的作法，见 P.52 例例 2原（对偶）问题：原（对偶）问题：Min Z=2x1+5x2 y1 x1 4 4 y2 x2 3 3 y3 x x1 1+2x2 8 x1 ,x2 00 x1 x2 1 0 1 0 1 2y y1 1 y y2 2y y3 3 对偶（原）问题为：对偶（原）问题为：MaxW=4y1+3 y2+8y3 y1+y3 2 2 x1y2 +2y3 5 5 x2y y1 10,y0,y2 20,y0,y3 300 25 1 0 0 1 1 2438 x1 x2y y1 1 y y2 2y y3 3 XoYoMax W=(4 ,3 ,8)原（对偶）问题：原（对偶）问题：Min Z=(2,5)第10页，本讲稿共117页写出下面线性规划的对偶规划写出下面线性规划的对偶规划：1.max z=2xmax z=2x1 1+3x+3x2 2 2x 2x1 1+2x+2x2 21212 x x1 1+2x+2x2 288 s.t.s.t.4x 4x1 1 16 16 4x 4x2 2 12 12 x x1 1,x,x2 200 2.第11页，本讲稿共117页Min w=12y1+8y2+16y2+12y2s.t.2y1+y2+4y3 22y1+2y2+4y4 3y1,y2,y3,y4 0解：解：2.首先将原式变形首先将原式变形对偶问题：对偶问题：解：解：1.第12页，本讲稿共117页三、非对称的对偶线性规划三、非对称的对偶线性规划 对于对称形式的线性规划可按上述规则写出其对偶规划，对于对称形式的线性规划可按上述规则写出其对偶规划，对于对称形式的线性规划可按上述规则写出其对偶规划，对于对称形式的线性规划可按上述规则写出其对偶规划，但是经常遇到的是非对称形式的线性规划问题（但是经常遇到的是非对称形式的线性规划问题（但是经常遇到的是非对称形式的线性规划问题（但是经常遇到的是非对称形式的线性规划问题（dual of a dual of a nonnormal LPnonnormal LP），这时可将其转化为等价的、满足），这时可将其转化为等价的、满足），这时可将其转化为等价的、满足），这时可将其转化为等价的、满足对称形式条件的线性规划问题，然后再按照对称形式对称形式条件的线性规划问题，然后再按照对称形式对称形式条件的线性规划问题，然后再按照对称形式对称形式条件的线性规划问题，然后再按照对称形式的原问题与对偶问题的对应关系表，构造其对偶问题。的原问题与对偶问题的对应关系表，构造其对偶问题。的原问题与对偶问题的对应关系表，构造其对偶问题。的原问题与对偶问题的对应关系表，构造其对偶问题。在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，若原问题是求若原问题是求若原问题是求若原问题是求目标函数极大、约束条件不等式为目标函数极大、约束条件不等式为目标函数极大、约束条件不等式为目标函数极大、约束条件不等式为“”“”，可在不等式两端，可在不等式两端，可在不等式两端，可在不等式两端乘以乘以乘以乘以-1-1，将，将，将，将“”“”化为化为化为化为“”“”；若决策变量；若决策变量；若决策变量；若决策变量x xj j或或或或yiyi0000，则令，则令，则令，则令x xj j=-=-x xj j或或或或y yi i=-y=-yi i，将决策变量化为非负值。对于约束条件是等式，将决策变量化为非负值。对于约束条件是等式，将决策变量化为非负值。对于约束条件是等式，将决策变量化为非负值。对于约束条件是等式的标准型形式的原问题，可由下述方法导出其对偶规划问题。的标准型形式的原问题，可由下述方法导出其对偶规划问题。的标准型形式的原问题，可由下述方法导出其对偶规划问题。的标准型形式的原问题，可由下述方法导出其对偶规划问题。例如：对约束条件是等式的例如：对约束条件是等式的例如：对约束条件是等式的例如：对约束条件是等式的LPLP问题问题问题问题 max z=CX max z=CX s.t.AX=b s.t.AX=b X0 X0第13页，本讲稿共117页 s.t.AX=b X0 由于由于 AXb AXb 即即AX=bAX=b AXb-AX-b所以，原问题可化为所以，原问题可化为 max z=CX s.t.AXb -AX-b X0 A b X -A -b 第14页，本讲稿共117页 设设设设YY：AXbAXb的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）Y Y：-AX-b-AX-b的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：min w =Yb-Yb=min w =Yb-Yb=（Y-YY-Y）b b （Yb=bYb=bT TY YT T）s.t YA-YAC s.t YA-YAC （YA=A YA=AT TY YT T）Y0 Y0，Y0 Y0 令令令令Y=Y-YY=Y-Y，则对偶问题为，则对偶问题为，则对偶问题为，则对偶问题为 min w=Yb min w=Yb s.t YAC s.t YAC Y Y符号不限符号不限符号不限符号不限 结论：原问题中约束条件为等式，对应的对偶变量无结论：原问题中约束条件为等式，对应的对偶变量无结论：原问题中约束条件为等式，对应的对偶变量无结论：原问题中约束条件为等式，对应的对偶变量无非负要求；反过来同样成立。非负要求；反过来同样成立。非负要求；反过来同样成立。非负要求；反过来同样成立。第15页，本讲稿共117页 求下列原问题的对偶问题：求下列原问题的对偶问题：求下列原问题的对偶问题：求下列原问题的对偶问题：max z=4x max z=4x max z=4x max z=4x1 1 1 1+5x+5x+5x+5x2 2 2 2 s.t.3x s.t.3x s.t.3x s.t.3x1 1 1 1+2x+2x+2x+2x2 2 2 220202020 4x 4x 4x 4x1 1 1 1-3x-3x-3x-3x2 2 2 210101010 x x x x1 1 1 1+x+x+x+x2 2 2 2=5=5=5=5 x x x x1 1 1 1 0,x0,x0,x0,x2 2 2 2 符号不限符号不限符号不限符号不限 解：解：解：解：首先将原问题化成首先将原问题化成首先将原问题化成首先将原问题化成 对称形式，令对称形式，令对称形式，令对称形式，令 x x x x2 2 2 2=x=x=x=x3 3 3 3-x-x-x-x4 4 4 4,x x x x3 3 3 300，x x4 400，原问题化为原问题化为原问题化为原问题化为 max z=4xmax z=4xmax z=4xmax z=4x1 1 1 1+5x+5x+5x+5x3 3 3 3-5x-5x-5x-5x4 4 4 4 s.t.3x s.t.3x s.t.3x s.t.3x1 1 1 1+2x+2x+2x+2x3 3 3 3-2x-2x-2x-2x4 4 4 4 20202020 -4x -4x -4x -4x1 1 1 1+3x+3x+3x+3x3 3 3 3-3x-3x-3x-3x4 4 4 4-10101010 x x x x1 1 1 1+x+x+x+x3 3 3 3xxxx4 4 4 4 5 5 5 5 -x -x -x -x1 1 1 1-x-x-x-x3 3 3 3+x+x+x+x4 4 4 4-5 5 5 5 x x x x1 1 1 1，x x x x3 3 3 3，x x x x4 4 4 4 00 将对称形式线性规划问题化为对偶问题如下将对称形式线性规划问题化为对偶问题如下将对称形式线性规划问题化为对偶问题如下将对称形式线性规划问题化为对偶问题如下第16页，本讲稿共117页 Min W=20wMin W=20w1 1-10w-10w2 2+5w+5w3 3-5w-5w4 4 s.t.3w s.t.3w1 1-4w-4w2 2+w+w3 3-w-w4 444 2w 2w1 1+3w+3w2 2+w+w3 3-w-w4 455 -2w -2w1 1-3w-3w2 2-w-w3 3+w+w4 4-5 -5 w w1 1，w w2 2，w w3 3，w w4 400 -1-1，得，得 2w 2w1 1+3w+3w2 2+w+w3 3-w-w4 4 5 5 令令y y1 1=w=w1 1，y y2 2=w=w2 2，y y3 3=w=w3 3-w-w4 4，得，得 Min W=20y Min W=20y1 1-10y-10y2 2+5y+5y3 3 s.t.3y s.t.3y1 1-4y-4y2 2+y+y3 3 44 2y 2y1 1+3y+3y2 2+y+y3 3=5=5 y y1 1，y y2 20,y0,y3 3符号不限符号不限第17页，本讲稿共117页原规划与对偶规划的线性关系56 56 表表3 33 3原（对偶）规划原（对偶）规划对偶（原）规划对偶（原）规划目标目标max zmax zmin fmin f目标目标约束约束mm个个 =mm个个 0 0 0 0自由自由变量变量变量变量n n个个 0 0 0 0自由自由n n个个 =约束约束限制向量限制向量b b价值向量价值向量C C系数矩阵系数矩阵A A价值向量价值向量C C限制向量限制向量b b系数矩阵系数矩阵A AT T第18页，本讲稿共117页 对对对对于于于于非非非非对对对对称称称称形形形形式式式式的的的的规规规规划划划划，可可可可以以以以按按按按照照照照下下下下面面面面的的的的对对对对应应应应关关关关系系系系直直直直接接接接给给给给出出出出其其其其对对对对偶偶偶偶规划。规划。规划。规划。（1 1 1 1）对对对对原原原原问问问问题题题题模模模模型型型型为为为为“max“max“max“max，约约约约束束束束条条条条件件件件为为为为”或或或或“min“min“min“min，约约约约束束束束条条条条件件件件为为为为”的的的的形形形形式式式式，对对对对应应应应的的的的对对对对偶偶偶偶规规规规划划划划的的的的变变变变量量量量大大大大于于于于0 0 0 0；反反反反之之之之，若若若若原原原原问问问问题题题题模模模模型型型型为为为为“max“max“max“max，”或或或或“min“min“min“min，”的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于0 0 0 0。（2 2 2 2）原原原原问问问问题题题题线线线线性性性性规规规规划划划划的的的的决决决决策策策策变变变变量量量量大大大大于于于于0 0 0 0，则则则则对对对对偶偶偶偶问问问问题题题题的的的的模模模模型型型型为为为为“max“max“max“max，约约约约束束束束条条条条件件件件为为为为”或或或或“min“min“min“min，约约约约束束束束条条条条件件件件为为为为”的的的的形形形形式式式式；若若若若原原原原问问问问题题题题线线线线性性性性规规规规划划划划的的的的决决决决策变量小于策变量小于策变量小于策变量小于0 0 0 0；则对偶问题的模型为；则对偶问题的模型为；则对偶问题的模型为；则对偶问题的模型为“max“max“max“max，”或或或或“min“min“min“min，”的形式。的形式。的形式。的形式。非对称形式非对称形式的对偶规划的对偶规划 （3 3 3 3）若若若若原原原原规规规规划划划划的的的的某某某某个个个个约约约约束束束束条条条条件件件件为为为为等等等等式式式式约约约约束束束束，则则则则在在在在对对对对偶偶偶偶规规规规划划划划中中中中与与与与此此此此约约约约束束束束对应的那个变量取值没有非负限制；对应的那个变量取值没有非负限制；对应的那个变量取值没有非负限制；对应的那个变量取值没有非负限制；（4 4 4 4）若若若若原原原原规规规规划划划划的的的的某某某某个个个个变变变变量量量量的的的的值值值值没没没没有有有有非非非非负负负负限限限限制制制制，则则则则在在在在对对对对偶偶偶偶问问问问题题题题中中中中与与与与此此此此变变变变量对应的那个约束为等式。量对应的那个约束为等式。量对应的那个约束为等式。量对应的那个约束为等式。第19页，本讲稿共117页 max z=4x max z=4x1 1+5x+5x2 2 s.t.3x s.t.3x1 1+2x+2x2 22020 4x 4x1 1-3x-3x2 21010 x x1 1+x+x2 2 =5=5 x x1 1 0,x0,x2 2 符号不限符号不限符号不限符号不限 Min W=20yMin W=20y1 1+10y+10y2 2+5y+5y3 3 s.t.3y s.t.3y1 1+4y+4y2 2+y+y3 3 44 2y 2y1 1-3y-3y2 2+y+y3 3=5=5 y y1 1 0 0，y y2 20,y0,y3 3符号不限符号不限符号不限符号不限 Min W=20y Min W=20y1 1-10y-10y2 2+5y+5y3 3 s.t.3y s.t.3y1 1-4y-4y2 2+y+y3 3 44 2y 2y1 1+3y+3y2 2+y+y3 3=5=5 y y1 1，y y2 20,y0,y3 3符号不限符号不限符号不限符号不限 第20页，本讲稿共117页 例例 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型解：先将约束条件变形为如下形式解：先将约束条件变形为如下形式第21页，本讲稿共117页 再根据非对称形式的对应关系，直接写出对偶规划再根据非对称形式的对应关系，直接写出对偶规划 max z=xmax z=xmax z=xmax z=x1 1 1 1-x-x-x-x2 2 2 2+5x+5x+5x+5x3 3 3 3-7x-7x-7x-7x4 4 4 4 第22页，本讲稿共117页求下列原问题的对偶问题：求下列原问题的对偶问题：1.max z=2x 1.max z=2x1 1+3x+3x2 2 s.t.2x s.t.2x1 1+x+x2 2=15=15 4x 4x1 1+3x+3x2 22020 x x1 1，x x2 2 0,0,2.max z=3x 2.max z=3x1 1-6x-6x2 2+5x+5x3 3+4x+4x4 4 s.t.x s.t.x1 1+2x+2x2 2-3x-3x3 3-4x-4x4 4=-5=-5 3x 3x1 1-x-x2 2+x+x3 3-7x-7x4 41414 -4x -4x1 1-5x-5x2 2+3x+3x3 3+2x+2x4 43 x x1 1，x x2 2 0,x0,x3 3，x x4 4符号不限符号不限 第23页，本讲稿共117页解答：1 Min W=15y1+20y2 s.t.2y1+4y2 4 y1+3y2 3 y1符号不限，y2 02 Min W=-5y1+14y2+3y3 s.t.Y1+3y2-4y3 3 2y1-y2-5y3-6 -3y1+y2+3y3 =5 -y1-7y2+2y3=4 y20，y3 0，y1符号不限第24页，本讲稿共117页练习：练习：第25页，本讲稿共117页答案：答案：第26页，本讲稿共117页作业题作业题课后习题二第课后习题二第1题（题（P7980页）。页）。第27页，本讲稿共117页四、线性规划的矩阵表示第28页，本讲稿共117页第29页，本讲稿共117页初始单纯形表初始单纯形表 非基变量非基变量基变量基变量基基X XB BX XN NX XI IC CI IX XI Ib bB BN NI IC Cj j=c=cj j-z-zi iC CB B-C-CI IB BC CN N-C-CI IN N0 0最优单纯形表最优单纯形表基变量基变量非基变量非基变量基基X XB BX XN NX XI IC CB BX XB BB B-1-1 b bI IB B-1-1N NB B-1-1C Cj j=c=cj j-z-zi i0 0C CN N-C-CB B B B-1-1 N NC CI I-C-CB B B B-1-1第30页，本讲稿共117页C CB Bc cj j303025250 00 0b bx x1 1x x2 2x x3 3x x4 40 0 x x3 32 24 41 10 04040 20 200 0 x x4 4332 20 01 130301010C Cj j303025250 00 0Z=CZ=CB Bb=0b=02525x x2 20 01 13/83/8-1/4-1/415/215/23030 x x1 11 10 0-1/4-1/41/21/25 5C Cj j0 00 0-15/8-15/8-35/4-35/4Z=337.5Z=337.5XBXj请分别指出，B-1，B-1，CN-CB B-1 N，CI-CB B-1第31页，本讲稿共117页初始单纯形表初始单纯形表2 2-1-11 10 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x4 46 61 11 11 11 10 00 0 x x5 54 4-1-12 20 00 01 1Z Z2 2-1-11 10 00 0最终单纯形表最终单纯形表2 2-1-11 10 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 52 2x x1 1（）（）（）（）1 1（）0 0 x x5 5（）（）（）（）1 1（）Z Z（）（）（）（）（）习题：一个极大化（目标函数为习题：一个极大化（目标函数为习题：一个极大化（目标函数为习题：一个极大化（目标函数为max Zmax Z）的线性规划问题，有三）的线性规划问题，有三）的线性规划问题，有三）的线性规划问题，有三个非负变量个非负变量个非负变量个非负变量x x1 1,x,x2 2,x,x3 3，两个，两个，两个，两个“”“”型约束条件，型约束条件，型约束条件，型约束条件，x x4 4,x,x5 5是松弛变量，是松弛变量，是松弛变量，是松弛变量，用单纯形法计算时得到的初始单纯型表及最终单纯型表如下，最用单纯形法计算时得到的初始单纯型表及最终单纯型表如下，最用单纯形法计算时得到的初始单纯型表及最终单纯型表如下，最用单纯形法计算时得到的初始单纯型表及最终单纯型表如下，最优单纯型表中，优单纯型表中，优单纯型表中，优单纯型表中，x x1 1、x x5 5为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。1 10 00 01 11 13 36 610101 11 10 0-3-3-1-1-2-20 0第32页，本讲稿共117页性质一、对称性定理：对偶问题的对偶是原问题。性质一、对称性定理：对偶问题的对偶是原问题。第二节第二节 对偶问题的性质对偶问题的性质max z=-Cmax z=-CT TX Xs.t.-AXs.t.-AX-b-bX 0X 0min y=-bTWs.t.-ATW-CW 0max y=bTWs.t.ATWCW 0min z=Cmin z=CT TX Xs.t.AXbs.t.AXb X 0 X 0对偶的定义对偶的定义第33页，本讲稿共117页其他形式问题的对偶其他形式问题的对偶原问题与对偶问题互为对偶，任意一个原问原问题与对偶问题互为对偶，任意一个原问题经过两次对偶形式的转换后，必定等价于题经过两次对偶形式的转换后，必定等价于原问题。原问题。min z=Cmin z=CT TX Xs.t.s.t.AXAXb bX 0X 0max y=bTWs.t.ATWC W 0min z=Cmin z=CT TX Xs.t.s.t.AXAX=b bX 0X 0max y=bTWs.t.ATWC W：unr第34页，本讲稿共117页性质二性质二 弱对偶性弱对偶性 若若X为原问题（最大化）为原问题（最大化）的可行解，的可行解，Y为对偶问题（最小化）的可为对偶问题（最小化）的可行解，行解，则则 CXYb。Max Max z z=30=30 x x1 1+25+25x x2 2 CX s.t.2 s.t.2x x1 1+4+4x x2 2 40 40 3 3x x1 1+2+2x x2 2 30 30 原问题原问题 x x1 1,x x2 2 0 0 Min w=40Min w=40y y1 1+30+30y y2 2 Yb s.t.2 s.t.2y y1 1+3+3y y2 2 3030 4 4y y1 1+2+2y y2 2 25 25 对偶问题对偶问题 y y1 1,y y2 2,0 0第35页，本讲稿共117页z z=30=30 x x1 1+25+25x x2 2 w=40w=40y y1 1+30+30y y2 2(LP)Max z=c x (DP)Min f=y b s.t.Ax b s.t.y A c x 0 y 0 “Max-”“Min-”yAx yb y A x cx 由上面两个不等式由上面两个不等式 yb cx 弱对偶定理说明：如果原问题是最大化问题，则它的任一可弱对偶定理说明：如果原问题是最大化问题，则它的任一可弱对偶定理说明：如果原问题是最大化问题，则它的任一可弱对偶定理说明：如果原问题是最大化问题，则它的任一可行解对应的目标函数值不大与其对偶问题（最小化问题）的行解对应的目标函数值不大与其对偶问题（最小化问题）的行解对应的目标函数值不大与其对偶问题（最小化问题）的行解对应的目标函数值不大与其对偶问题（最小化问题）的可行解对应的目标函数值。可行解对应的目标函数值。可行解对应的目标函数值。可行解对应的目标函数值。第36页，本讲稿共117页性质三性质三（最优性判定定理最优性判定定理）可行解是最优解时的性质）可行解是最优解时的性质 当当X*是原问题（是原问题（Max）的可行解，）的可行解，Y*是其对偶问题是其对偶问题（MinMin）的可行解时，若的可行解时，若 CX*=Y*b，则，则 X*与与 Y*是各自问题的最是各自问题的最优解。优解。证明证明：设设X*是原问题的任意一个可行解，由性质是原问题的任意一个可行解，由性质 2即即弱对偶定理可知，弱对偶定理可知，CX*YY*b b，又由又由 CX*=Y*b知知:CX*YY*b=CXb=CX*,就是说就是说,X,X*使目标函数所达到的值比其它任何可行解使目标函数所达到的值比其它任何可行解使目标函数所达到的值不会小，所以使目标函数所达到的值不会小，所以X X*是最优解。是最优解。同理（设同理（设Y*b CX*=Y*b），Y Y*是是其对偶问题的最优其对偶问题的最优解。解。证毕。证毕。第37页，本讲稿共117页 性质四性质四 （强强对偶定理）若原问题有最优解，则对偶问对偶定理）若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。题也有最优解，且目标函数最优值相等。证明证明 设原问题的形式为：设原问题的形式为：Max Z=CX，AX b;X 0 b;X 0，于是，于是AX+XS=b=b，即（，即（A A，I I）=b =b，其中，其中A A为为 m x n m x n 矩阵，矩阵，I I为为 m m 阶单位矩阵，阶单位矩阵，XS为为m 维列向量。维列向量。既知有最优解，必有最优基变量对应的矩阵，记之为既知有最优解，必有最优基变量对应的矩阵，记之为 B B，那么，在最终单纯形表中，检验数所形成的行向量为：那么，在最终单纯形表中，检验数所形成的行向量为：（C-CC-CB BB B-1-1A A，-C-CB BB B-1-1）0 0，于是，于是 C-C C-CB BB B-1-1A0 A0，即，即 C CB BB B-1-1A C A C （YA C）令令 Y Y*=C=CB BB B-1-1，又又-CBB-10，即，即 CBB-1 0，可得，可得 Y*=CBB-1 0，则则 YA C,Y Y*是对偶问题是对偶问题 （Min W=Yb;YA C;C;Y 0Y 0）的可行解，而）的可行解，而 W=Y W=Y*b=C b=CB B B B-1-1b b。因为