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

1、本科畢業(yè)論文本科畢業(yè)論文(設(shè)計(jì)設(shè)計(jì)) 生活中的一些最優(yōu)化問(wèn)題研究生活中的一些最優(yōu)化問(wèn)題研究 院院 （系）（系）數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 專(zhuān)專(zhuān) 業(yè)業(yè)信息與計(jì)算科學(xué) 學(xué)學(xué) 號(hào)號(hào)08251001133 學(xué)生姓名學(xué)生姓名游佳能 指導(dǎo)教師指導(dǎo)教師柴嘯龍 提交日期提交日期2012 年 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)語(yǔ)及成績(jī)畢業(yè)論文（設(shè)計(jì)）指導(dǎo)教師評(píng)語(yǔ)及成績(jī) 成績(jī)成績(jī) 指導(dǎo)教師簽名指導(dǎo)教師簽名 年年 月月 日日 畢業(yè)論文（設(shè)計(jì)）復(fù)評(píng)教師評(píng)語(yǔ)及成績(jī)畢業(yè)論文（設(shè)計(jì)）復(fù)評(píng)教師評(píng)語(yǔ)及成績(jī) 成績(jī)成績(jī) 復(fù)評(píng)

2、教師簽名復(fù)評(píng)教師簽名 年年 月月 日日 畢業(yè)論文（設(shè)計(jì)）答辯評(píng)語(yǔ)及成績(jī)畢業(yè)論文（設(shè)計(jì)）答辯評(píng)語(yǔ)及成績(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 life major: information and computing science applicant: jia-neng you supervisor: xiao-long chai 內(nèi)容摘要內(nèi)容摘要

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

4、ract mathematics to our daily lives 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, th

5、e use of mathematical principles for 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 c

6、ontribution of this paper is the optimization 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 applic

7、ation. keywords: optimization; tabular method; shapley method; application 目目 錄錄 1 1 研究的意義研究的意義與與目的目的 .1 1 2 2 研究現(xiàn)狀分析研究現(xiàn)狀分析 .1 1 2.1 研究的方法 .1 2.2 研究現(xiàn)狀 .2 3 3 本文研究方向本文研究方向 .2 2 3.1 運(yùn)輸調(diào)配方向 .3 3.2 效益分配方向.3 4 4 運(yùn)輸調(diào)配問(wèn)題最優(yōu)化研究運(yùn)輸調(diào)配問(wèn)題最優(yōu)化研究 .3 3 4.1 初始方案的給定 .4 4.2 最優(yōu)性檢驗(yàn)與方案的調(diào)整 .6 4.3 表上作業(yè)法的總結(jié) .8 4.4 表上作業(yè)法的改進(jìn)及其推

8、廣應(yīng)用 .9 5 5 效益分配問(wèn)題最優(yōu)化研究效益分配問(wèn)題最優(yōu)化研究 .1212 5.1 n 人合作對(duì)策和 shapley 值.12 5.2 shapley 值的推廣應(yīng)用.14 5.3 shapley 值法存在的缺陷.16 5.4 其他求解方法.17 5.4.1 協(xié)商解 .17 5.4.2 raiffa 解 .18 6 6 傳統(tǒng)模型的改進(jìn)設(shè)想傳統(tǒng)模型的改進(jìn)設(shè)想 .1818 6.1 最小元素法的改進(jìn)設(shè)想 .18 6.2 效益分配的改進(jìn)設(shè)想 .20 7 7 總結(jié)與展望總結(jié)與展望 .2020 7.1 本文的主要貢獻(xiàn) .20 7.2 本文主要的改進(jìn)方案 .21 7.3 研究展望 .21 參考文獻(xiàn)參考文獻(xiàn)

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

10、一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常生活當(dāng)中可能出現(xiàn)的數(shù)學(xué)問(wèn) 題，通過(guò)適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。本文 通過(guò)對(duì)日常生活中經(jīng)常涉及到的若干最優(yōu)化問(wèn)題進(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 研究的方法 不同類(lèi)型的最優(yōu)化問(wèn)題可以有不同的最優(yōu)化方法，即使同一類(lèi)型的問(wèn)題也 可有多種最優(yōu)化方法。反之，某些最優(yōu)化方法可適用于不同類(lèi)型的模型。目前， 最優(yōu)化問(wèn)題的求解方

11、法大致可分成解析法、直接法、數(shù)值計(jì)算法。解析法： 這種方法只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。求解方法 是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等 式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過(guò)必要條件將問(wèn)題簡(jiǎn)化， 因此也稱(chēng)間接法。直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述 時(shí)，無(wú)法用解析法求必要條件。此時(shí)可采用直接搜索的方法經(jīng)過(guò)若干次迭代搜 索到最優(yōu)點(diǎn)。這種方法常常根據(jù)經(jīng)驗(yàn)或通過(guò)試驗(yàn)得到所需結(jié)果。對(duì)于一維搜索 (單變量極值問(wèn)題)，主要用消去法或多項(xiàng)式插值法；對(duì)于多維搜索問(wèn)題(多變量 極值問(wèn)題)主要應(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ī)械、建筑等部門(mén)都 已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選 取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題得到解決5。最優(yōu)計(jì)劃:現(xiàn)代國(guó)民 經(jīng)濟(jì)或部門(mén)經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī) 劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開(kāi)始應(yīng)用最 優(yōu)化方法。一個(gè)重要的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門(mén)進(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) 控制，化工、冶金等工廠(chǎng)的最佳工況的控制。計(jì)算機(jī)接口裝置不斷完善和優(yōu)化 方法的進(jìn)一步發(fā)展，還為計(jì)算機(jī)在線(xiàn)生產(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)化問(wèn)題研究漸趨成熟，也應(yīng)用到很多不同的領(lǐng)域，但對(duì)日常 生活存在的

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

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

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

17、【例 1】某食品加工公司經(jīng)銷(xiāo)的主要產(chǎn)品之一是酸奶。該公司下面設(shè)有三個(gè)加 工廠(chǎng)，每天酸奶的生產(chǎn)量分別為：，。該公司把這些酸 1 7at 2 4at 3 9at 奶分別運(yùn)往四個(gè)地區(qū)的門(mén)市部進(jìn)行銷(xiāo)售，各地區(qū)每天的銷(xiāo)售量分別為： ，。已知從每個(gè)加工廠(chǎng)到對(duì)應(yīng)的各銷(xiāo)售門(mén)市部 1 3bt 2 6bt 3 5bt 4 6bt 每噸酸奶的運(yùn)價(jià)如表 4-1 所示，問(wèn)該食品公司該如何調(diào)運(yùn)，在滿(mǎn)足各門(mén)市部銷(xiāo) 售需要的前提下，使得總運(yùn)費(fèi)支出達(dá)到最少。 表 4-1 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 以下運(yùn)用表上作業(yè)法求解運(yùn)輸問(wèn)題，首先給出一個(gè)初始

18、方案，一般來(lái)講，這個(gè) 方案不會(huì)是最好的。因此需要給出一個(gè)判別準(zhǔn)則，并對(duì)初始方案通過(guò)不斷地調(diào) 整、改進(jìn)，一直到求得最優(yōu)方案為止10。 先列出這個(gè)問(wèn)題的的產(chǎn)銷(xiāo)平衡表和單位運(yùn)價(jià)表，見(jiàn)表 4-2 和表 4-3 表 4-2 產(chǎn)銷(xiāo)平衡表 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 7 4 9 銷(xiāo)量3 6 5 6 表 4-3 單位運(yùn)價(jià)表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 4.1 初始方案的給定 給定初始方案的方法有很多，一般希望方法簡(jiǎn)便易行，盡量能給出較好的 方案，減少迭代的次數(shù)，這里采用最小元素法。最小元素法的基本

19、思想是就近 供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開(kāi)始確定供銷(xiāo)關(guān)系，依此類(lèi)推，一直到給 出全部方案為止10。 門(mén)市部 加工廠(chǎng) 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 第一步：從表 4-3 的單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為 1（如果有兩個(gè)最小運(yùn)價(jià)時(shí) 任選其一） ，即從生產(chǎn)的酸奶首先供應(yīng)需求。由于每天生產(chǎn) 4t，每天 2 a 1 b 2 a 1 b 需要 3t,即每天生產(chǎn)的除了要滿(mǎn)足全部需求之外，還剩下 1t。因此在表 4- 2 a 1 b 2 中（，）的交叉格中填上數(shù)字 3，表示調(diào)運(yùn) 3t 酸奶給，再在表 4-3 2 a 1 b 2 a 1 b 中將所在的這一列運(yùn)價(jià)劃去，表示已經(jīng)滿(mǎn)足的需求，無(wú)需繼續(xù)調(diào)運(yùn)給它。 1 b 1

20、 b 第一步得到的結(jié)果如表 4-4 和表 4-5 所示。 表 4-4 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 3 7 4 9 銷(xiāo)量3 6 5 6 表 4-5 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 第二步：從表 4-5 中未劃去的元素之中找出最小的運(yùn)價(jià)為 2，即每天剩余的 2 a 酸奶要供應(yīng)給。每天需要 5t，每天只能供應(yīng) 1t，因此在表 4-4（， 3 b 3 b 2 a 2 a ）交叉處填寫(xiě) 1，劃去表 4-5 所在的這一行運(yùn)價(jià)，表示生產(chǎn)的酸奶已 3 b 2 a 2 a 分配完，其結(jié)果見(jiàn)表 4-6 和

21、表 4-7. 表 4-6 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 3 1 7 4 9 銷(xiāo)量3 6 5 6 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 表 4-7 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 第三步：同理再?gòu)谋?4-7 中未劃去的元素之中找出最小的元素為 3，即生產(chǎn) 1 a 的酸奶應(yīng)優(yōu)先滿(mǎn)足需求。每天生產(chǎn) 7t，還缺 4t。因此在表中 3 b 1 a 3 b （，）交叉格內(nèi)填上 4，由于的需求此時(shí)已經(jīng)滿(mǎn)足，在表 4-7 中劃去 1 a 3 b 3 b 所在列的元素。 3 b 這樣一步一步地進(jìn)行下去，直到

