新參考答案

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

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

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

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

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

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

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

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

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

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