信息與計(jì)算機(jī)科學(xué)畢業(yè)論文

1、本科畢業(yè)論文本科畢業(yè)論文(設(shè)計(jì)設(shè)計(jì))生活中的一些最優(yōu)化問題研究生活中的一些最優(yōu)化問題研究院院 （系）（系）數(shù)學(xué)與計(jì)算科學(xué)學(xué)院專專 業(yè)業(yè)信息與計(jì)算科學(xué)學(xué)學(xué) 號(hào)號(hào)08251001133學(xué)生姓名學(xué)生姓名游佳能指導(dǎo)教師指導(dǎo)教師柴嘯龍?zhí)峤蝗掌谔峤蝗掌?012 年 5 月 20 日2012-jx16-廣廣 東東商學(xué)院商學(xué)院畢業(yè)論文畢業(yè)論文( (設(shè)計(jì)設(shè)計(jì)) )成績(jī)?cè)u(píng)定表成績(jī)?cè)u(píng)定表畢業(yè)論文（設(shè)計(jì)）指導(dǎo)教師評(píng)語及成績(jī)畢業(yè)論文（設(shè)計(jì)）指導(dǎo)教師評(píng)語及成績(jī)成績(jī)成績(jī) 指導(dǎo)教師簽名指導(dǎo)教師簽名 年年 月月 日日畢業(yè)論文（設(shè)計(jì)）復(fù)評(píng)教師評(píng)語及成績(jī)畢業(yè)論文（設(shè)計(jì)）復(fù)評(píng)教師評(píng)語及成績(jī)成績(jī)成績(jī) 復(fù)評(píng)教師簽名復(fù)評(píng)教師簽名 年年 月

2、月 日日畢業(yè)論文（設(shè)計(jì)）答辯評(píng)語及成績(jī)畢業(yè)論文（設(shè)計(jì)）答辯評(píng)語及成績(jī)成績(jī)成績(jī) 答辯委員會(huì)主席簽名答辯委員會(huì)主席簽名 年年 月月 日日畢業(yè)論文（設(shè)計(jì)）總成績(jī)（五級(jí)記分制）畢業(yè)論文（設(shè)計(jì)）總成績(jī)（五級(jí)記分制） 院（系）負(fù)責(zé)人簽名院（系）負(fù)責(zé)人簽名 年年 月月 日日title: some optimization problem research in lifemajor: information and computing scienceapplicant: jia-neng yousupervisor: xiao-long chai內(nèi)容摘要內(nèi)容摘要數(shù)學(xué)與我們?nèi)粘Ｉ蠲芮邢嚓P(guān)，日常生活中的許多問題

3、來源于數(shù)學(xué)思想的應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常當(dāng)中可能出現(xiàn)的數(shù)學(xué)問題，通過適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。本文的主要研究方向是通過對(duì)日常生活中經(jīng)常涉及到的若干最優(yōu)化問題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原理并將其推廣應(yīng)用到其他生活案例當(dāng)中去。本文的主要貢獻(xiàn)是通過對(duì)運(yùn)輸成本問題和效益分配問題的最優(yōu)化分析，詳細(xì)地介紹了表上作業(yè)法和 shapley 值法的求解過程，指出了模型存在的缺陷和不足，并對(duì)模型進(jìn)行修改以及推廣應(yīng)用。關(guān)鍵詞關(guān)鍵詞: : 最優(yōu)化；表上作業(yè)法；shapley 值；推廣應(yīng)用abstractmathematics to our daily lives

4、 are closely related to many of the problems in our daily life from the application of mathematical thinking. master the mathematical basis of the premise of the mathematical problems that may arise in day-to-day which, through appropriate planning arrangements, the use of mathematical principles fo

5、r solving optimization program effective.the main research directions to daily life often related to certain optimization problem to summarize,analyze its mathematical principles involved and promote the application to which the case of other life to go.the main contribution of this paper is the opt

6、imization analysis on transportation costs and efficiency of the distribution of the mostdetailed description of the solution process of the tabular method and the shapley value,pointed out that the model defects and deficiencies,and to modify the model and application.keywords: optimization; tabula

7、r method; shapley method; application廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究目目 錄錄1 1 研究的意義研究的意義與與目的目的 .1 12 2 研究現(xiàn)狀分析研究現(xiàn)狀分析 .1 12.1 研究的方法 .12.2 研究現(xiàn)狀 .23 3 本文研究方向本文研究方向 .2 23.1 運(yùn)輸調(diào)配方向 .33.2 效益分配方向.34 4 運(yùn)輸調(diào)配問題最優(yōu)化研究運(yùn)輸調(diào)配問題最優(yōu)化研究 .3 34.1 初始方案的給定 .44.2 最優(yōu)性檢驗(yàn)與方案的調(diào)整 .64.3 表上作業(yè)法的總結(jié) .84.4 表上作業(yè)法的改進(jìn)及其推廣應(yīng)用 .95 5 效益分配問題最優(yōu)化研究效

8、益分配問題最優(yōu)化研究 .12125.1 n 人合作對(duì)策和 shapley 值.125.2 shapley 值的推廣應(yīng)用.145.3 shapley 值法存在的缺陷.165.4 其他求解方法.175.4.1 協(xié)商解 .175.4.2 raiffa 解 .186 6 傳統(tǒng)模型的改進(jìn)設(shè)想傳統(tǒng)模型的改進(jìn)設(shè)想 .18186.1 最小元素法的改進(jìn)設(shè)想 .186.2 效益分配的改進(jìn)設(shè)想 .207 7 總結(jié)與展望總結(jié)與展望 .20207.1 本文的主要貢獻(xiàn) .207.2 本文主要的改進(jìn)方案 .217.3 研究展望 .21參考文獻(xiàn)參考文獻(xiàn) .2222致謝致謝 .2323廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些