22、單位運(yùn)價(jià)表上所有元素都被劃去為止，這時(shí)在 產(chǎn)銷(xiāo)平衡表上可以得到一個(gè)調(diào)動(dòng)方案（見(jiàn)表 4-8） ，這個(gè)調(diào)動(dòng)方案總的運(yùn)費(fèi)為 86 元。 表 4-8 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 4 3 3 1 6 3 7 4 9 銷(xiāo)量3 6 5 6 4.2 最優(yōu)性檢驗(yàn)與方案的調(diào)整 最小元素法給出的是運(yùn)輸問(wèn)題的一個(gè)基可行解，需要通過(guò)最優(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)輸問(wèn)題中的閉回路是指 調(diào)運(yùn)方案中的一個(gè)空格和幾個(gè)有數(shù)字格的水平和垂直之間的連線(xiàn)包圍成的封閉 回路11。 構(gòu)建閉回路是為了計(jì)算解

23、中各非基變量（對(duì)應(yīng)空格）的檢驗(yàn)數(shù)，方法是令 某一非基變量取值為 1，通過(guò)變動(dòng)原基變量的值找出一個(gè)的可行解，將其與原 來(lái)的基可行解進(jìn)行比較。在表 4-8 中給出了一個(gè)調(diào)運(yùn)方案中， （，）是空 1 a 1 b 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 1 格，即為非基變量。令，相應(yīng)地為了找到新的可行解，原有基變量中 11 x 11 1x 需減 1，加 1，減 1，見(jiàn)表 4-9。表中由（，） ， （，） ， 13 x 23 x 21 x 1 a 1 b 1 a 3 b （，） ， （，）4 個(gè)格的水平和垂直連線(xiàn)圍成的閉回路，該閉回路除（ 2 a 3 b 2 a 1 b ，）為空格之外， （，） ， （，） ， （，）

