【正文】 往往是建模時(shí)遺漏了某些約束條件所至。發(fā)生此情況是因?yàn)槟Ｐ椭谐霈F(xiàn)了相互矛盾的約束條件?；?、基向量、基變量基解、基可行解 基解：滿足約束方程組（ 12）且非基變量為 0的解。 可行基 對(duì)應(yīng)于基可行解的基，稱為可行基。一般基可行解的數(shù)目要小于基解的數(shù)目。n 另外還要說明一點(diǎn)，基解中的非零分量的個(gè)數(shù)小于 m個(gè)時(shí)，該基解是退化解。以上給出了線性規(guī)劃問題的解的概念和定義，它們將有助于用來分析線性規(guī)劃問題的求解過程。例 1 用圖解法求解 因存在 ，所以必須在直角坐標(biāo)的第 1象限內(nèi)作圖，求解。目標(biāo)值在（ 4， 2）點(diǎn)，達(dá)到最大值 14目標(biāo)函數(shù)圖 1可能出現(xiàn)的幾種情況（ 1） 無窮多最優(yōu)解 (多重最優(yōu)解 )目標(biāo)函數(shù) max圖 3 （ 2）無界解圖 4 （ 3）無可行解 當(dāng)存在矛盾的約束條件時(shí)，為無可行域。該問題的可行域?yàn)?空集 ，即無可行解， n 定理 2 線性規(guī)劃問題的基可行解對(duì)應(yīng)線性規(guī)劃 問題可行域（凸集）的頂點(diǎn)（極點(diǎn)）。結(jié)論：求解線性規(guī)劃問題歸結(jié)為找最優(yōu)基可行 解， 即在其可行域（凸集）的頂點(diǎn)（極點(diǎn)） 中找使目標(biāo)函數(shù)最小的頂點(diǎn)（極點(diǎn)）。 它主要通過基可行解的轉(zhuǎn)換完成。步驟 2 解 步驟 3 求單純形乘子 ，解使用表格形式的單純形方法使用表格形式的單純形方法 用單純形法解下列問題： 初始基可行解的確定n 大 M法 基本思想：在約束中增加人工變量 ，同時(shí)改變目標(biāo)函數(shù) ，加上罰項(xiàng) ，其中 是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過程中，由于大 的存在，將使人工變量離基。n 達(dá)到問題（ 114）的最優(yōu)解，且 ，這時(shí)問題（ 113）無可行解。n 問題（ 114）不存在有限最優(yōu)值，在單純形表中， ， 這時(shí) 問題（ 113）無可行解。對(duì)添加了人工變量的線性規(guī)劃問題分兩個(gè)階段計(jì)算。消去人工變量 的一種方法是解下列第一階段問題：兩個(gè)階段法 求解（ 116），設(shè)得到的最優(yōu)基本可行解是 ，此時(shí)必有下列三種情形之一：n 這時(shí)（ 113）無可行解。 兩個(gè)階段法n 的某些分量是基變量，這時(shí)可用主元消去法，把原來變量中的某些非基變量引進(jìn)基，替換出基變量中的人工變量，再開始兩階段法的第二階段。 兩階段法的第二階段，就是從得到的基可行解出發(fā)，用單純形方法求（ 113）的最優(yōu)解。操作上可直接在第一階段的最終單純形表基礎(chǔ)上進(jìn)行，只需在表中除去人工變量列、恢復(fù)目標(biāo)價(jià)值向量為原問題之前的狀況即可。特別地， 的像點(diǎn)為 。 計(jì)算步驟及框圖n 計(jì)算步驟 （ P4142） 關(guān)鍵的問題是 ：對(duì)于任一迭代點(diǎn) ，如何求得一個(gè)適當(dāng)?shù)?移動(dòng)方向 ，使 是一個(gè) 改進(jìn)的內(nèi)點(diǎn)可行解 。 線性規(guī)劃問題的計(jì)算機(jī)求解 現(xiàn)在已經(jīng)出現(xiàn)了很多能夠求解線性規(guī)劃問題的計(jì)算機(jī)軟件產(chǎn)品，如 Lindo,Lingo或 Matlab等。將模型轉(zhuǎn)換成如下 “標(biāo)準(zhǔn)形式 ”：線性規(guī)劃問題的計(jì)算機(jī)求解 在上述標(biāo)準(zhǔn)形式中，目標(biāo)函數(shù)求極小，約束條件嚴(yán)格地分為三類：不等式約束且取 “ ”不等號(hào)、等式約束及變量取值范圍約束。因此，在調(diào)用函數(shù) linprog傳遞參數(shù)時(shí)必須按語法指定的順序?qū)?yīng)傳遞，若缺少某些參數(shù)，除非其位于參數(shù)表的尾部，否則調(diào)用時(shí)必須以空數(shù)組 “[]”形式占位。 （ 3）代碼中所使用的標(biāo)點(diǎn)分隔符，如逗號(hào)、分號(hào)、括號(hào)等，必須是半角字符。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)系。通過測試獲得 n 組溫度與時(shí)間之間的實(shí)驗(yàn)數(shù)據(jù) ，試確定參數(shù) 使理論曲線盡可能地與 n個(gè)測試點(diǎn)擬合。n 在目標(biāo)函數(shù)或約束條件中，至少有一個(gè)是變量的非線性函數(shù)。n 無約束最優(yōu)性條件 n 約束最優(yōu)性條件 無約束最優(yōu)性條件一（單）元函數(shù)的最優(yōu)性條件（１） 若（２）為 的局部極小點(diǎn)， 則若 則 為的嚴(yán)格局部極小點(diǎn)；若（３） 為 的局部極小點(diǎn)， 則：多元函數(shù)的一階必要條件（ P106107)定理 1:若 為 的局部極小點(diǎn)， 且在內(nèi) 一階連續(xù)可導(dǎo)， 則注:(1)僅僅是必要條件，而非充分條件．(2)滿足 的點(diǎn)稱為駐點(diǎn)．駐點(diǎn)分為：極小點(diǎn)，極大點(diǎn)，鞍點(diǎn)．多元函數(shù)的二階充分條件定理 2: 若在 內(nèi) 二階連續(xù)可導(dǎo)， 且 正定 , 則 為嚴(yán)格局部 極小點(diǎn)． 注:如果 負(fù)定 , 則 為嚴(yán)格局部極大點(diǎn)． 二階必要條件和充要條件定理 3:若 為 的局部極小點(diǎn)， 且在內(nèi) 二階連續(xù)可導(dǎo)， 則 半正定．定理 4:設(shè) 在 上是凸函數(shù)且有一階連續(xù)偏導(dǎo)數(shù)， 則 為 的整體極小點(diǎn)的充要條件是例 1： 利用極值條件解下列問題：解：令 即：得到駐點(diǎn)：函數(shù) 的海色陣：由此， 在點(diǎn) 處的海色陣依次為：由于矩陣 不定，則 不是極小點(diǎn)．負(fù)定， 則 不是極小點(diǎn)，實(shí)際上它是極大點(diǎn)．正定， 則 是局部極小點(diǎn)．約束最優(yōu)性條件 (p133p136)定義 1:有效約束： 若 (*)中的一個(gè)可行點(diǎn) 使得某個(gè)不等式約束 變成等式， 即則 稱為關(guān)于 的有效 (積極）約束．非有效約束： 若對(duì) 則 稱為關(guān)于 的非有效 (無效 ）約束．有效集：定義 2:錐： 的子集， 如果它關(guān)于正的數(shù)乘運(yùn)算是封閉的． 如果錐也是凸集，則稱為 凸錐 ．凸錐 關(guān)于加法和正的數(shù)乘運(yùn)算是封閉的．一階必要條件定理:(KuhnTucker一階必要條件)(1951)設(shè) 在（ KT條件）一階必要條件定理 1‘:(KuhnTucker一階必要條件 )（互補(bǔ)松弛條件）例 2： 驗(yàn)證 是否滿足 KuhnTucker條件：試驗(yàn)證最優(yōu)點(diǎn) 為 KT點(diǎn)．解：令所以即：所以： 是 KT點(diǎn)．Lagrange函數(shù)及 KT條件在一定凸性下的最優(yōu)性的充分條件一維最優(yōu)化方法（線性搜索方法）已知 并且求出了 處的可行下降方向從 出發(fā)， 沿方向 求目標(biāo)函數(shù)的最優(yōu)解，或者選取 使得：問題描述即設(shè)其最優(yōu)解為 （叫精確步長因子），所以線性搜索是求解一元函數(shù)的最優(yōu)化問 題（也叫一維最優(yōu)化問題）。搜索區(qū)間：搜索區(qū)間求取方法 n 進(jìn)退法： 一種簡單的確定初始搜索區(qū)間方法 .n 基本思想： 是從一點(diǎn)出發(fā)，按一定步長，試圖確定出函數(shù)值呈現(xiàn) “高 低 高 ”的三點(diǎn)，即 這里 。 若 ，則下一步仍以 為出發(fā)點(diǎn)，沿反方向同樣搜索，直到目標(biāo)函數(shù)上升就停止。這種方法叫進(jìn)退法。設(shè) 在 上為下單峰函數(shù)， 即有唯一的極小點(diǎn) 在 左邊 嚴(yán)格下降，在 右邊 嚴(yán)格上升。 要求最終區(qū)間長度不大于原始區(qū)間長度的 ．解： 函數(shù) 在區(qū)間 上為下單峰函數(shù)，第一次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為迭代次數(shù)０ 否１ 否２ 否３ 否４ 否５ 否６ 是Fibonacci法為了盡快得到結(jié)果，希望區(qū)間縮小的盡量小。如果知道兩個(gè)試點(diǎn) 根據(jù)的大 小關(guān)系， 可以得到縮小的區(qū)間或者 它與 ：搜索區(qū)間長度的縮短率不是采用 ，而是采用 Fibonacci數(shù)。按什么方式取點(diǎn)，求 次函數(shù)值之后， 可最多將多長的原始區(qū)間長度縮小為 設(shè) 為試點(diǎn)個(gè)數(shù)為 最終區(qū)間長度為 時(shí)、 原始區(qū)間 的最大可能長度。（１）最后的兩個(gè)試點(diǎn)的選取方式：例 （ Fibonacci法）用 Fibonacci法求函數(shù) 在區(qū)間上的極小點(diǎn)。第一次迭代：縮短后區(qū)間為第二次迭代 ：縮短后區(qū)間為第三次迭代：縮短后區(qū)間為第四次迭代：縮短后區(qū)間為第五次迭代：取最優(yōu)解Fibonacci方法評(píng)價(jià)Fibonacci法的優(yōu)點(diǎn)（１）如果縮小的區(qū)間包含原來的試點(diǎn)，則該試點(diǎn)在下一步被利用；（２）效率最高，有限個(gè)試點(diǎn)的情況下，可將最優(yōu)點(diǎn)所在的區(qū)間縮小到最?。瓼ibonacci法的缺點(diǎn)（１）搜索前先要計(jì)算搜索的步數(shù)；（２）每次搜索試點(diǎn)計(jì)算的公式不一致．黃金分割法（ ）與 Fibonacci法的區(qū)別與聯(lián)系是什么？請(qǐng)讀者自己寫出算法和程序 二分法若 的導(dǎo)數(shù)存在且容易計(jì)算， 則線性搜索的速度可以得到提高． 下面的二分法每次將區(qū)間縮小至原來的二分之一．設(shè) 為下單峰函數(shù)， 若 在 內(nèi)具有連續(xù)的一階導(dǎo)數(shù)， 且取 若 則 為極小點(diǎn)；若 則以 代替若 則以 代替。FR共軛梯度法收斂定理定理 4:假定 在有界水平集上連續(xù)可微， 且有下界， 那么采用精確線搜索下的FR共軛梯度法產(chǎn)生的點(diǎn)列 至少有一個(gè)聚點(diǎn)是駐點(diǎn)，即：(1) 當(dāng) 是有窮點(diǎn)列時(shí)， 其最后一個(gè)點(diǎn)是的駐點(diǎn)．(2)當(dāng) 是無窮點(diǎn)列時(shí)， 它必有聚點(diǎn)， 且任一聚點(diǎn)都是 的駐點(diǎn)．再開始 FR共軛梯度法算法Step1: 給出Step2: 計(jì)算 如果 停，Step4:否則Step3: 由精確線搜索求 并令：計(jì)算 若令 轉(zhuǎn) Step2。否則 ,轉(zhuǎn) step5。n 動(dòng)態(tài)規(guī)劃的產(chǎn)生 1951年，美國數(shù)學(xué)家貝爾曼（ ）等人，根據(jù)一類多階段決策問題的特點(diǎn)， 把多階段決策問題表示為一系列單階段問題， 即把一個(gè) N變量問題作為一系列的 N個(gè)單變量問題而逐個(gè)加以解決，提出了解決這類問題的 “ 最優(yōu)化原理 ” ，并將其應(yīng)用于很多實(shí)際問題的研究，從而建立了運(yùn)籌學(xué)的一個(gè)分支 —— 動(dòng)態(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃研究內(nèi)容n 動(dòng)態(tài)規(guī)劃問題及相關(guān)概念和理論n 動(dòng)態(tài)規(guī)劃的解法n 動(dòng)態(tài)規(guī)劃的應(yīng)用 動(dòng)態(tài)規(guī)劃研究對(duì)象n 多階段決策問題 多階段決策過程 是指這樣一類特殊的活動(dòng)過程，他們可以 按時(shí)間 （或空間） 順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過程的決策是一個(gè)決策序列 ，所以多階段決策過程也稱為 序貫決策過程 。 動(dòng)態(tài)規(guī)劃問題實(shí)例n 時(shí)間階段的例子 設(shè)備負(fù)荷分配問題 （書 P167例 ）n 空間階段的例子 最短路問題（書 P166例 ） 動(dòng)態(tài)規(guī)劃法窮舉法A B階段 1 C D2 3 4 E F5 G6動(dòng)態(tài)規(guī)劃問題的模型建立n 動(dòng)態(tài)規(guī)劃方法的基本思想 將問題的過程分成幾個(gè)相互聯(lián)系的階段， 通過恰當(dāng)?shù)倪x取變量（包括狀態(tài)變量及決策變量）并定義最優(yōu)值函數(shù) ， 從而把 一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題 ， 從邊界條件開始，逐段遞推尋優(yōu)， 在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，最后 一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。 動(dòng)態(tài)規(guī)劃的基本概念n 階段 n 狀態(tài) n 決策 n 策略 n 狀態(tài)轉(zhuǎn)移方程 n 指標(biāo)函數(shù)和最優(yōu)值函數(shù) n 最優(yōu)策略和最優(yōu)軌線 n 邊界條件 書 P170173動(dòng)態(tài)規(guī)劃的基本理論n 最優(yōu)性原理 （貝爾曼最優(yōu)化原理） 無論過去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。 n 基本方程（或泛函方程） 書 P174176逆序遞推 順序遞推