基于線性規(guī)劃的煤炭運輸問題研究

施 文

(上海市第二中學 上海 200031)

一、線性規(guī)劃基本原理簡述

求解最優(yōu)化問題一般用線性規(guī)劃的方法。[1-3]最優(yōu)化問題是指：在一組約束條件的限制下，求目標函數(shù)的最大值或者最小值。當目標函數(shù)和給定的約束條件是全部是線性函數(shù)時，這個最優(yōu)化問題即可轉化為線性規(guī)劃問題；當目標函數(shù)和給定的約束條件中只要有一個不是線性的，則不能看作線性規(guī)劃問題。目標函數(shù)以及約束條件通常是在實際問題中根據(jù)人為理解為解決問題而建立的。[4-7]線性規(guī)劃一般的求解步驟在高中階段學校已經學習，一般步驟是這樣的：列出目標函數(shù)以及約束條件；在二維直角坐標系畫出約束條件表示的可行域；在可行域內找到目標函數(shù)的最優(yōu)解。[8]由于很多實際問題的約束條件較為復雜，并不能直觀地在二維直角坐標系中直接畫出可行域，本文采用了計算機處理的方式，解決了這一難點。

二、研究問題

現(xiàn)有甲乙丙丁四個鋼鐵廠，鋼鐵廠所需的煤炭由A、B、C三個煤場供應。四個鋼鐵廠每天必須得到保證的供應量為30、70、10、10千噸。但由于煤炭資源緊缺，三個煤場煤炭最多只能分別供應50、60、50千噸煤炭。三個煤場的煤通過統(tǒng)一的煤炭運輸管理站被運往四個鋼鐵廠。由于地理位置的差別，現(xiàn)在各煤場向煤炭輸送管理站所需支付的費用不同。根據(jù)規(guī)定，現(xiàn)C煤場發(fā)往丁鋼鐵廠的煤由于政策原因，暫時不用支付管理費用，其他管理費用都是450元每千噸。根據(jù)規(guī)定，各個鋼鐵廠按照統(tǒng)一標準900元每千噸收費。此外，四個鋼鐵廠都向煤炭運輸管理站申請了額外用量，分別為每天50、70、20、40千噸。那么請問煤炭輸送站應該如何分配供煤量，才能獲利最多。各煤炭場運輸煤炭到各鋼鐵廠的單位價格見表1，各個鋼鐵廠需求量及額外用量見表2，各個煤炭場輸出量見表3。

表1 各煤炭場運輸煤炭到各鋼鐵廠的單位價格

表2 各個鋼鐵廠需求量及額外用量

表3 各個煤炭場輸出量

三、問題分析

煤炭運輸管理站分配三個煤場向四個鋼鐵廠運煤的方案是為了獲利最多。而從給出的數(shù)據(jù)看，A、B、C三個煤炭廠的總供煤量為160千噸，不會超過四個鋼鐵廠的基本煤炭用量與額外煤炭用量總和300千噸，因而可以全部輸出并獲利。于是煤炭輸送管理中心的收入是900*(50+60+50)=144000(元)。同樣，其他費用也是固定的，為450*(50+60+50)=72000(元)。要使利潤最大，則需使管理費最少。

四、建立模型

1.確定決策變量：

記x11為A輸送至甲的煤炭量，x21為A輸送至乙的煤炭量，x31為A輸送至丙的煤炭量，x41為A輸送至丁的煤炭量；x12記為B輸送至甲的煤炭量，x22為B輸送至乙的煤炭量，x32為B輸送至丙的煤炭量，x42為B輸送至丁的煤炭量；記x13為C輸送至甲的煤炭量，x23為C輸送至乙的煤炭量，x33為C輸送至丙的煤炭量，x43為C輸送至丁的煤炭量。

2.確定約束條件：

決策變量均有范圍限制，因為所有鋼鐵廠必須正常工作，所有煤炭輸出量不能低于需求量，且受限于上限。而且鋼鐵廠必須用完煤炭場產能。煤炭場的供煤量可表示為以下三個式子。

各個鋼鐵廠需求量可表示為以下四個式子。

3.確定目標函數(shù)為：

綜合如上分析得到規(guī)劃模型為：

這是一個線性規(guī)劃模型，可以利用Python代碼求解，代碼如下所示。

結果方案為：A煤炭場向乙鋼鐵廠供50千噸。B煤炭場向乙鋼鐵廠供20千噸，向丁鋼鐵廠供40千噸。C煤炭場向甲鋼鐵廠供40千噸，向丙鋼鐵廠供10千噸。煤炭輸送管理費為24400元。最后計算得出利潤是，總收入減去其他管理費用再減去輸送管理費用，共47600元。

五、模型擴展

如果A、B、C三個煤場的每天最大供煤量擴大一倍，則總供煤量為320千噸，大于需求量300千噸。那么這種情況下煤炭不能全部被賣出。那么煤炭輸送管理站應該如何設計分配方案，達到利益最大化呢？先計算供應每千噸的凈利潤，從收入中減去管理費。得到新的純利潤表。

?

決策變量仍為xij表示煤場j每天向i鋼鐵廠的供煤量。由于C與丁之間沒有運輸渠道，所以x43=0。約束條件：由于煤不能全部賣出，應將小于號改為小于等于號，需求量限制不變。約束條件的式子如下所示：

目標函數(shù)如下：

所以模型可以表示如下形式：

利用python代碼求解：

得到方案為：A向乙鋼鐵廠供煤100千噸，B向甲、乙、丁鋼鐵廠分別供30、40、50千噸，C向甲、丙鋼鐵廠分別供50、30千噸，總利潤為88700元。

六、總結

模型考慮的是，將某種物資從若干物資運往需求點，在供應量約束條件下，使總費用最小或總利潤最大。這一類問題一般稱為運輸問題，是線性規(guī)劃應用最廣泛的領域之一。[9]在標準的運輸問題中，供需量一般是平衡的，即供應點的總供應量等于需求點的總需求量。[10]模型擴展中供需量不平衡，但這并不會引起本質區(qū)別，一樣可以用線性規(guī)劃模型求解。