用矩陣法求解線性規劃問題

摘要：線性規劃作為運籌學的一個重要分支，自1947年丹捷格提出了一般線性規劃問題的求解方法即單純形法之后，線性規劃在理論上日益成熟，在使用中日益廣泛與深入，至今單純形法仍是求解線性規劃問題最常用、最有效的方法之一。單純形法的基本步驟是換基迭代，求解過程實質是對線性規劃問題所確定的某個特定矩陣施行初等變換以達到某種形式的過程。因此本文利用線性方程組的同解理論，通過引進人工變量等手段，化一般線性規劃為標準線性規劃，建立線性方程組，寫出其系數矩陣，對系數矩陣進行一系列的最優化過程，得到最優矩陣從而求出最優解。

關鍵詞：線性規劃 單純形法 矩陣 求解

現代科學技術迅猛發展的今天對數學問題的研究提出了更新更高的要求，而線性規劃問題在數學領域及科學技術中應用廣泛，所以對線性規劃問題的求解法要求也越來越高。教材中介紹的主要是用單純形法求解，由于線性約束條件是由線性方程組構成的，而方程組的問題可以轉化為矩陣的形式。所以本文結合自己的學習，通過認真分析查閱資料，整理出了用矩陣法求解線性規劃問題的步驟，以期對線性規劃問題的研究有一定的參考價值。

1、線性規劃問題基本知識簡介

1.1線形規劃問題的標準形式

我們考慮下列線性規劃問題：

約束條件為

其中，稱為決策變量，變量表示決策方案，滿足上述約束條件的決策變量的值稱為線性規劃問題的可行解，我們把使目標函數達到最大的可行解叫最優解，這個最大的值我們稱為最優值；叫價值系數. 在解問題時若要求線性規劃問題的極小值，即

這時只需令

即可將原問題轉化為

即可.

當約束條件為不等式時，有兩種處理方式：當約束條件為“ ”的不等式時，可在不等式的左端加入非負松弛變量，將不等式變為等式；當約束條件為“”的不等式，可在不等式左端減去一個非負剩余變量（也可稱松弛變量），把不等式變為等式約束.

1.2線性規劃問題標準形式的矩陣形式

線性規劃問題用矩陣描述時為：

其中：

—約束條件的維系數矩陣，一般

—資源向量； —價值向量； —決策變量向量

為便于使用矩陣法求解上述線性規劃問題，我們構造如下初始矩陣

這里是一個由約束方程的增廣矩陣和價值系數組成的

矩陣，其中是約束條件的個數，是決策變量的個數.而問題中涉及的 表示的是矩陣秩，即 .問題的基變量可由矩陣中列向量的最大線性無關組的選取方式來確定。

1.3線性規劃問題的最優解

(1)可行解

線性規劃問題：

中，滿足約束條件的

稱為線性規劃問題的可行解，而使目標函數值達到最大的可行解稱為該問題的最優解.

(2)基

設是約束方程組的維系數矩陣，其秩為，是矩陣中階非奇子矩陣（），則稱是線性規劃問題的一個基.這就是說，矩陣是由個線性獨立的列向量組成，不失一般性，可設

稱為基向量，與基向量相應的變量 為基變量，否則稱為非基變量. 為了進一步討論線性規劃問題的解，下面研究約束方程組(1-1) 的求解問題.假設該方程組系數矩陣的秩為，因 ，故它有無窮多個解，假設前個變量的系數列向量是線性獨立的，這時(1-1)式可寫成

或

方程組(1-3)的一個基是

設 是對應于這個基的基變量

現若令(1-3)式的非基變量 ，這時變量的個數等于線性方程的個數.用高斯消去法求出一個解

該解的非零分量的數目不大于方程的個數 ，稱為基解.由此可見，有一個基，就可以求出一個基解.

(3)基可行解

滿足非負條件，的基解，稱為基可行解.

(4)可行基

對應于基可行解的基稱為可行基.

單純形法的基本思想是用迭代法從初始基可行解出發，判斷當前基可行解是否為最優解，如果是則求解結束，否則要進行換基，即將一個非基變量變為一個基變量（叫做入基），同時將一個基變量變為非基變量（叫做出基），換基的原則是換入使目標函數變化最大的，不斷重復上述過程找到問題的最優解為止.

1.4用矩陣法求解線性規劃問題的步驟

(1)確定初始基變量，求得初始基可行解.

將矩陣第一列中 ，得到新的矩陣.重復(2)-(5)直到終止.

2、應用舉例

例1.某工廠在計劃期內要安排生產兩種產品，已知生產單位產品需要設備1臺時，原材料 4千克，生產單位產品需要設備2臺時，原材料 4千克，且該工廠共有設備8臺時，原材料 16千克，原材料12千克.該工廠每生產一件產品可獲利2元，每生產一件產品可獲利3元，問應如何安排計劃使該工廠獲利最多？

