《Introduction to Linear Optimization》pdf电子书免费下载
下载方式一：
百度网盘下载地址：https://pan.baidu.com/s/15JIaUR5t1SzhcbmAqZdS5g
百度网盘密码：1111
下载方式二：
http://ziliaoshare.cn/Download/ab_123506_pd_IntroductiontoLinearOptimization.zip
|
|
作者：Dimitris Bertsimas John N. Tsitsiklis 页数：579 出版社：Massachusetts Institute of Technology |
《Introduction to Linear Optimization》介绍
这本书的目的是提供一个统一的，有见地的，线性优化，即线性规划，网络流问题，离散线性优化的现代处理。我们既讨论古典主题，也讨论艺术现状。我们特别关注理论，但也涵盖应用和目前的案例研究。我们的主要目标是帮助读者成为一个成熟的（线性）优化的实践者或研究者。更具体地说，我们希望发展的能力，制定相当复杂的优化问题，提供一个主要类的问题，实际上是可解的鉴赏，描述可用的解决方法，并建立一个理解的定性性质的解决方案。我们的一般哲学是，洞察力最重要。对于这本书的主题，这必然需要一个几何视图。另一方面，问题是通过算法来解决的，这些问题只能用代数来描述。因此，我们的重点是代数和几何之间美丽的相互作用。我们使用图形和几何参数建立理解，然后将想法转化为代数公式和算法。如果有足够的时间，我们希望读者能够不费吹灰之力地发展从一个领域到另一个领域的能力。我们的另一个目标是全面而经济。我们努力涵盖和突出这一领域的所有主要思想。然而，我们并没有试图成为百科全书式的，或者讨论与特定算法相关的每一个可能的细节。我们的前提是，一旦对基本原则有了成熟的理解，读者就可以不费吹灰之力地获得更多的细节。我们的最后一个目标是让读者了解最新的艺术水平。这在我们处理内点方法、大规模优化以及扩展现有算法和计算机限制的案例研究中尤其如此。任何优化方法的成功都取决于它处理大型重要问题的能力。从这个意义上说，最后一章，关于线性优化的艺术，是这本书的关键部分。我们希望，这将使读者相信，在挑战性问题上取得进展既需要针对具体问题的洞察力，也需要对基础理论有更深入的理解。西席序在任何一本关于线性规划的书中，对于单纯形法的处理有一些重要的选择。传统上，单纯形法是根据完整的单纯形表来发展的，这往往成为中心话题。我们发现全单纯形表是计算数值例子的有用工具。但除此之外，我们努力不过分强调其重要性。我们还要提到与许多其他教科书不同的另一点。介绍性的处理通常集中在标准形式的问题上，这对于单纯形法来说是足够的。另一方面，这种方法常常让读者怀疑某些属性是否普遍正确，并且会阻碍对主题的深入理解。我们从这个传统出发：我们考虑线性规划问题的一般形式，并在此背景下定义关键概念（例如，极值点）(当然，当涉及到算法时，我们通常必须专门研究标准形式。）本着同样的精神，我们把线性规划的结构理解从单纯形法的细节中分离出来。例如，我们包括对偶理论的推导，它不依赖于单纯形法。最后，这本书包含了几个不常涉及的重要主题的处理。其中包括对柱几何的讨论及其对单纯形法效率的洞察，对偶性与金融资产定价之间的联系，延迟柱生成和切割平面法的统一观点，随机规划和Benders分解，针对指派问题的拍卖算法、椭球算法的一定理论含义、内点法的深入处理，以及一整章的线性优化实践。练习中还包括几个值得注意的主题，如Leontief系统、严格互补、期权定价、von Neumann算法、子模函数极小化和一些整数规划问题的界。这是对这本书的逐章描述。第一章：介绍了线性规划问题，并给出了一些例子，提供了一些关于线性代数的背景资料。第二章：讨论了多面体的基本几何性质，重点讨论了极值点的定义和存在性，以及emph
《Introduction to Linear Optimization》目录
目录
前言。席
1.简介。
1 . 1 . 线性规划问题的变体。
1.2. 线性规划问题举例
1 .3. 分段线性凸目标函数
1.4. 图形表示与求解
1 .5. 线性代数背景与符号
1.6. 算法和运算计数
1 . 7.练习。
1.8. 历史、笔记和来源
2 . 线性规划的几何
2.1. 多面体和凸集。
2.2. 极值点、顶点和基本可行解
2.3. 标准形多面体
2.4. 简并度。
2.5. 极值点的存在。
2.6. 极值点的最优性
2.7. 有界多面体的表示*
2.8. 多面体的投影：Fourier-Motzkin消元法*
2.9. 摘要。
2.10练习。
2 . 1 1 . 注释和来源
三。单纯形法
3.1. 最优性条件。
3.2. 单纯形法的发展。
3.3. 单纯形法的实现
3.4.反循环：辞典学与布兰德法则
3.5.寻找初始基本可行解
3.6.柱几何学与单纯形法
3.7.单纯形法的计算效率
3.8.摘要。
3.9.练习。
3.10注释和来源
4. 对偶理论。
4.1.动机。
4.2.双重问题。
4.3.对偶定理。
4.4.作为边际成本的最优对偶变量
4.5.标准形问题与对偶单纯形法
4.6.法卡斯引理和线性不等式。
4.7.从分离超平面到对偶*
4.8.锥体和极端射线。
4.9.多面体的表示。
4.10一般线性规划对偶*
4.11摘要。
4.12练习。
4.13注释和来源
5. 敏感性分析
5.1. 局部敏感性分析。
5.2. 右侧向量的全局依赖性
5.3. 所有对偶最优解的集合*。
5.4. 全球对成本向量的依赖
5.5. 参数编程
5.6. 摘要。
5.7. 练习。
5.8. 注释和来源
6.大规模优化
6.1. 延迟列生成
6.2. 下料问题
6.3. 切割平面方法。
6.4. Dantzig-Wolfe分解
6.5. 随机规划与Benders分解
6.6. 摘要。
6.7. 练习。
6.8. 注释和来源
7.网络流问题
7.1. 图表。
7.2. 网络流问题的表述
7.3. 网络单纯形算法。
7.4. 负成本周期算法
7.5. 最大流量问题。
7.6. 网络流问题的对偶性
7.7. 双上升法*。
7.8. 分配问题与拍卖算法
7.9. 最短路径问题。
7.10 最小生成树问题。
7.11 摘要。
7.12. 练习。
7.13. 注释和来源
8. 线性规划的复杂性与椭球
8.1. 方法。
8.2. 高效的算法和计算复杂性。
8.3. 椭球法背后的关键几何结果
8.4. 可行性问题的椭球方法
8.5. 椭球优化法。
8.6. 指数多约束问题*
8.7. 摘要。
8.8. 练习。
9 注释和来源
9.1. 内点法
9.2. 仿射尺度算法
9.3. 仿射标度的收敛性*
9.4. 势约化算法
9.5. 原始路径跟踪算法
9.6. 原-对偶路径跟踪算法
9.7. 概述
9.8. 练习。
10 注释和来源
101 . 整数规划公式
10.2. 建模技术。
10.3. 强力配方指南。
10.4. 具有指数多约束的建模。
10.5. 摘要
10.6. 注释和来源477
1 1. 整数规划方法479
1 1 . 1 . 剖切面法480
11.2. 分支和绑定485
11.3. 动态规划490
11.4. 整数规划对偶494
1 1 .5. 近似算法507
1 1 .6. 本地搜索511
1 1.7. 模拟退火512
1 1 .8. 复杂性理论514
11.9. 总结522
1 1 . 10练习523
1 1 . 1 1 . 注释和来源530
1 2. 线性优化的艺术。533
121 . 线性优化的建模语言。534
12.2. 线性优化库和一般观测535
12.3. 机队分配问题537
12.4. 空中交通流量管理问题544
12.5. job-shop调度问题551
12.6. 摘要562
12.7. 练习563
12.8. 注释和来源567
参考文献569
索引579
Contents
Preface . . . . . . . . . . . . . . . . . . . . . xi
1. Introduction . . . . . . . . . . . .
1 . 1 . Variants o f the linear programming problem .
1.2. Examples o f linear programming problems
1 .3. Piecewise linear convex objective functions
1.4. Graphical representation and solution
1 .5. Linear algebra background and notation
1.6. Algorithms and operation counts
1 . 7. Exercises . . . . . . . .
1.8. History, notes, and sources
2 . The geometry o f linear programming
2.1. Polyhedra and convex sets . . . . . . . . . . .
2.2. Extreme points, vertices , and basic feasible solutions
2.3. Polyhedra i n standard form
2.4. Degeneracy . . . . . . . .
2.5. Existence of extreme points .
2.6. Optimality o f extreme points
2.7. Representation of bounded polyhedra*
2.8. Projections o f polyhedra: Fourier-Motzkin elimination*
2.9. Summary . . . .
2. 10. Exercises . . . .
2 . 1 1 . Notes and sources
3 . The simplex method
3.1. Optimality conditions . . . . . . .
3.2. Development o f the simplex method . .
3.3. Implementations o f the simplex method
3.4.
3.5.
3.6.
3.7.
3.8.
3.9.
3. 10.
4.
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
4. 10.
4.11.
4.12.
4. 13.
5.
Anticycling: lexicography and Bland's rule
Finding an initial basic feasible solution
Column geometry and the simplex method
Computational efficiency of the simplex method
Summary . . . .
Exercises . . . .
Notes and sources
Duality theory . .
Motivation . . . .
The dual problem . .
The duality theorem .
Optimal dual variables as marginal costs
Standard form problems and the dual simplex method
Farkas ' lemma and linear inequalities . .
From separating hyperplanes to duality*
Cones and extreme rays . . . . .
Representation of polyhedra . . . .
General linear programming duality*
Summary . . . .
Exercises . . . .
Notes and sources
Sensitivity analysis
5.1. Local sensitivity analysis . . . . . . . . . .
5.2. Global dependence o n the right-hand side vector
5.3. The set o f all dual optimal solutions* .
5.4. Global dependence on the cost vector
5.5. Parametric programming
5.6. Summary . . . .
5.7. Exercises . . . .
5.8. Notes and sources
6. Large scale optimization
6.1. Delayed column generation
6.2. The cutting stock problem
6.3. Cutting plane methods . .
6.4. Dantzig-Wolfe decomposition
6.5. Stochastic programming and Benders decomposition
6.6. Summary . . . .
6.7. Exercises . . . .
6.8. Notes and sources
7.
7. 1.
7.2.
7.3.
7.4.
7.5.
7.6.
7.7.
7.8.
7.9.
7. 10.
7. 11.
7.12.
7.13.
8.
8.1.
8.2.
8.3.
8.4.
8.5.
8.6.
8.7.
8.8.
9.
9.1.
9.2.
9.3.
9.4.
9.5.
9.6.
9.7.
9.8.
10.
10. 1 .
10.2.
10.3.
10.4.
10.5.
Network flow problems
Graphs . . . . . . . . . . . . . . .
Formulation of the network flow problem
The network simplex algorithm .
The negative cost cycle algorithm
The maximum flow problem . . .
Duality in network flow problems
Dual ascent methods* . . . . .
The assignment problem and the auction algorithm
The shortest path problem . . . . .
The minimum spanning tree problem .
Summary . . . .
Exercises . . . .
Notes and sources
Complexity of linear programming and the ellipsoid
method . . . . . . . . . . . . . . . . . . .
Efficient algorithms and computational complexity . .
The key geometric result behind the ellipsoid method
The ellipsoid method for the feasibility problem
The ellipsoid method for optimization . . . .
Problems with exponentially many constraints*
Summary . . . .
Exercises . . . .
Notes and sources
Interior point methods
The affine scaling algorithm
Convergence of affine scaling*
The potential reduction algorithm
The primal path following algorithm
The primal-dual path following algorithm
An overview
Exercises . . . .
Notes and sources
Integer programming formulations
Modeling techniques . . . . . . . . .
Guidelines for strong formulations . . .
Modeling with exponentially many constraints .
Summary
x Contents
10.6. Notes and sources 477
1 1. Integer programming methods 479
1 1 . 1 . Cutting plane methods 480
11.2. Branch and bound 485
11.3. Dynamic programming 490
11.4. Integer programming duality 494
1 1 .5. Approximation algorithms 507
1 1 .6. Local search 511
1 1.7. Simulated annealing 512
1 1 .8. Complexity theory 514
11.9. Summary 522
1 1 . 10. Exercises 523
1 1 . 1 1 . Notes and sources 530
1 2. The art in linear optimization . . . . 533
12. 1 . Modeling languages for linear optimization . 534
12.2. Linear optimization libraries and general observations 535
12.3. The fleet assignment problem 537
12.4. The air traffic flow management problem 544
12.5. The job shop scheduling problem 551
12.6. Summary 562
12.7. Exercises 563
12.8. Notes and sources 567
References 569
Index 579