B題參考答案B題參考答案第第#頁,共7頁下面用巖石產量達到上限為約束，礦石產量最大為目標函數求解最佳物流。（2）計算整數線性規劃，以得到最大礦石產量及最佳物流由于這個整數規劃的復雜性，所以必須考慮快速算法。先求解去掉整數約束的相應的線性規劃，目標值為341.2807車次。由于求的是整數線性規劃，礦石的最大產量（車次）必然應為一整數。因為線性規劃的最優解是整數規劃最優解的上界，逐個減一地依次求“礦石產量等于比342小的整數”加到約束條件中，目標為總運量最小的整數規劃。第一個出現可行解的規劃的最優解必為原整數規劃的最優解，且總運量最小。由于等式約束造成可行域的減小，運算量已大幅度減少。把礦石卸點的最大產量為341車次作為約束條件加入到整數線性規劃中，沒有可行解。把礦石卸點的最大產量為340車次作為約束條件加入到整數線性規劃中，得出的結果如下，即為所求。最佳物流相對應的各個路線上的最佳運輸車次為：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏382418倒裝場I16542268巖場127474巖石漏80283220倒裝場II1446022第二層規劃仍用啟發式算法：用實際流量，計算卡車在各個路線上一個班次最多可以運行的次數：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏15161819232426294436倒裝場I29392937362733282221巖場14151517212026263745巖石漏44303530242518201614倒裝場II18192022272442313647根據最佳物流計算各路線上需要的卡車數：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏2.11110.82760.4091倒裝場I0.55171.38460.75861.8378巖場0.461521.6444巖石漏1.81820.93330.91430.6667倒裝場II0.73680.21.93550.4681所有路線所需卡車數（實數）的和，為19.66。各路線上需要的整數卡車數為9（這些卡車在一個班次內一直在固定路線上運輸）：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏2倒裝場I11巖場21巖石漏1倒裝場II1各個路線上的聯合派車的卡車數為11，方案為：第1輛：從鏟位1到倒裝場I、巖石漏，鏟位1到倒裝場I運5車，到巖石漏運36車。第2輛：從鏟位2到倒裝場I、巖石漏，鏟位2到倒裝場I運2車，到巖石漏運28車。第3輛：從鏟位3到倒裝場I、巖石漏，鏟位3到倒裝場I運2車，到巖石漏運32車。第4輛:從鏟位4到倒裝場I、巖石漏，鏟位4到倒裝場I運12車，到巖石漏運20車。第5輛：從鏟位1、2、3到倒裝場I,鏟位1到倒裝場I運11車，鏟位2到倒裝場I運13車，鏟位3到倒裝場I運8車。第6輛：從鏟位3、4到倒裝場I和鏟位3到礦石漏，鏟位3到倒裝場I運12車，鏟位4到倒裝場I運19車，鏟位3到礦石漏運1車。第7輛：從鏟位2、3、8到倒裝場H,鏟位2到倒裝場n運14車，鏟位3到倒裝場H運4車，鏟位8到倒裝場n運1車。第8輛：從鏟位8、io到倒裝場n,鏟位8到倒裝場n運28車，鏟位io到倒裝場n運4車。第9輛：從鏟位io到巖場、倒裝場n,鏟位io到巖場運27車，鏟位io到倒裝場n運18車。第10輛：從鏟位8、io到巖場和從鏟位8到礦石漏，鏟位8到巖場運i2車，鏟位io到巖場運2車，鏟位8到礦石漏運i4車。第11輛：從鏟位3、8、9到礦石漏，鏟位3到礦石漏運i車，鏟位8到礦石漏運io車，鏟位9到礦石漏運i8車。鏟位1、2、3、4、8、9、10處各放置一臺電鏟。一共使用20輛卡車；總運量為142385.3噸公里；巖石產量為49280噸；礦石產量為52360噸。附注：本題主要難點.各路線上安排的車輛數應有一個最大值限制。如果在一個路線上的車輛過多就會出現題意不允許發生的等待情況。如果這一點沒想到,后面的結果很難正確。.從鏟位i到卸點j的流量為i54噸的整數倍。這題的核心問題之一是如何用近似算法求解NPC問題。整數規劃的現有解法不是快速算法,無法保證在任何數據下都能在短時間內算完。對這題的數據而言,從競賽的時間和軟件上來說最優解是求不出來的,必須想辦法巧妙地使用規劃軟件減少運行整數規劃耗費的時間。比如：求解相對應的線性規劃,最優解取整,如果還可行作為整數規劃的近優解,等等。.怎樣處理在io個鏟位安排7臺電鏟的問題。4．關于派車算法中的一些問題。派車問題本質為組合優化問題,學生需要想辦法快速得到最優解或近優解。可能還要考慮卡車的初始位置和終止位置,特別是兩種聯合派車時。另外由于裝車造成的延時可能造成后面的