运筹学第三章对偶单纯形法

运筹帷幄之中决胜千里之外对偶理论与灵敏度分析第二章对偶理论与灵敏度分析第一节对偶问题的提出第二节线性规划的对偶理论第三节对偶问题的经济解释第四节对偶单纯形法【例2-1】某家电厂利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD第一节对偶问题的提出如何安排生产，使获利最多？厂家设

Ⅰ产量––––Ⅱ产量––––

设：设备A——

元／时

设备B––––

元／时

调试工序––––

元／时承租

付出的代价最小，

且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：出让代价应不低于用同等数量的资源自己生产的利润。收购方的意愿：厂家对偶问题原问题承租厂家一对对偶问题第二节线性规划的对偶理论一﹑原问题与对偶问题的关系二﹑对偶问题的基本性质一﹑原问题与对偶问题的关系1﹒对称式的对偶“≤”不等式约束条件的原问题与“≥”不等式约束条件的对偶问题，称为对称式的一对对偶问题。原问题：maxz=c1x1+c2x2+…+cnxn

a11

a12…a1n

am1

am2…amn·········x1xn···b1bm···≤

x1，x2，…，xn≥0对偶问题：minω=b1y1+b2y2+…+bmym

a11

a12…a1n

am1

am2…amn·········≥

y1，y2，…，ym≥0(y1,y2,…,ym)(c1,c2,…,cn)maxz=CXAX≤bX≥0minω=YbYA≥CY≥0

n个变量，m个约束条件

m个变量，n个约束条件2﹒约束条件全部为“=”的对偶maxz=CXAX＝bX≥0原问题：maxz=CXAX≤bX≥0AX≥b等价maxz=CXAX≤bX≥0－AX≤－bmaxz=CXX≥0A－AX≤b－bminω=(Y1,Y2)Y1,Y2≥0A－A≥Cb－b(Y1,Y2)其中

Y1=(y1,y2,…ym)，Y2=(ym+1,ym+2,…y2m)等价等价minω=YbY为无约束YA≥Cminω=(Y1－Y2)bY1,Y2≥0(Y1－Y2)A≥C令Y=(Y1－Y2)对偶问题对偶问题3﹒约束条件为“≥”的对偶maxz=CXAX≥bX≥0原问题：maxz=CX－AX≤－

bX≥0minω=Y1(－b)Y1(－A)≥CY1≥0minω=YbYA≥CY≤0等价对偶问题令Y=

－Y1对偶问题4﹒变量≤0的对偶maxz=CXAX≤bX≤0原问题：令X=

－X1maxz=C(－X1)A(－X1)≤bX1≥0maxz=(－C)X1(－A)X1≤bX1≥0等价minω=YbY

(－A)≥－CY≥0minω=YbY

A≤CY≥0对偶问题对偶问题等价5﹒变量无约束的对偶maxz=CXAX≤bX无约束原问题：令X=X1－X2X1，X2≥0maxz=CX1－CX2X1,X2≥0AX1－AX2≤bmaxz=(C,－C)X1,X2≥0≤bX1X2(A,－A)X1X2等价minω=YbY≥0Y(A,－A)≥(C,－C)对偶minω=YbYA≥CY≥0－YA≥－Cminω=YbYA

＝CY≥0minω=YbYA≥CY≥0YA≤C等价等价等价对偶问题6﹒原问题与对偶问题的关系表原问题（或对偶问题）对偶问题（或原问题）目标函数maxzn个变量变量≥0变量≤0变量无约束目标函数minω

n个约束条件约束≥约束≤约束=m个约束条件约束≥约束≤约束=约束条件右端项目标函数变量系数m个变量变量≤0变量≥0变量无约束目标函数变量系数约束条件右端项【例2-2】试求下述线性规划问题的对偶问题（P）与(D)的关系对应表：原(对偶)问题对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A解：

（P）与(D)的关系对应表：原(对偶)问题对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A【例2-3】

试求下述线性规划原问题的对偶问题解：原问题的对偶问题【课堂练习】（P）与(D)的关系对应表：原问题对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A构建对偶问题的规则原始问题的目标对偶问题目标约束类型变量符号最大化极小化>=无限制最小化极大化<=无限制要求：1、将所有约束转换成等式；2、将所有决策变量转换成大于等于。回顾：原问题与对偶问题的关系表原问题（或对偶问题）对偶问题（或原问题）目标函数maxzn个变量变量≥0变量≤0变量无约束目标函数minω

