MBA學(xué)位課程運(yùn)籌學(xué)課件

§2.6運(yùn)輸問(wèn)題及其解法

引例：某公司經(jīng)銷(xiāo)甲產(chǎn)品，它下設(shè)三個(gè)加工廠(chǎng)，每日的產(chǎn)量分別為：A1-40噸，A2-40噸，A3-90噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷(xiāo)售點(diǎn)，各銷(xiāo)售點(diǎn)每日銷(xiāo)量為：B1-30噸，B2-40噸，B3-60噸，B4-20噸,B5-20噸。已知從各工廠(chǎng)到各銷(xiāo)售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為下表所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿(mǎn)足各銷(xiāo)售點(diǎn)需求量的前提下，使總運(yùn)費(fèi)為最少銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn)量（萬(wàn)噸）A171086440A259712640A336581190銷(xiāo)量（萬(wàn)噸）30406020201§2.6運(yùn)輸問(wèn)題及其解法引例：某公司經(jīng)銷(xiāo)甲產(chǎn)品解：這是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，設(shè)Xij表示從Ai調(diào)運(yùn)產(chǎn)品到Bj的數(shù)量（噸），其數(shù)學(xué)模型是：2解：這是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，設(shè)Xij表示從Ai調(diào)運(yùn)產(chǎn)品一、產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題及其解法1.產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特點(diǎn)：特點(diǎn)：（1）其系數(shù)矩陣的結(jié)構(gòu)疏松，且每一列向量 Pij=(0,…1,…1,…0)T=ei+em+j可以證明，r(A)=m+n－1。即有m+n－1個(gè)獨(dú)立方程。于是，該LP問(wèn)題有且僅有m+n－1個(gè)基變量。3一、產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題及其解法1.產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題的數(shù)學(xué)模（2）（產(chǎn)銷(xiāo)平衡條件）

（3）因?yàn)?故必有可行解和最優(yōu)解。

由于上述特點(diǎn)，若按單純形法求解必須增加人工變量，致使計(jì)算量大大增加，故用特殊解法──表上作業(yè)法。2.表上作業(yè)法表上作業(yè)法實(shí)質(zhì)上還是單純形法，但具體計(jì)算和術(shù)語(yǔ)上有所不同。其計(jì)算步驟和方法，我們通過(guò)對(duì)引例的求解過(guò)程說(shuō)明之。（1）用最小元素法確定初始方案（即初始基可行解）

切記在產(chǎn)銷(xiāo)平衡表上必須且只能填寫(xiě)m+n－1個(gè)數(shù)字格4（2）例18（P37）設(shè)某產(chǎn)品從產(chǎn)地A1，A2，A3運(yùn)往銷(xiāo)地B1，B2，B3，B4，B5，運(yùn)量和單位運(yùn)價(jià)如下表所示，問(wèn)如何調(diào)運(yùn)才能使總的運(yùn)費(fèi)最少？銷(xiāo)地運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量（萬(wàn)噸）A171086440A259712640A336581190銷(xiāo)量（萬(wàn)噸）3040602020解：用最小元素法或伏格爾法求得其初始調(diào)運(yùn)方案如下：5例18（P37）設(shè)某產(chǎn)品從產(chǎn)地A1，A2，A3運(yùn)往銷(xiāo)地B1，銷(xiāo)地運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量（萬(wàn)噸）A171086440A259712640A336581190銷(xiāo)量（萬(wàn)噸）3040602020304060202000接下來(lái)我們就要判別這個(gè)調(diào)運(yùn)方案是否是最優(yōu)調(diào)運(yùn)方案？判別的方法同線(xiàn)性規(guī)劃一樣，首先求出空格的檢驗(yàn)數(shù)，由于是最小化問(wèn)題，所以當(dāng)所有空格的檢驗(yàn)數(shù)均小于0時(shí)得到的解為最優(yōu)解。求運(yùn)輸問(wèn)題的空格的檢驗(yàn)數(shù)的方法有閉回路法和位勢(shì)法。6銷(xiāo)地B1B2B3B4B5產(chǎn)量（萬(wàn)（2）用閉回路法或位勢(shì)法求空格的檢驗(yàn)數(shù)1)用閉回路法求檢驗(yàn)數(shù)：首先，每一個(gè)空格有且僅有一個(gè)閉回路，而圈格無(wú)閉回路。

閉回路是以空格為起點(diǎn)，沿同一行或同一列前進(jìn)，遇上圈格可轉(zhuǎn)90度繼續(xù)前進(jìn)，按此方法進(jìn)行下去，直到回到始點(diǎn)的一個(gè)封閉折線(xiàn)。以始點(diǎn)為第0個(gè)點(diǎn)，依次給閉回路上的每一個(gè)頂點(diǎn)編號(hào)。其中奇序數(shù)對(duì)應(yīng)的為奇頂點(diǎn)，偶數(shù)對(duì)應(yīng)的為偶頂點(diǎn)。其次，每一個(gè)空格的檢驗(yàn)數(shù)=奇頂點(diǎn)運(yùn)費(fèi)之和–偶頂點(diǎn)運(yùn)費(fèi)之和。7（2）用閉回路法或位勢(shì)法求空格的檢驗(yàn)數(shù)7

2)用位勢(shì)法求出空格的檢驗(yàn)數(shù)并進(jìn)行最優(yōu)解的判別設(shè)u1,u2,…um;v1,v2,…,vn是對(duì)應(yīng)運(yùn)輸問(wèn)題m+n個(gè)約束條件的對(duì)偶變量，B為含有人工變量的初始可行基，由LP問(wèn)題的對(duì)偶理論知：CBB-1=(u1,u2,…um;v1,v2,…,vn)而每個(gè)決策變量Xij相應(yīng)的系數(shù)向量Pij=ei+em+j，所以CBB-1Pij=ui+vj，于是，檢驗(yàn)數(shù)σij=CBB-1Pij－Cij=(ui+vj)－Cij又各基變量的檢驗(yàn)數(shù)為0，故對(duì)每個(gè)基變量所在的圈格的檢驗(yàn)數(shù)有

即有方程組：共m+n個(gè)未知數(shù)s=m+n－1個(gè)方程82)用位勢(shì)法求出空格的檢驗(yàn)數(shù)并進(jìn)行最優(yōu)解的判別即有顯然上述方程有解，且由于含有一個(gè)自由變量，因此，令任一未知數(shù)為0，就可求出上述方程組的解(ui1,ui2,…uim,vj1,vj2,…vjn)──稱(chēng)為位勢(shì)解。如用位勢(shì)法求引例初始基可行解的檢驗(yàn)數(shù)：銷(xiāo)地運(yùn)價(jià)產(chǎn)地B1B2B3B4B5vjA17108646A259712612A336581110ui-7-3-50-2-8-7-70412-33040602020009顯然上述方程有解，且由于含有一個(gè)自由變量，因此，令第一步：將運(yùn)價(jià)表中增加vj和ui列。

第二步：利用圈格分別算出ui和vj，即令u1=0，然后按ui+vj=Cij(i,jJB)，相繼確定ui，vj的值。第三步：按σij=(ui+vj)－Cij(i,jJN)算出表中各空格（即非基變量）的檢驗(yàn)數(shù)：由于運(yùn)輸問(wèn)題的目標(biāo)函數(shù)是求最小化，故判別最優(yōu)解的準(zhǔn)則是所有的非基變量的檢驗(yàn)數(shù)：σij=CBB-1Pij－Cij≤0因?yàn)棣?5=+4，σ32=+1，σ34=+2均為正數(shù)，所以目前尚未得到最優(yōu)解（其實(shí)只要有一個(gè)正檢驗(yàn)數(shù)，所對(duì)應(yīng)的方案就不是最優(yōu)方案），尚須改進(jìn)。

方案的調(diào)整（即換基迭代）是在閉回路上進(jìn)行10第一步：將運(yùn)價(jià)表中增加vj和ui列。方案的調(diào)整（即

3）在調(diào)運(yùn)平衡表上用閉回路法進(jìn)行調(diào)整，得到新的基可行解（新的調(diào)運(yùn)方案）

i)確定進(jìn)基變量：自上而下，自左向右第一個(gè)正檢驗(yàn)數(shù)相應(yīng)的非基變量（空格）為進(jìn)基變量。

ii)作閉回路：以進(jìn)基變量空格為出發(fā)點(diǎn)，用水平或垂直線(xiàn)向前劃，當(dāng)碰到某一恰當(dāng)數(shù)格轉(zhuǎn)90后，繼續(xù)前進(jìn)，直至回到起始空格止。

iii)確定調(diào)整量=min{奇頂點(diǎn)的調(diào)運(yùn)量}（即閉回路上奇頂點(diǎn)運(yùn)量的最小值為調(diào)整量）

iv)在閉回路上進(jìn)行調(diào)整：對(duì)閉回路上每個(gè)奇頂點(diǎn)的調(diào)運(yùn)量－，對(duì)閉回路上每個(gè)偶頂點(diǎn)（含起始格）的調(diào)運(yùn)量+。調(diào)整后，將閉回路中為0的一個(gè)數(shù)格作為空格（即出基變量）。閉回路外的各調(diào)運(yùn)量不變。這樣便得到新的調(diào)運(yùn)方案（新基可行解)113）在調(diào)運(yùn)平衡表上用閉回路法進(jìn)行調(diào)整，得到新的基可行解（新銷(xiāo)地運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量（萬(wàn)噸）A171086+04-040A259712-06+040A336581190銷(xiāo)量（萬(wàn)噸）304060202020