9、最優(yōu)化問題研究第第 1 1 頁頁生活中的一些最優(yōu)化問題研究生活中的一些最優(yōu)化問題研究1 1 研究的意義與目的研究的意義與目的最優(yōu)化問題，是指在日常生活中通過適當(dāng)?shù)囊?guī)劃安排，使得完成一件事所用的費(fèi)用最少、路線最短、時(shí)間最短、產(chǎn)值最高、容積最大等的效率與分配問題，也就是要在各種方案中，尋求一個(gè)最節(jié)約、合理的方案。解決這類問題要注意兩點(diǎn): 一是明確問題，即通過問題描述中已知的數(shù)量關(guān)系把生活問題轉(zhuǎn)化為單純的數(shù)學(xué)問題，我們稱之為數(shù)學(xué)建模的過程；二是建模后的求解問題，即用相關(guān)的數(shù)學(xué)知識(shí)求解出最優(yōu)的處理方案1。數(shù)學(xué)與我們?nèi)粘Ｉ蠲芮邢嚓P(guān)，日常生活中的許多問題來源于數(shù)學(xué)思想的應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)的前提下

10、，結(jié)合日常生活當(dāng)中可能出現(xiàn)的數(shù)學(xué)問題，通過適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。本文通過對(duì)日常生活中經(jīng)常涉及到的若干最優(yōu)化問題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原理并將其推廣應(yīng)用到其他生活案例當(dāng)中去2。因而，引導(dǎo)學(xué)生學(xué)習(xí)應(yīng)用數(shù)學(xué)，從眾多的解決方案中尋求到最優(yōu)化的方案，使他們感受到數(shù)學(xué)的應(yīng)用價(jià)值，是一種能夠調(diào)動(dòng)高校學(xué)生積極學(xué)習(xí)數(shù)學(xué)的辦法3。2 2 研究現(xiàn)狀分析研究現(xiàn)狀分析2.1 研究的方法不同類型的最優(yōu)化問題可以有不同的最優(yōu)化方法，即使同一類型的問題也可有多種最優(yōu)化方法。反之，某些最優(yōu)化方法可適用于不同類型的模型。目前，最優(yōu)化問題的求解方法大致可分成解析法、直接法、數(shù)值計(jì)算法。解

11、析法：這種方法只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過必要條件將問題簡(jiǎn)化，廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 2 2 頁頁因此也稱間接法。直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時(shí)，無法用解析法求必要條件。此時(shí)可采用直接搜索的方法經(jīng)過若干次迭代搜索到最優(yōu)點(diǎn)。這種方法常常根據(jù)經(jīng)驗(yàn)或通過試驗(yàn)得到所需結(jié)果。對(duì)于一維搜索(單變量極值問題)，主要用消去法或多項(xiàng)式插值法；對(duì)于多維搜索問題(多變量極值問題)主要應(yīng)用爬山法。數(shù)值計(jì)算法：這

12、種方法也是一種直接法。它以梯度法為基礎(chǔ)，所以是一種解析與數(shù)值計(jì)算相結(jié)合的方法4。2.2 研究現(xiàn)狀最優(yōu)化一般可以分為最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。最優(yōu)設(shè)計(jì):世界各國(guó)工程技術(shù)界,尤其是飛機(jī)、造船、機(jī)械、建筑等部門都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問題得到解決5。最優(yōu)計(jì)劃:現(xiàn)代國(guó)民經(jīng)濟(jì)或部門經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開始應(yīng)用最優(yōu)化方法。一個(gè)重要的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門進(jìn)行各種優(yōu)化決策。最優(yōu)管理：一般在日常生產(chǎn)計(jì)劃的制訂

13、、調(diào)度和運(yùn)行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務(wù),用最短時(shí)間達(dá)到目標(biāo);再如飛機(jī)、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。計(jì)算機(jī)接口裝置不斷完善和優(yōu)化方法的進(jìn)一步發(fā)展，還為計(jì)算機(jī)在線生產(chǎn)控制創(chuàng)造了有利條件。最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制6。3 3 本文研究方向本文研究方向雖然現(xiàn)今最優(yōu)化問題研究漸趨成熟，也應(yīng)用到很多不同的領(lǐng)域，但對(duì)日常生活存在的最優(yōu)化問題的研究仍存在一

14、定的空缺。本文將通過對(duì)日常生活中經(jīng)常涉及到的一些最優(yōu)化問題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原理并將其推廣應(yīng)用到其他生活案例當(dāng)中去。因而，如何運(yùn)用最優(yōu)化原理解決生活中存在的實(shí)際問題將是本文研究的主要方向，主要針對(duì)生活中的運(yùn)輸成本問題和效益公平分配問題進(jìn)行研究分析7。廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 3 3 頁頁3.1 運(yùn)輸調(diào)配方向運(yùn)輸成本問題涉及了很多生活領(lǐng)域，生產(chǎn)運(yùn)輸、物流運(yùn)輸、倉庫調(diào)配等等，但其主要的數(shù)學(xué)模型都是相似的，因此掌握這種問題的解決方法有著重要的作用。文中通過對(duì)生產(chǎn)運(yùn)輸問題進(jìn)行分析，運(yùn)用表上作業(yè)法列出詳細(xì)的求解過程，并進(jìn)行推廣應(yīng)用8。3.2 效益分配方向

15、在日常的社會(huì)生活中，若干實(shí)體相互合作結(jié)成聯(lián)盟或集團(tuán)，常能比個(gè)體單獨(dú)行動(dòng)獲得更多的經(jīng)濟(jì)利益或社會(huì)效益。但是效益公平分配問題經(jīng)常成為他們合作的阻礙，如何合理地分配這些效益是促進(jìn)合作的前提，也能給合作帶來更多的效益。文中通過對(duì)合作效益分配問題進(jìn)行分析研究，運(yùn)用 shapley 法列出詳細(xì)的求解過程，并對(duì)模型進(jìn)行修改推廣。4 4 運(yùn)輸調(diào)配問題最優(yōu)化研究運(yùn)輸調(diào)配問題最優(yōu)化研究運(yùn)輸問題是社會(huì)經(jīng)濟(jì)生活和軍事活動(dòng)中經(jīng)常出現(xiàn)的優(yōu)化問題，是特殊的線性規(guī)劃問題，它是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。最早研究這類問題的hitchcock以及后來的koopmans獨(dú)立地提出運(yùn)輸問題并詳細(xì)地對(duì)該問題加以討論；同時(shí)kahto

