【文章內(nèi)容簡(jiǎn)介】 或非線性規(guī)劃方法有時(shí)更為有效。此外， 雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃 (如線性規(guī)劃、 非線性規(guī)劃 )，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解 。 迄今為止，動(dòng)態(tài)規(guī)劃模型已廣泛應(yīng)用于經(jīng)濟(jì)、生物、工程、軍事等許多領(lǐng)域，并取得了很好的效果。 本章具體研究多階段的動(dòng)態(tài)規(guī)劃模型及其在資源分配問(wèn)題上的實(shí)例應(yīng)用。 資源分配問(wèn)題上的動(dòng)態(tài)規(guī)劃模型 所謂“資源分配問(wèn)題”就是把一定數(shù)量的若干資源合理地分配給若干個(gè)使用者，使 11 指標(biāo)函數(shù)達(dá)到最優(yōu)。 這里僅討論一種資源的分配問(wèn)題。其一般提法是，設(shè)某 種資源的總量為 a，擬用于n 項(xiàng)經(jīng)營(yíng)活動(dòng)，若給第 j 項(xiàng)活動(dòng)分配 jx 個(gè)單位，其收益為 )( jj xg ，問(wèn)應(yīng)如何分配，才能使這 n 項(xiàng)經(jīng)營(yíng)活動(dòng)總的收益值最大？ 對(duì)于該問(wèn)題，我們可以直接表示為 ?????????????nixaxtsxgZiniiinii,...,2,1,0..)(m a x11 因此，可用非線性規(guī)劃方法求解。但是利用這類(lèi)問(wèn)題的特性，也可 以把它看做一個(gè)多階段決策問(wèn)題，建立如下的動(dòng)態(tài)規(guī)劃模型： 以階段變量 k 表示資源分配給第 k 項(xiàng)經(jīng)營(yíng)活動(dòng)的過(guò)程； 以狀態(tài)變量 kx 表示在開(kāi)始給第 k 項(xiàng)經(jīng)營(yíng)活動(dòng)分配資源時(shí)尚剩余的資源數(shù)量； 以決策變量 ku 表示分配給第 k 項(xiàng)經(jīng)營(yíng)活動(dòng)的資源數(shù)量，則允許決策集合為? ?kkkkk xuuxU ??? 0|)( ； 狀態(tài)轉(zhuǎn)移方程為 nkuxx kkk ,...,2,1,1 ???? ； 以 ? ?kkk uxV , 表示從現(xiàn)有 kx 個(gè)單位資源中分配給第 k 項(xiàng)經(jīng)營(yíng)活動(dòng) ku 個(gè)單位資源后的預(yù)計(jì)收益； 以 )( kk xf 表示從現(xiàn)有 kx 個(gè)單位資源中分配給第 k 項(xiàng)到第 n 項(xiàng)經(jīng)營(yíng)活動(dòng)后，所得的最大利益，則函數(shù)基本方程為 ?????????????????1, . . . ,1,0)()}(),({m a x)(1111)(nnkxfxfuxVxfnnkkkkkxUukkkkk 動(dòng)態(tài)規(guī)劃模型在資源分配問(wèn)題的應(yīng)用舉例 某工廠擬將 5 臺(tái)先進(jìn)設(shè)備分配給下屬的甲、乙、丙三個(gè)分廠，分廠獲得該設(shè)備后每年為總廠提供的盈利如 下表所示 (如表 )： 12 表 各分廠獲得該設(shè)備后每年為總廠提供的盈利 分廠 分分 分廠 盈利（ 萬(wàn)元）元） 設(shè)備（臺(tái)） 0 1 2 3 4 5 甲 乙 丙 0 0 0 3 5 4 7 10 6 9 11 12 12 11 12 13 11 12 試問(wèn)：該工廠如何分配這些設(shè)備，才能使總廠的盈利最大？ 變量說(shuō)明 k 表示給甲、乙、丙三個(gè)分廠分配的過(guò)程，其中 k=1,2,3 kx 表示在開(kāi)始給第 k 個(gè)分廠分配時(shí)尚未分配的臺(tái)數(shù) ku 表示分配給第 k 分廠的臺(tái)數(shù) ? ?kkk uxV , 表示從現(xiàn)有 kx 臺(tái)中分配給第 k 分廠 ku 臺(tái)后的預(yù)計(jì)盈 利 )(kkxf 表示從現(xiàn)有 kx 臺(tái)中分配給第 k 分廠到第 3 分廠后，所得的最大盈利 問(wèn)題分析 本問(wèn)題可以看做一個(gè)多階段決策問(wèn)題，采用動(dòng)態(tài)規(guī)劃方法解決之，將問(wèn)題分為 3 個(gè)子問(wèn)題，分別作出決策，最終得到一個(gè)策略，使得工廠獲得最大盈利。 13 模型假設(shè) 假設(shè) 1：設(shè)備不會(huì)出現(xiàn)故障，影響盈利； 假設(shè) 2：甲乙丙三者的單 位利潤(rùn)與它們相互間箱數(shù)無(wú)關(guān)； 假設(shè) 3：甲乙丙三者的設(shè)備臺(tái)數(shù)可以是任意整數(shù)。 模型建立 ??????????? ???1,2,30)()}(),({m a x)(4411)(kxfxfuxVxf kkkkkxUukk kkk 模型求解 算法描述 根據(jù)以上的模型，可設(shè)計(jì)解資源分配問(wèn)題的動(dòng)態(tài)規(guī)劃算法 [2,6]maxprofit 如下： public static void maxprofit(int n,int m,int [][]v,int [][]p) { //該 maxprofit 函數(shù)主要得到問(wèn)題的最優(yōu)值，即資源分配問(wèn)題的總盈利 //n:設(shè)備數(shù)量 。m:分廠數(shù)量 //v[i][j]:i 臺(tái)設(shè)備提供給第 j 分廠將得到的盈利 //p[i][j]:記錄 f[i][j]的值是由哪一個(gè)子問(wèn)題的解得到 . //f[i][j]:用 i 臺(tái)設(shè)備分配給后 j 個(gè)分廠將得到的盈利 int [][]f=new int[n+1][m+1]。 for(int i=1。i=n。i++) f[i][0]=0。 for(int j=1。j=m。j++) f[0][j]=0。 for (int i=1。i=n。i++) { f[i][m]=v[i][m]。 p[i][m]=i。 } for(int j=m1。j=1。j) 14 for(int i=1。i=n。i++) for(int k=0。k=i。k++) { if(f[i][j]f[ik][j+1]+v[k][j]) { f[i][j]=f[ik][j+1]+v[k][j]。 p[i][j]=k。 } } (最大獲利是： %2d 萬(wàn)元 \n,f[n][1])。 } public static void distribution(int n,int m,int [][]p) { //該 distribution 得到問(wèn)題的最優(yōu)解，即資源分配問(wèn)題的資源分配方案 int k=n。 (資源分配方案： \n)。 for(int j=1。j=m。j++) { (%1d 臺(tái)設(shè)備分配給第 %1d 分廠使用 \n,p[k][j],j)。 k=kp[k][j]。 } } 運(yùn)行結(jié)果 根據(jù)以上的算法設(shè)計(jì)，可以得到該例子的運(yùn)行結(jié)果（見(jiàn)圖 ）： 15 圖 運(yùn)行結(jié)果 結(jié)果分析 根據(jù)以上的運(yùn)行結(jié)果（見(jiàn)圖 ），可以知道總廠每年最大的盈利為 15 萬(wàn)元，其中，最優(yōu)分配方案為：分別給甲、乙、丙門(mén)市部分配 0 箱， 2 箱， 3 箱。 本章小結(jié) 我們研究多階段決策問(wèn) 題，常用的有效方法就是動(dòng)態(tài)規(guī)劃模型。 建立動(dòng)態(tài)規(guī)劃模型的步驟 (1)、根據(jù)時(shí)間或空間的自然特征，把實(shí)際問(wèn)題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段，使問(wèn)題能夠轉(zhuǎn)化成一個(gè)多階段決策問(wèn)題。 (2)、正確地選擇狀態(tài)變量 kx ，確定狀態(tài)集合 kX 。 (3)、確定決策變量 ku 及每個(gè)階段的允許決策集合 }{)( kkk uxU ? 。 (4)、寫(xiě)出狀態(tài)轉(zhuǎn)移方程，即給出從第 k 階段到第 k+1 階段的狀態(tài)轉(zhuǎn)移規(guī)律：),(1 kkkk uxTx ?? 。 (5)、正確的寫(xiě)出指標(biāo)函數(shù)。 (6)、寫(xiě)出動(dòng)態(tài)規(guī)劃函數(shù)基本方程。 其中如何選定狀態(tài)是關(guān)鍵的一步，狀態(tài)應(yīng)能描述過(guò)程的特征，可以直接或間接觀測(cè)，并且具有無(wú)后效性，即當(dāng)某階段的狀態(tài)給定后，過(guò)程 以后的演變與該階段以前的狀態(tài)無(wú)關(guān)。 動(dòng)態(tài)規(guī)劃的適用條件 任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿(mǎn)足最優(yōu)化原理和無(wú)后效性。 16 動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：動(dòng)態(tài)規(guī)劃把較為復(fù)雜的問(wèn)題劃分為若干個(gè)相互聯(lián)系的階段，每個(gè)階段的求解問(wèn)題相對(duì)簡(jiǎn)單，而通過(guò)逐段求解這一遞推過(guò)程便可得到原問(wèn)題的全局最優(yōu)解。此外，動(dòng)態(tài)規(guī)劃得到的是全過(guò)程和所有后部子過(guò)程的各個(gè)狀態(tài)的最優(yōu)解，這在討論最優(yōu)決策和最優(yōu)值對(duì)于狀態(tài)的穩(wěn)定性，或者實(shí)際問(wèn) 題要尋找次優(yōu)解時(shí)是很有用的。還有，由于動(dòng)態(tài)規(guī)劃方法反映了動(dòng)態(tài)過(guò)程演變的聯(lián)系和特征，在計(jì)算時(shí)可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。 缺點(diǎn)：沒(méi)有統(tǒng)一標(biāo)準(zhǔn)模型可供采用，也沒(méi)有萬(wàn)能的構(gòu)造模型的方法。不同的實(shí)際問(wèn)題，其動(dòng)態(tài)規(guī)劃模型也隨之不同，因而，實(shí)際問(wèn)題的動(dòng)態(tài)規(guī)劃模型的建立往往需要豐富的想象力和靈活的技巧性，這就帶來(lái)了應(yīng)用上的局限性，同時(shí)，也就需要我們?cè)谝院蟮难芯恐羞M(jìn)一步尋求更好的算法。 結(jié)論 本論文主要對(duì)最優(yōu)化方法在生活中資源配置方面的應(yīng)用進(jìn)行了理論知識(shí)的闡述和通過(guò)舉例論證來(lái)探討。 論文首先介紹了最優(yōu)化方 法和資源配置方面的理論知識(shí)，提出了最優(yōu)化方法在資源配置方面的應(yīng)用的重要性。在當(dāng)今各方面競(jìng)爭(zhēng)越來(lái)越激烈的時(shí)代下，資源方面的競(jìng)爭(zhēng)成為成為生活中至關(guān)重要的一方面。如何去真正做到資源的合理配置，僅憑經(jīng)驗(yàn)，直覺(jué)等非客觀因素來(lái)做一個(gè)決策已然不可行。而最優(yōu)化方法 主要運(yùn)用 數(shù)學(xué)方法 研 究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)，必定成為生活中資源配置方面的一個(gè)重要使用工具。 論文在第二章具體介紹了最優(yōu)化方法中的線 性規(guī)劃模型及其在生活中生產(chǎn)計(jì)劃制定的實(shí)例應(yīng)用。主要探討了資源的影子價(jià)格如何直接關(guān)系到資源的最有效利用，提高經(jīng)濟(jì)效益，以及研究了線性規(guī)劃模型中的數(shù)據(jù)集合的波動(dòng)對(duì)最優(yōu)解或最優(yōu)基的影響。線性規(guī)劃模型在有限資源的配置方面具有十分重要的現(xiàn)實(shí)價(jià)值。 論文在第三章具體介紹了最優(yōu)化方法中的多階段的動(dòng)態(tài)規(guī)劃模型及其在生活中資源分配問(wèn)題中的實(shí)例應(yīng)用。主要探討了動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想在多階段決策問(wèn)題上的應(yīng)用。動(dòng)態(tài)規(guī)劃模型在多階段的資源分配問(wèn)題具有重要的現(xiàn)實(shí)應(yīng)用價(jià)值。 在整個(gè)論文的研究里面，可以看出最優(yōu)化方法在現(xiàn)實(shí)生活中具有重要的 現(xiàn)實(shí)意義， 17 我們應(yīng)該將數(shù)學(xué)最優(yōu)化問(wèn)題最有效地結(jié)合到生活實(shí)際中。不管是適用于資源有限的線性規(guī)劃模型，還是適用于多階段資源配置的動(dòng)態(tài)規(guī)劃模型，都可以體現(xiàn)出最優(yōu)化方法提供了生活上合理配置資源十分重要的參考，并從數(shù)據(jù)上給予人們做出決策提供關(guān)鍵的支持。當(dāng)然在現(xiàn)實(shí)生活中，我們不能僅靠最優(yōu)化方法的理論知識(shí)直接做出資源配置的決策，還要結(jié)合個(gè)人經(jīng)驗(yàn)、市場(chǎng)變化等各種因素，將最優(yōu)化方法的理論知識(shí)最有效的結(jié)合到生活中資源配置方面的問(wèn)題上，才能確保真正做到資源合理配置，實(shí)現(xiàn)資源的有效利用，提高經(jīng)濟(jì)效益。 另外，以下幾個(gè)問(wèn)題還需要以后進(jìn) 一步研究探討 : 第一，線性規(guī)劃是指從各種限制條件的組合中，選擇出最為合理的計(jì)算方法，建立線性規(guī)劃模型從而求得最佳結(jié)果。由于個(gè)人的能力問(wèn)題，所舉得的生活實(shí)例主要談及有限資源的合理配置，沒(méi)去涉及到設(shè)備更新等因素?？梢?jiàn)，如果涉及到這些方面的因素，做出的決策將更具有現(xiàn)實(shí)意義，這就需要我們進(jìn)一步研究線性規(guī)劃模型在生活中資源配置方面的應(yīng)用。 第二，論文中的多階段的動(dòng)態(tài)規(guī)劃模型主要應(yīng)用于一種資源的分配問(wèn)題。然而，在現(xiàn)實(shí)生活中，我們往往要做到的是多種資源的組合分配問(wèn)題。如果進(jìn)一步談及動(dòng)態(tài)規(guī)劃模型在多種資源的組合分配問(wèn)題的應(yīng) 用，將對(duì)論文結(jié)論的說(shuō)服力進(jìn)一步加強(qiáng)，這就需要我們進(jìn)一步研究探討。 第三， 由于研究經(jīng)驗(yàn)不足以及實(shí)際處理能力還不夠強(qiáng)，論文中所選取的例子在各方面處理上離實(shí)踐仍有偏差，這則表明選取的例子還沒(méi)能真正與實(shí)踐結(jié)合，也不夠完善。此外，還可以進(jìn)一步結(jié)合最優(yōu)化方法中的其他優(yōu)化理論，談?wù)勂湓谫Y源配置方面的應(yīng)用。論文只能對(duì)于實(shí)踐有著一定的參考性，但若要成為實(shí)踐中直接引用的方案，還是遠(yuǎn)遠(yuǎn)不夠的。 18 參 考 文 獻(xiàn) [1] 唐煥文、秦學(xué)志主編 .實(shí)用最優(yōu)化方法 [M].大連：大連理工大學(xué)出版社， 2021. [2] 陳寶林主編 .最優(yōu)化理論與算法 [M].北京：清華大學(xué)出版社， 2021. [3] 盧險(xiǎn)峰主編 .最優(yōu)化方法基礎(chǔ) [M].上海：同濟(jì)大學(xué)出版社， 2021.