淺談線性規(guī)劃方法的應(yīng)用

[摘要] 線性規(guī)劃是運籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學(xué)管理的一種數(shù)學(xué)方法，線性規(guī)劃是輔助企業(yè)“轉(zhuǎn)軌”、“變型”的十分有利的工具，它在幫助企業(yè)經(jīng)營決策、計劃優(yōu)化等方面具有重要的作用。

[關(guān)鍵詞] 線性規(guī)劃 方法 應(yīng)用

線性規(guī)劃是運籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學(xué)管理的一種數(shù)學(xué)方法，早在1939年蘇聯(lián)的康托洛維奇（H.B.Kahtopob ）和美國的希奇柯克（F.L.Hitchcock）等人就在生產(chǎn)組織管理和制定交通運輸方案方面首先研究和應(yīng)用線性規(guī)劃方法。1947年旦茨格等人提出了求解線性規(guī)劃問題的單純形方法，為線性規(guī)劃的理論與計算奠定了基礎(chǔ)，特別是電子計算機的出現(xiàn)和日益完善，更使規(guī)劃論得到迅速的發(fā)展，可用電子計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃（或非線性規(guī)劃）問題。從應(yīng)用范圍來看，小到一個班組的計劃安排，大至整個部門，以至國民經(jīng)濟計劃的最優(yōu)化方案分析，它都有用武之地，從解決技術(shù)問題的最優(yōu)化，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)以及決策分析部門它都可以發(fā)揮作用。線性規(guī)劃方法具有適應(yīng)性強，應(yīng)用面廣，計算技術(shù)比較簡便的特點。其基本思路是在滿足一定的約束條件下，使預(yù)定的目標達到最優(yōu)。它的研究內(nèi)容可歸納為兩個方面：一是系統(tǒng)的任務(wù)已定，如何合理籌劃，精細安排，用最少的資源(人力、物力和財力)去實現(xiàn)這個任務(wù)；二是資源的數(shù)量已定，如何合理利用、調(diào)配，使任務(wù)完成的最多。前者是求極小，后者是求極大。線性規(guī)劃是在滿足企業(yè)內(nèi)、外部的條件下，實現(xiàn)管理目標的極值(極小值和極大值)問題，就是要以盡量少的資源輸入來實現(xiàn)更多的社會需要的產(chǎn)品的產(chǎn)出。因此，線性規(guī)劃是輔助企業(yè)“轉(zhuǎn)軌”、“變型”的十分有利的工具，它在輔助企業(yè)經(jīng)營決策、計劃優(yōu)化等方面具有十分重要的作用。

一、線性規(guī)劃模型的結(jié)構(gòu)

企業(yè)是一個復(fù)雜的系統(tǒng)，要研究它必須將其抽象出來形成模型。如果將系統(tǒng)內(nèi)部因素的相互關(guān)系和它們活動的規(guī)律用數(shù)學(xué)的形式描述出來，就稱之為數(shù)學(xué)模型。線性規(guī)劃的模型決定于它的定義，線性規(guī)劃的定義是：求一組變量的值，在滿足一組約束條件下，求得目標函數(shù)的最優(yōu)解。

根據(jù)這個定義，就可以確定線性規(guī)劃模型的基本結(jié)構(gòu)。

1.變量:變量又叫未知數(shù)，它是實際系統(tǒng)的未知因素，也是決策系統(tǒng)中的可控因素，一般稱為決策變量，常引用英文字母加下標來表示，如Xl，X2，X3，Xm等。

2.目標函數(shù):將實際系統(tǒng)的目標，用數(shù)學(xué)形式表現(xiàn)出來，就稱為目標函數(shù)，線性規(guī)劃的目標函數(shù)是求系統(tǒng)目標的數(shù)值，即極大值（如產(chǎn)值極大值、利潤極大值）或者極小值（如成本極小值、費用極小值、損耗極小值等等）。

3.約束條件:約束條件是指實現(xiàn)系統(tǒng)目標的限制因素。它涉及到企業(yè)內(nèi)部條件和外部環(huán)境的各個方面，如原材料供應(yīng)、設(shè)備能力、計劃指標、產(chǎn)品質(zhì)量要求和市場銷售狀態(tài)等等，這些因素都對模型的變量起約束作用，故稱其為約束條件。約束條件的數(shù)學(xué)表示形式有三種，即≥、＝、≤。線性規(guī)劃的變量應(yīng)為正值，因為變量在實際問題中所代表的均為實物，所以不能為負。

在經(jīng)濟管理中，線性規(guī)劃使用較多的是下述幾個方面的問題：

(1)投資問題—確定有限投資額的最優(yōu)分配，使得收益最大或者見效最快。

(2)計劃安排問題—確定生產(chǎn)的品種和數(shù)量，使得產(chǎn)值或利潤最大，如資源配制問題。

