运筹学胡运权第五版课件第二章

第二章线性规划的对偶理论DualTheory§2.1对偶问题的提出

例

常山机器厂生产I、II

两种产品。这两种产品都分别要在ABC三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表：如何安排生产才能使总的利润最大？消耗设备工时III设备工时限量设备A设备B设备C240205121615利润（元）23解：maxz=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20

s.t.LP1

假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问：常山机器厂应该如何给这些资源定出一个合理的租金，既使四海机器厂愿意租借，又使本厂能得到自己组织生产这些产品时所能获得的最大收益。解：设A、B、C设备每小时出租的价格分别为y1、y2、y3元，则新的线性规划数学模型为：LP2

对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP1

）必然有与之相伴而生的另一个线性规划问题（LP2

），即任何一个求max

z

的LP1都有一个求min

w的LP2

。将LP1称为“原问题”，记为P；将LP2称为“对偶问题”，记为D。原问题（P）：对偶问题（D）：1、基本概念原问题P对偶问题D原变量x1,x2对偶变量y1,y2,y3原目标z对偶目标w原约束对偶约束变量约束2、一般形式原问题Pmaxz=c1x1+c2x2+···+

cn

xn

s.t.

a11x1+a12x2+···+

a1nxn

b1

a21x1+a22x2+···+

a2nxn

b2

···am1x1+am2x2+···+

amn

xn

bm

xj

0，（j=1,2,···,n）

对偶问题Dminw=b1y1+b2y2+···+bm

ym

s.t.

a11y1+a21y2+···+am1ym

c1

a12y1+a22y2+···+am2ym

c2

···a1ny1+a2ny2+···+amn

ym

cn

yi0，(i=1,2,···,m)其中

例：写出下列LP问题的对偶问题解：对偶问题为：§2.2原问题与对偶问题（max的基本形式）（min的基本形式）1、基本形式的联系与区别（1）原目标求极大，对偶目标求极小；（2）原约束个数=对偶变量个数原变量个数=对偶约束个数

原约束决定对偶变量原变量决定对偶约束；（3）原约束≤方向，对偶约束≥方向；（4）原目标的系数对应对偶约束的右端常数原约束的右端常数对应对偶目标的系数；（5）原系数矩阵与对偶系数矩阵互为转置；（6）原变量与对偶变量都是非负取值。例将下列问题作为原问题，写出其对偶问题。解：先改写为原问题的基本形式：再对偶化：最后简化得到已知问题的对偶问题：2、基本形式的表格比较3、互为对偶关系

若LP2是LP1的对偶问题，则LP1是LP2的对偶问题。minZ’=-CXs.t.-AX≥-b X≥0

minW=bTYs.t.ATY≥CTY≥0maxZ=CXs.t.AX≤b X≥0对偶的定义对偶的定义maxW’=-bTYs.t.-ATY≤-CTY≥0改写改写例写出下列问题的对偶问题。解：第一步改写为min的基本形式第二步对偶化第三步简化为已知问题的对偶问题：比较原问题和对偶问题：基本形式非基本形式4、原问题与对偶问题的互化原问题（或对偶问题）对偶问题（或原问题）目标函数max（基本）目标函数min

（基本）约束条件m个m个变量≤（基本）≥0（基本）≥≤0=无约束变量n个n个约束条件≥0（基本）≥（基本）≤0≤无约束=约束条件的右端项目标函数的系数目标函数的系数约束条件的右端项例直接写出下列线性规划问题的对偶问题。练习写出下列问题的对偶问题。解：对偶问题为：§2.3对偶问题的基本性质在本节中设原问题和对偶问题如下：1、弱对偶性（弱对偶原理）：设和分别是问题P和D的可行解，则必有证明：2、最优性：

若X*和Y*分别是P和D的可行解且CX*=bTY*，则X*，Y*分别是问题P和D的最优解。证明：3、无界性

若原问题有无界解，则对偶问题无可行解。

若对偶问题有无界解，则原问题无可行解。证明：注：逆定理不成立。即“如果原问题无可行解，那么对偶问题有无界解”不成立。此时，对偶问题可能有无界解，也可能无可行解。4、强对偶性（对偶定理）

