第二章线性规划问题的对偶与灵敏度分析

第二章线性规划的对偶与灵敏度分析§1线性规划的对偶问题§2对偶问题的基本性质§4对偶单纯形法§5灵敏度分析2/4/20231线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点2/4/20232§1线性规划的对偶问题提出问题(LP1)maxz=2x1+x2

st.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0一个公司要收购美佳公司的资源(设备)，问它至少要付出多大的代价？设备A设备B调试工序假设y1、y2、y3分别代表单位时间设备A、设备B、调试工序的出让价y1y2y32/4/20233美佳出价：出让价应不低于用同等数量的资源由自己组织生产活动时所获得的利润6y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0买家还价：买家在满足上述条件的前提下，希望用最小的代价获得美佳公司的全部资源Minω＝15y1+24y2+5y32/4/20234(LP2)Minω＝15y1+24y2+5y3st.6y2+y3≥25y1+2y2+y3≥1y1,y2,y3

≥0一个新的线性规划称(LP1)为原问题，(LP2)为对偶问题当LP中的变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，而当目标函数求极小时均取“≥”时，则称这样的LP问题具有对称形式2/4/20235一般规律(1)

原问题有n个变量，m个约束，对偶问题有m个变量，n个约束。原问题的目标函数求极大，对偶问题的目标函数求极小(2)

原问题的目标函数中变量的系数为对偶问题的约束条件的常数项，反之亦然(3)

原问题与对偶问题的约束方程的系数矩阵互为转置2/4/20236(LP1)Maxz=CX

s.t.

AX≤b

X≥0(LP2)Minω=

bT

Ys.t.AT

Y≥CTY≥0

非对称形式的对偶问题一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，一般事先转换成对称形式，然后按对应规则写出其对偶问题2/4/20237Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤23x1－x2+6x3

≥1

x1+x2+x3=4x1≥0,x2≤0,x3无约束y1y3’y2’Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤2

－3x1＋x2－

6x3

≤－1

x1+x2+x3≤

4

－x1－x2－x3≤－4x1≥0,x2≤0,x3无约束Maxz=x1

－4x’2

+3x’3－3x’’3St.2x1－3x’2－5x’3+5x’’3≤2

－3x1－x2－

6’x3＋6x’’3

≤－1

x1－x2+x’3－x’’3≤

4

－x1+x2－x’3+x’’3≤－4x1,x’2,x’3,x’’3≥0y3’’每个约束方程对应一个对偶变量。原则：是“≤”的方程直接对应y；是“≥”的对应y’；是“＝”的分别对应y’,y’’2/4/20238Minω=2y1-y’2+4y’3-4y’’3St.2y1-3y’2+y’3-y’’3≥1-3y1-y’2-y’3+y’’3≥-4-5y1-6y’2+y’3-y’’3≥35y1+6y’2-y’3+y’’3≥-3y1,y’2,y’3,y’’3≥0Minω=2y1+y2+4y3St.2y1+3y2+y3≥13y1-y2+y3≤4-5y1+6y2+y3=3y1≥0,y2≤0,y3无约束令y2=－y’2y3=y’3－y’’3Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤23x1－x2+6x3

≥1

x1+x2+x3=4x1≥0,x2≤0,x3无约束原问题对偶问题2/4/20239也可以直接利用对应关系写出线性规划问题的对偶问题Maxz=－5x1

－6x2

－7x3St.－x1+5x2－3x3

≥15

－5x1－6x2+10x3

≤

20

x1－x2－x3=－5x1≤

0,x2≥0,x3无约束Minω=15y1+20y2－5y3St.－y1－5y2+y3≥－55y1－6y2－y3≤－6

－3y1+10y2－y3=－7y1≤0,y2≥

0,y3无约束掌握两者之间的对应系：对偶问题的变量对应原问题的约束方程，对偶问题的约束方程对应原问题的变量（见表2-2）y1y2y3x1x2x32/4/202310§2对偶问题的基本性质一、单纯形法计算的矩阵表示松弛变量m×m单位矩阵单纯形法计算时，总取I为初始基，对应的基变量为Xs。迭代若干步后基变量为XB,XB在初始单纯形表中的系数矩阵为B，将A中去掉B后的剩余部分记为N(具体情况见下表)2/4/202311非基变量基变量0XsbXBXNBNXsIσjcB

cN0初始单纯形表迭代若干步基变量非基变量cB

XBB－1bXBIXNXsB－1NB－1

σj0cN－cBB－1N

-cBB－1最终单纯形表2/4/202312

21000

x1x2x3x4x5cjCB

基(变量)bx3x4x500015245

05100

62010

11001σj21000cj21000CB

