露天礦生產(chǎn)的車輛安排B

1、露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排 2002年年A（C）題）題露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排-問題陳述問題陳述裝卸點(diǎn)平面分布圖露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低平均鐵含量不低于于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間裝車時(shí)間5分鐘分鐘礦石卸點(diǎn)需要的鐵含量要求都為礦石卸點(diǎn)需要的鐵含量要求都為29.5%1%(品位品位限

2、制），搭配量在一個(gè)班次（限制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變。平均卸車時(shí)間限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變。平均卸車時(shí)間為為3分鐘。分鐘。主要因素與已知條件主要因素與已知條件:電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)。電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運(yùn)輸。卡車每次都是滿載運(yùn)輸。 卡車載重量為卡車載重量為154噸，平均時(shí)速噸，平均時(shí)速28km,卡車在等待卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)時(shí)不應(yīng)發(fā)生卡車等待不應(yīng)發(fā)生卡車等待的情況。的情況。 鏟位鏟位1

3、1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石量礦石量0.951.051.001.051.101.251.051.301.351.25巖石量巖石量1.251.101.351.051.151.351.051.151.351.25鐵含量鐵含量30%28%29%32%31%33%32%31%33%31%實(shí)例數(shù)據(jù)實(shí)例數(shù)據(jù): : 距離距離鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏5.265.194.214.

4、002.952.742.461.900.641.27倒裝倒裝1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)巖場(chǎng)5.895.615.614.563.513.652.462.461.060.57巖石漏巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝倒裝4.423.863.723.162.252.810.781.621.270.50有鏟位有鏟位10個(gè)，卸點(diǎn)個(gè)，卸點(diǎn)5個(gè)，鏟車個(gè)，鏟車7臺(tái)，卡車臺(tái)，卡車20輛。各卸輛。各卸點(diǎn)一個(gè)班次的產(chǎn)量要求：礦石漏點(diǎn)一個(gè)班次的產(chǎn)量要求：礦石漏1.2萬(wàn)噸、倒裝場(chǎng)萬(wàn)噸、倒裝場(chǎng)1.3萬(wàn)噸、倒裝場(chǎng)

5、萬(wàn)噸、倒裝場(chǎng)1.3萬(wàn)噸、巖石漏萬(wàn)噸、巖石漏1.9萬(wàn)噸、巖萬(wàn)噸、巖場(chǎng)場(chǎng)1.3萬(wàn)噸。萬(wàn)噸。 問題：?jiǎn)栴}：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次分別在哪些路線上各運(yùn)輸多少次 ? ?考慮下面兩條原則之一：考慮下面兩條原則之一： 1.1.總運(yùn)量（噸公里）最小，同時(shí)出動(dòng)最少的卡車，從總運(yùn)量（噸公里）最小，同時(shí)出動(dòng)最少的卡車，從而運(yùn)輸成本最小；而運(yùn)輸成本最小；2.2.利用現(xiàn)有車輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量?jī)?yōu)利用現(xiàn)有車輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量?jī)?yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解）先；在產(chǎn)量相同的情況下，取總運(yùn)量

6、最小的解）就兩條原則分別建立數(shù)學(xué)模型，并給出一個(gè)班次生產(chǎn)就兩條原則分別建立數(shù)學(xué)模型，并給出一個(gè)班次生產(chǎn)計(jì)劃的快速算法。針對(duì)下面的實(shí)例，給出具體的生產(chǎn)計(jì)劃的快速算法。針對(duì)下面的實(shí)例，給出具體的生產(chǎn)計(jì)劃、相應(yīng)的總運(yùn)量及巖石和礦石產(chǎn)量。計(jì)劃、相應(yīng)的總運(yùn)量及巖石和礦石產(chǎn)量。 問題分析問題分析 與典型的運(yùn)輸問題明顯有以下不同：與典型的運(yùn)輸問題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問題；這是運(yùn)輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問題；為了完成品位約束，礦石要搭配運(yùn)輸；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷地均有單位時(shí)間的流量限制；產(chǎn)地、銷地均

7、有單位時(shí)間的流量限制；運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，154噸噸/車次；車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個(gè)個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；產(chǎn)地作為最后結(jié)果中的產(chǎn)地；1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。運(yùn)輸問題對(duì)應(yīng)著線性規(guī)劃，以上第運(yùn)輸問題對(duì)應(yīng)著線性規(guī)劃，以上第1、2、3、4條可條可通過(guò)變量設(shè)計(jì)、調(diào)整約束條件實(shí)現(xiàn)；第通過(guò)變量設(shè)計(jì)、調(diào)整約束條件實(shí)現(xiàn)；第5條使其變條使其變?yōu)檎麛?shù)線性規(guī)劃；第為整數(shù)線性規(guī)劃；第6條用線性模型實(shí)現(xiàn)的一種辦條用線性模型實(shí)現(xiàn)的一種辦法，是從法，是從

