运筹学：第三章 线性规划对偶理论及其应用

第三章线性规划对偶理论及其应用第一节线性规划对偶问题第二节对偶规划的基本性质第三节对偶单纯形法第四节影子价格和灵敏度分析第五节用Excel进行灵敏度分析第一节线性规划对偶问题

一、引例二、线性规划对偶问题三、对称形式与非对称形式四、原问题与对偶问题的关系甲乙资源限量煤（吨）94360电（千瓦时）45200油（吨）310300单价（万元）712例3.1：A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见下表：收入最大化生产计划模型:Maxz=7x1+12x2

(总销售收入)s.t.9x1+4x2360

(煤资源限制)4x1+5x2200

(电资源限制)

3x1+10x2300(油资源限制)

x1

0，x20(非负条件)x1

=产品甲的计划生产量x2=产品乙的计划生产量一、引例现有另一家B公司欲收购A公司的资源（煤、电、油）。B公司收购A公司的本质行为是，以适当的价格将A公司的所有资源全部买下，且A公司自愿放弃原来的生产活动。

一方面，A公司愿意按照这种价格出售其所有资源，另一方面，B公司力求以最小代价收购资源为目标

注意到A公司总是按照收入最大化的生产计划组织自己的生产活动。因此，要使A公司自愿出售其全部能源，必须是A公司的资源出售收入不低于生产产品所得收入。这表明：A公司按照最优生产计划所获得的生产收入便是其出售所有能源资源的收入底线。双方谈判的焦点——各种资源的价格y1=煤价（万元/吨）y2=电价（万元/千瓦时）y3=油价（万元/吨）Minw=360y1+200y2

+300y3

B企业的目标:A工厂的底线:y1

0，y20，y30价格的非负性:分析：如果9y1+4y2

+3y3

<7，则A工厂可把部分资源用于生产甲产品将会获得更好的收益。这表明：A工厂将不会出售所有资源。甲乙资源煤94360电45200油310300单价712按B企业提供的能源价格折算的产品价格A工厂的要求产品价格9y1+4y2

+3y3

74y1+5y2

+10y3

12双方谈判的焦点——每种能源的价格

分析：如果4y1+5y2

+10y3

<12，则A工厂可把部分资源用于生产乙产品将会获得更好的收益。这表明：A工厂将不会出售所有资源。当B厂的收购价大于等于A厂自己生产所带来的利润时，A厂才有可能出售自己的所有资源。对于B厂来说，它们希望收购价越少越好，同时又希望能收购到资源，所以当时，是双方都能容易接受的结果，当这个结果存在时，这个结果就是两个工厂决策者认为的最优方案。Maxz=7x1+12x2s.t.9x1+4x23604x1+5x22003x1+10x2300

x1

0，x20Minw=360y1+200y2

+300y3

s.t.9y1+4y2

+3y3

74y1+5y2

+10y312y1

0，y20，y30A工厂的计划模型B企业的定价模型这两个线性规划问题无论从经济意义上或者是从数学意义上都是紧密相连的：

—

从经济上看，A公司的目标是寻找最优生产方案，以获得最大生产收入；而B公司是寻求最优价格，使总成本最低。

—

从数学模型的形式上看，它们也是关联的，比较模型如下：价格系数(c)资源向量(b)最大化(Max)变量个数(n)约束个数(m)约束系数行(A)资源向量(c)价格系数(b)最小化(Min)约束个数(n)变量个数(m)约束系数列(AT)原问题(LP):Maxz=cx

s.t.Axbx0对偶问题(LD):Minw=bTy

s.t.ATy

cTy0

对于上述原问题的约束条件是“≤”形式的对偶问题我们也称为对称形式的线性规划问题的对偶问题；二、线性规划对偶问题对偶定义:

(LP)Maxz=cx(DP)Minw=bT

ys.t.Ax≤bs.t.AT

y≥cT

x≥0y≥0