若原问题有最优解，则对偶问题一定有最优解，且

zmax=wmin.证：设X*是原问题的最优解，则所有检验数都非正。即

=C-CBB-1A0∴CBB-1AC令CBB-1=

Y*

T，有

Y*T

AC,转置得ATY*

CT-----------------------①又因为

S′

=-CBB-1

=-Y*T0，所以Y*=-（S′）T

0------②

由①②知Y*是对偶问题的可行解，而CX*=CBb′，其满足:CX*

=CB(B-1b)=CBB-1b=Y*T

b=bTY*

由最优性(性质2)，∴Y*是对偶问题的最优解。注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解是第三列，而对偶问题的最优解是松弛变量检验数的相反数。

1001/40

00-21/21

011/2-1/80

4422X10X53X2

x1x2x3x4x5

CBXBb

23000

Cj00-3/2-1/805、互补松弛性证明：松条件---变量＞0，约束不等式；紧条件---变量=0，约束为等式。将该性质应用于其对偶问题时，则有：例考虑下面问题解:则6、P和D之间存在一对互补的基解

（1）原问题的变量对应于对偶问题的剩余变量，原松弛变量对应对偶变量；（2）互相对应的变量在一个问题中是基变量，在另一个问题中是非基变量；（3）互补的基解对应的目标函数值相等。原问题对偶问题原变量x1,x2对偶剩余变量y4,y5原松弛变量x3,x4,x5对偶变量y1,y2,y3例对比两个互为对偶问题间的互补基解。序号原问题P目标函数值对偶问题Dx1x2x3x4x5基可行解？y1y2y3y4y5基可行解？143-200×1701/23/500√233040√15*101/500√(15)342005√143/2-1/4000×4404015√801/200-3×5600-815×121000-1×6036160√9003/5-20×706016-15×183/20010√800121615√0000-2-3×利用一对互补的基解，判定目标函数的大小：目标函数值原问题P可行解非可行解对偶问题D可行解最优zmaxz＞zmax非可行解z＜zmax不确定小结

利用对偶问题的基本性质确定最优解的方法：性质2（最优性）一对使目标函数相等的可行解为最优解。性质4（强对偶性）最终表中原问题的最优解在第三列，对偶问题的最优解是松弛变量的检验数的相反数。性质5（互补松弛性）性质6（互补的基解）一对可行的互补基解为最优解。例判断下列说法是否正确：（1）若线性规划的原问题有可行解，则对偶问题一定有可行解。（2）若线性规划的对偶问题无可行解，则原问题一定无可行解。（3）在互为对偶的一对原问题和对偶问题中，不管原问题是求极大还是求极小，原问题可行解的目标函数值一定不超过对偶问题可行解的目标函数值。（4）任何线性规划问题都有唯一的对偶问题（×）（×）（×）（√）1、定义对于一对互补的基解，总满足§2.4影子价格其中，bi是线性规划原问题约束条件的右端项，表示第i种资源的拥有量；对偶变量yi表示对一个单位的第i种资源在生产中做出贡献的估价，称为第i种资源的影子价格（shadowprice）.注意：影子价格不是资源的市场价格。2、性质（1）资源的市场价格随市场供求变化，通常是稳定的；影子价格随资源的利用情况变化，通常是不稳定的。（2）影子价格是一种边际价格。例已知PQ(4,2)x1x24x1=164x2=12x1+2x2=944083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=14x1+2x2=84x1=174x2=13当b1变化1个单位时，z增加1.5，对应y1=1.5；当b2变化1个单位时，z增加0.125，对应y2=0.125；当b3变化1个单位时，z无变化，对应y3=0.P和D的最优解分别为：（3）影子价格是一种机会成本。

假设第i种资源的单位市场价格为mi

，影子价格为yi

。当yi>mi

时，企业愿意购进这种资源，单位纯利为yi－mi，即有利可图；当yi<mi

时，企业愿意有偿转让这种资源，可获单位纯利为mi－yi，否则企业无利可图，甚至亏损；当yi=mi

