運(yùn)籌學(xué)應(yīng)用范例與解法（第4版）

第1章建模理論概述
1.1模型化概述
1.1.1說明性模型或最優(yōu)化模型
1.1.2目標(biāo)函數(shù)
1.1.3決策變量
1.1.4約束條件
1.1.5完整的最優(yōu)化模型
1.1.6靜態(tài)和動(dòng)態(tài)模型
1.1.7線性和非線性模型
1.1.8整數(shù)和非整數(shù)模型
1.1.9確定性和隨機(jī)性模型
1.27步驟建模過程
1.3CITGO石油公司
1.3.1最優(yōu)化煉油廠的經(jīng)營
1.3.2SDM系統(tǒng)
1.4舊金山警察局調(diào)度方法
1.5GE Capital公司
參考文獻(xiàn)
第2章線性代數(shù)基礎(chǔ)知識(shí)
2.1矩陣和向量
2.1.1矩陣
2.1.2向量
2.1.3兩個(gè)向量的標(biāo)量積
2.1.4矩陣運(yùn)算
2.1.5矩陣乘法的性質(zhì)
2.1.6利用Excel的矩陣乘法
2.2線性方程的矩陣和線性方程組
2.3解線性方程組的高斯約當(dāng)方法
2.3.1基本行運(yùn)算
2.3.2利用高斯約當(dāng)方法求解
2.3.3特殊情況： 無解或者有無窮多組解
2.3.4高斯約當(dāng)方法小結(jié)
2.3.5線性方程組的基變量和基本解
2.4線性相關(guān)和線性無關(guān)
2.4.1矩陣的秩
2.4.2如何判別向量組是否線性無關(guān)
2.5逆矩陣
2.5.1沒有逆矩陣的矩陣
2.5.2利用高斯約當(dāng)方法求m×m矩陣A的逆矩陣
2.5.3利用逆矩陣解線性方程組
2.5.4利用Excel求逆矩陣
2.6行列式
2.7小結(jié)
2.7.1矩陣
2.7.2矩陣和線性方程
2.7.3高斯約當(dāng)方法
2.7.4線性無關(guān)、線性相關(guān)和矩陣的秩
2.7.5逆矩陣
2.7.6行列式
2.8復(fù)習(xí)題
參考文獻(xiàn)
第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凸集、極點(diǎn)和LP
3.2.5最小化問題的圖解法
3.3特殊情況
3.3.1可選或多個(gè)最優(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)實(shí)應(yīng)用
3.6資本預(yù)算問題
3.6.1利用Excel計(jì)算NPV
3.6.2XNPV函數(shù)
3.7短期財(cái)務(wù)計(jì)劃
3.8混合問題
3.8.1建模問題
3.8.2現(xiàn)實(shí)應(yīng)用
3.9生產(chǎn)過程模型
3.10使用線性規(guī)劃求解多階段問題： 庫存模型
3.11多階段財(cái)務(wù)模型
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復(fù)習(xí)題
參考文獻(xiàn)
第4章單純形算法和目標(biāo)規(guī)劃
4.1如何將LP轉(zhuǎn)換成標(biāo)準(zhǔ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)換成標(biāo)準(zhǔn)形式
4.5.2當(dāng)前基本可行解是最優(yōu)的嗎
4.5.3確定換入變量
4.5.4求新的基本可行解： 換入變量中的主元素
4.5.5應(yīng)用于max問題的單純形算法小結(jié)
4.5.6表示單純形表
4.6使用單純形算法求解最小化問題
4.6.1方法1
4.6.2方法2
4.7可選最優(yōu)解
4.8無界LP
4.9LINDO計(jì)算機(jī)軟件包
4.10矩陣生成器、LINGO和LP的定標(biāo)
4.10.1LINGO軟件包
4.10.2LP的定標(biāo)
4.11單純形算法的退化和集中
4.12大M法
4.12.1大M法的描述
4.12.2如何判別不可行LP
4.13兩階段單純形法
4.14符號無限制變量
4.15求解LP的Karmarkar方法
4.16不存在不確定性時(shí)的多屬性決策： 目標(biāo)規(guī)劃
4.16.1優(yōu)先目標(biāo)規(guī)劃
4.16.2使用LINDO或LINGO求解優(yōu)先目標(biāo)規(guī)劃問題
4.17使用Excel Solver求解LP
4.17.1使用Excel Solver求解飲食問題
4.17.2使用Solver求解Sailco示例
4.17.3使用Value of選項(xiàng)
4.17.4Solver和不可行LP
4.17.5Solver和無界LP
4.18本章小結(jié)
4.18.1準(zhǔn)備好利用單純形算法進(jìn)行求解的LP
4.18.2單純形算法
4.18.3大M法
4.18.4兩階段法
4.18.5求解最小化問題
4.18.6可選最優(yōu)解
4.18.7符號無限制變量
4.19復(fù)習(xí)題
附錄ALINDO菜單命令和語句
A.1菜單命令
A.2可選的建模語句
附錄BLINGO初步
B.1什么是LINGO
B.2LINGO的基礎(chǔ)知識(shí)
附錄CLINGO菜單命令和功能
C.1菜單命令
C.2函數(shù)
參考文獻(xiàn)
第5章靈敏度分析： 應(yīng)用方法
5.1靈敏度分析的圖形介紹
5.1.1利用圖形分析目標(biāo)函數(shù)系數(shù)變化時(shí)的影響
5.1.2利用圖形分析右端項(xiàng)變化對LP最優(yōu)解的影響
5.1.3影子價(jià)格
5.1.4靈敏度分析的重要性
5.2計(jì)算機(jī)和靈敏度分析
5.2.1目標(biāo)函數(shù)系數(shù)范圍
5.2.2縮減成本和靈敏度分析
5.2.3右端項(xiàng)范圍
5.2.4影子價(jià)格和對偶價(jià)格
5.2.5影子價(jià)格的符號
5.2.6靈敏度分析以及松弛和剩余變量
5.2.7退化和靈敏度分析
5.3影子價(jià)格的管理應(yīng)用
5.4如果當(dāng)前基不再是最優(yōu)的，最優(yōu)z將發(fā)生什么情況
5.5本章小結(jié)
5.5.1圖形靈敏度分析
5.5.2影子價(jià)格
5.5.3目標(biāo)函數(shù)系數(shù)范圍
5.5.4縮減成本
5.5.5右端項(xiàng)范圍
5.5.6影子價(jià)格的符號
5.5.7作為約束條件右端項(xiàng)之函數(shù)的最優(yōu)z值
5.5.8作為目標(biāo)函數(shù)系數(shù)之函數(shù)的最優(yōu)z值
5.6復(fù)習(xí)題
第6章靈敏度分析和對偶理論
6.1靈敏度分析的圖形介紹
6.1.1利用圖形分析目標(biāo)函數(shù)系數(shù)變化時(shí)的影響
6.1.2利用圖形分析右端項(xiàng)變化對LP最優(yōu)解的影響
6.1.3影子價(jià)格
6.1.4靈敏度分析的重要性
6.2一些重要的公式
6.2.1根據(jù)B-1和原LP表示單純形表中的約束條件
6.2.2根據(jù)原LP確定最優(yōu)表的第0行
6.2.3簡化變量為松弛、剩余或人工變量時(shí)的公式(10)
6.2.4根據(jù)原表計(jì)算最優(yōu)表的公式小結(jié)
6.3靈敏度分析
6.3.1改變非基變量的目標(biāo)函數(shù)系數(shù)
6.3.2改變基變量的目標(biāo)函數(shù)系數(shù)
6.3.3解釋LINDO輸出的目標(biāo)系數(shù)范圍塊
6.3.4改變約束條件的右端項(xiàng)
6.3.5解釋LINDO輸出的右端項(xiàng)范圍塊
6.3.6改變非基變量列
6.3.7增加新活動(dòng)
6.4多個(gè)參數(shù)發(fā)生變化時(shí)的靈敏度分析： 100%規(guī)則
6.4.1改變目標(biāo)函數(shù)系數(shù)的100%規(guī)則
6.4.2改變右端項(xiàng)的100%規(guī)則
6.5求LP的對偶
6.5.1求規(guī)范max或min問題的對偶
6.5.2求非規(guī)范LP的對偶
6.6對偶問題的經(jīng)濟(jì)解釋
6.6.1解釋max問題的對偶
6.6.2解釋min問題的對偶
6.7對偶理論及其推論
6.7.1弱對偶性
6.7.2對偶理論
6.7.3當(dāng)原問題是max問題時(shí)，如何根據(jù)最優(yōu)表的第0行判別
最優(yōu)對偶解
6.7.4當(dāng)原問題是min問題時(shí)，如何根據(jù)最優(yōu)表的第0行判別
最優(yōu)對偶解
6.8影子價(jià)格
6.8.1影子價(jià)格符號的直觀解釋
6.8.2解釋LINDO輸出的對偶價(jià)格列
6.8.3退化和靈敏度分析
6.9對偶性和靈敏度分析
6.10互補(bǔ)松弛性
6.11對偶單純形法
6.11.1max問題的對偶單純形法
6.11.2把一個(gè)約束條件添加到LP中以后，求新的最優(yōu)解
6.11.3改變右端項(xiàng)以后，求新的最優(yōu)解
6.11.4求解規(guī)范min問題
6.12數(shù)據(jù)開發(fā)分析
6.12.1使用LINGO運(yùn)行DEA
6.12.2對偶價(jià)格和DEA
6.13本章小結(jié)
6.13.1  圖形靈敏度分析
6.13.2影子價(jià)格(1)
6.13.3符號表示
6.13.4如何根據(jù)初始LP計(jì)算最優(yōu)表
6.13.5靈敏度分析
6.13.6目標(biāo)函數(shù)系數(shù)范圍
6.13.7縮減成本
6.13.8右端項(xiàng)范圍
6.13.9求LP的對偶問題
6.13.10對偶理論
6.13.11求LP的最偶問題的最優(yōu)解
6.13.12影子價(jià)格(2)
6.13.13對偶性和靈敏度分析
6.13.14互補(bǔ)松弛性
6.13.15對偶單純形法
6.14復(fù)習(xí)題
參考文獻(xiàn)
第7章運(yùn)輸、指派和轉(zhuǎn)運(yùn)問題
7.1表述運(yùn)輸問題
7.1.1運(yùn)輸問題的一般性描述
7.1.2對總供應(yīng)量超過總需求量的運(yùn)輸問題進(jìn)行平衡
7.1.3對總供應(yīng)量小于總需求量的運(yùn)輸問題進(jìn)行平衡
7.1.4把庫存問題建模為運(yùn)輸問題
7.1.5在計(jì)算機(jī)上求解運(yùn)輸問題
7.1.6由Excel電子表格獲得LINGO數(shù)據(jù)
7.1.7運(yùn)輸問題的電子表格求解方法
7.2求運(yùn)輸問題的基本可行解
7.2.1求基本可行解的西北角法
7.2.2求基本可行解的最少成本法
7.2.3求基本可行解的伏格爾法
7.3運(yùn)輸單純形法
7.3.1運(yùn)輸問題中的旋轉(zhuǎn)運(yùn)算
7.3.2對非基變量進(jìn)行定價(jià)(以第6章為基礎(chǔ))
7.3.3如何確定換入非基變量(以第5章為基礎(chǔ))
7.3.4運(yùn)輸單純形法小結(jié)和舉例
7.4運(yùn)輸問題的靈敏度分析
7.4.1改變非基變量的目標(biāo)函數(shù)系數(shù)
7.4.2改變基變量的目標(biāo)函數(shù)系數(shù)
7.4.3把供應(yīng)量si和需求量dj同時(shí)增加Δ
7.5指派問題
7.5.1匈牙利方法
7.5.2指派問題的計(jì)算機(jī)解法
7.6轉(zhuǎn)運(yùn)問題
7.7本章小結(jié)
7.7.1符號表示
7.7.2求平衡運(yùn)輸問題的基本可行解
7.7.3求運(yùn)輸問題的最優(yōu)解
7.7.4指派問題
7.7.5轉(zhuǎn)運(yùn)問題
7.7.6運(yùn)輸問題的靈敏度分析
7.8復(fù)習(xí)題
參考文獻(xiàn)
第8章網(wǎng)絡(luò)模型
8.1基本定義
8.2最短路徑問題
8.2.1Dijkstra算法
8.2.2作為轉(zhuǎn)運(yù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計(jì)算事項(xiàng)最早時(shí)間
8.4.2計(jì)算事項(xiàng)最遲時(shí)間
8.4.3總時(shí)差
8.4.4求關(guān)鍵路線
8.4.5單時(shí)差
8.4.6使用線性規(guī)劃求關(guān)鍵路線
8.4.7項(xiàng)目趕期
8.4.8使用LINGO確定關(guān)鍵路線
8.4.9PERT： 計(jì)劃評審法
8.4.10PERT的難點(diǎn)
8.5最少費(fèi)用網(wǎng)絡(luò)流量問題
8.5.1把運(yùn)輸問題表述為MCNFP
8.5.2把最大流量問題表述為MCNFP
8.5.3利用LINGO求解MCNFP
8.6最小生成樹問題
8.7網(wǎng)絡(luò)單純形法
8.7.1MCNFP的基本可行解
8.7.2計(jì)算bfs的第0行
8.7.3網(wǎng)絡(luò)單純形法中的旋轉(zhuǎn)變換
8.7.4網(wǎng)絡(luò)單純形法小結(jié)
8.8本章小結(jié)
8.8.1最短路徑問題
8.8.2最大流量問題
8.8.3關(guān)鍵路線法
8.8.4PERT
8.8.5最少費(fèi)用網(wǎng)絡(luò)流量問題
8.8.6最小生成樹問題
8.8.7網(wǎng)絡(luò)單純形法
8.9復(fù)習(xí)題
參考文獻(xiàn)
第9章整數(shù)規(guī)劃
9.1整數(shù)規(guī)劃簡介
9.2表述整數(shù)規(guī)劃問題
9.2.1固定費(fèi)用問題
9.2.2集合覆蓋問題
9.2.3二選一約束條件
9.2.4假設(shè)(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求解機(jī)器調(diào)度問題的分枝定界法
9.6.2求解旅行推銷員問題的分枝定界法
9.6.3求解TSP的啟發(fā)式方法
9.6.4評價(jià)啟發(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固定費(fèi)用問題
9.9.3二選一約束條件
9.9.4假設(shè)(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使單臺(tái)機(jī)器上的延遲時(shí)間最短的分枝定界法
9.9.11求解旅行推銷員問題的分枝定界法
9.9.12求解TSP的啟發(fā)式方法
9.9.13隱枚舉法
9.9.14割平面法
9.10復(fù)習(xí)題
參考文獻(xiàn)
第10章線性規(guī)劃的高級主題
10.1改進(jìn)單純形法
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方法的標(biāo)準(zhǔn)形式
10.7本章小結(jié)
10.7.1改進(jìn)單純形法和逆矩陣的乘積形式
10.7.2列生成法
10.7.3 DantzigWolfe分解算法
10.7.4上界變量單純形法
10.7.5Karmarkar方法
10.8復(fù)習(xí)題
參考文獻(xiàn)
第11章非線性規(guī)劃
11.1微積分理論
11.1.1極限
11.1.2連續(xù)性
11.1.3微分
11.1.4高階導(dǎo)數(shù)
11.1.5泰勒級數(shù)展開式
11.1.6偏導(dǎo)數(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的點(diǎn)
11.4.2情況2： f′(x)不存在的點(diǎn)
11.4.3情況3： 區(qū)間［a,b］的端點(diǎn)a和b
11.4.4定價(jià)和非線性優(yōu)化
11.4.5利用LINGO求解單變量NLP
11.5黃金分割搜索法
11.6具有多個(gè)變量的無約束最大化和最小化問題
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)化理論和權(quán)衡曲線
11.14本章小結(jié)
11.14.1凸函數(shù)和凹函數(shù)
11.14.2求解單變量的NLP
11.14.3黃金分割搜索法
11.14.4具有多個(gè)變量的無約束最大化和最小化問題
11.14.5最速上升法
11.14.6拉格朗日乘子
11.14.7庫恩塔克條件
11.14.8二次規(guī)劃
11.14.9分離規(guī)劃
11.14.10可行方向法
11.14.11權(quán)衡曲線過程小結(jié)
11.15復(fù)習(xí)題
參考文獻(xiàn)
第12章對策論
12.1二人零和與恒定和對策： 鞍點(diǎn)
12.1.1二人零和對策的特點(diǎn)
12.1.2二人零和對策理論的基本假設(shè)
12.1.3二人恒定和對策
12.2二人零和對策： 隨機(jī)化策略、控制和圖解法
12.2.1隨機(jī)化策略或混合策略
12.2.2Odd和Even的圖解
12.2.3更多關(guān)于值和最優(yōu)策略的概念
12.3線性規(guī)劃和零和對策
12.3.1行局中人的LP
12.3.2列局中人的LP
12.3.3行局中人的LP和列局中人的LP之間的關(guān)系
12.3.4如何求解行和列局中人的LP
12.3.5使用LINDO或LINGO來求解二人零和對策
12.3.6關(guān)于如何求解二人零和對策的小結(jié)
12.4二人非恒定和對策
12.5n人對策理論簡介
12.6n人對策的核心
12.7沙普利值＊
12.8本章小結(jié)
12.8.1二人零和與恒定和對策
12.8.2二人非恒定和對策
12.8.3n人對策
12.9復(fù)習(xí)題
參考文獻(xiàn)
附錄A@Risk錦囊
附錄B案例
案例1幫幫忙，我一點(diǎn)都沒有變年輕！
案例2你們家的太陽能
ⅩⅦ案例3GolfSport： 管理運(yùn)營
案例4Vision公司： 生產(chǎn)規(guī)劃和裝運(yùn)
案例5通用郵件處理設(shè)施的材料處理
案例6選擇公司培訓(xùn)計(jì)劃
案例7BestChip： 擴(kuò)張策略
案例8消防車在Springfield的位置
案例9System Design： 項(xiàng)目管理
案例10HelpYou公司的模塊化設(shè)計(jì)
案例11Brite Power： 容量擴(kuò)展