24、均有數(shù)字的格。將 1 a 1 b 1 a 3 b 2 a 3 b 2 a 1 b 新可行解與原來(lái)解費(fèi)用比較：從 0 變成 1，運(yùn)費(fèi)加 3 元，減 1，運(yùn)費(fèi)減少 11 x 13 x 3 元，加 1，運(yùn)費(fèi)加 2 元，減 1，運(yùn)費(fèi)減少 1 元，由此新可行解較原來(lái)解 23 x 21 x 運(yùn)費(fèi)增加了（3-3+2-1）=1 元，稱(chēng)為檢驗(yàn)數(shù)，將其填入檢驗(yàn)數(shù)表中（表 4-10） 的（，）相應(yīng)的交叉格位置。類(lèi)似地（，）為空格，可通過(guò)該空格找 1 a 1 b 3 a 1 b 出一條其余頂點(diǎn)都有數(shù)字格的閉回路，求得其相應(yīng)的檢驗(yàn)數(shù)為（7-1+2-3+10- 5）=10，將其填入檢驗(yàn)數(shù)表 4-10 的（，）的交叉格位置

25、，因?yàn)槿我獾姆?3 a 1 b 基向量均可表示為基向量的唯一線(xiàn)性組合，因此通過(guò)任一空格可以找到，并且 只能找到唯一的閉回路，并計(jì)算得到對(duì)應(yīng)表 4-8 中解全部非基變量的檢驗(yàn)數(shù)12。 表 4-9 1 b 2 b 3 b 4 b產(chǎn)量 1 a （+1）4（-1） 37 2 a3（-3） 1（+1） 4 3 a639 銷(xiāo)量3656 表 4-10 檢驗(yàn)數(shù)表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 12 1 -1 10 12 銷(xiāo)地 產(chǎn)地 33 2 銷(xiāo)地 產(chǎn)地 如果檢驗(yàn)數(shù)表中所有的數(shù)字都大于等于零，表明對(duì)調(diào)運(yùn)方案作出任何改變 都不會(huì)導(dǎo)致運(yùn)費(fèi)減少，即給定的方案為最優(yōu)方案。但在表 4-10 中，

26、 （,） 2 a 4 b 格的檢驗(yàn)數(shù)是負(fù)的，說(shuō)明方案仍需進(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ù)字格而組 2 a 4 b 成的閉回路。在這條閉回路上，按照以上講的方法對(duì)運(yùn)量作最大限度的調(diào)整。 從表 4-9 看出，為了把生產(chǎn)的酸奶調(diào)運(yùn)給，就要相應(yīng)減少調(diào)運(yùn)給的 2 a 4 b 2 a 3 b 酸奶和調(diào)運(yùn)給的酸奶，才能得到新的平衡。這兩個(gè)格內(nèi)，較小運(yùn)量為 1， 1 a 4 b 因此最多只能調(diào)運(yùn) 1t 酸奶給。由此得到一個(gè)新的調(diào)運(yùn)方案（見(jiàn)表 4-11） 。 2 a 4 b

27、這個(gè)新方案的運(yùn)費(fèi)為 85 元。 表 4-11 1 b 2 b 3 b 4 b 產(chǎn)量 1 a 2 a 3 a 5 2 3 1 6 3 7 4 9 銷(xiāo)量3 6 5 6 表 4-11 給出的調(diào)運(yùn)方案是否達(dá)到最優(yōu)，仍需對(duì)這個(gè)方案的每一個(gè)空格求出 其檢驗(yàn)數(shù)（見(jiàn)表 4-12） 。由于檢驗(yàn)數(shù)表中所有的檢驗(yàn)數(shù)大于等于零，因此肯定 表 4-11 給出的方案是最優(yōu)方案。 表 4-12 檢驗(yàn)數(shù)表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 0 2 2 1 9 12 4. 3 表上作業(yè)法的總結(jié) 運(yùn)輸問(wèn)題成本最優(yōu)化解決方法主要有三個(gè)步驟，可以用以下流程圖總結(jié)出 來(lái)，見(jiàn)圖 4-1。 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 否

