第三章 对偶问题与 灵敏度分析

第一讲 对偶理论

第二讲 灵敏度分析

第一讲 对偶理论一、对偶问题产品 车间 A B C 单位产品获利 工时单耗 甲 乙 1 0 3 3 0 2 4 5 生产能力 8 12 36

例1中该厂的产品销售，现有另一企业想租赁其设备。 厂方为了在谈判时心中有数，需掌握设备台时费用 的最低价码，以便衡量对方出价，对是否出租做出 抉择。

第一讲 对偶理论一、对偶问题

对原企业而言，它用于出租或转让的资源收益不应 低于自行生产产品所获得的利润，才肯出租或转让。 在这个问题上厂长面临着两种选择：自行生产或出 租设备。首先要弄清两个问题： ①如何合理安排生产，取得最大利润? ②为保持利润水平不降低，资源转让的最低价格是多少？

问题 ①的最优解：x1=4,x2=6,Z*=42。

第一讲 对偶理论第二个问题：出让定价

假设出让设备A、B、C所得利润分别为y1、y2、y3 原本用于生产甲产品的设备台时，如若出让，不应低于自行 生产带来的利润，否则宁愿自己生产。于是有对甲产品 y1+0y2+3y3 ≥ 3 同理，对乙产品而言，则有 0y1+2y2+4y3 ≥ 5 设备台时出让的收益(租用企业希望出让的收益最少值) Min W =8y1+12y2+36y3 显然还有 y1,y2,y3 ≥0

第一讲 对偶理论例1的对偶问题的数学模型Max Z= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x + 4x ≤36 1 2 x1 , x2 ≥ 0 Min W= 8y1+12y2+36y3 y1 + 0y2 + 3y3 ≥ 3 S.t. 0y1 + 2y2 + 4y3 ≥ 5 y1 , y2 , y3 ≥ 0

称后一个线性规划问题为前一个线性规划问题的对偶问题。 对偶问题的最优解： y1=0,y2=1/2,y3=1,W* =42 两个问题的目标函数值相等，这不是偶然的，上述两个问题 实际上是一个问题的两个方面，如果把前者称为线性规划原 问题，则后者便是它的对偶问题，反之亦然。 对偶问题的最优解对应于原问题最优单纯型法表中“初始基 变量的检验数的负值”。

第一讲 对偶理论原问题最优单纯型法表CjCB XB b

3

5

0

0

0

x10 0 1 0

x20 1 0 0

x31 0 0 0

x42/3 1/2 -2/3 -1/2

x5-1/3 0 1/3 -1

0 5

x3 x2

4 6 4 -42

3

x1

检验数 j

对偶问题的最优解： y1=0,y2=1/2,y3=1 对应于原问题最优 单纯型法表中，初始基变量x3 , x4 , x5的检验数的负值。

对称形式下对偶问题的一般形式对称形式：变量均为非负，其约束条件当目标函数求极 大时均取“≤”,当目标函数取极小时均取“≥”。

线性规划原问题(P)

Max Z= c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ≤ b1 a21x1+a22x2+…+a2nxn ≤ b2 …………… am1x1+am2x2+…+amnxn ≤ bm x1,x2,…,xn ≥0

对偶问题(D)

Min Z= b1y1+b2y2+…+bmym a11y1+a21y2+…+am1ym ≥ c1 a12y1+a22y2+…+am2ym ≥ c2 …………… a1ny1+a2ny2+…+

amnym ≥ cm y1,y2,…,ym ≥0

第一讲 对偶理论对称形式下对偶模型的特点 若原问题为极大，则对偶问题为极小； 对极大的原问题，其约束条件为≤,而极小化的对偶问题的 约束为≥; 原问题的变量个数即为对偶问题的约束条件的个数，而原问 题的约束条件的个数，即为对偶问题的变量的个数； 原问题的约束条件的右端常数项即为对偶问题的目标函数中 变量的系数，而原问题的目标函数中变量的系数即为对偶问 题的约束条件的右端常数项。

第一讲 对偶理论对称形式下原问题与对偶问题的对应关系Max Z Min W

