1、B.露天礦生產的車輛安排問題 摘要： 本文通過對原有的對多目標規劃模型進行線性和加權，使得多目標的規劃問題轉化為單目標非線性規劃問題，另外在選定7個鏟點的時候，通過對于數據的處理和論證，預先選定了5個鏟點，而在剩下的5個鏟點中搜索最優的2個鏟點，大大簡化了運算量。而且搜索出的10組數據是很離散化的，涵蓋了各種不同的情況，說明我們的搜索算法是可行的，是可以搜索出最優解的。而且由于采用線性加權和算法，所以能比較好的反映出各個目標函數的重要程度。另外，我們對于礦石的品位精度對于總運量和卡車數的影響進行了研究，得出的結果雖然比問題一的最優結果在運輸成本上差很多，但是對于對礦石的品位精度有較高要求的時候

2、（比如礦石的價格比較高），這種算法還是給出了最優解的。 通過在計算機上運行 程序，分別得到了問題一，二的最優解。 問題一所選用的鏟點為1，2，3，4，8，9，10，共用了7輛鏟車，13輛卡車，總運量為87964.8噸公里。 問題二所選用的鏟點為1，2，3，4，8，9，10，共用了7輛鏟車，20輛卡車，總產量為103488噸，其中巖石產量為49280噸，總運量為148771.7噸公里。 在得出最優解的同時，我們還大致排出了卡車的調度計劃。 問題的提出： 鋼鐵工業是國家工業的基礎之一，鐵礦是鋼鐵工業的主要原料基地。許多現代化鐵礦是露天開采的，它的生產主要是由電動鏟車（以下簡稱電鏟）裝車、電動輪自卸

3、卡車（以下簡稱卡車）運輸來完成。提高這些大型設備的利用率是增加露天礦經濟效益的首要任務。 露天礦里有若干個爆破生成的石料堆，每堆稱為一個鏟位，每個鏟位已預先根據鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多能安置一臺電鏟，電鏟的平均裝車時間為5分鐘。 卸貨地點（以下簡稱卸點）有卸礦石的礦石漏、2個鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏、巖場等，每個卸點都有各自的產量要求。從保護國家資源的角度及礦山的經濟效益考慮，應該盡量把礦石按礦石卸點需要的鐵含量（假設要求都為29.5%

4、 1%，稱為品位限制）搭配起來送到卸點，搭配的量在一個班次（8小時）內滿足品位限制即可。從長遠看，卸點可以移動，但一個班次內不變。卡車的平均卸車時間為3分鐘。 所用卡車載重量為154噸，平均時速28 。卡車的耗油量很大，每個班次每臺車消耗近1噸柴油。發動機點火時需要消耗相當多的電瓶能量，故一個班次中只在開始工作時點火一次。卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應發生卡車等待的情況。電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務。卡車每次都是滿載運輸。 每個鏟位到每個卸點的道路都是專用的寬60 的雙向車道，不會出現堵車現象，每段道路的里程都是已知的。 一個班次的生產計劃應該包含以

5、下內容：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次（因為隨機因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，只求出各條路線上的卡車數及安排即可）。一個合格的計劃要在卡車不等待條件下滿足產量和質量（品位）要求，而一個好的計劃還應該考慮下面兩條原則之一： 1.總運量（噸公里）最小，同時出動最少的卡車，從而運輸成本最小； 2.利用現有車輛運輸，獲得最大的產量（巖石產量優先；在產量相同的情況下，取總運量最小的解）。 請你就兩條原則分別建立數學模型，并給出一個班次生產計劃的快速算法。針對下面的實例，給出具體的生產計劃、相應的總運量及巖石和礦石產量。 某露天礦有鏟位

6、10個，卸點5個，現有鏟車7臺，卡車20輛。各卸點一個班次的產量要求：礦石漏1.2萬噸、倒裝場1.3萬噸、倒裝場1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。 各鏟位和各卸點之間的距離（公里）如下表：   鏟位1 鏟位2 鏟位3 鏟位4 鏟位5 鏟位6 鏟位7 鏟位8 鏟位9 鏟位10 礦石漏 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 倒裝場 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 巖場 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46

