資源分配問(wèn)題 運(yùn)籌學(xué)實(shí)驗(yàn)報(bào)告.doc

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程名稱 ： 資源分配問(wèn)題 實(shí)驗(yàn)地點(diǎn)： 2016 年 5 月至 2016 年 6 月 專 業(yè) 班 級(jí) 學(xué)生姓名 學(xué) 號(hào) 指導(dǎo)老師 實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目：B15201301實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí) 實(shí)驗(yàn)日期：2015年5月到6月實(shí)驗(yàn)要求：梳理資源分配問(wèn)題的產(chǎn)生時(shí)間、背景，清楚資源分配問(wèn)題的原理及方法，運(yùn)用這個(gè)方法解決一個(gè)實(shí)際問(wèn)題。實(shí)驗(yàn)內(nèi)容：資源分配問(wèn)題1資源分配問(wèn)題的產(chǎn)生1.1資源分配問(wèn)題的產(chǎn)生時(shí)間由于資源分配問(wèn)題的復(fù)雜性和明顯的遞階結(jié)構(gòu)特征，資源分配問(wèn)題需要用兩層模型來(lái)描述。等人首次建立了一類兩層次多部門(mén)資源分配問(wèn)題的兩層規(guī)劃模型。該模型是按照正向主從策略、并假定下級(jí)各部門(mén)之間是相互獨(dú)立的、平等的。仲偉俊等在此基礎(chǔ)上研究了下級(jí)之間具有合作關(guān)系的資源分配問(wèn)題。杜綱等人1(1997)建立了資源分配問(wèn)題的層次激勵(lì)模型，張晉東等人2(2002)基于主從結(jié)構(gòu)的分析框架建立了資源分配問(wèn)題的變權(quán)激勵(lì)模型，提出了與之相應(yīng)的變權(quán)激勵(lì)策略。這些模型反映了資源分配本身決策變量的層次性和相互之間的聯(lián)系。但對(duì)于本文所提到的系統(tǒng)復(fù)雜性的定量描述還需要進(jìn)行進(jìn)一步的研究，兩層決策理論及有關(guān)算法就是描述這類問(wèn)題重要而基本的工具。基于以上背景，本文選擇了資源分配問(wèn)題的兩層決策模型進(jìn)行研究，以期使資源分配問(wèn)題的研究更符合現(xiàn)實(shí)，具有一般性。1.2資源分配問(wèn)題的產(chǎn)生背景資源作為工程實(shí)施和生產(chǎn)活動(dòng)等企業(yè)管理的基本要素，是企業(yè)所能控制的并能用以制定和實(shí)施戰(zhàn)略或方案、以提高效率和效果的因素，資源獲得數(shù)量的多少和資源的利用情況直接影響著企業(yè)的經(jīng)濟(jì)目標(biāo)，因此，每一個(gè)生產(chǎn)企業(yè)或工程實(shí)體都希望能夠獲得更多的資源，以實(shí)現(xiàn)他們的目標(biāo)。然而，在實(shí)際工程建設(shè)和生產(chǎn)中，在一定的時(shí)間內(nèi)，由于各方面的原因，所得到的資源總是有一定限度的，若不加考慮地使用資源，直接的后果是造成生產(chǎn)成本增加、工程費(fèi)用提高等，在資源極其短缺的情況下，還會(huì)造成工程各部門(mén)或生產(chǎn)各單位忙亂爭(zhēng)奪資源的現(xiàn)象，從而導(dǎo)致無(wú)法取得最佳經(jīng)濟(jì)目標(biāo)，造成資源的浪費(fèi)。為了充分地利用現(xiàn)有資源，以獲得最優(yōu)經(jīng)濟(jì)成果，于是就產(chǎn)生了如何分配以使工程目標(biāo)或生產(chǎn)目的達(dá)到最優(yōu)的問(wèn)題。2.原理及方法2.1兩層決策描述一般的兩層決策方法是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化方法。它包含一個(gè)上層問(wèn)題和多個(gè)下層問(wèn)題，上層問(wèn)題和下層問(wèn)題都有各自的目標(biāo)函數(shù)和約束條件。上層問(wèn)題的目標(biāo)函數(shù)和約束條件不僅與上層決策變量有關(guān)，而且還依賴于下層問(wèn)題的最優(yōu)解，而下層問(wèn)題的最優(yōu)解又受上層決策變量的影響。一般上層決策者處于一個(gè)領(lǐng)導(dǎo)和協(xié)調(diào)下層各執(zhí)行部門(mén)的地位，而下層各決策者處于執(zhí)行地位。在決策中，上層決策者有權(quán)首先確定他的決策方案，并將該信息傳遞給下層各執(zhí)行部門(mén)。決策方案的滿意與否是由上層決策者根據(jù)其自身的目標(biāo)函數(shù)決定的。兩層決策方法所描述決策問(wèn)題的決策過(guò)程是上層決策者首先宣布它的決策，這一決策將影響下層決策問(wèn)題的約束集和目標(biāo)函數(shù)。然后下層各決策者在這種限制下選取使自己的目標(biāo)函數(shù)最優(yōu)的決策，它也影響上層決策問(wèn)題的目標(biāo)函數(shù)，上層決策者再調(diào)整它的決策變量的取值，該過(guò)程不斷進(jìn)行，直至上層目標(biāo)函數(shù)達(dá)到最優(yōu)為止。國(guó)內(nèi)外對(duì)兩層決策方法的研究大多限于從理論的角度建立不同的兩層決策，模型的基礎(chǔ)上研究各種算法，將兩層決策方法用于研究解決實(shí)際問(wèn)題還很少見(jiàn)到。由于兩層決策模型的結(jié)構(gòu)和其決策過(guò)程恰好體現(xiàn)了多種資源在多個(gè)項(xiàng)目間分配問(wèn)題的遞階優(yōu)化結(jié)構(gòu)， 因此都是用于解決一個(gè)決策點(diǎn)上的決策問(wèn)題。但在實(shí)際社會(huì)生活中，存在著組織內(nèi)包含多個(gè)決策點(diǎn)的復(fù)雜決策系統(tǒng)。這種復(fù)雜系統(tǒng)通常具有多級(jí)、遞階結(jié)構(gòu)。如一個(gè)國(guó)家內(nèi)有中央、省市及縣區(qū)等不同的組織管理層次;一個(gè)企業(yè)內(nèi)有公司級(jí)、廠級(jí)、車間級(jí)的組織決策層次。在這種復(fù)雜系統(tǒng)中，由于涉及到具有主動(dòng)行為的多個(gè)決策者的決策活動(dòng)，系統(tǒng)內(nèi)部決策的分散化使各決策部門(mén)的責(zé)任、權(quán)限和利益將有明確的區(qū)別。這樣，每個(gè)決策者都有自己希望達(dá)到的一個(gè)或一組目標(biāo)。同時(shí)，系統(tǒng)中的各個(gè)決策部門(mén)之間存在各種復(fù)雜的相互促進(jìn)和相互制約的關(guān)系。如果決策者處于系統(tǒng)中的不同的級(jí)，那么處于較高級(jí)的決策部門(mén)將具有更大的權(quán)利，他通過(guò)一些調(diào)控手段來(lái)引導(dǎo)下級(jí)部門(mén)在實(shí)現(xiàn)其局部目標(biāo)的同時(shí)，使上級(jí)的目標(biāo)得到盡可能多的滿足。對(duì)這樣的復(fù)雜決策系統(tǒng)，目前主要針對(duì)兩層的，且上層只有一個(gè)決策者的情況研究分析它的模型和決策方法。2.3資源分配問(wèn)題的兩層決策任何一個(gè)現(xiàn)代化生產(chǎn)系統(tǒng)的決策過(guò)程都具有層次性，作為這個(gè)系統(tǒng)的上層管理者，總是企圖使整個(gè)系統(tǒng)取得最好的效果，而效果的產(chǎn)生是通過(guò)具體的資源分配等生產(chǎn)過(guò)程實(shí)現(xiàn)的，這就構(gòu)成了資源的分配者和資源的使用者的統(tǒng)一體。由于不同的分配方式可能產(chǎn)生不同的效果，生產(chǎn)決策者要在上層給出的資源下使效果盡可能最佳。然后，上層管理者再根據(jù)下層的反應(yīng)在可能的范圍內(nèi)作出最佳決策。于是，這種生產(chǎn)系統(tǒng)的決策過(guò)程就形成了一個(gè)二層系統(tǒng)的決策問(wèn)題。這個(gè)二層系統(tǒng)的下層是確定分配方式與生產(chǎn)效果的對(duì)應(yīng)關(guān)系，這個(gè)二層系統(tǒng)的上層則是要根據(jù)資源分配方案的效果，在可能范圍內(nèi)，調(diào)整資源分配方案使整個(gè)系統(tǒng)產(chǎn)生最好的效果。這樣，資源分配問(wèn)題本身就明顯地具有了兩層遞階結(jié)構(gòu)，根據(jù)兩層決策的決策機(jī)理，可把資源分配問(wèn)題抽象成兩層決策模型: 其中是使用資源的最佳效果函數(shù)。上述模型中，由于使用資源的最佳效果函數(shù)，有多種形式，因此，有必要進(jìn)一步明確上述模型的意義。本文對(duì)使用資源的最佳效果函數(shù)采用兩種目標(biāo)，一是以資源有限最大經(jīng)濟(jì)價(jià)值為目標(biāo)，二是以最小工期為目標(biāo)。由于資源的分配者分配資源的方案也有多種分配后產(chǎn)生的效果，因此，本文對(duì)分配方案的目標(biāo)采用相對(duì)于最大經(jīng)濟(jì)價(jià)值來(lái)說(shuō)資源總量最小。在工程應(yīng)用領(lǐng)域，采用相對(duì)于最小工期而言，整個(gè)工期的拖期最小為目標(biāo)。43.應(yīng)用實(shí)例設(shè)上層總廠有 m 種可連續(xù)變化的資源要分配給下層 p 個(gè)項(xiàng)目，每個(gè)項(xiàng)目中有用個(gè)活動(dòng)用到 m 種共享資源，且每個(gè)活動(dòng)只用到一種共享資源。下層每個(gè)項(xiàng)目擁有各自的自有資源。為簡(jiǎn)化問(wèn)題，在此不考慮每個(gè)項(xiàng)目中自有資源的分配，假定下層各項(xiàng)目中使用自有資源的活動(dòng)所需自有資源量均能滿足，且活動(dòng)持續(xù)時(shí)間不變，使用共享資源的活動(dòng)持續(xù)時(shí)間由所分配到的資源量決定。設(shè)使用共享資源的活動(dòng)持續(xù)時(shí)間與資源分配量成反比關(guān)系如2臺(tái)機(jī)器干6天，4臺(tái)機(jī)器就干3天 。那么活動(dòng)持續(xù)時(shí)間=活動(dòng)工作量資源量。上層以 p 個(gè)項(xiàng)目均在各自的預(yù)定工期內(nèi)完成，消耗的共享資源總量最小為目標(biāo)，下層 p 個(gè)項(xiàng)目都以工期最短為目標(biāo)。下層各項(xiàng)目的進(jìn)度計(jì)劃分別用網(wǎng)絡(luò)計(jì)劃表示。為了便于將下層求最短工期問(wèn)題用線性規(guī)劃表示，在此用雙代號(hào)網(wǎng)絡(luò)圖表示下層各項(xiàng)目。設(shè)第 k 個(gè)項(xiàng)目中共有Nk 個(gè)活動(dòng)，用雙代號(hào)法表示有Mk 個(gè)節(jié)點(diǎn)。由此描述資源在多項(xiàng)目間分配問(wèn)題的數(shù)學(xué)模型如下： （a） （b） （c） （d） （e） （f） （g） （h）式中，(a)式為上層決策者的目標(biāo)函數(shù)，該式中第一項(xiàng)代表各個(gè)項(xiàng)目的生產(chǎn)周期相對(duì)于指定完工期的拖期；第二項(xiàng)為一輔助目標(biāo)，為一任意小的正數(shù)(如10-4)。在目標(biāo)函數(shù)中加上該項(xiàng)是由于下層決策問(wèn)題的目標(biāo)函數(shù)是工期最短，那么存在這樣一種情況，當(dāng)網(wǎng)絡(luò)計(jì)劃中使用共享資源的 m個(gè)活動(dòng)有一個(gè)或幾個(gè)不在網(wǎng)絡(luò)的關(guān)鍵路線上時(shí)，該活動(dòng)所分配到的資源在一定范圍內(nèi)變化將不影響整個(gè)工期，出現(xiàn)解的不唯一性。為了克服解的不唯一性，在上層目標(biāo)函數(shù)中加入要求資源消耗量最小的輔助目標(biāo)。Tk 為第 k 個(gè)項(xiàng)目的網(wǎng)絡(luò)計(jì)劃最短工期； 為第 k個(gè)項(xiàng)目要求的預(yù)定工期；Rkl 為分配給第 k 個(gè)項(xiàng)目的第 l 種共享資源量；為第l種共享資源總量；(b)、(c)式表示共享資源約束；(d)式為下層第 k 個(gè)決策者的目標(biāo)函數(shù)，它代表第 k 個(gè)項(xiàng)目的工期， 為第 k 個(gè)項(xiàng)目工期受第 m 項(xiàng)目影響的系數(shù)，為第 k 個(gè)項(xiàng)目中事項(xiàng)i的實(shí)現(xiàn)時(shí)間；為第 k 種活動(dòng)的持續(xù)時(shí)間，為 0-1變量，當(dāng)?shù)趉個(gè)項(xiàng)目存在活動(dòng)時(shí)為 1，否則為 0。為第 k個(gè)項(xiàng)目中使用共享資源的活動(dòng)工作量；Kij，t為的客各項(xiàng)目中自有資源確定的時(shí)間。(e)式表示第 k 個(gè)項(xiàng)目網(wǎng)絡(luò)計(jì)劃中緊前關(guān)系約束；（f）為第 k 個(gè)項(xiàng)目中各活動(dòng)的時(shí)間。在上述模型中，式(a)(c)是上層決策者面對(duì)的決策問(wèn)題。他們所要解決的問(wèn)題是在m種資源總量一定的情況下，如何將它們分配給 p個(gè)項(xiàng)目，使 p 個(gè)項(xiàng)目都能在預(yù)定工期內(nèi)完成，且消耗的共享資源總量最小。式(d)( h)是下層第 k項(xiàng)目負(fù)責(zé)人面臨的問(wèn)題，它所要解決的問(wèn)題是根 。據(jù)上層決策者給定的資源量來(lái)制定自己的進(jìn)度計(jì)劃，其目標(biāo)是使自己的項(xiàng)目工期盡可能短。整個(gè)模型描述的決策過(guò)程是上層決策者首先給出一個(gè)資源分配方案，下層p個(gè)決策者利用所分配到的資源求出各自的最短工期，并將結(jié)果返回給上層決策者。上層決策者根據(jù)其目標(biāo)函數(shù)的要求調(diào)整資源分配方案，該過(guò)程持續(xù)進(jìn)行，直到上層決策者的目標(biāo)函數(shù)達(dá)到最優(yōu)為止。參考文獻(xiàn)1仲偉俊，徐南榮.具有合作關(guān)系的多人遞階資源分配問(wèn)題研究J，系統(tǒng)-1.程理論與實(shí)踐，1993；2杜綱，顧培亮.資源分配問(wèn)題的層次激勵(lì)模型仁，管理工程學(xué)報(bào)，1997；3 張晉東，杜綱.資源分配問(wèn)題的變權(quán)激勵(lì)模型J，數(shù)量經(jīng)濟(jì)技術(shù)經(jīng)濟(jì)研究2002；4毛瑞友，資源最優(yōu)分配模型的研究與應(yīng)用D，中國(guó)地質(zhì)大學(xué)（北京），2007。實(shí)驗(yàn)總結(jié)在對(duì)資源分配問(wèn)題進(jìn)行全面胡了解后，可以知道目前對(duì)資源分配問(wèn)題的研究從以下幾個(gè)方面入手:定量資源的最優(yōu)利用問(wèn)題，這類問(wèn)題是研究如何把有限的資源分配于不同產(chǎn)品的生產(chǎn)，以取得最大收益。其實(shí)質(zhì)是在生產(chǎn)資料數(shù)量既定的條件下，如何選擇生產(chǎn)部門(mén)，確定生產(chǎn)規(guī)模，尋求產(chǎn)品與產(chǎn)品之間的最佳組合，以取得最大經(jīng)濟(jì)效益問(wèn)題；多階段資源分配問(wèn)題，這類問(wèn)題是研究將數(shù)量一定的可回收資源投入到某種生產(chǎn)方式中，在一段時(shí)間內(nèi)組織生產(chǎn)使該段時(shí)間內(nèi)總收益最大的問(wèn)題；隨機(jī)可重復(fù)資源分配問(wèn)題，這類問(wèn)題是研究對(duì)動(dòng)態(tài)隨機(jī)到達(dá)的任務(wù)，在確定時(shí)間限制內(nèi)如何分配其可重復(fù)使用資源的決策問(wèn)題；有限資源合理分配問(wèn)題，在資源有限制的前提下，力求使活動(dòng)網(wǎng)絡(luò)的總工期最短的問(wèn)題。資源分配問(wèn)題是一個(gè)在理論上具有相當(dāng)難度、在實(shí)踐上富有復(fù)雜性的問(wèn)題，不但涉及上下級(jí)的多個(gè)目標(biāo)、下級(jí)之間的合作關(guān)系，也涉及上級(jí)對(duì)下級(jí)的權(quán)利影響等，本文在研究多下級(jí)資源分