8、 個(gè)整數(shù)規(guī)劃中取最優(yōu)的即得到最個(gè)整數(shù)規(guī)劃中取最優(yōu)的即得到最佳物流；對(duì)第佳物流；對(duì)第7條由最佳物流算出各條路線上的最條由最佳物流算出各條路線上的最少派出車輛數(shù)（整數(shù)），再給出具體安排即完成全少派出車輛數(shù)（整數(shù)），再給出具體安排即完成全部計(jì)算。部計(jì)算。對(duì)于這個(gè)實(shí)際問題，要求快速算法，計(jì)算含對(duì)于這個(gè)實(shí)際問題，要求快速算法，計(jì)算含50個(gè)變個(gè)變量的整數(shù)規(guī)劃比較困難。另外，這是一個(gè)二層規(guī)劃量的整數(shù)規(guī)劃比較困難。另外，這是一個(gè)二層規(guī)劃，第二層是組合優(yōu)化，如果求最優(yōu)解計(jì)算量較大，第二層是組合優(yōu)化，如果求最優(yōu)解計(jì)算量較大，現(xiàn)成的各種算法都無(wú)能為力。于是問題變?yōu)檎乙粋€(gè)現(xiàn)成的各種算法都無(wú)能為力。于是問題變?yōu)檎乙粋€(gè)尋

9、求近優(yōu)解的近似解法，尋求近優(yōu)解的近似解法，例如可用啟發(fā)式方法求解例如可用啟發(fā)式方法求解 120710C近似處理：近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排這是一個(gè)多目標(biāo)規(guī)劃，第一問的目標(biāo)有兩層：第一這是一個(gè)多目標(biāo)規(guī)劃，第一問的目標(biāo)有兩層：第一層是總運(yùn)量（噸公里）最小，第二層是出動(dòng)卡車數(shù)層是總運(yùn)量（噸公里）最小，第二層是出動(dòng)卡車數(shù)最少，從而實(shí)現(xiàn)運(yùn)輸成本最小。第二問的目標(biāo)有：最少，從而實(shí)現(xiàn)運(yùn)輸成本最小。第二問的目標(biāo)有：巖石產(chǎn)量最大；礦石產(chǎn)量最大；運(yùn)量最小，三者的巖石產(chǎn)量最大

10、；礦石產(chǎn)量最大；運(yùn)量最小，三者的重要性應(yīng)按此序。重要性應(yīng)按此序。調(diào)用調(diào)用120次整數(shù)規(guī)劃可用三種方法避免：（次整數(shù)規(guī)劃可用三種方法避免：（1）先不）先不考慮電鏟數(shù)量約束運(yùn)行整數(shù)線性規(guī)劃，再對(duì)解中運(yùn)考慮電鏟數(shù)量約束運(yùn)行整數(shù)線性規(guī)劃，再對(duì)解中運(yùn)量最少的幾個(gè)鏟位進(jìn)行篩選；（量最少的幾個(gè)鏟位進(jìn)行篩選；（2）在整數(shù)線性規(guī)劃）在整數(shù)線性規(guī)劃的鏟車約束中調(diào)用函數(shù)來(lái)實(shí)現(xiàn)；（的鏟車約束中調(diào)用函數(shù)來(lái)實(shí)現(xiàn)；（3）增加）增加10個(gè)個(gè)01變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。模型假設(shè)模型假設(shè) 卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；的情況； 在鏟

11、位或卸點(diǎn)處由兩條路線以上造成的沖突問題在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問題面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)為不沖突。我們不排時(shí)地進(jìn)行討論；為不沖突。我們不排時(shí)地進(jìn)行討論； 空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大；因此總運(yùn)量只考慮重載運(yùn)量因此總運(yùn)量只考慮重載運(yùn)量 卡車可提前退出系統(tǒng)，等等。卡車可提前退出系統(tǒng)，等等。符號(hào)符號(hào) xij ：從：從i號(hào)鏟位到號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量號(hào)卸點(diǎn)的石料運(yùn)量 (車車) 單位：噸單位：噸 cij ：從：從i號(hào)鏟位到號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離號(hào)卸點(diǎn)的距離 公里公里 Ti

