新參考答案

1、B題參考答案第1頁，共7頁20032003高教社杯全國大學(xué)生數(shù)學(xué)建模競賽高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題參考答案題參考答案注意：以下答案是命題人給出的，僅供參考。各評閱組應(yīng)根據(jù)對題目的理注意：以下答案是命題人給出的，僅供參考。各評閱組應(yīng)根據(jù)對題目的理解及學(xué)生的解答，自主地進(jìn)行評閱。解及學(xué)生的解答，自主地進(jìn)行評閱。問題分析：問題分析：本題目與典型的運(yùn)輸問題明顯有以下不同：1運(yùn)輸?shù)V石與巖石兩種物資；2產(chǎn)量大于銷量的不平衡運(yùn)輸；3在品位約束

2、下礦石要搭配運(yùn)輸；4產(chǎn)地、銷地均有單位時(shí)間的流量限制；5運(yùn)輸車輛每次都是滿載，154噸車次；6鏟位數(shù)多于鏟車數(shù)意味著最優(yōu)的選擇不多于7個(gè)產(chǎn)地；7最后求出各條路線上的派出車輛數(shù)及安排。運(yùn)輸問題對應(yīng)著線性規(guī)劃，以上第1、2、3、4條可通過變量設(shè)計(jì)、調(diào)整約束條件實(shí)現(xiàn)；第5條使其變?yōu)檎麛?shù)線性規(guī)劃；第6條用線性模型實(shí)現(xiàn)的一種辦法，是從個(gè)120710?C整數(shù)規(guī)劃中取最優(yōu)的即得到最佳物流；對第7條由最佳物流算出各條路線上的最少派出車輛數(shù)（整數(shù)），再給

3、出具體安排即完成全部計(jì)算。對于這個(gè)實(shí)際問題，要求快速算法，計(jì)算含50個(gè)變量的整數(shù)規(guī)劃比較困難。另外，這是一個(gè)二層規(guī)劃，第二層是組合優(yōu)化，如果求最優(yōu)解計(jì)算量較大，現(xiàn)成的各種算法都無能為力。于是問題變?yōu)檎乙粋€(gè)尋求近優(yōu)解的近似解法，例如可用啟發(fā)式方法求解。調(diào)用120次整數(shù)規(guī)劃可用三種方法避免：（1）先不考慮電鏟數(shù)量約束運(yùn)行整數(shù)線性規(guī)劃，再對解中運(yùn)量最少的幾個(gè)鏟位進(jìn)行篩選；（2）在整數(shù)線性規(guī)劃的鏟車約束中調(diào)用函數(shù)來實(shí)現(xiàn)；（3）增加10個(gè)0－1變

4、量來標(biāo)志各個(gè)鏟位是否有產(chǎn)量。sign這是一個(gè)多目標(biāo)規(guī)劃，第一問的目標(biāo)有兩層：第一層是總運(yùn)量（噸公里）最小，第二層是出動卡車數(shù)最少，從而實(shí)現(xiàn)運(yùn)輸成本最小。第二問的目標(biāo)有：巖石產(chǎn)量最大；礦石產(chǎn)量最大；運(yùn)量最小，三者的重要性應(yīng)按此序。合理的假設(shè)主要有：1.卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；2.在鏟位或卸點(diǎn)處因兩條路線（及以上）造成的沖突時(shí)，只要平均時(shí)間能完成任務(wù)即可，不進(jìn)行排時(shí)討論；3.空載與重載的速度都是28kmh，耗油相差

5、卻很大，因此總運(yùn)量只考慮重載運(yùn)量；4.卡車可提前退出系統(tǒng)。符號符號：xij~從i號鏟位到j(luò)號卸點(diǎn)的石料運(yùn)量單位噸；cij~從i號鏟位到j(luò)號卸點(diǎn)的距離公里；Tij~從i號鏟位到j(luò)號卸點(diǎn)路線上運(yùn)行一個(gè)周期平均所需時(shí)間分；Aij~從i號鏟位到j(luò)號卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)輛；Bij~從i號鏟位到j(luò)號卸點(diǎn)路線上一輛車最多可以運(yùn)行的次數(shù)次；pi~i號鏟位的礦石鐵含量。%p=(30282932313332313331)qj~j號卸點(diǎn)任務(wù)需求噸B題參

