运筹学第二章：线性规划的对偶理论与灵敏度分析
Charles007
August 27, 2020
1 线性规划的对偶问题
一个线性规划问题，如果它的目标是利用现有资源最大化利益，那么它的对偶问题就是如何在收购这些资源时花
最小的代价。这能够帮助理解：在一对对偶问题中，如果这对对偶问题都有可行解，那么最小化问题的任意可行
解对应的目标值大于等于最大化问题的任意可行解对应的目标值，当它们的目标函数值相等时，两个问题都取得
最优解。先看看对称形式下的对偶问题的一般形式。原问题：
max z = c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
s.t.
a
11
x
1
+ a
12
x
2
+ · · · + a
1n
x
n
≤ b
1
a
21
x
1
+ a
22
x
2
+ · · · + a
2n
x
n
≤ b
2
.
.
.
a
m1
x
1
+ a
m2
x
2
+ · · · + a
mn
x
n
≤ b
m
x
j
≥ 0 (j = 1, . . . , n)
对偶问题：
min ω = b
1
y
1
+ b
2
y
2
+ . . . + b
m
y
m
s.t.
a
11
y
1
+ a
21
y
2
+ · · · + a
m1
y
m
≥ c
1
a
12
y
1
+ a
22
y
2
+ · · · + a
m2
y
m
≥ c
2
.
.
.
a
1n
y
1
+ a
2n
y
2
+ · · · + a
mn
y
m
≥ c
n
y
i
≥ 0 (i = 1, . . . , m)
并非所有线性规划问题都具有对称形式，对于一般形式下的线性规划问题，先看一个示例。原问题：
max z = c
1
x
1
+ c
2
x
2
+ c
3
x
3
s.t.
a
11
x
1
+ a
12
x
2
+ a
13
x
3
≤ b
1
a
21
x
1
+ a
22
x
2
+ a
23
x
3
= b
2
a
31
x
1
+ a
32
x
2
+ a
33
x
3
≥ b
3
x
1
≥ 0, x
2
≤ 0, x
3
无约束
对偶问题：
min ω = b
1
y
1
+ b
2
y
2
+ b
3
y
3
s.t.
a
11
y
1
+ a
21
y
2
+ a
31
y
3
≥ c
1
a
12
y
1
+ a
22
y
2
+ a
32
y
3
≤ c
2
a
13
y
1
+ a
23
y
2
+ a
33
y
3
= c
3
y
1
≥ 0, y
2
无约束, y
3
≤ 0
实际上，对称形式的线性规划问题可以看做是一般线性规划问题的一种特殊情况，对于一般情况下的线性规划问
题，其原问题和对偶问题的对应关系总结如表 1所示。需要注意，原问题是最大化问题和是最小化问题时，求取
对偶问题的方法是有区别的。具体地说，如果原问题是求最大化问题，那么原问题的约束条件的符号和对偶问题
的变量的符号是相反的，原问题的变量符号和对偶问题的约束条件的符号是相同的；如果原问题是求最小化问
题，那么原问题的约束条件的符号和对偶问题的变量的符号是相同的，原问题的变量符号和对偶问题的约束条件
的符号是相反的。
1
剩余10页未读，继续阅读
KnowledgeIsMagic
- 粉丝: 2
- 资源: 15
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0