本书是一本适应当今运筹学发展趋势的优秀的综合性入门教材，主要特点是重视建模和算法的结合，引入了相关的建模工具以及用其进行模型开发的基本技巧。全书采用统一的理论框架，以简单的“改进搜索”思路贯穿始终，全面且循序渐进地演绎了各种优化算法和方法，包括传统的单纯形法、牛顿法、网络流算法以及各种启发式算法，使读者感受到每次引入的新算法都建立在以往算法的基础上，直观且逻辑性强，易于理解。本书收录了丰富的实际案例，并有大量上机习题，便于理论结合实践。

本书是一本适应当今运筹学发展趋势的优秀的综合性入门教材，主要特点是重视建模和算法的结合，引入了相关的建模工具以及用其进行模型开发的基本技巧。全书共分14章，前3章介绍数学模型的问题求解和改进搜索的基本概念与原理，其余内容则覆盖了确定型优化领域的几乎全部内容，除了传统的线性规划的模型、算法、对偶理论和灵敏度分析等内容以外，还包括了网络流、整数／组合优化、非线性规划和目标规划等领域的基本模型和主要算法。此外，本书还包含了遗传算法、模拟退火、禁忌搜索和分支切割算法等前沿内容。全书采用统一的理论框架，以简单的“改进搜索”思路贯穿始终，全面且循序渐进地演绎了各种优化算法和方法，包括传统的单纯形法、牛顿法、网络流算法以及各种启发式算法，使读者感受到每次引入的新算法都建立在以往算法的基础上，直观且逻辑性强，易于理解。本书收录了丰富的实际案例，并有大量上机习题，便于理论结合实践。

本书适用于工程和数学专业本科生或研究生的运筹学引论课程，也可以作为管理专业本科生或研究生的选修课教材，以及诸如线性规划、整数规划和组合优化、网络流和非线性规划等子领域的入门课程的教材。

CHAPTER 1 PROBLEM SOLVING WITH MATHEMATICAL MODELS

　1.1 OR Application Stories

　1.2 Optimization and the Operations Research Process

　1.3 System Boundaries, Sensitivity Analysis, Tractability and Validity

　1.4 Descriptive Models and Simulation

　1.5 Numerical Search and Exact versus Heuristic Solutions

　1.6 Deterministic versus Stochastic Models

　1.7 Perspectives

　Exercises

CHAPTER 2 DETERMINISTIC OPTIMIZATION MODELS IN OPERATIONS RESEARCH

　2.1 Decision Variables, Constraints, and Objective Functions

　2.2 Graphic Solution and Optimization Outcomes

　2.3 Large-Scale Optimization Models and Indexing

　2.4 Linear and Nonlinear Programs

　2.5 Discrete or Integer Programs

　2.6 Multiobjective Optimization Models

　2.7 Classification Summary

　Exercises

CHAPTER 3 IMPROVING SEARCH

　3.1 Improving Search, Local and Global Optima

　3.2 Search with Improving and Feasible Directions

　3.3 Algebraic Conditions for Improving and Feasible Directions

　3.4 Unimodel and Convex Model Forms Tractable for Improving Search

　3.5 Searching and Starting Feasible Solutions

　Exercises

CHAPTER 4 LINEAR PROGRAMMING MODELS

　4.1 Allocation Models

　4.2 Blending Models

　4.3 Operations Planning Models

　4.4 Shift Scheduling and Staff Planning Models

　4.5 Time-Phased Models

　4.6 Models with Linearizable Nonlinear Objectives

　Exercises

CHAPTER 5 SIMPLEX SEARCH FOR LINEAR PROGRAMMING

　5.1 LP Optimal Solutions and Standard Form

　5.2 Extreme-Point Search and Basic Solutions

　5.3 The Simplex Algorithm

　5.4 Dictionary and Tableau Representations of Simplex

　5.5 Two Phase Simplex

　5.6 Degeneracy and Zero-Length Simplex Steps

　5.7 Convergence and Cycling with Simplex

　5.8 Doing It Efficiently: Revised Simplex

　5.9 Simplex with Simple Upper and Lower Bounds

　Exercises

CHAPTER 6 INTERIOR POINT METHODS FOR LINEAR PROGRAMMING

 6.1 Searching through the Interior

 6.2 Scaling with the Current Solution

 6.3 Affine Scaling Search

 6.4 Log Barrier Methods for Interior Point Search

 6.5 Dual and Primal-Dual Extensions

 Exercises