B1B2B3B4B5產(chǎn)量（萬(wàn)噸）A171086440A259712640A336581190銷(xiāo)量（萬(wàn)噸）304060202020004030602030604002020012銷(xiāo)地B1B2B3B4B5產(chǎn)量（萬(wàn)4）表上作業(yè)法須注意的問(wèn)題：

i)在最終調(diào)運(yùn)表中，若有某個(gè)空格（非基變量）的檢驗(yàn)數(shù)為0時(shí)，則表明該運(yùn)輸問(wèn)題有多重調(diào)運(yùn)方案；

ii)在確定初始方案時(shí)，若某一行的產(chǎn)量與某一列的需求量同時(shí)滿(mǎn)足，這時(shí)也只能劃去一行或一列（絕對(duì)不能同時(shí)把行、列劃去，否則就不滿(mǎn)足圈格=m+n－1個(gè)的要求，即基變量的個(gè)數(shù)永遠(yuǎn)要保持為m+n－1個(gè)）；

iii)在用閉回路法調(diào)整時(shí)，當(dāng)閉回路上奇頂點(diǎn)有幾個(gè)相同的最小值時(shí)，調(diào)整后只能有一個(gè)空格，其余均要保留數(shù)“0”，以保證圈格=m+n－1個(gè)的需要。iv)用最小元素法所得到的初始方案可以不唯一。134）表上作業(yè)法須注意的問(wèn)題：13二、產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法1.數(shù)學(xué)模型：

產(chǎn)大于銷(xiāo)銷(xiāo)大于產(chǎn)14二、產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法1.數(shù)學(xué)模型：然后再用產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題的解法進(jìn)行解之。2.解法思路：將不平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題。即當(dāng)時(shí)，考慮在平衡表中增加一虛擬列，表示增加一個(gè)銷(xiāo)貨點(diǎn)(j=n+1)如倉(cāng)庫(kù)，其銷(xiāo)貨量為，且各運(yùn)價(jià)Cin+1=0；當(dāng)時(shí)，考慮在平衡表中增加一虛擬行，表示增加一個(gè)新產(chǎn)地，且各運(yùn)價(jià)Cm+1j=0。15然后再用產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題的解法進(jìn)行解之。2.解法思路：1例題19（P45）三個(gè)電視機(jī)廠(chǎng)供應(yīng)四個(gè)地區(qū)某種型號(hào)的電視機(jī)，其運(yùn)價(jià)表如下，試求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案？例18下表是一個(gè)運(yùn)輸問(wèn)題的單位運(yùn)價(jià)表。

B1B2B3B4產(chǎn)量（萬(wàn)噸）A11035650A221131270A3781870銷(xiāo)量（萬(wàn)噸）20304060比較總產(chǎn)量和總銷(xiāo)量可知，這是一個(gè)非平衡運(yùn)輸問(wèn)題（屬于產(chǎn)大于銷(xiāo)的情況），為化為平衡運(yùn)輸問(wèn)題，需虛設(shè)一個(gè)銷(xiāo)點(diǎn)B5，其運(yùn)價(jià)為0，其銷(xiāo)量為40。B50004016例題19（P45）三個(gè)電視機(jī)廠(chǎng)供應(yīng)四個(gè)地區(qū)某種型號(hào)銷(xiāo)地廠(chǎng)家B1B2B3B4產(chǎn)量（萬(wàn)臺(tái)）A16312610A2439—12A3910131010最低需求61405最高需求10146不限(12)銷(xiāo)地廠(chǎng)家B1B1`B2B3B4B4`產(chǎn)量（萬(wàn)臺(tái)）A1663126610A24439MM12A3991013101010A4M0M0M1010銷(xiāo)量6414657化為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題有：17銷(xiāo)地B1B2B3B4產(chǎn)量（萬(wàn)臺(tái)）A16三、轉(zhuǎn)運(yùn)問(wèn)題及其解法1.所謂轉(zhuǎn)運(yùn)問(wèn)題是在以下背景產(chǎn)生的：(1)每個(gè)工廠(chǎng)生產(chǎn)的產(chǎn)品不直接運(yùn)到銷(xiāo)地，可以幾個(gè)產(chǎn)地集中一起運(yùn)。(2)運(yùn)往各銷(xiāo)地的物資可先運(yùn)給其中的幾個(gè)銷(xiāo)地，再轉(zhuǎn)運(yùn)給其它銷(xiāo)地。(3)除產(chǎn)、銷(xiāo)地之外，還可以有幾個(gè)中間轉(zhuǎn)運(yùn)站，在產(chǎn)地之間，銷(xiāo)地之間或產(chǎn)銷(xiāo)地之間轉(zhuǎn)運(yùn)。凡類(lèi)似上述情況下的調(diào)運(yùn)物資并使總運(yùn)費(fèi)最小的問(wèn)題統(tǒng)稱(chēng)為轉(zhuǎn)運(yùn)問(wèn)題。2.求解“轉(zhuǎn)運(yùn)問(wèn)題”的思路是把問(wèn)題中所有的產(chǎn)地、中轉(zhuǎn)站和銷(xiāo)地都既看作產(chǎn)地，又都看作銷(xiāo)地，把“轉(zhuǎn)運(yùn)問(wèn)題”變成擴(kuò)大后的產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題處理。18三、轉(zhuǎn)運(yùn)問(wèn)題及其解法1.所謂轉(zhuǎn)運(yùn)問(wèn)題是在以下背景產(chǎn)生的：183.求解“轉(zhuǎn)運(yùn)問(wèn)題”的方法步驟：(1)建立擴(kuò)大的產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題單位運(yùn)價(jià)表。其中1)對(duì)兩地不能直接運(yùn)輸?shù)膯挝贿\(yùn)價(jià)定為M（很大的正數(shù)）3)對(duì)產(chǎn)量列的各數(shù)據(jù)可按下式計(jì)算并填入：Ai的產(chǎn)量=ai+,Tj產(chǎn)量=，Bj的產(chǎn)量=4)對(duì)銷(xiāo)量行的各數(shù)據(jù)可按下式計(jì)算并填入：Aj的產(chǎn)量=,Tj銷(xiāo)量=，Bj的銷(xiāo)量=+bj(2)用表上作業(yè)法進(jìn)行求解2)對(duì)所有中轉(zhuǎn)站Tj的產(chǎn)量和銷(xiāo)量定為相等，設(shè)定為193.求解“轉(zhuǎn)運(yùn)問(wèn)題”的方法步驟：3)對(duì)產(chǎn)量列的各數(shù)據(jù)可按下式例26（P61）已知甲、乙兩處分別有100噸和85噸同種物質(zhì)外運(yùn)，A、B、C三處各需物質(zhì)55，60，70（噸），物質(zhì)可以直接運(yùn)到目的地，也可以經(jīng)某些中轉(zhuǎn)點(diǎn)轉(zhuǎn)運(yùn)，已知各處之間的距離如下表所示，試確定一個(gè)最優(yōu)的調(diào)運(yùn)方案。從到甲乙甲乙010120從到ABC甲乙101514121218從到ABCABC0108140121140從到甲乙ABC產(chǎn)量甲乙ABC010MMM120MMM1015010814121401212181140285270185185185銷(xiāo)量185185240245255再用表上作業(yè)法進(jìn)行求解。20例26（P61）已知甲、乙兩處分別有100噸和85噸同種物質(zhì)§2.7線(xiàn)性目標(biāo)規(guī)劃及其解法前面的線(xiàn)性規(guī)劃問(wèn)題都是處理單個(gè)目標(biāo)的情況，但是在現(xiàn)實(shí)世界中有許多問(wèn)題具有多個(gè)目標(biāo)，這些目標(biāo)的重要性各不相同，往往有不同的量綱，有的目標(biāo)相互依賴(lài)，例如決策者既希望實(shí)現(xiàn)利潤(rùn)最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問(wèn)題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線(xiàn)性時(shí)，我們稱(chēng)其為線(xiàn)性目標(biāo)規(guī)劃問(wèn)題。在這里我們主要討論線(xiàn)性目標(biāo)規(guī)劃問(wèn)題。1、目標(biāo)規(guī)劃模型的建立21§2.7線(xiàn)性目標(biāo)規(guī)劃及其解法前面的線(xiàn)性規(guī)劃問(wèn)引例：對(duì)于生產(chǎn)計(jì)劃問(wèn)題：

甲乙資源限額材料2324工時(shí)3226單位利潤(rùn)43

