当前位置：文档之家 › 运筹学对偶理论l

运筹学对偶理论l

  • 格式：ppt
  • 大小：979.01 KB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

运筹学基础-对偶线性规划(2)

运筹学基础-对偶线性规划(2)

用单纯形法同时求解原问题和对偶问题
原问题是：
maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0
5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0
原问题的标准型是：maxZ=2x1 +x2+0x3+0x4 +0x5
b
15 24 5 0
x1 0 6 1 2
比 值
-
24/6=4
5/1=5
检验数j
对偶问题剩余变量 y4、y5
对偶问题变量 y1、y2 、y3
检验数行的－ (cj-zj)值是其对偶问题的一个基本解yi ；
原问题变量
0 2
原问题松驰变量
1 0 0 0 0 1/6 -1/6 -1/3 0 0 1 0
3
x3 x1
x2 1 检验数j= cj-zj
-1/4 -1/2
对偶问题剩余变量 y4、y5
对偶问题变量 y1、y2 、y3
此时得原问题最优解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2 则对偶问题最优解:Y*=(0,1/4,1/2,0,0)T，S*=17/2
又例：用单纯形法同时求解原问题和对偶问题
定理6（互补松弛定理）
在线性规划问题的最优解中，如果对应某一约束条件的 对偶变量值为非零，则该约束条件取严格等式；反之如果约 束条件取严格不等式，则其对应的对偶变量一定为零。
注：证明过程参见教材59页性质5证明
讨论:
互补松弛定理也称松紧定理，它描述了线性规划达到最

线性规划对偶问题__运筹学__胡运权__清华大学出版社

线性规划对偶问题__运筹学__胡运权__清华大学出版社

证毕。
2.3 主（强）对偶定理
定理 如果原问题和对偶问题都有可行解，则它们都有最 优解，且它们的最优解的目标函数值相等。
证：由弱对偶定理推论1可知，原问题和对偶问题的目标
函数有界，故一定存在最优解。又由 YA C， Y
0及w= Yb = CBB—1b=z知，当原问题为最优解时，
其对偶问题的解为可行解，且有w=z，由最优性知， 这时两者的解都为最优解 。
17
(4) 对于极小化问题的具有非负限制的变量(极大化问题的具 有非正限制的变量)，在其对偶问题中，相应的约束为“≤” 型不等式；对于极小化问题的具有非正限制的变量(极大化问 题的具有非负限制的变量)，在其对偶问题中，相应的约束为 “≥”型不等式；对于原问题中无正负限制的变量，在其对偶 问题中，相应的约束为等式。
s
s
证：将(P)、(D)的约束化为等式：AX IXs b,YA Ys I C, 因为X、Y是最优解，所以CX Yb,即 (YA Ys I ) X Y ( AX IX s ),而YX s ,Ys X 0, 故只有Y X s Ys X 0。 （自证）。
26
互补松弛定理的应用
约束条件数：m个
对偶变量数：m个
第 i 个 约 束 条 件 类 型 为 “ ≤ ”第i个变量≥0
第 i 个 约 束 条 件 类 型 为 “ ≥ ”第i个变量≤0
第i个约束条件类型为“=” 第i个变量是自由变量
决策变量数：n个 第j个变量≥0 第j个变量≤0 第j个变量是自由变量
约束条件数：n 第j个约束条件类型为“≥” 第j个约束条件类型为“≤” 第j个约束条件类型为“=”
6 互补松弛性
20
1 单纯形法的矩阵描述
max z CX AX b

运筹学第2章