12、j : 從從i號(hào)鏟位到號(hào)鏟位到j(luò)號(hào)卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間號(hào)卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間 分分 Aij ：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù) 輛輛 Bij ：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù)：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù) 次次 pi： i號(hào)鏟位的礦石鐵含量號(hào)鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j號(hào)卸點(diǎn)任務(wù)需求，號(hào)卸點(diǎn)任務(wù)需求， q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸 cki ：i號(hào)鏟位的鐵礦石儲(chǔ)量號(hào)鏟位的鐵礦石儲(chǔ)量 萬(wàn)噸萬(wàn)噸

13、cyi ：i號(hào)鏟位的巖石儲(chǔ)量號(hào)鏟位的巖石儲(chǔ)量 萬(wàn)噸萬(wàn)噸 fi : 描述第描述第i號(hào)鏟位是否使用的號(hào)鏟位是否使用的0-1變量，變量， 取取1為使用；為使用；0為關(guān)閉。為關(guān)閉。模型建立、算法設(shè)計(jì)與模型求解：模型建立、算法設(shè)計(jì)與模型求解： 問題一、求運(yùn)輸成本最小的生產(chǎn)計(jì)劃問題一、求運(yùn)輸成本最小的生產(chǎn)計(jì)劃一以總運(yùn)量最小為目標(biāo)函數(shù)求解最佳物流一以總運(yùn)量最小為目標(biāo)函數(shù)求解最佳物流-第第一層規(guī)劃一層規(guī)劃 一個(gè)電鏟（卸點(diǎn)）不能同時(shí)為兩輛卡車服務(wù)，一條一個(gè)電鏟（卸點(diǎn)）不能同時(shí)為兩輛卡車服務(wù)，一條路線上最多能同時(shí)運(yùn)行的卡車數(shù)是有限制的?？肪€上最多能同時(shí)運(yùn)行的卡車數(shù)是有限制的。卡車從車從i號(hào)鏟位到號(hào)鏟位到j(luò)號(hào)卸點(diǎn)