現(xiàn)在工廠(chǎng)領(lǐng)導(dǎo)要考慮市場(chǎng)等一系列其他因素，提出如下目標(biāo)：（1）根據(jù)市場(chǎng)信息，甲產(chǎn)品的銷(xiāo)量有下降的趨勢(shì)，而乙產(chǎn)品的銷(xiāo)量有上升的趨勢(shì)，故考慮乙產(chǎn)品的產(chǎn)量應(yīng)大于甲產(chǎn)品的產(chǎn)量。（2）盡可能充分利用工時(shí)，不希望加班。（3）應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)30元。現(xiàn)在的問(wèn)題是：在原材料不能超計(jì)劃使用的前提下，如何安排生產(chǎn)才能使上述目標(biāo)依次實(shí)現(xiàn)？22引例：對(duì)于生產(chǎn)計(jì)劃問(wèn)題：現(xiàn)在工廠(chǎng)領(lǐng)導(dǎo)要考慮市場(chǎng)等一系列解：（1）決策變量：仍設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品各為x1和x2偏差變量：對(duì)于每一目標(biāo)，我們引進(jìn)正、負(fù)偏差變量。如對(duì)于目標(biāo)1，設(shè)d1-表示乙產(chǎn)品的產(chǎn)量低于甲產(chǎn)品產(chǎn)量的數(shù)，d1+表示乙產(chǎn)品的產(chǎn)量高于甲產(chǎn)品產(chǎn)量的數(shù)。稱(chēng)它們分別為產(chǎn)量比較的負(fù)偏差變量和正偏差變量。則對(duì)于目標(biāo)1，可將它表示為等式約束的形式-x1+x2+d1--d1+=0(目標(biāo)約束)

同樣設(shè)d2-和d2+分別表示安排生產(chǎn)時(shí)，低于可利用工時(shí)和高于可利用工時(shí)，即加班工時(shí)的偏差變量，則對(duì)目標(biāo)2，有-3x1+2x2+d2--d2+=26對(duì)于目標(biāo)3，設(shè)d3-和d3+分別表示安排生產(chǎn)時(shí)，低于計(jì)劃利潤(rùn)30元和高于計(jì)劃利潤(rùn)30元的偏差變量，有：23解：（1）決策變量：仍設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品各為x1和x24x1+3x2+d3--d3+=30（2）約束條件：有資源約束和目標(biāo)約束資源約束：2x1+3x2≤24目標(biāo)約束：為上述各目標(biāo)中得出的約束（3）目標(biāo)函數(shù)：三個(gè)目標(biāo)依次為：minZ1=d1-，minZ2=d2++d2-，minZ3=d3-

因而該問(wèn)題的數(shù)學(xué)模型可表述如下：minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24s．t．-x1+x2+d1--d1+=0-3x1+2x2+d2--d2+=264x1+3x2+d3--d3+=30244x1+3x2+例20（提級(jí)加新問(wèn)題）某公司的員工工資有四級(jí)，根據(jù)公司的業(yè)務(wù)發(fā)展情況，準(zhǔn)備招收部分新員工，并將部分員工的工資提升一級(jí)。該公司的員工工資及提級(jí)前后的編制表如下，其中提級(jí)后編制是計(jì)劃編制，允許有變化，其中1級(jí)員工中有8%要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下：（1）提級(jí)后在職員工的工資總額不超過(guò)550千元；（2）各級(jí)員工不要超過(guò)定編人數(shù)；（3）為調(diào)動(dòng)積極性，各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的18%；（4）總提級(jí)面不大于20%，但盡可能多提；（5）4級(jí)不足編制人數(shù)可錄用新工人。25例20（提級(jí)加新問(wèn)題）某公司的員工工資有四級(jí)，問(wèn)：應(yīng)如何擬定一具滿(mǎn)意的方案，才能接近上述目標(biāo)？級(jí)別1234工資（千元）8643現(xiàn)有員工數(shù)10204030編制員工數(shù)10225230解：（1）決策變量：設(shè)x1,x2,x3,x4分別表示提升到1，2，3級(jí)和新錄用的員工數(shù)。偏差變量：為各目標(biāo)的正、負(fù)偏差變量。（2）約束條件：1）

提級(jí)后在職員工的工資總額不超過(guò)550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1--d1+=550

26問(wèn)：應(yīng)如何擬定一具滿(mǎn)意的方案，才能接近上述目標(biāo)？級(jí)別123

2）各級(jí)員工不要超過(guò)定編人數(shù)1級(jí)有：10-108%+x1+d2--d2+=102級(jí)有：20-x1+x2+d3--d3+=223級(jí)有：40-x2+x3+d4--d4+=524級(jí)有：30-x3+x4+d5--d5+=303）各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的18%對(duì)2級(jí)有：x1+d6--d6+=2218%對(duì)3級(jí)有：x2+d7--d7+=4018%對(duì)4級(jí)有：x3+d8--d8+=3018%

4）總提級(jí)面人數(shù)不大于20%，但盡可能多提x1+x2+x3+d9--d9+=10020%272）各級(jí)員工不要超過(guò)定編人數(shù)27（3）目標(biāo)函數(shù)：minZ1=d1+minZ2=d2++d3++d4++d5+minZ3=d6-+d7-+d8-minZ4=d9++d9-目標(biāo)規(guī)劃的一般模型見(jiàn)書(shū)本P48

二、目標(biāo)規(guī)劃的解法由于目標(biāo)規(guī)劃有多個(gè)目標(biāo)，各個(gè)目標(biāo)又有相對(duì)不同的重要性，求解時(shí)是首先滿(mǎn)足重要性權(quán)數(shù)大的目標(biāo)，再滿(mǎn)足重要性權(quán)數(shù)次大的目標(biāo)，所以并不能保證所有的目標(biāo)都能達(dá)到，所求的解也不一定是最優(yōu)解，而只能求出滿(mǎn)意解。28（3）目標(biāo)函數(shù)：二、目標(biāo)規(guī)劃的解法28求解目標(biāo)規(guī)劃有圖解法和單純形法，在這里我們主要介紹單純形法。求解目標(biāo)規(guī)劃的單純形法與線(xiàn)性規(guī)劃的單純形法原理基本一致，只是此時(shí)檢驗(yàn)數(shù)行不再是一行，而是變化為一個(gè)檢驗(yàn)數(shù)矩陣。例1例20

用單純形法求解如下線(xiàn)性目標(biāo)規(guī)劃模型minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24加入松馳變量化為標(biāo)準(zhǔn)形

2x1+3x2+x3=24s．t．-x1+x2+d1--d1+=0-3x1+2x2+d2--d2+=264x1+3x2+d3--d3+=30解：取x3，d1-，d2-，d3-為基變量，建立初始單純形表29求解目標(biāo)規(guī)劃有圖解法和單純形法，在這里我們主要介紹單純形法。-1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003[1]232-1342402630x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步驟完全與線(xiàn)性規(guī)劃的單純形法一樣。滿(mǎn)意解的判定：檢驗(yàn)數(shù)矩陣的每一列從上至下第一個(gè)非零元為負(fù)數(shù)，則解為滿(mǎn)意解。迭代的最優(yōu)表如下：30-1-2-11-10Z100000013224x3d3+d2-2-1-1-11-1020Z1Z2Z3100000-106/5-2/5-13/5-10000010-6/52/51-3/57/51/5-11/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而滿(mǎn)意解為：x1=24/5，x2=24/5，d2-=2，d3+=18/5其中第一、三目標(biāo)已達(dá)到最優(yōu)，第二個(gè)目標(biāo)未達(dá)最優(yōu)。目標(biāo)利潤(rùn)Z=4x1+3x2=168/531-10Z1106/5-10-6/57/50018/5d3+d§2.8評(píng)價(jià)相對(duì)有效性的DEA模型DEA模型（也稱(chēng)數(shù)據(jù)包絡(luò)分析）最早由美國(guó)運(yùn)籌學(xué)家A.Charnes等人于1978年提出，在中國(guó)最早由中國(guó)人民大學(xué)的魏權(quán)齡教授于1985向國(guó)內(nèi)介紹。DEA是對(duì)其決策單元（同類(lèi)型的企業(yè)或部門(mén)）的投入規(guī)模、技術(shù)有效性作出評(píng)價(jià)，即對(duì)各同類(lèi)型的企業(yè)投入一定數(shù)量的資金、勞動(dòng)力等資源后，其產(chǎn)出的效益（經(jīng)濟(jì)效益和社會(huì)效益）作一個(gè)相對(duì)有效性評(píng)價(jià)。例如：區(qū)域可持續(xù)發(fā)展的DEA評(píng)價(jià)、企業(yè)營(yíng)銷(xiāo)效果的DEA評(píng)價(jià)、企業(yè)競(jìng)爭(zhēng)能力的DEA評(píng)價(jià)等。為了說(shuō)明DEA模型的建模思路，我們看下面的例子：32§2.8評(píng)價(jià)相對(duì)有效性的DEA模型32例1：某公司有甲、乙、丙三個(gè)企業(yè)，為評(píng)價(jià)這幾個(gè)企業(yè)的生產(chǎn)效率，收集到反映其投入（固定資產(chǎn)年凈值x1、流動(dòng)資金x2、職工人數(shù)x3）和產(chǎn)出（總產(chǎn)值y1、利稅總額y2）的有關(guān)數(shù)據(jù)如下表企業(yè)指標(biāo)甲乙丙x1（萬(wàn)元）41527x2（萬(wàn)元）1545x3（萬(wàn)元）825y1（萬(wàn)元）602224y2（萬(wàn)元）1268由于投入指標(biāo)和產(chǎn)出指標(biāo)都不止一個(gè)，故通常采用加權(quán)的辦法來(lái)綜合投入指標(biāo)值和產(chǎn)出指標(biāo)值。33例1：某公司有甲、乙、丙三個(gè)企業(yè)，為評(píng)價(jià)這對(duì)于第一個(gè)企業(yè)，產(chǎn)出綜合值為60u1+12u2,投入綜合值4v1+15v2+8v3，其中u1u2v1v2v3分別為產(chǎn)出與投入的權(quán)重系數(shù)。我們定義第一個(gè)企業(yè)的生產(chǎn)效率為：總產(chǎn)出與總投入的比即類(lèi)似，可知第二、第三個(gè)企業(yè)的生產(chǎn)效率分別為：34對(duì)于第一個(gè)企業(yè)，產(chǎn)出綜合值為60u1+12u2,投入綜合值4我們限定所有的hj值不超過(guò)1，即，這意味著，若第k個(gè)企業(yè)hk=1，則該企業(yè)相對(duì)于其他企業(yè)來(lái)說(shuō)生產(chǎn)率最高，或者說(shuō)這一生產(chǎn)系統(tǒng)是相對(duì)有效的，若hk<1，那么該企業(yè)相對(duì)于其他企業(yè)來(lái)說(shuō)，生產(chǎn)效率還有待于提高，或者說(shuō)這一生產(chǎn)系統(tǒng)還不是有效的。即max因此，建立第一個(gè)企業(yè)的生產(chǎn)效率最高的優(yōu)化模型如下：這是一個(gè)分式規(guī)劃，需要將它化為線(xiàn)性規(guī)劃才能求解。35我們限定所有的hj值不超過(guò)1，即設(shè)則此分式規(guī)劃可化為如下的線(xiàn)性規(guī)劃其對(duì)偶問(wèn)題為max36設(shè)則此分式規(guī)劃可化為如下的線(xiàn)性規(guī)劃其對(duì)偶問(wèn)題為max36設(shè)vi為第i個(gè)指標(biāo)xi的權(quán)重，ur為第r個(gè)產(chǎn)出yr指標(biāo)的權(quán)重，則第j個(gè)企業(yè)投入的綜合值為，產(chǎn)出的綜合值為其生產(chǎn)效率定義為:于是問(wèn)題實(shí)際上是確定一組最佳的權(quán)變量v1,v2,v3和u1,u2，使第j個(gè)企業(yè)的效率值hj最大。這個(gè)最大的效率評(píng)價(jià)值是該企業(yè)相對(duì)于其他企業(yè)來(lái)說(shuō)不可能更高的相對(duì)效率評(píng)價(jià)值。

