全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽-運(yùn)輸問(wèn)題(參考答案)

2003高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題參考答案注意：以下答案是命題人給出的，僅供參考。各評(píng)閱組應(yīng)根據(jù)對(duì)題目的理解及學(xué)生的解答，自主地進(jìn)行評(píng)閱。問(wèn)題分析：本題目與典型的運(yùn)輸問(wèn)題明顯有以下不同：1．運(yùn)輸?shù)V石與巖石兩種物資；2．產(chǎn)量大于銷(xiāo)量的不平衡運(yùn)輸；3．在品位約束下礦石要搭配運(yùn)輸；4．產(chǎn)地、銷(xiāo)地均有單位時(shí)間的流量限制；5．運(yùn)輸車(chē)輛每次都是滿(mǎn)載，154噸/車(chē)次；6．鏟位數(shù)多于鏟車(chē)數(shù)意味著最優(yōu)的選擇不多于7個(gè)產(chǎn)地；7．最后求出各條路線上的派出車(chē)輛數(shù)及安排。運(yùn)輸問(wèn)題對(duì)應(yīng)著線性規(guī)劃，以上第1、2、3、4條可通過(guò)變量設(shè)計(jì)、調(diào)整約束條件實(shí)現(xiàn)；第5條使其變?yōu)檎麛?shù)線性規(guī)劃；第6條用線性模型實(shí)現(xiàn)的一種辦法，是從個(gè)整數(shù)規(guī)劃中取最優(yōu)的即得到最佳物流；對(duì)第7條由最佳物流算出各條路線上的最少派出車(chē)輛數(shù)（整數(shù)），再給出具體安排即完成全部計(jì)算。對(duì)于這個(gè)實(shí)際問(wèn)題，要求快速算法，計(jì)算含50個(gè)變量的整數(shù)規(guī)劃比較困難。另外，這是一個(gè)二層規(guī)劃，第二層是組合優(yōu)化，如果求最優(yōu)解計(jì)算量較大，現(xiàn)成的各種算法都無(wú)能為力。于是問(wèn)題變?yōu)檎乙粋€(gè)尋求近優(yōu)解的近似解法，例如可用啟發(fā)式方法求解。調(diào)用120次整數(shù)規(guī)劃可用三種方法避免：（1）先不考慮電鏟數(shù)量約束運(yùn)行整數(shù)線性規(guī)劃，再對(duì)解中運(yùn)量最少的幾個(gè)鏟位進(jìn)行篩選；（2）在整數(shù)線性規(guī)劃的鏟車(chē)約束中調(diào)用－1變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。函數(shù)來(lái)實(shí)現(xiàn)；（3）增加10個(gè)0這是一個(gè)多目標(biāo)規(guī)劃，第一問(wèn)的目標(biāo)有兩層：第一層是總運(yùn)量（噸公里）最小，第二層是出動(dòng)卡車(chē)數(shù)最少，從而實(shí)現(xiàn)運(yùn)輸成本最小。第二問(wèn)的目標(biāo)有：巖石產(chǎn)量最大；礦石產(chǎn)量最大；運(yùn)量最小，三者的重要性應(yīng)按此序。合理的假設(shè)主要有：1.卡車(chē)在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；2.在鏟位或卸點(diǎn)處因兩條路線（及以上）造成的沖突時(shí)，只要平均時(shí)間能完成任務(wù)即可，不進(jìn)行排時(shí)討論；3.空載與重載的速度都是28km/h，耗油相差卻很大，因此總運(yùn)量只考慮重載運(yùn)量；4.卡車(chē)可提前退出系統(tǒng)。符號(hào)：xij~從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量單位噸；cij~從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離公里；Tij~從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)路線上運(yùn)行一個(gè)周期平均所需時(shí)間分；Aij~從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車(chē)數(shù)Bij~從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)路線上一輛車(chē)最多可以運(yùn)行的次數(shù)次；輛；pi~i號(hào)鏟位的礦石鐵含量。%p=(30,28,29,32,31,33,32,31,33,31)qj~j號(hào)卸點(diǎn)任務(wù)需求噸q=(1.2,1.3,1.3,1.9,1.3)*10000cki~i號(hào)鏟位的鐵礦石儲(chǔ)量萬(wàn)噸cyi~i號(hào)鏟位的巖石儲(chǔ)量萬(wàn)噸fi:~描述第i號(hào)鏟位是否使用的0-1開(kāi)關(guān)變量，取1為使用；取0為關(guān)閉。模型建立、算法設(shè)計(jì)與模型求解：?jiǎn)栴}一、求運(yùn)輸成本最小的生產(chǎn)計(jì)劃一．以總運(yùn)量最小為目標(biāo)函數(shù)求解最佳物流—-第一層規(guī)劃（1）道路能力約束：一個(gè)電鏟（卸點(diǎn)）不能同時(shí)為兩輛卡車(chē)服務(wù)，一條路線上最多能同時(shí)運(yùn)行的卡車(chē)數(shù)是有限制的?？ㄜ?chē)從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)運(yùn)行一個(gè)周期平均所需時(shí)間為（分鐘）。由于裝車(chē)時(shí)間5分鐘大于卸車(chē)時(shí)間3分鐘，所以這條路線上在卡車(chē)不等待條件下最多能同時(shí)運(yùn)行的卡車(chē)數(shù)為：；其中最后開(kāi)始發(fā)車(chē)的一輛卡車(chē)一個(gè)班次中在這條路線上最多可以運(yùn)行的次數(shù)為（其他卡車(chē)可能比此數(shù)多1次），這里是開(kāi)始裝車(chē)時(shí)最后一輛車(chē)的延時(shí)時(shí)間。一個(gè)班次中這條固定路線上最多可能運(yùn)行的總車(chē)次大約為：，總噸數(shù)。（2）電鏟能力約束：一臺(tái)電鏟不能同時(shí)為兩輛卡車(chē)服務(wù)，所以一臺(tái)電鏟在一個(gè)班次中的最大可能產(chǎn)量為8×60/5×154（噸）。（3）卸點(diǎn)能力約束：卸點(diǎn)的最大吞吐量為每小時(shí)60/3=20車(chē)次，于是一個(gè)卸點(diǎn)在一個(gè)班次中的最大可能產(chǎn)量為8×20×154（噸）。（4）鏟位儲(chǔ)量約束：鏟位的礦石和巖石產(chǎn)量都不能超過(guò)相應(yīng)的儲(chǔ)藏量。（5）產(chǎn)量任務(wù)約束：各卸點(diǎn)的產(chǎn)量不小于該卸點(diǎn)的任務(wù)要求。（6）鐵含量約束：各礦石卸點(diǎn)的平均品位要求都在指定的范圍內(nèi)。（7）電鏟數(shù)量約束：電鏟數(shù)量約束無(wú)法用普通不等式表達(dá)，可以引入10個(gè)0—1變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。（8）整數(shù)約束：當(dāng)把問(wèn)題作為整數(shù)規(guī)劃模型時(shí)，流量xij除以154為非負(fù)整數(shù)。（9）卡車(chē)數(shù)量約束：不超過(guò)20輛。得到的一種模型為（0）s.t.（1）（2）（3）（4）（5）（6）.（7）（8）（9）二．對(duì)最佳物流的結(jié)果進(jìn)行派車(chē)—-第二層規(guī)劃這是組合優(yōu)化中的一維背包模型，針對(duì)快速算法的要求，用啟發(fā)式方法求近優(yōu)解。先用最佳物流修正Bij,確定卡車(chē)一個(gè)班次中在這條路線上實(shí)際最多可以運(yùn)行的次數(shù)。然后在以目標(biāo)為出動(dòng)總卡車(chē)數(shù)最少的各路線派車(chē)中，把各路線需要的卡車(chē)數(shù)分成整數(shù)部分和小數(shù)部分，進(jìn)而可以分配任務(wù)讓輛車(chē)在i到j(luò)路線上，每輛往返運(yùn)輸Bij次。為了最后實(shí)現(xiàn)第二層規(guī)劃的目標(biāo)，只需聯(lián)合處理所有的時(shí)把這些小數(shù)組合成