16、pobny也圍繞著運(yùn)輸問題作了大量的研究，因此運(yùn)輸問題又稱為hitchcock問題或kantorvich問題。運(yùn)輸問題不僅代表了物資合理調(diào)運(yùn)、車輛合理調(diào)度等問題，有些其他類型的問題經(jīng)過適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問題，如指派問題、最短路問題、最小費(fèi)用流問題可轉(zhuǎn)化為運(yùn)輸問題或轉(zhuǎn)運(yùn)問題9。運(yùn)輸問題在運(yùn)籌學(xué)教學(xué)過程中占有重要地位，并且得到了眾多學(xué)者的廣泛關(guān)注，取得了許多重要的研究成果。但就在常用的運(yùn)籌學(xué)教材中僅僅介紹運(yùn)輸問題的基礎(chǔ)知識(shí)，對(duì)于運(yùn)輸問題的前沿發(fā)展涉及甚少，這遠(yuǎn)遠(yuǎn)不能反映當(dāng)前對(duì)運(yùn)輸問題的深入研究。為此，在介紹運(yùn)輸問題的基本理論和方法的基礎(chǔ)上，運(yùn)用表上作業(yè)法對(duì)類似問題進(jìn)行推廣運(yùn)用10?！纠?1

17、】某食品加工公司經(jīng)銷的主要產(chǎn)品之一是酸奶。該公司下面設(shè)有三個(gè)加工廠，每天酸奶的生產(chǎn)量分別為：，。該公司把這些酸17at24at39at奶分別運(yùn)往四個(gè)地區(qū)的門市部進(jìn)行銷售，各地區(qū)每天的銷售量分別為：，。已知從每個(gè)加工廠到對(duì)應(yīng)的各銷售門市部13bt26bt35bt46bt廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 4 4 頁頁每噸酸奶的運(yùn)價(jià)如表 4-1 所示，問該食品公司該如何調(diào)運(yùn)，在滿足各門市部銷售需要的前提下，使得總運(yùn)費(fèi)支出達(dá)到最少。表 4-1 1b2b3b4b1a2a3a3 11 3 101 9 2 87 4 10 5以下運(yùn)用表上作業(yè)法求解運(yùn)輸問題，首先給出一個(gè)初始方案，一

18、般來講，這個(gè)方案不會(huì)是最好的。因此需要給出一個(gè)判別準(zhǔn)則，并對(duì)初始方案通過不斷地調(diào)整、改進(jìn)，一直到求得最優(yōu)方案為止10。先列出這個(gè)問題的的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，見表 4-2 和表 4-3表 4-2 產(chǎn)銷平衡表 1b2b3b4b產(chǎn)量1a2a3a749銷量3 6 5 6表 4-3 單位運(yùn)價(jià)表 1b2b3b4b1a2a3a3 11 3 101 9 2 87 4 10 54.1 初始方案的給定給定初始方案的方法有很多，一般希望方法簡(jiǎn)便易行，盡量能給出較好的方案，減少迭代的次數(shù)，這里采用最小元素法。最小元素法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，依此類推，一直到給出全部方案為

19、止10。門市部加工廠銷地產(chǎn)地銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 5 5 頁頁第一步：從表 4-3 的單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為 1（如果有兩個(gè)最小運(yùn)價(jià)時(shí)任選其一） ，即從生產(chǎn)的酸奶首先供應(yīng)需求。由于每天生產(chǎn) 4t，每天2a1b2a1b需要 3t,即每天生產(chǎn)的除了要滿足全部需求之外，還剩下 1t。因此在表 4-2a1b2 中（，）的交叉格中填上數(shù)字 3，表示調(diào)運(yùn) 3t 酸奶給，再在表 4-32a1b2a1b中將所在的這一列運(yùn)價(jià)劃去，表示已經(jīng)滿足的需求，無需繼續(xù)調(diào)運(yùn)給它。1b1b第一步得到的結(jié)果如表 4-4 和表 4-5 所示。表 4-4 1b2b3b4b產(chǎn)量1a

20、2a3a3749銷量3 6 5 6表 4-5 1b2b3b4b1a2a3a3 11 3 101 9 2 87 4 10 5第二步：從表 4-5 中未劃去的元素之中找出最小的運(yùn)價(jià)為 2，即每天剩余的2a酸奶要供應(yīng)給。每天需要 5t，每天只能供應(yīng) 1t，因此在表 4-4（，3b3b2a2a）交叉處填寫 1，劃去表 4-5 所在的這一行運(yùn)價(jià)，表示生產(chǎn)的酸奶已3b2a2a分配完，其結(jié)果見表 4-6 和表 4-7.表 4-6 1b2b3b4b產(chǎn)量1a2a3a3 1749銷量3 6 5 6銷地產(chǎn)地銷地產(chǎn)地銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 6 6 頁頁表 4-7 1b2b

21、3b4b1a2a3a3 11 3 101 9 2 87 4 10 5第三步：同理再從表 4-7 中未劃去的元素之中找出最小的元素為 3，即生產(chǎn)1a的酸奶應(yīng)優(yōu)先滿足需求。每天生產(chǎn) 7t，還缺 4t。因此在表中3b1a3b（，）交叉格內(nèi)填上 4，由于的需求此時(shí)已經(jīng)滿足，在表 4-7 中劃去1a3b3b所在列的元素。3b這樣一步一步地進(jìn)行下去，直到單位運(yùn)價(jià)表上所有元素都被劃去為止，這時(shí)在產(chǎn)銷平衡表上可以得到一個(gè)調(diào)動(dòng)方案（見表 4-8） ，這個(gè)調(diào)動(dòng)方案總的運(yùn)費(fèi)為 86元。表 4-8 1b2b3b4b產(chǎn)量1a2a3a 4 33 1 6 3749銷量3 6 5 64.2 最優(yōu)性檢驗(yàn)與方案的調(diào)整最小元素法給

