第9页
(二)非对称型对偶问题
max z c1x1 c2x2 c3x3 c3x3 s.t. a11x1 a12 x2 a13x3 a13x3 b1
a21x1 a22 x2 a23x3 a23x3 b2 a2a1x21x1 a2a2 x222x2 a2a3x233x3 a2a3x233x3 b2b2 a31x1 a32x2 a33x3 a33x3 b3
n个
约
≥
束
≤
条 件
=
第14页
例2、写出下述线性规划问题的对偶问题
max z 2x1 3x2 5x3 x4
s.t. x1 x2 3x3 x4 5 2x1 2x3 x4 4 x2 x3 x4 6 x1 0,x2, x3 0, x4无约束
解：设对偶变量为 y1, y2, y3，则对偶问题为
对偶问题（D）
第6页
二、原问题与对偶问题的对应关系
P max z 3x1 4x2
s.t. x1 x2 6 y1

x1

2 x2 x2

8 3
y2 y3
x1, x2 0
矩阵形式：
max z (3
4)

x1 x2

s.t. 1 1
min w b1y1 b2 y2 b3 y3 s.t. a11 y1 a21 y2 a31 y3 c1
a12 y1 a22 y2 a32 y3 c2
a13 y1 a23 y2 a33 y3 c3 y1 0，y2无约束，y3 0
第11页
(二)非对称型对偶问题
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3
原问题（原对问偶题问题）
y1 y2 y3
目标函数 max 目标函数的系数 约束条件右端常数
目标函数的系数
3个
≥0
变
≤0
量
无符号限制
23个
约
≥
束
≤
条
=
件
第13页
二、原问题与对偶问题的对应关系
原问题（对偶问题）
目标函数 max
目标函数的系数
约束条件右端常数
约 m个
束≤
条 件
≥
=
n个
变
≥0
量
≤0
无符号限制
对偶问题（原问题）
目标函数 min
约束条件右端常数
目标函数的系数
m个
≥0
变
≤0
量
无符号限制
min w 5y1 4 y2 6 y3
s.t. y1 2 y2 2
y1
y3 3
3y1 2 y2 y3 5
y1 y2 y3 1
y1 0, y2 0, y3无约束
第15页
例3、写出下述线性规划问题的对偶问题
min z 2x1 3x2 5x3 x4
s.t. x1 x2 3x3 x4 5 2x1 2x3 x4 4 x2 x3 x4 6 x1 0,x2, x3 0, x4无约束
y3

4
y1, y2 , y3 0
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
max z c1x1 c2x2 c3x3 c3x3 s.t. a11x1 a12 x2 a13x3 a13x3 b1
aaa222a111xxx2111x1 aaa222a222xxx22222x2 aaa222a333xxx23333x3 aaa222a333xxx23333x3 bbb222b2 a3a13x11x1 a3a23x22x2 a3a33x33x3 a3a33x33x3 b3b3 x1, x2 , x3, x3 0
对偶变量
y1 y2 y2 y3
第10页
(二)非对称型对偶问题
令 y2 y2 -y2，y3 y3
min w b1y1 b2 y2 b2 y2 b3 y3 s.t. a11 y1 a21 y2 a21 y2 a31 y3 c1
x1≥0, x2≤0, x3无约束
约
3个
束
≤
min w b1y1 b2 y2 b3 y3 s.t. a11 y1 a21 y2 a31 y3 c1
条
≥
件
=
a12 y1 a22 y2 a32 y3 c2 a13 y1 a23 y2 a33 y3 c3 y1 0，y2无约束，y3 0
a12 y1 a22 y2 a22 y2 a32 y3 c2 a13 y1 a23 y2 a23 y2 a33 y3 c3 a13 y1 a23 y2 a23 y2 a33 y3 c3 y1, y2 , y2, y3 0
第2页
一、对偶问题的提出
对同一问题从不同角度考虑，有两种对立的描述。
例例如1：、平应面如中何矩安形排的面生积产与计周划长，的使关系一天的总利润最大？
周某长企一业定生面产积甲最、大乙的两矩种形产是品正，方要形用: 面A、积B一、定C周三长种最不短同的的矩原形料是。正每方生形产1 吨甲产品，需耗用三种原料分别为1，1，0单位；生产1吨乙产品，需耗用三 种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知 道每生产1吨甲产品企业利润为300元，每生产1吨乙产品企业利润为400元。
原料
单位利润
产品
A
B
C
（百元）
甲
1
1
0
3
乙
1
2
1
4
供应量
6
8
3
第3页
假设该企业决策者决定不生产甲、乙产品，而是将厂
里的例现1有、资应源如外何售安。排决生策产者计应划怎，样使制一定天每的种总资源利的润收最费大？
标准才合理？
原料
单位利润
产品
A
B
C
（百元）
甲
1
1
0
3
乙
1
2
1
4
供应量
6
8
3
设 xj 表示第 j 种产品每天的产量
对偶问题： x1, x2 , x3, x3 0
min w b1y1 b2 y2 b2 y2 b3 y3 s.t. a11 y1 a21 y2 a21 y2 a31 y3 c1
a12 y1 a22 y2 a22 y2 a32 y3 c2 a13 y1 a23 y2 a23 y2 a33 y3 c3 a13 y1 a23 y2 a23 y2 a33 y3 c3 y1, y2 , y2, y3 0
max z = 3x1 + 4x2 s.t. x1 + x2 ≤ 6
x1 + 2x2 ≤ 8 x2 ≤ 3
x1 ≥ 0 , x2 ≥ 0
第4页
分析问题：
1、出让例每1、种资应源怎的样收制入定不收能费低标于准自才己合生理产时？的可获利润；
2、定价不能太高，要使对方能够接受。
原料
单位利润
产品
A
BC（百元） Nhomakorabea第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，x3 x3 x3 (x3 0, x3 0)
6

1 0
2 1


x1 x2



8 3


x1 x2


0
max z=CX s.t. AX ≤b
X≥0
D min w 6 y1 8y2 3y3
s.t. y1 y2 3

y1

2
y2

min w 6 y1 8y2 3y3
s.t. y1 y2 3

y1

2
y2

y3

4
y1, y2 , y3 0
原问题（对偶问题）
目标函数 max
目标函数的系数
约束条件右端常数
约
3个
束
≤
条
≥
件
=
23个
变
≥0
量
≤0
无符号限制
对偶问题（原问题）
目标函数 min
约束条件右端常数
3个
变
≥0
量
≤0
无符号限制
对偶问对题偶（问原题问题）
目标函数 min
约束条件右端常数
目标函数的系数