我們限定所有的hj值(j=1,2,3)不超過(guò)1，即maxhj≤1。這意味著，若第k個(gè)企業(yè)hk=1，則該企業(yè)相對(duì)于其他企業(yè)來(lái)說(shuō)生產(chǎn)率最高，或者說(shuō)這一系統(tǒng)是相對(duì)而言有效的；若hk<1，那么該企業(yè)相對(duì)于其他企業(yè)來(lái)說(shuō)，生產(chǎn)率還有待于提高，或者說(shuō)這一生產(chǎn)系統(tǒng)還不是有效的。37設(shè)vi為第i個(gè)指標(biāo)xi的權(quán)重，ur為第r個(gè)產(chǎn)出根據(jù)上述分析，可以建立確定任何一個(gè)企業(yè)（如第3個(gè)企業(yè)即丙企業(yè)）的相對(duì)生產(chǎn)率最優(yōu)化模型如下：

1、評(píng)價(jià)決策單元技術(shù)和規(guī)模綜合效率的C2R模型設(shè)有n個(gè)同類(lèi)型的企業(yè)（也稱(chēng)決策單元），對(duì)于每個(gè)企業(yè)都有m種類(lèi)型的“輸入”（表示該單元對(duì)“資源”的消耗）以及p種類(lèi)型的“輸出”（表示該單元在消耗了“資源”之后的產(chǎn)出）。

這n個(gè)企業(yè)及其輸入-輸出關(guān)系如下：

38根據(jù)上述分析，可以建立確定任何一個(gè)企業(yè)（如第3個(gè)……:………:……y1ny2n:ypny1jy2j:ypj……:…y12y22:yp2y11y21:yp1u1u2:up12:p輸出x1nx2n:xmnx1jx2j:xmj……:…x12x22:xm2x11x21:xm1v1v2:vm12:m輸入nj…21部門(mén)指標(biāo)權(quán)數(shù)每個(gè)決策單元的效率評(píng)價(jià)指數(shù)為：

j=1,2,…,n39………y1ny1j…y12y11u11輸x1nx1j…x12而第j0個(gè)決策單元的相對(duì)效率優(yōu)化評(píng)價(jià)模型為：上述模型中xij,yrj為已知數(shù)（可由歷史資料或預(yù)測(cè)數(shù)據(jù)得到），vi,ur為變量。模型的含義是以權(quán)系數(shù)vi,ur為變量，以所有決策單元的效率指標(biāo)hj為約束，以第j0個(gè)決策單元的效率指數(shù)為目標(biāo)。即評(píng)價(jià)第j0個(gè)決策單元的生產(chǎn)效率是否有效，是相對(duì)于其他所有決策單元而言的。

s.t.

vi,ur≥0,i=1,2,…,m;r=1,2,…,p（1）40而第j0個(gè)決策單元的相對(duì)效率優(yōu)化評(píng)價(jià)模型為：上述模這是一個(gè)分式規(guī)劃模型，我們必須將它化為線(xiàn)性規(guī)劃模型才能求解。為此，令

則模型（1）轉(zhuǎn)化為：（2）41這是一個(gè)分式規(guī)劃模型，我們必須將它化為線(xiàn)性規(guī)劃模型才其對(duì)偶問(wèn)題為：（3）寫(xiě)成向量形式有：s.t.無(wú)約束（4）minθ42其對(duì)偶問(wèn)題為：（3）寫(xiě)成向量形式有：s.t.無(wú)約束（4）設(shè)問(wèn)題（4）的最優(yōu)解為λ*，s*-,s*+,θ*，則有如下結(jié)論：（1）若θ*=1，則DMUj0為弱DEA有效（總體）。（2）若θ*=1，且s*-=0,s*+=0，則DMUj0為DEA有效（總體）（3）令0=θ*x0-s*-,0=y0-s*+,則<0,0>為<x0,y0>在有效前沿面上的投影，相對(duì)于原來(lái)的n個(gè)DMU是有效（總體）的。

（4）若存在λj*(j=1,2,…,m),使=1成立，則DMUj0為規(guī)模效益不變；若不存在λj*(j=1,2,…,m)，使=1成立，則<1DMUj0為規(guī)模效益遞增；若不存在λj*(j=1,2,…,m)，使=1成立，則>1DMUj0為規(guī)模效益遞減。

43設(shè)問(wèn)題（4）的最優(yōu)解為λ*，s*-,s*+,θ*，則有如下結(jié)②評(píng)價(jià)第j0決策單元DMU純技術(shù)效率C2GS2模型為：minσs.t.j=1,2,…,n無(wú)約束（5）該模型計(jì)算出的DMU效率是純技術(shù)效率，反映DMU的純技術(shù)效率狀況，稱(chēng)為純技術(shù)效率。設(shè)問(wèn)題（2）的最優(yōu)解為λ*，s*-,s*+,σ*，則有如下對(duì)結(jié)論：44②評(píng)價(jià)第j0決策單元DMU純技術(shù)效率C2GS2模型為：mi（1）若σ*=1，則DMUj0為弱DEA有效（純技術(shù)）。（2）若σ*=1，且s*-=0,s*+=0，則DMUj0為DEA有效（純技術(shù)）。③評(píng)價(jià)第j0決策單元DMU純規(guī)模效率模型為：（6）根據(jù)DEA的理論，總體效率θ*、純技術(shù)效率σ*、純規(guī)模效率s*三個(gè)參數(shù)之間存在（6）式所述的關(guān)系，由（6）可直接計(jì)算DMU的純規(guī)模效率。45（1）若σ*=1，則DMUj0為弱DEA有效（純技術(shù)）。（6P63例28以1997年全部獨(dú)立核算企業(yè)為對(duì)象,對(duì)安徽、江西、湖南和湖北四省進(jìn)行生產(chǎn)水平的比較。投入要素取固定資產(chǎn)凈值年平均余額(億元),流動(dòng)資金年平均余額及從業(yè)人員(萬(wàn)人),產(chǎn)出要素取總產(chǎn)值(億元)和利稅總額(億元).安徽江西湖南湖北固定資產(chǎn)932.66583.08936.841306.56流動(dòng)資金980.45581.64849.311444.30從業(yè)人員401.8294.2443.20461.00利稅總額179.2949.76144.20181.41總產(chǎn)值2196.09930.221659.042662.21全要素相對(duì)生產(chǎn)率(即DEA評(píng)價(jià)值)1.0000.71400.92851.000排序132146P63例28以1997年全部獨(dú)立核算企業(yè)為對(duì)象,對(duì)安徽、1.建立評(píng)價(jià)湖南省的DEA模型如下求解結(jié)果為:調(diào)整方案為:輸入調(diào)整前輸入調(diào)整后輸出調(diào)整前輸出調(diào)整后936.84936.84*0.9285-119.71=750.15144.20144.20849.31849.31*0.9285=788.581659.041659.04+107.24=1766.28443.20443.2*0.9285-88.17=323.34471.建立評(píng)價(jià)湖南省的DEA模型如下求解結(jié)果為:調(diào)整方案為:第二章整數(shù)線(xiàn)性規(guī)劃問(wèn)題及其解法在上一章討論的LP問(wèn)題中,對(duì)決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值,即可以是正分?jǐn)?shù)或正小數(shù)。然而在許多經(jīng)濟(jì)管理的實(shí)際問(wèn)題中，決策變量只有非負(fù)整數(shù)才有實(shí)際意義。對(duì)求整數(shù)最優(yōu)解的問(wèn)題，稱(chēng)為整數(shù)規(guī)劃(IntegerProgramming)(簡(jiǎn)記為IP)。又稱(chēng)約束條件和函數(shù)均為線(xiàn)性的IP為整數(shù)線(xiàn)性規(guī)劃(IntegerLinearProgramming)(簡(jiǎn)記為ILP)。根據(jù)變量取整數(shù)的情況,將整數(shù)規(guī)劃分為：（1）純整數(shù)規(guī)劃，所有變量都取整數(shù).（2）混合整數(shù)規(guī)劃，一部分變量取整數(shù),一部分變量取實(shí)數(shù)（3）0-1整數(shù)規(guī)劃,所有變量均取0或1求解整數(shù)規(guī)劃常用的算法有分枝定界法、割平面法,求解0-1的還有隱枚舉法、匈牙利法。48第二章整數(shù)線(xiàn)性規(guī)劃問(wèn)題及其解法在上一章討一、整數(shù)線(xiàn)性規(guī)劃模型的建立例題2P72某單位有5個(gè)擬選擇的投資項(xiàng)目，其所需投資額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系，A、C、E之間必須選擇一項(xiàng)且僅需選擇一項(xiàng)；B和D之間需選擇也僅需選擇一項(xiàng)；又由于C和D兩項(xiàng)目密切相關(guān)，C的實(shí)施必須以D的實(shí)施為前提條件，該單位共籌集資金15萬(wàn)元，問(wèn)應(yīng)該選擇哪些項(xiàng)目投資，使期望收益最大？項(xiàng)目所需投資額（萬(wàn)元）期望收益（萬(wàn)元）A610B48C27D46E5949一、整數(shù)線(xiàn)性規(guī)劃模型的建立例題2P72某單位有5個(gè)擬選解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng)：x1+x3+x5=1項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件：x3

