【摘要】線性規(guī)劃是運籌學(xué)中發(fā)展較快，方法較成熟的一個重要分支，已經(jīng)被廣泛的應(yīng)用于工業(yè)、 農(nóng)業(yè)、 交通運輸、 商業(yè)、 國防、 郵電及經(jīng)濟管理等領(lǐng)域，幫助決策人員科學(xué)地制定方針和決策。本文主要闡述了線性規(guī)劃的原理以及計算方法，并通過若干實際案例來說明如何應(yīng)用線性規(guī)劃來解決經(jīng)濟管理中所遇到的問題。

【關(guān)鍵詞】線性規(guī)劃 經(jīng)濟管理

【中圖分類號】G64 【文獻標(biāo)識碼】A 【文章編號】2095-3089（2013）11-0251-03

線性規(guī)劃是運籌學(xué)中發(fā)展最成熟，應(yīng)用最廣泛的一個重要分支。在1951年，美國經(jīng)濟學(xué)家?guī)炱章故状螌⒕€性規(guī)劃應(yīng)用于經(jīng)濟領(lǐng)域，并以此與康托羅維奇一起獲得了1957年的諾貝爾經(jīng)濟學(xué)獎[1]。從此，線性規(guī)劃便被廣泛的應(yīng)用于經(jīng)濟領(lǐng)域，為人類進行經(jīng)濟管理和分析決策提供科學(xué)依據(jù)。

1.線性規(guī)劃簡介

1.1線性規(guī)劃的基本思想

線性規(guī)劃的主要研究內(nèi)容是求解線性目標(biāo)函數(shù)在一定約束條件下的極值問題。而在經(jīng)濟管理領(lǐng)域，許多實際問題都能夠轉(zhuǎn)化為線性規(guī)劃問題，求解線性規(guī)劃問題的最優(yōu)解就是得到這些實際問題的解，也就是指導(dǎo)經(jīng)濟生活的最佳方案。實際問題轉(zhuǎn)化為線性規(guī)劃問題的首要步驟就是建立線性規(guī)劃數(shù)學(xué)模型。求解數(shù)學(xué)模型的過程即為解決實際問題得到最佳方案的過程。數(shù)學(xué)模型建立的一般步驟為：第一，列出約束條件及目標(biāo)函數(shù)；第二，畫出約束條件所表示的可行域；第三，在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值[2]。線性規(guī)劃問題的滿足線性約束條件的解叫作可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃問題的三要素。其中決策變量對應(yīng)實際問題中出現(xiàn)的未知因素。約束條件對應(yīng)實際問題中的限制因素，而目標(biāo)函數(shù)即為實際問題的數(shù)學(xué)表達形式。

1.2線性規(guī)劃的發(fā)展概況

早在1823年，法國數(shù)學(xué)家傅里葉便提出了線性規(guī)劃的概念，然而并未足夠的引起重視。1911年，另一個法國數(shù)學(xué)家瓦萊有一次獨立的提出了線性規(guī)劃的想法，依然沒有引起關(guān)注。直到1947年的夏天，美國數(shù)學(xué)家G.B.丹齊克提出了單純形法從而為線性規(guī)劃奠定了基礎(chǔ)。

50年代后線性規(guī)劃取得了較大的進展，許多學(xué)者對其進行了大量的理論研究，并涌現(xiàn)出一大批新計算方法。例如，1954年C.萊姆基提出了對偶單純形法，同年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。隨著線性規(guī)劃算法以及電子計算機的出現(xiàn)，線性規(guī)劃的應(yīng)用領(lǐng)域隨著逐步擴大。

2.線性規(guī)劃的數(shù)學(xué)模型建立和求解方法

2.1 線性規(guī)劃的數(shù)學(xué)模型

線性規(guī)劃的數(shù)學(xué)模型分為一般形式和標(biāo)準(zhǔn)形式兩種，其一般形式表示如下：

由于在實際應(yīng)用過程當(dāng)中，實際問題的復(fù)雜化，多樣化都會導(dǎo)致建立數(shù)學(xué)模型時約束條件以及目標(biāo)函數(shù)在內(nèi)容和形式上的巨大差異，為了方便討論以及規(guī)范計算方法，可以將一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式，轉(zhuǎn)化過程必須掌握三個原則：目標(biāo)最值化，約束等式化以及變量非負(fù)化[3]。轉(zhuǎn)化之后的標(biāo)準(zhǔn)表示形式如下：

其中算是（1）、（4）、（7）均為目標(biāo)函數(shù)，而（2）、（3）、（4）、（6）、（8）為約束條件。

2.2 線性規(guī)劃的求解方法

