【文章內(nèi)容簡介】 行解 當(dāng)存在矛盾的約束條件時，為無可行域。 如果在例 1的數(shù)學(xué)模型中增加一個約束條件 :該問題的可行域為 空集 ，即無可行解， 不存在可行域增加的約束條件圖 5小結(jié)n （ 1） 線性規(guī)劃問題的模型特征n （ 2） 通過圖解法了解如何求解線性規(guī)劃 問題n （ 3） 為求解高維線性規(guī)劃問題，必須建 立的概念線性規(guī)劃的單純形方法u 線性規(guī)劃問題的幾個定理l 單純形法的原理l 初始基可行解的確定線性規(guī)劃問題的幾個定理n 定理 1 若線性規(guī)劃問題存在可行解，則問題的 可行域是凸集。n 定理 2 線性規(guī)劃問題的基可行解對應(yīng)線性規(guī)劃 問題可行域（凸集）的頂點（極點）。n 定理 3 若線性規(guī)劃問題有最優(yōu)解，則一定存在 一個基可行解是最優(yōu)解。結(jié)論：求解線性規(guī)劃問題歸結(jié)為找最優(yōu)基可行 解， 即在其可行域（凸集）的頂點（極點） 中找使目標(biāo)函數(shù)最小的頂點（極點）。單純形法的原理n 單純形方法的基本思想 從一個基可行解出發(fā)，求一個使目標(biāo)函數(shù)值有所改善的基可行解；通過不斷改進基可行解，力圖達到最優(yōu)基可行解。 它主要通過基可行解的轉(zhuǎn)換完成。n 基可行解的轉(zhuǎn)換 考慮矩陣形式的標(biāo)準(zhǔn)形問題： 式中n最優(yōu)性檢驗和解的判別單純形方法的計算步驟步驟 1 找一個初始基可行解（常用大 M法和兩階法找）。步驟 2 解 步驟 3 求單純形乘子 ，解使用表格形式的單純形方法使用表格形式的單純形方法 用單純形法解下列問題： 初始基可行解的確定n 大 M法 基本思想：在約束中增加人工變量 ，同時改變目標(biāo)函數(shù) ，加上罰項 ，其中 是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過程中，由于大 的存在，將使人工變量離基。 考慮線性規(guī)劃問題大 M法 引進人工變量 ，研究下列問題： 用單純形法求解線性規(guī)劃問題 (114)，獲得其解，它與（ 113）的解的關(guān)系如下：大 M法n 達到問題（ 114）的最優(yōu)解，且 ，這時得到的 為問題（ 113）的最優(yōu)解。n 達到問題（ 114）的最優(yōu)解，且 ，這時問題（ 113）無可行解。n 問題（ 114）不存在有限最優(yōu)值，在單純形表中， ， 這時 問題（ 113）無界。n 問題（ 114）不存在有限最優(yōu)值，在單純形表中， ， 這時 問題（ 113）無可行解。大 M法用大 M法求解下列問題：兩個階段法n 基本思想：在約束中增加人工變量 ，以構(gòu)造一個單位矩陣。對添加了人工變量的線性規(guī)劃問題分兩個階段計算。 第一階段是用單純形方法消去人工變量（如果可能的話），即把人工變量 都變成非基變量，求出原來問題的一個基本可行解。消去人工變量 的一種方法是解下列第一階段問題：兩個階段法 求解（ 116），設(shè)得到的最優(yōu)基本可行解是 ，此時必有下列三種情形之一：n 這時（ 113）無可行解。n 的分量都是非基變量，這時的基變量都 是原來的變量，又知 是（ 116）的基可行解，因此 是（ 113）的一個基可行解。 兩個階段法n 的某些分量是基變量，這時可用主元消去法，把原來變量中的某些非基變量引進基，替換出基變量中的人工變量，再開始兩階段法的第二階段。應(yīng)該指出，為替換出人工變量而采用的主元消去法，在主元的選擇上，并不要求遵守單純形法確定離進基變量的規(guī)則。 兩階段法的第二階段，就是從得到的基可行解出發(fā)，用單純形方法求（ 113）的最優(yōu)解。即在問題（ 116）中去掉人工變量，以第一階段最后的基變量為初始基變量開始迭代。操作上可直接在第一階段的最終單純形表基礎(chǔ)上進行，只需在表中除去人工變量列、恢復(fù)目標(biāo)價值向量為原問題之前的狀況即可。兩個階段法用兩階段法求解下列問題：內(nèi)點法 n 卡瑪卡 （ Karmarkar） 算法 投影尺度法 在大型問題的應(yīng)用中，顯示出能與單純形法競爭的潛力 不能直接用于通常形式的線性規(guī)劃問題 n 原仿射尺度法 (改進的內(nèi)點法 ) 可以直接求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題 理論依據(jù) n 定理 在仿射尺度變換 下， 的正卦限中的點仍變?yōu)檎韵拗械狞c，但其分量值發(fā)生變化。特別地， 的像點為 。n 定理 設(shè)為行滿秩矩陣 ，則向量 在 的零空間上 的正交投影為 基本思想 先找出一個 內(nèi)點可行解 ；從該點出發(fā)，在 可行域的內(nèi)部 尋求一個使 目標(biāo)函數(shù)值下降 的 可行方向 ，沿該方向移動到一個新的 內(nèi)點可行解 ；如此逐步移動，當(dāng)移動到與最優(yōu)解充分接近時，迭代停止。 計算步驟及框圖n 計算步驟 （ P4142） 關(guān)鍵的問題是 ：對于任一迭代點 ，如何求得一個適當(dāng)?shù)?移動方向 ，使 是一個 改進的內(nèi)點可行解 。 利用仿射尺度變換 的逆變換 定理 ， 可找到： , 計算框圖P42 例題及初始內(nèi)點可行解的確定 n 例 用原仿射尺度算法求解如下問題 （ P4344)n 初始內(nèi)點可行解的確定（ P44） 方法：類似于單純形方法的大 M法。 線性規(guī)劃問題的計算機求解 現(xiàn)在已經(jīng)出現(xiàn)了很多能夠求解線性規(guī)劃問題的計算機軟件產(chǎn)品，如 Lindo,Lingo或 Matlab等。下面以 Matlab為背景，介紹如何在Matlab中求解線性規(guī)劃。將模型轉(zhuǎn)換成如下 “標(biāo)準(zhǔn)形式 ”：線性規(guī)劃問題的計算機求解 在上述標(biāo)準(zhǔn)形式中，目標(biāo)函數(shù)求極小，約束條件嚴(yán)格地分為三類：不等式約束且取 “ ”不等號、等式約束及變量取值范圍約束。其中 線性規(guī)劃問題的計算機求解 調(diào)用時需注意以下幾點：（ 1） Matlab提供了一種機制，允許調(diào)用某個函數(shù)時提供 的參數(shù)個數(shù)少于定義該函數(shù)時所定義的參數(shù)個數(shù)。因此，在調(diào)用函數(shù) linprog傳遞參數(shù)時必須按語法指定的順序?qū)?yīng)傳遞，若缺少某些參數(shù)，除非其位于參數(shù)表的尾部，否則調(diào)用時必須以空數(shù)組 “[]”形式占位。（ 2）若問題的模型為目標(biāo)函數(shù)求最（極）大，須先將目標(biāo)函數(shù)轉(zhuǎn)換為最（極）小。 （ 3）代碼中所使用的標(biāo)點分隔符，如逗號、分號、括號等，必須是半角字符。 線性規(guī)劃問題的計算機求解寫出下列問題的 Matlab調(diào)用代碼：分支定界法 與隱枚舉法 n 解決的問題各是什么？n 理論依據(jù) Discussn 基本思想n 計算步驟及框圖 n 計算中的說明n 計算機求解的異同？n 講 P62例 練 P90 7（ 1）分支定界法的計算框圖隱枚舉法的計算框圖表上作業(yè)法 與匈牙利法 n 解決的問題各是什么？n 理論依據(jù) Discussn 基本思想n 計算步驟及框圖 n 計算中的說明 表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)是單純形法。n 結(jié)合算法步驟講 P63例 P67例 . 表上作業(yè)法的計算框圖匈牙利法的計算框圖第三專題 非線性優(yōu)化問題n 非線性優(yōu)化模型的建立n 非線性優(yōu)化模型的尋優(yōu)非線性優(yōu)化模型的建立n 確定決策變量n 確定目標(biāo)（決策準(zhǔn)則）n 確定約束條件實例分析（ 1）投資決策問題（ P88)（ 2）曲線擬合問題 在實驗數(shù)據(jù)處理或統(tǒng)計資料分析中，常常遇到這樣的問題：如何利用有關(guān)變量的實驗數(shù)據(jù)（資料）去確定這些變量間的函數(shù)關(guān)系。例如，已知某物體的溫度 與時間 之間有如下形式的經(jīng)驗函數(shù)關(guān)系： 其中 是待定參數(shù)。通過測試獲得 n 組溫度與時間之間的實驗數(shù)據(jù) ，試確定參數(shù) 使理論曲線盡可能地與 n個測試點擬合。 非線性規(guī)劃問題的共同特征n 都是求一個目標(biāo)函數(shù)在一組約束條件下 的極值問題。n 在目標(biāo)函數(shù)或約束條件中，至少有一個是變量的非線性函數(shù)。非線性規(guī)劃問題n 一般形式：n 向量形式：非線性優(yōu)化問題的尋優(yōu)n 相關(guān)概念及理論n 一維最優(yōu)化方法n 多維無約束最優(yōu)化方法n 多維有約束最優(yōu)化方法非線性規(guī)劃的相關(guān)概念及理論n 一階導(dǎo)數(shù)、二階導(dǎo)數(shù)和 n元函數(shù)的 Taylor公式定義 4 設(shè)函數(shù) 定義在凸集 上，若對任意的 及任意的都有：則稱函數(shù) 為凸集 上的凸函數(shù)．定義 5 嚴(yán)格凸函數(shù)注： 將上述定義中的不等式反向，可以得到凹函數(shù)的定義．凸函數(shù)例 1： 設(shè) 試證明 在上是嚴(yán)格凸函數(shù)．證明 :設(shè) 且 都有：因此 在 上是嚴(yán)格凸函數(shù)．例 2： 試證線性函數(shù)是證明 :設(shè)上的凸函數(shù)．則所以 是凸函數(shù)．類似可以證明 是凹函數(shù)．凸函數(shù)的幾何性質(zhì)對一元函數(shù) 在幾何上表示連接 的線段．表示在點 處的函數(shù)值．所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點的線段總是位于曲線弧的上方．凸函數(shù)的性質(zhì)（１） 設(shè)（２） 設(shè)函數(shù)，是凸集 上的凸函數(shù)，實數(shù) 則 也是 上的凸函數(shù)．是凸集 上的凸實數(shù) 則也是 上的凸函數(shù)．（３） 設(shè) 是凸集 上的凸函數(shù)，是實數(shù)， 則水平集是凸集．下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出水平集是凸集凸函數(shù)的判定定理 1 設(shè) 上，令 則 :(1)是定義在凸集是凸集 上的凸函數(shù)的充要條件是對任意的 一元函數(shù) 為 上的凸函數(shù) .(2)設(shè) 若 在 上為嚴(yán)格凸函數(shù)， 則 在 上為嚴(yán)格凸函數(shù)．該定理的幾何意義是：凸函數(shù)上任意兩點之間的部分是一段向下凸的?。浑A條件定理 設(shè)在凸集 上 可微， 則：在 上為凸函數(shù)的充要條件是對任意的都有：定理 嚴(yán)格凸函數(shù) (充要條件)二階條件定理 3 設(shè)在開凸集 內(nèi) 二階可微，則(1)是 內(nèi)的凸函數(shù)的充要條件為， 在內(nèi)任一點 處， 的海色矩陣 半正定 ,其中：二階條件定理 3 設(shè)在開凸集 內(nèi)(2)若在 內(nèi) 正定 , 則 在 內(nèi)二階可微，則是嚴(yán)格凸函數(shù)．注 : 反之不成立．例：顯然是嚴(yán)格凸的， 但在點 處不是正定的凸規(guī)劃定義 6 設(shè) 為凸集， 為 上的凸函數(shù)，則稱規(guī)劃問題 為凸規(guī)劃問題．定理 4 (1)凸規(guī)劃問題的任一局部極小點 是整體極小點，全體極小點組成凸集．(2)若 是凸集 上的嚴(yán)格凸函數(shù)，且凸規(guī)劃問題 整體極小點存在，則整體極小點是唯一的．非線性規(guī)劃的最優(yōu)性條件 最優(yōu)性條件：是指非線性規(guī)劃模型的最優(yōu)解所要滿足的必要和充分條件。n 無約束最優(yōu)性條件 n 約束最優(yōu)性條件 無約束最優(yōu)性條件一（單）元函數(shù)的最優(yōu)性條件（１） 若（２）為 的局部極小點， 則若 則 為的嚴(yán)格局部極小點；若（３） 為 的局部極小點， 則：多元函數(shù)的一階必要條件（ P106107)定理 1:若 為