运筹学第2章
China University of Mining and Technology
-43-
运 筹 学
线性规划的对偶理论
性质3 最优性定理：如果 X 0 是原问题的可行解， 0 是其对偶 Y 问题的可行解，并且:
CX 0 BY 0
即: z w
则 X 0是原问题的最优解，Y 0是其对偶问题的最优解。
T
分别是原问题和对偶问题的可行解。 且原问题的目标函数值为
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
Z CX 10
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
(DP)
-41China University of Mining and Technology
-44China University of Mining and Technology
运 筹 学
线性规划的对偶理论
性质4 强(主)对偶性：若原问题及其对偶问题均具有可行解， 则两者均具有最优解，且它们最优解的目标函数值相等。
还可推出另一结论：若一对对偶问题中的任意一个有最优解， 则另一个也有最优解，且目标函数最优值相等；若一个问题 无最优解，则另一问题也无最优解。 一对对偶问题的关系，有且仅有下列三种： 1. 都有最优解，且目标函数最优值相等； 2. 两个都无可行解； 3. 一个问题无界，则另一问题无可行解。
-1-
运 筹 学
学习要点： 1. 理解对偶理论，掌握描述一个线性规划问题 的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。

运筹学02对偶理论1线性规划的对偶模型,对偶性质

运筹学02对偶理论1线性规划的对偶模型,对偶性质

(x1, x2, x3)T 0
从而对偶问题为
4 min w Yb ( y1, y2 ) 1 4 y1 y2
4 1 －1
YA ( y1, y2 ) 1 －7
5
(4 y1 y2, y1 7 y2， y1 5y2 ) (5, 2, 3)
min Z 4 y1 y2
4 y1 y2 5
min
w
6 y1
8y2
10 y3
约束, 即
5yy1175yy22
y3 3 y3
4
3
yi 0, i 1,2,3
3.1 线性规划的对偶模型 Dual model of LP
线性规划问题的规范形式(Canonical Form 或叫对称形式) ： 定义：
目标函数求极大值时，所有约束条件为≤号，变量非负； 目标函数求极小值时，所有约束条件为≥号，变量非负。
【例3.2】写出下列线性规划的对偶问题
max Z (5, 2,3)(x1, x2, x3)T
max Z 5x1 2x2 3x3
4x1x1 7
x2 x2
x3 4 5x3 1
x1, x2, x3 0
【解】设Y=(y1，y2 )， 则有
4
1
1 7
1
5
x1 x2 x3
4 1
y1y1 7
y2 2 5 y2 3
y1 0, y2 0
3.1 线性规划的对偶模型 Dual model of LP
【例3.3】 写出下列线性规划的对偶问题
max Z 4x1 3x2
5x1 x2 6 7x1x1 35x2x2108 x1 0, x2 0
【解】该线性规划的对偶问题是求最 小值，有三个变量 且非负, 有两个“ ≥”

运筹(第二章对偶与灵敏度分析)(1)

运筹(第二章对偶与灵敏度分析)(1)

