運籌學應用范例與解法（第4版）

第1章建模理論概述
1.1模型化概述
1.1.1說明性模型或最優(yōu)化模型
1.1.2目標函數(shù)
1.1.3決策變量
1.1.4約束條件
1.1.5完整的最優(yōu)化模型
1.1.6靜態(tài)和動態(tài)模型
1.1.7線性和非線性模型
1.1.8整數(shù)和非整數(shù)模型
1.1.9確定性和隨機性模型
1.27步驟建模過程
1.3CITGO石油公司
1.3.1最優(yōu)化煉油廠的經(jīng)營
1.3.2SDM系統(tǒng)
1.4舊金山警察局調(diào)度方法
1.5GE Capital公司
參考文獻
第2章線性代數(shù)基礎知識
2.1矩陣和向量
2.1.1矩陣
2.1.2向量
2.1.3兩個向量的標量積
2.1.4矩陣運算
2.1.5矩陣乘法的性質(zhì)
2.1.6利用Excel的矩陣乘法
2.2線性方程的矩陣和線性方程組
2.3解線性方程組的高斯約當方法
2.3.1基本行運算
2.3.2利用高斯約當方法求解
2.3.3特殊情況： 無解或者有無窮多組解
2.3.4高斯約當方法小結(jié)
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小結(jié)
2.7.1矩陣
2.7.2矩陣和線性方程
2.7.3高斯約當方法
2.7.4線性無關、線性相關和矩陣的秩
2.7.5逆矩陣
2.7.6行列式
2.8復習題
參考文獻
第3章線性規(guī)劃
3.1什么是線性規(guī)劃問題
3.1.1比例性假定和相加性假定
3.1.2可除性假定
3.1.3確定性假定
3.1.4可行域和最優(yōu)解
3.2兩變量線性規(guī)劃問題的圖解法
3.2.1求可行解
3.2.2求最優(yōu)解
3.2.3綁定和非綁定約束條件
3.2.4凸集、極點和LP
3.2.5最小化問題的圖解法
3.3特殊情況
3.3.1可選或多個最優(yōu)解
3.3.2不可行LP
3.3.3無界LP
3.4飲食問題
3.5工作調(diào)度問題
3.5.1制定公平的員工調(diào)度方案
3.5.2建模問題
3.5.3現(xiàn)實應用
3.6資本預算問題
3.6.1利用Excel計算NPV
3.6.2XNPV函數(shù)
3.7短期財務計劃
3.8混合問題
3.8.1建模問題
3.8.2現(xiàn)實應用
3.9生產(chǎn)過程模型
3.10使用線性規(guī)劃求解多階段問題： 庫存模型
3.11多階段財務模型
3.12多階段工作調(diào)度
3.13小結(jié)
3.13.1線性規(guī)劃的定義
3.13.2線性規(guī)劃問題的圖解法
3.13.3LP的解： 4種情況
3.13.4表述LP
3.14復習題
參考文獻
第4章單純形算法和目標規(guī)劃
4.1如何將LP轉(zhuǎn)換成標準形式
4.2單純形算法概覽
4.2.1基變量和非基變量
4.2.2可行解
4.3無界方向
4.4為什么LP有最優(yōu)bfs
4.4.1相鄰基本可行解
4.4.2三維LP的幾何圖形
4.5單純形算法
4.5.1把LP轉(zhuǎn)換成標準形式
4.5.2當前基本可行解是最優(yōu)的嗎
4.5.3確定換入變量
4.5.4求新的基本可行解： 換入變量中的主元素
4.5.5應用于max問題的單純形算法小結(jié)
4.5.6表示單純形表
4.6使用單純形算法求解最小化問題
4.6.1方法1
4.6.2方法2
4.7可選最優(yōu)解
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不存在不確定性時的多屬性決策： 目標規(guī)劃
4.16.1優(yōu)先目標規(guī)劃
4.16.2使用LINDO或LINGO求解優(yōu)先目標規(guī)劃問題
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本章小結(jié)
4.18.1準備好利用單純形算法進行求解的LP
4.18.2單純形算法
4.18.3大M法
4.18.4兩階段法
4.18.5求解最小化問題
4.18.6可選最優(yōu)解
4.18.7符號無限制變量
4.19復習題
附錄ALINDO菜單命令和語句
A.1菜單命令
A.2可選的建模語句
附錄BLINGO初步
B.1什么是LINGO
B.2LINGO的基礎知識
附錄CLINGO菜單命令和功能
C.1菜單命令
C.2函數(shù)
參考文獻
第5章靈敏度分析： 應用方法
5.1靈敏度分析的圖形介紹
5.1.1利用圖形分析目標函數(shù)系數(shù)變化時的影響
5.1.2利用圖形分析右端項變化對LP最優(yōu)解的影響
5.1.3影子價格
5.1.4靈敏度分析的重要性
5.2計算機和靈敏度分析
5.2.1目標函數(shù)系數(shù)范圍
5.2.2縮減成本和靈敏度分析
5.2.3右端項范圍
5.2.4影子價格和對偶價格
5.2.5影子價格的符號
5.2.6靈敏度分析以及松弛和剩余變量
5.2.7退化和靈敏度分析
5.3影子價格的管理應用
5.4如果當前基不再是最優(yōu)的，最優(yōu)z將發(fā)生什么情況
5.5本章小結(jié)
5.5.1圖形靈敏度分析
5.5.2影子價格
5.5.3目標函數(shù)系數(shù)范圍
5.5.4縮減成本
5.5.5右端項范圍
5.5.6影子價格的符號
5.5.7作為約束條件右端項之函數(shù)的最優(yōu)z值
5.5.8作為目標函數(shù)系數(shù)之函數(shù)的最優(yōu)z值
5.6復習題
第6章靈敏度分析和對偶理論
6.1靈敏度分析的圖形介紹
6.1.1利用圖形分析目標函數(shù)系數(shù)變化時的影響
6.1.2利用圖形分析右端項變化對LP最優(yōu)解的影響
6.1.3影子價格
6.1.4靈敏度分析的重要性
6.2一些重要的公式
6.2.1根據(jù)B-1和原LP表示單純形表中的約束條件
6.2.2根據(jù)原LP確定最優(yōu)表的第0行
6.2.3簡化變量為松弛、剩余或人工變量時的公式(10)
6.2.4根據(jù)原表計算最優(yōu)表的公式小結(jié)
6.3靈敏度分析
6.3.1改變非基變量的目標函數(shù)系數(shù)
6.3.2改變基變量的目標函數(shù)系數(shù)
6.3.3解釋LINDO輸出的目標系數(shù)范圍塊
6.3.4改變約束條件的右端項
6.3.5解釋LINDO輸出的右端項范圍塊
6.3.6改變非基變量列
6.3.7增加新活動
6.4多個參數(shù)發(fā)生變化時的靈敏度分析： 100%規(guī)則
6.4.1改變目標函數(shù)系數(shù)的100%規(guī)則
6.4.2改變右端項的100%規(guī)則
6.5求LP的對偶
6.5.1求規(guī)范max或min問題的對偶
6.5.2求非規(guī)范LP的對偶
6.6對偶問題的經(jīng)濟解釋
6.6.1解釋max問題的對偶
6.6.2解釋min問題的對偶
6.7對偶理論及其推論
6.7.1弱對偶性
6.7.2對偶理論
6.7.3當原問題是max問題時，如何根據(jù)最優(yōu)表的第0行判別
最優(yōu)對偶解
6.7.4當原問題是min問題時，如何根據(jù)最優(yōu)表的第0行判別
最優(yōu)對偶解
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中以后，求新的最優(yōu)解
6.11.3改變右端項以后，求新的最優(yōu)解
6.11.4求解規(guī)范min問題
6.12數(shù)據(jù)開發(fā)分析
6.12.1使用LINGO運行DEA
6.12.2對偶價格和DEA
6.13本章小結(jié)
6.13.1  圖形靈敏度分析
6.13.2影子價格(1)
6.13.3符號表示
6.13.4如何根據(jù)初始LP計算最優(yōu)表
6.13.5靈敏度分析
6.13.6目標函數(shù)系數(shù)范圍
6.13.7縮減成本
6.13.8右端項范圍
6.13.9求LP的對偶問題
6.13.10對偶理論
6.13.11求LP的最偶問題的最優(yōu)解
6.13.12影子價格(2)
6.13.13對偶性和靈敏度分析
6.13.14互補松弛性
6.13.15對偶單純形法
6.14復習題
參考文獻
第7章運輸、指派和轉(zhuǎn)運問題
7.1表述運輸問題
7.1.1運輸問題的一般性描述
7.1.2對總供應量超過總需求量的運輸問題進行平衡
7.1.3對總供應量小于總需求量的運輸問題進行平衡
7.1.4把庫存問題建模為運輸問題
7.1.5在計算機上求解運輸問題
7.1.6由Excel電子表格獲得LINGO數(shù)據(jù)
7.1.7運輸問題的電子表格求解方法
7.2求運輸問題的基本可行解
7.2.1求基本可行解的西北角法
7.2.2求基本可行解的最少成本法
7.2.3求基本可行解的伏格爾法
7.3運輸單純形法
7.3.1運輸問題中的旋轉(zhuǎn)運算
7.3.2對非基變量進行定價(以第6章為基礎)
7.3.3如何確定換入非基變量(以第5章為基礎)
7.3.4運輸單純形法小結(jié)和舉例
7.4運輸問題的靈敏度分析
7.4.1改變非基變量的目標函數(shù)系數(shù)
7.4.2改變基變量的目標函數(shù)系數(shù)
7.4.3把供應量si和需求量dj同時增加Δ
7.5指派問題
7.5.1匈牙利方法
7.5.2指派問題的計算機解法
7.6轉(zhuǎn)運問題
7.7本章小結(jié)
7.7.1符號表示
7.7.2求平衡運輸問題的基本可行解
7.7.3求運輸問題的最優(yōu)解
7.7.4指派問題
7.7.5轉(zhuǎn)運問題
7.7.6運輸問題的靈敏度分析
7.8復習題
參考文獻
第8章網(wǎng)絡模型
8.1基本定義
8.2最短路徑問題
8.2.1Dijkstra算法
8.2.2作為轉(zhuǎn)運問題的最短路徑問題
8.3最大流量問題
8.3.1最大流最問題的LP解法
8.3.2利用LINGO求解最大流量問題
8.3.3求解最大流量問題的FordFulkerson方法
8.3.4FordFulkerson方法小結(jié)和舉例
8.4CPM和PERT
8.4.1計算事項最早時間
8.4.2計算事項最遲時間
8.4.3總時差
8.4.4求關鍵路線
8.4.5單時差
8.4.6使用線性規(guī)劃求關鍵路線
8.4.7項目趕期
8.4.8使用LINGO確定關鍵路線
8.4.9PERT： 計劃評審法
8.4.10PERT的難點
8.5最少費用網(wǎng)絡流量問題
8.5.1把運輸問題表述為MCNFP
8.5.2把最大流量問題表述為MCNFP
8.5.3利用LINGO求解MCNFP
8.6最小生成樹問題
8.7網(wǎng)絡單純形法
8.7.1MCNFP的基本可行解
8.7.2計算bfs的第0行
8.7.3網(wǎng)絡單純形法中的旋轉(zhuǎn)變換
8.7.4網(wǎng)絡單純形法小結(jié)
8.8本章小結(jié)
8.8.1最短路徑問題
8.8.2最大流量問題
8.8.3關鍵路線法
8.8.4PERT
8.8.5最少費用網(wǎng)絡流量問題
8.8.6最小生成樹問題
8.8.7網(wǎng)絡單純形法
8.9復習題
參考文獻
第9章整數(shù)規(guī)劃
9.1整數(shù)規(guī)劃簡介
9.2表述整數(shù)規(guī)劃問題
9.2.1固定費用問題
9.2.2集合覆蓋問題
9.2.3二選一約束條件
9.2.4假設(ifthen)約束條件
9.2.5整數(shù)規(guī)劃和分段線性函數(shù)
9.2.6利用LINDO求解IP
9.2.7利用LINGO求解IP
9.2.8使用Excel Solver求解IP問題
9.3求解純整數(shù)規(guī)劃問題的分枝定界法
9.4求解混合整數(shù)規(guī)劃問題的分枝定界法
9.5利用分枝定界法求解背包問題
9.6利用分枝定界法求解組合最優(yōu)化問題
9.6.1求解機器調(diào)度問題的分枝定界法
9.6.2求解旅行推銷員問題的分枝定界法
9.6.3求解TSP的啟發(fā)式方法
9.6.4評價啟發(fā)式方法
9.6.5TSP的整數(shù)規(guī)劃表述
9.6.6使用LINGO求解TSP
9.7隱枚舉法
9.8割平面法
9.9本章小結(jié)
9.9.1整數(shù)規(guī)劃表述
9.9.2固定費用問題
9.9.3二選一約束條件
9.9.4假設(ifthen)約束條件
9.9.5如何利用0—1型變量建立分段線性函數(shù)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的啟發(fā)式方法
9.9.13隱枚舉法
9.9.14割平面法
9.10復習題
參考文獻
第10章線性規(guī)劃的高級主題
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勢函數(shù)
10.6.6把LP變換成Karmarkar方法的標準形式
10.7本章小結(jié)
10.7.1改進單純形法和逆矩陣的乘積形式
10.7.2列生成法
10.7.3 DantzigWolfe分解算法
10.7.4上界變量單純形法
10.7.5Karmarkar方法
10.8復習題
參考文獻
第11章非線性規(guī)劃
11.1微積分理論
11.1.1極限
11.1.2連續(xù)性
11.1.3微分
11.1.4高階導數(shù)
11.1.5泰勒級數(shù)展開式
11.1.6偏導數(shù)
11.2基本概念
11.2.1NLP的示例
11.2.2利用LINGO求解NLP
11.2.3NLP和LP之間的區(qū)別
11.2.4局部極值
11.2.5NLP表述的其他示例
11.2.6利用Excel求解NLP
11.3凸函數(shù)和凹函數(shù)
11.4求解單變量的NLP
11.4.1情況1： a＜x＜b且f′(x)=0的點
11.4.2情況2： f′(x)不存在的點
11.4.3情況3： 區(qū)間［a,b］的端點a和b
11.4.4定價和非線性優(yōu)化
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二次規(guī)劃
11.10.1二次規(guī)劃和投資組合選擇
11.10.2利用LINGO求解NLP
11.10.3NLP的電子表格解法
11.10.4求解二次規(guī)劃問題的Wolfe方法
11.11分離規(guī)劃
11.12可行方向法
11.13帕累托最優(yōu)化理論和權衡曲線
11.14本章小結(jié)
11.14.1凸函數(shù)和凹函數(shù)
11.14.2求解單變量的NLP
11.14.3黃金分割搜索法
11.14.4具有多個變量的無約束最大化和最小化問題
11.14.5最速上升法
11.14.6拉格朗日乘子
11.14.7庫恩塔克條件
11.14.8二次規(guī)劃
11.14.9分離規(guī)劃
11.14.10可行方向法
11.14.11權衡曲線過程小結(jié)
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更多關于值和最優(yōu)策略的概念
12.3線性規(guī)劃和零和對策
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關于如何求解二人零和對策的小結(jié)
12.4二人非恒定和對策
12.5n人對策理論簡介
12.6n人對策的核心
12.7沙普利值＊
12.8本章小結(jié)
12.8.1二人零和與恒定和對策
12.8.2二人非恒定和對策
12.8.3n人對策
12.9復習題
參考文獻
附錄A@Risk錦囊
附錄B案例
案例1幫幫忙，我一點都沒有變年輕！
案例2你們家的太陽能
ⅩⅦ案例3GolfSport： 管理運營
案例4Vision公司： 生產(chǎn)規(guī)劃和裝運
案例5通用郵件處理設施的材料處理
案例6選擇公司培訓計劃
案例7BestChip： 擴張策略
案例8消防車在Springfield的位置
案例9System Design： 項目管理
案例10HelpYou公司的模塊化設計
案例11Brite Power： 容量擴展