28、 分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo) 平衡表及單位運(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)銷(xiāo)平衡為前提的，即 。但實(shí)際問(wèn)題中大部分產(chǎn)銷(xiāo)是不平衡的。為了更好地應(yīng)用表上作業(yè) 11 mn ij ij ab 法，就需要把產(chǎn)銷(xiāo)不平衡的問(wèn)題轉(zhuǎn)化成產(chǎn)銷(xiāo)平衡的問(wèn)題13。 當(dāng)產(chǎn)大于銷(xiāo)時(shí)，運(yùn)輸問(wèn)題的數(shù)學(xué)模型可寫(xiě)為 11 mn ij ij ab () (4.1a) 11 min mn ijij ij zc x s.t

29、. 1 1 (1,.,)(4.1 ) (1,., )(4.1 ) 0(4.1 ) n iji j m ijj i ij xa imb xbjnc xd 如果總的產(chǎn)量大于銷(xiāo)量，可以考慮多余的物資在那一個(gè)產(chǎn)地庫(kù)存的。設(shè)是 ,1i n x 產(chǎn)地的庫(kù)存量，于是可以得到 i a (4.2) 1 ,1 11 nn iji nij jj xxxa (1,.,)im (4.3) 1 m ijj i xb (1,., )jn ,11 111 mmn i nijn iij xabb 令 (4.4) ijij cc (1,.,;1,., )im jn 0 ij c (1,.,;1,.,1)im jn 將(4.2)-

30、(4.4)分別代入或替換(4.1a)-(4.1d)，得到 (4.5a) 1 ,1 1111111 min mnmnmmn ijijijiji niijij ijijiij zc xc xcxcx s.t 1 1 1 (1,.,)(4.5 ) (1,., )(4.5 ) 0(4.5 ) n ij j m ijj i ij xa imb xbjnc xd 由于（4.5）模型中，是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。因 1 1 111 mnn iini ijj abbb 此當(dāng)產(chǎn)量大于銷(xiāo)量時(shí)，只需增加一個(gè)假想的銷(xiāo)地 j=n+1(實(shí)際上庫(kù)存銷(xiāo)地的單位 運(yùn)價(jià)，就可以轉(zhuǎn)化成為一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。類(lèi)似地，當(dāng)銷(xiāo)量大于

31、,1 0 i n c 產(chǎn)量時(shí)，可以在產(chǎn)銷(xiāo)平衡中增加一個(gè)假想的產(chǎn)地，該地產(chǎn)量為1im ，在單位運(yùn)價(jià)表中令從該假想產(chǎn)地到各銷(xiāo)地的運(yùn)價(jià)，同 11 () nm ji ji ba 1, 0 mj c 樣可以轉(zhuǎn)化成為一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。 【例 2】設(shè)有三個(gè)產(chǎn)地生產(chǎn)某種物資，三個(gè)產(chǎn)地的產(chǎn)量分別為 123 ,a a a 7t、5t、7t，四個(gè)銷(xiāo)地需要該種物資，銷(xiāo)量分別為 1234 ,b b b b 2t、3t、4t、6t，又知各產(chǎn)銷(xiāo)地之間的單位運(yùn)價(jià)見(jiàn)表 4-13，試解出總運(yùn)費(fèi)最少 的調(diào)動(dòng)方案。 表 4-13 單位運(yùn)價(jià)表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 2 11 3 4 10 3 5

32、 9 7 8 1 2 【解】產(chǎn)地總產(chǎn)量為 19t，銷(xiāo)地總銷(xiāo)量為 15t，因此這是產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題。 可按照上述方法轉(zhuǎn)化成為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，轉(zhuǎn)化之后其產(chǎn)銷(xiāo)平衡表和單位 運(yùn)價(jià)表分別見(jiàn)表 4-14、見(jiàn)表 4-15. 表 4-14 產(chǎn)銷(xiāo)平衡表 庫(kù)存 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 7 5 7 銷(xiāo)量2 3 4 6 4 表 4-15 單位運(yùn)價(jià)表 庫(kù)存 1 b 2 b 3 b 4 b 1 a 2 a 3 a 2 11 4 4 0 10 3 9 9 0 7 8 2 2 0 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 銷(xiāo)地 產(chǎn)地 對(duì)表 4-14、表 4-15 可以用表上作業(yè)法計(jì)算求出最優(yōu)方案如表

33、 4-16 表 4-16 最優(yōu)方案 庫(kù)存 1 b 2 b 3 b 4 b 產(chǎn)量 1 a 2 a 3 a 2 3 2 3 2 4 3 7 5 7 銷(xiāo)量2 3 4 6 4 5 5 效益分配問(wèn)題最優(yōu)化研究效益分配問(wèn)題最優(yōu)化研究 在日常的社會(huì)生活中若干實(shí)體（如個(gè)人、公司、協(xié)會(huì)等）相互合作結(jié)成聯(lián) 盟或集團(tuán)，常能比個(gè)體單獨(dú)行動(dòng)獲得更多的經(jīng)濟(jì)利益或社會(huì)效益。但是效益公 平分配問(wèn)題經(jīng)常成為他們合作的阻礙，如何合理地分配這些效益是促進(jìn)合作的 前提，也能給合作帶來(lái)更多的效益14。 【例 3】設(shè)有甲乙丙三人經(jīng)商。若單獨(dú)經(jīng)營(yíng)，每人僅能獲利 1 萬(wàn)元；甲乙合作 可獲利 7 萬(wàn)元；甲丙合作可獲利 5 萬(wàn)元；乙丙合作可獲利

34、 4 萬(wàn)元；三人合作則 可獲利 11 萬(wàn)元。問(wèn)三人合作時(shí)怎么合理地分配 11 萬(wàn)元的收入。 【解】設(shè)甲乙丙三人各得萬(wàn)元，從題目中給定的條件我們可列出滿(mǎn)足條 123 ,x x x 件的一組方程 123 11xxx 123121323 ,1,7,5,4x x xxxxxxx 根據(jù)上述這兩組方程可求出許多組滿(mǎn)足條件的解組，如 等 123 ()(5,3,3),(4,4,3),(4,3.5,3.5)xxx 這種求解的方案最為普遍，但仍存在一定的局限性，當(dāng)條件不夠多的時(shí)無(wú)法求 出最優(yōu)的解組。以下將介紹一種其他的方法求解這類(lèi)問(wèn)題。 5.1 n 人合作對(duì)策和 shapley 值 n 個(gè)人從事一項(xiàng)經(jīng)濟(jì)活動(dòng)，對(duì)于

35、他們之中的若干人組合的每一種合作（單 人也視為一種合作） ，都可以得到一定的效益，僅當(dāng)人們之間的利益是非對(duì)抗性 時(shí)，合作中人數(shù)的增加不會(huì)引起其效益的減少。這樣全體 n 個(gè)人的合作將帶來(lái) 銷(xiāo)地 產(chǎn)地 更大的效益。n 個(gè)人的集合以及各種合作的效益就構(gòu)成 n 人合作對(duì)策，shapley 值是分配這個(gè)效益的一種方案15。定義如下： 設(shè)集合，如果對(duì)于 i 的任一子集 s 都對(duì)應(yīng)著一個(gè)實(shí)值函數(shù) v(s)，1,2,.,in 滿(mǎn)足 (5.1)()0v (5.2) 121212 ()( )(),v ssv sv sss 稱(chēng)為n 人合作對(duì)策，v 為對(duì)策的特函數(shù)。, i v 在上面所述的經(jīng)濟(jì)活動(dòng)中，i 定義為 n

36、人集合，s 為 n 人集合中的任一種合 作，v(s)為合作中 s 的效益。 用表示 i 的成員 i 從合作的最大效益 v(i)中應(yīng)得到的一份收入。 i x 叫做合作對(duì)策的分配，滿(mǎn)足 12 ,., n xx xx 1 ( ) n i i xv i ，( ) i xv i1,2,.,in shapley 值由特征函數(shù) v 確定，記作。對(duì)于任意的子 12 ( )( ),( ),.,( ) n vvvv 集 s，記，即 s 中各成員的分配。對(duì)一切，滿(mǎn)足的 x( ) i i s x sx si( )( )x sv s 組合的集合稱(chēng)的核心。當(dāng)核心存在時(shí)，即所有的 s 的分配都小于 s 的效益。, i v

37、可以將 shapley 值作為一種特定的分配，即。 1( )i vx shapley 值 12 ( )( ),( ),.,( ) n vvvv ， （5.3）( )(| |)( )( ) i i ss vw sv sv s i 1,2,.,in （5.4） (| |)(| | 1)! (| |) ! nss w s n 其中是i中包含i的所有子集，|s|是子集 s 中的元素?cái)?shù)目（人數(shù)） ，w(|s|)是 i s 加權(quán)因子，si 表示 s 去掉 i 后的集合。 接下來(lái)利用這組公式計(jì)算例 3 給出的三人經(jīng)商問(wèn)題的分配，以此來(lái)解釋公式的 用法和意義。 甲乙丙三人記為，經(jīng)商獲利的定義為 i 上的特征函

