当前位置：文档之家 › 运筹学课件 06对偶理论和灵敏度分析

运筹学课件 06对偶理论和灵敏度分析

  • 格式：ppt
  • 大小：378.50 KB
  • 文档页数：26

下载文档原格式

  / 26

合集下载

运筹学对偶理论与灵敏分析PPT课件

运筹学对偶理论与灵敏分析PPT课件

2x1 x2 3x3 2x4 20
x1
4
0
试验证弱对偶性原理。
第25页/共86页
解：
m i nW 20y1 20y2
（D）
y1 2 y2 1
22
y1 y1
y2 3 y2
2 3
3 y1 2 y2 4
y1 0, y2 0
由观察可知：
__
X =（1.1.1.1），
Y__=（1.1），分别是
（1）若原问题是
MaxZ CX
(P)
s.t.
AX b X 0
(2) 其对偶问题为
MinW bY
(D)
YA C
s.t.
Y
0
这两个式子的变换关系称为“对称形式的对偶关系”。
第11页/共86页
怎样写出非对称形式的对偶问题？ 根据对应规律（参见对偶关系表）直接 写出；
第12页/共86页
原问题（或对偶问题） 对偶问题（或原问题）
第7页/共86页
如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。
原问题与对偶问题之间没有严格的 界限，它们互为对偶。
第8页/共86页
(P) 例1.1
MaxZ 2x1 3x2
x1 2x2 8
s.t.44
x1 x2
16 12
x1, x2 0
第37页/共86页
对偶性质定理总结：
定理2弱对偶定理： 判断原问题（对偶问题）目标函数值的上界 （下界）。
定理3、4、5： 判断原问题（对偶问题）解的两种对应关系。
判断原问题（对偶问题）有无最优解。
定理6互补松弛性定理： 根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。

对偶问题与灵敏度分析课件

对偶问题与灵敏度分析课件
第三章 对偶问题与 灵敏度分析
第一讲 对偶理论 第二讲 灵敏度分析
对偶问题与灵敏度分析
第一一讲、对偶对问偶题 理论
车间
产品 工时单耗
甲
乙
生产能力
A
1
0
8
B
0
2
12
C
3
4
36
单位产品获利 3
5
• 例1中该厂的产品销售，现有另一企业想租赁其设备。 厂方为了在谈判时心中有数，需掌握设备台时费用的 最低价码，以便衡量对方出价，对是否出租做出抉择。
• 对偶问题的最优解： y1=0，y2=1/2，y3=1 对应于原问题最优 单纯型法表中，初始基变量x3 , x4 , x5的检验数的负值。
对偶问题与灵敏度分析
对称形式下对偶问题的一般形式
对称形式：变量均为非负，其约束条件当目标函数求极
大时均取“≤”，当目标函数取极小时均取“≥”。
线性规划原问题（P）
S.t. 4x1 +x2 - x3 ≤10 x1 + x2 - x3 = 4 x1 ≥0, x2 ≤0, x3 无限制
Max W= 5y1+10y2+4y3
S.t.
y1+ 4y2+ 1y3 ≤ 5 -y1+ y2+ y3 ≥ 3
2y1 - y2 - y3 =-1
y1≥0, y2≤0, y3 无限制
对偶问题与灵敏度分析
• 问题 ①的最优解：x1=4，x2=6，Z*=42。
对偶问题与灵敏度分析
第一讲 对偶理论 第二个问题：出让定价
• 假设出让设备A、B、C所得利润分别为y1、y2、y3
• 原本用于生产甲产品的设备台时，如若出让，不应低于自行生 产带来的利润，否则宁愿自己生产。于是有对甲产品

对偶理论与灵敏度分析课件

对偶理论与灵敏度分析课件

