University of Waterloo CO 经典教材 Intro to Optimization

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

co250-web.pdf (1.36 MB, 需要: 8 个论坛币)

2011-8-11 06:56:57 上传

intro to optimizaiton
需要: 8 个论坛币  [购买]

By Department of Combinatorics and Optimization, University Of Waterloo

Contents
1 Introduction
1.1 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 A production planning example . . . . . . . . . . . . . . . . . . . . . 8
1.1.2 Multiperiod models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.1 MaximumWeight Matching . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Nonlinear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.1 Pricing a DVD Player . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.2 Portfolio Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Overview of the course . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Solving linear programs 25
2.1 Possible outcomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Infeasible linear programs . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Linear programs with optimal solutions . . . . . . . . . . . . . . . . . 29
2.1.3 Unbounded linear programs . . . . . . . . . . . . . . . . . . . . . . . 32
2.2 Standard equality form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 A Simplex iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Bases and canonical forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3
CONTENTS 4
2.4.1 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.2 Canonical forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 The Simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5.1 An example with an optimal solution . . . . . . . . . . . . . . . . . . 47
2.5.2 An unbounded example . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.3 Formalizing the procedure . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6 Finding feasible solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.6.1 Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6.2 The Two Phase method - an example . . . . . . . . . . . . . . . . . . 59
2.6.3 Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.7 Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.8 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 Computational complexity 67
3.1 Fast and slow algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2 Decision problems and certificates . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3 Hard problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.4 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4 Introduction to duality 77
4.1 A first example: Maximum weight matching . . . . . . . . . . . . . . . . . . . 78
4.2 Bounding the optimal value of a linear program . . . . . . . . . . . . . . . . . 79
4.3 The matching example revisited . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4 A second example: Network flow . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5 A third example: Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.6 Duals of general linear programs . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.7 The duality theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.7.1 Integer programs and the duality gap . . . . . . . . . . . . . . . . . . . 102
4.7.2 Linear programs and the duality theorem . . . . . . . . . . . . . . . . 103

CONTENTS 5
4.8 Complementary Slackness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.9 Complementary Slackness and combinatorial examples . . . . . . . . . . . . . 110
4.9.1 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.9.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.10 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5 Solving Integer Programs 117
5.1 Maximum weight matching algorithm . . . . . . . . . . . . . . . . . . . . . . 118
5.1.1 Hall’s condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.1.2 An optimality condition . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.1.3 The Hungarian matching algorithm . . . . . . . . . . . . . . . . . . . 121
5.2 Cutting planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.1 General scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.2 Valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.3 Cutting plane and simplex . . . . . . . . . . . . . . . . . . . . . . . . 129
5.3 Branch & Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3.1 A discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.4 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6 Geometry of optimization 139
6.1 Feasible solutions to linear programs and polyhedra . . . . . . . . . . . . . . . 139
6.2 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.3 Extreme points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4 Geometric interpretation of Simplex algorithm . . . . . . . . . . . . . . . . . . 147
6.5 Cutting planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.6 A geometric interpretation of optimality . . . . . . . . . . . . . . . . . . . . . 151
6.7 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7 Nonlinear optimization 155
7.1 Definition of Nonlinear Programming Problems . . . . . . . . . . . . . . . . . 155

CONTENTS 6
7.2 Convex optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.3 Lagrangian and a Karush-Kuhn-Tucker Theorem . . . . . . . . . . . . . . . . 163
7.4 KKT Theorem for the smooth (differentiable) case . . . . . . . . . . . . . . . 165
7.5 Further reading and notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168[attach]946119[/attach

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏2 回帖

关键词：Optimization University Universit waterloo Optim University planning example 经典

有没有waterloo的校友啊~~~~~

呼唤啊啊呼唤啊  

不错     那那那那那那那

wo jiang wu.

谢谢

唉还是木有啊

我是waterloo的

不错的参考教材，谢谢分享

谢谢