对偶性及对偶单纯形法

2-4对偶性及对偶单纯形法一线性规划的对偶理论1.对偶线性规划例2．1生产计划问题（资源利用问题）

胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？数学模型

maxg=50x1+30x2s.t.4x1+3x21202x1+x250(4.1)x1,x20

如果我们换一个角度，考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？

假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：

mins=120y1+50y2目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。

该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：

4y1+2y2503y1+y230y1,y20

得到另外一个数学模型：

mins=120y1+50y2s.t.4y1+2y2503y1+y230(4.2)y1,y20模型(4.1)和模型(4.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(4.1)是站在家具厂经营者立场追求销售收入最大，模型(4.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型(4.1)称为原问题，则模型(4.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。例2.2营养配餐问题

假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455(4.3)400x1+200x2+300x3+500x4800x1，x2，

x3，x40

该问题的对偶问题：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30(4.4)该问题的对偶问题(4.4)经济意义可解释为：市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。线性规划的对偶关系：（I）MaxS=Cxs.t.Axb

（4.5）

x0(II)Ming=ybs.t.Atyct

（4.6）

y0（4.5)(4.6)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。

a11a12….a1nb1A=a21a22….a2nb

=

b2

。。。。。。。。。。。。。。。

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=yt=……………..…..cnxn0ym原问题（或对偶问题）对偶问题（或原问题）目标函数maxZ价值系数资源系数目标函数minW资源系数价值系数行约束的个数为m第i个行约束取“≤”第ι个行约束取“＝”对偶变量的个数为m第i个变量yi

≥0第ι个变量yι无限制原变量的个数为n第j个变量xj

≥0第k个变量xk无限制行约束的个数为n第j个行约束取“≥”第k个行约束取“＝”线性规划的原问题与对偶问题的变换规则表：例2-3：写出下列线性规划问题的对偶问题minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

22x1+2x2+4x43x1，x2，x3，x40minS=12x1+8x2+16x3+12x4

s.t.2x1+x2+4x3

2y12x1+2x2+4x43y2x1，x2，

x3，x40解：该问题的对偶问题：

maxg=2y1+3y2s.t.2y1+2y212y1+2y284y1164y212y1，y20例2-4：写出下列线性规划问题的对偶问题maxS=10x1+x2+2x3s.t.X1+x2+2x310y14x1+2x2-x320

y2

x1，x2，

x30解：该问题的对偶问题：

ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y2

0例2-5：写出下列线性规划问题的对偶问题

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

3x1+x2+7x33x1，x2，

x30解：用（-1）乘以第二个约束方程两边

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2y1

-3x1-x2-7x3-3y2x1，x2，

x30该问题的对偶问题：

maxg=2y1-3y2s.t.2y1-3y213y1-y225y1-

7y23y1，y20例2-6：写出下列线性规划问题的对偶问题

minS=2x1+3x2-5x3s.t.x1+x2-x3

52x1+x3=4x1，x2，x30解：将原问题的约束方程写成不等式约束形式：minS=2x1+3x2-5x3s.t.x1+x2-x35

y12x1+x34

y2’

-2x1-x3-4

y2”

x1，x2,x30引入变量y1,y2’，y2”

写出对偶问题

maxg=5y1+4y2’-4y2”

s.t.y1+2y2’-2y2”

2y1

3-y1+y2’-y2”

-5y1，y2’，y2”

0令y2=y2’-y2”

得到

maxg=5y1+4y2s.t.y1+2y22y1

3-y1+y2-5y10，y2无非负约束此类问题称为非对称型对偶问题。前面的问题称为对称型对偶问题。例2-7：写出下列线性规划问题的对偶问题

minS=3x1-2x2+x3s.t.x1+2x2=1

y1

2x2-x3-2

y2

2x1+x33

y3

x1-2x2+3x34

y4

x1，x20

，

x3无非负限制

minS=3x1-2x2+x3s.t.x1+2x2=1y1-2x2+x32y22x1+x33y3x1-2x2+3x34y4x1，x20

，

x3无非负限制解:综合运用对偶原则得到maxg=y1+2y2+3y3+4y4s.t.y1+2y3+y432y1-2y2-2y4-2y2+y3+3y4=1y2,y3,y40，y1无非负约束2.对偶问题的基本定理(对称性定理)课本Th2.5.2

对偶问题的对偶就是原问题.对偶问题的基本定理推理一:对偶问题中,任意一个可行解,都产生了另一个问题的目标函数的界。推理二:若原问题和对偶问题都有可行解,则它们都有最优解。推理三:若互为对偶问题中任意一个有可行解,但无最优解,则另一个就无可行解。对偶问题的基本定理定理(最优准则)

若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解.对偶问题的基本定理定理(对偶定理)课本Th2.5.1

若原问题有最优解,则对偶问题也有最优解,且最优值相等.原问题与对偶问题解的对应关系二、对偶单纯形法原始单纯形法其基本思路：在换基迭代过程中，始终保持基变量值非负，逐步使检验数变成非正，最后求得最优解或判断无最优解。对偶单纯形法其基本思路：在换基迭代过程中，始终保持检验数非正，逐步使基变量值变成非负，最后求得最优解或判断无最优解。对偶单纯形法计算步骤如下：

步骤1确定原问题（L）的初始基B，使所有检验数，即Y=CBB-1是对偶可行解，建立初始单纯形表。

步骤2检查基变量的取值，若XB=B-1b≥0，则已得最优解，计算停；否则求min{(B-1b)i│(B-1b)i＜0｝=(B-1b)ι确定单纯形表第L行对应的基变量为旋出变量。

步骤3若所有aιj≥0,则原问题无可行解，计算停；否则，计算θ=min｛σj/aιj│aιj

＜0

｝=σk/aιk确定对应的xk为旋入变量。

步骤4

以aιk为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。

例2-9：用对偶单纯形法解下列线性规划问题

minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x4

2x1，x2，

x3，x40解：此题可用人工变量方法求，但也可用对偶单纯形法。

maxS’=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=-2x1，x2,x3，x4，x5,x6

0计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。常数项是负数且最小为3，确定出基变量x5。用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1）主元运算：第一行乘（-1）主元运算：第二行加上第一行（-2）计算检验数确定出基变量x6

确定进基变量X3，主元（-2）主元运算：第二行乘（-1/2）主元运算：第一行加第二行计算检验数：全为非正。但此时常数b已全大于零，最优解=（7，0，4，0）最优值S’=-7S=7例2-10：用对偶单纯形法解下列线性规划问题

minS=x1+2x2s.t.-x1+2x2-x3

1-x1-2x2+x36x1，x2，x30解：将原问题化成

maxS’=-x1-2x2s.t.x1-2x2+x3+x4=-1x1+2x2-x3+x5=-6x1，x2，x3，x4,x5

0常数项最小出基变量X5，按比值无法比较。常数项次小出基变量X4，按比值X2为进基变量。主元（-2）主元运算：第一行乘（-1/2）主元运算：第二行加第一行（-2）计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。例2-11用对偶单纯形法求解下述问题

minZ=12x1+8x2+16x3+12x4

2x1+x2+4x3≥2

2x1+2x2+4x4≥3

x1,x2,x3,x4≥0解：令=-Z，则问题可变为max=-12x1-8x2-16x3-12x4

-

2x1-x2-4x3+x5=-2

-2x1-2x2

-4x4+x6=-3

x1,x2,x3,x4,x5,x6≥0取B=（P5,P6）为初始基，易见所有检验数σj≤0，从而可建立单纯形表，计算结果如下：

C-12-8-16-1200CBXBB-1bX1X2X3X4X5X600X5X6-2-3

-2-1-4010-2-20［-4］01σ-12-8-16-12000-12X5X4-23/4

-2［-1］-40101/21/2010-1/4σ

-6-2-1600-3-8-12X2X42-1/4

2140-10［-1/2］

0-211/2-1/4σ

-20-80-2-3-8-12X2X111/2

01-441-1104-2-11/2σ

000-4-4-2L=2，K=4L=1，K=2L=2，K=1最优解：X1=1/2，X2=1，X3=X4=0,minZ=14本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解：

①问题标准化后，价值系数全非正；②所有约束全是不等式。例2-11：某种农作物在生长过程中至少需要氮肥33公斤，磷肥24公斤，钾肥42公斤。已知有甲、乙、丙、丁四种复合肥料的每公斤价格和含氮、磷、钾肥数量如下表。问应如何使用这些肥料，既能满足作物生长的需要，又能使施肥成本最低？原始数据表解：设用甲、乙、丙、丁为X1、X2、X3、X4公斤。数学模型为：minS=4x1+15x2+10x3+13x4s.t.0.03x1+0.3x2+0.15x4330.05x1+0.2x3+0.1x4240.14x1+0.07x4

24x1，x2，

x3，x40也可将模型化为：maxS=-4x1-15x2-10x3-13x4-0.03x1-0.3x2-0.15x4+x5=-33-0.05x1-0.2x3-0.1x4+x6=-24-0.14x1-0.07x4+x7=-24x1，x2，x3，x4,x5，x6,x70

初始可行基B1