38、數(shù)，即1,2,3i ()0, (1)(2)(3)1, (1,2)7, (1,3)5, (2,3)4vvvvvvv 。容易驗(yàn)證 v 滿(mǎn)足(5.1)和(5.2)。為計(jì)算首先找出 i 的所有子集( )10v i 1( ) v ，然后 s 跑遍，將計(jì)算結(jié)果記入表 5-1.最后將表中末行 1: 1 , 1,2 , 1,3 , si 1 s 相加得到。 1( ) 4v 元 表 5-1 三人經(jīng)商中甲的分配的計(jì)算 1( ) v s1 1,2 1,3 i v(s)1 7 5 10 v(s1)0 1 1 4 v(s)-v(s1)1 6 4 6 |s|1 2 2 3 w(|s|)1/3 1/6 1/6 1/3 w(

39、|s|) v(s)-v(s1)1/3 1 2/3 2 同樣按照 shapley 值方法可以計(jì)算出，。所以， 2( ) 3.5v萬(wàn)元 3( ) 2.5v萬(wàn)元 甲乙丙三人合作合理的分配分別為 4 萬(wàn)元、3.5 萬(wàn)元、2.5 萬(wàn)元。 5.2 shapley 值的推廣應(yīng)用 【例 4】設(shè)沿河有三城鎮(zhèn) 1，2，和 3，地理位置如圖 2 所示。污水需要處理后 才能排入河中。三個(gè)城鎮(zhèn)既可以單獨(dú)建立污水處理廠(chǎng)，也可以聯(lián)合建廠(chǎng)，用管 道將污水集中進(jìn)行處理（污水由河流上游的城鎮(zhèn)向下游城鎮(zhèn)輸送） 。用 q 表示污 水量（t/s） ，用 l 表示管道長(zhǎng)度（km） ，按照經(jīng)驗(yàn)公式，建立處理廠(chǎng)的費(fèi)用為 ，鋪設(shè)管道費(fèi)用為已知