“Max--≤”“Min--≥”上述形式称为对称形式：互为对偶对称形式的线性规划问题与对偶问题具有如下特点：若一个模型为目标求“最大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“最小”，约束是“大于等于”的不等式。从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从数据b、c的位置看：在两个规划模型中，b和c的位置对换。两个规划模型中的变量皆非负。三、对称形式与非对称形式非对称形式的对偶规划计算步骤如下：（1）将原问题约束条件中“≤”的不等式两边乘以-1变为“≥”的不等式；（2）对偶问题是最大化问题；（3）原问题有n个决策变量，则对偶问题有n个约束条件。对偶问题的第一个约束条件对应原问题中的x1变量，对偶问题的第二个约束条件对应原问题中的x2变量，依此类推。（4）原问题有m个约束条件，则对偶问题有m个决策变量。对偶问题的y1变量对应原问题中的第一个约束条件，对偶问题的y2变量对应的是原问题中的第二约束条件，依此类推。（5）原问题的约束条件的右端值成为对偶问题的目标函数系数。（6）原问题的目标函数系数成为对偶问题中的约束条件的右端值。（7）目标函数中原问题第i个变量的系数成为对偶问题中第i个约束条件的常数项。（8）若原问题的第i个约束条件为等式，则对偶问题的第i个决策变量取任意值。（9）若原问题的第i个决策变量无符号限制，则对偶问题的第i个约束条件为等式约束。例3.2写出下列线性规划问题的对偶问题：解：首先将最小化问题化为最大化问题：四、原问题与对偶问题的关系例3.3：写出下列线性规划问题的对偶问题：

将原问题中”≥”的约束化为”≤”,即第二节对偶规划的基本性质一、对称性二、弱对偶性三、最优性四、强对偶性五、松驰互补性

(LP)Maxz=cx(LD)Minw=bTys.t.Ax≤bs.t.ATy≥cT

x≥0y≥0

其中,考虑如下形式的线性规划原问题（LP）：对偶规划问题具有如下基本性质:

(LP):Maxz=cx

s.t.Axbx0(LD):Minw=bTy

s.t.ATy

cTy0对偶问题(LD):Max–w=-bTy

s.t.-ATy-cTy0(LP):Min-z=-cTxs.t.-(At)Tx

-bx0对偶问题定理3.1（对称性）一个线性规划的对偶问题的对偶问题便是原问题。（互为对偶问题！）一、对称性maxz=cxminw=bTys.t.Ax≤b

（3.3）s.t.ATy≥cT

（3.4）

x≥0y≥0定理3.2（弱对偶性）：如果x，y分别是（3.3）和（3.4）的可行解，则bTy≥cx证明：x，y分别是（3.3）和（3.4）的可行解，则因为ATy≥cT，即二、弱对偶性已知定理3.3（最优性）：如果x，y分别是（3.3）和（3.4）的可行解，且有bTy=cx，则x，y分别是（3.3）和（3.4）的最优解。证明：设x*是原问题（3.3）的最优解，y*是对偶问题（3.4）的最优解。则

由弱对偶性得：

三、最优性四、强对偶定理：证明：设x是原问题的最优解，引入松弛变量设B是原问题最优解的基矩阵，因为（1）存在最优解，B是最优解的基矩阵，所以

(1)令定理3.4（强对偶性）：原问题有最优解x,则对偶问题也有最优解y.且。

再由弱对偶性可知：x是对偶问题的最优解。定理3.5（互补松弛性）：设、分别是（3.3）和（3.4）的可行解，则、是最优解的充要条件是对所有的和，下列关系成立：（1）如果，有；（2）如果，有；（3）如果，有；（4）如果，有。其中是A的第列，是A的第行。证明：cTx≤

(ATy)Tx=yTAx≤yTb=bTy设x*,y*分别（LP）和（LD）的最优解；由最优性：cTx*=bTy*

得：yTAx=yTb;

所以，yT(Ax–b)=0;五、松驰互补性第三节对偶单纯形法一、对偶单纯形法的基本思想二、对偶单纯形算法三、对偶单纯形表格法四、对偶单纯形算法与单纯形算法比较一、对偶单纯形法的基本思想单纯形方法:要求所有常数项大于零。且已知初始基本可行解对偶单纯形法是在未知原问题初始基本可行解时，求最优解的另一种方法。(1)定义：设x0是原问题的基本解，它对应的基矩阵为B，令yT=cBB-1，若y是其对偶问题的可行解，则称x0是原问题的对偶可行基本解。对偶可行的基本解不一定是原问题的可行解，当对偶可行的基本解x0=(B-1b,0)也是原问题的可行解(即B-1b≥0)时，则它是原问题的最优解。对偶单纯形法的基本思想：首先从原问题的一个对偶可行的基本解（它不是原线性规划问题的可行解）出发，求改进的对偶可行的基本解，向原问题的可行域逼近，当求到对偶可行的基本解是原问题的可行解时，就得到了最优解1.给定一个初始对偶可行的基本解，设相应的基为B；2.若b’=