7、1.06 0.57 巖石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 倒裝場 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50 各鏟位礦石、巖石數量(萬噸)和礦石的平均鐵含量如下表：   鏟位1 鏟位2 鏟位3 鏟位4 鏟位5 鏟位6 鏟位7 鏟位8 鏟位9 鏟位10 礦石量 095 105 100 105 110 125 105 130 135 125 巖石量 125 110 135 105 115 135 105 115 135 125 鐵含量 30% 28% 29% 32

8、% 31% 33% 32% 31% 33% 31% 模型的假設： 1  因為每個鏟位到每個卸點的道路都是專用的寬60 的雙向車道，所以不會出現堵車現象。 2  卡車每次都是滿載運輸的。 3    因為產量限制的數量級是 (噸)，而卡車滿載的載重量為154噸，所以在運輸結果中如果誤差在10噸以內，我們認為是沒有誤差的。 4    在一個班次內的鏟車固定在鏟位，而且不進行移動。 5    因為隨機因素影響，裝卸時間與運輸時間都不精確，所以我們在安排車次的時候忽略時間的影響。 本文所用的變量

9、和符號： 點 巖場點 巖石漏點 礦石漏點 倒裝場1點 倒裝場210個鏟點分別用1，2，3.10編號每個鏟點的巖石量為 ，其中 每個鏟點的礦石量為 ，其中 每個鏟點的含鐵量為 ，其中 用 表示 點到鏟點 的距離，其中 比如：用 表示 點到鏟點1的距離， 表示 點到鏟點2的距離.以此類推。用 表示鏟點 到 點卡車所跑的次數，其中 比如：用 表示卡車從鏟點1到 點卡車所跑的次數， 表示卡車從鏟點2到 點所跑的次數.以此類推。用 表示 所形成的矩陣。用 表示在一個班次內卡車從鏟點運到卸點的巖石或礦石的總質量，其中 ， ，比如： 表示在一個班次內卡車從鏟點1運到卸點 的巖石的總質量， 表示在一個班次內卡

10、車從鏟點1運到卸點 的礦石的總質量表示礦石卸點的實際品位，其中 表示在一個班次內所有汽車的總路程表示卸點的在一個班次內的實際產量，其中 表示卸點的在一個班次內的計劃產量，其中 表示在理論上一個班次內所用卡車的總數表示鏟車的臺數表示第 輛汽車的工作時間。 問題的分析： 因為電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務，而且一個班次的工作時間是8個小時。電鏟為卡車裝車的時間為5分鐘，所以一個鏟點在8小時內不間斷的裝車，只能裝 （車次）。卡車在卸點卸車時間為3分鐘，所以一個卸點在8小時內不間斷的接收卡車的卸車，只能接受 （車次）。 一個班次總運量（噸公里）的定義為總運量的定義應該是運量與路程的乘積，

11、也就是 ， 。下面針對總運量的定義給出一個結論，并給予證明：結論：汽車在一個班次內的總運量應該近似的等于每輛汽車的滿載量與總路程的1/2的乘積。 證明： ， 其中 ， ， 而一個班次內所有汽車的總路程 等于 每臺車轉換鏟點的路程， ， ，實際上這段路程全部加起來不會超過10，對于我們的總路程是不會產生太大影響的，而且車在轉換鏟點的時候是空載，所以這部分實際上是沒有運量的。所以 證明完畢。 所以要求一個班次內的總運量最小的問題，就可以轉化為求一個班次內所有卡車的總路程最小的問題。 模型的建立： 根據題意,得出以下關于問題一的1多目標函數的最優化問題的原始數學模型:： ， 模型的轉化： 在問題分析

12、中我們已經給出證明 ， ，除此之外， 理論上所需要的卡車總數和在一個班次內卡車在每個鏟位和每個卸點之間所走的路程 ，以及卡車在每個鏟位和每個卸點之間所走的次數 有關。從時間的角度考慮，為了使車輛數最小，假定每輛車都工作了8小時，則這時的 ，其中 ， , 再由問題的分析，一個鏟點在8小時內不間斷的裝車，只能裝96車次。一個卸點在8小時內不間斷的接收卡車的卸車，只能接受160車次。也就是說， ， 這個約束條件可以轉化為以下兩個約束條件： ， ； ， 。各礦石卸點的實際品位 ， ， 這個條件可以轉化為矩陣 的非零列向量的個數小于等于7，又因為矩陣 中的每一個元素 （車次）都是大于等于0的，所以該條件

