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

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

2、教師簽名復(fù)評教師簽名 年年 月月 日日 畢業(yè)論文（設(shè)計）答辯評語及成績畢業(yè)論文（設(shè)計）答辯評語及成績 成績成績 答辯委員會主席簽名答辯委員會主席簽名 年年 月月 日日 畢業(yè)論文（設(shè)計）總成績（五級記分制）畢業(yè)論文（設(shè)計）總成績（五級記分制） 院（系）負(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)，日常生活中的許多問題來源于數(shù)學(xué) 思想的應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常當(dāng)中可能出現(xiàn) 的數(shù)學(xué)問題，通過適當(dāng)?shù)囊?guī)劃安排，運用數(shù)學(xué)原理求解出行之有效的最 優(yōu)化方案。 本文的主要研究方向是通過對日常生活中經(jīng)常涉及到的若干最優(yōu)化 問題進(jìn)行歸納總結(jié)，分析其所涉及的數(shù)學(xué)原理并將其推廣應(yīng)用到其他生 活案例當(dāng)中去。本文的主要貢獻(xiàn)是通過對運輸成本問題和效益分配問題 的最優(yōu)化分析，詳細(xì)地介紹了表上作業(yè)法和 shapley 值法的求解過程， 指出了模型存在的缺陷和不足，并對模型進(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 運輸調(diào)配方向 .3 3.2 效益分配方向.3 4 4 運輸調(diào)配問題最優(yōu)化研究運輸調(diào)配問題最優(yōu)化研究 .3 3 4.1 初始方案的給定 .4 4.2 最優(yōu)性檢驗與方案的調(diào)整 .6 4.3 表上作業(yè)法的總結(jié) .8 4.4 表上作業(yè)法的改進(jìn)及其推

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

10、一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常生活當(dāng)中可能出現(xiàn)的數(shù)學(xué)問 題，通過適當(dāng)?shù)囊?guī)劃安排，運用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。本文 通過對日常生活中經(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)用 價值，是一種能夠調(diào)動高校學(xué)生積極學(xué)習(xí)數(shù)學(xué)的辦法3。 2 2 研究現(xiàn)狀分析研究現(xiàn)狀分析 2.1 研究的方法 不同類型的最優(yōu)化問題可以有不同的最優(yōu)化方法，即使同一類型的問題也 可有多種最優(yōu)化方法。反之，某些最優(yōu)化方法可適用于不同類型的模型。目前， 最優(yōu)化問題的求解方

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

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

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

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

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

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

17、【例 1】某食品加工公司經(jīng)銷的主要產(chǎn)品之一是酸奶。該公司下面設(shè)有三個加 工廠，每天酸奶的生產(chǎn)量分別為：，。該公司把這些酸 1 7at 2 4at 3 9at 奶分別運往四個地區(qū)的門市部進(jìn)行銷售，各地區(qū)每天的銷售量分別為： ，。已知從每個加工廠到對應(yīng)的各銷售門市部 1 3bt 2 6bt 3 5bt 4 6bt 每噸酸奶的運價如表 4-1 所示，問該食品公司該如何調(diào)運，在滿足各門市部銷 售需要的前提下，使得總運費支出達(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è)法求解運輸問題，首先給出一個初始

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

