【正文】 動(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)軌線(xiàn) n 邊界條件 書(shū) P170173動(dòng)態(tài)規(guī)劃的基本理論n 最優(yōu)性原理 （貝爾曼最優(yōu)化原理） 無(wú)論過(guò)去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。 動(dòng)態(tài)規(guī)劃研究?jī)?nèi)容n 動(dòng)態(tài)規(guī)劃問(wèn)題及相關(guān)概念和理論n 動(dòng)態(tài)規(guī)劃的解法n 動(dòng)態(tài)規(guī)劃的應(yīng)用 動(dòng)態(tài)規(guī)劃研究對(duì)象n 多階段決策問(wèn)題 多階段決策過(guò)程 是指這樣一類(lèi)特殊的活動(dòng)過(guò)程，他們可以 按時(shí)間 （或空間） 順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列 ，所以多階段決策過(guò)程也稱(chēng)為 序貫決策過(guò)程 。否則 ,轉(zhuǎn) step5。（１）最后的兩個(gè)試點(diǎn)的選取方式：例 （ Fibonacci法）用 Fibonacci法求函數(shù) 在區(qū)間上的極小點(diǎn)。如果知道兩個(gè)試點(diǎn) 根據(jù)的大 小關(guān)系， 可以得到縮小的區(qū)間或者 它與 ：搜索區(qū)間長(zhǎng)度的縮短率不是采用 ，而是采用 Fibonacci數(shù)。設(shè) 在 上為下單峰函數(shù)， 即有唯一的極小點(diǎn) 在 左邊 嚴(yán)格下降，在 右邊 嚴(yán)格上升。 若 ，則下一步仍以 為出發(fā)點(diǎn)，沿反方向同樣搜索，直到目標(biāo)函數(shù)上升就停止。n 無(wú)約束最優(yōu)性條件 n 約束最優(yōu)性條件 無(wú)約束最優(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)滿(mǎn)足 的點(diǎn)稱(chēng)為駐點(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： 利用極值條件解下列問(wèn)題：解：令 即：得到駐點(diǎn)：函數(shù) 的海色陣：由此， 在點(diǎn) 處的海色陣依次為：由于矩陣 不定，則 不是極小點(diǎn)．負(fù)定， 則 不是極小點(diǎn)，實(shí)際上它是極大點(diǎn)．正定， 則 是局部極小點(diǎn)．約束最優(yōu)性條件 (p133p136)定義 1:有效約束： 若 (*)中的一個(gè)可行點(diǎn) 使得某個(gè)不等式約束 變成等式， 即則 稱(chēng)為關(guān)于 的有效 (積極）約束．非有效約束： 若對(duì) 則 稱(chēng)為關(guān)于 的非有效 (無(wú)效 ）約束．有效集：定義 2:錐： 的子集， 如果它關(guān)于正的數(shù)乘運(yùn)算是封閉的． 如果錐也是凸集，則稱(chēng)為 凸錐 ．凸錐 關(guān)于加法和正的數(shù)乘運(yùn)算是封閉的．一階必要條件定理:(KuhnTucker一階必要條件)(1951)設(shè) 在（ KT條件）一階必要條件定理 1‘:(KuhnTucker一階必要條件 )（互補(bǔ)松弛條件）例 2： 驗(yàn)證 是否滿(mǎn)足 KuhnTucker條件：試驗(yàn)證最優(yōu)點(diǎn) 為 KT點(diǎn)．解：令所以即：所以： 是 KT點(diǎn)．Lagrange函數(shù)及 KT條件在一定凸性下的最優(yōu)性的充分條件一維最優(yōu)化方法（線(xiàn)性搜索方法）已知 并且求出了 處的可行下降方向從 出發(fā)， 沿方向 求目標(biāo)函數(shù)的最優(yōu)解，或者選取 使得：?jiǎn)栴}描述即設(shè)其最優(yōu)解為 （叫精確步長(zhǎng)因子），所以線(xiàn)性搜索是求解一元函數(shù)的最優(yōu)化問(wèn) 題（也叫一維最優(yōu)化問(wèn)題）。通過(guò)測(cè)試獲得 n 組溫度與時(shí)間之間的實(shí)驗(yàn)數(shù)據(jù) ，試確定參數(shù) 使理論曲線(xiàn)盡可能地與 n個(gè)測(cè)試點(diǎn)擬合。 （ 3）代碼中所使用的標(biāo)點(diǎn)分隔符，如逗號(hào)、分號(hào)、括號(hào)等，必須是半角字符。線(xiàn)性規(guī)劃問(wèn)題的計(jì)算機(jī)求解 在上述標(biāo)準(zhǔn)形式中，目標(biāo)函數(shù)求極小，約束條件嚴(yán)格地分為三類(lèi)：不等式約束且取 “ ”不等號(hào)、等式約束及變量取值范圍約束。 線(xiàn)性規(guī)劃問(wèn)題的計(jì)算機(jī)求解 現(xiàn)在已經(jīng)出現(xiàn)了很多能夠求解線(xiàn)性規(guī)劃問(wèn)題的計(jì)算機(jī)軟件產(chǎn)品，如 Lindo,Lingo或 Matlab等。特別地， 的像點(diǎn)為 。 兩階段法的第二階段，就是從得到的基可行解出發(fā)，用單純形方法求（ 113）的最優(yōu)解。消去人工變量 的一種方法是解下列第一階段問(wèn)題：兩個(gè)階段法 求解（ 116），設(shè)得到的最優(yōu)基本可行解是 ，此時(shí)必有下列三種情形之一：n 這時(shí)（ 113）無(wú)可行解。n 問(wèn)題（ 114）不存在有限最優(yōu)值，在單純形表中， ， 這時(shí) 問(wèn)題（ 113）無(wú)可行解。步驟 2 解 步驟 3 求單純形乘子 ，解使用表格形式的單純形方法使用表格形式的單純形方法 用單純形法解下列問(wèn)題： 初始基可行解的確定n 大 M法 基本思想：在約束中增加人工變量 ，同時(shí)改變目標(biāo)函數(shù) ，加上罰項(xiàng) ，其中 是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過(guò)程中，由于大 的存在，將使人工變量離基。結(jié)論：求解線(xiàn)性規(guī)劃問(wèn)題歸結(jié)為找最優(yōu)基可行 解， 即在其可行域（凸集）的頂點(diǎn)（極點(diǎn)） 中找使目標(biāo)函數(shù)最小的頂點(diǎn)（極點(diǎn)）。該問(wèn)題的可行域?yàn)?空集 ，即無(wú)可行解， max目標(biāo)值在（ 4， 2）點(diǎn)，達(dá)到最大值 14目標(biāo)函數(shù)圖 1可能出現(xiàn)的幾種情況（ 1） 無(wú)窮多最優(yōu)解 (多重最優(yōu)解 )目標(biāo)函數(shù) 以上給出了線(xiàn)性規(guī)劃問(wèn)題的解的概念和定義，它們將有助于用來(lái)分析線(xiàn)性規(guī)劃問(wèn)題的求解過(guò)程。一般基可行解的數(shù)目要小于基解的數(shù)目。基、基向量、基變量基解、基可行解 基解：滿(mǎn)足約束方程組（ 12）且非基變量為 0的解。發(fā)生這種情況往往是建模時(shí)遺漏了某些約束條件所至。 定義 在線(xiàn)性規(guī)劃問(wèn)題的可行域中，使目標(biāo)函數(shù)值達(dá)到最優(yōu)（最大或最小）的可行解稱(chēng)為該問(wèn)題的 最優(yōu)解 。（ 4）當(dāng)決策變量的取值約束為 時(shí)，令 ，則有 。這就同標(biāo)準(zhǔn)形的目標(biāo)函數(shù)的形式一致了。18表 21（ 2）原材料的合理利用問(wèn)題（ P1112）（ 3） 01背包問(wèn)題 (P12) 背包問(wèn)題(P13)(4) 運(yùn)輸問(wèn)題 (5)分派（指派）問(wèn)題 線(xiàn)性的特點(diǎn)n 比例性n 可加性 共同的特征(1) 每一個(gè)線(xiàn)性規(guī)劃問(wèn)題都用一組決策變量 表示某一方案，這組決策變量的值就代表一個(gè)具體方案。22 (P1011)對(duì)于給定的坐標(biāo)系而言，已知第 個(gè)用戶(hù)位置的坐標(biāo)為 。每種食品含有 種基本營(yíng)養(yǎng)成分，第 種食品每一個(gè)單位含有第 種營(yíng)養(yǎng)成分為 。常用的 終止準(zhǔn)則有：（ 1）或或（３）其中 是預(yù)先給定的。收斂速度定義 設(shè)序列 收斂于 而且若 則稱(chēng)序列 為線(xiàn)性收斂的，稱(chēng)為收斂比；若 則稱(chēng)序列 為超線(xiàn)性收斂的。最優(yōu)化問(wèn)題的算法的一般迭代格式給定初始點(diǎn) 令（１）確定 處的可行下降方向（２）確定步長(zhǎng) 使得：（３）令（４）若 滿(mǎn)足某種終止準(zhǔn)則，則停止；否則令 轉(zhuǎn)（１）收斂性 如果一個(gè)算法只有當(dāng)初始點(diǎn)充分接近最優(yōu)解時(shí)，產(chǎn)生的點(diǎn)列才收斂，則稱(chēng)該算法為具有 局部收斂 的算法。當(dāng) 具有連續(xù)的一階偏導(dǎo)數(shù)，令由 Taylor公式：當(dāng) 時(shí)，有所以（ 充分小時(shí)） 是 在 處的一個(gè)下降方向。因此通常構(gòu)造映射 F的關(guān)鍵就在于設(shè)計(jì)一種能從 出發(fā)，確定方向 與步長(zhǎng) 的方法，要求滿(mǎn)足式（ 2）并使整個(gè)序列（或子列）具有收斂性。定義１ .5 范數(shù)：　在 維向量空間 中，定義實(shí)函數(shù) 使其滿(mǎn)足以下三個(gè)條件：（１）對(duì)任意 有在當(dāng)且僅當(dāng)時(shí)（２）對(duì)任意 及實(shí)數(shù) 有（３）對(duì)任意 有則稱(chēng)函數(shù) 為 上的向量范數(shù)。 其中同樣有：嚴(yán)格局部最優(yōu)解。 現(xiàn)代優(yōu)化問(wèn)題（動(dòng)態(tài)優(yōu)化問(wèn)題） 動(dòng)態(tài)規(guī)劃 與最優(yōu)控制問(wèn)題 組合優(yōu)化問(wèn)題最優(yōu)解的相關(guān)定義定義１ .1 可行解 　滿(mǎn)足約束條 ()和 ()的 x稱(chēng)為可行解，也稱(chēng)為可行點(diǎn)或容許點(diǎn)。在 管理科學(xué) 、 運(yùn)籌學(xué) 、 經(jīng)濟(jì)學(xué) 、 最優(yōu)控制 等領(lǐng)域，隨機(jī)規(guī)劃有著廣泛的應(yīng)用。n 第二種是由 查納斯 （ ）和 庫(kù)伯 (）于 1959年提出的 機(jī)會(huì)約束規(guī)劃 ，是在一定的概率意義下達(dá)到最優(yōu)的理論。它不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編碼和 經(jīng)濟(jì)分析 等方面也有新的應(yīng)用。 整數(shù)規(guī)劃與組合最優(yōu)化的關(guān)系　 整數(shù)規(guī)劃與組合最優(yōu)化從廣泛的意義上說(shuō)，兩者的領(lǐng)域是一致的，都是在有限個(gè)可供選擇的方案中，尋找滿(mǎn)足一定標(biāo)準(zhǔn)的最好方案。從最廣泛的意義上說(shuō)，組合規(guī)劃與 整數(shù)規(guī)劃 這兩者的領(lǐng)域是一致的，都是指在有限個(gè)可供選擇的方案的組成集合中，選擇使目標(biāo)函數(shù)達(dá)到極值的最優(yōu)子集。 　n 0—1 規(guī)劃 在整數(shù)規(guī)劃中占有重要地位，一方面因?yàn)樵S多實(shí)際問(wèn)題，例如指派問(wèn)題、選地問(wèn)題、送貨問(wèn)題都可歸結(jié)為此類(lèi)規(guī)劃，另一方面任何有界變量的整數(shù)規(guī)劃都與 0—1 規(guī)劃等價(jià)，用 0—1 規(guī)劃方法還可以把多種非線(xiàn)性規(guī)劃問(wèn)題表示成整數(shù)規(guī)劃問(wèn)題，所以不少人致力于這個(gè)方向的研究。對(duì)每個(gè)衍生問(wèn)題又伴隨一個(gè)比它更易于求解的松弛問(wèn)題（衍生問(wèn)題稱(chēng)為松弛問(wèn)題的源問(wèn)題）。 在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱(chēng)為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，則稱(chēng)為混合整數(shù)規(guī)劃。在線(xiàn)性規(guī)劃問(wèn)題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問(wèn)題，常要求解答必須是整數(shù)。幾何規(guī)劃理論研究和算法軟件開(kāi)發(fā)、發(fā)展都很快，并且在化工、機(jī)械、土木、電氣、核工程等部門(mén)的工程 優(yōu)化設(shè)計(jì) 和企業(yè)管理、資源分配、環(huán)境保護(hù)以及技術(shù)經(jīng)濟(jì)分析等方面都得到廣泛應(yīng)用。幾何規(guī)劃最初是由數(shù)學(xué)家 1961年在研究工程費(fèi)用極小化問(wèn)題基礎(chǔ)上提出的，直到 1967年 《 幾何規(guī)劃 》 一書(shū)出版后才正式定名。這些方法后來(lái)都形成體系，成為近代很活躍的學(xué)科，對(duì)促進(jìn)運(yùn)籌學(xué)、 管理科學(xué) 、 控制論 和 系統(tǒng)工程 等學(xué)科的發(fā)展起了重要作用。最優(yōu)化的發(fā)展簡(jiǎn)史 第二次世界大戰(zhàn) 前后，由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展，許多實(shí)際的最優(yōu)化問(wèn)題已經(jīng)無(wú)法用古典方法來(lái)解決，這就促進(jìn)了 近代最優(yōu)化方法的產(chǎn)生。 最優(yōu)化的發(fā)展簡(jiǎn)史 但是最優(yōu)化方法真正形成為科學(xué)方法則在 17世紀(jì)以后。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制。 最優(yōu)化方法的具體應(yīng)用舉例 ④ 最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的優(yōu)化。最優(yōu)化方法的具體應(yīng)用舉例 ② 最優(yōu)計(jì)劃 :現(xiàn)代國(guó)民經(jīng)濟(jì)或部門(mén)經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂 ,都已開(kāi)始應(yīng)用最優(yōu)化方法。① 最優(yōu)設(shè)計(jì) :世界各國(guó)工程技術(shù)界 ,尤其是飛機(jī)、造船、機(jī)械、建筑等部門(mén)都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題得到解決。 最優(yōu)化方法的目的 在于針對(duì)所研究的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物 達(dá)到最優(yōu)目標(biāo)的方案，稱(chēng)為 最優(yōu)方案 ，搜索最優(yōu)方案的方法，稱(chēng)為 最優(yōu)化方法 。這種方法的數(shù)學(xué)理論，稱(chēng)為 最優(yōu)化理論 。力和財(cái)力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。一個(gè)新的發(fā)展動(dòng)向是最優(yōu)設(shè)計(jì)和 計(jì)算機(jī)輔助設(shè)計(jì) 相結(jié)合。一個(gè)重要的發(fā)