施 文

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

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

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

二、研究問(wèn)題

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

表1 各煤炭場(chǎng)運(yùn)輸煤炭到各鋼鐵廠的單位價(jià)格

表2 各個(gè)鋼鐵廠需求量及額外用量

表3 各個(gè)煤炭場(chǎng)輸出量

三、問(wèn)題分析

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

四、建立模型

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.確定約束條件：

決策變量均有范圍限制，因?yàn)樗袖撹F廠必須正常工作，所有煤炭輸出量不能低于需求量，且受限于上限。而且鋼鐵廠必須用完煤炭場(chǎng)產(chǎn)能。煤炭場(chǎng)的供煤量可表示為以下三個(gè)式子。

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

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

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

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

結(jié)果方案為：A煤炭場(chǎng)向乙鋼鐵廠供50千噸。B煤炭場(chǎng)向乙鋼鐵廠供20千噸，向丁鋼鐵廠供40千噸。C煤炭場(chǎng)向甲鋼鐵廠供40千噸，向丙鋼鐵廠供10千噸。煤炭輸送管理費(fèi)為24400元。最后計(jì)算得出利潤(rùn)是，總收入減去其他管理費(fèi)用再減去輸送管理費(fèi)用，共47600元。

五、模型擴(kuò)展

如果A、B、C三個(gè)煤場(chǎng)的每天最大供煤量擴(kuò)大一倍，則總供煤量為320千噸，大于需求量300千噸。那么這種情況下煤炭不能全部被賣(mài)出。那么煤炭輸送管理站應(yīng)該如何設(shè)計(jì)分配方案，達(dá)到利益最大化呢？先計(jì)算供應(yīng)每千噸的凈利潤(rùn)，從收入中減去管理費(fèi)。得到新的純利潤(rùn)表。

?

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

目標(biāo)函數(shù)如下：

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

利用python代碼求解：

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

六、總結(jié)

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