19、思想是就近 供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，依此類推，一直到給 出全部方案為止10。 門市部 加工廠 銷地 產(chǎn)地 銷地 產(chǎn)地 第一步：從表 4-3 的單位運價表中找出最小運價為 1（如果有兩個最小運價時 任選其一） ，即從生產(chǎn)的酸奶首先供應(yīng)需求。由于每天生產(chǎn) 4t，每天 2 a 1 b 2 a 1 b 需要 3t,即每天生產(chǎn)的除了要滿足全部需求之外，還剩下 1t。因此在表 4- 2 a 1 b 2 中（，）的交叉格中填上數(shù)字 3，表示調(diào)運 3t 酸奶給，再在表 4-3 2 a 1 b 2 a 1 b 中將所在的這一列運價劃去，表示已經(jīng)滿足的需求，無需繼續(xù)調(diào)運給它。 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 銷量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 中未劃去的元素之中找出最小的運價為 2，即每天剩余的 2 a 酸奶要供應(yīng)給。每天需要 5t，每天只能供應(yīng) 1t，因此在表 4-4（， 3 b 3 b 2 a 2 a ）交叉處填寫 1，劃去表 4-5 所在的這一行運價，表示生產(chǎn)的酸奶已 3 b 2 a 2 a 分配完，其結(jié)果見表 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 銷量3 6 5 6 銷地 產(chǎn)地 銷地 產(chǎn)地 銷地 產(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 第三步：同理再從表 4-7 中未劃去的元素之中找出最小的元素為 3，即生產(chǎn) 1 a 的酸奶應(yīng)優(yōu)先滿足需求。每天生產(chǎn) 7t，還缺 4t。因此在表中 3 b 1 a 3 b （，）交叉格內(nèi)填上 4，由于的需求此時已經(jīng)滿足，在表 4-7 中劃去 1 a 3 b 3 b 所在列的元素。 3 b 這樣一步一步地進(jìn)行下去，直到

22、單位運價表上所有元素都被劃去為止，這時在 產(chǎn)銷平衡表上可以得到一個調(diào)動方案（見表 4-8） ，這個調(diào)動方案總的運費為 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 銷量3 6 5 6 4.2 最優(yōu)性檢驗與方案的調(diào)整 最小元素法給出的是運輸問題的一個基可行解，需要通過最優(yōu)性檢驗判別 該解的目標(biāo)函數(shù)值是否達(dá)到最優(yōu)，當(dāng)為否時，應(yīng)進(jìn)行調(diào)整得到優(yōu)化。檢驗的方 法常用的有閉回路法和位勢法，這里采用閉回路法。運輸問題中的閉回路是指 調(diào)運方案中的一個空格和幾個有數(shù)字格的水平和垂直之間的連線包圍成的封閉 回路11。 構(gòu)建閉回路是為了計算解

23、中各非基變量（對應(yīng)空格）的檢驗數(shù)，方法是令 某一非基變量取值為 1，通過變動原基變量的值找出一個的可行解，將其與原 來的基可行解進(jìn)行比較。在表 4-8 中給出了一個調(diào)運方案中， （，）是空 1 a 1 b 銷地 產(chǎn)地 銷地 產(chǎn)地 1 格，即為非基變量。令，相應(yīng)地為了找到新的可行解，原有基變量中 11 x 11 1x 需減 1，加 1，減 1，見表 4-9。表中由（，） ， （，） ， 13 x 23 x 21 x 1 a 1 b 1 a 3 b （，） ， （，）4 個格的水平和垂直連線圍成的閉回路，該閉回路除（ 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 新可行解與原來解費用比較：從 0 變成 1，運費加 3 元，減 1，運費減少 11 x 13 x 3 元，加 1，運費加 2 元，減 1，運費減少 1 元，由此新可行解較原來解 23 x 21 x 運費增加了（3-3+2-1）=1 元，稱為檢驗數(shù)，將其填入檢驗數(shù)表中（表 4-10） 的（，）相應(yīng)的交叉格位置。類似地（，）為空格，可通過該空格找 1 a 1 b 3 a 1 b 出一條其余頂點都有數(shù)字格的閉回路，求得其相應(yīng)的檢驗數(shù)為（7-1+2-3+10- 5）=10，將其填入檢驗數(shù)表 4-10 的（，）的交叉格位置

25、，因為任意的非 3 a 1 b 基向量均可表示為基向量的唯一線性組合，因此通過任一空格可以找到，并且 只能找到唯一的閉回路，并計算得到對應(yīng)表 4-8 中解全部非基變量的檢驗數(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 銷量3656 表 4-10 檢驗數(shù)表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 12 1 -1 10 12 銷地 產(chǎn)地 33 2 銷地 產(chǎn)地 如果檢驗數(shù)表中所有的數(shù)字都大于等于零，表明對調(diào)運方案作出任何改變 都不會導(dǎo)致運費減少，即給定的方案為最優(yōu)方案。但在表 4-10 中，

26、 （,） 2 a 4 b 格的檢驗數(shù)是負(fù)的，說明方案仍需進(jìn)一步調(diào)整。改進(jìn)的方法是從檢驗數(shù)為負(fù)數(shù) 的格出發(fā)（當(dāng)存在兩個以上負(fù)數(shù)檢驗數(shù)時，從絕對值最大的負(fù)檢驗數(shù)格出發(fā)） ， 這里是從（,）格出發(fā)，作一條除該空格以外其余頂點都為有數(shù)字格而組 2 a 4 b 成的閉回路。在這條閉回路上，按照以上講的方法對運量作最大限度的調(diào)整。 從表 4-9 看出，為了把生產(chǎn)的酸奶調(diào)運給，就要相應(yīng)減少調(diào)運給的 2 a 4 b 2 a 3 b 酸奶和調(diào)運給的酸奶，才能得到新的平衡。這兩個格內(nèi)，較小運量為 1， 1 a 4 b 因此最多只能調(diào)運 1t 酸奶給。由此得到一個新的調(diào)運方案（見表 4-11） 。 2 a 4 b

27、這個新方案的運費為 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 銷量3 6 5 6 表 4-11 給出的調(diào)運方案是否達(dá)到最優(yōu)，仍需對這個方案的每一個空格求出 其檢驗數(shù)（見表 4-12） 。由于檢驗數(shù)表中所有的檢驗數(shù)大于等于零，因此肯定 表 4-11 給出的方案是最優(yōu)方案。 表 4-12 檢驗數(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ōu)化解決方法主要有三個步驟，可以用以下流程圖總結(jié)出 來，見圖 4-1。 銷地 產(chǎn)地 銷地 產(chǎn)地 否

28、 分析實際問題列出產(chǎn)銷 平衡表及單位運價表 確定初始調(diào)運方案 求檢驗數(shù) 所有檢驗數(shù)0 找出絕對值最大的負(fù)檢驗數(shù)用 閉回路調(diào)整，得出新的調(diào)運方 案 得到最優(yōu)方案 算出總的運價 是 圖 4-1 表上作業(yè)法計算步驟框圖 4.4 表上作業(yè)法的改進(jìn)及其推廣應(yīng)用 前面所講的表上作業(yè)法的計算理論，都是以產(chǎn)銷平衡為前提的，即 。但實際問題中大部分產(chǎn)銷是不平衡的。為了更好地應(yīng)用表上作業(yè) 11 mn ij ij ab 法，就需要把產(chǎn)銷不平衡的問題轉(zhuǎn)化成產(chǎn)銷平衡的問題13。 當(dāng)產(chǎn)大于銷時，運輸問題的數(shù)學(xué)模型可寫為 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)量大于銷量，可以考慮多余的物資在那一個產(chǎn)地庫存的。設(shè)是 ,1i n x 產(chǎn)地的庫存量，于是可以得到 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）模型中，是一個產(chǎn)銷平衡的運輸問題。因 1 1 111 mnn iini ijj abbb 此當(dāng)產(chǎn)量大于銷量時，只需增加一個假想的銷地 j=n+1(實際上庫存銷地的單位 運價，就可以轉(zhuǎn)化成為一個產(chǎn)銷平衡的運輸問題。類似地，當(dāng)銷量大于

31、,1 0 i n c 產(chǎn)量時，可以在產(chǎn)銷平衡中增加一個假想的產(chǎn)地，該地產(chǎn)量為1im ，在單位運價表中令從該假想產(chǎn)地到各銷地的運價，同 11 () nm ji ji ba 1, 0 mj c 樣可以轉(zhuǎn)化成為一個產(chǎn)銷平衡的運輸問題。 【例 2】設(shè)有三個產(chǎn)地生產(chǎn)某種物資，三個產(chǎn)地的產(chǎn)量分別為 123 ,a a a 7t、5t、7t，四個銷地需要該種物資，銷量分別為 1234 ,b b b b 2t、3t、4t、6t，又知各產(chǎn)銷地之間的單位運價見表 4-13，試解出總運費最少 的調(diào)動方案。 表 4-13 單位運價表 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，銷地總銷量為 15t，因此這是產(chǎn)銷不平衡的運輸問題。 可按照上述方法轉(zhuǎn)化成為產(chǎn)銷平衡的運輸問題，轉(zhuǎn)化之后其產(chǎn)銷平衡表和單位 運價表分別見表 4-14、見表 4-15. 表 4-14 產(chǎn)銷平衡表 庫存 1 b 2 b 3 b 4 b產(chǎn)量 1 a 2 a 3 a 7 5 7 銷量2 3 4 6 4 表 4-15 單位運價表 庫存 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 銷地 產(chǎn)地 銷地 產(chǎn)地 銷地 產(chǎn)地 對表 4-14、表 4-15 可以用表上作業(yè)法計算求出最優(yōu)方案如表

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

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

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

36、人集合，s 為 n 人集合中的任一種合 作，v(s)為合作中 s 的效益。 用表示 i 的成員 i 從合作的最大效益 v(i)中應(yīng)得到的一份收入。 i x 叫做合作對策的分配，滿足 12 ,., n xx xx 1 ( ) n i i xv i ，( ) i xv i1,2,.,in shapley 值由特征函數(shù) v 確定，記作。對于任意的子 12 ( )( ),( ),.,( ) n vvvv 集 s，記，即 s 中各成員的分配。對一切，滿足的 x( ) i i s x sx si( )( )x sv s 組合的集合稱的核心。當(dāng)核心存在時，即所有的 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 中的元素數(shù)目（人數(shù)） ，w(|s|)是 i s 加權(quán)因子，si 表示 s 去掉 i 后的集合。 接下來利用這組公式計算例 3 給出的三人經(jīng)商問題的分配，以此來解釋公式的 用法和意義。 甲乙丙三人記為，經(jīng)商獲利的定義為 i 上的特征函

38、數(shù)，即1,2,3i ()0, (1)(2)(3)1, (1,2)7, (1,3)5, (2,3)4vvvvvvv 。容易驗證 v 滿足(5.1)和(5.2)。為計算首先找出 i 的所有子集( )10v i 1( ) v ，然后 s 跑遍，將計算結(jié)果記入表 5-1.最后將表中末行 1: 1 , 1,2 , 1,3 , si 1 s 相加得到。 1( ) 4v 元 表 5-1 三人經(jīng)商中甲的分配的計算 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 值方法可以計算出，。所以， 2( ) 3.5v萬元 3( ) 2.5v萬元 甲乙丙三人合作合理的分配分別為 4 萬元、3.5 萬元、2.5 萬元。 5.2 shapley 值的推廣應(yīng)用 【例 4】設(shè)沿河有三城鎮(zhèn) 1，2，和 3，地理位置如圖 2 所示。污水需要處理后 才能排入河中。三個城鎮(zhèn)既可以單獨建立污水處理廠，也可以聯(lián)合建廠，用管 道將污水集中進(jìn)行處理（污水由河流上游的城鎮(zhèn)向下游城鎮(zhèn)輸送） 。用 q 表示污 水量（t/s） ，用 l 表示管道長度（km） ，按照經(jīng)驗公式，建立處理廠的費用為 ，鋪設(shè)管道費用為已知

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)合建廠，各城鎮(zhèn)如何分擔(dān)費用。 圖 5-1 三城鎮(zhèn)地理位置示意圖 【解】三城鎮(zhèn)污水處理共有以下 5 種方案，以下計算出投資費用以作比較。 （1） 分別建廠。其投資分別 為： 0.712 (1)73 5230,(2)160,(3)230ccca 總投資 1 (1)(2)(3)620dccc （2）1，2 合作，在城 2 建廠。投資為： 0.7120.51 (1,2)73 (53)0.66 520350c

41、 總投資 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）1，3 合作，在城 3 建廠。投資為： 0.7120.51 (1,3)73 (55)0.66 558463c 這個費用超過 1，3 分別建廠的費用。合作沒有效益，不可能(1)(3)460cc 實現(xiàn)。 （5）三城合作，在城 3 建廠。總投資為： 0.7120.510.51 5 (1,2,3)73 (535)0.66 5200.66 (53)38556dc 比較結(jié)果千元最小，所以應(yīng)選擇聯(lián)合建廠

42、方案。接下來的問題是如何 5 556d 分擔(dān)費用。 5 d 總費用中有 3 部分： 5 d 聯(lián)合建廠費為； 0.712 1 73 (535)453d 城 1 至 2 的管道費為； 0.51 2 0.66 (53)2030d 城 2 至 3 的管道費為. 0.51 3 0.66 (53)3873d 城 3 提出，由三城按污水量比例 5:3:5 分擔(dān)，是為城 1，2 鋪設(shè) 1 d 2 d 3 d 的管道費，應(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 提不出反對意見，按上述辦法各城 2 d 應(yīng)當(dāng)分擔(dān)的費用： 123 20km

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

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

45、 ( )( )( )64( )vvvv i 表 5-1 污水處理問題是的計算 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 最后，同理運用 shapley 值法可以算出在聯(lián)合建廠方案總投資額 556 千元中各 城分擔(dān)費用為：城 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ǔ)，在處理合作對策的分配問題時比較公正 合理等，但是它需要知道所有合作方的獲利，即需要定義的所有1,2,.,in 子集（共個）的特征函數(shù)，這實際上是很難做到的。如 n 個單位共同合作治2n 理污染，第 i 方單獨治理的投資和 n 方共同合作治理的投資 y，這通常是已 i y 知的。為了度量第 i 方在合作中的“貢獻(xiàn)” ，還常需要設(shè)法知道第 i 方不參加時 其余 n-1 方所需的投資。特征函數(shù)應(yīng)定義為共同合作的獲利，即節(jié)約的投資， i z 有( )0(1,2,. ),v iin 顯然除此之外還有很多無法獲取，無法應(yīng) 1

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

48、下兩步進(jìn)行。先從 n 個 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)過協(xié)商將其平均分配，于是最終的分配結(jié)果為 11 11 () nn iiiii ii b xxbxbb nnn 剩余，它等價于 1 0 n i i bx 1 1 1 n i i bb n 對三人經(jīng)商問題，(4,3,1),(5,4,2)xx 5.4.2 raiffa 解 h

