資源分配問題的求解方法.doc

石家莊學(xué)院畢業(yè)論文- 14 -資源分配問題的求解方法【摘要】資源分配問題就是將一種或幾種資源（原材料、資金、機(jī)器設(shè)備等）以最優(yōu)的方式分配給若干個使用者，以獲得最大的效益。它可以是靜態(tài)規(guī)劃問題，也可以通過構(gòu)造動態(tài)規(guī)劃模型求解。本文通過用單純形法求解線性規(guī)劃問題，用隱枚舉法、LINGO軟件求解 0-1 規(guī)劃問題，以及用逆序遞推算法求解動態(tài)規(guī)劃問題。這幾種算法的最終目的都是用來求解資源分配的最優(yōu)值問題。【關(guān)鍵詞】資源分配；線性規(guī)劃；0-1規(guī)劃；動態(tài)規(guī)劃The Method of Solving the Resource Allocation Problem【Abstract】Resource allocation problem is one or several resources( raw materials, machinery, equipment, etc.)assigned to several users by best way to get maximum benefit. It is a static planning problem, and can also through structural dynamic programming model to solve. This paper solves linear programming problem by using simplex method, 0-1 programming problem by using the implicit enumeration method, LINGO software method, and dynamic programming problem by using reverse recursive algorithm. The ultimate goal of this several algorithms is to solve the optimal value problem of the resources allocation.【Key Word】Resource allocation; Linear Programming; 0-1 programming; Dynamic programming目錄 1 引言12 線性規(guī)劃12.1 模型的建立12.2 求解方法22.3 實(shí)例 133 0-1規(guī)劃53.1 模型的建立53.2 求解方法63.3 實(shí)例 284 動態(tài)規(guī)劃104.1 模型的建立104.2 求解方法104.3 實(shí)例 3125 結(jié)論14參考文獻(xiàn)15附錄16致謝18- 17 -石家莊學(xué)院畢業(yè)論文1 引言人們奮斗所爭取的一切，都同他們的利益有關(guān)。資源分配問題關(guān)系著人們的利益能否實(shí)現(xiàn)，因而一直是政治經(jīng)濟(jì)學(xué)研究的中心課題之一。在近幾年，隨著社會經(jīng)濟(jì)的發(fā)展，資源分配問題已經(jīng)廣泛存在于社會各個領(lǐng)域，并且已經(jīng)成為制約我國改革、發(fā)展、穩(wěn)定的焦點(diǎn)問題。如何在滿足各使用者的基礎(chǔ)上，將有限資源進(jìn)行最佳分配，使得生產(chǎn)成本最低、投資最省、產(chǎn)量最高、利潤最大，以最大限度地提高效益，是資源分配問題中亟待解決的難題，所以資源分配的求解方法就給解決這種問題帶來了很大的方便。線性規(guī)劃是運(yùn)籌學(xué)中研究較早，理論和算法比較成熟的分支之一，它主要研究在線性等式（或不等式）的限制條件下，使某一線性目標(biāo)函數(shù)取得最大值（或最小值）的問題，并且求解有統(tǒng)一而簡單的方法即單純形法。但在許多問題中，決策變量必須為整數(shù)，例如當(dāng)決策變量是分配的人數(shù)、購買的設(shè)備數(shù)、投入的車輛數(shù)時，它們一般必須為非負(fù)整數(shù)時才有意義。在這種情況下，常需要應(yīng)用整數(shù)規(guī)劃進(jìn)行優(yōu)化。0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情況，也是最廣泛的整數(shù)規(guī)劃，用0-1整數(shù)規(guī)劃求解時有時會更容易。有時源分配問題上也可以使用動態(tài)規(guī)劃求解，動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法，這種方法就是把它看成一個時間軸，在時間的推移過程中，在每個時間階段選擇適當(dāng)?shù)臎Q策，以使整個系統(tǒng)達(dá)到最優(yōu)。本文不僅介紹了線性規(guī)劃、0-1規(guī)劃、和動態(tài)規(guī)劃幾種求解資源分配的方法，還介紹了求解線性規(guī)劃的方法單純形法、求解0-1規(guī)劃的方法隱枚舉法和LINGO軟件法、以及求解動態(tài)規(guī)劃的方法逆序遞推法等幾種算法的模型、求解的具體步驟和所對應(yīng)的實(shí)例。通過對本文的這幾種求解方法的介紹，基本上就可以使不同的資源分配問題得到更好更快的解答。2 線性規(guī)劃2.1 模型的建立線性規(guī)劃是運(yùn)籌學(xué)中最基本且范圍最廣的分支，它最主要是應(yīng)用于合理的進(jìn)行各種資源的分配，以取得最佳的效果。對于這類需要種不同的原材料生產(chǎn)種不同的產(chǎn)品的資源分配問題，一般是已知每種原材料的庫存量，每種產(chǎn)品所需的各種原材料的分量，以及生產(chǎn)每種產(chǎn)品能獲得多少利益1。這類資源分配問題只要運(yùn)用線性規(guī)劃就可以解決。 表1 產(chǎn)品原材料產(chǎn)品庫存量原材料利潤這種線性規(guī)劃問題的數(shù)學(xué)模型為： 這里為由目標(biāo)函數(shù)的系數(shù)組成的向量， 和 分別為不等式約束條件的系數(shù)矩陣和右端向量， 和 分別為等式約束條件的系數(shù)矩陣和右端向量，當(dāng)約束條件沒有等式時， 和 就用空矩陣 表示， 和分別是變量的下界和上界約束。滿足全部約束條件的一組決策變量 ，稱為此線性問題的可行解，而使目標(biāo)函數(shù)達(dá)到問題要求的最優(yōu)值(或)的可行解稱為線性規(guī)劃問題的最優(yōu)解。2.2 求解方法單純形法是求解線性規(guī)劃問題的通用方法。單純形法的基本思想是：先找出一個基本可行解，對它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的更好的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行，經(jīng)過反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到最大值（或最小值），就得到了最優(yōu)解?？梢杂脠D形表示為：單純形法的思路最優(yōu)解核心是：變量迭代找出一個初始基本可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解是否循環(huán)結(jié)束 圖1單純形法的一般解題步驟可歸納如下2： (1) 把線性規(guī)劃問題的約束方程組表達(dá)成典式方程組，找一個初始的可行基；(2) 求出對應(yīng)的典式及檢驗(yàn)數(shù)向量； (3) 求； (4) 若，停止，已找到最優(yōu)解(5) 若，停止，原問題無界；(6) 求；(7) 以代替得到新的基，轉(zhuǎn)第（2）步；用單純形法解題時，可通過單純形表求得最優(yōu)解。2.3 實(shí)例1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源。現(xiàn)將有關(guān)數(shù)據(jù)列表如下： 表2 產(chǎn)品資源甲乙資源限量煤 9 4 360 電 4 5 200油 3 10 300單位產(chǎn)品價格 7 12 試擬訂使總收入最大的生產(chǎn)計劃方案。解：決策變量：甲、乙產(chǎn)品的計劃產(chǎn)量，記為，；目標(biāo)函數(shù)：總收入，記為，則；為體現(xiàn)對其求極大化，在的前面冠以極大號；約束條件：分別來自資源煤、電、油限量的約束和產(chǎn)量非負(fù)的約束，表示為：其標(biāo)準(zhǔn)形式為其中，為松弛變量。用單純形表解題： 表3 7 12 00 0 94 1 0 0 36090 4 5 0 1 0 200 40 3 10 0 0 1 30030 0 0 0 0 1 0 240 0 0 1 5020 1 0 0 301000 00 0 0 1 84 1 0 0 20 0 1 0 24由單純形表求得的最優(yōu)解為；所以最優(yōu)解為。3 01規(guī)劃 3.1 模型的建立整數(shù)規(guī)劃指的是決策變量為非負(fù)整數(shù)值的一類線性規(guī)劃，在實(shí)際問題的應(yīng)用中，整數(shù)規(guī)劃模型對應(yīng)著大量的生產(chǎn)計劃或活動安排等決策問題，整數(shù)規(guī)劃的解法主要有分枝定界解法及割平面解法。0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特例，其數(shù)學(xué)模型的目標(biāo)函數(shù)、約束條件與線性規(guī)劃相同，所不同的是如果整數(shù)線性規(guī)劃問題的所有決策變量僅限于取0或1兩個值，則稱此問題為0-1整數(shù)規(guī)劃，簡稱為0-1規(guī)劃，把只能取0或1值的變量稱為0-1變量。其一般的數(shù)學(xué)模型為3 ：其中為0-1變量，也稱二進(jìn)制變量、邏輯變量。僅取值0或1這個條件可由下述約束條件所代替。，為整數(shù)，它和一般整數(shù)線性規(guī)劃的約束條件形式是一致的。另一種形式為4：引進(jìn)0-1變量：及資源單位數(shù)向量：則可建立與實(shí)際相應(yīng)數(shù)學(xué)模型： 這兩種是常見的0-1規(guī)劃模型，可用隱枚舉法求解，有時為了求解更加快捷、方便則通常用LINGO軟件求解。3.2 求解方法(1) 隱枚舉法求解 解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，基本上此法可以從所有變量等于零出發(fā)（初始點(diǎn)），然后依次指定一些變量取值為1，直到獲得一個可行解，于是把第一個可行解記作迄今為止最好的可行解，再重復(fù)，依次檢查變量為0，1的各種組合，對迄今為止最好的可行解加以改進(jìn)，直到獲得最優(yōu)解。這就需要檢查變量取值的個組合。對于變量個數(shù)較大（例如），這幾乎是不可能的。而隱枚舉法就是在此基礎(chǔ)上改進(jìn)的，通過加入一定的過濾條件，使運(yùn)算次數(shù)減少，從而較快的求得最優(yōu)解。因此常設(shè)計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解，這樣的方法稱為隱枚舉法。其解題關(guān)鍵是尋找可行解，產(chǎn)生過濾條件（滿足目標(biāo)函數(shù)值優(yōu)于計算過的可行解目標(biāo)函數(shù)值的約束條件）。一般步驟為：1)、用試探法求出一個可行解，以它的目標(biāo)值作為當(dāng)前最好的值；2)、增加過濾條件；3)、將 按由小大排列。最小化問題反之。(2) 用LINGO求解5LINGO：Linear Interactive and General Optimizer 即“交互式的線性和通用優(yōu)化求解器”，它是一種專門用于求解最優(yōu)化問題的軟件。1）程序語言說明： LINGO程序以“MODEL”開始，以“END”結(jié)束，它們之間由語句組成，并且每個語句都是以分號“；”結(jié)尾。 在LINGO中語句順序不重要，程序中不區(qū)分大小寫，變量必須以字母開頭，以開頭的都是函數(shù)的調(diào)用。 LINGO已假定所有變量非負(fù)，可用限定變量取值范圍的函數(shù)BIN（X）（限定X為0或1）、GIN（X）（限定X為整數(shù)）、FREE（X）（取消對X的符號限制）、BND（L，X，U）（限制）改變變量的非負(fù)假定。2）邏輯運(yùn)算符：#AND#（與），#OR#（或），#NOT#（非），#EQ#(等于)、#NE#(不等于)、#GT#(大于)、#GE#(大于等于)、#LT#(小于)、#LE#(小于等于)。3）利用 LINGO 對上面第二種模型進(jìn)行編程求解，其部分程序語句如下(省略號處表示有部分程序語句省略)： 模型的設(shè)置部分，定義模型中所定義的數(shù)據(jù)結(jié)構(gòu)。sets：row/1.m/:z;建立行號集合;arrange/1.n/;建立列號集合;link(row, arrange):x, y;建立雙下標(biāo)集合,派生出效益集合X以及0-1變量集合Y; 模型的主體部分。max=sum(link(i,j):X(i,j)*y(i,j);目標(biāo)函數(shù);for(arrange (i):sum(link(j,k)|k #eq# 1:y(j,k)=1); 每個部門只取一個效益值; for(link(i,j):y(i,j)*z(i)=M;);限制條件：資源總數(shù)為;for(link(i,j):BIN(y(i,j););定義Y為0-1變量; 模型的數(shù)據(jù)部分。data:X=x(i,j);Z=z(i);enddata3.3 實(shí)例2(1) 用隱枚舉法求解實(shí)例某部門在今后五年中可用于投資的資金總額為萬元，有 個可以考慮的投資項目，假定每個項目最多投資一次，第個項目所需的資金為萬元，將會獲得的利潤為萬元。問應(yīng)如何選擇投資項目，才能使獲得的總利潤最大2。解這類問題時設(shè)投資決策變量為設(shè)獲得的總利潤為，則上述問題列出的數(shù)學(xué)模型為：例如：1、通過試探性求一個可行解，易看出 滿足約束條件，故為一個可行解，且相應(yīng)的目標(biāo)函數(shù)值為。2、因?yàn)槭乔髽O大值問題，故求最優(yōu)解時，凡是目標(biāo)值的解不必檢驗(yàn)是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個約束條件（目標(biāo)值下界）： 稱該條件為過濾條件。 從而原問題等價于 ：用隱枚舉法求解： 表4目標(biāo)值約束條件過濾條件a b c d e05 27 38 510 從而得最優(yōu)解 ，最優(yōu)值。在計算過程中，若遇到值已超過條件(a)右邊的值，應(yīng)改變條件(a)，使右邊為迄今為止最大者，然后繼續(xù)作。例如，當(dāng)檢查點(diǎn)（0，0，1）時因，所以應(yīng)將條件(a)換成。(2) 用LINGO軟件求解實(shí)例現(xiàn)有某種設(shè)備共有五臺，準(zhǔn)備分給用戶1、2、3 三個工廠，各工廠利用這些設(shè)備獲得的盈利各不相同，問如何分配這五臺設(shè)備，可以使總盈利為最大5？ 表5設(shè)備臺數(shù)各工廠產(chǎn)生的效益值123000015542151526340404048060455907050解：引進(jìn)0-1變量用LINGO軟件求解的程序代碼見附錄1，求解的結(jié)果見附錄2。由結(jié)果可知，即分配5臺給用戶1，獲得最大盈利為。4 動態(tài)規(guī)劃4.1 模型的建立動態(tài)規(guī)劃所研究的對象是多階段決策問題，所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要做出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)，每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達(dá)到最優(yōu)。設(shè)有某種資源，總數(shù)量為，用于生產(chǎn)種產(chǎn)品；若分配數(shù)量用于生產(chǎn)第種產(chǎn)品，其收益為。問應(yīng)如何分配，可使總收益最大6？ 這種資源分配問題可建立的動態(tài)規(guī)劃模型為：4.2 求解方法17基本思路：把尋求最優(yōu)策略看作連續(xù)遞推的過程，從最終階段開始，逆著實(shí)際過程的進(jìn)展方向逐段求解，在每一段求解中都要利用剛求解完那段的結(jié)果，直到初始階段求出結(jié)果，返回始點(diǎn)為止，這種求解方法叫做逆序遞推求解。gn(xn)12S1=ax1x2g1(x1)g2(x2)s2s3n nnxnsn. 圖2(1)明確問題，確定階段的劃分和階段變量。根據(jù)多階段決策問題的特點(diǎn)，將其劃分為若干個相互獨(dú)立又相互聯(lián)系的部分，每一個部分為一個階段，劃分出的每一個階段通常就是需要做出一個決策的子問題。階段通常是按決策進(jìn)行的時間或空間上的先后順序劃分的，階段變量用表示，表示把資源分配給第種產(chǎn)品的過程。(2)確定狀態(tài)、狀態(tài)變量。在多階段決策過程中，狀態(tài)是描述每個階段所必須的信息，表示每個階段開始時所處的自然狀況或客觀條件。一個階段有若干個狀態(tài)，過程的狀態(tài)用一個或一組變量來描述，狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息，用表示第個階段的狀態(tài)變量，=表示在給第種產(chǎn)品分配之前還剩有的資源量。(3)定義決策變量。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)做出的選擇。決策變量用表示，表示分配給第種產(chǎn)品的資源量。(4)正確寫出狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程,如果給定第個階段的狀態(tài)變量,則該階段的決策變量一經(jīng)確定,第階段的狀態(tài)變量的值也就可以確定。(5)確定階段指標(biāo)函數(shù)。每階段選定決策后所產(chǎn)生的效益，記。(6)確定過程指標(biāo)函數(shù)（目標(biāo)函數(shù)）。用表示第子過程的指標(biāo)函數(shù)。(7)寫出動態(tài)規(guī)劃函數(shù)基本方程:4.3 實(shí)例3 某公司擬將某種高效設(shè)備5臺分配給所屬甲、乙、丙3廠。各廠獲此設(shè)備后可產(chǎn)生的效益如下表。問應(yīng)如何分配，可使所產(chǎn)生的總效益最大?表 6工廠效益設(shè)備臺數(shù)甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12 建立動態(tài)規(guī)劃模型,并按逆序遞推法逐段求解:1、階段依次表示把設(shè)備分配給甲、乙、丙廠的過程；2、狀態(tài)表示給第個分廠分配時尚未分配出去的臺數(shù)； 3、決策表示給第個分廠分配的臺數(shù)； ；4、狀態(tài)轉(zhuǎn)移；5、階段指標(biāo)表示每階段選定決策后所產(chǎn)生的效益； 6、指標(biāo)函數(shù)；7、預(yù)計創(chuàng)立額為；8、基本方程 用列表解： 表7k 3012345012345 0+0 4+0 6+011+012+012+0046111212 0 4 6111212012345k 2 0 0 0 0+0 0 00 1 0 0 0+4 5 10 1 5 5+0 0 0 0+6 2 1 5 5+4 10 20 2 10 10+0 0 0 0+11 3 1 5 5+6 14 21 2 10 10+4 3 11 11+0 0 0 0+12 1 5 5+11 4 2 10 10+6 16 13 3 11 11+4 22 4 11 11+0 0 0 0+12 1 5 5+12 5 2 10 10+11 21 23 3 11 11+6 4 11 11+4 5 11 11+0k 15012345 0+21 3+16 7+149+1012+513+003791213 21023221最優(yōu)策略： 為0-2-3或2-2-1， 即分給甲廠0臺、分給乙廠2臺、分給丙廠3臺， 或分給甲廠2臺、分給乙廠2臺、分給丙廠1臺。最優(yōu)值：=21。5 結(jié)論本文從三個方面介紹了求解資源分配問題的方法，主要是線性規(guī)劃、0-1規(guī)劃和動態(tài)規(guī)劃。用單純形法求解簡單的線性規(guī)劃問題，用隱枚舉法和LINGO軟件求解0-1規(guī)劃問題，用逆序遞推法求解動態(tài)規(guī)劃問題。動態(tài)規(guī)劃與靜態(tài)規(guī)劃研究的對象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題，兩種規(guī)劃在很多情況下原則上是可以相互轉(zhuǎn)換的，但在解決簡單的問題時常用線性規(guī)劃求解，在解決整數(shù)問題時常用0-1規(guī)劃求解，在解決多階段決策問題和離散性問題時常用動態(tài)規(guī)劃求解，因?yàn)樵诮鉀Q這種問題時用動態(tài)規(guī)劃求解比用線性規(guī)劃或非線性規(guī)劃更加有效,并且解決時效率更高,同時易于實(shí)現(xiàn)。但是使用動態(tài)規(guī)劃方法也有一定的限制，如沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也會使問題變得復(fù)雜化，并且只適用于一些維數(shù)相當(dāng)?shù)偷膯栴}等。所以在解決資源分配問題時可以根據(jù)問題的不同類型采用不同的解題方法，對具體問題進(jìn)行具體分析，這樣就可以使問題得到更好地解決。參考文獻(xiàn)1張玉娟.資源分配問題的求解D.桂林.桂林理工大學(xué)理學(xué)院.2010.12.2刁在筠,劉桂真等.運(yùn)籌學(xué)M.北京：高等教育出版社,2007：29.3熊義杰.運(yùn)籌學(xué)教程M.(2).北京：北京國防工業(yè)出版社.2007：85.4黃政龍.資源分配問題的優(yōu)化模型轉(zhuǎn)換及其算法J.中南林業(yè)科技大學(xué)學(xué)報.第27卷：第2期.2007.4.5盧向南.應(yīng)用運(yùn)籌學(xué)M.浙江：浙江大學(xué)出版社.2005：30-33.6趙則民.運(yùn)籌學(xué)M.重慶：重慶大學(xué)出版社.2002：137.7吳慶豐.資源分配問題的動態(tài)求解方法J.淮北煤炭師范學(xué)院學(xué)報.第29卷：第2期.2008.6.附錄(用LINGO軟件求解的代碼和結(jié)果)附錄1：sets:R/1.6/:z; !建立行號集合，派生出設(shè)備臺數(shù)集合; L/1.3/; !建立列號集合;c(R,L):x,y; !建立雙下標(biāo)集合(i,j)，派生出效益集合X以及0-1變量集合Y;endsetsdata:X= 0 0 0 5 5 4 15 15 26 40 40 40 80 60 45 90 70 50;z=0 1 2 3 4 5;enddatamax=sum(c(i,j):X(i,j)*y(i,j); !目標(biāo)函數(shù);for(l(i):sum(c(j,k)|k#eq#1:y(j,k)=1); !每個工廠只取一個效益值;sum(c(i,j):y(i,j)*z(i)=5; !設(shè)備總臺數(shù)為5;for(c(i,j):BIN (y(i,j); !為0-1變量;end附錄2：Global optimal solution found. Objective value: 90.00000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost Z ( 1) 0.000000 0.000000 Z ( 2) 1.000000 0.000000 Z ( 3) 2.000000 0.000000 Z ( 4) 3.000000 0.000000 Z ( 5) 4.000000 0.000000 Z ( 6) 5.000000 0.000000 X ( 1, 1) 0.000000 0.000000 X ( 1, 2) 0.000000 0.000000 X ( 1, 3) 0.000000 0.000000 X ( 2, 1) 5.000000 0.000000X ( 2, 2) 5.000000 0.000000 X ( 2, 3) 4.000000 0.000000 X ( 3, 1) 15.00000 0.000000 X ( 3, 2) 15.00000 0.000000X ( 3, 3) 26.00000 0.000000 X ( 4, 1) 40.00000 0.000000 X ( 4, 2) 40.00000 0.000000 X ( 4, 3) 40.00000 0.000000 X ( 5, 1) 80.00000 0.000000 X ( 5, 2) 60.00000 0.000000 X ( 5, 3) 45.00000 0.000000 X ( 6, 1) 90.00000 0.000000