## 線性規劃與單純形法的幾何與經濟解釋
## An Introduction to Linear Programming and Simplex Method: Geometric and Economic Implications of the Model and the Method

## 台灣大學生物環境系統工程學系
## 劉佳明

### 摘要
本文考慮一個農場生產規劃案例，從代數、幾何與經濟三個方面，介紹線性規劃模式與其單純形演算法。農場以三種資源生產二種作物，在資源有限的條件下，為使收益最高，如何決定作物產量？首先，建立這個問題的線性規劃模式，然後，在二維與三維(二產品產量與收益)坐標系統中，考慮模式各式的圖形：限制式各為一邊界面一側的半空間，而限制式組則是其交集 - 一個凸多邊形直角柱；收益函數則是一空間平面。因此，在幾何觀點下，案例問題就是：收益「平面」斜截限制「凸多邊形直角柱」，二者交集為「凸多邊形」，求其最高點?
藉案例的上述圖像場景，單純形法的原理可以描述如下：在收益平面與限制柱體所交截的凸多邊形上，從一個角點出發，選擇改善收益最快的邊界前行，直到鄰近角點；重復同樣步驟：沿最陡邊界爬升到鄰近角點；直到一個角點，其邊坡無一上升時，所在點即收益最高角點。然後，將幾何上這個「沿邊界逐點上坡」的單純形法觀念，發展成代數的演算程序。
最後，檢視模式方程組的行與列係數，說明演算過程中的一些經濟觀念，包括投入新產品時，舊產品的對應變動率(即替換率)、新舊產品的對應收益變動率(即直接收益與機會成本)、各資源對舊產品的替換率、各資源的邊際價值等，以及這些項目之間的關係。

### 1. 前言
第二次世界大戰期間，英軍為了有效利用軍事資源，發展軍備，掌握敵情，研擬策略，乃召集科學家與工程師，設立作業研究團隊，對戰術戰略、軍需製造與輸配等作業進行研究。隨後，美、加軍方也設立類似的團隊。它們先是建立一些軍事作業的數學模式，然後發展其分析方法並應用在各類實際作業上。
大戰結束後，學術單位、政府機構與企業組織紛紛投入各類型系統作業的研究。因為實際的需要、理論的進展與計算機科技的成熟，作業研究仍然在成長與拓展中。
各類作業研究方法中，線性規劃(Dantzig, 1963; Murty, 1983; Padberg 1999)的應用最廣，而且理論完備，演算快速，一般個人電腦即能處理成千上萬個變數與限制式的各類龐大問題，所以常應用在各類系統的規劃問題上，如調查規劃、設計施工、生產輸配或維護管理等項目(Hillier & Hillier, 2003; 劉佳明, 1979)。在微軟公司EXCEL增益集中就有線性規劃求解程式，可以想見這個方法的應用已經相當普遍。
對線性規劃與單純形法的介紹，除非專書，否則常只說明代數模式與其演算步驟，本文藉簡單農場規劃案例，從代數、幾何與經濟三個面向加以解釋。首先，建立農場二產品三資源生產案例的線性規劃模式，接著，檢視這個代數模式的坐標圖形。在幾何觀點下，限制式是以「凸多邊形直角柱體」表示，收益則以「平面」表示。案例所求就是「柱體」與「平面」交截面的最高點。面對這個圖形，可以清楚的描述它的解法：沿收益截面的邊界逐點攀升，直到一角點，它的所有邊界不再上升，那便是收益最高點。
最後，從幾何回到代數，將上述直覺的幾何解法構想，發展成代數演算程序，並探討過程中方程組係數所代表的經濟觀念，包括新投入產品與資源對目前產品的替換率與機會成本等項目。
初讀本文可以略過標題加註星號*的各小節與各處的細節部分，因為它們通常在比較深入的探討演算效率或經濟觀念時才有需要。
### 2. 生產規劃案例與其數學模式
#### 2.1 農場生產規劃案例
有一農場擬以土地、工時與水三種資源，生產小麥與玉米二種產品，它有三組規劃資料：‹1›資源的供應量，‹2›單位產品的淨收益，‹3›單位產品的資源需求量，見表1各行列。根據已知資料，如何決定產品產量以使收益最大？

|單位產品<br>資源需求量| |產品| |資源供應量|產量規劃問題|
| -| -| -| -| -| -|
|||小麥|玉米|
|資源|土地|1|1| 7 公頃|求產量方案$(x_1, x_2)$使總收益最大，並且滿足資源與產品限制條件。模式見(0)~(4)式。|
||工時|2|1| 12 工時|
||水量|1|3| 15 公噸|
|單位產品淨益| |4|5|萬元/公頃|
|(面積)產量變數| |$x_1$|$x_2$|公頃|

#### 2.2 農場生產規劃模式
設小麥與玉米二種產品的(面積)產量分別為$x_1$與$x_2$公頃，以代數式表示產品的收益和資源的限制，建立下列農場案例的模式：
產量方案$(x_1, x_2)$的總收益z以式(0)表示，稱為目標函數式；方案各資源需求量不應大於其供應量條件，分別以式(1)、(2)、(3)表示，稱為關係(或函數、或結構)限制；各產量不小於0的條件，以一組式(4)表示，稱為變數非負限制。以上目標函數與限制(或稱約束)都是一次式，故組成一個線性規劃模式。各類問題考慮的限制不同，生產問題除了資源，還有需求、技術與機具等限制。
模式的關係限制為等式，而且變數皆有非負條件者，稱為標準形式。這個形式對運算和討論都比較方便。案例模式的各關係不等式(1)至(3)，若分別引進餘變數(或稱鬆弛變數)$x_3, x_4, x_5$，則可化為等式，故案例模式的標準形式為：
列各式中的餘變數$x_3, x_4, x_5$，分別表示土地、工時與水資源的剩餘量。例如，根據(13)式$x_5=15- (x_1+ 3x_2)=$ 供應水量 - 產品總需水量，故餘變數$x_5$表示水量供需差值，即剩餘水量。
符號'~'將用以表示前後二編號中間的連續編號，
例如，(0)~(4)表示(0), (1), (2), (3), (4)。
從代數的觀點，資源和產品一樣，有其對應變數，資源餘變數表示需要單一資源的產品的產量，其單位收益為0。例如，生產水量餘變數$x_5$這種產品一單位，只需水1公噸，不需其它資源，這可由關係式(11)~ (13)中變數$x_5$的係數0, 0, 1得知，故$x_5$是閑置水量的產品。關係式變數$x_j$的係數，表示$x_j$產品單位產量的資源需求量，例如，變數$x_1$的係數1, 2, 1，表示生產單位小麥需要土地1公頃、人工2工時和水量1公噸。