13、可以轉化為2矩陣 的列元素的和大于0的列數小于等于7。這樣模型的目標函數和約束條件都可以化成以 為自變量的函數。則原始模型可以轉化為以下形式：， 然后，再通過3線性加權和方法，對于目標函數 分別引入權系數 ，把這個多目標函數的最優化問題就轉化成了關于單變量 的單目標函數 的最優化問題。 模型的求解及計算機實現： 鏟位和卸點位置的二位示意圖如下： 因為題目并沒有要求我們考慮鏟車的成本問題，所以在計算時我們先按照7臺鏟車全部被使用的時候開始計算的。 1 鏟車位置的確定： 因為一共有10個礦點，鏟車只有7臺，顯然做不到每個鏟位都安排一輛鏟車。所以鏟車位置的確定就是很重要的，他們的確定很可能會影響最終

14、的結果。從最簡單的角度來看，在運輸的時候，鏟位如果距離卸點的距離越近那么所需的成本則最小。在選取鏟位的時候，我們應該優先考慮那些距離卸點較近的鏟位。這樣我們就把距離5個卸點最近的點先確定，這樣，共有1，2，9，10四個點。（其中鏟位10距離巖場和倒裝場2的距離在10個鏟位中都是最小的）。另外，運礦石的時候，因為品位限制鐵的最高含量為30.5%,而大部分鏟位的鐵含量基本都比30.5%大，只有1，2，3鏟位的鐵礦石的鐵含量是低于這30.5%的，所以為了達到鐵礦石的品位要求，應該盡可能的把這3個鏟位都考慮進去。而且3鏟位距離卸點的距離也比較近，所以我們認為有必要把這3這個鏟位作為首選進入7個鏟位之中

15、。 這樣我們就在7個鏟位中率先確定了1，2，3，9，10這五個點，剩下的兩個鏟位由于距離各個卸點的距離都比較遠，在選定的時候無法確定，所以應該在剩下的4，5，6，7，8這五個點中每次選擇2個點，計算其總運量和需要的總車數，這樣共會得到10組不同的數據，在進行比較以后，再選取最優的一組作為我們最終確定的鏟位方案。 2權系數的確定：4權系數由試探和修正確定，我們發現當 的時候 ，所得到的結果最優，而且滿足題里所給出的各種條件。當 取別的權值的時候，要么理論上的卡車數大于20或者品位不滿足 的要求，要不就是達不到最優解。 對權的說明：兩個權值 反映了對萬噸公里數和卡車數的對總成本重要程度。也就是說我

16、們在搜索的時候，卡車數是優先于萬噸公里數的。當 的時候 ， 和 的比值約為1：10較符合實際。從實際的角度來講，讓較少的卡車多跑一些路程要比讓較多的卡車少跑一些路程所需要的成本要少。 3搜索算法初值的確定：通過計算機模擬試驗得出一個符合要求的初始值。 4鏟位的搜索算法：每個鏟位確定的時候，搜索每個鏟位的在滿足各個卸點的產量和品位的要求情況下，總運量最小的同時，總車數最小的方案。因為礦石的品位要求鐵含量最高為30.5%，所以為了滿足卸點的品位要求，從一個鏟位向卸點運輸顯然是無法滿足品位要求的。所以這就有必要從1，2，3這三個鏟位也向礦石卸點運輸，從而達到題目所要求的品位要求。在運礦石的時候，我們

17、應該盡可能的從鄰近的鏟位向卸點運輸，當達到一個品位所能允許的最大噸位的時候再靠1，2，3鏟位的礦石來補足。所以為了能夠找到最優解，我們盡可能的把滿足每個礦石卸點所有的分配方案都計算出來。最后我們用5 優化函數 搜索了10組方案。如表一所示：  表一：以總運量和卡車數為目標函數搜索得到的結果       鏟點總路程（千米）理論上的車輛數對理論上的車輛數取整倒裝場1的品位（%）倒裝場2的品位（%）礦石漏的品位（%）鏟車數目4，51240.613.1381429.61230.25930.15474，61227.413.0631429.64730.30630.1