40、三城鎮(zhèn)污水量為 0.712 1 73pq千元 0.51 2 0.66pql 千元 的數(shù)值如圖 5-1 所示。試從節(jié)約總投資的角度為三城鎮(zhèn)制 123 5,3,5,qqql 定最優(yōu)的污水處理方案。如果聯(lián)合建廠(chǎng)，各城鎮(zhèn)如何分擔(dān)費(fèi)用。 圖 5-1 三城鎮(zhèn)地理位置示意圖 【解】三城鎮(zhèn)污水處理共有以下 5 種方案，以下計(jì)算出投資費(fèi)用以作比較。 （1） 分別建廠(chǎng)。其投資分別 為： 0.712 (1)73 5230,(2)160,(3)230ccca 總投資 1 (1)(2)(3)620dccc （2）1，2 合作，在城 2 建廠(chǎng)。投資為： 0.7120.51 (1,2)73 (53)0.66 520350c

41、 總投資 2 (1,2)(3)580dcc （3）2，3 合作，在城 3 建廠(chǎng)。投資為： 0.7120.51 (2,3)73 (53)0.66 338365c 總投資 3 (1)(2,3)595dcc （4）1，3 合作，在城 3 建廠(chǎng)。投資為： 0.7120.51 (1,3)73 (55)0.66 558463c 這個(gè)費(fèi)用超過(guò) 1，3 分別建廠(chǎng)的費(fèi)用。合作沒(méi)有效益，不可能(1)(3)460cc 實(shí)現(xiàn)。 （5）三城合作，在城 3 建廠(chǎng)?？偼顿Y為： 0.7120.510.51 5 (1,2,3)73 (535)0.66 5200.66 (53)38556dc 比較結(jié)果千元最小，所以應(yīng)選擇聯(lián)合建廠(chǎng)

42、方案。接下來(lái)的問(wèn)題是如何 5 556d 分擔(dān)費(fèi)用。 5 d 總費(fèi)用中有 3 部分： 5 d 聯(lián)合建廠(chǎng)費(fèi)為； 0.712 1 73 (535)453d 城 1 至 2 的管道費(fèi)為； 0.51 2 0.66 (53)2030d 城 2 至 3 的管道費(fèi)為. 0.51 3 0.66 (53)3873d 城 3 提出，由三城按污水量比例 5:3:5 分擔(dān)，是為城 1，2 鋪設(shè) 1 d 2 d 3 d 的管道費(fèi)，應(yīng)當(dāng)由他們擔(dān)負(fù)；城 2 同意，并提出由城 1，2 按污水量之比 3 d 5：3 分擔(dān)，則應(yīng)當(dāng)由城 1 自己擔(dān)負(fù)；城 1 提不出反對(duì)意見(jiàn)，按上述辦法各城 2 d 應(yīng)當(dāng)分擔(dān)的費(fèi)用： 123 20km

43、 38km 河流 1 5 3174 13 d 城分擔(dān)費(fèi)用為 13 53 2132 138 dd城分擔(dān)費(fèi)用為 132 53 1250 138 ddd城分擔(dān)費(fèi)用為 結(jié)果表明城 2，3 分擔(dān)的費(fèi)用均比單獨(dú)建廠(chǎng)費(fèi)用 c(2)，c（3）小，而城 1 分的費(fèi)用卻比 c(1)大。顯然，城 1 不能同意這種分擔(dān)總費(fèi)用的辦法。 為促成三城聯(lián)合建廠(chǎng)以節(jié)約總投資，應(yīng)當(dāng)尋求合理分擔(dān)總費(fèi)用的方案。三 城的合作節(jié)約了投資，產(chǎn)生了效益，是一個(gè) n 人合作對(duì)策問(wèn)題，可以運(yùn)用 shapley 值法合理地分配這個(gè)效益。 把分擔(dān)費(fèi)用轉(zhuǎn)化成分配效益，就不會(huì)出現(xiàn)城 1 聯(lián)合建廠(chǎng)分擔(dān)的費(fèi)用反比單 獨(dú)建廠(chǎng)費(fèi)用高的情況了。將三城分別記為 i

44、=(1，2，3)，聯(lián)合建廠(chǎng)比單獨(dú)建廠(chǎng) 節(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)(2)(3)(1,2,3)230 16023055664v icccc 三城聯(lián)合建廠(chǎng)的總效益為 64 千元。用 shapley 值作為這個(gè)效益的分配標(biāo)準(zhǔn)， 城 1 應(yīng)分得的份額的計(jì)算結(jié)果列入表 5-1 中，得到。類(lèi)似 1( ) v 1( ) 19.7v千元 地算得。不難驗(yàn)證，。 23 ( )32.1( )12.2vv， 123

45、 ( )( )( )64( )vvvv i 表 5-1 污水處理問(wèn)題是的計(jì)算 2( ) v s 1 1,2 1,3 i v(s) 0 40 0 64 v(s1) 0 0 0 25 v(s)-v(s1) 0 40 0 39 |s| 1 2 2 3 w(|s|) 1/3 1/6 1/6 1/3 w(|s|) v(s)-v(s1) 0 6.7 0 13 最后，同理運(yùn)用 shapley 值法可以算出在聯(lián)合建廠(chǎng)方案總投資額 556 千元中各 城分擔(dān)費(fèi)用為：城 1 是；城 2 是 1 (1)( )230 19.7210.4cv ；城 3 是。 2 (2)( )127.9cv 3 (3)( )217.8cv