x1a11a21 a31 a41

x2a12 a22 a32 a42

x3a13 a23 a33 a43≤ ≤ ≤ ≤

x3 ≥ 0b1 b2

y1 y2 y3 y4

b3b4

yi ≥ 0

c1

c2

c3

一般形式下对偶关系对应表目标函数类型 目标函数系数与右 边项的对应关系

原问题(或对偶问题) 对偶问题(或原问题) Max Min目标函数系数 右边项系数 右边项系数 目标函数系数

变量数与约束数的 对应关系原问题变量类型与 对偶问题约束条件 的对应关系 原问题约束类型与 对偶问题变量类型 的对应关系

变量数 n 约束数 m ≥0 变量 ≤0 无限制 ≤ 约束 ≥ =

约束数 n 变量数 m ≥ 约束 ≤ = ≥0 变量 ≤0 无限制

第一讲 对偶理论例:写出对偶模型Min Z= 5x1 +3 x2- x3 x1 - x2 +2 x3 ≥ 5 S.t. 4x1 +x2 - x3 ≤10 x1 + x2 - x3 = 4 x1 ≥0, x2 ≤0, x3 无限制 Max W= 5y1+10y2+4y3 y1+ 4y2+ 1y3 ≤ 5 S.t. -y1+ y2+ y3 ≥ 3 2y1 - y2 - y3 =-1 y1≥0, y2≤0, y3 无限制

第一讲 对偶理论练习:求对偶模型Max Z = x1 +2x2- 3x3+ 4x4 -x1 + x2 -x3 - 3x4 = 5 S.t. 6x1 +7x2 -x3+ 5x4 ≥ 8 12x1 - 9x2 +7x3+6x4 ≤ 10 x1 ≥0, x3 ≥ 0, x2 , x4 无限制

第一讲 对偶理论二、对偶问题的基本性质 对称性： 对偶问题的对偶是原问题。 弱对偶性： 若X0为原问题(P)的可行解，Y0是对偶问题(D)的可行解，则 CX0 ≤Y0b。 最优解： 若X*为(P)的可行解，Y*是(D)的可行解，且CX*=Y*b,则 X*, Y* 分别为最优解。 强对偶性 若(P)有最优解，则(D)也有最优解；反之亦然，且两者目标 函数相等。

第一讲 对偶理论例题:已知线性规划问题Min Z = x1 - x2 +x3 x1 -x3 ≥ 4 S.t. x1 -x2 +2x3 ≥ 3 x1 , x2 , x3 ≥0 证明：此问题的对偶问题为： Max W = 4y1 + 3y2 y1 + y2 ≤ 1 S.t. - y2 ≤ -1 -y1 + 2y2 ≤ 1 y1 , y2 ≥0 试用对偶理论证明 此线性规划问题有 无界解(即有可行 解，但无最优解)。

第一讲 对偶理论三、对偶问题的经济解释——影子价格

Z c j x j bi yi W* * * j 1 i 1

n

m

*

此时，同时达到最优解

Z * yi bi

*

bi为第i种资源的拥有量

说明 yi是右端项 bi每增加一个单位的第 i种资源对目标函数 Z的贡献。 对偶变量 yi在经济上表示原

问题第i种资源的边际价值。 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 若原问题的价值系数Cj表示单位价格，则 yi *称为影子价格。 若原问题的价值系数Cj表示单位利润，则 yi *称为影子利润。

第一讲 对偶理论 特别注意 影子价格不是资源的实际价格 ( 市场价格 ) ,而是资源配置结 构的反映，是在其它数据相对稳定的条件下对现有资源实现 最大效益时的一种估价；它表明资源增加对总效益产生的影 响。 对资源i总存量的评估：购进 or 出让 对资源i当前分配量的评估：增加 or 减少 ①它表明了当前的资源配置状况，告诉经营者应当优先增加 何种资源，才能获利更多。 ②告诉经营者以怎样的代价去取得紧缺资源。 ③提示设备出租或原材料转让的基价。 ④告诉经营者补给紧缺资源的数量，不要盲目大量补给。 ⑤借助影子价格进行内部核算。