x4項(xiàng)目B、D之間必須且只需選擇一項(xiàng)：x2+x4=1歸納起來(lái)，其數(shù)學(xué)模型為：50解：決策變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條由此，ILP問(wèn)題數(shù)學(xué)模型的一般形式為：求一組變量X1,X2,…,Xn，使

此例還表明，利用0-1變量處理一類(lèi)“可供選擇條件”的問(wèn)題非常簡(jiǎn)明方便。下面再進(jìn)一步分別說(shuō)明對(duì)0-1變量的應(yīng)用。假定現(xiàn)有m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為：求一組決策變量X1,X2,…,Xn，使 （3.1）（3.2）（3.3）51由此，ILP問(wèn)題數(shù)學(xué)模型的一般形式為：求一組變量X1,X2,1.對(duì)可供項(xiàng)目的選擇（1）如果在可供選擇的前k(kn)個(gè)項(xiàng)目中，必須且只能選擇一項(xiàng)，則在(3.2)中加入新的約束條件：（2）如果可供選擇的k(kn)個(gè)項(xiàng)目是相互排斥的，則在(3.2)中加入新的約束條件：同時(shí)它還表示在第k個(gè)項(xiàng)目中至多只能選擇一項(xiàng)投資。（3）如果在可供選擇的k(kn)個(gè)項(xiàng)目中，至少應(yīng)選擇一項(xiàng)投資，則在(3.2)中加入新的約束條件：521.對(duì)可供項(xiàng)目的選擇（1）如果在可供選擇的前k(kn)個(gè)（4）如果項(xiàng)目j的投資必須以項(xiàng)目i的投資為前提，則可在(3.2)中加入新的約束條件：XjXi

（5）如果項(xiàng)目i與項(xiàng)目j要么同時(shí)被選中，要么同時(shí)不被選中，則在(3.2)中加入新的約束條件：Xj=Xi(ij)2.對(duì)可供資源的選擇（1）如果對(duì)第r種資源br與第t種資源bt的投資是相互排斥的，即只允許對(duì)資源br與bt中的一種進(jìn)行投資，則可將(3.2)的第r個(gè)和第t個(gè)約束條件改寫(xiě)為：53（4）如果項(xiàng)目j的投資必須以項(xiàng)目i的投資為前提，則可在(3.

①

②其中y為新引進(jìn)的0-1變量，M為充分大正數(shù)。易見(jiàn)，當(dāng)y=0時(shí)，①式就是原來(lái)的第r個(gè)約束條件，具有約束作用。此時(shí)對(duì)②式而言，無(wú)論Xj為何值都成立，毫無(wú)約束作用，這就使問(wèn)題僅允許第r種資源進(jìn)行投資。當(dāng)y=1時(shí)，②式對(duì)Xj起了約束作用，而①式成了多余的條件。到底是滿(mǎn)足①還是②，則視問(wèn)題在求出最優(yōu)解后，y為0還是1而定。54 ①其（2）如果問(wèn)題是要求在前m個(gè)約束條件中至少滿(mǎn)足k(1<k<m)個(gè)，則可將(3.2)中的原約束條件修改為：其中M為充分大的正數(shù)，k為整數(shù)。整數(shù)規(guī)劃問(wèn)題的建模與線(xiàn)性規(guī)劃問(wèn)題的建?；疽恢拢园匆韵?個(gè)步驟進(jìn)行：（1）確定決策變量；（2）確定目標(biāo)函數(shù)；（3）確定約束條件。但0-1規(guī)劃要注意變量的選擇和約束條件的選擇。55（2）如果問(wèn)題是要求在前m個(gè)約束條件中至少滿(mǎn)足k(1<k<m例8（P91）（倉(cāng)庫(kù)選用問(wèn)題）某決策者擬在n個(gè)倉(cāng)庫(kù)中決定租用其中的幾個(gè)，以滿(mǎn)足m個(gè)銷(xiāo)售點(diǎn)對(duì)貨物的需要。每個(gè)銷(xiāo)售點(diǎn)的需要量bj(j=1,2,…m)必須從租用的倉(cāng)庫(kù)中得到滿(mǎn)足，且只能從租用的倉(cāng)庫(kù)得到滿(mǎn)足。而對(duì)租用的倉(cāng)庫(kù)必須支付固定的運(yùn)營(yíng)費(fèi)（如租金、管理費(fèi)等），同時(shí)，還應(yīng)決定從租用的哪個(gè)倉(cāng)庫(kù)中運(yùn)多少貨物到銷(xiāo)售點(diǎn)處，以使總的費(fèi)用為最小。

解：分析，該問(wèn)題是由一個(gè)倉(cāng)庫(kù)選用和一個(gè)運(yùn)輸問(wèn)題綜合而成。設(shè)gi表示租用倉(cāng)庫(kù)i的固定運(yùn)營(yíng)費(fèi)（即固定成本）；di表示倉(cāng)庫(kù)i的允許容量；Cij表示從倉(cāng)庫(kù)i運(yùn)送貨物到銷(xiāo)售點(diǎn)j處的單位費(fèi)用（即可變成本）56例8（P91）（倉(cāng)庫(kù)選用問(wèn)題）解：分析，該問(wèn)題是由一個(gè)倉(cāng)庫(kù)選（1）決策變量：xij表示從租用的倉(cāng)庫(kù)i運(yùn)送給銷(xiāo)售點(diǎn)j的貨物量；（2）約束條件：此處的約束條件只有運(yùn)輸問(wèn)題的產(chǎn)量約束和銷(xiāo)量約束，表示為（3）目標(biāo)函數(shù)：總費(fèi)用包括兩部分，一是倉(cāng)庫(kù)租用費(fèi)用，二是運(yùn)輸費(fèi)用，因此總費(fèi)用表示為57（1）決策變量：xij表示從租用的倉(cāng)庫(kù)i運(yùn)送給銷(xiāo)售點(diǎn)j的貨物求解ILP問(wèn)題方法的思考：1）“舍入取整”法：即先不考慮整數(shù)性約束，而去求解其相應(yīng)的LP問(wèn)題（稱(chēng)為松馳問(wèn)題），然后將得到的非整數(shù)最優(yōu)解用“舍入取整”的方法。這樣能否得到整數(shù)最優(yōu)解？否！這是因?yàn)椤吧崛肴≌钡慕庖话悴皇窃瓎?wèn)題的最優(yōu)解，甚至是非可行解。但在處理個(gè)別實(shí)際問(wèn)題時(shí)，如果允許目標(biāo)函數(shù)值在某一誤差范圍內(nèi)，有時(shí)也可采用“舍入取整”得到的整數(shù)可行解作為原問(wèn)題整數(shù)最優(yōu)解的近似。這樣可節(jié)省求解的人力、物力和財(cái)力。二、整數(shù)線(xiàn)性規(guī)劃模型的求解58求解ILP問(wèn)題方法的思考：1）“舍入取整”法：即嚴(yán)格地說(shuō)，IP是個(gè)非線(xiàn)性規(guī)劃問(wèn)題。這是因?yàn)镮P的可行解集是由一些離散的非負(fù)整數(shù)所組成，不是一個(gè)凸集。迄今為止，求解IP問(wèn)題尚無(wú)統(tǒng)一的有效算法。但常用的有求解一般整數(shù)規(guī)劃的分枝定界法、割平面法和求解0-1規(guī)劃的隱枚舉法。在這里我們只介紹分枝定界法和隱枚舉法。