49、oward raiffa 提出的解決辦法按以下的步驟進(jìn)行17： （1）按照 n 個 n-1 方合作的獲利得到了各方分配的下限，即協(xié)商解中的，作x 為分配的前提； （2）當(dāng) j 方加入（原來無 j 的）n-1 方合作時，計算獲利的增加，即 j 方的邊際 效益17，就是最小距離解中的上限； jj xbb （3）按兩步分配：首先先由 j 方和無 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 對三人經(jīng)商問題， 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ōu)化問題的常用而有效的方法，但是表上作 業(yè)法求解過程比較復(fù)雜，而且如果供求雙方數(shù)量比較多，檢驗數(shù)的計算和閉回 路的調(diào)整更容易出錯。因此，如果初始方案的

51、給定能盡可能地趨向最優(yōu)化，在 運輸成本預(yù)算比較充裕的情況下可以直接采用初始方案。 初始方案給定的方法最常用的是最小元素法，而最小元素法的物資配送是 滿足運輸配送的每一次單位運價都最小化，但從整體上考慮，它并不能保證總 運價達(dá)到最小，也不能在第一時間滿足需求點的一定量的物資需求。因此，本 文將對最小元素法的配送過程進(jìn)行調(diào)整，首先通過對物資配送環(huán)節(jié)進(jìn)行改進(jìn)， 可以在第一時間滿足某些需求點的物資需求，然后通過增加一臨時節(jié)點c（該 點是離需求方較近的一點） ，對所有供應(yīng)點經(jīng)過一定階段配送后的剩余物資進(jì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ì)生活中，效益分配問題最常見的是合作分配利益問題，前面主要介 紹了 shapley 值效益分配法，但這種方法主要的缺陷是需要知道合作各方在活 動中的“貢獻(xiàn)” ，還有總的合作效益，這在實際生活中是難以評估的，因為一個 項目還沒開展，其效益很難作出準(zhǔn)確的評估。這里將通過合作各方以往的工作 效益制定一定的分配標(biāo)準(zhǔn)，在項目完成之后總效益算出來再進(jìn)行分配。 設(shè)有三個工程師甲乙丙共同合作參與完成一個項目，甲乙丙一個月的工作 效益是分別是、（假設(shè)三人一個月的工作時間一樣，而且工作效益變 1 x 2 x 3

53、 x 動不大） ，項目完成時三人的工作時間分別為、，總的效益為 ，則三 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)，日常生活中的許多問題來源于數(shù)學(xué)思想的 應(yīng)用。在掌握一定的數(shù)學(xué)基礎(chǔ)

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

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