14、運(yùn)行一個(gè)周期平均所需時(shí)號(hào)卸點(diǎn)運(yùn)行一個(gè)周期平均所需時(shí)間為間為: 532平均速度距離到j(luò)iTij 道路能力約束：道路能力約束：5ijijTAijijijTAB5) 1(608(近似近似)最多能同時(shí)運(yùn)行的卡車數(shù)為：最多能同時(shí)運(yùn)行的卡車數(shù)為： 最后一輛卡車一個(gè)班次中在這條路線上最多可以運(yùn)最后一輛卡車一個(gè)班次中在這條路線上最多可以運(yùn)行的次數(shù)為行的次數(shù)為 :一個(gè)班次中這條固定路線上最多可能運(yùn)行的總車次一個(gè)班次中這條固定路線上最多可能運(yùn)行的總車次大約為：大約為： ijijijBAL總噸數(shù)總噸數(shù) 為為:ijL154一臺(tái)電鏟不能同時(shí)為兩輛卡車服務(wù)，所以一臺(tái)電鏟一臺(tái)電鏟不能同時(shí)為兩輛卡車服務(wù)，所以一臺(tái)電鏟在一個(gè)班

15、次中的最大可能產(chǎn)量為在一個(gè)班次中的最大可能產(chǎn)量為:860/5154（噸）。（噸）。 電鏟能力約束：電鏟能力約束： 卸點(diǎn)能力約束：卸點(diǎn)能力約束： 卸點(diǎn)的最大吞吐量為每小時(shí)卸點(diǎn)的最大吞吐量為每小時(shí)60/3=20車次，于是一車次，于是一個(gè)卸點(diǎn)在一個(gè)班次中的最大可能產(chǎn)量為個(gè)卸點(diǎn)在一個(gè)班次中的最大可能產(chǎn)量為:820154（噸）（噸） 鏟位儲(chǔ)量約束：鏟位儲(chǔ)量約束：鏟位的礦石和巖石產(chǎn)量都不能超過(guò)相應(yīng)的儲(chǔ)藏量。鏟位的礦石和巖石產(chǎn)量都不能超過(guò)相應(yīng)的儲(chǔ)藏量。 產(chǎn)量任務(wù)約束：產(chǎn)量任務(wù)約束：各卸點(diǎn)的產(chǎn)量不小于該卸點(diǎn)的任務(wù)要求。各卸點(diǎn)的產(chǎn)量不小于該卸點(diǎn)的任務(wù)要求。 鐵含量約束：鐵含量約束：各礦石卸點(diǎn)的平均品位要求都在指

16、定的范圍內(nèi)。各礦石卸點(diǎn)的平均品位要求都在指定的范圍內(nèi)。 整數(shù)約束：整數(shù)約束：當(dāng)把問題作為整數(shù)規(guī)劃模型時(shí)，流量當(dāng)把問題作為整數(shù)規(guī)劃模型時(shí)，流量xij除以除以154為為非負(fù)整數(shù)非負(fù)整數(shù) 卡車數(shù)量約束：卡車數(shù)量約束：不超過(guò)不超過(guò)20輛。輛。 電鏟數(shù)量約束：電鏟數(shù)量約束：電鏟數(shù)量約束無(wú)法用普通不等式表達(dá)，可以引入電鏟數(shù)量約束無(wú)法用普通不等式表達(dá)，可以引入10個(gè)個(gè)01變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。變量來(lái)標(biāo)志各個(gè)鏟位是否有產(chǎn)量。優(yōu)化模型優(yōu)化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1

17、,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力）道路能力(卡車數(shù)卡車數(shù))約束約束（2）電鏟能力約束）電鏟能力約束（3）卸點(diǎn)能力約束）卸點(diǎn)能力約束（4）鏟位儲(chǔ)量約束）鏟位儲(chǔ)量約束（5）產(chǎn)量任務(wù)約束）產(chǎn)量任務(wù)約束（6）鐵含量約束）鐵含量約束（7）電鏟數(shù)量約束）電鏟數(shù)量約束（8）整數(shù)約束）整數(shù)約束（9）車輛）車輛約束約束5 , 1,154/101jqxjiij5 , 2 , 1,0)5 .28(0)5 .30(101101jpxpxiiijiiij.7101iifxij為非負(fù)整數(shù)為非負(fù)整數(shù)fi 為為0-1整數(shù)整數(shù)20154,jiijijBx計(jì)算結(jié)果（

18、計(jì)算結(jié)果（LINGO軟件）軟件）車次車次鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦漏礦漏131354541111倒倒42424343巖場(chǎng)巖場(chǎng)70701515巖漏巖漏81814343倒倒13132 27070車輛數(shù)車輛數(shù)鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏0.8671.8620.314倒場(chǎng)倒場(chǎng)1.0771.162巖場(chǎng)巖場(chǎng)1.8920.326巖石漏巖石漏1.8411.229倒場(chǎng)倒場(chǎng)

19、0.6840.11.489計(jì)算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏1 (29)倒場(chǎng)1 (39)1 (37)巖場(chǎng)1 (37)巖石漏1(44)1 (35)倒場(chǎng)1 (47)此外：此外：6輛聯(lián)合派車方案為：輛聯(lián)合派車方案為： 第第1輛：從鏟位輛：從鏟位1、3到巖石漏，鏟位到巖石漏，鏟位1到巖石漏運(yùn)到巖石漏運(yùn)37車，鏟位車，鏟位3到巖石漏運(yùn)到巖石漏運(yùn)5車。車。 第第2輛：從鏟位輛：從鏟位9、10到巖場(chǎng)，鏟位到巖場(chǎng)，鏟位9到巖場(chǎng)運(yùn)到巖場(chǎng)運(yùn)33車，車，鏟位鏟位10到巖場(chǎng)運(yùn)到巖場(chǎng)運(yùn)5車。車。 第第3輛：從鏟位輛：從鏟位8、10到礦石漏，鏟位到礦石漏，鏟位8到礦石漏運(yùn)

20、到礦石漏運(yùn)22車，車，鏟位鏟位10到礦石漏運(yùn)到礦石漏運(yùn)6車。車。 第第4輛：從鏟位輛：從鏟位2、8到礦石漏，鏟位到礦石漏，鏟位2到礦石漏運(yùn)到礦石漏運(yùn)13車，鏟車，鏟位位8到礦石漏運(yùn)到礦石漏運(yùn)3車。車。 第第5輛：從鏟位輛：從鏟位2、4到倒裝場(chǎng)到倒裝場(chǎng)和從鏟位和從鏟位2、3到倒裝場(chǎng)到倒裝場(chǎng)，鏟位鏟位2到倒裝場(chǎng)到倒裝場(chǎng)運(yùn)運(yùn)3車，鏟位車，鏟位4到倒裝場(chǎng)到倒裝場(chǎng)運(yùn)運(yùn)6車，鏟位車，鏟位2到到倒裝場(chǎng)倒裝場(chǎng)運(yùn)運(yùn)13車，鏟位車，鏟位3到倒裝場(chǎng)到倒裝場(chǎng)運(yùn)運(yùn)1車。車。 第第6輛：從鏟位輛：從鏟位3到倒裝場(chǎng)到倒裝場(chǎng)、巖石漏和從鏟位、巖石漏和從鏟位10到礦石漏、到礦石漏、巖場(chǎng)、倒裝場(chǎng)巖場(chǎng)、倒裝場(chǎng)，鏟位，鏟位3到巖石漏

21、運(yùn)到巖石漏運(yùn)3車，鏟位車，鏟位3到倒裝場(chǎng)到倒裝場(chǎng)運(yùn)運(yùn)1車，鏟位車，鏟位10到倒裝場(chǎng)到倒裝場(chǎng)運(yùn)運(yùn)23車，鏟位車，鏟位10到巖場(chǎng)運(yùn)到巖場(chǎng)運(yùn)10車，鏟車，鏟位位10到礦石漏運(yùn)到礦石漏運(yùn)5車。車。結(jié)論：結(jié)論：鏟位鏟位1、2、3、4、8、9、10處各放置一臺(tái)電鏟。處各放置一臺(tái)電鏟。一共使用了一共使用了13輛卡車；總運(yùn)量為輛卡車；總運(yùn)量為85628.62噸公里；噸公里；巖石產(chǎn)量為巖石產(chǎn)量為32186噸；礦石產(chǎn)量為噸；礦石產(chǎn)量為38192噸。噸。問題二、利用現(xiàn)有車輛運(yùn)輸而獲得最大的產(chǎn)量問題二、利用現(xiàn)有車輛運(yùn)輸而獲得最大的產(chǎn)量第二問的解法和第一問類似，也采用多目標(biāo)二層規(guī)第二問的解法和第一問類似，也采用多目標(biāo)二

22、層規(guī)劃算法，第一層用整數(shù)線性規(guī)劃，第二層用求派出劃算法，第一層用整數(shù)線性規(guī)劃，第二層用求派出車輛數(shù)最小的啟發(fā)式方法。下面是第二問解法與第車輛數(shù)最小的啟發(fā)式方法。下面是第二問解法與第一問的不同之處。一問的不同之處。 如果是，把巖石的總產(chǎn)量取最大值如果是，把巖石的總產(chǎn)量取最大值,即加入到約束即加入到約束條件中，以礦石產(chǎn)量最大為目標(biāo)；如果否，把巖條件中，以礦石產(chǎn)量最大為目標(biāo)；如果否，把巖石產(chǎn)量最大做為目標(biāo)，求解最佳物流。石產(chǎn)量最大做為目標(biāo)，求解最佳物流。 由于巖石產(chǎn)量?jī)?yōu)先，第一層規(guī)劃計(jì)算前先做目標(biāo)由于巖石產(chǎn)量?jī)?yōu)先，第一層規(guī)劃計(jì)算前先做目標(biāo)函數(shù)取巖石產(chǎn)量最大（函數(shù)取巖石產(chǎn)量最大（ ）的試算，）的試算，