22、出的是運(yùn)輸問題的一個(gè)基可行解，需要通過最優(yōu)性檢驗(yàn)判別該解的目標(biāo)函數(shù)值是否達(dá)到最優(yōu)，當(dāng)為否時(shí)，應(yīng)進(jìn)行調(diào)整得到優(yōu)化。檢驗(yàn)的方法常用的有閉回路法和位勢(shì)法，這里采用閉回路法。運(yùn)輸問題中的閉回路是指調(diào)運(yùn)方案中的一個(gè)空格和幾個(gè)有數(shù)字格的水平和垂直之間的連線包圍成的封閉回路11。 構(gòu)建閉回路是為了計(jì)算解中各非基變量（對(duì)應(yīng)空格）的檢驗(yàn)數(shù)，方法是令某一非基變量取值為 1，通過變動(dòng)原基變量的值找出一個(gè)的可行解，將其與原來的基可行解進(jìn)行比較。在表 4-8 中給出了一個(gè)調(diào)運(yùn)方案中， （，）是空1a1b銷地產(chǎn)地銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 7 7 頁頁1格，即為非基變量。令，相應(yīng)

23、地為了找到新的可行解，原有基變量中11x111x 需減 1，加 1，減 1，見表 4-9。表中由（，） ， （，） ，13x23x21x1a1b1a3b（，） ， （，）4 個(gè)格的水平和垂直連線圍成的閉回路，該閉回路除（2a3b2a1b，）為空格之外， （，） ， （，） ， （，）均有數(shù)字的格。將1a1b1a3b2a3b2a1b新可行解與原來解費(fèi)用比較：從 0 變成 1，運(yùn)費(fèi)加 3 元，減 1，運(yùn)費(fèi)減少11x13x3 元，加 1，運(yùn)費(fèi)加 2 元，減 1，運(yùn)費(fèi)減少 1 元，由此新可行解較原來解23x21x運(yùn)費(fèi)增加了（3-3+2-1）=1 元，稱為檢驗(yàn)數(shù)，將其填入檢驗(yàn)數(shù)表中（表 4-10）的（，

24、）相應(yīng)的交叉格位置。類似地（，）為空格，可通過該空格找1a1b3a1b出一條其余頂點(diǎn)都有數(shù)字格的閉回路，求得其相應(yīng)的檢驗(yàn)數(shù)為（7-1+2-3+10-5）=10，將其填入檢驗(yàn)數(shù)表 4-10 的（，）的交叉格位置，因?yàn)槿我獾姆?a1b基向量均可表示為基向量的唯一線性組合，因此通過任一空格可以找到，并且只能找到唯一的閉回路，并計(jì)算得到對(duì)應(yīng)表 4-8 中解全部非基變量的檢驗(yàn)數(shù)12。表 4-91b2b3b4b產(chǎn)量1a（+1）4（-1）372a3（-3）1（+1）43a639銷量3656表 4-10 檢驗(yàn)數(shù)表 1b2b3b4b1a2a3a12 1 -110 12銷地產(chǎn)地332銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科

25、學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 8 8 頁頁如果檢驗(yàn)數(shù)表中所有的數(shù)字都大于等于零，表明對(duì)調(diào)運(yùn)方案作出任何改變都不會(huì)導(dǎo)致運(yùn)費(fèi)減少，即給定的方案為最優(yōu)方案。但在表 4-10 中， （,）2a4b格的檢驗(yàn)數(shù)是負(fù)的，說明方案仍需進(jìn)一步調(diào)整。改進(jìn)的方法是從檢驗(yàn)數(shù)為負(fù)數(shù)的格出發(fā)（當(dāng)存在兩個(gè)以上負(fù)數(shù)檢驗(yàn)數(shù)時(shí)，從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)格出發(fā)） ，這里是從（,）格出發(fā)，作一條除該空格以外其余頂點(diǎn)都為有數(shù)字格而組2a4b成的閉回路。在這條閉回路上，按照以上講的方法對(duì)運(yùn)量作最大限度的調(diào)整。從表 4-9 看出，為了把生產(chǎn)的酸奶調(diào)運(yùn)給，就要相應(yīng)減少調(diào)運(yùn)給的2a4b2a3b酸奶和調(diào)運(yùn)給的酸奶，才能得到新的平衡。這兩

26、個(gè)格內(nèi)，較小運(yùn)量為 1，1a4b因此最多只能調(diào)運(yùn) 1t 酸奶給。由此得到一個(gè)新的調(diào)運(yùn)方案（見表 4-11） 。2a4b這個(gè)新方案的運(yùn)費(fèi)為 85 元。表 4-11 1b2b3b4b產(chǎn)量1a2a3a 5 23 1 6 3749銷量3 6 5 6表 4-11 給出的調(diào)運(yùn)方案是否達(dá)到最優(yōu)，仍需對(duì)這個(gè)方案的每一個(gè)空格求出其檢驗(yàn)數(shù)（見表 4-12） 。由于檢驗(yàn)數(shù)表中所有的檢驗(yàn)數(shù)大于等于零，因此肯定表 4-11 給出的方案是最優(yōu)方案。表 4-12 檢驗(yàn)數(shù)表 1b2b3b4b1a2a3a0 22 19 124. 3 表上作業(yè)法的總結(jié)運(yùn)輸問題成本最優(yōu)化解決方法主要有三個(gè)步驟，可以用以下流程圖總結(jié)出來，見圖 4-

27、1。銷地產(chǎn)地銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 9 9 頁頁否分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案求檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)用閉回路調(diào)整，得出新的調(diào)運(yùn)方案得到最優(yōu)方案算出總的運(yùn)價(jià)是圖 4-1 表上作業(yè)法計(jì)算步驟框圖4.4 表上作業(yè)法的改進(jìn)及其推廣應(yīng)用前面所講的表上作業(yè)法的計(jì)算理論，都是以產(chǎn)銷平衡為前提的，即。但實(shí)際問題中大部分產(chǎn)銷是不平衡的。為了更好地應(yīng)用表上作業(yè)11mnijijab法，就需要把產(chǎn)銷不平衡的問題轉(zhuǎn)化成產(chǎn)銷平衡的問題13。當(dāng)產(chǎn)大于銷時(shí)，運(yùn)輸問題的數(shù)學(xué)模型可寫為11mnijijab() (4.1a)11minmn