航空航天领域
飞机和航天器的设计过程中需要 对气动性能、结构性能等进行灵
敏度分析，以优化设计方案。
机械工程领域
在机械设计中，需要对机构性能 、动力学特性等进行灵敏度分析 ，以提高机械设备的性能和稳定
性。
环境工程领域
在环境治理和生态保护方面，需 要对污染物扩散、水体自净等进 行灵敏度分析，以制定有效的环
详细描述
在机器学习中，我们通常会使用各种模型来预测未知数据。对偶理论和灵敏度分析可以 帮助我们理解这些模型的预测能力和泛化性能。例如，通过对偶理论，我们可以将一个 复杂的模型转化为一个更简单的模型，从而更容易理解和使用。同时，灵敏度分析可以
用来研究模型参数变化对预测结果的影响，从而更好地调整模型参数。
详细描述
在优化问题中，对偶理论可以将原问题转化为一个等价的优 化问题，有时这个新问题可能更容易求解。同时，灵敏度分 析可以用来研究原问题的参数变化对最优解的影响，从而更 好地理解问题的性质和最优解的稳定性。
金融问题中的对偶与灵敏度分析
总结词
在金融领域，对偶理论和灵敏度分析可 以用于风险评估、投资组合优化等问题 。
对偶理论的应用场景
资源分配问题
对偶理论可以应用于资源分配问 题，通过求解对偶问题来获得最
优解。
运输问题
对偶理论可以应用于运输问题，通 过求解对偶问题来获得最优解。
投资组合优化
对偶理论可以应用于投资组合优化 问题，通过求解对偶问题来获得最 优解。
02
灵敏度分析简介
灵敏度分析的定义
01
灵敏度分析是指对系统参数变化 引起系统性能变化的程度进行分 析，旨在了解系统对参数变化的 敏感程度。2
灵敏度分析算法的改进

运筹学：对偶理论与敏感性分析培训课件

运筹学：对偶理论与敏感性分析培训课件

4
max z 4.5x1 5x2 7 x3 2x1 2x2 4x3 800 4x1x1 22x2x233x3x3685500 2x1 4x2 2x3 700 x1, x2 , x3 0
5
若这家公司决定不生产这三种产品， 决定将设备进行出租，那么如何对各种资 源的租金进行定价？
5
x2
0
1
0 -1/14 0 -1/7 5/14 500/7
7
x3
0
0
1 -3/7 0 -1/7 -1/7 850/7
0
x5
0
0
0 -6/7 1 2/7 -3/14 400/7
j
0
0
0 19/14 0 3/14 13/28 11150/7
对偶规划
CB
YB
-800 y1
-850 j y3 -700 y4
x1 , x2 ≥ 0
对偶问 题为:
Max w = - y1 + 9y2 -5y1 + 3y2 ≤ 4 -7y1 + 2 y2 ≤6
y1 , y2 , ≥ 0
12
例 写出下列LP问题的对偶问题:
Max Z = 4 x1 + 6 x2 5 x1 + 7 x2 ≤ 1 3 x1 + 2 x2 ≤ 9 x1 ≥ 0 , x2取值无约束
xB
xN
xS
0 xS b
B
N
I
检验数行
cB
cN
0
经过若干次迭代
变成第一个 约束条件的 系数
反过来，由下 往上也是一样 的。
最小化问题：
系数变成约束 条件右侧值
min z x1 x2 x3
x1 x2 2x3 25

运筹学——对偶问题与灵敏度分析幻灯片PPT

运筹学——对偶问题与灵敏度分析幻灯片PPT
产品A 产品B 资源限制
劳动力
9
4
360
设备
4
5
200
原材料
3
10
300
单位利润 70
120
OR1
18
Cj
CB XB
0 X3 0 X4 0 X5
σj
0 X3 0 X4 120 X2
σj
70 X3 1200 X1
X2 σj
OR1
b
360 200 300 0
240 50 30 3600
84 20 24 4280
〔1〕根据LP问题，列出初始单纯形表。检查b列的数字， 假设都为非负，检验数都为非正，那么已得到最优解， 停顿计算。假设检查b列的数字时，至少还有一个负分 量，检验数保持非正，那么进展以下计算。
〔2〕确定换出变量：将B-1b中最小的负分量所对应的 变量确定为换出变量。
〔3〕确定换入变量：检查换出变量所在行〔第L行〕的
〔3〕在灵敏度分析中，有时需要用对偶单纯形 法，这样可使问题的处理简化。
OR1
29
2.2灵敏度分析〔考研时常考的知识点〕
灵敏度分析通常有两类问题：①是当C,A,b 中某一局部数据发生给定的变化时，讨论 最优解与最优值怎么变化；②是研究 C,A,b中数据在多大范围内波动时，使原 有最优基仍为最优基，同时讨论此时最优 解如何变动？
OR1
22
对偶单纯形法
设有问题maxZ=CX ，
AX ＝b ，
X ≥0
又设B是其一个基，当非基变量都为0时， 可以得到XB=B-1b。假设在B-1b中至少有 一个负分量，设第i个为负分量，并且在单 纯形表的检验数行中的检验数都为非正，
这种情况就可以用对偶单纯形法来进展求 解。

