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