6、考答案第3頁，共7頁（6）5210)5.28(0)5.30(101101??????????????????jpxpxiiijiiij.（7）51101154154?????????????jixxijij（8）7101???iif（9）20154???jiijijBx二對最佳物流的結(jié)果進(jìn)行派車—第二層規(guī)劃這是組合優(yōu)化中的一維背包模型，針對快速算法的要求，用啟發(fā)式方法求近優(yōu)解。先用最佳物流修正Bij確定卡車一個(gè)班次中在這條路線上實(shí)際最多

7、可以運(yùn)行的次數(shù)。然后在以目標(biāo)為出動總卡車數(shù)最少的各路線派車中，把各路線需要的卡車數(shù)分成整數(shù)部分和小數(shù)部分，進(jìn)而可以分配任務(wù)讓輛車)154(ijijijBxe???ije??ijijee???ije在i到j(luò)路線上，每輛往返運(yùn)輸Bij次。為了最后實(shí)現(xiàn)第二層規(guī)劃的目標(biāo)，只需聯(lián)合處理所有的時(shí)把這些小數(shù)組合成最少的整數(shù)卡車數(shù)。所需總卡車數(shù)的下界顯然是??ijijee?。如果某種派車方案恰好派出Y0輛車實(shí)現(xiàn)了所有的xij，則其即為第二層目標(biāo)意???

8、?????jiijeY0義下近優(yōu)解的最優(yōu)方案。但由于有聯(lián)合派車而總公里數(shù)不一定最小故不一定為全局意義下的最佳方案。出動卡車數(shù)最少，意味著出動的卡車?yán)寐室畲蟆Ｈ菀壮霈F(xiàn)的一輛卡車為兩個(gè)以上路線服務(wù)的聯(lián)合派車，可分為兩種情況：⑴有共同鏟位（或卸點(diǎn)）的聯(lián)合派車（V字形或更復(fù)雜）；⑵不同鏟位且不同卸點(diǎn)之間的聯(lián)合派車（Z字形或四邊形或更復(fù)雜）。派車方案的空載路線應(yīng)盡量安排在第一層規(guī)劃的最佳物流路線內(nèi)，即使有的超出也要保證超出的路程總和最小，這樣

9、才能實(shí)現(xiàn)重載路程最小且使卡車空載路程也最小。而情況⑴的路線不會超出第一層規(guī)劃的最佳物流路線。只有情況⑵才會有一部分不在第一層規(guī)劃的最佳物流路線內(nèi)。問題：各路線都是小數(shù)的需車數(shù)，如何組合使總卡車數(shù)最少且如果出現(xiàn)情況⑵時(shí)空載超出部分總和盡量小。如果存在情況⑴，則整體考慮情況⑴形路線需要的卡車數(shù)相加的和先確定和的整數(shù)部分的車數(shù)并對這些車分配任務(wù)（任務(wù)的形式為在哪條路線上運(yùn)幾趟，再在哪條路線上運(yùn)幾趟，等等）。之后已無情況⑴了，再對各個(gè)小數(shù)進(jìn)行組

10、合相加試探，在所有動用卡車數(shù)最少的情況中，選擇超出第一層最佳物流路線的總和最小的，即為最后派車方案，再對這些車分配任務(wù)。由于屬情況⑴的為多數(shù)，故后面的組合搜索比較簡單，常常只有一兩個(gè)任務(wù)屬情況⑵。根據(jù)最后派車方案，回代計(jì)算出各車輛在各路線的運(yùn)輸次數(shù)。由于整數(shù)部分已分配完運(yùn)輸次數(shù)小數(shù)乘以對應(yīng)路線上的Bij取整計(jì)算出小數(shù)部分對應(yīng)的具體運(yùn)輸次數(shù).進(jìn)一步計(jì)算出實(shí)際總運(yùn)量與礦石和巖石的產(chǎn)量。三、求解過程：（一）第一層規(guī)劃求解前面給出的整數(shù)規(guī)劃模型