5x2 3x3 30
x1 0, x2无约束，x3 0
2023/2/22
17
解：将原问题模型变形, 令x1 x1
min z 7x1 4x2 3x3
4x1 2x2 6x3 24
3x1 6x2 4x3 15 5x2 3x3 30
y1 y2 y3
x1 0, x2无约束，x3 0
则对偶问题是
max w 24 y1 15y2 30 y3
4 y1 3y2
7
x1
2 y1 6 y2 5 y3 4
x2
6 y1 4 y2 3x3 3
x3
y1, y2 0, x3无约束
2023/2/22
18
小结：对偶问题与原问题的关系：
目标函数：MAX
原 约束条件：m个约束
对
问
y1 y2
ym
2023/2/22
12
类似于前面的资源定价问题，每一个约束条件对 应一个“ 对偶变量”，它就相当于给各资源的单 位定价。于是我们有如下的对偶规划：
min W b1 y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym c1 a12y1 a22y2 am2ymc2 a1n y1 a2n y2 amn ym cn y1, y2 ,, ym 0
分别是原问题和对偶问题的可行解，则恒有
n
m
c j x j bi yi
j 1
i 1
m
n
考虑利用 c j aij yi 及
aij x j bi
i 1
j 1
代入。
2、无界性 如果原问题（对偶问题）有无界解，则
其对偶问题(原问题）无可行解。
2023/2/22

运筹学02对偶理论1线性规划的对偶模型,对偶性质

运筹学02对偶理论1线性规划的对偶模型,对偶性质

min Z 4 y1 y2 4 y1 y2 5 y 7 y 2 1 2 y1 5 y2 3 y1 0, y2 0
3.1 线性规划的对偶模型 Dual model of LP
Chapter3 对偶理论 Dual Theory
【例3.3】 写出下列线性规划的对偶问题
3.1 线性规划的对偶模型 Dual model of LP
Chapter3 对偶理论 Dual Theory
价格不可能小于零，即有yi≥0(i=1, …,4), 从而企业的资源价格 模型为
min w 36 y1 40 y2 76 y3 3 y1 5 y2 9 y3 32 4 y1 4 y2 8 y3 30 y 0, i 1, ,3 i
(2)原问题的目标函数系数对应于对偶问题的右端项
(3)原问题的右端项对应于对偶问题的目标函数系数 (4)原问题的约束矩阵转置就是对偶问题系数矩阵
(5)原问题求最大，对偶问题是求最小
(6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥”
3.1 线性规划的对偶模型 Dual model of LP
y1 y 2 1 1 y1 y 2 2 2 y , y 0 1 2
有可行解，由结论(3)知必有无界解。
3.2 对偶性质 Dual property
Chapter3 对偶理论 Dual Theory
【性质3】最优准则定理: 设X*与Y*分别是(LP)与(DP) 的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当 C X*= Y*b . 【性质4】对偶性：若互为对偶的两个问题其中一个有 最优解，则另一个也有最优解，且最优值相同。 另一结论：若 (LP) 与 (DP) 都有可行解，则两者都有最优 解，若一个问题无最优解，则另一问题也无最优解。 【性质5】互补松弛定理: 设X*、Y*分别为 (LP) 与 (DP) 的可行解，XS和YS分别是它们的松弛变量的可行解，则 X*和Y*是最优解当且仅当

对偶理论(1)


a y a y a y a y 1 j 1 2 j 2 i ji m jm
9
m in by by 11 2 2 st .. a y a y 1 1 1 2 1 2 a a 1 2y 1 2 2y 2 a a 1 ny 1 2 ny 2 y 1 y 2
by mm a y y m 1 m m 1 a m 2y m a m ny m y m y m 1 y m
6
• 二、影子价格的特点
1、 它依赖于资源的利用方式。当企业生产任务、产品结构、
生产方式等变化，它也会随之变化，而不像市场价格相对稳定。 z 2、 y i 表示在资源得到最优利用的生产条件下， b bi i 每增加一单位目标函数z的增量。 3、 它是一种机会成本，对市场有调节作用。 在完全市场经济 条件下，当某资源的市场价格低于影子价格应买进。 当高于时， 应卖出。当然买进卖出会影响影子价格，直至影子价格与 市场 价格持平。（企业影子价格在不断调整）市场价格相对稳定。
11 22
； 其中
cx mmm n1j2 BB mm m /
m k
12

m
生产获利 出让获利
其中B为最优基， b i 为第 i 种资源的拥有量。
5
y
i
代表在本企业资源在现有生产方式和最优利用条件下
对单位第
i
种资源的估价，称为shadow price。
它不是市场价格，而是根据资源在（现有）生产中作出的贡献 而作的估价（在买方可能接受的双方制衡之下）。 （针对具体工厂、具体产品在现有资源和现有生产方案下。）
8
a a 1 1x 1 1 2x 2 a a 2 1x 1 2 2x 2 a a m 1x 1 m 2x 2 x 1 x 2

运筹学_第2章_对偶理论习题

第二章线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2≥23y1 + 2y2 ≥23y1 + 4y2≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1－y2 + 4 y3≥23y1+5y2 + 2y3≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。

试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为min w=20y1+ 20y2y1 + 2y2≥1 （1）2y1 + y2 ≥2 （2）2y1 +3y2≥3 （3）3y1 +2y2≥4 （4）y1、y2≥0将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。

又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以2x3*+3x4* = 203x3* +2x4* = 20解得x3* = x4* = 4。

故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划min z=4x1+2x2+6x32x1 +4x2 +8x3 ≥244x1 + x2 + 4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2 －8x3 + x4=－24－4x1－x2－4x3+x5 =－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。

对偶单纯形法(经典运筹学)


引进人工变量 x6，x7 max Z 2 x1 x 2 Mx6 Mx7 3x1 x 2 x3 x6 3 4 x 3 x x x 6 2 4 7 s.t 1 x1 2 x 2 x5 3 x1 , x 2 , x3 , x 4 , x5 0
3 6 最优解 X （ ，， 0， 0， 0 ） 5 5
最优值 Z 12
5
对偶单纯形法步骤：
1、找出一个初始对偶可行解。 即找出一个基B，
把原问题写成该基的典则形式时，目标函数的系数均≤0
2、判断： （1）若B-1b≥0，则得到最优解 （2）若B-1b≥0， 记B 1b b1 , b2 , , bm
m ax Z 2 x1 x 2 3 x1 x 2 x3 3 4 x 3x x 6 1 2 4 s.t 基 B的典则形式 x1 2 x 2 x5 3 x1 , x 2 , x3 , x 4 , x5 0
取基B P 3, P 4,P 5
解：问题化为标准型 max Z 2 x1 x 2 5 x1 x 2 x3 2 x 2 x3 x 4 5 s.t 6x xx 9 xx 2 2 6 x3 3 5 5 9 44 x1 , x 2 , x3，x 4，x5 0
1、确定出基变量： 设br =min{bi | bi <0} 则取br所在行的基变量 为出基变量 即取X4为出基变量 2、确定入基变量： 原则： 保持检验行系数≤0
i i0 设 min | a ri 0 a ri a ri 0
1 21 3
X1 检 -2/3 X3 -5/3 X2 4/3 X5 -5/3 X1 检 0 X3 0 X3 X4 0 -1/3 1 0 0

运筹学第2章 对偶理论01-对偶问题及影子价格、对偶单纯形法

第2章对偶理论及灵敏度分析主要内容对偶理论⏹线性规划对偶问题⏹对偶问题的基本性质⏹影子价格⏹对偶单纯形法灵敏度分析⏹灵敏度问题及其图解法⏹灵敏度分析⏹参数线性规划线性规划的对偶问题⏹对偶问题的提出⏹原问题与对偶问题的数学模型⏹原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B 调试工序利润（元）612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––1x 2x ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=052426155 2max 212121221x x x x x x x s.t.x x z ,设设备A ——元／时设备B ––––元／时调试工序––––元／时1y 2y 3y 收购付出的代价最小，且对方能接受。

出让代价应不低于用同等数量的资源自己生产的利润。

设备A 设备B 调试工序利润（元）0612521115时24时5时ⅠⅡD ⏹厂家能接受的条件：⏹收购方的意愿：32152415min yy y w ++=单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。

1252632132≥++≥+y y y y y52426155 2212121221⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=x x x x x x x s.t.x x z ,max ⎪⎩⎪⎨⎧≥≥++≥+++=0y 125265241532132132321y y y y y y y t s y y y w ,,.min 对偶问题原问题收购厂家一对对偶问题⎩⎨⎧≥≥=⇒⎩⎨⎧≥≤=00bY C YA s.t.Yb w X AX t s CX z min ..max ),(21c c C =⎪⎪⎫ ⎛=1x x X )(ij a A =()321,y ,y y Y =⎪⎪⎪⎫ ⎛=321b b b b 3个约束2个变量2个约束3个变量原问题对偶问题其它形式的对偶问题?特点：1.原问题的约束个数（不包含非负约束）等于对偶问题变量的个数；2.原问题的价值系数对应于对偶问题右端项；3.原问题右端项对应于对偶问题的价值系数；4.原问题约束矩阵转置就是对偶问题约束矩阵；5.原问题为求最大，对偶问题是求最小问题；6.原问题不等约束符号为“≤”，对偶问题不等式约束符号为“≥”;二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

§2 对偶 问题 的基 本性
质
性质1（弱对偶性）
若互为对偶的LP问题(1)、(2)分别有可行解：
X (x1 , x2 ,, xn )T Y ( y1, y2 ,, ym )
则其相应的目标函数值满足
Z c1x1 c2 x2 cn xn C X
b1 y1 b2 y2 bm ym Yb W
x1＋x2－3x3＋x4≥5
y1
2x1 ＋2x3－x4≤4
y2
x2＋x3＋x4＝6
y3
x1≤0，x2，x3≥0，x4无约束
1 A 2
≥ 0
x1
≤
1 3
02
≤1 1≤
x2 x3
≥
≥
1 ≥ 5 y1 ≥ 1≤ 4 y2 ≤ ＝1 ＝ 6 y3 无
无x4
max w＝5y1＋4y2＋6y3
上述关系可写为下表：
x1 x2
y1
a11 a12
y2
a21 a22
… ……
yn
am1 am2
对偶关系 ≥ ≥
max z c1 c2
max Z=2x1＋3x2 x1＋2x2≤8
4x1 ≤16 4x2≤12
x1，x2 ≥0
… xn 原关系 min w
… a1n
≤
b1
… a2n
≤
b2
……
≤
…
… amn
≤
bm
1
2
4 7

y1 y2



3 3


y1 y2


0
推论1 极大化问题的任意一个可行解所对
应的目标函数值是其对偶问题最优目标函
数值的一个下界。
几
个
推论2 极小化问题的任意一个可行解所对 应的目标函数值是其对偶问题最优目标函
推
数值的一个上界。
a11 a12
a1n
a21 a22
a2n
am1 y1 c1

am2
amn
y2 ym


c2 cn

对称 形式 的对 偶问 题
y1, y2 ,, ym 0
maxZ CX
对
对 偶 问
对偶理论就是研究线性规划及其对偶 问题的理论，是线性规划理论的重要 内容之一。
2.1 原问 题与 对偶 问题 的关
系
我们将前面的LP原问题与其对偶问题进行比较有： ⑴一个问题的约束条件个数等于另一问题中变量数；
⑵一问题目标函数系数是另一问题中约束条件的右端 项；
⑶一问题约束条件为“≤”，另一则为“≥”； ⑷一个为求极大，另一个为求极小。
x2 ＋ x3 ＋ x4' - x4" ≤ 6
y1
＋y3 ≤ 3
－x2 － x3 － x4'＋x4" ≤-6
－3y1＋2y2＋y3 ≤-5
x1'，x2，x3，x4'，x4" ≥0
y1 －y2 ＋y3 ＝ 1
直接写出其对偶问题，有
y1≥0，y2≤0，y3无约束
对 偶 问 题 的 定 义
min z＝2x1＋3x2－5x3＋x4

a22 x2


a2n xn

(, )b2
般 线 性
问 题 的 定 义
am1x1 am2 x2 amnxn (, )bm x j 0( 0,或符号不限 ) j 1 ~ n
规 划 问
min W b1 y1 b2 y2 bm ym
10
x3
11 14
题
x1 0, x2符号不限, x3 0
的
max W 7 y1 11y2 14 y3
写 出
4 y1 8y2 12y3 4
5y61
y1
9y2 10 y
13
2
y3

2 3
y1符号不限, y2 0, y3 0
min w=15y1＋24y2＋5y3 6y2＋y3 ≥2
5y1＋2y2＋y3≥1 y1，y2，y3≥0
例2 写出上例中对偶问题的对偶问题。
解：先将之化为目标极大、约束为≤的形式得：
max w'=－15y1－24y2－5y3 min z'=－2x1－x2
－6y2－ y3≤－2
－5x2≥－15
－5y1－2y2பைடு நூலகம்y3≤－1
AX b
s.t.
X

0
称 形 式
的
题
minW Yb
对
的 定 义
s.t.YYA0C
偶 问 题
对 偶 问 题 的 定 义
例3：写出下面LP问题的对偶问题。
min z＝2x1＋3x2－5x3＋x4
x1＋x2－3x3＋x4≥5
2x1 ＋2x3－x4≤4
x2＋x3＋x4＝6
①
x1≤0，x2，x3≥0，x4无约束
-y1
＋y3' – y3" ≥-3
x2 ＋ x3 ＋ x4' - x4" ≤ 6
3y1＋2y2'＋y3' – y3"≥5
x2 ＋ x3 ＋ x4' - x4" ≥ 6 ③
-y1 －y2' ＋y3' – y3"≥ 1
x1'，x2，x3，x4'，x4" ≥0
y1 ＋y2' －y3' ＋ y3"≥-1
②×(-1)，③×(-1)，得，
y1，y2，y3≥0
－－6xx11－－2xx22≥≥－－524
x1，x2 ≥0
结论：原问题与对偶问题互为对偶。
max Z c1x1 c2 x2 cn xn
对 偶 问
s.t.
a11 a21
am1
a12 a22
am2


a1n a2n
amn
y1，y2'，y3'，y3" ≥0
max z'＝2x1'－3x2＋5x3－x4'＋x4" 令w'＝-w, y2＝-y2', y3＝y3"–y3',得，
x1'－x2＋3x3－(x4' - x4")≤-5 max w＝5y1＋4y2＋6y3
-2x1' ＋2x3－(x4' - x4")≤4
y1 ＋2y2
≥2

a2n xn

b2
am1x1 am2 x2 amn xn bm
x1, x2 ,, xn 0
min W b1 y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym c1
a12y1

a22 y2
a11 y1 a21 y2 am1 ym (, )c1
a12y1

a22 y2

am2
ym

(, )c2
题 的 对 偶 问
a1n y1 a2n y2 amn ym (, )cn
题
y j 0(符号不限,或 0)i 1 ~ m
y1 ＋2y2
≥2
x1
y1
＋y3 ≤ 3
x2
－3y1＋2y2＋y3 ≤-5
x3
y1 －y2 ＋y3 ＝ 1
x4
y1≥0，y2≤0，y3无约束
max Z c1x1 c2 x2 cn xn
一
对 偶
a11x1 a12 x2 a1n xn (, )b1
a21x1
解：令 z'＝-z, x1＝-x1', x4＝ x4' - x4"，①拆为两式得，
max z'＝2x1'－3x2＋5x3－x4'＋x4" min w'＝-5y1＋4y2'＋6y3' –6y3"
－x1'＋x2－3x3＋x4' - x4"≥5 ②
y1－2y2'
≥2
-2x1' ＋2x3－(x4' - x4")≤4
义
第j个变量≤0
第j个约束类型为“≤”
第j个变量是自由变量 第j个约束类型为“＝”
对 偶 问 题 的 写 出
例4：写出下面问题的对偶问题
max Z c1x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21 x1
a22 x2
原材料B
0
单位产品利润（元） 2
2
8台时
0
16kg
4
12kg
3
若工厂的决策者不生产产品I、II，而是将之出租或出 售，则工厂的决策者就要考虑给每种资源如何定价的 问题。显然，出让这些资源的代价不应低于自己组织 生产活动时的利润。已知原模型为：
对 偶 问 题 的 提 出
max Z=2x1＋3x2 x1＋2x2≤8
对偶问题对应表
对
原问题（对偶问题） 对偶问题（原问题）
偶
目标函数maxZ
目标函数minZ
问
约束条件： m个
第i个约束类型为“≤”
变量数： m个
第i个变量≥0
题
第i个约束类型为“≥”
第i个变量≤0
第i个约束类型为“＝” 第i个变量是自由变量
的
定
变量数：n个