46、 5.3 shapley 值法存在的缺陷 shppley 值法以嚴(yán)格的條件為基礎(chǔ)，在處理合作對(duì)策的分配問(wèn)題時(shí)比較公正 合理等，但是它需要知道所有合作方的獲利，即需要定義的所有1,2,.,in 子集（共個(gè)）的特征函數(shù)，這實(shí)際上是很難做到的。如 n 個(gè)單位共同合作治2n 理污染，第 i 方單獨(dú)治理的投資和 n 方共同合作治理的投資 y，這通常是已 i y 知的。為了度量第 i 方在合作中的“貢獻(xiàn)” ，還常需要設(shè)法知道第 i 方不參加時(shí) 其余 n-1 方所需的投資。特征函數(shù)應(yīng)定義為共同合作的獲利，即節(jié)約的投資， i z 有( )0(1,2,. ),v iin 顯然除此之外還有很多無(wú)法獲取，無(wú)法應(yīng) 1

47、 ( ), ( ) n iji ij i v iyy v i iyz ( )v s 用 shapley 值方法求解。 5.4 其他求解方法 以下仍以例 3 提出的三人經(jīng)商問(wèn)題為例，介紹兩種其它的解決方法。 【例 4】我們只知道全體合作的獲利，記作，及無(wú) i 參加時(shí)其他 n-1 方( )v ib 合作的獲利，記作試確定各方對(duì)全 12 ( )(1,2,., )( ,.,). in v i ib inbb bb，且記 體合作獲利的分配，記得在三人經(jīng)商問(wèn)題， 12 ( ,.,). n xx xx * 11,(4,5,7),bb 求 123 ( ,).xx x x 5.4.1 協(xié)商解16 分配分別按照以

48、下兩步進(jìn)行。先從 n 個(gè) n-1 方合作的獲利求出各方分配的下限 ，即求解 12 ( ,.,) n xx xx 11 1 1 . n i i n inn i xxb xxb 得到 1 1 ,1,2,., 1 n iii i xbb in n 再求出按下限分配后全體合作獲利的剩余為，它通常是較小的部分，x 1 n i i bx 經(jīng)過(guò)協(xié)商將其平均分配，于是最終的分配結(jié)果為 11 11 () nn iiiii ii b xxbxbb nnn 剩余，它等價(jià)于 1 0 n i i bx 1 1 1 n i i bb n 對(duì)三人經(jīng)商問(wèn)題，(4,3,1),(5,4,2)xx 5.4.2 raiffa 解 h

49、oward raiffa 提出的解決辦法按以下的步驟進(jìn)行17： （1）按照 n 個(gè) n-1 方合作的獲利得到了各方分配的下限，即協(xié)商解中的，作x 為分配的前提； （2）當(dāng) j 方加入（原來(lái)無(wú) j 的）n-1 方合作時(shí)，計(jì)算獲利的增加，即 j 方的邊際 效益17，就是最小距離解中的上限； jj xbb （3）按兩步分配：首先先由 j 方和無(wú) j 方的 n-1 方平分，然后 n-1 方再等分， j x 即 ,1,2,., , 22(1) jj jii xx xxxin ij n 其中 n-1 方是在的基礎(chǔ)上分配的；x （4）j 取 1,2,n，再重復(fù)第 3 步，然后求和、平均，得到最終分配為 (5

50、.5) 111 ,1,2,., 22(1) i iij j i xn xxxin nnn 將，代入，(5.5)式可表為xx 1 231 ,1,2,., 2(1) n iii i bn xbbin nnn a1 a2 a3 o b1 b2 b3 b4 對(duì)三人經(jīng)商問(wèn)題， 2115 (4,3,1),(7,6,4),(4,3,2). 31212 xxx 6 6 傳統(tǒng)模型的改進(jìn)設(shè)想傳統(tǒng)模型的改進(jìn)設(shè)想 6.1 最小元素法的改進(jìn)設(shè)想 表上作業(yè)法是求解運(yùn)輸成本最優(yōu)化問(wèn)題的常用而有效的方法，但是表上作 業(yè)法求解過(guò)程比較復(fù)雜，而且如果供求雙方數(shù)量比較多，檢驗(yàn)數(shù)的計(jì)算和閉回 路的調(diào)整更容易出錯(cuò)。因此，如果初始方案的

51、給定能盡可能地趨向最優(yōu)化，在 運(yùn)輸成本預(yù)算比較充裕的情況下可以直接采用初始方案。 初始方案給定的方法最常用的是最小元素法，而最小元素法的物資配送是 滿(mǎn)足運(yùn)輸配送的每一次單位運(yùn)價(jià)都最小化，但從整體上考慮，它并不能保證總 運(yùn)價(jià)達(dá)到最小，也不能在第一時(shí)間滿(mǎn)足需求點(diǎn)的一定量的物資需求。因此，本 文將對(duì)最小元素法的配送過(guò)程進(jìn)行調(diào)整，首先通過(guò)對(duì)物資配送環(huán)節(jié)進(jìn)行改進(jìn)， 可以在第一時(shí)間滿(mǎn)足某些需求點(diǎn)的物資需求，然后通過(guò)增加一臨時(shí)節(jié)點(diǎn)c（該 點(diǎn)是離需求方較近的一點(diǎn)） ，對(duì)所有供應(yīng)點(diǎn)經(jīng)過(guò)一定階段配送后的剩余物資進(jìn)行 重新分配，這樣可以使運(yùn)輸總成本得到優(yōu)化。 圖 6-1 傳統(tǒng)的最小元素法配送網(wǎng)絡(luò) a1 a2 a3

