[摘要] 在經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟活動中，合理安排人力物力資源尤為重要?？梢越⒕€性規(guī)劃問題的標準形式，利用矩陣的理論和方法，作一系列的行初等變換，根據(jù)檢驗數(shù)的值求出線性規(guī)劃最優(yōu)解。

[關鍵詞] 數(shù)學模型 初等變換 檢驗數(shù) 最優(yōu)解

運籌學發(fā)展歷史不長，但內(nèi)容豐富，涉及面廣，應用范圍大，形成了相當龐大的學科。線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數(shù)學方法。在經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟活動中，提高經(jīng)濟效益是人們不可缺少的要求，建立數(shù)學模型運用矩陣求規(guī)劃問題的最優(yōu)解尤為重要。

一、線性規(guī)劃問題

1.線性規(guī)劃問題的數(shù)學模型的一般形式：

設有n個變量，滿足

s稱為目標函數(shù)，式(1)稱為約束條件.一般地，求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。滿足線性約束條件的解叫做可行解，使S取最大值或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解。

2.線性規(guī)劃問題的標準形式

只要引入新的非負變量（稱為松弛變量），不妨設不等式組中每一個不等式加一個松弛變量后變?yōu)榈仁?，這樣就可以使不等式組(1)變?yōu)榫€性方程組，作為線性規(guī)劃問題的標準形式。即

滿足（2）的解成為線性規(guī)劃的最優(yōu)解，相應的s值稱為該問題的最優(yōu)值。

二、運用矩陣解線性規(guī)劃最優(yōu)解

矩陣在經(jīng)濟分析中有著廣泛的應用，可以利用矩陣的理論和方法，對標準形式中線性方程組的增廣矩陣作一系列的行初等變換，根據(jù)檢驗數(shù)的值可判定基變量為多少時，規(guī)劃問題有最優(yōu)解及最優(yōu)值，最優(yōu)解及最優(yōu)值是多少，從而解決線性規(guī)劃最優(yōu)解問題。

在方程（2）中若S把視為一個變量，寫為

方程（3）是一個n+m+1個未知量，m+1個方程的線性方程組，解法如下

[第一步]

記方程（3）的增廣矩陣為

矩陣L中的最后一行的數(shù)稱為檢驗數(shù)，從S=0做起。

[第二步]

當所有檢驗數(shù)為非負數(shù)時，轉(zhuǎn)入第三步。當檢驗數(shù)有負數(shù)時，轉(zhuǎn)入第五步。

[第三步]

最小比值原則：用矩陣L中的第一列前m行大于0的元素除同行對應的最后一列的元素，即。取比值最小者，記為。此時稱為主元，所在的行稱為主元行，所在的列稱為主元列。(若第一列的前m個元素沒有正數(shù)，就試第二列，依次類推)

對矩陣作初等行變換，將主元變?yōu)?，所在列的其他元素變?yōu)?；重復類似的變換運算，依次繼續(xù)作若干次得到矩陣，在中必有m行m列的元素構(gòu)成一個m階單位矩陣，不妨設的前m行m列是m階單位矩陣，于是，矩陣為

[第四步]

①的單位矩陣所在的列的檢驗數(shù)都為0，而其余檢驗數(shù)非負時，則所求的最優(yōu)值為

(中最后一行最后一列的元素數(shù)值)

矩陣中單位矩陣所在各行的最后一列元素，為所求相應變量（稱為基變量）的值，其他變量取值均為0（稱為非基變量）這樣得到的解為所求的最優(yōu)解。

②的檢驗數(shù)有負數(shù)時，轉(zhuǎn)入第五步。

[第五步]

所有檢驗數(shù)為負數(shù)時，取其絕對值最大者所在的列為主元列，返回第三步作行初等變換，從而求出最優(yōu)解及最優(yōu)值。

三、解決經(jīng)濟中的實際問題

例如 為制造兩種類型的產(chǎn)品，倉庫最多提供80的鋼材，已知每制造一件Ⅰ型產(chǎn)品需要耗鋼2kg，最少需生產(chǎn)10件，而每件售價50元；每制造一件Ⅱ型產(chǎn)品需要耗鋼1kg，最少需生產(chǎn)40件，而每件售價30元。試選擇最優(yōu)生產(chǎn)方案，以獲最大收入?

設生產(chǎn)Ⅰ型產(chǎn)品件，生產(chǎn)型產(chǎn)品件，獲得的收入為R

則此規(guī)劃問題的一般形式為

引入非負的松弛變量，標準形式為

對應的方程組

方程組的增廣矩陣為

末行檢驗數(shù)中有兩個負數(shù)，絕對值最大者為-50，取-50所在的列為主元列，用最小比值原則，第二行為主元行，為主元。進行行初等變換得：

檢驗數(shù)中仍有負數(shù)，同樣，-50所在第四列為主元列，按最小比值原則，取為主元。進行行初等變換得：

仍有負檢驗數(shù)-5，同樣的方法取為主元。進行行初等變換得：

以上矩陣前三行的第1，2，4列構(gòu)成一個3階單位矩陣，其所在的列的檢驗數(shù)為0，其余檢驗數(shù)均非負，所以，為基變量，為非基變量，得到

最優(yōu)解為:件，件，件，件，件

最優(yōu)值為：（元）

故當件，件時，獲得最大收入為件，件。

在線性規(guī)劃的實際問題中，主要研究解決兩種類型的問題：一是給定一定數(shù)量的人力、物力和財力資源，怎樣運用這些資源使完成的任務量最大，收到的效益最大；二是給定一項任務問怎樣統(tǒng)籌安排，完成這項任務耗費的人力、物力資源最小．隨著計算機的逐漸普及，它越來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事行動和科學研究的各個方面，為社會節(jié)省的財富、創(chuàng)造的價值無法估量。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。