【中華百科全書●科學●線形規畫】

楊籍富

【中華百科全書●科學●線形規畫】

 

線形規畫(LinearProgramming)，又稱線形調配，是擬訂資源最佳分配計劃之基本原理。

 

應用於各種不同的系統，包括經濟運用系統、企業營運系統、機器設備系統，及人力運用系統等。

 

其意義是研擬各動作，包括資源、人力、資金等，作最佳之分配，以達成系統營運之最佳成果。

 

線形規劃普通可以數學模式表示之，俾用以求出，達成目標函數所需之目標。

 

至於其解法則有三，一、圖解法：用於較簡單之兩個變數問題，其方法係繪各方程式之直線於平面圖上，應用多面凸集之極點理論求解。

 

二、單純法：為解決複雜線形規畫問題之基本方法，須先導入人工變數於原有方程系內，並作一連串的演算，將最初方程系變為一典型方程系，然後求解。

 

若單純法演算次數過多時，須採用對偶理論，將原有關係方程式改換方式求解。

 

三、改訂單純法：其基本原理，是採用一組數值稱為單純乘數與基底之倒值，以產生在計算上所需要的數值，俾可分析變數較多的線形規畫模型，此種方法，較適合於電子計算機之應用。

 

最早發展的線形規劃，肇始於運輸系統之營運上；

 

而汽油混合問題，也是很早應用於石油工業的線形規劃。

 

特殊的線形規畫問題，尚有整數線形規劃、指派問題及大型線形方程系等。

 

線形規劃的基本問題，既是決定滿足一些線形不等式，或線形等式之線形函數的極值問題。

 

則我們可將一般線形規劃的問題描述如下：給予一組n個變數之線形不等式或線形等式(設共有m個此類不等式或等式，這些不等式或等式稱為限制式)，我們想尋求這n個變數的非負值，而這些值不但要滿足所給的限制式，且要使這些變數之某一線形函數(稱為目標函數)之值為極大或極小。

 

使用數學符號，可將前面的述改寫如下：設此n個變數分別為x1,x2,…,xn，則線形規畫問題之數學模式為：求函數f(x1,x2,…,xn)=c1x1 c2x2 … cnxn的極大值(或極小值)，且滿足(方程式圖)在前述線形規畫問題的數學模式中，目標函數f(x1,x2,…,xn)以及各限制式均為變數x1,x2,…,xn的一次式，所以都是線形的。

 

又各限制式中的｛≧,=,≦｝表示一次式的關係是"≧"或"="或"≦"三者中的某一個。

 

下面我們以一個例子來說明線形規畫問題的模式：某電視台製作甲、乙兩種社教節目，甲節目每次播出時間為二十分鐘，其中有一分鐘廣告時間；

 

乙節目每次播出時間為十分鐘，其中有一分鐘廣告時間。

 

每次播出時收視甲節目的觀眾為二萬名，收視乙節目的觀眾為一萬名。

 

此電視台每週能夠播出社教節目的時間不超過一百六十分鐘，而提供社教節目的廣告商堅持一週內在這兩種社教節目中，至少需播出十二分鐘的廣告。

 

問每週分別要播出甲、乙節目各多少次才會有最多的觀眾？

 

設x1,x2分別為甲、乙兩節目於一週內播出的次數。

 

由播出的時間與廣告時間的限制，x1與x2的值必須滿足20x1 10x2≦160和x1 x2≧12，且x1≧0,x2≧0。

 

一週內的觀眾人數為f(x1,x2)=30000x1 10000x2。

 

因此此問題可寫成如下的數學模式：求x1,x2的值，使f(x1,x2)=30000x1 10000x2的值為極大，且x1,x2滿足：20x1 10x2≦160,x1 x2≧12,x1≧0,x2≧0。

 

這種數學模式的極值問題，就是線形規畫的問題。

 

(張有成、林光賢)

 

引用：http://ap6.pccu.edu.tw/Encyclopedia/data.asp?id=9098