矩陣在線性規(guī)劃中的應(yīng)用

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

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

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

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

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

設(shè)有n個(gè)變量，滿足

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

2.線性規(guī)劃問題的標(biāo)準(zhǔn)形式

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

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

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

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

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

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

[第一步]

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

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

[第二步]

當(dāng)所有檢驗(yàn)數(shù)為非負(fù)數(shù)時(shí)，轉(zhuǎn)入第三步。當(dāng)檢驗(yàn)數(shù)有負(fù)數(shù)時(shí)，轉(zhuǎn)入第五步。

[第三步]

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

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

[第四步]

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

(中最后一行最后一列的元素?cái)?shù)值)

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

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

[第五步]

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

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

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

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

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

引入非負(fù)的松弛變量，標(biāo)準(zhǔn)形式為

對(duì)應(yīng)的方程組

方程組的增廣矩陣為

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

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

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

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

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

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

故當(dāng)件，件時(shí)，獲得最大收入為件，件。

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

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