1、整數(shù)規(guī)劃的分枝定界法（1）分枝定界法的基本思想P76（2）分枝定界法的求解步驟P76例求解下列整數(shù)規(guī)劃問(wèn)題：59嚴(yán)格地說(shuō)，IP是個(gè)非線(xiàn)性規(guī)劃問(wèn)題。這是因?yàn)镮P的可解：首先不考慮整數(shù)約束，相應(yīng)的問(wèn)題稱(chēng)為原問(wèn)題的松馳問(wèn)題松馳問(wèn)題（0）用單純形法求得其最優(yōu)解為x1=2.5，x2=2.5，z=87.5具體求解過(guò)程見(jiàn)P76-78，其求解框圖如下：60解：首先不考慮整數(shù)約束，相應(yīng)的問(wèn)題稱(chēng)為原問(wèn)題的松馳問(wèn)題松馳問(wèn)問(wèn)題（0）x1=2.5，x2=2.5z=87.5問(wèn)題（1）x1=2，x2=2.67z=83.3問(wèn)題（2）x1=3，x2=1.75z=80問(wèn)題（3）x1=2，x2=2z=70問(wèn)題（4）x1=1，x2=3z=75問(wèn)題（0）x1=3.5，x2=1z=72.5問(wèn)題（6）無(wú)可行解61問(wèn)題（0）問(wèn)題（1）問(wèn)題（2）

0-1規(guī)劃的隱枚舉法是一種特殊的分枝定界法，其基本思想是利用變量只能為0或1兩個(gè)值的特性，進(jìn)行分枝定界，以減少枚舉而達(dá)到求出最優(yōu)解之目的。該法適用于任何0-1規(guī)劃問(wèn)題的求解，包括指派問(wèn)題。2、0-1規(guī)劃的隱枚舉法

隱枚舉法首先要將問(wèn)題化為規(guī)范形。（

1）0-1規(guī)劃的規(guī)范形為620-1規(guī)劃的隱枚舉法是一種特殊的分枝定界法，其基本思（2）化規(guī)范形的方法：1）如果目標(biāo)函數(shù)為求極小值，則對(duì)目標(biāo)函數(shù)兩邊乘以-1，化為求極大值；2）若目標(biāo)函數(shù)中某變量xj的系數(shù)cj>0，則令xj=1-yj3）如果約束條件是“”形，則可兩邊乘-1，改為“”形；4）若某個(gè)約束條件為“=”形，則化為兩個(gè)“”的不等式,如63（2）化規(guī)范形的方法：63（3）隱枚舉法的基本思想見(jiàn)P83例1、用隱枚舉法求解下列0-1規(guī)劃解：令x1=1-y1,x3=1-y3,x5=1-y5,x2=y2,x4=y4化為規(guī)范形得：64（3）隱枚舉法的基本思想見(jiàn)P83例1、用隱枚舉法求其求解過(guò)程如下圖所示：y4=0y5=101234567810911121314Z=11y3=1y3=0y4=1y5=1y5=0y2=1y2=0y4=0y4=1y5=0y1=0y1=1可行解z=3可行解z=1可行解z=2不可行子域不可行子域可行解z=6可行解z=2不可行子域由此可知，最優(yōu)解為x3=x4=x5=1,x1=x2=0,maxz=665其求解過(guò)程如下圖所示：y4=0y5=101234567810三.指派問(wèn)題及其解法當(dāng)指派第i人去完成第j項(xiàng)工作否則引例：假設(shè)有4個(gè)人去完成4項(xiàng)任務(wù)，每個(gè)人由于技術(shù)、專(zhuān)長(zhǎng)不同，完成任務(wù)的時(shí)間如下表，且規(guī)定每人只能做一項(xiàng)工作，每項(xiàng)工作只能由一人完成，問(wèn)應(yīng)如何分配任務(wù)使總費(fèi)用最小？66三.指派問(wèn)題及其解法當(dāng)指派第i人去完成第j項(xiàng)工作6767諸如此類(lèi)，有n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)，但由于每人的技術(shù)專(zhuān)長(zhǎng)不同，完成任務(wù)的效率(所費(fèi)時(shí)間不同，為使完成n項(xiàng)任務(wù)的總效率最高（即所需總時(shí)間最少），應(yīng)如何指派（分派）人員的問(wèn)題統(tǒng)稱(chēng)為指派（分派）問(wèn)題。一、指派問(wèn)題的數(shù)學(xué)模型及其特點(diǎn)1.數(shù)學(xué)模型：68諸如此類(lèi)，有n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任2.特點(diǎn)（1）給定一個(gè)指派問(wèn)題時(shí)，必須給出效率矩陣（系數(shù)矩陣）C=(Cij)nxn,且Cij0，因此必有最優(yōu)解()。（2）指派問(wèn)題是一種特殊的平衡運(yùn)輸問(wèn)題，由于模型結(jié)構(gòu)的特殊性（看作每個(gè)產(chǎn)地的產(chǎn)量均為1，每個(gè)銷(xiāo)地的銷(xiāo)量均為1），故可用更為簡(jiǎn)便的匈牙利算法進(jìn)行求解。二、指派問(wèn)題的解法——匈牙利法

匈牙利法是求解指派問(wèn)題的一種好算法，它只能求解目標(biāo)函數(shù)為最小化的情況，它由匈牙利數(shù)學(xué)家柯尼格（D.Konig)提出，因此而得名。692.特點(diǎn)（2）指派問(wèn)題是一種特殊的平衡運(yùn)輸問(wèn)題，由于模型結(jié)構(gòu)1.匈牙利法的基本思想是：對(duì)同一項(xiàng)工作（任務(wù)）j來(lái)說(shuō)，同時(shí)提高或降低每人相同的效率（常數(shù)ti），不影響其最優(yōu)指派；同樣，對(duì)同一個(gè)人i來(lái)說(shuō)，完成各項(xiàng)工作的效率都提高或降低相同的效率（常數(shù)di），也不影響其最優(yōu)指派，因此可得到新的效率矩陣(bij)nxn，其中bij=Cij+ti+dj（對(duì)所有的i,j）701.匈牙利法的基本思想是：對(duì)同一項(xiàng)工作（任務(wù)）j來(lái)說(shuō)這說(shuō)明Z與Z同時(shí)達(dá)到最小值。因而最優(yōu)解相同。故指派問(wèn)題有以下性質(zhì)：

若從效率矩陣(Cij)nxn的一行（列）各元素中分別減去該行（列）的最小元素，得到的新效率矩陣(bij)nxn不改變?cè)概蓡?wèn)題的最優(yōu)解。2.匈牙利法的計(jì)算步驟見(jiàn)P88-89三、關(guān)于求最大化的指派問(wèn)題71這說(shuō)明Z與Z同時(shí)達(dá)到最小值。因而最優(yōu)解相同。故對(duì)于求最大化的指派問(wèn)題（即求）,可采用構(gòu)造新的效率矩陣(M－Cij)nxn，其中M=max{Cij}，（顯然M－Cij0），將其轉(zhuǎn)化為

求所得到的最優(yōu)解就是原問(wèn)題的最優(yōu)解。事實(shí)上

由于nM為常數(shù)，因此，使Z取得最小的最優(yōu)解就是使Z取得最大的最優(yōu)解。72對(duì)于求最大化的指派問(wèn)題（即求4.以上討論的指派問(wèn)題是效率矩陣的行數(shù)等于列數(shù)，即m+n的情況。當(dāng)mn時(shí)，則可用增加虛設(shè)的零元數(shù)行（列）使效率矩陣變成方陣后，再用匈牙利法求解。

5.指派問(wèn)題必有最優(yōu)解，但可以不唯一。n-m行當(dāng)m<n時(shí)m-n列當(dāng)m>n時(shí)734.以上討論的指派問(wèn)題是效率矩陣的行數(shù)等于列數(shù)，即m+n的情第四章動(dòng)態(tài)規(guī)劃

（DynamicProgramming)

動(dòng)態(tài)規(guī)劃是1951年由美國(guó)數(shù)學(xué)家貝爾曼（RichardBellman)提出，它是解決一類(lèi)多階段決策問(wèn)題的優(yōu)化方法，也是考察問(wèn)題的一種途徑，而不是一種算法（如LP單純形法）。因此它不象LP那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。動(dòng)態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法。如果一個(gè)問(wèn)題可將其過(guò)程劃分為若干個(gè)相互聯(lián)系的階段問(wèn)題，且它的每一階段都需進(jìn)行決策，則這類(lèi)問(wèn)題均可用動(dòng)態(tài)規(guī)劃方法進(jìn)行求解。根據(jù)多階段決策過(guò)程的時(shí)序和決策過(guò)程的演變，動(dòng)態(tài)規(guī)劃方法有以下四種類(lèi)型：離散確定型、離散隨機(jī)型、連續(xù)確定型和連續(xù)隨機(jī)型。返回74第四章動(dòng)態(tài)規(guī)劃

（DynamicProgrammi§1動(dòng)態(tài)規(guī)劃的基本概念和最優(yōu)化原理一、引例（最短路問(wèn)題）