时，处于平衡状态。（4）互补松弛性在最优配置下，若资源bi未充分利用，则影子价格yi为0；若影子价格yi大于0，则该资源bi已经利用完。（5）检验数的经济意义

其中，cj代表第j种产品的产值；是生产一个单位该种产品所消耗的各项资源的影子价格的总和，称为产品的隐含成本。当该项产品的产值大于隐含成本时，表示生产该产品有利，可在计划中安排；否则不在计划中安排。

（2）使管理者了解花多大代价买进资源或卖出资源是合适的3、影子价格的意义（1）使管理者掌握增加何种资源对企业更有利（3）为新产品定价提供依据（4）使有限资源发挥更大的经济效益§2.6灵敏度分析1．概念广义：对系统或事物因周围条件变化显示出来的敏感程度的分析。狭义：在线性规划问题中，分析一个或多个参数发生变化时，最优解将如何改变；或者分析参数在一个怎样的范围内变化时，最优解不变。其中可以改变的参数有：cj——目标函数系数的变化，即市场条件的改变；

bi——约束右端项的变化，即资源拥有量的改变；Pj——约束左端系数的变化，即工艺技术条件的改变。其他的变化例如：增加一种新产品、增加一道新工序等。2．步骤

（1）cj的变化：直接反映到最终表中，重新计算检验数。（2）bi的变化：（b+△b）´=B-1

（b+△b）=B-1b+B-1△b=b´+（△b)´(△b)´=B-1△b（3）Pj的变化：

（Pj+△Pj

）´=B-1

（Pj+△Pj

）=B-1

Pj+B-1△Pj=Pj´+(△Pj)´

(△Pj)´=B-1△Pj（4）增加新产品：即增加一个决策变量，仿照Pj变化。（5）增加新工序：即增加一个约束条件，直接反映到最终表中。第一步利用最终单纯形表将变化后的结果按下述基本原则修改最终表。第二步在最终表中分别检查原问题和对偶问题是否为可行解。若第三列没有负数，则原问题的基解是可行解；若检验数没有正数，则对偶问题的基解是可行解。第三步按下表所列情况进行：原问题对偶问题结论或继续可行解可行解仍为最优解可行解非可行解用单纯形法继续非可行解可行解用对偶单纯形法继续(略)非可行解非可行解引入人工变量，用单纯形法继续（略）6-1分析cj的变化范围

例已知线性规划问题如下，试分析λ1和λ2分别在什么范围内变化时，问题的最优解不变。解：当λ1=λ2=0时，上述线性规划问题的最终表为：Cj23000CBXBbX1X2X3X4X52X10X43X234310½0-1/500-214/501001/5

00-10-1/5当λ2=0时，将λ1反映到最终表得到Cj

2+λ13000CBXBbX1X2X3X4X52+λ1

X10X43X234310½0-1/500-214/501001/5

00-1-½λ10-1/5+1/5λ1

为使表中解为最优解，条件是即当时，满足要求。当λ1=0时，将λ2反映到最终表得到Cj

23+λ2000CBXBbX1X2X3X4X52

X10X43+λ2

X234310½0-1/500-214/501001/5

00-10-1/5-1/5λ2

为使表中解为最优解，条件是即当时，满足要求。综上所述，为使最优解不变必须满足：6-2分析bi的变化范围

例已知线性规划问题如下，试分析λ1，λ2和λ3分别在什么范围内变化时，问题的最优基不变。Cj23000CBXBbX1X2X3X4X52X10X43X234310½0-1/500-214/501001/5

00-10-1/5解：当λ1=λ2=λ3=0时，上述线性规划问题的最终表为：（1）分析λ1的影响由公式使问题的最优基不变的条件是：解得：（2）分析λ2的影响由公式使问题的最优基不变的条件是：解得：（3）分析λ3的影响由公式使问题的最优基不变的条件是：解得：终上所述，使问题的最优基不变的条件是：6-3增加一个变量的分析例已知线性规划问题如下，若增加一个变量x6，而且试分析问题最优解的变化。Cj23000CBXBbX1X2X3X4X52X10X43X2