运筹学精品课件之 对偶问题和灵敏度分析

运筹学精品课件之 对偶问题和灵敏度分析
82 0 0 -10/3 0 -11/3 -2产品工艺结构改变) (1)、非基变量Xj工艺改变 只影响单纯形表Pj 列， σ j .
关键看σ j 0? 还是>0? . 用(三)类似方法解决。
(2)、基变量Xj工艺改变，复杂
例：产品A工艺改变，对甲、乙需求变为2，2。 利润为7，问最优方案如何？
0 X4 2 8 X2 10
80
1 0 0 1 -1/2 1 1 1 0 1/2 -5 0 -2 0 -7/2
这时最优方案发生了改变。
基变量Xj工艺改变
•也可能 B-1 b出现负数
•检验数与基变量均不满足最优解要求
例 p1’ = 1
3
C1’ = 7
p一1’ = B-1 p1’ = σ一1’= -4
(2)、 b1改变, b1=30 ，B-1 b= 2 -1
30 40 =
-1 1 20 -10
5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1
120 0 0 -2 -2 -3
5 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1
100 0 -2 -4 0 -5
问：如何安排产品产量，可获最大利润？
解 maxZ=5X1 +8X2 +6X3
X1+ X2 + X3+X4 = 12 X1+2X2+2X3 +X5 =20
X1 … X5 0
58 60 0
X1 X2 X3 X4 X5 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1
058 60 0
② C1改变 C1=10， σ 5 =2>0 ,换基

运筹学线性规划对偶理论与灵敏度分析ppt课件

2020/2/21
2020/2/21
一、单纯形法计算的矩阵描述
本节以对称形式的原始-对偶问题为讨论的基础， 除非特别需要，一般不再专门说明。
P. max z = CX AX≤b
D. min w = Yb YA≥C
X≥0
Y≥0
原问题通过加入松弛变量 Xs 可以化为标准形式：
max z = CX +0Xs st. AX + IXs = b
max z = x1－2 x4 + x5 － x6
x1 － x4 － x5 + x6 ≤ 2 x1－ x4 － x5 + x6 ≤ - 1 x1 + x4 + x5 － x6 ≤ 1 2x1+ x4 － x5 + x6 ≤- 2 x1 , x4 , x5 , x6 ≥0
（2）写出上述 对称形式线性规 划问题的对偶。
a12y1+ a22y2 + … + am2ym ≥ c2 ……
a1ny1+ a2ny2 + … + amnym ≥ cn y1 , y2 , …, ym ≥0
2020/2/21
原问题：
max z = C X AX ≤ b X ≥0
Y=(y1,y2,…,ym) 对偶问题： min w = Y b YA≥C Y≥0
max z =c1x1+ c2x2 +… + cnxn
a11x1+ a12x2 + … + a1nxn ≤ b1
st.
a21x1+ a22x2 + … + a2nxn ≤ b2 ……
am1x1+ am2x2 + … + amnxn ≤ bm

运筹学-对偶理论及灵敏度分析


1 − 2 ≥
1, 2 ≥ 0
max =
=
≥0
s.t.ቊ
原问题
原问题与对偶问题
综上所述，我们可以归纳
原问题与对偶问题
= 21 + 32
1 + 22 ≤ 8
41
≤ 16
s. t.
42 ≤ 12
1 , 2 ≥ 0
min = 81 + 162 + 123
恒有cx≤ yb
③最优性：x是原问题的可行解，y是对偶问题的可行
解，且有cx=yb，则x是原问题的最优解，y是对偶问题
的最优解
④强对偶性：若原问题及对偶问题均有可行解，
则两者均具有最优解，且最优解的目标函数值相同
⑤松紧定理：在线性规划问题的最优解中，对应
某一约束条件的对偶变量值为非零，则该约束条件取
40
X1
15
1
3/2
0
-1/2
1/2
0
0
X5
9
0
3/2
0
-3/2
1/2
1
50
x2
15/2
0
-1/4
1
3/4
-1/4
0
用x1‘替换x1
以x1‘作为换入变量，x1作为换出变量
灵敏度分析
增加一个约束条件的变化
计划生产如下所示：
产品
资源
产品A
产品B
资源总量
煤
1
2
30
劳动日
3
2
60
仓库
0
2
24
利润
40
50
产品A、B增加一道检验程序，A检测3小时/件，B检测2小时/件，