B-1b≥0,则停止计算，现行对偶可行的基本解为最优解;否则,令，则该行所对应的变量xr为换出基的变量；3.若所有j,aij’≥0，则停止计算，原问题无可行解;否则，令（或）

xr为换入基的变量；4.以xrk’为主元进行主元消去,返回2。对偶单纯形法的计算步骤：二、对偶单纯形算法三、对偶单纯形表格法

标准化：

maxz=3x1+x2s.t.

-x1-x2+x3=-1-2x1-3x2+x4=-2

x1,x2,x3,x4≥0minz=3x1+x2s.t.x1+x2≥12x1+3x2≥2

x1,x2≥0

例3.4：用对偶单纯形法求解下列线性规划：

cj3100cBxBbx1x2x3x40x3-1-1-1100x4-2-2[-3]01σj31000x3-1/3-1/301[-1/3]1x22/32/310-1/3σj7/3001/30x4110-311x2111-10σj2010所以得最优解：，最优目标函数值。

minz=2x1+2x2s.t.3x2≥1

x1+2x2≥22x1+x2≥3x1≥1

x1,x2≥0

例3.5：求解线性规划：

maxw=u1+2u2+3u3+u4s.t.u2+2u3+u4+u5=23u1+2u2+u3+u6=2u1,u2,…,u6≥0

cj123100b5/y5cBuBbu1u2u3u4u5u60u5201[2]11010u623210012σj1231003u3101/211/21/200u61[3]3/20-1/2-1/211/3σj11/20-1/2-3/203u3101/211/21/201u11/311/20-1/6-1/61/3σj000-1/3-4/3-1/3所以得最优解：，最优目标函数值。单纯形（max）对偶单纯形（min）前提条件最优性检验若,则最优若,则最优换入、换出变量的确定先确定换入变量先确定换出变量后确定换出变量后确定换入变量原始基本解的变化可行解最优解非可行解可行解（即最优解）四、对偶单纯性算法与单纯性算法比较第四节影子价格和灵敏度分析一、影子价格二、灵敏度分析一、影子价格影子价格是经济学上一个重要的概念，它表示约束条件右端值（即资源）改变1个单位时，目标函数（即利润）最优值的变化量。它度量了约束条件对应的那种资源的边际价值。如果约束条件常数项表示资源，目标函数最优值表示最优收益，则影子价格是指资源增加对最优收益产生的影响，所以又称为资源的边际产出或资源的机会成本。它表示资源在最优产品组合时所能具有的潜在价值。资源的影子价格越高，表明该种资源的贡献越大。在完全的宏观市场条件下，随着资源的买进和卖出，影子价格随之变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。影子价格的经济含义是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性的增加。影子价格为正数，表明该种资源在最优决策下已充分利用耗尽，并成为进一步增加总收益的紧缺资源。

影子价格是对企业资源的使用具有一顶的指导意义。企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。在原问题和对偶问题中，有关决策变量、影子价格之间的对应关系可用下表表示：Minz=4x1+7x2+8x3s.t.x1+x2≥3x2+2x3≥

1x1+x2+x3≥

8

x1

0，x20，x20例3.6：求下列原问题的最优解及影子价格和对偶问题的最优解和影子价格。解：最优解为x*={7.5,0,0.5}影子价格为{0，2，4}最优值为34其原问题的对偶问题Maxw=3u1+u2+8u3s.t.u1+u34u1+u2+u3

72u2+u3

8

u1

0，u20，u20最优解为u*={0，2，4}；影子价格为{7.5,0,0.5}；最优值为34。Maxz=7x1+12x2s.t.9x1+4x23604x1+5x22003x1+10x2300

x1