CHAPTER 7 DUALITY AND SENSITIVITY IN LINEAR PROGRAMMING

 7.1 Generic Activities versus Resources Perspective

 7.2 Qualitative Sensitivity to Changes in Model Coefficients

 7.3 Quantifying Sensitivity to Changes in LP Model Coefficients: A Dual Model

 7.4 Formulating Linear Programming Duals

 7.5 Primal-to-Dual Relationships

 7.6 Computer Outputs and What If Changes of Single Parameters

 7.7 Bigger Model Changes, Reoptimization, and Parametric Programming

 Exercises

CHAPTER 8 MULTIOBYECTIVE OPTIMIZATION AND GOAL PROGRAMMING

 8.1 Multiobjective Optimization Models

 8.2 Efficient Points and the Efficient Frontier

 8.3 Preemptive Optimization and Weighted Sums of Objectives

 8.4 Goal Programming

 Exercises

CHAPTER 9 SHORTEST PATHS AND DISCRETE DrNAMIC PROGRAMMING 409

 9.1 Shortest Path Models

 9.2 Dynamic Programming Approach to Shortest Paths

 9.3 Shortest Paths From One Node to All Others:Bellman-Ford

 9.4 Shortest Paths From All Nodes to All Others:Floyd-Warshall

 9.5 Shortest Path From One Node to All Others With Costs Nonnegative:Dijkstra

 9.6 Shortest Paths From One Node to All Others in Acyclic Digraphs

 9.7 CPM Project Scheduling and Longest Paths

 9.8 Discrete Dynamic Programming Models

 Exercises

CHAPTER 10 NETWORK FLOWS

 10.1 Graphs, Networks, and Flows

 10.2 Cycle Directions for Network Flow Search

 10.3 Rudimentary Cycle Direction Search Algorithms for Network Flows

 10.4 Integrality of Optimal Network Flows

 10.5 Transportation and Assignment Models

 10.6 Other Single-Commodity Network Flow Models

 10.7 Network Simplex Algorithm for Optimal Flows

 10.8 Cycle Canceling Algorithms for Optimal Flows

 10.9 Multicommodity and Gain/Loss Flows

 Exercises

CHAPTER 11 DISCRETE OPTIMIZATION MODELS 555

 11.1 Lumpy Linear Programs and Fixed Charges

 11.2 Knapsack and Capital Budgeting Models

 11.3 Set Packing, Covering, and Partitioning Models

 11.4 Assignment and Matching Models

 11.5 Traveling Salesman and Routing Models

 11.6 Facility Location and Network Design Models

 11.7 Processor Scheduling and Sequencing Models

 Exercises

CHAPTER 12 DISCRETE OPTIMIZATION METHODS

 12.1 Solving by Total Enumeration

 12.2 Relaxations of Discrete Optimization Models and Their Uses

 12.3 Stronger LP relaxations, Valid Inequalities,and Lagrangian Relaxations

 12.4 Branch and Bound Search

 12.5 Rounding, Parent Bounds, Enumerations Sequences, and Stopping Early in Branch and Bound

 12.6 Improving Search Heuristics for Discrete Optimization INLPs 680

 12.7 Tabu, Simulated Annealing, and Genetic Algorithm Extensions

of Improving Search

 12.8 Constructive Heuristics

 Exercises 705

CHAPTER 13 UNCONSTRAINED NONLINEAR PROGRAMMING

 13.1 Unconstrained Nonlinear Programming Models

 13.2 One-DimensionalSearch 726

 13.3 Derivatives, Taylor Series, and Conditions for Local Optima

 13.4 Convex/Concave Functions and Global Optimality 749

 13.5 Gradient Search

 13.6 Newton's Method

 13.7 Quasi-Newton Methods and BFGS Search

 13.8 Optimization without Derivatives and Nelder-Mead 774

 Exercises 781

CHAPTER 14 CONSTRAINED NONLINEAR PROGRAMMING

 14.1 Constrained Nonlinear Programming Models

 14.2 Convex, Separable, Quadratic and Posynomial Geometric

  Programming Special NLP Forms

 14.3 Lagrange Multiplier Methods

 14.4 Karush-Kuhn-Tucker Optimality Conditions

 14.5 Penalty and Barrier Methods

 14.6 Reduced Gradient Algorithms

 14.7 Quadratic Programming Methods

 14.8 Separable Programming Methods

 14.9 Posynomial Geometric Programming Methods

 Exercises

SELECTED ANSWERS

INDEX