(3)任務(wù)分配問題—分配不同的工作給各個對象(勞動力或機床)，使產(chǎn)量最多、效率最高，如生產(chǎn)安排問題。

(4)下料問題—如何下料，使得邊角料損失最小。

(5)運輸問題—在物資調(diào)運過程中，確定最經(jīng)濟的調(diào)運方案。

(6)庫存問題—如何確定最佳庫存量，做到即保證生產(chǎn)又節(jié)約資金等等。

二、應(yīng)用線性規(guī)劃建立數(shù)學(xué)模型的三步驟

1.明確問題，確定目標，列出約束條件。

2.收集資料，建立模型。

3.模型求解(最優(yōu)解)，進行優(yōu)化后分析。

其中，最困難的是建立模型，而建立模型的關(guān)鍵是明確問題、確定目標，在建立模型過程中花時間、花精力最大的是收集資料。

三、線性規(guī)劃的應(yīng)用實例

例1 某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件甲產(chǎn)品要耗鋼材2kg、煤2kg、產(chǎn)值為120元；每件乙產(chǎn)品要耗鋼材3kg，煤1kg，產(chǎn)值為100元。現(xiàn)鋼廠有鋼材600kg，煤400kg，試確定甲、乙兩種產(chǎn)品各生產(chǎn)多少件，才能使該廠的總產(chǎn)值最大？

解： 設(shè)甲、乙兩種產(chǎn)品的產(chǎn)量分別為X1、X2，則總產(chǎn)值是X1 、X2的函數(shù)

f(X1，X2)＝120X1＋100X2

資源的多少是約束條件：

由于鋼的限制，應(yīng)滿足2X1＋3X2≤600；由于煤的限制，應(yīng)滿足2X1＋X2≤400。

綜合上述表達式，得數(shù)學(xué)模型為

求最大值（目標函數(shù)）：f(X1，X2)＝120X1＋100X2

2X1＋3X2≤600

2X1＋X2≤400

X1≥0，X2≥0

Xl，X2為決策變量，解（略）得：Xl≤150件，X2≤100件

fmax＝(120 ×150＋100×100)元＝28000元

故當甲產(chǎn)品生產(chǎn)150件、乙產(chǎn)品生產(chǎn)100件時，產(chǎn)值最大，為28000元。

例2：已知甲、乙兩煤礦每年的產(chǎn)量分別為200萬噸和300萬噸，需經(jīng)過東車站和西車站兩個車站運往外地。東車站每年最多能運280萬噸煤，西車站每年最多能運360萬噸煤，甲煤礦運往東車站和西車站的運費價格分別為1元/噸和1.5元/噸，乙煤礦運往東車站和西車站的運費價格分別為0.8元/噸和1.6元/噸。煤礦應(yīng)怎樣編制調(diào)運方案，能使總運費最少?

解：設(shè)甲煤礦向東車站運x萬噸煤，乙煤礦向東車站運y萬噸煤，那么總運費

f(X，Y)=x+1.5(200－x)+0.8y+1.6(300－y)(萬元)

即f(X，Y)=780－0.5x－0.8y

現(xiàn)要求此目標函數(shù)的最小值。

x、y應(yīng)滿足：x≥0 ;y≥0

200-x≥0

300-y≥0

x+y≤280

200-x+(300-y)≤360

解（略）得：X=0 ，Y=280

∴甲煤礦生產(chǎn)的煤全部運往西車站、乙煤礦向東車站運280萬噸向西車站運20萬噸時，總運費最少。

上述兩例是只有兩個變量的線性規(guī)劃（求目標函數(shù)最大，最小）問題，其求解方法為圖解法，對于含更多變量的線性規(guī)劃問題，在解決思路、步驟上基本一致，只是在具體求解方法上要用到所謂的“單純形”方法，在此不再贅述。

四、結(jié)束語

線性規(guī)劃作為運籌學(xué)的重要分支，它在輔助企業(yè)經(jīng)營決策、計劃優(yōu)化，對于企業(yè)優(yōu)化配置資源，降低成本，實現(xiàn)效益最大化等方面都具有重要的作用，因此作為企業(yè)的經(jīng)營決策者有必要學(xué)習(xí)一點線性規(guī)劃知識，為科學(xué)決策，合理規(guī)劃做必要的知識準備。

參考文獻:

[1]管梅谷鄭漢影:線性規(guī)劃[M].山東科學(xué)技術(shù)出版社， 1983

[2]路正南張懷勝:運籌學(xué)基礎(chǔ)教程[M].中國科學(xué)技術(shù)大學(xué)出版社，2004

[3]趙鳳治:最優(yōu)化計算方法[M].上海科學(xué)技術(shù)出版社， 1983