假如上圖是一個(gè)線(xiàn)路網(wǎng)絡(luò)，兩點(diǎn)之間連線(xiàn)上的數(shù)字表示兩點(diǎn)間的距離（或費(fèi)用），我們的問(wèn)題是要將貨物從A地運(yùn)往E地，中間通過(guò)B、C、D三個(gè)區(qū)域，在區(qū)域內(nèi)有多條路徑可走，現(xiàn)求一條由A到E的線(xiàn)路，使總距離最短（或總費(fèi)用最小）。AB1B2B3C1C2C3D1D2E2437463242653463333475§1動(dòng)態(tài)規(guī)劃的基本概念和最優(yōu)化原理一、引例（最短路問(wèn)題）

將該問(wèn)題劃分為4個(gè)階段的決策問(wèn)題，即第一階段為從A到Bj（j=1，2，3），有三種決策方案可供選擇；第二階段為從Bj到Cj（j=1,2,3），也有三種方案可供選擇；第三階段為從Cj到Dj(j=1,2)，有兩種方案可供選擇；第四階段為從Dj到E，只有一種方案選擇。如果用完全枚舉法，則可供選擇的路線(xiàn)有3×3×2×1=18（條），將其一一比較才可找出最短路線(xiàn)：A→B1→C2→D3→E其長(zhǎng)度為12。顯然，這種方法是不經(jīng)濟(jì)的，特別是當(dāng)階段數(shù)很多，各階段可供的選擇也很多時(shí)，這種解法甚至在計(jì)算機(jī)上完成也是不現(xiàn)實(shí)的。由于我們考慮的是從全局上解決求A到E的最短路問(wèn)題，而不是就某一階段解決最短路線(xiàn)，因此可考慮從最后一階段開(kāi)始計(jì)算，由后向前逐步推至A點(diǎn)：76將該問(wèn)題劃分為4個(gè)階段的決策問(wèn)題，即第一階段為從A第四階段，由D1到E只有一條路線(xiàn)，其長(zhǎng)度f(wàn)4（D1）=3，同理f4（D2）=4。第三階段，由Cj到Di分別均有兩種選擇，即，決策點(diǎn)為D1,決策點(diǎn)為D1，決策點(diǎn)為D277第四階段，由D1到E只有一條路線(xiàn)，其長(zhǎng)度f(wàn)4（D1）=3，，第二階段，由Bj到Cj分別均有三種選擇，即：決策點(diǎn)為C2

決策點(diǎn)為C1或C2決策點(diǎn)為C2

78第二階段，由Bj到Cj分別均有三種選擇，即：決策點(diǎn)為C2第一階段，由A到B，有三種選擇，即：決策點(diǎn)為B3f1（A）=15說(shuō)明從A到E的最短距離為12，最短路線(xiàn)的確定可按計(jì)算順序反推而得。即A→B3→C2→D2→E上述最短路線(xiàn)問(wèn)題的計(jì)算過(guò)程，也可借助于圖形直觀的表示出來(lái)：79第一階段，由A到B，有三種選擇，即：決策點(diǎn)為B3

圖中各點(diǎn)上方框的數(shù)，表示該點(diǎn)到E的最短距離。圖中紅箭線(xiàn)表示從A到E的最短路線(xiàn)。從引例的求解過(guò)程可以得到以下啟示：

①對(duì)一個(gè)問(wèn)題是否用上述方法求解，其關(guān)鍵在于能否將問(wèn)題轉(zhuǎn)化為相互聯(lián)系的決策過(guò)程相同的多個(gè)階段決策問(wèn)題。

AB1B2B3C1C2C3D1D2E243746324265346333343467699111280圖中各點(diǎn)上方框的數(shù)，表示該點(diǎn)到E的最短距離。圖中紅箭1、所謂多階段決策問(wèn)題是：把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程，也稱(chēng)為序貫決策過(guò)程。如下圖所示：

②在處理各階段決策的選取上，不僅只依賴(lài)于當(dāng)前面臨的狀態(tài)，而且還要注意對(duì)以后的發(fā)展。即是從全局考慮解決局部（階段）的問(wèn)題。③各階段選取的決策，一般與“時(shí)序”有關(guān)，決策依賴(lài)于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，整個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)，故有“動(dòng)態(tài)”含義。因此，把這種方法稱(chēng)為動(dòng)態(tài)規(guī)劃方法。④決策過(guò)程是與階段發(fā)展過(guò)程逆向而行。811、所謂多階段決策問(wèn)題是：把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈

2、多階段決策問(wèn)題的典型例子：企業(yè)在生產(chǎn)過(guò)程中，由于需求是隨著時(shí)間變化的因素，因此企業(yè)為了獲得全年最佳經(jīng)濟(jì)效益，就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季的根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。某種機(jī)器，可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷下生產(chǎn)的產(chǎn)量多，但每生產(chǎn)一個(gè)階段后機(jī)器的完好率低；低負(fù)荷下生產(chǎn)時(shí)的情況則相反。現(xiàn)在需要安排該種機(jī)器在多個(gè)階段內(nèi)的生產(chǎn)，問(wèn)應(yīng)該如何決定各階段中機(jī)器的使用，使整個(gè)計(jì)劃期內(nèi)的總產(chǎn)量最大。某臺(tái)設(shè)備，例如汽車(chē)，剛買(mǎi)來(lái)時(shí)故障少，耗油低，出車(chē)時(shí)間長(zhǎng)，處理價(jià)值和經(jīng)濟(jì)效益高。隨著使用時(shí)間的增加則變?yōu)楣收隙啵挠透?，維修費(fèi)用增加，經(jīng)濟(jì)效益差。使用時(shí)間愈長(zhǎng)，處理價(jià)值也愈低。另外，每次更新都要付出更新費(fèi)用。因此，應(yīng)當(dāng)如何決定設(shè)備的使用年限，使總的效益最佳。822、多階段決策問(wèn)題的典型例子：企業(yè)在生產(chǎn)過(guò)程中，由于3、動(dòng)態(tài)規(guī)劃方法的特點(diǎn)

優(yōu)點(diǎn)：①許多問(wèn)題用動(dòng)態(tài)規(guī)劃研究求解比線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃更有效，特別是離散性問(wèn)題，解析數(shù)學(xué)無(wú)用武之地，而動(dòng)態(tài)規(guī)劃成為得力工具；②某些情況下，用動(dòng)態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計(jì)算機(jī)給出求其數(shù)值解的方法。

缺點(diǎn)：①?zèng)]有統(tǒng)一的處理方法，求解時(shí)要根據(jù)問(wèn)題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此，實(shí)踐經(jīng)驗(yàn)及創(chuàng)造性思維將起重要的引導(dǎo)作用。②“維數(shù)障礙”：當(dāng)變量個(gè)數(shù)太多時(shí)，由于計(jì)算機(jī)內(nèi)存和速度的限制導(dǎo)致問(wèn)題無(wú)法解決。有些問(wèn)題由于涉及的函數(shù)沒(méi)有理想的性質(zhì)使問(wèn)題只能用動(dòng)態(tài)規(guī)劃描述，而不能用動(dòng)態(tài)規(guī)劃方法求解。833、動(dòng)態(tài)規(guī)劃方法的特點(diǎn)

優(yōu)點(diǎn)：①許多問(wèn)題用動(dòng)態(tài)規(guī)劃研究二、動(dòng)態(tài)規(guī)劃的基本概念

1、階段。階段的劃分，一般根據(jù)時(shí)序和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為階段決策的過(guò)程。描述階段的變量稱(chēng)為階段變量，常用自然數(shù)k表示。如引例可劃分為4個(gè)階段求解，k=1，2，3，4。2、狀態(tài)。狀態(tài)就是階段的起始位置。它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。（1）狀態(tài)變量和狀態(tài)集合。描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量。它可用一個(gè)數(shù)、一組數(shù)或一向量（多維情形）來(lái)描述，常用Sk表示第k階段的狀態(tài)變量。通常一個(gè)階段有若干個(gè)狀態(tài)。第k階段的狀態(tài)就是該階段所有始點(diǎn)的集合。如引例中84二、動(dòng)態(tài)規(guī)劃的基本概念1、階段。階段的劃分，一般根

（2）狀態(tài)應(yīng)具有無(wú)后效性（即馬爾可夫性）。即如果某階段狀態(tài)給考慮，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響。3、決策與決策變量。在某階段對(duì)可供選擇狀態(tài)的決定（或選擇），稱(chēng)為決策。描述的變量稱(chēng)為決策變量。常用dk(Sk)表示第k階段處于狀態(tài)Sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。決策變量允許取值的范圍，稱(chēng)為允許決策集合，常用Dk(Sk)表示。顯然dk（Sk）∈Dk(Sk)。如在引例的第二階段中，若從B1出發(fā)，D2（B1）={B1C1,B1C2,B1C3}如果決定選取B1C2，則d2（B1）=B1C2。85（2）狀態(tài)應(yīng)具有無(wú)后效性（即馬爾可夫性）。即如果某稱(chēng)可供選擇策略的范圍，為允許策略集，用P表示。動(dòng)態(tài)規(guī)劃方法就是要從允許策略集P中找出最優(yōu)策略P1n*。