n个约束条件约束≥约束≤约束=m个约束条件约束≥约束≤约束=约束条件右端项目标函数变量系数m个变量变量≤0变量≥0变量无约束目标函数变量系数约束条件右端项二﹑对偶问题的基本性质1﹒对称性：对偶问题的对偶问题是原问题。2﹒弱对偶性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则存在CX(0)≤Y(0)b。3﹒无界性：若原问题无界解，则其对偶问题无可行解。4﹒最优性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，且CX(0)=Y(0)b，则X(0)，Y(0)是最优解。5﹒对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。6﹒互补松弛性：若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则YsX(0)=0和Y(0)Xs=0当且仅当X(0)，Y(0)是最优解。其中Xs和Ys分别为原问题和对偶问题的松弛变量的可行解.【例2-4】已知线性规划问题minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。【例2-4】已知线性规划问题解：先写出它的对偶问题maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0【例2-4】已知线性规划问题将y1*=4/5,y2*=3/5的值代入约束条件，得②=1/5<3，③=17/5<5，④=7/5<2

它们为严格不等式；由互补松弛性得

x2*=x3*=x4*=0。因y1，y2≥0；原问题的两个约束条件应取等式，故有

x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为

X*=(1，0，0，0，1)T；w*=51、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第三节对偶问题的经济解释2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=minw3、资源影子价格的性质从对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即z=CX(0)=Y(0)b=CBB-1b.也即z=CX(0)=Y(0)b=CBB-1b=y1(0)b1+y2(0)b2

+…+ym(0)bm

其中X(0),Y(0)分别是原问题和对偶问题的最优解。现在考虑在最优解处，常数项bi的微小变动对目标函数值的影响(不改变原来的最优基).求z对bi的偏导数，可得：y1(0)

＝∂z—∂b1,y2(0)

＝∂z—∂b2,ym(0)

＝∂z—∂bm,…这说明，若原问题的某一约束条件的右端常数项bi增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。最优变量yi(0)的值，就相当于对单位第I种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为“影子价格”。【例1-3】

求下列问题的最优解。

影价格及其经济解释

第四节对偶单纯形法6﹒(LP)的检验数的相反数对应于(DP)的一个基解，其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量ysj的解，第i个松弛变量xsi的检验数的相反数对应于第i个对偶变量yi的解。ＸＢＸＮＸs0Ys1CN1－CBB-1N1﹣Ys2－CBB-1﹣Y二﹑对偶问题的基本性质【例2-4】线性规划（1）用单纯形方法求最优解；（2）求每步迭代对应对偶问题的基本解。cj6-2100CBXBbx1x2x3x4x500x4x524[2]1﹣10241001

δj

6-210060x1x51310﹣1/2[1/2]131/2-1/201

δj

01-5-306-2x1x2461001460-112

δj

00-11-2-2123解：原问题与对偶问题解之间的对应关系指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cj−CBB-1Pj≤0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。设原问题为

maxz=CX

AX=b

X≥0又设B是一个基。不失一般性，令B=(P1，P2，…，Pm)，它对应的变量为XB=(x1，x2，…,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i＜0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解。每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。2﹒对偶单纯形法的计算步骤⑴列出初始单纯形表⑵最优性检验

根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。

检查b列的数，若都为非负，则已得到最优解。停止计算。若b列的数中，还有分量为负数，则进行下一步计算。⑶确定换出变量

按min{(B-1b)i|(B-1b)i<0}=(B-1b)l

确定xl为换出变量。⑷确定换入变量①如果xl所在行各系数alj

(j=1,2,…n).都有alj>0，则无可行解，停止计算。②如果有alj<0(

j=1,2,…n),则计算ck－zkθ＝mincj－zj———

alj|alj<０＝———

alk确定xk为换入变量，且保持得到的对偶问题的解是基可行解。⑸迭代运算

以alk为主元素，对单纯形表进行迭代运算，得到新单纯表。重复⑵—⑸【例2-5】用对偶单纯形法求解x1+2x2+x3≥32x1－x2+3x3≥4minω=2x1+3x2+4x3x1,x2,x3≥0﹣x1﹣2x2﹣x3+

x4=﹣3﹣2x1+x2﹣3x3+x5=﹣4maxz=﹣2x1﹣3x2﹣4x3x1,x2,x3x4,x5≥0解：cj﹣2﹣3﹣400CBXBbx1x2x3x4x500x4x5﹣3﹣4﹣1[﹣2]﹣21﹣1﹣31001

δj

﹣2﹣3﹣400θ1－4/3其中x4,x5为松弛变量cj﹣2﹣3﹣400CBXBbx1x2x3x4x50﹣2x4x1﹣1201[﹣5/2]﹣1/21/23/210﹣1/2﹣1/2

δj

0﹣4﹣10﹣1θ﹣8/5﹣﹣2cj﹣2﹣3﹣400CBXBbx1x2x3x4x5﹣3﹣2x2x12/511/50110﹣1/57/5﹣2/5﹣1/51/5﹣2/5

δj

00﹣9/5﹣8/5﹣1/5原最优X*=(11/5,2/5,0,0,0)T，对偶最优Y*=(8/5,1/5)从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个对偶问题初始可行基，因而这种方法在求解线性规划问题时很少单独应用。对偶单纯形法的计算步骤（min）⑴列出初始单纯形表⑵最优性检验

根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。

检查b列的数，