線性規(guī)劃問題的求解方法多種多樣，早在1947年，美國數(shù)學(xué)家G. B. Dantzig便提出了求解線性規(guī)劃問題的單純形方法，而這種方法也日益成熟，成為求解線性規(guī)劃問題的通用方法。單純形法的理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間 Rn中的多面凸集， 其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應(yīng)的可行解稱為基本可行解[4-6]。其主要思想是先找到一個初始基本可行解，鑒別此初始基本可行解是否為最優(yōu)解，如不是，則從此初始基本可行解出發(fā)，經(jīng)過一定的轉(zhuǎn)化法則求得一個使目標(biāo)函數(shù)值有所改善的基本可行解，再進行鑒別，如仍不是最優(yōu)解，繼續(xù)進行轉(zhuǎn)化和鑒別，通過不斷改進基本可行解，力圖得到最優(yōu)基本可行解；由于基本可行解的個數(shù)有限，經(jīng)過有限次轉(zhuǎn)換必能得到一個最優(yōu)解。然而單純形法有一個弱點，那就是它們首先要找出一組基本可行解，再從這個基本可行解出發(fā)求改進的基本可行解，目前較常見的求初始基本可行解的方法有兩種，一種是兩階段法；另外一種是大M法[7]。

除卻單純形算法，另外一種方法也得到了廣泛的應(yīng)用，即Karmarkar算法。Karmarkar算法是由印度科學(xué)家Karmarkar于1984年提出，一經(jīng)提出便引起了轟動。Karmarkar算法極大的提高了線性規(guī)劃的求解時間，因此也被稱為多項式時間算法。Karmarkar算法與單純形算法的不同之處在于，兩者的出發(fā)點不同，單純形從邊界出發(fā)，而Karmarkar算法從內(nèi)部出發(fā)，并永不從邊界走。

3.線性規(guī)劃在經(jīng)濟管理中的應(yīng)用案例

在經(jīng)濟管理中時常會遇到譬如如何獲得最大產(chǎn)出率或者利潤率的問題。如何解決這些問題都是在線性規(guī)劃研發(fā)的范疇內(nèi)。

3.1 最大利潤問題

先假設(shè)某工廠需要在計劃期內(nèi)生產(chǎn)三種產(chǎn)品x1， x2， x3。這三種產(chǎn)品都分別需要使用四臺設(shè)備進行加工，四臺設(shè)備分別以A， B， C， D表示。 根據(jù)生產(chǎn)工藝，產(chǎn)品 x1、x2、x3各需要使用四臺設(shè)備的加工臺時數(shù)見下表（表1）。已知各設(shè)備在計劃期內(nèi)有效臺時數(shù)分別是16 ， 14 ， 20 ， 16。（一臺設(shè)備工作一小時稱為一臺時），該工廠每生產(chǎn)一件x1產(chǎn)品可得利潤 2萬元，而每生產(chǎn)一件x2產(chǎn)品可得利潤 3萬元，每生產(chǎn)一件x3產(chǎn)品可獲得利潤1萬元。問題是工場如何安排生產(chǎn)計劃， 才能獲得最大的利潤？

表1 三種產(chǎn)品所需要的臺時數(shù)

第一步，建立模型。

第二步，將其化為線性規(guī)劃的標(biāo)準(zhǔn)形。

引入松弛變量：

x4—設(shè)備A的閑置臺時數(shù)

x5—設(shè)備B的閑置臺時數(shù)

x6—設(shè)備C的閑置臺時數(shù)

x7—設(shè)備D的閑置臺時數(shù)

標(biāo)準(zhǔn)型表示式為：

3.2 投資收益率最大問題

假設(shè)某人利用10萬元現(xiàn)金進行投資，并具有以下3種投資項目：

項目A：從第一年到第四年每年年初需要投資， 并于次年末回收本利 110 % ；

項目B：第三年年初需要投資， 到第五年末回收本利 125 %， 但規(guī)定最大投資額不超過 5萬元；

項目C：五年內(nèi)每年初可買公債，于當(dāng)年末歸還，并加利息7%。問如何確定這些項目每年的投資額， 使得此人第五年末擁有的資金本利總額最大？

第一步，可根據(jù)投資情況建立投資份額表，如下表（表2）：

表2 投資份額表

上表中xia，xib，xic（i=1，2，3，4，5）分別代表第i年年初向項目A，B，C項目投入的投資額。

第二步：確定目標(biāo)函數(shù)，在此例中如何獲得最大的本利總額，設(shè)Z為最大的本利總額。目標(biāo)函數(shù)應(yīng)該是三項投資在第五年末回收的本利之和。

第三步：確定函數(shù)的約束條件。在此例中，要想獲得最大的收益，必須在每年年初就將手頭全部資金投出去，這是原則一。每年年底收獲的本息總額即為第二年年初的投資總額，這為原則二。根據(jù)這兩個原則，可以確定如下關(guān)系式：

第五步，求解此模型。根據(jù)單純形法的迭代運算（具體步驟此處省略）求得最佳的投資方案如下：