52、o b1 b2 b3 b4 c 圖 6-2 改進(jìn)后的最小元素法配送網(wǎng)絡(luò) 6.2 效益分配的改進(jìn)設(shè)想 在經(jīng)濟(jì)生活中，效益分配問(wèn)題最常見(jiàn)的是合作分配利益問(wèn)題，前面主要介 紹了 shapley 值效益分配法，但這種方法主要的缺陷是需要知道合作各方在活 動(dòng)中的“貢獻(xiàn)” ，還有總的合作效益，這在實(shí)際生活中是難以評(píng)估的，因?yàn)橐粋€(gè) 項(xiàng)目還沒(méi)開(kāi)展，其效益很難作出準(zhǔn)確的評(píng)估。這里將通過(guò)合作各方以往的工作 效益制定一定的分配標(biāo)準(zhǔn)，在項(xiàng)目完成之后總效益算出來(lái)再進(jìn)行分配。 設(shè)有三個(gè)工程師甲乙丙共同合作參與完成一個(gè)項(xiàng)目，甲乙丙一個(gè)月的工作 效益是分別是、（假設(shè)三人一個(gè)月的工作時(shí)間一樣，而且工作效益變 1 x 2 x 3

53、 x 動(dòng)不大） ，項(xiàng)目完成時(shí)三人的工作時(shí)間分別為、，總的效益為 ，則三 1 t 2 t 3 ts 人應(yīng)分配的效益之比為： (6.1) 332211321 :txtxtxsss 明顯，由前提條件可以得到： (6.2)ssss 321 由式(6.1)和式(6.2)可以得到甲乙丙三人分配的效益分別為： s txtxtx tx s 332211 11 1 s txtxtx tx s 332211 22 2 s txtxtx tx s 332211 33 3 7 7 總結(jié)與展望總結(jié)與展望 7.1 本文的主要貢獻(xiàn) 數(shù)學(xué)與我們?nèi)粘Ｉ蠲芮邢嚓P(guān)，日常生活中的許多問(wèn)題來(lái)源于數(shù)學(xué)思想的 應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)

54、的前提下，結(jié)合日常當(dāng)中可能出現(xiàn)的數(shù)學(xué)問(wèn)題， 通過(guò)適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。通過(guò)對(duì)日 常生活中經(jīng)常涉及到的若干最優(yōu)化問(wèn)題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原 理并將其推廣應(yīng)用到其他生活案例當(dāng)中去18。 本文的主要貢獻(xiàn)有以下幾個(gè)方面：首先，本文主要選取了生活中較具有代 表性的運(yùn)輸成本問(wèn)題和效益分配問(wèn)題進(jìn)行最優(yōu)化研究，分別詳細(xì)地介紹了表上 作業(yè)法和 shapley 值法的求解過(guò)程。然后，根據(jù)這兩種求解方法的局限性和普 遍性進(jìn)行分析，指出了這兩種模型存在的缺陷和不足，最后，針對(duì)模型存在的 缺陷分別提出了相應(yīng)的改進(jìn)方法，并將其推廣應(yīng)用到其他不同的領(lǐng)域19。 7.2 本文主要的

55、改進(jìn)方案 運(yùn)用表上作業(yè)法解決運(yùn)輸成本問(wèn)題存在著一定的局限性，主要應(yīng)用于產(chǎn)銷(xiāo) 平衡的運(yùn)輸問(wèn)題，但實(shí)際問(wèn)題中產(chǎn)銷(xiāo)往往是不平衡的。為了應(yīng)用表上作業(yè)法計(jì) 算，就需要把產(chǎn)銷(xiāo)不平衡的問(wèn)題化成產(chǎn)銷(xiāo)平衡的問(wèn)題。當(dāng)總的產(chǎn)量大于銷(xiāo)量時(shí)， 可以考慮將多余的物資在那一個(gè)產(chǎn)地就地庫(kù)存，此時(shí)需要在產(chǎn)銷(xiāo)平衡表上增加 一個(gè)假想的銷(xiāo)地，通過(guò)這樣的修改，原先不平衡的運(yùn)輸問(wèn)題就轉(zhuǎn)化成為產(chǎn)銷(xiāo)平 衡問(wèn)題了。當(dāng)總的銷(xiāo)量大于產(chǎn)量時(shí)，同理可以在產(chǎn)銷(xiāo)平衡表中增加一個(gè)假想的 產(chǎn)地，同時(shí)在單位運(yùn)價(jià)表上設(shè)定該假想產(chǎn)地到各銷(xiāo)地的運(yùn)價(jià)為零，同樣轉(zhuǎn)化成 為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。通過(guò)這樣的轉(zhuǎn)化問(wèn)題就能順利解決了20。 shapley 值方法嚴(yán)格的公理為基礎(chǔ)，在處理合作對(duì)策問(wèn)題時(shí)具有公平、合理 等特點(diǎn)，但是它需要知道所有合作的獲利，合作方越多，需要的信息就越大， 在實(shí)際上這些信息往往難以完全提供。協(xié)商解法計(jì)算相對(duì)簡(jiǎn)單，且便于理解， 但通常偏袒強(qiáng)者，可用于各方實(shí)力相差不大的情況。raiffa 解法考慮了分配的 上下限，又吸取了 shapley 的思想，在一定的程序上保護(hù)弱者。因此，只要根 據(jù)問(wèn)題提供的條件和要求，運(yùn)用相應(yīng)的