【正文】 源配置方面的應用進行了理論知識的闡述和通過舉例論證來探討。 缺點：沒有統(tǒng)一標準模型可供采用，也沒有萬能的構(gòu)造模型的方法。此外，動態(tài)規(guī)劃得到的是全過程和所有后部子過程的各個狀態(tài)的最優(yōu)解，這在討論最優(yōu)決策和最優(yōu)值對于狀態(tài)的穩(wěn)定性，或者實際問 題要尋找次優(yōu)解時是很有用的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。 動態(tài)規(guī)劃的適用條件 任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。 (6)、寫出動態(tài)規(guī)劃函數(shù)基本方程。 (4)、寫出狀態(tài)轉(zhuǎn)移方程，即給出從第 k 階段到第 k+1 階段的狀態(tài)轉(zhuǎn)移規(guī)律：),(1 kkkk uxTx ?? 。 (2)、正確地選擇狀態(tài)變量 kx ，確定狀態(tài)集合 kX 。 本章小結(jié) 我們研究多階段決策問 題，常用的有效方法就是動態(tài)規(guī)劃模型。 k=kp[k][j]。j=m。 (資源分配方案： \n)。 } } (最大獲利是： %2d 萬元 \n,f[n][1])。k++) { if(f[i][j]f[ik][j+1]+v[k][j]) { f[i][j]=f[ik][j+1]+v[k][j]。i++) for(int k=0。j) 14 for(int i=1。 } for(int j=m1。i++) { f[i][m]=v[i][m]。 for (int i=1。j=m。i++) f[i][0]=0。 for(int i=1。 模型建立 ??????????? ???1,2,30)()}(),({m a x)(4411)(kxfxfuxVxf kkkkkxUukk kkk 模型求解 算法描述 根據(jù)以上的模型，可設(shè)計解資源分配問題的動態(tài)規(guī)劃算法 [2,6]maxprofit 如下： public static void maxprofit(int n,int m,int [][]v,int [][]p) { //該 maxprofit 函數(shù)主要得到問題的最優(yōu)值，即資源分配問題的總盈利 //n:設(shè)備數(shù)量 。但是利用這類問題的特性，也可 以把它看做一個多階段決策問題，建立如下的動態(tài)規(guī)劃模型： 以階段變量 k 表示資源分配給第 k 項經(jīng)營活動的過程； 以狀態(tài)變量 kx 表示在開始給第 k 項經(jīng)營活動分配資源時尚剩余的資源數(shù)量； 以決策變量 ku 表示分配給第 k 項經(jīng)營活動的資源數(shù)量，則允許決策集合為? ?kkkkk xuuxU ??? 0|)( ； 狀態(tài)轉(zhuǎn)移方程為 nkuxx kkk ,...,2,1,1 ???? ； 以 ? ?kkk uxV , 表示從現(xiàn)有 kx 個單位資源中分配給第 k 項經(jīng)營活動 ku 個單位資源后的預計收益； 以 )( kk xf 表示從現(xiàn)有 kx 個單位資源中分配給第 k 項到第 n 項經(jīng)營活動后，所得的最大利益，則函數(shù)基本方程為 ?????????????????1, . . . ,1,0)()}(),({m a x)(1111)(nnkxfxfuxVxfnnkkkkkxUukkkkk 動態(tài)規(guī)劃模型在資源分配問題的應用舉例 某工廠擬將 5 臺先進設(shè)備分配給下屬的甲、乙、丙三個分廠，分廠獲得該設(shè)備后每年為總廠提供的盈利如 下表所示 (如表 )： 12 表 各分廠獲得該設(shè)備后每年為總廠提供的盈利 分廠 分分 分廠 盈利（ 萬元）元） 設(shè)備（臺） 0 1 2 3 4 5 甲 乙 丙 0 0 0 3 5 4 7 10 6 9 11 12 12 11 12 13 11 12 試問：該工廠如何分配這些設(shè)備，才能使總廠的盈利最大？ 變量說明 k 表示給甲、乙、丙三個分廠分配的過程，其中 k=1,2,3 kx 表示在開始給第 k 個分廠分配時尚未分配的臺數(shù) ku 表示分配給第 k 分廠的臺數(shù) ? ?kkk uxV , 表示從現(xiàn)有 kx 臺中分配給第 k 分廠 ku 臺后的預計盈 利 )(kkxf 表示從現(xiàn)有 kx 臺中分配給第 k 分廠到第 3 分廠后，所得的最大盈利 問題分析 本問題可以看做一個多階段決策問題，采用動態(tài)規(guī)劃方法解決之，將問題分為 3 個子問題，分別作出決策，最終得到一個策略，使得工廠獲得最大盈利。 這里僅討論一種資源的分配問題。 本章具體研究多階段的動態(tài)規(guī)劃模型及其在資源分配問題上的實例應用。此外， 雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃 (如線性規(guī)劃、 非線性規(guī)劃 )，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解 。動態(tài)規(guī)劃把比較復雜的問題劃分成若干階段，通過逐段求解，最終得到全局最優(yōu)解。 20 世紀 50 年代初 美國 數(shù)學家 等人在研究多階段決策過程 (multistep decision process)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為 一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法 —— 動態(tài)規(guī)劃。多階段決策問題，不論其本身是否與時間有關(guān)，由于分為階段來依次解決，這便具有了明顯的時序性，而在各階段中所采取的決策是隨階段而變動的，不同階段采取不同決策，這便是“動態(tài)”的含義。把一個問題劃分成若干個相互聯(lián)系的階段，選取其最優(yōu)策略，這類問題就是多階段決策問題。若對應于一個策略，可以由一 個量化的指標來確定這個策略所對應的活動過程的效果，那么，不同的策略就有各自的效果。 10 3 多階段的動態(tài)規(guī)劃模型 所謂多階段決策問題 [1]是指這樣一類活動過程：它可以分為若干個相互聯(lián)系的階段，在每個階段上都需要作出決策，而一個階段的決策確定以后，將會影響以后各階段的活動及其決策，當所有階段的決策確定后，就完全確定了該問題的活動過程。線性規(guī)劃模型日益成熟，在生活各方面都會經(jīng)常用到線性規(guī)劃模型，通過對線性規(guī)劃模型的數(shù)據(jù) A， b， C 進行靈敏度分析，可以盡可能控制這些數(shù)據(jù)的變化范圍，使得企業(yè)保持一定的收益。綜上，若每公斤 C 的獲利增加到 14 元，則 3x 系數(shù)變?yōu)?14*4=56，在允許范圍內(nèi)，所以不應改變生產(chǎn)計劃。 圖 的第 19 行“ CURRENT COEF”的“ ALLOWABLE INCREASE”和“ ALLOWABLE DECREASE”給出了最優(yōu)解不變條件下目標函數(shù)系數(shù)的允許變化范圍：3x 的系數(shù)為（ 4812,48+12），即（ 36,60）。 圖 的第 9 行“ DUAL PRICES”告訴我們，勞動時間增加 1 小時時利潤增長4 元，即 1 小時勞動的影子價格為 4 元。 圖 的第 8 行“ DUAL PRICES”告訴我們，增加 1 公斤黃豆時利潤增長 24 元，即 1 公斤黃豆的影子價格為 24 元； 圖 的第 23 行“ CURRENT RHS”的“ ALLOWABLE INCREASE”和“ ALLOWABLE DECREASE”給出了黃豆的影子價格有意義條件下約束右端的限制范圍：黃豆最多增加 30 公斤。 模型假設(shè) 假設(shè) 1： A， B， C 每公斤的獲利與它們各自產(chǎn)量無關(guān)； 假設(shè) 2： A， B， C 每公斤的獲利與它們相互間產(chǎn)量無關(guān)； 假設(shè) 3：加工 A， B， C 的黃豆的重 量可以是任意實數(shù)。決策收到的限制：原料供應、勞動時間、設(shè)備的加工能力。 為該廠制定一個生產(chǎn)計劃，使每天獲利最大。根據(jù)市場需求，生 產(chǎn)的 A， B， C 全部能售出，且每公斤 A 獲利 24 元，每公斤 B 獲利 16 元，每公斤 C 獲利 12 元。增加一個新變量，假設(shè)在獲得原線性規(guī)劃的最優(yōu)解 *X 之后，又發(fā)現(xiàn)了一個新變量 1?nx ，其對應的價值系數(shù)為 1?nc ，在新的約束矩陣中對應的系數(shù)列向量為1?nP，于是得到如下新的線性規(guī)劃問題：??????????????0,0..m a x11111nnnnnxXbxPAXtsxcCXZ ；增加一個約束，不妨假設(shè)此附加的約束條件為不等式形式，即 11 ?? ? mm bXa ，其中 1?ma 是 n 維行向量， 1?mb 為右端項系數(shù)，于是新的線性規(guī)劃模型變?yōu)???????????0..max11XbXabAXtsCXZmm。一般而言，約束矩陣 A 的改變可能導致不同的最優(yōu)解和最優(yōu)基，進行靈敏度分析不是一件簡單的事。 B 的波動會使最優(yōu)解和最優(yōu)目標函數(shù)值，但可以不改變原最優(yōu)基 B，只要 *1 XbB ???? 即可，其中 *X 為原最優(yōu)解。若 ic 是某基變量 ix 的價值系數(shù)， jc?為該價值系數(shù)的改變量，只要非基變量對應的檢驗數(shù) ? ? Nii NBc ??? ?1 ，就可以保持現(xiàn)行最優(yōu)解依舊最優(yōu)，由此可以確定價值系數(shù) jc 的可變化范圍。 下面，我們分別討論當價值系數(shù) C、資源擁有量 b 和資源消耗系數(shù)向量 A 變化的響應情況： 考慮 只有價值向量 C 的改變的情形。 通過改變模型（ 1）中資源消耗系數(shù)，即約束函數(shù)的斜率 A,使得預期目標解成為可行解。由于不改變可行域 D，因此，預期目標解必須是線性規(guī)劃原問題的可行解； 6 通過改變模型（ 1）中資源擁有量 b，使得預期目標解成為可行解。那么，就有必要去分析下這些數(shù)據(jù)波動時，對當前的最優(yōu)解或最優(yōu)基產(chǎn)生什么影響，即是所謂的靈敏度分析。 線性規(guī)劃的靈敏度分析 線性規(guī)劃問題所對應的數(shù)據(jù)集合 A、 b、 C 常常是通過預測或估計所得到的的統(tǒng)計數(shù)據(jù)，可能存在一定的誤差。隨著資源的買進賣出，企業(yè)資源的影子價格也隨著發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。影子價格是一種編輯價格，iy 的值相當于在資源得到最優(yōu)利用的條件下， ib 每增加 1 個單位時，目標函數(shù) Z 的增加值。 ),...,( 21 myyyY ? 為對偶問題最優(yōu)解，它代表在資源最優(yōu)利用下，對各種單位資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻而作出的估價，簡稱影子價格。前者是由矩陣 A、右端向量 b 和價值向量 C 定義的，稱之為原問題；后者也是有相同的數(shù)據(jù)集合 A、 b 和 C 構(gòu)成，稱之為原問題的對偶問題。 對偶線性規(guī)劃及其影子價格 對偶理論 [5]是線性規(guī)劃的重要內(nèi)容之一。然而，現(xiàn)實生活中，常常遇到的不是僅僅靠一般的線性規(guī)劃模型就能解決的生產(chǎn)方面資源配置問題。 定理 1 最優(yōu)解判別定理 : 對于線性規(guī)劃問題 ? ?0,|,m a x ????? XbAXRXDCXZ n，若某個基本可行解所對應的檢驗向量 01 ??? ? NBCC BNN? ，那這個 基本可行解就是最優(yōu)解。單純形法是求解線性規(guī)劃問題的一種通用的有效算法，它的基本思路是從一個初始的基本可行解出發(fā)，尋找一條達到最優(yōu)基本可行解的最佳途徑。為 nmaAbbbbxxxXcccCmnijTmTnTn *,.. .,.. .,.. ., 212121 ???? 線性規(guī)劃的基本定理 : 如果可行域 ? ?0,| ???? XbAXRXD n 非空有界，那么線性規(guī)劃問題的目標函數(shù)一定可以在可行域 D 上的頂點上達到最優(yōu)值。該線性規(guī)劃模型常用于有限資源的分配問題。其實質(zhì)是在一組線性約束條件下，尋找一組決策變量使得目標函數(shù)取得最大或最小的條件極值問題。 線性規(guī)劃 線性規(guī)劃 [1,5]就是由目標函數(shù)為決策變量的線性函數(shù)和約束條件為線性等式或線性不等式所組成的數(shù)學規(guī)劃。對于這類組織資源使企業(yè)的生產(chǎn)任務最大限度滿足市場需求的問題，我們現(xiàn)在經(jīng)常采用到線性規(guī)劃的對偶規(guī)劃。這其中的原因主要是我們在利用線性規(guī)劃制定生產(chǎn)計劃時，將資源約束作為剛性約束來處理，沒有去考慮在市場環(huán)境下部分資源約束是彈性約束。對于這些制定企業(yè)生產(chǎn)計劃，最有效方法就是線性規(guī)