4、策略與子策略。策略是一個(gè)決策序列的集合。當(dāng)k=1時(shí)，P1n（S1）={d1(s1),d2(s2),…,dn(sn)}就稱(chēng)為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略，簡(jiǎn)記為P1n(S1).稱(chēng)Pk,n(Sk)={dk(sk),dk+1(sk+1),…,dn(sn)}為由第k階段開(kāi)始到最后階段止的一個(gè)子策略，簡(jiǎn)稱(chēng)后部子策略。簡(jiǎn)記為Pk,n(Sk)5、狀態(tài)轉(zhuǎn)移方程。它是確定過(guò)程由某一階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)的演變過(guò)程，用Sk+1=Tk(Sk,dk)表示。該方程描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。因此又稱(chēng)其為狀態(tài)轉(zhuǎn)移函數(shù)。86稱(chēng)可供選擇策略的范圍，為允許策略集，用P表示。4、策略與子策6、階段指標(biāo)、指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)（1）衡量某階段決策效益優(yōu)劣的數(shù)量指標(biāo)，稱(chēng)為階段指標(biāo)，用vk(Sk,dk)表示第k階段的階段指標(biāo)。在不同的問(wèn)題中，其含義不同。它可以是距離、利潤(rùn)、成本等。在引例中，用dk=vk(Sk,dk)表示在第k階段由點(diǎn)Sk到點(diǎn)Sk+1=dk(Sk)距離。如d2(B3,C1)=6。876、階段指標(biāo)、指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)87（2）用于衡量所選定策略?xún)?yōu)劣的數(shù)量指標(biāo)，稱(chēng)為指標(biāo)函數(shù)。它是定義在全過(guò)程和所有后部子過(guò)程上確定的數(shù)量函數(shù)。記為Vk,n(Sk,Pk,n).Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1)k=1,2,…,n。構(gòu)成動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿(mǎn)足遞推關(guān)系。常見(jiàn)的指標(biāo)函數(shù)的形式有：①

②88（2）用于衡量所選定策略?xún)?yōu)劣的數(shù)量指標(biāo)，稱(chēng)為指標(biāo)函數(shù)。它是定（3）最優(yōu)指標(biāo)函數(shù)fk(Sk),表示從第k階段的狀態(tài)Sk開(kāi)始采用最優(yōu)子策略P*k,n，到第n階段終止時(shí)所得到的指標(biāo)函數(shù)值。即fk(Sk)=OptVk,n(Sk,dk,…Sn+1)其中Opt是最優(yōu)化（Optimum）的縮寫(xiě)，可根據(jù)題意取max或min。在引例中，指標(biāo)函數(shù)Vk,n表示在第k階段由點(diǎn)Sk至終點(diǎn)E的距離。fk(sk)表示第k階段點(diǎn)Sk到終點(diǎn)E的最短距離。f2(B1)=11表示從第2階段中的點(diǎn)B1到點(diǎn)E的最短距離。

89（3）最優(yōu)指標(biāo)函數(shù)fk(Sk),表示從第k階段的狀態(tài)Sk開(kāi)始7、基本方程（遞推關(guān)系式）從引例求A到E的最短路的計(jì)算過(guò)程中可以看出，在求解的各個(gè)階段，我們利用了k階段與k+1階段之間的遞推關(guān)系一般地，若則有907、基本方程（遞推關(guān)系式）一般地，若若三、動(dòng)態(tài)規(guī)劃的基本思想與最優(yōu)化原理91若三、動(dòng)態(tài)規(guī)劃的基本思想與最優(yōu)化原理91

1、基本思想：動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本方程，因此首先必須將問(wèn)題的過(guò)程劃分為多個(gè)相互聯(lián)系的多階段決策過(guò)程，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問(wèn)題化成一族同類(lèi)型的子問(wèn)題。然后從邊界條件開(kāi)始，逆過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每個(gè)子問(wèn)題求解時(shí)，均利用它前面已求出的子問(wèn)題的最優(yōu)化結(jié)果依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前的一段和未來(lái)的各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每階段決策的選取是從全局來(lái)考慮，與該段的最優(yōu)選擇一般是不同的。動(dòng)態(tài)規(guī)劃方法的基本思想體現(xiàn)了多階段性、無(wú)后效性、遞歸性、總體優(yōu)化性。921、基本思想：動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)

2、最優(yōu)化原理動(dòng)態(tài)規(guī)劃方法基于R·Bellman等人提出的最優(yōu)化原理：“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)于先前的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。”簡(jiǎn)言之，“一個(gè)最優(yōu)策略的子策略總是最優(yōu)的”。但是，最優(yōu)化原理僅是策略最優(yōu)性的必要條件，而基本方程是策略最優(yōu)性的充要條件。由此可見(jiàn)，基本方程是動(dòng)態(tài)規(guī)劃理論與方法的基礎(chǔ)。§2、動(dòng)態(tài)規(guī)劃模型的建立與求解一、構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件932、最優(yōu)化原理§2、動(dòng)態(tài)規(guī)劃模型的建立與求解一

建立動(dòng)態(tài)規(guī)劃模型，就是分析問(wèn)題并建立問(wèn)題的動(dòng)態(tài)規(guī)劃基本方程。為此，必須滿(mǎn)足以下條件：1、將問(wèn)題的過(guò)程劃分成恰當(dāng)?shù)碾A段；2、正確選擇狀態(tài)變量Sk，使它既能描述過(guò)程的演變，又要滿(mǎn)足無(wú)后效性；3、確定決策變量dk及每階段的允許決策集合Dk(Sk)；4、正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程；5、正確寫(xiě)出指標(biāo)函數(shù)Vk,n的關(guān)系式，它應(yīng)具有以下三個(gè)性質(zhì)；（1）是定義全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)；（2）具有可分離性，并滿(mǎn)足遞推關(guān)系，即Vk,n(Sk,dk,…Sn+1)=￠(Sk,dk,Vk+1,n)（3）函數(shù)￠（Sk,dk,Vk+1,n）對(duì)于Vk+1,n要求嚴(yán)格單調(diào)。以上五點(diǎn)是正確寫(xiě)出動(dòng)態(tài)規(guī)劃基本方程的要素。94建立動(dòng)態(tài)規(guī)劃模型，就是分析問(wèn)題并建立問(wèn)題的動(dòng)態(tài)規(guī)二、求解動(dòng)態(tài)規(guī)劃模型的方法1、在已知初始狀態(tài)S1下，采用逆序解法：（反向遞歸）

按上圖示意的求解方法稱(chēng)為逆序法。例如引例的求解，就是把A看作始端，E為終端，規(guī)定從A到E為過(guò)程的行進(jìn)方向，而尋優(yōu)則是從E到A逆過(guò)程進(jìn)行，所以是采用了逆序法。階段1s1d1(s1)v1(s1,d1)階段2s2d2(s2)v2(s2,d2)…階段kskdk(sk)vk(sk,dk)階段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)階段nsndn(sn)vn(sn,dn)…vk,nfk(sk)=optVk,n尋優(yōu)方向95二、求解動(dòng)態(tài)規(guī)劃模型的方法1、在已知初始狀態(tài)S1下，采用逆序2、在已知終止?fàn)顟B(tài)Sn下，采用順序解法（正向遞歸）

如果我們把引例中E看作始端，A為終端，規(guī)定從E到A過(guò)程為行進(jìn)方向，而尋優(yōu)則是從A到E過(guò)程進(jìn)行求解的方法稱(chēng)為順序法。其示意圖如下：

逆序法與順序法的不同僅在對(duì)始端終端看法的顛倒或在規(guī)定的行進(jìn)方向不同。但在尋優(yōu)時(shí)卻都是逆行進(jìn)方向，從最后一階段開(kāi)始，逐段逆推向前計(jì)算，找出最優(yōu)結(jié)果。962、在已知終止?fàn)顟B(tài)Sn下，采用順序解法（正向遞歸）3、兩種解法在建模時(shí)的區(qū)別如下表所示973、兩種解法在建模時(shí)的區(qū)別如下表所示97

應(yīng)用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)必須首先建立動(dòng)態(tài)規(guī)劃模型，再用逆序或順序算法求解。寫(xiě)一個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃模型一般包含以下6個(gè)步驟：（1）階段劃分k=1,2,…,n（2）確定狀態(tài)變量sk（3）確定決策變量dk（4）確定狀態(tài)轉(zhuǎn)移方程sk+1=f(sk,dk)或sk-1=f(sk,dk)（5）確定階段指標(biāo)V(sk,dk)（6）確定基本遞推方程或98應(yīng)用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)必須首先建立動(dòng)態(tài)規(guī)劃模型，例2某商店在未來(lái)四個(gè)月里，利用一個(gè)倉(cāng)庫(kù)經(jīng)銷(xiāo)某種商品。該倉(cāng)庫(kù)的最大容量為1000件，每月中旬訂購(gòu)商品，并于下月初取到訂貨。據(jù)估計(jì)，今后四個(gè)月這種商品的購(gòu)價(jià)和售價(jià)如下表所示。假定商店在1月初開(kāi)始經(jīng)銷(xiāo)時(shí)倉(cāng)庫(kù)已存有該種商品500件，每月市場(chǎng)需求不限，問(wèn)應(yīng)如何計(jì)劃每個(gè)月的訂購(gòu)與銷(xiāo)售量，使這四個(gè)月的總利潤(rùn)最大（不考慮倉(cāng)庫(kù)的存儲(chǔ)費(fèi)用）？月份k購(gòu)價(jià)pk售價(jià)qk110122993111341517解：首先建立動(dòng)態(tài)規(guī)劃模型。（1）問(wèn)題劃分為四個(gè)階段K=1，2，3，4；（2）