运筹学应用范例与解法（第4版）

第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.27步骤建模过程
1.3CITGO石油公司
1.3.1最优化炼油厂的经营
1.3.2SDM系统
1.4旧金山警察局调度方法
1.5GE 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.2XNPV函数
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.3LP的解： 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.9LINDO计算机软件包
4.10矩阵生成器、LINGO和LP的定标
4.10.1LINGO软件包
4.10.2LP的定标
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.4Solver和不可行LP
4.17.5Solver和无界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复习题
附录ALINDO菜单命令和语句
A.1菜单命令
A.2可选的建模语句
附录BLINGO初步
B.1什么是LINGO
B.2LINGO的基础知识
附录CLINGO菜单命令和功能
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-1和原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.1max问题的对偶单纯形法
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把供应量si和需求量dj同时增加Δ
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.1Dijkstra算法
8.2.2作为转运问题的最短路径问题
8.3最大流量问题
8.3.1最大流最问题的LP解法
8.3.2利用LINGO求解最大流量问题
8.3.3求解最大流量问题的FordFulkerson方法
8.3.4FordFulkerson方法小结和举例
8.4CPM和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.9PERT： 计划评审法
8.4.10PERT的难点
8.5最少费用网络流量问题
8.5.1把运输问题表述为MCNFP
8.5.2把最大流量问题表述为MCNFP
8.5.3利用LINGO求解MCNFP
8.6最小生成树问题
8.7网络单纯形法
8.7.1MCNFP的基本可行解
8.7.2计算bfs的第0行
8.7.3网络单纯形法中的旋转变换
8.7.4网络单纯形法小结
8.8本章小结
8.8.1最短路径问题
8.8.2最大流量问题
8.8.3关键路线法
8.8.4PERT
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.5TSP的整数规划表述
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如何利用0—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.4DantzigWolfe分解算法
10.5上界变量单纯形法
10.6求解LP的Karmarkar方法
10.6.1投影
10.6.2Karmarkar方法的中心变换
10.6.3Karmarkar方法的说明和示例
10.6.4Karmarkar方法的第一次迭代
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.5Karmarkar方法
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.1NLP的示例
11.2.2利用LINGO求解NLP
11.2.3NLP和LP之间的区别
11.2.4局部极值
11.2.5NLP表述的其他示例
11.2.6利用Excel求解NLP
11.3凸函数和凹函数
11.4求解单变量的NLP
11.4.1情况1： a＜x＜b且f′(x)=0的点
11.4.2情况2： f′(x)不存在的点
11.4.3情况3： 区间［a,b］的端点a和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.3NLP的电子表格解法
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.2Odd和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.5n人对策理论简介
12.6n人对策的核心
12.7沙普利值＊
12.8本章小结
12.8.1二人零和与恒定和对策
12.8.2二人非恒定和对策
12.8.3n人对策
12.9复习题
参考文献
附录A@Risk锦囊
附录B案例
案例1帮帮忙，我一点都没有变年轻！
案例2你们家的太阳能
ⅩⅦ案例3GolfSport： 管理运营
案例4Vision公司： 生产规划和装运
案例5通用邮件处理设施的材料处理
案例6选择公司培训计划
案例7BestChip： 扩张策略
案例8消防车在Springfield的位置
案例9System Design： 项目管理
案例10HelpYou公司的模块化设计
案例11Brite Power： 容量扩展