23、來(lái)判斷巖石產(chǎn)量是否能達(dá)到上限來(lái)判斷巖石產(chǎn)量是否能達(dá)到上限: 10143maxijijx492802154208 為了求巖石（或礦石）產(chǎn)量最大的同時(shí)，保證總為了求巖石（或礦石）產(chǎn)量最大的同時(shí)，保證總運(yùn)量運(yùn)量(噸公里噸公里)較小，還不影響輕重順序，運(yùn)量的加較小，還不影響輕重順序，運(yùn)量的加權(quán)系數(shù)很小。如權(quán)系數(shù)很小。如 可設(shè)目標(biāo)函數(shù)為。可設(shè)目標(biāo)函數(shù)為。cxxxxijijijiiii 101511015210001. 0)(maxcxxxijijijiii 10151101430001. 0)(max或或 約束條件（約束條件（1）至（）至（9）不變）不變 在現(xiàn)有條件下巖石產(chǎn)量能否達(dá)到上限在現(xiàn)有條件下巖石

24、產(chǎn)量能否達(dá)到上限 由于這個(gè)整數(shù)規(guī)劃的復(fù)雜性，所以必須考慮快速由于這個(gè)整數(shù)規(guī)劃的復(fù)雜性，所以必須考慮快速算法算法: 先求解去掉整數(shù)約束的相應(yīng)的線性規(guī)劃先求解去掉整數(shù)約束的相應(yīng)的線性規(guī)劃; 目標(biāo)值為目標(biāo)值為341.2807車次車次逐個(gè)減一地依次求逐個(gè)減一地依次求“礦石產(chǎn)量等于比礦石產(chǎn)量等于比342小的整數(shù)小的整數(shù)”加到約束條件中，目標(biāo)為總運(yùn)量最小的整數(shù)規(guī)劃。加到約束條件中，目標(biāo)為總運(yùn)量最小的整數(shù)規(guī)劃。第一個(gè)出現(xiàn)可行解的規(guī)劃的最優(yōu)解必為原整數(shù)規(guī)第一個(gè)出現(xiàn)可行解的規(guī)劃的最優(yōu)解必為原整數(shù)規(guī)劃的最優(yōu)解劃的最優(yōu)解 把礦石卸點(diǎn)的最大產(chǎn)量為把礦石卸點(diǎn)的最大產(chǎn)量為341車次作為約束條件加車次作為約束條件加入到整數(shù)

25、線性規(guī)劃中，沒有可行解。入到整數(shù)線性規(guī)劃中，沒有可行解。 把礦石卸點(diǎn)的最大產(chǎn)量為把礦石卸點(diǎn)的最大產(chǎn)量為340車次作為約束條件加車次作為約束條件加入到整數(shù)線性規(guī)劃中，得出的結(jié)果如下，即為所求入到整數(shù)線性規(guī)劃中，得出的結(jié)果如下，即為所求 最佳物流相對(duì)應(yīng)的各個(gè)路線上的最佳運(yùn)輸車次為：最佳物流相對(duì)應(yīng)的各個(gè)路線上的最佳運(yùn)輸車次為：車次數(shù)車次數(shù)鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏382418倒裝場(chǎng)倒裝場(chǎng)16542268巖場(chǎng)巖場(chǎng)127474巖石漏巖石漏80283220倒裝場(chǎng)倒裝場(chǎng)144602

26、2卡車數(shù)卡車數(shù)鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏2.11112.11110.82760.82760.40910.4091倒裝場(chǎng)倒裝場(chǎng)0 0555517171.38461.38460.75860.75861.83781.8378巖場(chǎng)巖場(chǎng)0.46150.46152 21.64441.6444巖石漏巖石漏1 1818182820.93330.93330.91430.91430.66670.6667倒裝場(chǎng)倒裝場(chǎng)0.73680.73680.20.21.93551.93550.46810

27、.4681 根據(jù)最佳物流計(jì)算各路線上需要的卡車數(shù)根據(jù)最佳物流計(jì)算各路線上需要的卡車數(shù) 所有路線所需卡車數(shù)（實(shí)數(shù)）的和，為所有路線所需卡車數(shù)（實(shí)數(shù)）的和，為19.66。 各路線上需要的整數(shù)卡車數(shù)為各路線上需要的整數(shù)卡車數(shù)為9（這些卡車在一（這些卡車在一個(gè)班次內(nèi)一直在固定路線上運(yùn)輸）個(gè)班次內(nèi)一直在固定路線上運(yùn)輸） 鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏2 2倒裝場(chǎng)倒裝場(chǎng)1 11 1巖場(chǎng)巖場(chǎng)2 21 1巖石漏巖石漏1 1倒裝場(chǎng)倒裝場(chǎng)1 1 各個(gè)路線上的聯(lián)合派車的卡車數(shù)為各個(gè)路線上的聯(lián)合派車的卡車數(shù)為11， 各個(gè)路線上的聯(lián)合派車的卡車數(shù)為各個(gè)路線上的聯(lián)合派車的卡車數(shù)為11，方案為：，方案為： 第第1輛：從鏟位輛：從鏟位1到倒裝場(chǎng)到倒裝場(chǎng)、巖石漏，鏟位、巖石漏，鏟位1到倒裝到倒裝場(chǎng)場(chǎng)運(yùn)運(yùn)5車，到巖石漏運(yùn)車，到巖石漏運(yùn)36車。車。 第第2輛：從鏟位輛：從鏟位2到倒裝場(chǎng)到倒裝場(chǎng)、巖石漏，鏟位、巖石漏，鏟位2到倒裝到倒裝場(chǎng)場(chǎng)運(yùn)運(yùn)2車，到巖石漏運(yùn)車，到巖石漏運(yùn)2