运筹学第二章对偶理论

§1线性规划的对偶问题的提出

每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。

0,0768940453643.3032max2121212121³³ïîïíì£+£+£++=xxxxxxxxtsxxz矩阵形式

0.max³£=XbAXt.sCXz实际问题提出：某厂生产甲、乙两种产品，产量、利润、设备台时如下模型所示第二章线性规划的对偶理论

从另一个角度讨论这个问题：另一方面，工厂决定设备转让、收取租金，确定租价。设y1，y2，y3分别为设备A、B、C每台时的租价，同意租让的原则：产品甲租让的租费不低于原利润32元，其余产品类似。工厂将所有设备台时都出租，其收入和约束为：矩阵形式

为什么目标取最小？租金定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。其中Y=（y1，y2，y3）§２线性规划的对偶理论原问题与对偶问题的数学模型原问题：对偶问题：

标准对偶问题化成对偶问题的标准形

1.若原问题的约束条件全部是等式约束

总结：原问题与对偶问题的对应关系

2.其它形式，按线性规划化标准形的方法进行进一步有原问题（或对偶问题）对偶问题（或原问题）

目标函数maxz目标函数minw

约束条件:m个对偶变量数:m个变量

第i个约束条件类型约束为≤对偶变量:yi

≥0

第i个约束条件类型约束为≥对偶变量:yi

≤0

第i个约束条件类型约束为=对偶变量:yi是自由变量

决策变量总数:n个约束条件总数为n个

决策变量xi≥0第j个约束条件类型为≥

决策变量xi≤0第j个约束条件类型为≤

决策变量xi是自由变量第j个约束条件类型为=

原问题中的价值向量与对偶问题中的资源向量对换,“上下对换”.

原问题:X在C和A的右边;对偶问题:Y在b和A的左边,“左右对换”

对偶问题的基本性质和基本定理1.对称性定理：对偶问题的对偶是原问题证明：2.弱对偶性定理

若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）≤Y（0）b3.若原问题（对偶问题）可行，但目标函数无界，则其对偶问题（原问题）无可行解。4.最优性定理

若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有CX（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。

5.对偶定理

有一对对偶的线性规划问题，若其中一个有最优解，则另一个也有最优解，且相应的目标函数值相等。

综上，一对对偶问题的解必然为下列情况之一：1、原问题和对偶问题都有解，且目标函数值相等2、一个问题具有无界解，另一个问题无可行解3、原问题和对偶问题都无可行解6.互补松弛定理

若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是Y（0）

Xs=0和YsX（0）=0。

其中Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm

分别是原问题的松弛变量.

Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn分别是对偶问题的剩余变量。

松弛的含义是如果有某个原始最优解X(0)，使得对某个下标j，满足X(0)j>0(对原问题是松的)，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(对对偶问题是紧的)；如果原始约束在最优情况下对某个下标i满足x(0)si>0(对原问题是松的)，那么，对偶最优解中与之对应的y(0)i=0(对偶问题是紧的)。例4已知线性规划问题

maxz=x1+x2

-x1+x2+x3

≤2

-2x1+x2-x3

≤1

x1,x2,x3≥0

试用对偶理论证明上述线性规划问题无最优解。

证:首先看到该问题存在可行解，例如X=(0,0,0)

而上述问题的对偶问题为

minω=2y1+y2

-y1-2y2≥1

y1+y2≥1

y1-y2≥0

y1,y2≥0

由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。例5已知线性规划问题

minω=2x1+3x2+5x3+2x4+3x5

x1+x2+2x3+x4+3x5

≥42x1-x2+3x3+x4+x5

≥3xj≥0,j=1,2,3,4,5

已知其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解.解:

先写出它的对偶问题

maxz=4y1+3y2y1+2y2≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0将y1*,y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0

因y1,y2

0，原问题的两个约束条件应取等式，故有

x1*+3x5*=42x1*+x5*=3

求解后得x1*=1，x5*=1故原问题的最优解为

X*=(1,0,0,0,1)T最优值为ω*=5§３对偶问题的经济解释（影子价格）由对偶定理知，当达到最优解时有：

z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+…+ym（0）bm在最优解处，常数项bi

的微小改变对目标函数值的影响（在不改变最优基情况下）有这说明若原问题的bi增加一个单位，则由此引起的最优目标函数值增加量，就等于该约束条件相对应的对偶变量yi的最优值。因此，最优对偶变量yi的值，就相当于对单位变化的第i种资源在实现最大利润时的一种价格估计，这种估计被称之为影子价格。原问题：可以理解为资源的合理利用使总利润最大对偶问题：估计资源的价值问题（但并不是第ｉ种资源的实际成本，而是根据企业制造产品的收益估计资源的单位价值，既资源在最优产品组合时具有的潜在价值）影子价格：不同于市场价格，是企业内部估计或核算价格例：某厂生产Ⅰ、Ⅱ种产品要消耗钢、煤、机械加工时间，现有资源数和利润表如下，试制定一个最优生产计划。单位消耗Ⅰ

Ⅱ现有资源数钢煤机时１２２２１６１００１８０２４０利润１３解得：对偶问题:由互补松弛条件：解得：所以：钢增加一吨，收入增加3/4万煤增加一吨，收入增加0

机时增加一个，收入增加1/4万

煤本身没有用完，再增加量，收入也不会增加，而另两种资源已经用完，再增加资源才会增加收益影子价格在经济管理中的作用:指示企业内部挖潜的方向：yi高,对目标增益贡献大,应重视此资源的组织、采购；(2)指导企业的购销决策：yi*是新增资源的价值，在最优产品不变的情况下，购入资源价格大于yi*时，企业亏损，若企业有市价高于影子价格的资源，应设法将其转让；(3)用影子价格分析工艺改变后对资源节约的收益:(4)指导企业间的分工协作:

企业接受外协加工时，制定收费标准可依据影子价格，以使双方都有利润，可以促进协作；当外协单位支付的报酬不低于影子价格时，企业可以接受，合作可以促进产品更新换代，以发挥各自优势。例：A、B、C三厂生产车床、刨床，若只生产一种产品，每天效率表如右图。三个厂车、刨床需求比例为1：2，试制定最优分工协作计划，使总的套数最多。解：A、B、C三厂编号为1，2，3

车、刨床的编号为1，2效率车床刨床ABC4223为第i厂生产第j种产品的时间比例则：三厂生产车床总数：三厂生产刨床总数：展开得：总套数为E，则解得：生产车床：3/4×5=15/4（台）生产刨床：4×1+1/4×2+3×1=15/2（台）A厂只生产刨床，B厂3/4生产车床，1/4生产刨床C厂只生产刨床此计划能否执行看较单独生产获利增加情况A厂单独生产：解得A厂生产能力：2/3×1=2/3台车床

1/3×4=4/3台刨床（每天生产一台车床或4台刨床而需求比例为1:2）（用2/3的能力生产车床，1/3的能力生产刨床）B厂单独生产：B厂生产能力：1/6×5=5/6台车床

5/6×2=5/3台刨床解得：C厂单独生产：解得：C厂生产能力：3/7×2=6/7台车床

4/7×3=12/7台刨床