吉林大学本科运筹学课件对偶理论与灵敏度分析


线性规划的对偶模型
2. 原问题与对偶问题的对应关系
max z 2x1 3x2
2x1 2x2 12
s.t
4xx1 12
x2 16
8
4x2 12
x1 , x2 0
原问题-P
min 12 y1 8 y2 16 y3 12 y4
2 y1 y2 4 y3 0 y4 2
s.t 2 y1 2 y2 0 y3 4 y4 3
右段项 b≥0，原因在对偶
单纯型表中只保证 j而 不0
保证
B，故1b b可0 以是负
数。
线性规划的对偶模型
对偶问题： minW 2 y1 3 y2 5 y3
2 y1 3 y2 y3 2
3 y1 y2 4 y3 3
5 y1
7 y2
6 y3
4
y1 , y2 , y3 0
线性规划的对偶模型
3
x1
x2Leabharlann 7x33x1 4 x2 6 x3 5
x1 , x2 , x3 0
解：首先将原问题变形为对称形式
max Z 2x1 3 x2 4 x3
2 x 3 x2 5 x3 2
3
x1 x1
x2 4 x2
7x3 6x3
3 5
x1 , x2 , x3 0
注意：以后不强调等式
目标函数 min
m个
≥0
变
≤0
量
无约束
n个
约
≥
束
≤
条
=
件
目标函数变量的系数
约束条件右端项
线性规划的对偶模型
例2.2 写出下列线性规划问题的对偶问题.
max Z 2 x1 3 x2 4 x3

对偶理论与灵敏度分析.ppt



假设工厂考虑不进行生产而把 全部资源都转让，问如何定价 这些资源，既能使其获利不低 于安排生产所获得的收益，又 能使资源租让具有竞争力。
Min W =600y1+400y2+300y3+200y4 s.t. 3y1+2y2+ y3+ y4≥2000 4y1+ y2+3y3+2y4≥4000 2y1+2y2+3y3+4y4≥3000 y1, y2, y3, y4≥0
16
max z=CX; AX≤b; X≥0……(L) 推论2 min w=Yb; YA≥C; Y≥0……(D)
极大化问题（L）的任何一个可行解所对应的目标函 数值都是其对偶问题（D）目标函数值的下界。 Yb≥CX(0) 推论3 极小化问题（D）的任何一个可行解所对应的目标 函数值都是其对偶问题（L）目标函数值的上界。 CX ≤ Y(0)b
MinW 2u1 u2 2u3 u1 u2 2u3 1 u u u 2 1 2 3 ST : u1 u2 u3 1 u2无约束， u3 0 u1 0，
11
MinW 2u1 u2 2u3 u1 u2 2u3 u1 u2 u3 ST : u1 u2 u3 u1 0, u2无约束, u3 1 2 1 0

8
y1-y2+y3 -y4 ≤ 2
上述第一类对称形式LP问2 －y3－2y4 Max Z = x1－2x2’ +x3’ －x3’’ y 1 +y 2 － y 3 － 2 y 4 ≥ 1 x1 －x2’ －x3’+x3’’ ≤ 2 x +x ’+x ’ －x ’’ ≤ 1 －y1+y2 －y3 +y4 ≥-2 1 2 3 3 s.t. －y1+y2 －y3－y4 ≥ 1 s.t. x1 －x2’ －x3’+x3’’ ≤－1 y1 －y2+y3 +y4 ≥-1 －2x1+x2’ －x3’+x3’’ ≤－2 y1, y2, y3, y4 ≥0 x1, x2’, x3’, x3’’ ≥0 Min W =2u1+u2+2u3 令 u1= y1 u1+u2+2u3 ≥1 - y 1 +y 2 - y 3 - y 4 ≤ 1 则上述问 u2=y2－y3 s.t. u1 －u2+ u3 ≤2 u3=－y4 题变为： －u1+u2+ u3 =1 u1≥0, u3≤0 ,u2无约束
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1 第三张表： B 4 0
0 1 0
2 0 ， 4
1 0 B -1 4 1 0 0
1 - 2 2 1 4
1 3 c3 C B B 1 P3 0 2 0 3 4 2 0