28、ijijijzc xs.t.廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1010 頁頁11(1,.,)(4.1 )(1,., )(4.1 )0(4.1 )nijijmijjiijxa imbxbjncxd如果總的產(chǎn)量大于銷量，可以考慮多余的物資在那一個(gè)產(chǎn)地庫存的。設(shè)是,1i nx產(chǎn)地的庫存量，于是可以得到ia (4.2)1,111nniji nijjjxxxa(1,.,)im (4.3)1mijjixb(1,., )jn,11111mmni nijniijxabb令 (4.4)ijijcc (1,.,;1,., )im jn 0ijc (1,.,;1,.,1)im jn將(4

29、.2)-(4.4)分別代入或替換(4.1a)-(4.1d)，得到 (4.5a)1,11111111minmnmnmmnijijijiji niijijijijiijzc xc xcxcxs.t111(1,.,)(4.5 )(1,., )(4.5 )0(4.5 )nijjmijjiijxa imbxbjncxd由于（4.5）模型中，是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。因11111mnniiniijjabbb此當(dāng)產(chǎn)量大于銷量時(shí)，只需增加一個(gè)假想的銷地 j=n+1(實(shí)際上庫存銷地的單位運(yùn)價(jià)，就可以轉(zhuǎn)化成為一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。類似地，當(dāng)銷量大于,10i nc產(chǎn)量時(shí)，可以在產(chǎn)銷平衡中增加一個(gè)假想的產(chǎn)地，該地產(chǎn)

30、量為1im廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1111 頁頁，在單位運(yùn)價(jià)表中令從該假想產(chǎn)地到各銷地的運(yùn)價(jià)，同11()nmjijiba1,0mjc樣可以轉(zhuǎn)化成為一個(gè)產(chǎn)銷平衡的運(yùn)輸問題?！纠?2】設(shè)有三個(gè)產(chǎn)地生產(chǎn)某種物資，三個(gè)產(chǎn)地的產(chǎn)量分別為123,a a a7t、5t、7t，四個(gè)銷地需要該種物資，銷量分別為1234,b b b b2t、3t、4t、6t，又知各產(chǎn)銷地之間的單位運(yùn)價(jià)見表 4-13，試解出總運(yùn)費(fèi)最少的調(diào)動(dòng)方案。表 4-13 單位運(yùn)價(jià)表 1b2b3b4b1a2a3a2 11 3 410 3 5 97 8 1 2【解】產(chǎn)地總產(chǎn)量為 19t，銷地總銷量為 15t，

31、因此這是產(chǎn)銷不平衡的運(yùn)輸問題。可按照上述方法轉(zhuǎn)化成為產(chǎn)銷平衡的運(yùn)輸問題，轉(zhuǎn)化之后其產(chǎn)銷平衡表和單位運(yùn)價(jià)表分別見表 4-14、見表 4-15.表 4-14 產(chǎn)銷平衡表 庫存1b2b3b4b產(chǎn)量1a2a3a757銷量2 3 4 6 4表 4-15 單位運(yùn)價(jià)表 庫存1b2b3b4b1a2a3a2 11 4 4 010 3 9 9 07 8 2 2 0銷地產(chǎn)地銷地產(chǎn)地銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1212 頁頁對(duì)表 4-14、表 4-15 可以用表上作業(yè)法計(jì)算求出最優(yōu)方案如表 4-16表 4-16 最優(yōu)方案 庫存1b2b3b4b產(chǎn)量1a2a3a2 3 2 3 2

32、 4 3757銷量2 3 4 6 45 5 效益分配問題最優(yōu)化研究效益分配問題最優(yōu)化研究在日常的社會(huì)生活中若干實(shí)體（如個(gè)人、公司、協(xié)會(huì)等）相互合作結(jié)成聯(lián)盟或集團(tuán)，常能比個(gè)體單獨(dú)行動(dòng)獲得更多的經(jīng)濟(jì)利益或社會(huì)效益。但是效益公平分配問題經(jīng)常成為他們合作的阻礙，如何合理地分配這些效益是促進(jìn)合作的前提，也能給合作帶來更多的效益14?！纠?3】設(shè)有甲乙丙三人經(jīng)商。若單獨(dú)經(jīng)營(yíng)，每人僅能獲利 1 萬元；甲乙合作可獲利 7 萬元；甲丙合作可獲利 5 萬元；乙丙合作可獲利 4 萬元；三人合作則可獲利 11 萬元。問三人合作時(shí)怎么合理地分配 11 萬元的收入?！窘狻吭O(shè)甲乙丙三人各得萬元，從題目中給定的條件我們可列出

33、滿足條123,x x x件的一組方程12311xxx123121323,1,7,5,4x x xxxxxxx根據(jù)上述這兩組方程可求出許多組滿足條件的解組，如等123()(5,3,3),(4,4,3),(4,3.5,3.5)xxx這種求解的方案最為普遍，但仍存在一定的局限性，當(dāng)條件不夠多的時(shí)無法求出最優(yōu)的解組。以下將介紹一種其他的方法求解這類問題。5.1 n 人合作對(duì)策和 shapley 值n 個(gè)人從事一項(xiàng)經(jīng)濟(jì)活動(dòng)，對(duì)于他們之中的若干人組合的每一種合作（單人也視為一種合作） ，都可以得到一定的效益，僅當(dāng)人們之間的利益是非對(duì)抗性時(shí)，合作中人數(shù)的增加不會(huì)引起其效益的減少。這樣全體 n 個(gè)人的合作將帶

34、來銷地產(chǎn)地廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1313 頁頁更大的效益。n 個(gè)人的集合以及各種合作的效益就構(gòu)成 n 人合作對(duì)策，shapley值是分配這個(gè)效益的一種方案15。定義如下：設(shè)集合，如果對(duì)于 i 的任一子集 s 都對(duì)應(yīng)著一個(gè)實(shí)值函數(shù) v(s)，1,2,.,in滿足 (5.1)()0v (5.2)121212()( )(),v ssv sv sss 稱為n 人合作對(duì)策，v 為對(duì)策的特函數(shù)。, i v在上面所述的經(jīng)濟(jì)活動(dòng)中，i 定義為 n 人集合，s 為 n 人集合中的任一種合作，v(s)為合作中 s 的效益。用表示 i 的成員 i 從合作的最大效益 v(i)中

35、應(yīng)得到的一份收入。ix叫做合作對(duì)策的分配，滿足12,.,nxx xx1( )niixv i，( )ixv i1,2,.,inshapley 值由特征函數(shù) v 確定，記作。對(duì)于任意的子12( )( ),( ),.,( )nvvvv集 s，記，即 s 中各成員的分配。對(duì)一切，滿足的 x( )ii sx sxsi( )( )x sv s組合的集合稱的核心。當(dāng)核心存在時(shí)，即所有的 s 的分配都小于 s 的效益。, i v可以將 shapley 值作為一種特定的分配，即。1( )ivxshapley 值12( )( ),( ),.,( )nvvvv， （5.3）( )(| |)( )( )iissvw

36、sv sv s i1,2,.,in （5.4）(| |)(| | 1)!(| |)!nssw sn其中是i中包含i的所有子集，|s|是子集 s 中的元素?cái)?shù)目（人數(shù)） ，w(|s|)是is加權(quán)因子，si 表示 s 去掉 i 后的集合。接下來利用這組公式計(jì)算例 3 給出的三人經(jīng)商問題的分配，以此來解釋公式的用法和意義。甲乙丙三人記為，經(jīng)商獲利的定義為 i 上的特征函數(shù)，即1,2,3i ()0, (1)(2)(3)1, (1,2)7, (1,3)5, (2,3)4vvvvvvv 廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1414 頁頁。容易驗(yàn)證 v 滿足(5.1)和(5.2)。為