0，x20例3.7：考虑2.1的影子价格问题。用单纯形法求得：x1=20，x2=24。对偶问题Minw=360y1+200y2+300y3s.t.9y1+4y2+3y3≥74y1+5y2+10y3≥

12

y1

0，y20，y20用单纯形法求解得：y1=0，y2=1.36，y3=0.52。

根据影子价格确定某种资源的追加价值。

—

例如：煤、电、石油的影子价格分别为0、1.36、0.52，则可确定应首先增加电资源，因为相比之下它能导致更多的生产收入。

—

又如：每增加1度电能使生产收入增加1.36

，如果1度电的价格高于1.36就不划算了；反之，如果1度电的价格低于1.36，则购买电资源是有利可图的。根据影子价格制定新产品的价格。

—

例如，A工厂要生产一种新产品，如果每单位新产品需耗用煤、电、石油分别为5、10、3单位，则新产品的价格必须大于5×0+10×1.36+3×0.52=15.19才可能增加生产收入。如果售价低于15.19，生产该新产品是不划算的。

在线性规划中，我们假定模型的系数都是已知常数。而在实际中，周围的环境、条件都是在不断地变化，因此这种假定很难成立。灵敏度分析将回答：最优解对线性规划模型中各种系数变化的敏感性二、灵敏度分析1．目标函数系数的变化：

1）如果非基变量的系数变为时，此时不变，

如果，则原来问题的最优解也是新问题的最优解。考虑下列线性规划问题：设最优解为，，其中B是最优可行基，分两种情况讨论目标系数的变化：2）若基变量的系数变为时，此时改变，所以判别数改变为：其中，，。当时，，，所以；当时，；

如果，则改变后为进基变量。把原来最优单纯形表中的换成，然后用单纯形表求新问题的最优解。下面以例子说明目标函数系数的变化对最优解的影响。例3.8：某球袋公司生产高中价位的球袋。生产该球袋要经过对原材料的剪裁、缝合、定型、检验和包装四个过程。生产一个中档球袋需用：7/10小时剪裁，1/2小时缝合、1小时定型、1/10小时检验和包装。生产高档球袋则需用：1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验和包装。由于该公司各生产部门的生产能力有限。每个部门的最大生产时间分别是：剪裁部门630小时、缝合部门600小时、定型部门708小时、检验和包装部门135小时。通过市场调研生产一个中档球袋的利润是10元，生产一个高档球袋的利润是9元。公司应各生产多少中档和高档球袋才能使公司的利润获得最大。设x1：表示中档球袋的产量；x2：表示高档球袋的产量；则可得到如下的数学模型：max10x1+9x2

s.t.7/10x1+x2≤6301/2x1+5/6x2≤600

x1+2/3x2≤7081/10x1+1/4x2≤135x1≥0，x2≥0现在的问题是：当中档球袋的价格在什么范围内变化时，公司的最优生产计划不变。1090000bi/yicBxBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.156010x154010-1.24901.87500x61800-0.34400.14100-4.3750-6.9380解：用单纯形法求解得最终单纯形表：原问题的最终单纯形表如下：90000bi/yicBxBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.1560x154010-1.24901.87500x61800-0.34400.14100-4.3750-6.9380当时，最优解不变，即，，解之，即当的系数在此范围内变化时，最优解基不变仍为生产中档球袋540个，高档球袋252个。但最优目标函数值将变化。例3.9：用图解法对例3.8进行灵敏度分析。解：因为Q点是最优解点，目标函数线为：7/10x1+x2；过Q点的定型直线l1：x1+2/3x2=708，即x2=-3/2x1+1062，其斜率为-3/2；过Q点的剪裁直线l2：7/10x1+x2=630，即x2=-10/7x1+900，其斜率为-10/7；设c1表示中档拉杆箱球袋的利润，c2表示高档拉杆箱球袋的利润，则目标函数的直线的一般式为：c1x1+c2x2=p，其斜率k=-c1/c2；所以，当目标函数的斜率满足时，Q点仍为最优解点，即

