没有合适的资源?快使用搜索试试~ 我知道了~
LinearProgrammingII.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 89 浏览量
2021-11-28
00:03:06
上传
评论
收藏 1002KB PDF 举报
温馨提示
试读
31页
算法设计
资源推荐
资源详情
资源评论
Lecture slides by Kevin Wayne
Last updated on 7/25/17 11:09 AM
LINEAR PROGRAMMING II
‣
LP duality
‣
strong duality theorem
‣
bonus proof of LP duality
‣
applications
LINEAR PROGRAMMING II
‣
LP duality
‣
Strong duality theorem
‣
Bonus proof of LP duality
‣
Applications
LP duality
Primal problem.
Goal. Find a lower bound on optimal value.
Easy. Any feasible solution provides one.
Ex 1. (A, B) = (34, 0) ⇒ z* ≥ 442
Ex 2. (A, B) = (0, 32) ⇒ z* ≥ 736
Ex 3. (A, B) = (7.5, 29.5) ⇒ z* ≥ 776
Ex 4. (A, B) = (12, 28) ⇒ z* ≥ 800
3
€
(P) max 13A + 23B
s. t. 5A + 15B ≤ 480
4 A + 4B ≤ 160
35A + 20B ≤ 1190
A , B ≥ 0
LP duality
Primal problem.
Goal. Find an upper bound on optimal value.
Ex 1. Multiply 2
nd
inequality by 6: 24 A + 24 B ≤ 960.
!
⇒ z* = 13 A + 23 B ≤ 24 A + 24 B ≤ 960.
4
objective function
€
(P) max 13A + 23B
s. t. 5A + 15B ≤ 480
4 A + 4B ≤ 160
35A + 20B ≤ 1190
A , B ≥ 0
LP duality
Primal problem.
Goal. Find an upper bound on optimal value.
Ex 2. Add 2 times 1
st
inequality to 2
nd
inequality: ≤
⇒ z* = 13 A + 23 B ≤ 14 A + 34 B ≤ 1120.
5
€
(P) max 13A + 23B
s. t. 5A + 15B ≤ 480
4 A + 4B ≤ 160
35A + 20B ≤ 1190
A , B ≥ 0
剩余30页未读,继续阅读
资源评论
码上富贵
- 粉丝: 1w+
- 资源: 177
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功