37、計(jì)算首先找出 i 的所有子集( )10v i 1( )v，然后 s 跑遍，將計(jì)算結(jié)果記入表 5-1.最后將表中末行 1: 1 , 1,2 , 1,3 ,si1s相加得到。1( )4v 元表 5-1 三人經(jīng)商中甲的分配的計(jì)算1( )vs1 1,2 1,3 iv(s)1 7 5 10v(s1)0 1 1 4v(s)-v(s1)1 6 4 6|s|1 2 2 3w(|s|)1/3 1/6 1/6 1/3w(|s|) v(s)-v(s1)1/3 1 2/3 2同樣按照 shapley 值方法可以計(jì)算出，。所以，2( )3.5v萬元3( )2.5v萬元甲乙丙三人合作合理的分配分別為 4 萬元、3.5 萬

38、元、2.5 萬元。5.2 shapley 值的推廣應(yīng)用【例 4】設(shè)沿河有三城鎮(zhèn) 1，2，和 3，地理位置如圖 2 所示。污水需要處理后才能排入河中。三個(gè)城鎮(zhèn)既可以單獨(dú)建立污水處理廠，也可以聯(lián)合建廠，用管道將污水集中進(jìn)行處理（污水由河流上游的城鎮(zhèn)向下游城鎮(zhèn)輸送） 。用 q 表示污水量（t/s） ，用 l 表示管道長(zhǎng)度（km） ，按照經(jīng)驗(yàn)公式，建立處理廠的費(fèi)用為，鋪設(shè)管道費(fèi)用為已知三城鎮(zhèn)污水量為0.712173pq千元0.5120.66pql 千元的數(shù)值如圖 5-1 所示。試從節(jié)約總投資的角度為三城鎮(zhèn)制1235,3,5,qqql定最優(yōu)的污水處理方案。如果聯(lián)合建廠，各城鎮(zhèn)如何分擔(dān)費(fèi)用。廣東商學(xué)院數(shù)學(xué)

39、與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1515 頁頁圖 5-1 三城鎮(zhèn)地理位置示意圖【解】三城鎮(zhèn)污水處理共有以下 5 種方案，以下計(jì)算出投資費(fèi)用以作比較。（1） 分別建廠。其投資分別 為：0.712(1)73 5230,(2)160,(3)230ccc總投資1(1)(2)(3)620dccc（2）1，2 合作，在城 2 建廠。投資為：0.7120.51(1,2)73 (53)0.66 520350c總投資2(1,2)(3)580dcc（3）2，3 合作，在城 3 建廠。投資為：0.7120.51(2,3)73 (53)0.66 338365c總投資3(1)(2,3)595dcc（4）

40、1，3 合作，在城 3 建廠。投資為：0.7120.51(1,3)73 (55)0.66 558463c這個(gè)費(fèi)用超過 1，3 分別建廠的費(fèi)用。合作沒有效益，不可能(1)(3)460cc實(shí)現(xiàn)。（5）三城合作，在城 3 建廠?？偼顿Y為：0.7120.510.515(1,2,3)73 (535)0.66 5200.66 (53)38556dc 比較結(jié)果千元最小，所以應(yīng)選擇聯(lián)合建廠方案。接下來的問題是如何5556d 分擔(dān)費(fèi)用。5d總費(fèi)用中有 3 部分：5d聯(lián)合建廠費(fèi)為；0.712173 (535)453d 城 1 至 2 的管道費(fèi)為；0.5120.66 (53)2030d 城 2 至 3 的管道費(fèi)為.

41、0.5130.66 (53)3873d 城 3 提出，由三城按污水量比例 5:3:5 分擔(dān)，是為城 1，2 鋪設(shè)1d2d3d的管道費(fèi)，應(yīng)當(dāng)由他們擔(dān)負(fù)；城 2 同意，并提出由城 1，2 按污水量之比3d5：3 分擔(dān)，則應(yīng)當(dāng)由城 1 自己擔(dān)負(fù)；城 1 提不出反對(duì)意見，按上述辦法各城2d應(yīng)當(dāng)分擔(dān)的費(fèi)用：12320km38km河流廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1616 頁頁15317413d 城分擔(dān)費(fèi)用d城分擔(dān)費(fèi)用為132531250138ddd城分擔(dān)費(fèi)用為結(jié)果表明城 2，3 分擔(dān)的費(fèi)用均比單獨(dú)建廠費(fèi)用 c(2)，c（3）小，而城 1分的費(fèi)用卻