是(D)的

Y 由于Y b C B B 1b C X ，根据性质 4 ， 的最优解。
是 (D)
6、 互补松弛定理
Y 分别为(P) 和(D) 的可行解，则它们为(P)和(D) 设X 、

的最优解的充分必要条件是：Y X S 0 和YS X 0 。其中， XS，YS 为(P)、(D)标准型问题中的松弛变量和剩余变量。 证：设(P)和(D)的标准型是： max z CX min Yb (P) AX X S b (D) YA YS C
例3 试求下述线性规划问题的对偶问题 min z 2 x1 3 x2 5 x3 x4
x1 x2 3 x3 x4 5 2 x1 2 x 3 x4 4 x 2 x 3 x4 6 x1 0 ; x2 , x3 0 ; x4无约束
解：设对偶变量为y1,y2,y3,对偶问题模型为：
1 0
0 1
C N CB B 1 N B 1 N
- CB B 1 B 1
- CB B -1b -1 B b
方程组中，非基变量为 0，基变量系数矩阵为单 位矩阵，故 XB=B-1b
z C B B 1 b P'j B 1 Pj
1 1 B B 可知，XS 的系数总对应 ；已知 ，就能求出
j c j C B B 1 Pj c j C B P'j
整个表。
如例1 的初始表和第三张表
cj CB 0 0 0 -z
CB 2 0 3 cj XB x1 x4 x2 -z
2 b 8 16 12 0
b 2 8 3 -13
3 x2 2 0 [4] 3
3 x2 0 0 1 0
0 x3 1 0 0 0
第二章 对偶理论和灵敏度分析
§ 1 单纯形法的矩阵描述
本节重点： 单纯形表各部分的数量关系
用矩阵描述单纯形法的每一次迭代、每一张单纯形 表， 能更深刻地理解单纯形法。 本节只考虑下列问题：
max z CX AX b s .t . X 0
标准型为：
max z CX AX X s b s .t . X， X s 0
此方程组的系数增广矩阵为：
1 0
0 1
C N CB B 1 N B 1 N
- CB B 1 B 1
- CB B -1b -1 B b -1
1 0
C CB B 1 A B 1 A
- CB B 1 B 1
- CB B -1b -1 B b
min y1b1 y2b2 y m bm a11 a12 a1n （D）( y1 , y2 , ym ) am1 am2 amn y1 , y2 , , ym 0 ( c , c , , c ) 1 2 n
(P)有 m 个约束 n 个变量，(D)有 m 个变量 n 个约束，(D) 的一个变量对应(P)的一个约束，反之亦然。 例如： max z 2 x1 3 x2 min 8 y1 16 y2 12 y3 x1 2 x2 8 y1 s .t . y1 4 y2 2 16 y2 (D) (P) 4 x1 2 y1 4 y3 3 4 x2 12 y3 y1 , y2 , y3 0 x1 , x2 0 系数： 8 1 16 4 12 0 2 2 0 4 3 转 翻 8 1 2 16 12 4 0 0 4
Z=CB（ B-1 b－ B-1 NXN－ B-1 XS）+CNXN+0XS = CB B-1 b+ （CN－CB B-1 N）XN－ CB B-1 XS
此方程组的系数增广矩阵为：
-Z
XB
XN
XS
右端
即方程组为：-Z+(C－CBB-1A)X－CBB-1XS=-CBB b B-1AX+B-1XS=B-1 b
注意： B 的列顺序 和 XB 的下标顺序 相同。
CBB-1 称为单 纯形乘子向量。
§ 2 改进单纯形法
单纯形法中，除换入变量外，非基变量系数列的迭 代运算是多余的。为了减少计算量和存储量，产生了改 进单纯形法。当 m<<n 时这种改进的效果明显。
§3 对偶问题的提出
第一章例1 某工厂，已知数据同前。若工厂决策者准备将所 有资源出租或转让，问应该如何定价？ 设出租单位设备台时的租金和出让单位原材料 A 、 B 的附 加费为y1、y2、y3。
Y 分别是(P)和(D)的最优解，由性 必要性：若 X ， 质 4 可知


