产品的利润： y1 y2 3
乙产m 品in 同理w ：6y1 y18 y2 2 y23 y3 y34
把s企.t.业 y所1 有原y 2 料出让 的3 总收入：
y1
2
y2
y3
4
y1 , y 2 , y3 0
w6y18y23y3
只能在满足≥所有产品的 利润的条件下,其总收入尽
可能少,才能成交.
第5页
一、对偶问题的提出
任何一个求极大的线性规划问题都有一个求极小的线性 规划问题与之对应，反之亦然.
把其中一个叫原问题，则另一个就叫做它的对偶问题， 这一对互相联系的两个问题就称为一对对偶问题。
LP1 max z3x14x2
s.t. x 1 x 2 6
x1
2
x2
8
x2 3
x 1 , x 2 0
第2页
一、对偶问题的提出
对同一问题从不同角度考虑，有两种对立的描述。
例例如1：、平应面如中何矩安形排的面生积产与计周划长，的关使系一天的总利润最大？
周某长企一业定生面产积甲最、大乙的两矩种形产是品正，方要形用: 面A、积B一、定C周三长种最不短同的的矩原形料是。正每方生形产1 吨甲产品，需耗用三种原料分别为1，1，0单位；生产1吨乙产品，需耗用三 种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知 道每生产1吨甲产品企业利润为300元，每生产1吨乙产品企业利润为400元。
矩阵形式：
max z (3
4)
x1 x2
s.t. 1
1 0
1
6
2 1
x1 x2
8 3
x1 x2
0
max z=CX s.t. AX ≤b
X≥0
D m inw 6y18y23y3
s.t. y1 y 2 3
y1
2
y2
y3
4
y1 , y 2 , y 3 0
其中 yi ≥ 0 （i = 1,2,…,m）称为对偶变量。
第8页
(二)非对称型对偶问题
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3无约束 分析：化为对称形式。令 x2 x2，x3x3x3(x30,x30)
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3无约束 设 yj 表示第 j 种原料的收费单价
把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3无约束
第3页
假设该企业决策者决定不生产甲、乙产品，而是将厂
原问题（P）
LP2 m inw 6y18y23y3
s.t. y1 y 2 3
y1
2
y2
y3
4
y1 ,
y2,
y3
0
对偶问题（D）
第6页
二、原问题与对偶问题的对应关系
P max z3x14x2
s.t. x 1 x 2 6 y 1
x1
2
x2 x2
8 3
y2 y3
x 1 , x 2 0
X≥0
Y≥0
max z = c1x1 + c2x2 + … + cnxn
s.t. a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≤ b2
(P)
……
am1x1 + am2x2 + … + amnxn ≤bm xj ≥ 0 （j = 1,2,…,n）
min w = b1 y1 + b2 y2 + … +bm ym
s.t. a11y1 + a21 y2 + … + am1ym ≥ c1
a12y1 + a22y2 + … + am2 ym ≥ c2
(D)
……
a1ny1 + a2ny2 + … + amnym ≥ cn yi≥ 0 （i = 1,2,…,m）
里的例现1有、资应源如外何售安。排决生策产者计应划怎，样使制一定天每的种总资源利的润收最费大？
标准才合理？
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3无约束
yj 表示对第 j 种资源的估价
y1
min
w 6
8
3
y2
s.t.
1
1
1 2
0 1
Байду номын сангаас
y1 y2 y3
y3
3
4
y1
y2 y3
0
min w =bTY s.t. ATY ≥CT
Y ≥ 0 第7页
(一)对称型对偶问题
均取变“≤量”均号具s，m.t有.a当xA非目zX=负≤C标bX约函束数，求且极约小束时条均件取：“s当m≥.t”.i目nA号w标TY=。函≥bTCY数T 求极大时
第四章 线性规划的对偶理论
Duality Theory ➢ 线性规划的对偶问题 ➢ 对偶问题的基本性质 ➢ 对偶问题的经济解释——影子价格 ➢ 对偶单纯形法 ➢ 灵敏度分析
第1页
第四章 线性规划的对偶理论
Duality Theory ➢ 线性规划的对偶问题 ➢ 对偶问题的基本性质 ➢ 对偶问题的经济解释——影子价格 ➢ 对偶单纯形法 ➢ 灵敏度分析
设 xj 表示第 j 种产品每天的产量
max z = 3x1 + 4x2 s.t. x1 + x2 ≤ 6
x1 + 2x2 ≤ 8 x2 ≤ 3
x1 ≥ 0 , x2 ≥ 0
第4页
分析问题：
1、出让例每1、种资应源怎的样收制入定不收能费低标于准自才己合生理产时？的可获利润；
2、定价不能太高，要使对方能够接受。
max zc 1x 1 c2x2 c3x3 c3x3 s.t. a 1 1 x 1 a 1 2 x 2 a 1 3 x 3 a 1 3 x 3 b 1