基(变量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/2B-1B2/4/202313五点结论（2）初始单纯形表中的常数项是b，最终单纯形表中B－1b（3）初始单纯形表中系数矩阵为[A,I]=[B,N,I]，最终单纯形表中系数矩阵

[B－1A,B－1]=[B－1B,B－1N,B－1I]=[I,B－1N,B－1]（1）对应初始单纯形表中的单位矩阵I，最终单纯形表中为B－1(非常重要的指标)2/4/202314（4）初始单纯形表中变量Xj的系数向量为Pj，最终单纯形表中为

P’j

=B－1Pj(1)（5）当B为最优基时，在最终单纯形表中应有

cN－cBB－1N≤0(2)

－cBB－1≤0(3)因为XB的检验数可写为

cB－cBI=cB-

cBB-1B=0(4)故（4）（2）可以合并写成(5)，(3)直接写成(6)

c－cBB－1

A≤0(5)

－cBB－1≤0(6)2/4/202315如果令YT=cBB－1(单纯形乘子)，则(5)、(6)可写为(7)原问题的对偶问题从(7)式可以看出，此时原问题的最优解对应的单纯形表中，检验数若取相反数恰好是其对偶问题的一个可行解！而且有原问题的最优解当原问题为最优解时，这时其对偶问题有可行解，且两者具有相同的目标函数值2/4/202316项目原问题变量原问题松弛变量x1x2x3x4x5x3

15/2x17/2x23/200100115/4-15/201/4-1/20-1/43/2σj000-1/4-1/2对偶问题的松弛变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题松弛变量y1y2y3

y4y5y2

1/4y31/2-5/41015/201-1/41/41/2-3/2σj15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x22/4/202317定理1(弱对偶定理）若x,y分别为原问题与对偶问题的可行解则恒有

cTx≤bTy二、对偶问题的基本性质

定理2(最优性定理)

若x,y分别原问题与对偶问题的可行解,且cTx=bTy

，那么x,y分别为原问题与对偶问题的最优解。2/4/202318

定理3(对偶定理)

若原问题与对偶问题均有可行解，那么它们均有最优解,且最优解的函数值相等。

定理4(互补松弛性定理)(比较重要)

若在线性规划问题的最优解中,若对应某一约束条件的对偶变量值为非零，则约束方程取严格等式；反之若约束方程取严格不等式，则其对应的对偶变量一定为零。2/4/202319对偶单纯形法的基本思想从对偶问题的可行解出发，去寻求原问题的最优解，此时根据对偶定理，原—对偶问题均有最优解§4对偶单纯形法2/4/202320

对偶单纯形法的基本思路从原问题的一个基解出发，此基解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原问题的基解是否可行，即是否有负的分量？如果有小于零的分量，则进行迭代，求另一个基解，此基解又对应着另一个对偶可行解（检验数非正）。如果得到的基解的分量皆非负，则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基解由不可行逐步变为可行。当同时得到对偶问题与原问题的可行解时，便得到原问题的最优解。2/4/202321对偶单纯形法在什么情况下使用：

应用前提：有一个基，其对应的基满足:

①单纯形表的检验数全部非正（对偶可行）

②变量取值可有负数（非可行解）。

注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯型表。2/4/202322

1.建立初始对偶单纯形表,对应一个基解,所有检验数均非正,转2；

2.若b’≥0,则得到最优解,停止;否则,若有bk<0则选k行的基变量为出基变量,转33.若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj’<0则选

=min{j’/

akj’┃akj’<0，j=1,2,…,n}=r’/akr’那么

xr为进基变量,转4；

4.以akr’为主元素,作矩阵初等行变换使其变为1,该列其他元变为0,转2。对偶单纯形法求解线性规划问题计算过程2/4/202323例3.2：用对偶单纯形法求解线性规划问题：

Minf=15y1+24y2+5y3

S.t.

6y2+y3≥25y1+2y2+y3≥1

y1,y2,y3≥0Maxz=－15y1－24y2－

5y3

S.t.

6y2+y3

－y4=25y1+2y2+y3

－y5=1

y1,y2,y3,y4,y5≥0Maxz=－15y1－24y2－

5y3

S.t.－6y2

－y3

＋y4=－2

－5y1－2y2－y3＋y5=－1

y1,y2,y3,y4,y5≥02/4/202324cj－15－24－500CB

基

by1y2y3y4y50y4

－2

0[－6]－1100y5

－1

－5－2－101

σj－15－24－500－24y21/3

011/6－1/60

0y5

－1/3

－50[－2／3]－1／31

σj－150－1－40－24y21／4－5／410－1／41／4－5y31／2

15／2011／2－3／2

σj－15／200－7／2－3／2对偶问题的最优解X=(7/2,3/2,15/2,0,0)T原问题的最优解Y=(0,1/4,1/2,0,0)Tx1x2x3x4x52/4/202325对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题2/4/202326是是是是否否否否所有所有得到最优解计算计算对应原规划的基本解是可行的对应原规划的检验数为非正所有所有计算计算以主元素为中心进行迭代以主元素为中心进行迭代停没有最优解没有最优解单纯形法对偶单纯形法2/4/202327进一步理解最优单纯性表中各元素的含义考虑问题

Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

≤b1a21x1+a22x2+…+a2nxn

≤b2

….

am1x1+am2x2+…+amnxn

≤bmx1，x2，…，xn≥0§5灵敏度分析cj,bi,aij,m,n参数2/4/202328当这些参数中的一个或几个发生变化时，线性规划问题的最优解会发生什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变？所要解决的问题重要公式1、将参数的改变通过下面的公式计算后直接反映到最终单纯形表上2、检查原问题是否仍有可行解2/4/2023294、按下表所列情况得出结论或决定继续计算的步骤原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，重新计算3、检查对偶问题是否仍有可行解2/4/202330一、价值系数cj发生变化线性规划问题中变量系数cj

的变化仅仅影响到检验数的变化，所以将cj

的变化直接反映到最终单纯形表中，此时只会出现如上表中的前两种情况cj21000CB

基(变量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/21.521/8-4/91.522/4/202331cj21000CB

基(变量)b

x1x2x3x4x50x46

005/41－61.5x12

10－1/5012x23011/500

σj

00－1/100－2/3因为变量x4对应的检验数大于零，属于第二种情况，所以用单纯形法继续迭代最优解XT=(2,3)T2/4/202332二、常数项b发生变化常数项的变化反映到最终单纯形表中将引起b列数字的变化，所以可能出现第一或第三两种情况。若是第一种情况，问题的最优基不变，变化后的b列值为最优解；出现第三种情况时，用对偶单纯形法继续找出最优解2/4/202333cj21000CB

基(变量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/21524515325转下页2/4/202334cj21000CB

基(变量)b

x1x2x3x4x50x335/2

0015/4－15/22x111/2

1001/4－1/21x2

－1/2

010[－1/4]3/2

σj

000－1/4－1/2用对偶单纯形法cj21000CB

基(变量)b

x1x2x3x4x50x315051002x15110010x42

0－401－6

σj

0－100－22/4/202335三、增加一个变量xj的分析增加一个变量x’j在实际问题中反映为增加一个新的产品。其分析步骤为例如，美佳公司计划推出新产品III，生产每件产品所需设备A、B及调试工序的时间分别为3、4、2小时，该产品的盈利为3元／件。试分析新的生产计划2/4/202336设该公司生产新产品x6，则有c6=3P6=(3,4,2)Tcj210003CB

基(变量)b

x1x2x3x4x5x60x315/2

0015/4－15/2－72x17/2

1001/4－1/201x23/2

010－1/43/22

σj

000－1/4－1/212/4/202337cj210003CB

基(变量)b

x1x2x3x4x5x60x315/2

0015/4－15/2－72x17/2

1001/4－1/201x23/2

010－1/43/2［2］

σj

000－1/4－1/21cj210003CB

基(变量)b

x1x2x3x4x5x60x351/4

07/213/8－9/402x17/2

1001/4－1/203x63/4

01/20－1/83/41

σj

0－1／20－1/8－5/40用单纯形法继续迭代2/4/202338四、分析参数aij的变化1、变量xj在最终单纯行表中为非基变量，参照上一段算法2、变量xj在最终单纯行表中为基变量，则相应的B和B-1会发生变化例如，在美佳公司，若产品II每件所需设备A、B及调试工序的时间分别为8、4、1小时，该产品的盈利为3元／件。试分析新的生产计划先将生产工时变化后的新产品II看成是一种新产品，生产量记为x’2，计算步骤与上一段一样2/4/202339cj210003CB

基(变量)b

x1x2x3x4x5x’20x315/2

0015/4－15/211/22x17/2

1001/4－1/21/21x23/2

010－1/43/2[1/2]

σj

000－1/4－1/23/2因为x2已经变换为x’2，故用x’2替换出x2，并在下一个表中不保留x22/4/202340cj23000CB

基(变量)b

x1x’2x3x4x50x3

-9

0014－242x12

1001/2－23x’23

010－1/23

σj

0001/2－5cj23000-MCB

基(变量)b

x1x’2x3x4x5x6-Mx6900-1-4[24]12x12

1001/2－203x’23

010－1/230

σj

00-M1/2-4M－5+24M0添加人工变量原、对偶问题均为非可行解2/4/202341cj23000-MCB

基(变量)b

x1x’2x3x4x5x60x53/800-1/24-1/611/242x111/410-1/121/601/123x’215/8011/800-1/8

σj

00-5/24-1/30－M+5/24结论：最优生产计划为生产家电I11/4件,家电II15/8件2/4/202342增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入1个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。五、增加一个约束条件的分析2/4/202343例如，美佳公司生产的产品还须一道实验工序，家电I:3小时，家电II：2小时，又实验工序的生产能力为12小时。问如何安排最优生产计划？增加的约束条件为3x1+2x2≤12将原最优解代入，得3×7/2+2×3/2=27/2>12故原问题的最优解不是现在的最优解假设≤12，则原问题的最优解是现在的最优解，问题结束2/4/202344将新的约束条件添加松弛变量3x1+2x2+x6=12以x6为基变量，将上式反映到最终单纯形表中cj210000CB

基(变量)b

x1x2x3x4x5x60x315/2

0015/4－15/202x17/2

1001/4－1/201x23/2

010－1/43/200x612320001