42、比 c(1)大。顯然，城 1 不能同意這種分擔(dān)總費(fèi)用的辦法。為促成三城聯(lián)合建廠以節(jié)約總投資，應(yīng)當(dāng)尋求合理分擔(dān)總費(fèi)用的方案。三城的合作節(jié)約了投資，產(chǎn)生了效益，是一個(gè) n 人合作對(duì)策問題，可以運(yùn)用shapley 值法合理地分配這個(gè)效益。把分擔(dān)費(fèi)用轉(zhuǎn)化成分配效益，就不會(huì)出現(xiàn)城 1 聯(lián)合建廠分擔(dān)的費(fèi)用反比單獨(dú)建廠費(fèi)用高的情況了。將三城分別記為 i=(1，2，3)，聯(lián)合建廠比單獨(dú)建廠節(jié)約的投資定義為特征函數(shù)。于是有()0, (1)(2)(3)0vvvv (1,2)(1)(2)(1,2)230 16035040vccc(2,3)(2)(3)(2,3)16023036525,vccc(1,3)0v( )(1

43、)(2)(3)(1,2,3)230 16023055664v icccc三城聯(lián)合建廠的總效益為 64 千元。用 shapley 值作為這個(gè)效益的分配標(biāo)準(zhǔn)，城 1 應(yīng)分得的份額的計(jì)算結(jié)果列入表 5-1 中，得到。類似1( )v1( )19.7v千元地算得。不難驗(yàn)證，。23( )32.1( )12.2vv，123( )( )( )64( )vvvv i表 5-1 污水處理問題是的計(jì)算2( )vs1 1,2 1,3 iv(s)0 40 0 64v(s1)0 0 0 25v(s)-v(s1)0 40 0 39|s|1 2 2 3w(|s|)1/3 1/6 1/6 1/3w(|s|) v(s)-v(s1

44、)0 6.7 0 13廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1717 頁頁最后，同理運(yùn)用 shapley 值法可以算出在聯(lián)合建廠方案總投資額 556 千元中各城分擔(dān)費(fèi)用為：城 1 是；城 2 是1(1)( )230 19.7210.4cv；城 3 是。2(2)( )127.9cv3(3)( )217.8cv5.3 shapley 值法存在的缺陷shppley 值法以嚴(yán)格的條件為基礎(chǔ)，在處理合作對(duì)策的分配問題時(shí)比較公正合理等，但是它需要知道所有合作方的獲利，即需要定義的所有1,2,.,in子集（共個(gè)）的特征函數(shù)，這實(shí)際上是很難做到的。如 n 個(gè)單位共同合作治2n理污染，第

45、 i 方單獨(dú)治理的投資和 n 方共同合作治理的投資 y，這通常是已iy知的。為了度量第 i 方在合作中的“貢獻(xiàn)” ，還常需要設(shè)法知道第 i 方不參加時(shí)其余 n-1 方所需的投資。特征函數(shù)應(yīng)定義為共同合作的獲利，即節(jié)約的投資，iz有( )0(1,2,. ),v iin顯然除此之外還有很多無法獲取，無法應(yīng)1( ), ( )nijiij iv iyy v i iyz( )v s用 shapley 值方法求解。5.4 其他求解方法以下仍以例 3 提出的三人經(jīng)商問題為例，介紹兩種其它的解決方法?！纠?4】我們只知道全體合作的獲利，記作，及無 i 參加時(shí)其他 n-1 方( )v ib合作的獲利，記作試確定

46、各方對(duì)全12( )(1,2,., )( ,.,).inv i ib inbb bb，且記體合作獲利的分配，記得在三人經(jīng)商問題，12( ,.,).nxx xx*11,(4,5,7),bb 求123( ,).xx x x5.4.1 協(xié)商解16分配分別按照以下兩步進(jìn)行。先從 n 個(gè) n-1 方合作的獲利求出各方分配的下限，即求解12( ,.,)nxx xx1111.niininnixxbxxb廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1818 頁頁得到 11,1,2,.,1niiiixbb inn再求出按下限分配后全體合作獲利的剩余為，它通常是較小的部分，x1niibx經(jīng)過協(xié)商將

47、其平均分配，于是最終的分配結(jié)果為1111()nniiiiiiibxxbxbbnnn剩余，它等價(jià)于10niibx111niibbn對(duì)三人經(jīng)商問題，(4,3,1),(5,4,2)xx5.4.2 raiffa 解howard raiffa 提出的解決辦法按以下的步驟進(jìn)行17：（1）按照 n 個(gè) n-1 方合作的獲利得到了各方分配的下限，即協(xié)商解中的，作x為分配的前提；（2）當(dāng) j 方加入（原來無 j 的）n-1 方合作時(shí)，計(jì)算獲利的增加，即 j 方的邊際效益17，就是最小距離解中的上限；jjxbb（3）按兩步分配：首先先由 j 方和無 j 方的 n-1 方平分，然后 n-1 方再等分，jx即,1,2

48、,., ,22(1)jjjiixxxxxin ijn其中 n-1 方是在的基礎(chǔ)上分配的；x（4）j 取 1,2,n，再重復(fù)第 3 步，然后求和、平均，得到最終分配為 (5.5) 111,1,2,.,22(1)iiijj ixnxxxinnnn將，代入，(5.5)式可表為xx1231,1,2,.,2(1)niiiibnxbbinnnn廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 1919 頁頁a1a2a3ob1b2b3b4對(duì)三人經(jīng)商問題，2115(4,3,1),(7,6,4),(4,3,2).31212xxx6 6 傳統(tǒng)模型的改進(jìn)設(shè)想傳統(tǒng)模型的改進(jìn)設(shè)想6.1 最小元素法的改進(jìn)設(shè)想