18、4364，71227.413.0631429.64730.30630.14364，81142.412.6661329.60030.39030.35175，61268.313.2621429.46430.11830.16565，71249.613.1451429.53630.19130.15475，81182.312.8621329.46430.25930.34676，71248.913.1421429.57130.32130.15466，81207.812.9751329.41230.40030.35177，81159.712.7441329.53330.42930.3517  在選

19、定最優解的時候，我們發現，如果總路程和總車數稍微放大一點的話，那么就會剩下一輛鏟車，因為題目并沒有給我們鏟車的成本數值，所以鏟車的數目并不是選取最優解的決定因素。而且從實際的角度考慮，車的耗油量很大，每個班次每臺車消耗近1噸柴油。發動機點火時需要消耗相當多的電瓶能量，故一個班次中只在開始工作時點火一次，所以卡車運行的成本應該比鏟車運行的成本要高，所以我們應該選擇總運量和總車數最小的解作為最優解。對于程序搜索結果的分析，通過表一我們可以看到，該算法是比較好的，因為它盡可能的搜索到了各種情況的點。也就是說，它所選取的點是比較離散的，能夠更好的描繪對于各個點的選取在總成本中的重要性。最終我們選擇了4

20、，8點作為問題的最優點，也就是說7個鏟點我們選擇了1，2，3，4，8，9，10這7個鏟點，選擇這7個鏟點得到總路程和理論上所需要的車次數都是最小的。至于實際能不能夠達到，既需要我們對這個方案進行調度。因為隨機因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，我們只求出了一個大概的時間分配方案。如表二所示：                            表二：問題一最優解的卡車調度計劃   工作時間 車輛號123456781B12 B

21、1D23E2D24E2D25B36C37D48C8 C39C8B310A911A9A1012E10A1013 E10 C10  每條線路的運輸車次所構成的矩陣 如表三：表三：問題一每個鏟點到礦點的運輸車次 鏟點卸點鏟點1鏟點2鏟點3鏟點4鏟點8鏟點9鏟點10A 巖場0 00007015B巖石漏810420000C礦石漏0025038014D倒裝場1051034000E倒裝場2017000067  總運量為87964.8噸公里，共需要13臺卡車，7臺鏟車。 在計算機進行搜索的時候，我們發現如果把卸點礦石的品位也作為一個目標函數進行加權的話，也可以得到一系列的最優解。但是這組最

22、優解除了礦石品位比表一中的數據更接近于29.5%,但是其余的數值（比如：總運量，卡車數）都遠遠大于表一中的數據。也就是說，為了使品位的精度控制更高，那么就要付出更多的運輸成本。這與實際的吻合是相當好的。但是對于本題的要求，對于品位精度的控制沒有那么嚴格的情況下，無疑表一中的數據是最好的。但是如果為了得到品位精度較高的礦石（礦石比較貴重，比一般的運輸成本要高）的時候，這種算法就是比較有效的。問題二的數學模型： 針對問題二的數學模型和問題一的數學模型基本一樣，只是目標函數有所改變。約束條件其中的卡車數由原來的小于等于20變成等于20。鏟車數由原來的小于等于7變成等于7（為了達到最大產量）。所以問題

23、二的數學模型為：    經過類似于模型一的變換，也可以將模型二轉化為目標函數和約束條件都以 為自變量的函數。然后，再通過線性加權和的方法，對于目標函數 分別引入權系數 ，把這個多目標函數的最優化問題就轉化成了關于單變量 的單目標函數 的最優化問題。在經過試探和修正，我們發現 的時候，能得到巖石產量的極大值的同時，總產量也盡可能的大，這樣的結果是比較好的。其中巖石產量的極大值= （噸）由于模型一中我們的選擇鏟點的方案求出的結果很好，給予一中所論述的理由，我們在這里依然按照模型一中的選點規則進行選點。也就是說先確定1，2，3，9，10四個礦點，然后再對剩下的5個礦點每次取出兩個