（3.25）当高档箱高档球袋的利润为9元时，则中档箱中档球袋的利润变化范围可通过求解不等式（3.25）得到：当中档箱中档球袋的利润为10元时，则高档箱高档球袋的利润变化范围通过求不等式（3.25）得：2．约束条件右边值的变化：设b改变为，改变前的最优基为B。1）如果，则原来的最优基不变，但基变量的取值和目标函数将发生变化。2）如果≯0，则原来的最优基不再是新问题的可行基。但所有判别数，所以现行基本解是对偶可行的基本解。此时只要把原最优表中的右端列修改为：，然后用对偶单纯形法求解新问题。例3.10仍考虑例3.8maxz=10x1+9x2

s.t.7/10x1+x2≤630剪裁部门

1/2x1+5/6x2≤600缝合部门

x1+2/3x2≤708定型部门

1/10x1+1/4x2≤135检验和包装部门x1≥0，x2≥0

分析当剪裁部门的时间再增加20小时，同时定型部门增加100小时。对公司利润的影响。解：用单纯形法求解原问题得最终单纯形表如下：1090000bi/yicBxBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.156010x154010-1.24901.87500x61800-0.3400.14100-4.3750-6.9380最优解是：。最优解的目标函数值为：。原问题的基变量，相应的基矩阵为：

所以最优解基不变，但取值将变为：x1=158.25，x2=702.5，此时新的目标函数值是：z=10x1+9x2=7905。增加利润7905-7668=237。3．变量个数的变化：

增加一个新变量在实际问题中就是增加一种新产品。设增加的变量为，B是原问题的最优基。如果判别数，则新问题最优解与原问题最优解一样，只需将得到的和直接写入单纯形表中即可。如果，则继续用单纯形法计算。例3.11在例3.8中，公司领导决定增加一种新款产品，经市场调研，该新款产品的利润可达12.85元，每件新产品需要0.8小时剪裁，1小时缝合，1小时定型，0.25小时检验和包装。此时，原来两种产品的最优生产计划是否改变？设x7为生产新款产品的数量，则例3.8的数学模型改变为：maxz=10x1+9x2+12.85x7

s.t.7/10x1+x2+0.8x7≤630剪裁部门

1/2x1+5/6x2

+x7≤600缝合部门

x1+2/3x2+x7≤708定型部门1/10x1+1/4x2+0.25x7≤135检验和包装部门x1≥0，x2≥0，x7≥0，。对于新问题,因为，，所以，。解：因为原问题例3.8的最优解变量为：，相应的基矩阵为：在原问题最终单纯形表中的右端加入一列p7

，得新单纯形表如下：109000012.85bi/yibx1x2x3x4x5x6x79x2252011.8740-1.31200.18813440x412000-0.93710.15600.406295.410x154010-1.24901.87500.875617.10x61800-0.34400.141(0.116)155.700-4.3750-6.93802.4125因为，原问题的最优解发生了变化。所以，继续用单纯形法对表求解，得最终单纯形表如下：109000012.85bi/yibx1x2x3x4x5x6x712.85x391.600.41110-0.63-0.6700x4320-0.1101-0.17-3.33010x12801-0.56001.67-6.6700x742801.2200-0.6676.6710-1.15900-8.1-190增加一个新品种后的最优生产计划为：中档球袋，高档球袋，新款箱，最优目标函数值为：z=8299.8。4．约束条件个数的变化

当增加一个约束条件时，如果原问题的最优解满足新增加的约束条件，则它也是新问题的最优解；如果原问题的最组优解不满足新增加的约束条件，则需要把新约束条件增加到原来单纯形表中重新求解。

例3.12:

在例3.11中，因为高档球袋的产量为0，为了占有各种型号的市场份额，对此结果公司的决策者显然不会满意，于是决定高档球袋的产量至少是中档球袋产量的30%。增加一个约束条件，即。这样原规划问题模型将变为：maxz=10x1+9x2+12.85x3

s.t.7/10x1+1x2+0.8x3≤630剪裁部门

1/2x1+5/6x2+x3≤600缝合部门

1x1+2/3x2+x3≤708定型部门

1/10x1+1/4x2+0.25x3≤135检验和包装部门

0.3x1－x2≤0x1≥0，x2≥0，x3≥0解：对5个约束引入5个非负松弛变量x4，x5，x6，x7，x8得到标准形式：maxz=10x1+9x2+12.85x3

s.t.7/10x1

+1x2

+0.8x3+x4≤630剪裁部门

1/2x1+5/6x2+x3+x5≤600缝合部门

1x