49、表上作業(yè)法是求解運(yùn)輸成本最優(yōu)化問題的常用而有效的方法，但是表上作業(yè)法求解過程比較復(fù)雜，而且如果供求雙方數(shù)量比較多，檢驗(yàn)數(shù)的計(jì)算和閉回路的調(diào)整更容易出錯(cuò)。因此，如果初始方案的給定能盡可能地趨向最優(yōu)化，在運(yùn)輸成本預(yù)算比較充裕的情況下可以直接采用初始方案。初始方案給定的方法最常用的是最小元素法，而最小元素法的物資配送是滿足運(yùn)輸配送的每一次單位運(yùn)價(jià)都最小化，但從整體上考慮，它并不能保證總運(yùn)價(jià)達(dá)到最小，也不能在第一時(shí)間滿足需求點(diǎn)的一定量的物資需求。因此，本文將對(duì)最小元素法的配送過程進(jìn)行調(diào)整，首先通過對(duì)物資配送環(huán)節(jié)進(jìn)行改進(jìn)，可以在第一時(shí)間滿足某些需求點(diǎn)的物資需求，然后通過增加一臨時(shí)節(jié)點(diǎn)c（該點(diǎn)是離需求方較

50、近的一點(diǎn)） ，對(duì)所有供應(yīng)點(diǎn)經(jīng)過一定階段配送后的剩余物資進(jìn)行重新分配，這樣可以使運(yùn)輸總成本得到優(yōu)化。圖 6-1 傳統(tǒng)的最小元素法配送網(wǎng)絡(luò)廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 2020 頁頁a1a2a3ob1b2b3b4c圖 6-2 改進(jìn)后的最小元素法配送網(wǎng)絡(luò)6.2 效益分配的改進(jìn)設(shè)想在經(jīng)濟(jì)生活中，效益分配問題最常見的是合作分配利益問題，前面主要介紹了 shapley 值效益分配法，但這種方法主要的缺陷是需要知道合作各方在活動(dòng)中的“貢獻(xiàn)” ，還有總的合作效益，這在實(shí)際生活中是難以評(píng)估的，因?yàn)橐粋€(gè)項(xiàng)目還沒開展，其效益很難作出準(zhǔn)確的評(píng)估。這里將通過合作各方以往的工作效益制定一定

51、的分配標(biāo)準(zhǔn)，在項(xiàng)目完成之后總效益算出來再進(jìn)行分配。設(shè)有三個(gè)工程師甲乙丙共同合作參與完成一個(gè)項(xiàng)目，甲乙丙一個(gè)月的工作效益是分別是、（假設(shè)三人一個(gè)月的工作時(shí)間一樣，而且工作效益變1x2x3x動(dòng)不大） ，項(xiàng)目完成時(shí)三人的工作時(shí)間分別為、，總的效益為 ，則三1t2t3ts人應(yīng)分配的效益之比為：332211321:txtxtxsss (6.1)明顯，由前提條件可以得到：ssss321 (6.2)由式(6.1)和式(6.2)可以得到甲乙丙三人分配的效益分別為：stxtxtxtxs332211111stxtxtxtxs332211222廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 2121

52、頁頁stxtxtxtxs3322113337 7 總結(jié)與展望總結(jié)與展望7.1 本文的主要貢獻(xiàn)數(shù)學(xué)與我們?nèi)粘Ｉ蠲芮邢嚓P(guān)，日常生活中的許多問題來源于數(shù)學(xué)思想的應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常當(dāng)中可能出現(xiàn)的數(shù)學(xué)問題，通過適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。通過對(duì)日常生活中經(jīng)常涉及到的若干最優(yōu)化問題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原理并將其推廣應(yīng)用到其他生活案例當(dāng)中去18。本文的主要貢獻(xiàn)有以下幾個(gè)方面：首先，本文主要選取了生活中較具有代表性的運(yùn)輸成本問題和效益分配問題進(jìn)行最優(yōu)化研究，分別詳細(xì)地介紹了表上作業(yè)法和 shapley 值法的求解過程。然后，根據(jù)這兩種求解方法

53、的局限性和普遍性進(jìn)行分析，指出了這兩種模型存在的缺陷和不足，最后，針對(duì)模型存在的缺陷分別提出了相應(yīng)的改進(jìn)方法，并將其推廣應(yīng)用到其他不同的領(lǐng)域19。7.2 本文主要的改進(jìn)方案運(yùn)用表上作業(yè)法解決運(yùn)輸成本問題存在著一定的局限性，主要應(yīng)用于產(chǎn)銷平衡的運(yùn)輸問題，但實(shí)際問題中產(chǎn)銷往往是不平衡的。為了應(yīng)用表上作業(yè)法計(jì)算，就需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。當(dāng)總的產(chǎn)量大于銷量時(shí)，可以考慮將多余的物資在那一個(gè)產(chǎn)地就地庫存，此時(shí)需要在產(chǎn)銷平衡表上增加一個(gè)假想的銷地，通過這樣的修改，原先不平衡的運(yùn)輸問題就轉(zhuǎn)化成為產(chǎn)銷平衡問題了。當(dāng)總的銷量大于產(chǎn)量時(shí)，同理可以在產(chǎn)銷平衡表中增加一個(gè)假想的產(chǎn)地，同時(shí)在單位運(yùn)價(jià)表

54、上設(shè)定該假想產(chǎn)地到各銷地的運(yùn)價(jià)為零，同樣轉(zhuǎn)化成為產(chǎn)銷平衡的運(yùn)輸問題。通過這樣的轉(zhuǎn)化問題就能順利解決了20。shapley 值方法嚴(yán)格的公理為基礎(chǔ)，在處理合作對(duì)策問題時(shí)具有公平、合理等特點(diǎn)，但是它需要知道所有合作的獲利，合作方越多，需要的信息就越大，在實(shí)際上這些信息往往難以完全提供。協(xié)商解法計(jì)算相對(duì)簡(jiǎn)單，且便于理解，但通常偏袒強(qiáng)者，可用于各方實(shí)力相差不大的情況。raiffa 解法考慮了分配的廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 生活中的一些最優(yōu)化問題研究第第 2222 頁頁上下限，又吸取了 shapley 的思想，在一定的程序上保護(hù)弱者。因此，只要根據(jù)問題提供的條件和要求，運(yùn)用相應(yīng)的解決方法就可以最大程序地公平分配效益21。7.3 研究展望將掌握的數(shù)學(xué)知識(shí)應(yīng)用到實(shí)際生活中有著重要的意義，不僅能夠促進(jìn)社會(huì)經(jīng)濟(jì)生