第一年： x1a =30000元， x1c =70000元

第二年： x2a =2249元， x2c =5000元

第三年： x3a = 0元， x3b = 50000元， x2c = 0

第四年： x4a = 45000元， x4c = 0

第五年： x5c = 0

到第五年末期擁有總金額為 126250元， 即盈利 26.25 %。

3.3 成本最小化問題

先假設(shè)某公司要對其生產(chǎn)的某產(chǎn)品進行電視廣告宣傳。廣告的受眾群體是婦女和兒童。電視廣告的收費根據(jù)時段的不同而不同。上午時段，播放一次廣告節(jié)目的收費為1000元，中午時段，播放一次廣告節(jié)目的收費為1300元，晚上時段，播放一次廣告節(jié)目的收費為5000元。而每個時段，受眾全體的收看人次也不一樣。先假設(shè)上午時段，每次廣告節(jié)目總共有500位婦女和500位兒童觀看；中午時段則有1000位婦女和1500位兒童觀看；晚上時段則有8000位婦女和6000位兒童觀看。該公司要求每天至少有90000位婦女和75000位兒童能觀看到此廣告節(jié)目。問如何安排廣告節(jié)目的播出時間以達到此要求又能最節(jié)省廣告成本。

根據(jù)以上描述，首先確定決策變量為x1，x2，x3分別為上午，中午，晚上播放廣告節(jié)目的次數(shù)?？纱_定總觀看人數(shù)表（表3）：

表 3 每時段觀看廣告人數(shù)

第一步，確定目標(biāo)函數(shù)，此例中目標(biāo)函數(shù)為最小的廣告成本，設(shè)廣告總成本為Z，則

minZ=1000x1+1300x2+5000x3

第二步，確定約束條件為：

500x1+1000x2+8000x3≥90000500x1+1500x2+6000x3≥75000x1，x2，x3≥0

第三步，運用單純形法計算得到最優(yōu)解為：x1=1，x2=10，x3=10，minZ=64000元。也就是說上午時段播一次，中午時段播10次，晚上時段播10次既能滿足受眾群的觀看要求，也使得播放成本最低。

4.結(jié)論

線性規(guī)劃通過建立數(shù)學(xué)模型，描述在經(jīng)濟管理工作中所遇到的各種實際問題，求解其最優(yōu)解或最佳方案，指導(dǎo)企業(yè)，政府機構(gòu)，銀行部門等進行整體統(tǒng)籌規(guī)劃，力求使用最少的人力物力資源達到最大的經(jīng)濟效益；或在一定的人力物力資源約束條件下，進行合理的統(tǒng)籌規(guī)劃以達到獲得最大的利益。運用線性規(guī)劃方法能夠使得企業(yè)的決策具有科學(xué)性和可靠性，能夠使得企業(yè)積極的適應(yīng)激烈的市場競爭，進行合理的資源配置，制定科學(xué)的生產(chǎn)計劃和投資計劃，從而提高企業(yè)的效率獲得最大的經(jīng)濟效益。線性規(guī)劃將管理和科學(xué)完美的結(jié)合在一起，將在管理領(lǐng)域具有廣泛的發(fā)展和應(yīng)用空間。

參考文獻：

[1]唐加冕， 周京徽. 線性規(guī)劃問題在經(jīng)濟生活中的應(yīng)用[J]， 商業(yè)時代， 2011（19）：10-11.

[2]齊毅. 經(jīng)濟應(yīng)用數(shù)學(xué)——線性代數(shù)與線性規(guī)劃[M]，北京： 北京高等教育出版社， 2002.

[3]劉春艷. 線性規(guī)劃在經(jīng)濟管理中的應(yīng)用[J]， 電力學(xué)報，2 008（23）：459-462.

[4]趙娜；黃瑞芳. 線性規(guī)劃模型在經(jīng)濟管理中的應(yīng)用[J]， 濟源職業(yè)技術(shù)學(xué)院學(xué)報， 2010（3）：62-65.

[5]楊冬英，高玉斌. 線性規(guī)劃在企業(yè)經(jīng)營中的應(yīng)用[J]， 河南科技， 2007（10）： 45- 46.

[6]熊楊. 線性規(guī)劃在現(xiàn)代管理中的應(yīng)用[J]， 山四財經(jīng)學(xué)院學(xué)報， 2009（4）.

[7]曾梅清，田大鋼. 線性規(guī)劃問題的算法綜述[J]， 科學(xué)技術(shù)與工程， 2010（1）：152-159.

[8]伍學(xué)濱，鄧小英. 運籌學(xué)在經(jīng)濟管理中的應(yīng)用[J]， 企業(yè)經(jīng)濟， 2005（11）：57-58.

[9]陳寶林. 最優(yōu)化理論與算法[M]， 清華大學(xué)出版社， 2005.