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