Operations research applications and algorithms

目录
第1章 建模理论概述
1.1 模型化概述
1.1.1 说明性模型或最优化模型
1.1.2 目标函数
1.1.3 决策变量
1.1.4 约束条件
1.1.5 完整的最优化模型
1.1.6 静态和动态模型
1.1.7 线性和非线性模型
1.1.8 整数和非整数模型
1.1.9 确定性和随机性模型
1.2 7步骤建模过程
1.3 CITGO石油公司
1.3.1 最优化炼油厂的经营
1.3.2 SDM系统
1.4 旧金山警察局调度方法
1.5 GE Capital公司
参考文献
第2章 线性代数基础知识
2.1 矩阵和向量
2.1.1 矩阵
2.1.2 向量
2.1.3 两个向量的标量积
2.1.4 矩阵运算
2.1.5 矩阵乘法的性质
2.1.6 利用Excel的矩阵乘法
2.2 线性方程的矩阵和线性方程组
2.3 解线性方程组的高斯-约当方法
2.3.1 基本行运算
2.3.2 利用高斯-约当方法求解
2.3.3 特殊情况：无解或者有无穷多组解
2.3.4 高斯-约当方法小结
2.3.5 线性方程组的基变量和基本解
2.4 线性相关和线性无关
2.4.1 矩阵的秩
2.4.2 如何判别向量组是否线性无关
2.5 逆矩阵
2.5.1 没有逆矩阵的矩阵
2.5.2 利用高斯-约当方法求m×m矩阵A的逆矩阵
2.5.3 利用逆矩阵解线性方程组
2.5.4 利用Excel求逆矩阵
2.6 行列式
2.7 小结
2.7.1 矩阵
2.7.2 矩阵和线性方程
2.7.3 高斯-约当方法
2.7.4 线性无关、线性相关和矩阵的秩
2.7.5 逆矩阵
2.7.6 行列式
2.8 复习题
参考文献
第3章 线性规划
3.1 什么是线性规划问题
3.1.1 比例性假定和相加性假定
3.1.2 可除性假定
3.1.3 确定性假定
3.1.4 可行域和最优解
3.2 两变量线性规划问题的图解法
3.2.1 求可行解
3.2.2 求最优解
3.2.3 绑定和非绑定约束条件
3.2.4 凸集、极点和LP
3.2.5 最小化问题的图解法
3.3 特殊情况
3.3.1 可选或多个最优解
3.3.2 不可行LP
3.3.3 无界LP
3.4 饮食问题
3.5 工作调度问题
3.5.1 制定公平的员工调度方案
3.5.2 建模问题
3.5.3 现实应用
3.6 资本预算问题
3.6.1 利用Excel计算NPV
3.6.2 XNPV函数
3.7 短期财务计划
3.8 混合问题
3.8.1 建模问题
3.8.2 现实应用
3.9 生产过程模型
3.10 使用线性规划求解多阶段问题：库存模型
3.11 多阶段财务模型
3.12 多阶段工作调度
3.13 小结
3.13.1 线性规划的定义
3.13.2 线性规划问题的图解法
3.13.3 LP的解：4种情况
3.13.4 表述LP
3.14 复习题
参考文献
第4章 单纯形算法和目标规划
4.1 如何将LP转换成标准形式
4.2 单纯形算法概览
4.2.1 基变量和非基变量
4.2.2 可行解
4.3 无界方向
4.4 为什么LP有最优bfs
4.4.1 相邻基本可行解
4.4.2 三维LP的几何图形
4.5 单纯形算法
4.5.1 把LP转换成标准形式
4.5.2 当前基本可行解是最优的吗
4.5.3 确定换入变量
4.5.4 求新的基本可行解：换入变量中的主元素
4.5.5 应用于max问题的单纯形算法小结
4.5.6 表示单纯形表
4.6 使用单纯形算法求解最小化问题
4.6.1 方法1
4.6.2 方法2
4.7 可选最优解
4.8 无界LP
4.9 LINDO计算机软件包
4.10 矩阵生成器、LINGO和LP的定标
4.10.1 LINGO软件包
4.10 LP的定标
4.11 单纯形算法的退化和集中
4.12 大M法
4.12.1 大M法的描述
4.12.2 如何判别不可行LP
4.13 两阶段单纯形法
4.14 符号无限制变量
4.15 求解LP的Karmarkar方法
4.16 不存在不确定性时的多属性决策：目标规划
4.16.1 优先目标规划
4.16.2 使用LINDO或LINGO求解优先目标规划问题
4.17 使用Excel Solver求解LP
4.17.1 使用Excel Solver求解饮食问题
4.17.2 使用Solver求解Sailco示例
4.17.3 使用Value of选项
4.17.4 Solver和不可行LP
4.17.5 Solver和无界LP
4.18 本章小结
4.18.1 准备好利用单纯形算法进行求解的LP
4.18.2 单纯形算法
4.18.3 大M法
4.18.4 两阶段法
4.18.5 求解最小化问题
4.18.6 可选最优解
4.18.7 符号无限制变量
4.19 复习题
附录A LINDO菜单命令和语句
A.1 菜单命令
A.2 可选的建模语句
附录B LINGO初步
B.1 什么是LINGO
B.2 LINGO的基础知识
附录C LINGO菜单命令和功能
C.1 菜单命令
C.2 函数
参考文献
第5章 灵敏度分析：应用方法
5.1 灵敏度分析的图形介绍
5.1.1 利用图形分析目标函数系数变化时的影响
5.1.2 利用图形分析右端项变化对LP最优解的影响
5.1.3 影子价格
5.1.4 灵敏度分析的重要性
5.2 计算机和灵敏度分析
5.2.1 目标函数系数范围
5.2.2 缩减成本和灵敏度分析
5.2.3 右端项范围
5.2.4 影子价格和对偶价格
5.2.5 影子价格的符号
5.2.6 灵敏度分析以及松弛和剩余变量
5.2.7 退化和灵敏度分析
5.3 影子价格的管理应用
5.4 如果当前基不再是最优的，最优Z将发生什么情况
5.5 本章小结
5.5.1 图形灵敏度分析
5.5.2 影子价格
5.5.3 目标函数系数范围
5.5.4 缩减成本
5.5.5 右端项范围
5.5.6 影子价格的符号
5.5.7 作为约束条件右端项之函数的最优Z值
5.5.8 作为目标函数系数之函数的最优Z值
5.6 复习题
第6章 灵敏度分析和对偶理论
6.1 灵敏度分析的图形介绍
6.1.1 利用图形分析目标函数系数变化时的影响
6.1.2 利用图形分析右端项变化对LP最优解的影响
6.1.3 影子价格
6.1.4 灵敏度分析的重要性
6.2 一些重要的公式
6.2.1 根据B〓和原LP表示单纯形表中的约束条件
6.2.2 根据原LP确定最优表的第0行
6.2.3 简化变量为松弛、剩余或人工变量时的公式(10)
6.2.4 根据原表计算最优表的公式小结
6.3 灵敏度分析
6.3.1 改变非基变量的目标函数系数
6.3.2 改变基变量的目标函数系数
6.3.3 解释LINDO输出的目标系数范围块
6.3.4 改变约束条件的右端项
6.3.5 解释LINDO输出的右端项范围块
6.3.6 改变非基变量列
6.3.7 增加新活动
6.4 多个参数发生变化时的灵敏度分析：100％规则
6.4.1 改变目标函数系数的100％规则
6.4.2 改变右端项的100％规则
6.5 求LP的对偶
6.5.1 求规范max或min问题的对偶
6.5.2 求非规范LP的对偶
6.6 对偶问题的经济解释
6.6.1 解释max问题的对偶
6.6.2 解释min问题的对偶
6.7 对偶理论及其推论
6.7.1 弱对偶性
6.7.2 对偶理论
6.7.3 当原问题是max问题时，如何根据最优表的第0行判别最优对偶解
6.7.4 当原问题是min问题时，如何根据最优表的第0行判别最优对偶解
6.8 影子价格
6.8.1 影子价格符号的直观解释
6.8.2 解释LINDO输出的对偶价格列
6.8.3 退化和灵敏度分析
6.9 对偶性和灵敏度分析
6.10 互补松弛性
6.11 对偶单纯形法
6.11.1 max问题的对偶单纯形法
6.11.2 把一个约束条件添加到LP中以后，求新的最优解
6.11.3 改变右端项以后，求新的最优解
6.11.4 求解规范min问题
6.12 数据开发分析
6.12.1 使用LINGO运行DEA
6.12.2 对偶价格和DEA
6.13 本章小结
6.13.1 图形灵敏度分析
6.13.2 影子价格(1)
6.13.3 符号表示
6.13.4 如何根据初始LP计算最优表
6.13.5 灵敏度分析
6.13.6 目标函数系数范围
6.13.7 缩减成本
6.13.8 右端项范围
6.13.9 求LP的对偶问题
6.13.10 对偶理论
6.13.11 求LP的最偶问题的最优解
6.13.12 影子价格(2)
6.13.13 对偶性和灵敏度分析
6.13.14 互补松弛性
6.13.15 对偶单纯形法
6.14 复习题
参考文献
第7章 运输、指派和转运问题
7.1 表述运输问题
7.1.1 运输问题的一般性描述
7.1.2 对总供应量超过总需求量的运输问题进行平衡
7.1.3 对总供应量小于总需求量的运输问题进行平衡
7.1.4 把库存问题建模为运输问题
7.1.5 在计算机上求解运输问题
7.1.6 由Excel电子表格获得LINGO数据
7.1.7 运输问题的电子表格求解方法
7.2 求运输问题的基本可行解
7.2.1 求基本可行解的西北角法
7.2.2 求基本可行解的最少成本法
7.2.3 求基本可行解的伏格尔法
7.3 运输单纯形法
7.3.1 运输问题中的旋转运算
7.3.2 对非基变量进行定价(以第6章为基础)
7.3.3 如何确定换入非基变量(以第5章为基础)
7.3.4 运输单纯形法小结和举例
7.4 运输问题的灵敏度分析
7.4.1 改变非基变量的目标函数系数
7.4.2 改变基变量的目标函数系数
7.4.3 把供应量S〓和需求量d〓同时增加Δ
7.5 指派问题
7.5.1 匈牙利方法
7.5.2 指派问题的计算机解法
7.6 转运问题
7.7 本章小结
7.7.1 符号表示
7.7.2 求平衡运输问题的基本可行解
7.7.3 求运输问题的最优解
7.7.4 指派问题
7.7.5 转运问题
7.7.6 运输问题的灵敏度分析
7.8 复习题
参考文献
第8章 网络模型
8.1 基本定义
8.2 最短路径问题
8.2.1 Dijkstra算法
8.2.2 作为转运问题的最短路径问题
8.3 最大流量问题
8.3.1 最大流最问题的LP解法
8.3.2 利用LINGO求解最大流量问题
8.3.3 求解最大流量问题的Ford-Fulkerson方法
8.3.4 Ford-Fulkerson方法小结和举例
8.4 CPM和PERT
8.4.1 计算事项最早时间
8.4.2 计算事项最迟时间
8.4.3 总时差
8.4.4 求关键路线
8.4.5 单时差
8.4.6 使用线性规划求关键路线
8.4.7 项目赶期
8.4.8 使用LINGO确定关键路线
8.4.9 PERT：计划评审法
8.4.10 PERT的难点
8.5 最少费用网络流量问题
8.5.1 把运输问题表述为MCNFP
8.5.2 把最大流量问题表述为MCNFP
8.5.3 利用LINGO求解MCNFP
8.6 最小生成树问题
8.7 网络单纯形法
8.7.1 MCNFP的基本可行解
8.7.2 计算bfs的第0行
8.7.3 网络单纯形法中的旋转变换
8.7.4 网络单纯形法小结
8.8 本章小结
8.8.1 最短路径问题
8.8.2 最大流量问题
8.8.3 关键路线法
8.8.4 PERT
8.8.5 最少费用网络流量问题
8.8.6 最小生成树问题
8.8.7 网络单纯形法
8.9 复习题
参考文献
第9章 整数规划
9.1 整数规划简介
9.2 表述整数规划问题
9.2.1 固定费用问题
9.2.2 集合覆盖问题
9.2.3 二选一约束条件
9.2.4 假设(if-then)约束条件
9.2.5 整数规划和分段线性函数
9.2.6 利用LINDO求解IP
9.2.7 利用LINGO求解IP
9.2.8 使用Excel Solver求解IP问题
9.3 求解纯整数规划问题的分枝定界法
9.4 求解混合整数规划问题的分枝定界法
9.5 利用分枝定界法求解背包问题
9.6 利用分枝定界法求解组合最优化问题
9.6.1 求解机器调度问题的分枝定界法
9.6.2 求解旅行推销员问题的分枝定界法
9.6.3 求解TSP的启发式方法
9.6.4 评价启发式方法
9.6.5 TSP的整数规划表述
9.6.6 使用LINGO求解TSP
9.7 隐枚举法
9.8 割平面法
9.9 本章小结
9.9.1 整数规划表述
9.9.2 固定费用问题
9.9.3 二选一约束条件
9.9.4 假设(if-then)约束条件
9.9.5 如何利用O—1型变量建立分段线性函数f(x)的模型
9.9.6 分枝定界法
9.9.7 求解纯IP的分枝定界法
9.9.8 求解混合IP的分枝定界法
9.9.9 求解背包问题的分枝定界法
9.9.10 使单台机器上的延迟时间最短的分枝定界法
9.9.11 求解旅行推销员问题的分枝定界法
9.9.12 求解TSP的启发式方法
9.9.13 隐枚举法
9.9.14 割平面法
9.10 复习题
参考文献
第10章 线性规划的高级主题
10.1 改进单纯形法
10.2 逆矩阵的乘积形式
10.3 使用列生成法求解大型LP
10.4 Dantzig-Wolfe分解算法
10.5 上界变量单纯形法
10.6 求解LP的Karmarkar方法
10.6.1 投影
10.6.2 Karmarkar方法的中心变换
10.6.3 Karmarkar方法的说明和示例
10.6.4 Karmarkar方法的第一次迭代
10.6.5 势函数
10.6.6 把LP变换成Karmarkar方法的标准形式
10.7 本章小结
10.7.1 改进单纯形法和逆矩阵的乘积形式
10.7.2 列生成法
10.7.3 Dantzig-Wolfe分解算法
10.7.4 上界变量单纯形法
10.7.5 Karmarkar方法
10.8 复习题
参考文献
第11章 非线性规划
11.1 微积分理论
11.1.1 极限
11.1.2 连续性
11.1.3 微分
11.1.4 高阶导数
11.1.5 泰勒级数展开式
11.1.6 偏导数
11.2 基本概念
11.2.1 NLP的示例
11.2.2 利用LINGO求解NLP
11.2.3 NLP和LP之间的区别
11.2.4 局部极值
11.2.5 NLP表述的其他示例
11.2.6 利用Excel求解NLP
11.3 凸函数和凹函数
11.4 求解单变量的NLP
11.4.1 情况1：α<x<b且〓'〓(x)=0的点
11.4.2 情况2：〓'〓(x)不存在的点
11.4.3 情况3：区间[α,b]的端点α和b
11.4.4 定价和非线性优化
11.4.5 利用LINGO求解单变量NLP
11.5 黄金分割搜索法
11.6 具有多个变量的无约束最大化和最小化问题
11.7 最速上升法
11.8 拉格朗日乘子
11.8.1 拉格朗日乘子的几何解释
11.8.2 拉格朗日乘子和灵敏度分析
11.8.3 在LINGO上求解具有等式约束条件的NLP
11.9 库恩-塔克条件
11.9.1 库恩-塔克条件的几何解释
11.9.2 制约条件
11.9.3 在LINGO上求解具有不等式(也许还有等式)约束条件的NLP
11.9.4 解释LINGO输出的Price列
11.10 二次规划
11.10.1 二次规划和投资组合选择
11.10.2. 利用LINGO求解NLP
11.10.3 NLP的电子表格解法
11.10.4 求解二次规划问题的Wolfe方法
11.11 分离规划
11.12 可行方向法
11.13 帕累托最优化理论和权衡曲线
11.14 本章小结
11.14.1 凸函数和凹函数
11.14.2 求解单变量的NLP
11.14.3 黄金分割搜索法
11.14.4 具有多个变量的无约束最大化和最小化问题
11.14.5 最速上升法
11.14.6 拉格朗日乘子
11.14.7 库恩-塔克条件
11.14.8 二次规划
11.14.9 分离规划
11.14.10 可行方向法
11.14.11 权衡曲线过程小结
11.15 复习题
参考文献
第12章 对策论
12.1 二人零和与恒定和对策：鞍点
12.1.1 二人零和对策的特点
12.1.2 二人零和对策理论的基本假设
12.1.3 二人恒定和对策
12.2 二人零和对策：随机化策略、控制和图解法
12.2.1 随机化策略或混合策略
12.2.2 Odd和Even的图解
12.2.3 更多关于值和最优策略的概念
12.3 线性规划和零和对策
12.3.1 行局中人的LP
12.3.2 列局中人的LP
12.3.3 行局中人的LP和列局中人的LP之间的关系
12.3.4 如何求解行和列局中人的LP
12.3.5 使用LINDO或LINGO来求解二人零和对策
12.3.6 关于如何求解二人零和对策的小结
12.4 二人非恒定和对策
12.5 n人对策理论简介
12.6 n人对策的核心
12.7 沙普利值*
12.8 本章小结
12.8.1 二人零和与恒定和对策
12.8.2 二人非恒定和对策
12.8.3 n人对策
12.9 复习题
参考文献
附录A @Risk锦囊
附录B 案例
案例1 帮帮忙，我一点都没有变年轻!
案例2 你们家的太阳能
案例3 Golf-Sport：管理运营
案例4 Vision公司：生产规划和装运
案例5 通用邮件处理设施的材料处理
案例6 选择公司培训计划
案例7 BestChip：扩张策略
案例8 消防车在Springfield的位置
案例9 System Design：项目管理
案例10 Help-You公司的模块化设计
案例11 Brite Power：容量扩展