學習用書為《Optimization in Operations Research》
Ronald L。Rardin
著。
第一章 運用數學模型解決問題
運籌學
（operations research，op）是研究如何為複雜的工程或者管理問題構建數學模型，以及如何分析模型以探索可能解決方案的一門學科。
運籌學方法的步驟
三個建模的基本關注點為（a）決策者需要做出的
決策（decision）
、（b）限制決策選擇的
約束（constraint）
、（c）人們偏好的決策所產生的
目標（objective）
。
可行解（feasible solution）
是滿足所有約束條件的決策變數的取值，
最優解（optional solution）
是能夠是目標函式值優於其他任意可行解的可行解。
小結：
運籌學分析者所面臨的選擇：是一些粗略的計算就已足夠，還是需要建立一個有條理的模型去解決問題；是需要建立一個比較細化的（因而比較有效的）模型，還是建立一個比較容易處理的近似模型。以模型為基礎的運籌學方法適用於解決那些足夠重要的、值得花時間與資源仔細研究的問題。
第二章 運籌學中的確定性最佳化模型
最佳化模型中描述決策的變數即為
決策變數
。
變數型別約束
詳細的說明了決策變數的定義域，即在什麼樣的取值集合中決策變數才有實際意義。
主約束
（main constrint）是最佳化模型中除變數型別約束外，其他所有表明對決策變數的限制以及表示決策變數之間關係的約束條件。
目標函式
是在最佳化模型中量化決策結果的函式，決策的目的通常是最大化或者最小化目標函式。
最佳化模型的標準形式如下：
min或max ［目標函式（可以是多個）］
s。t。（主約束）
（變數型別約束）
最優解
（optimal solution）是可行域內的決策變數某個（些）取值組合，這個（組）決策變數值能使目標函式值不差於其他可行解所能達到的目標函式值。
一個最佳化模型只可能存在一個
最優值
，但一個最優值可能對應多個最優解。
透過標引與矩陣可以用簡單的公式描述規模龐大的最佳化問題。
一個方程，如果它是關於決策變數的常數加權求和形式，則該方程為
線性
（linear）方程，否則該方程為
非線性
（non-linear）方程。
如果單一目標函式方程
f
以及約束方程
，···，
中均為關於決策變數的線性方程，則該最佳化模型為
線性規劃
（linear program，LP），其中目標函式值可以為滿足約束的任意整數或分數。
如果單一目標函式方程
f
以及約束方程
，···，
中存在關於決策變數的非線性方程，則該最佳化模型為
非線性規劃
（nonlinear program，NLP），其中目標函式值可以為滿足約束的任意整數或分數。
如果一個變數的取值範圍為某一區間的一些特定的或者可數的取值的集合，則該變數為
離散變數
。0-1變數（取值為0或者1的變數）是一種常用的離散變數。
如果一個變數的取值範圍為某一區間的任意數值，則該變數為
連續變數
（continuous）。
對於一些實際中應該為離散變數的決策變數，當最優決策變數的量級足夠大以至於分數對於實際應用沒有太大影響時，我們相對於離散變數更應該採用連續變數，因為連續變數相對於離散變數會大大降低最佳化問題的處理難度。
一個最佳化模型，如果它的決策變數中存在離散變數，則該最佳化模型為
整數規劃
（integer program，IP）。如果整數規劃中所有決策變數均為離散變數，則該整數規劃為
純整數規劃
（pure integer program）；否則，為
混合整數規劃
（mixed-integer program）。
當單一目標不再適用時，我們就需要另外一種新的模型——
多目標最佳化模型
（同時最大化或者最小化多個目標函式）去解決這樣一類問題。
當我們可以選擇時，我們要優先建立單目標最佳化模型而不是多目標最佳化模型，因為多目標最佳化模型目標函式之間的衝突會使得問題處理難度大大增加。
小結：
最佳化問題的型別如線性或者非線性、連續或者離散、單目標或者多目標，會對解決一個實際問題的難易程度、用何種方法解決產生巨大的影響。因此首要問題就是識別出要解決實際問題所對應的模型型別。
AMPL（A Modeling Language for Mathematical Programing）是一種應用極為廣泛的建模語言。
第三章 搜尋演算法
前序：
一些最佳化模型的最優解能夠透過顯式表示式明確刻畫出來，但絕大多數最佳化模型卻只能透過
數值搜尋
（numerical search）的方法來求解，即依次嘗試不同的決策變數取值，直到得到一個滿意的結果。大多數最佳化過程都可以看做是搜尋演算法的衍生方法。
搜尋演算法
（improving search）透過檢查鄰域來尋找比當前更好的解，若有改進，則替換當前解，繼續迭代，直到鄰域中沒有更好的解為止。搜尋演算法又稱
區域性改進
（local improvement）、
爬山演算法
（hillclimbing）、
區域性搜尋
（local search）或
鄰域搜尋
（neighborhood search）。搜尋就像狩獵，而搜尋演算法就是狩獵者的策略。
解是一組決策變數的取值。
對於決策向量為
x
的模型，搜尋過程經過第一組解表示為
，第二組為
，以此類推。
當前解
的鄰域（neighborhood）由所有附近的點組成，即所有與
有一段微小的正向距離的點。
倘若一組可行解周圍足夠小的領域內不存在優於該解的可行點，則稱該解為
區域性最優解
（local optimum）。最小化（最大化）問題存在
區域性最小（最大）解
。
如果在全域性範圍內不存在目標值優於某可行解的其他可行點，則稱該可行解為
全域性最優解
（global optimum）。最小化（最大化）問題存在全域性最小（最大）解。
全域性最優也是區域性最優，區域性最優不一定是全域性最優。
搜尋演算法最適應的是那些能夠從數學上保證每一個區域性最優都是全域性最優的最佳化模型。
方向步長（direction-step）正規化:
搜尋演算法沿
+
由當前點
向下一搜索點
移動，其中
是在當前點
處的
搜尋方向
（move direction），
（
>0）是沿該方向前進的
步長
（step size）。
對於所有足夠小的
，且
>0，都有
+
的目標值優於
，則稱
是當前解的一個
改進方向
（improving dirention）。
對於所有足夠小的
，且
>0，都有
+
滿足所有的約束函式，則稱
是當前解的一個
可行方向
。
確定最佳步長
：搜尋演算法通常將沿可行改進方向最大程度改進目標值，並保持可行的距離作為最佳步長
。
3A演算法：連續的搜尋演算法
第0步：初始化
。選擇初始可行解
，令t
0。
第1步：區域性最優
。如果當前解
處不存在可行改進方向
，則停止搜尋；根據模型形式的弱假設，當前解
是區域性最優點。
第2步：搜尋方向
。構建當前解
處可行改進方向。
第3步：最佳步長
。如果沿當前解的可行改進方向上存在同時改進目標值並保持可行的最大步長，則該步長為最佳步長；否則停止搜尋，該模型無界。
第4步：前進
。根據
+
得到下一搜索點
，令t
t+1，返回第1步。
最佳化模型中，只要某一組解存在可行改進方向，則該解不是區域性最優。
如果一個連續的搜尋演算法在沒有可行改進方向的解停止迭代，在弱假設下可以認為該點是區域性最優的。弱假設是因為存在沒有可行改進方向的當前解不是區域性最優，即當某點處任意直線方向的移動都無法改進目標值，而曲線方向卻可以改進目標值。
如果沿某一可行改進方向前進任意步長都能同時改進目標值並保持可行性，則該模型是
無界的
（unbounded）。
改進方向的梯度條件：
1.
對於最大化目標函式
，若
（
）
0，搜尋方向
是
處的改進方向；若
（
）
0，搜尋方向
不是
處的改進方向。
2.
對於最小化目標函式
，若
（
）
0，搜尋方向
是
處的改進方向；若
（
）
0，搜尋方向
不是
處的改進方向。
目標函式梯度作為搜尋方向：
當目標函式梯度
（
）
0，
（
）是最大化目標
的一個改進方向，
（
）是最小化目標
的一個改進方向。
起作用約束
（active constraint）是當前解
處恰好滿足等式的約束。
線性約束下可行方向的代數條件：
對於線性約束最佳化問題，當且僅當
所有起作用大於等於約束
，有：
0
所有起作用小於等於約束
，有：
0
所有起作用小於等於約束
，有：
0
時，搜尋方向
對於解
是可行的。
凸集：
如果可行域內任意兩點的連線都在可行域內，則稱該可行域為凸集（convex）。
離散的可行集總是非凸集（只有一個可行點的情況除外）。
連線的代數表示：
向量解
和
之間的連線由
，
上所有的點組成。
凸集和線性目標的全域性最優性：
對於一個具有線性目標和凸可行集的最佳化模型，若3A搜尋演算法在一個可行解
處停止，且不存在可行改進方向，則
是全域性最優解。也就是說，對於具有線性目標和凸集的模型，區域性最優解就是全域性最優解。
如果最佳化模型所有約束都是線性的（包括主要約束和變數約束），那麼該模型的可行域是凸集。
由上述兩個原理可以看出，線性約束的區域性最優解就是全域性最優解。
線性規劃中限制步長的約束即
阻礙約束
（blocking constraint），是不起作用約束。
尋找初始可行解
：兩種人工變數法，即
兩階段法
（two-phase）和
大M法
（big-M）。
3B演算法：兩階段搜尋演算法
第0步：人工問題
。選擇一個原問題的解，透過在未滿足的約束條件中加入（或減去）非負人工變數構建第一階段的人工問題。
第1步：第一階段
。給人工變數賦值，得到一個人工問題的初始可行解。從該可行解開始執行搜尋演算法，目標是最小化人工變數之和。
第2步：不可行性分析
。若第一階段中人工變數和等於0，繼續第3步，原問題可行；若人工變數的和大於0，則原問題無可行解，停止演算法；否則回到第一步，從另一個初始可行解開始執行演算法。
第3步：第二階段
。刪去第一階段最優解中的人工變數得到原問題的初始可行解。從該可行解開始，利用常規搜尋過程尋找滿足原問題約束條件的最優解。
若第一階段搜尋在目標值為0處停止，則當前解中的原問題變數構成了原問題的一個可行解。
若第一階段搜尋在全域性最小處停止，且目標值大於0，那麼原問題無可行解。
若第一階段搜尋在區域性最小處停止，且目標值大於0，那麼無法判定。由一個新的初始解重新開始第一階段。
大M法
（單一搜索實現上述兩個階段的任務）
為了在單一目標函式中綜合考慮可行性和最優性，
大M法
引入了人工變數係數M（M為任意大的正數），對於最大化問題有：
max（原目標）
M（人工變數和）
對於最小化問題有：
min（原目標）
M（人工變數和）
係數M的作用是懲罰因子，大M法也由此命名。當目標函式要實現最大化（或最小化）時，人工變數必須等於0，否則目標函式不可能達到最大值（或最小值），這樣也就保證了當人工變數和不等於0時，原問題是無可行解的。
若大M搜尋（M足夠大）在全域性最優解處停止迭代，且存在部分人工變數大於0，那麼原問題無可行解。
若大M搜尋在一個存在部分人工變數大於0的區域性最優解處停止迭代，或者M不夠大，那麼無法進行判定，應選擇一個新的初始解或足夠大的係數M重新進行迭代。