解 設分別表示在計劃期內產品的產量，則該問題可用數學模型表示為

第二步，比較價值系數，確定進基變量.

因為價值系數的大小對目標函數值的改變有影響，價值系數大的可以加快目標函數值的改變，故從所有價值系數中選擇絕對值最大的正數如，確定該數在矩陣中的位置，然后把該列代表的決策變量 作為一個新的基變量取代前一個基變量中的一個變量.在本題中由于2＜3，所以此題中價值系數最大的正數為，它在中占第二列，于是就把 作為一個新的基變量.

第三步，依據最小比值原理，找到出基變量，進而求得基可行解.

將 所對的那一列的前三個正數分別去除最后列的對應元素，選出所得商中最小的正值并確定出其在中所占的行數，于是把該行所代表的基變量作為出基變量.通過計算可知

那么其對應的行所代表的基變量就作為出基變量被換出而成為非基變量.于是得到矩陣 如下：

將矩陣作一系列初等變換，將矩陣中第三行第二列處的值變為1，第二列的其他位置的值變為0，這樣得到矩陣

令代入約束條件就求得該可行基對應的可行解

第四步，比較確定矩陣中的最后一行是否還有正數，有則重復二三步，直到最后一行所有元全為非正數為止.題中的最后一行中有正數=2，故重復上述二三步，因，且占中的第一行，故將作為新的基變量，作為非基變量，對作同的初等變換得到

從上面的例子我們可以看出，如果所給定的線性規劃問題有現成的基，那么我們可以直接寫出初始單純形矩陣.如果所給定的線性規劃問題沒有現成的基，則可通過引入人工變量的方法得到一個人造基，從而構造一個輔助問題.然后利用例一中使用的單純形法來求得輔助問題的最優解或判斷輔助問題無最優解.此時原問題和輔助問題的解的情況相同.如果原問題有無最優解無法判定，且輔助問題的最優解中已不含人工變量可以去掉輔助問題的單純形表中對于原問題來說是多余的行及多余的列.如果輔助問題的最優基中含有人工變量，這時若人工變量所對應的行中非人工變量的系數全為0，則可將此行去掉而使輔助問題的最優基中少一個人工變量.若人工變量所對應的行中某一非人工變量的系數不為0，則以此出發對單純形表進行適當的變換進行換基.目的是迫使人工變量離基，經有限個步驟以后總可以使輔助問題的最優基中不再含有人工變量，從而得到原問題的初始單純形表.以上所有的工作都可以用相應的單純形矩陣代替單純形表而對單純形矩陣施行初等行變換達到預期的目的.

3、靈敏度分析

靈敏度分析也叫優化后分析，是研究線性規劃模型某些參數或限制量的變化對最優解的影響及其程度的分析過程.靈敏度分析的主要內容包括研究目標函數的系數發生變化時對最優解的影響，約束方程右端系數發生變化時對最優解的影響以及約束方程組系數陣發生變化時對最優解的影響.針對上述情況，我們會作如下思考：如果上述問題中涉及的系數有一個或幾個發生變化時，那么我們所求得的最優解又回隨這些問題的變化而發生變化嗎？或者說它們會發生怎么樣的變化以及這些系數在哪個范圍內變化時不會影響原問題的最優解或者說不會使問題的最優基發生變化呢？下面我將從資源數量變化和技術系數兩方面的變化來討論它們的變化對線性規劃問題最優解和最優基的影響.

3.1資源數量變化的分析

3.2技術系數的變化

討論技術系數的變化，下面我們以具體例子來說明

例4.分析在原計劃中是否應該安排一種新產品.以例1為例，設該廠除了生產產品 外，現有一種新產品 ，已知生產產品每件需消耗原材料A，B各為6千克，3千克，使用設備2臺時，每件可獲利5元.問改廠是否生產該產品和生產多少？

4、結束語

線性規劃的求解問題在運籌學中中是最重要的知識點，且是貫穿運籌學各個章節的重要理論，在研究其他規劃方面有非常重要的作用.本文通過對線性規劃的矩陣求解法的描述加深了對單純形法實質的理解，矩陣形式是表達最為簡潔又便于理論推證的形式，單純形法的矩陣描述也為研究修正單純形法奠定了基礎.靈敏度分析作為優化后分析對于線性規劃的應用是非常重要的，但在考慮系數變化時一般每次只考慮一個，當多個系數同時變化時，就需要用參數線性規劃進行處理，因此，可以把參數線性規劃看作是靈敏度分析的擴展.

參考文獻：

[1]楊民助．運籌學[M]．西安：西安交通大學出版社，2000

[2]陶謙坎主編.運籌學應用案例[M]．北京：機械工業出版社，1993

[3]胡運權．運籌學習題集[M]．北京：清華大學出版社，1985

[4]林添華．線性規劃的矩陣求解法[J]．龍巖師專學報，2003，6