24、礦點進行搜索，得到以下的表四：  表四：以總產量，巖石總產量和總運量為目標函數搜索得到的結果     選取的鏟點 巖石和礦石的總產量（噸） 巖石的總產量（噸） 總路程（千米） 4，5 101486 49280 2018.5 4，6 98714 49280 2083.4 4，7 101948 49280 2013.0 4，8 103488 49280 1932.1 5，6 97804 49280 2109.0 5，7 103200 49280 2045.0 5，8 98319 49280 1978.2 6，7 100640 49280 2096.5 6，8 1022

25、00 49280 2040.2 7，8 102102 49280 2000.4   通過該表我們很容易得就找到了最優的鏟點，依然是4，8，這兩個鏟點無論從總產量還是從總運量的角度來看都是最優的。所以問題二所選用的鏟點為1，2，3，4，8，9，10，共用了7輛鏟車，20輛卡車，總產量為103488噸，其中巖石產量為49280噸，總運量為148771.7噸公里。 以下是我們的調度大致計劃，如表五所示： 表五：問題二最優解的卡車調度計劃 工作時間 車輛號123456781B12D1E23B1A104A105B2C86B2C87D28D2C39C310C3D311D3D312E3D413E3

26、D414 D415D4 E1016 A8E817 E818E8C9A919 A920 A9            每條線路的運輸次數所構成的矩陣 如表六所示：表六：問題一每個鏟點到礦點的運輸車次   鏟點卸點鏟點1鏟點2鏟點3鏟點4鏟點8鏟點9鏟點10A 巖場0 000118861B巖石漏73283128000C礦石漏003903180D倒裝場12360968000E倒裝場20817054035  模型評估： 優點：我們所建立的模型通過對原有的對多目標規劃模型進行線性和加權，使得多目標的規劃問題轉化為單目標非線性規

27、劃問題，另外在選定7個鏟點的時候，通過對于數據的處理和論證，預先選定了5個鏟點，而在剩下的5個鏟點中搜索最優的2個鏟點，大大簡化了運算量。而且搜索出的10組數據是很離散化的，涵蓋了各種不同的情況，說明我們的搜索算法是可行的，是可以搜索出最優解的。而且由于采用線性加權和算法，所以能比較好的反映出各個目標函數的重要程度。另外，我們對于礦石的品位精度對于總運量和卡車數的影響進行了研究，得出的結果雖然比問題一的最優結果在運輸成本上差很多，但是對于對礦石的品位精度有較高要求的時候（比如礦石的價格比較高），這種算法還是給出了最優解的。 缺點：由于采用線性加權和的算法，導致合理的權值的確定是很麻煩的，需要經

28、過多次的調試才能最終確定最后的權值。而且模型在計算中作了一些舍入和取整，不可避免的產生了一些誤差，但是這些誤差的是可以容忍的。 參考書目： 1 邢繼祥 張春蕊等，最優控制應用基礎，北京，科學出版社，2003年8月 2 北京大學數學系幾何與代數教研室代數小組，高等代數，北京，高等教育出版社，1988年3月 3 胡達，多目標規劃有效性理論，上海，上海科學技術出版社，1994年12月 4 郭晶， 輔助優化計算與設計，北京，電子工業出版社，2003年1月 5 蕭樹鐵，數學實驗，北京，高等教育出版社，1997年7月 附錄： 源程序： %目標與約束函數的實現程序 function f,g=yunkuang

29、(x)%x為自變量，f為優化目標，g為約束條件Dis=5.265.194.214.002.952.742.461.900.641.27; 1.900.991.901.131.272.251.482.043.093.51; 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 ;  quan=2000,1000;hl=0.951.051.001.051.101.251.051.301.351.

30、25; 1.251.101.351.051.151.351.051.151.351.25; 30 28 29 32 31 33 32 31 33 31;qudian=1 2 3 4 8 9 10;d=Dis(3 4 1 2 5,qudian);pin=hl(3,qudian);%f1為總路程函數f1=0;for i=1:5 for j=1:7 f1=x(i-1)*7+j)*d(i,j)+f1;endendtimes=0;for i=1:35 times=times+x(i);end%truck為卡車輛數truck=(f1*2/28+times*8/60)/8;for i=3:5 for j=1:7 pei(i-3)*7+j)=pin(j)*x(i-1)*7+j); endendfor i=1:3 peibi(i)=0; timestot(i)=0;endfor i=1:3 for j=1:7 timestot(i)=x(i+1)*7+j)+timestot(i);end