C X Y b


于是
Y A X YS X Y A X Y X S






又由于

Y ，X S 0 ， Y S， X ，



所以必有 YS X 0 ，Y X S 0 意义：
Y X S 0 x si yi 0




(反之亦然)
5、 对偶定理 若(P)有最优解，则(D)也有最优解，且目标函数最 优值相等。 证：设 X 是(P)的最优解，它对应的基矩阵是 B， 这时必有
C C B B A 0 ， z C X C B B 1b
1


Y 设 Y C B B 1 ，则Y A C , Y 0 ，说明 可行解,
Y 0 X 0
2、 弱对偶性 Y ，有 对于 (P) 的任一可行解 X 和 (D) 的任一可行解 C X Yb 。 证： 由于Y A C ，X 0 有 Y AX C X A X b , Y 0 ，所以 Y b Y A X C X 。 又
3、 无界性 若(P)为无界解，则(D)无可行解。 证： (P) 为无界解意味着 C X 无界。若 (D) 有可行 解Y ，则由弱对偶性，C X Y b ，矛盾。 注意：(D)无可行解，(P)不一定为无界解。 此性质还说明： (P)有可行解，(D)不一定有 可行解。
Max w=5y1+4y2+6y3
y1 +2y2 y1 -3y1 +2y2 +y3 y1 - y2 +y3 ≥2 + y3 ≤3 ≤-5
=1 y1≥0, y2≤0, y3无约束
4．1 对偶问题的基本性质 1． 对称性 原问题和对偶问题的概念是相对的。可以是 min Yb max z CX YA C AX b (P) (D)
0 x3 1 -4 0 -2
0 x4 0 1 0 0
0 x4 0 0 x5 -1/2 [2] 1/4 1/4
XB x3 x4 x5
x1 1 4 0 2
2 x1 1 0 0 0
cj CB 0 0 0 -z XB x3 x4 x5 b 8 16 12 0
2 x1 1 4 0 2
3 x2 2 0 [4] 3
0 x3 1 0 0 0
0 x4 0 1 0 0
0 x5 0 0 1 0
CB 2 0 3
cj XB x1 x4 x2 -z
2 b 2 8 3 -13 x1 1 0 0 0
3 x2 0 0 1 0
0 x3 1 -4 0 -2
0 x4 0 1 0 0
0 x5 -1/2 [2] 1/4 1/4
1 0 1 B b 4 1 0 0 1 0 B 1 P2 4 1 0 0
1 - 2 8 2 2 16 8 1 12 3 4 1 - 2 2 0 2 0 0 1 4 1 4
Max Z= CBXB+CNXN+0XS (()) BXB+NXN+IXS=b XB,XN,XS≥0 (1) (2)
XB=B-1 b－ B-1 NXN－ B-1 XS,
代入（0）式，有
Z=CB（ B-1 b－ B-1 NXN－ B-1 XS）+CNXN+0XS = CB B-1 b+ （CN－CB B-1 N）XN－ CB B-1 XS
展开式如下：
Max z c1 x1 c2 x2 cn xn a11 （P） am1 x1 a12 a1n b1 x2 am2 amn bm x n x1 , x2 , , xn 0
i 1 m
xsi 和 yi 二者必有一为零( i =1 ,…,m)
7、(P)的单纯形表的检验数行对应(D)的一个基解，其对 应关系是
在满足收入不能低于利润的条件下，按照市场规则， 总收入只能尽可能小，模型为
min 8 y1 16 y2 12 y3 s .t . y1 4 y2 2 y1 y1 , y2 , y3 0
2 4 y3 3
此问题就是第一章例 1 的对偶问题。 从理论上也可引出对偶问题。对偶问题的提出在运筹学中有 重要的理论意义。
2 3
例2 证明 max z CX min Yb AX b 的对偶问题是 YA C X 0 Y无符号约束 证： Y' AX=b AX b — 对应 '' Y -AX -b — 对应 由定义，对偶问题的约束条件为： Y ' A Y '' A C
Y ' 0 ,Y '' 0 ' '' Y Y Y 令 ，得(P)的对偶问题为: min Yb YA C