【中華百科全書●科學●線形規畫】
<P align=center><STRONG><FONT size=5>【<FONT color=red>中華百科全書●科學●線形規畫</FONT>】</FONT></STRONG></P> <P><STRONG>線形規畫(LinearProgramming)，又稱線形調配，是擬訂資源最佳分配計劃之基本原理。</STRONG></P><P><STRONG></STRONG> </P>
<P><STRONG>應用於各種不同的系統，包括經濟運用系統、企業營運系統、機器設備系統，及人力運用系統等。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>其意義是研擬各動作，包括資源、人力、資金等，作最佳之分配，以達成系統營運之最佳成果。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>線形規劃普通可以數學模式表示之，俾用以求出，達成目標函數所需之目標。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>至於其解法則有三，一、圖解法：用於較簡單之兩個變數問題，其方法係繪各方程式之直線於平面圖上，應用多面凸集之極點理論求解。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>二、單純法：為解決複雜線形規畫問題之基本方法，須先導入人工變數於原有方程系內，並作一連串的演算，將最初方程系變為一典型方程系，然後求解。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>若單純法演算次數過多時，須採用對偶理論，將原有關係方程式改換方式求解。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>三、改訂單純法：其基本原理，是採用一組數值稱為單純乘數與基底之倒值，以產生在計算上所需要的數值，俾可分析變數較多的線形規畫模型，此種方法，較適合於電子計算機之應用。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>最早發展的線形規劃，肇始於運輸系統之營運上；</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>而汽油混合問題，也是很早應用於石油工業的線形規劃。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>特殊的線形規畫問題，尚有整數線形規劃、指派問題及大型線形方程系等。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>線形規劃的基本問題，既是決定滿足一些線形不等式，或線形等式之線形函數的極值問題。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>則我們可將一般線形規劃的問題描述如下：給予一組n個變數之線形不等式或線形等式(設共有m個此類不等式或等式，這些不等式或等式稱為限制式)，我們想尋求這n個變數的非負值，而這些值不但要滿足所給的限制式，且要使這些變數之某一線形函數(稱為目標函數)之值為極大或極小。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>使用數學符號，可將前面的述改寫如下：設此n個變數分別為x1,x2,…,xn，則線形規畫問題之數學模式為：求函數f(x1,x2,…,xn)=c1x1 c2x2 … cnxn的極大值(或極小值)，且滿足(方程式圖)在前述線形規畫問題的數學模式中，目標函數f(x1,x2,…,xn)以及各限制式均為變數x1,x2,…,xn的一次式，所以都是線形的。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>又各限制式中的｛≧,=,≦｝表示一次式的關係是"≧"或"="或"≦"三者中的某一個。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>下面我們以一個例子來說明線形規畫問題的模式：某電視台製作甲、乙兩種社教節目，甲節目每次播出時間為二十分鐘，其中有一分鐘廣告時間；</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>乙節目每次播出時間為十分鐘，其中有一分鐘廣告時間。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>每次播出時收視甲節目的觀眾為二萬名，收視乙節目的觀眾為一萬名。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>此電視台每週能夠播出社教節目的時間不超過一百六十分鐘，而提供社教節目的廣告商堅持一週內在這兩種社教節目中，至少需播出十二分鐘的廣告。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>問每週分別要播出甲、乙節目各多少次才會有最多的觀眾？</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>設x1,x2分別為甲、乙兩節目於一週內播出的次數。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>由播出的時間與廣告時間的限制，x1與x2的值必須滿足20x1 10x2≦160和x1 x2≧12，且x1≧0,x2≧0。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>一週內的觀眾人數為f(x1,x2)=30000x1 10000x2。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>因此此問題可寫成如下的數學模式：求x1,x2的值，使f(x1,x2)=30000x1 10000x2的值為極大，且x1,x2滿足：20x1 10x2≦160,x1 x2≧12,x1≧0,x2≧0。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>這種數學模式的極值問題，就是線形規畫的問題。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>(張有成、林光賢)</STRONG></P>
<P><STRONG></STRONG> </P>引用：http://ap6.pccu.edu.tw/Encyclopedia/data.asp?id=9098
頁:
[1]