矩陣在線性規劃中的應用

[摘要] 在經濟管理、交通運輸、工農業生產等經濟活動中，合理安排人力物力資源尤為重要。可以建立線性規劃問題的標準形式，利用矩陣的理論和方法，作一系列的行初等變換，根據檢驗數的值求出線性規劃最優解。

[關鍵詞] 數學模型 初等變換 檢驗數 最優解

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

一、線性規劃問題

1.線性規劃問題的數學模型的一般形式：

設有n個變量，滿足

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

2.線性規劃問題的標準形式

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

滿足（2）的解成為線性規劃的最優解，相應的s值稱為該問題的最優值。

二、運用矩陣解線性規劃最優解

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

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

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

[第一步]

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

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

[第二步]

當所有檢驗數為非負數時，轉入第三步。當檢驗數有負數時，轉入第五步。

[第三步]

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

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

[第四步]

①的單位矩陣所在的列的檢驗數都為0，而其余檢驗數非負時，則所求的最優值為

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

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

②的檢驗數有負數時，轉入第五步。

[第五步]

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

三、解決經濟中的實際問題

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

設生產Ⅰ型產品件，生產型產品件，獲得的收入為R

則此規劃問題的一般形式為

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

對應的方程組

方程組的增廣矩陣為

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

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

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

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

最優解為:件，件，件，件，件

最優值為：（元）

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

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

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