線性規劃 (一):標準型問題

本文的閱讀等級:中級

線性規劃 (linear programming) 是一種最佳化問題。顧名思義,線性規劃的目標函數 (objective function) 是未知變數的線性函數,約束條件 (constraints) 則是包含未知變數的線性等式或不等式。儘管最佳化目標與約束條件可能因問題而有所不同,所有的線性規劃問題都可以轉換成下列標準型:

\begin{array}{lll}  \min & c_1x_1+c_2x_2+\cdots+c_nx_n &\\  \mathrm{subject~to}& a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=b_1\\  &a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n&=b_2\\  &\vdots&~~~~\vdots\\  &a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=b_m\\  &x_1\ge 0,~x_2\ge 0,\ldots, x_n\ge 0, &  \end{array}

其中 a_{ij}, b_{i}, c_{j}i=1,\ldots,mj=1,\ldots,n,是給定的實數,x_1,\ldots,x_n 是待決定的未知數。我們之所以將問題寫成標準型,主要的原因是為了執行消去法以化簡線性方程組 (消去法不適用於線性不等式)。針對標準型問題,所謂最佳化是指在滿足 (subject to) 給定的線性方程組,以及未知變數必須為非負值的條件下,尋找可使目標函數最小化的未知變數。因為約束等式可乘以 -1,為便利分析,我們假設每一 b_i\ge 0。線性規劃標準型問題可以用矩陣與向量簡明地表達如下:

\begin{array}{lll}  \min& \mathbf{c}^T\mathbf{x} \\  \mathrm{subject~to}& A\mathbf{x}=\mathbf{b}, ~~\mathbf{x}\ge\mathbf{0}.  \end{array}

上式中,A=[a_{ij}] 是一 m\times n 階矩陣,\mathbf{b}=[b_i] 是一 m 維向量,\mathbf{c}=[c_j] 是一 n 維向量,\mathbf{x}=[x_j] 是一 n 維未知向量。不等式 \mathbf{x}\ge\mathbf{0} 表示 \mathbf{x} 的每一元皆非負值。本文介紹一些典型的線性規劃問題,並說明如何將給定的問題轉換成標準型。

 
線性規劃廣泛應用於作業研究、管理學,和經濟學等領域,下面介紹四個類型的問題,它們要達成的目標不脫老祖母的智慧:「開源,節流」。

例一:飲食問題[1](diet problem)
假設某營養師的飲食計畫中涵蓋 n 種食物,以及每日必須攝取的 m 種營養素。對於 i=1,\ldots,mj=1,\ldots,n,令

  • a_{ij} 表示第 j 種食物中第 i 種營養素的每單位含量,
  • b_i 表示第 i 種營養素的每日需求量,
  • c_j 表示第 j 種食物的每單位價格,
  • x_j 表示第 j 種食物的每日食用量。

飲食問題的目標是在滿足所有營養素的每日需求的前提下,找出最少成本的飲食方式,陳述如下:

\begin{array}{lll}  \min & c_1x_1+c_2x_2+\cdots+c_nx_n &\\  \mathrm{subject~to}& a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n &\ge b_1\\  &a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n &\ge b_2\\  &\vdots&~~~~\vdots\\  &a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n &\ge b_m\\  &x_1\ge 0,~x_2\ge 0,\ldots, x_n\ge 0. &  \end{array}

例二:投資組合選擇問題 (portfolio selection problem)
假設某公司使用 m 種原料來生產 n 種產品。對於 i=1,\ldots,mj=1,\ldots,n,令

  • a_{ij} 表示第 j 種產品中第 i 種原料的每單位使用量,
  • b_i 表示第 i 種原料的庫存,
  • c_j 表示第 j 種產品的每單位獲利,
  • x_j 表示第 j 種產品的產量。

投資組合選擇問題的目標是在現有原料庫存的限制下,找出獲致最大利潤的產品組合方式,如下:

\begin{array}{lll}  \max & c_1x_1+c_2x_2+\cdots+c_nx_n &\\  \mathrm{subject~to}& a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n &\le b_1\\  &a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n &\le b_2\\  &\vdots&~~~~\vdots\\  &a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n &\le b_m\\  &x_1\ge 0,~x_2\ge 0,\ldots, x_n\ge 0. &  \end{array}

例三:運輸問題 (transportation problem)
假設某公司要將存放於 m 個倉庫的商品運送至 n 個客戶所在地。對於 i=1,\ldots,mj=1,\ldots,n,令

  • a_i 表示第 i 個倉庫的商品存量,
  • b_j 表示第 j 個客戶的需求量,
  • c_{ij} 表示從第 i 個倉庫至第 j 個客戶的每單位商品運輸成本,
  • x_{ij} 表示從第 i 個倉庫至第 j 個客戶的商品運送量。

運輸問題的目標是在滿足所有客戶需求的條件下,決定最少成本的運送方式:

\begin{array}{lll}  \min & \displaystyle\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij} &\\  \mathrm{subject~to}& \displaystyle\sum_{j=1}^nx_{ij}\le a_i,~~i=1,\ldots,m,\\  &\displaystyle\sum_{i=1}^mx_{ij}=b_j,~~j=1,\ldots,n,\\  &x_{ij}\ge 0,~~i=1,\ldots,m,~~j=1,\ldots,n.  \end{array}

例四:倉儲管理問題 (warehouse management problem)
假定某倉儲公司的管理業務是買進與賣出某商品。假設倉儲的容許庫藏量是 k,每單位商品的每月庫藏成本是 c。對於 i=1,\ldots,n,令

  • p_i 表示第 i 月的商品價格,
  • b_i 表示第 i 月的買入量,
  • s_i 表示第 i 月的賣出量,
  • x_i 表示第 i 月初的庫存量。

假設倉庫第 1 月的初始庫藏是零,第 n 月底結束經營時的庫藏量也是零。倉儲管理問題的目標是在容許庫藏量的限制下,找出獲取最大利潤的商品買入與賣出量,如下:

\begin{array}{lll}  \max & \displaystyle\sum_{i=1}^n(p_is_i-cx_i) &\\  \mathrm{subject~to}& x_1=0& \\  & x_{i+1}=x_i+b_i-s_i,~~ i=1,\ldots,n-1&\\  &0=x_n+b_n-s_n &\\  &k\ge x_i\ge 0,~b_i\ge 0,s_i\ge 0,~~ i=1,\ldots,n. &  \end{array}

 
從這些例子我們發現給出的問題描述未必符合標準型,共有三種情況需要考慮:問題規範是最大化目標函數,約束條件是不等式 (\ge\le),以及某些未知變數完全不受限 (前例未顯示此情況)。下面我們說明如何將這些外型不一的問題轉換成標準型。

(1) 將最大化改成最小化:線性規劃問題的最佳化標的若不是最小化成本函數,便是最大化效用函數。只要改變目標函數的正負號,即可將最大化問題改成標準型設定的最小化問題,也就是說,\max \mathbf{c}^T\mathbf{x} 等價於 \min (-\mathbf{c})^T\mathbf{x}

(2) 加入鬆弛變數 (slack variable) 與剩餘變數 (surplus variable):如欲將不等式 \le 替換為等式,不難確認

a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\le b_i

等價於

a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n+s_i=b_i,~~s_i\ge 0

其中 s_i 稱為鬆弛變數。相反的,

a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\ge b_i

等價於

a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n-s_i=b_i,~~s_i\ge 0

這時 s_i 稱為剩餘變數。注意,鬆弛變數的係數是 1,剩餘變數的係數是 -1。鬆弛變數與剩餘變數是線性規劃特有的名詞。在投資組合選擇問題中,假設不等式 2x_1+x_2\le 50 表示產品甲 (以 x_1 表示數量) 與產品乙 (以 x_2 表示數量) 使用的原料總量不可大於 50 單位。加入鬆弛變數 s 除了將不等式轉換成等式 2x_1+x_2+s=50,還有另一個好處。鬆弛變數清楚地告訴我們尚未使用,或者說閒置的 (idle) 原料數量是 s,所以稱之為鬆弛。反過來說,在飲食問題中,若不等式 2x_1+x_2\ge 50 表示食物甲 (x_1) 與食物乙 (x_2) 所含的營養素不能少於 50 單位。加入剩餘變數 s,則得 2x_1+x_2-s=50。剩餘變數指出超過最低需求,即額外多出來的 (extra) 營養素是 s 單位,所以稱之為剩餘。

(3) 去除自由變數:如果未知數 x_i 不受限制,我們說 x_i 是自由變數。每一個自由變數可以用兩個受限變數取代:令 x_i=u_i-v_i,其中 u_i\ge 0v_i\ge 0。這個方法會使系統增加一個未知變數,因此 x_i 存在無窮多種表達方式,不過引入冗餘並不會阻礙我們日後的求解工作。另一個辦法是挑選一個包含 x_i 的約束等式 (這肯定辦得到,否則約束最佳化問題即不成立),解出 x_i,再將此表達式代入目標函數與其他約束等式,如此即可消去 x_i。如此一來,系統不僅減少了一個變數,同時也減少一個約束條件式。

 
下面舉一例展示線性規劃問題轉換成標準型的程序。考慮

\begin{array}{lrl}  \max& 3x_1-2x_2 & \\  \mathrm{subject~to}&4x_1-6x_2&\le 5\\  &5x_1-2x_2&\ge 7\\  &x_1&\ge 0.  \end{array}

注意轉換步驟由上往下執行。(1) 將最大化目標改成 \min~ -3x_1+2x_2。(2) 加入鬆弛變數 s_1 與剩餘變數 s_2 以便將不等式改為等式。因為沒有必要區分原始的未知變數與新引進的鬆弛和剩餘變數,可令 x_3=s_1x_4=s_2,結果如下:

\begin{array}{lrl}  \min& -3x_1+2x_2 & \\  \mathrm{subject~to}&4x_1-6x_2+x_3&= 5\\  &5x_1-2x_2-x_4&=7\\  &x_1,x_3,x_4&\ge 0.  \end{array}

(3) 最後要處理自由變數 x_2。第一個方法設 x_2=u_2-v_2,並令 x_5=u_2x_6=v_2。代入步驟 (2) 導出的目標函數與約束條件,可得標準型:

\begin{array}{lrl}  \min& -3x_1+2x_5-2x_6 & \\  \mathrm{subject~to}&4x_1+x_3-6x_5+6x_6&= 5\\  &5x_1-x_4-2x_5+2x_6&=7\\  &x_1,x_3,\ldots,x_6&\ge 0.  \end{array}

第二個方法從步驟 (2) 的約束條件中挑選一個包含 x_2 的等式,譬如 4x_1-6x_2+x_3=5,可知 x_2=\frac{1}{6}(4x_1+x_3-5)。將上式代入目標函數與其他約束等式,化簡後即得等價的標準型:

\begin{array}{lrl}  \min& -\frac{5}{3}x_1+\frac{1}{3}x_3-\frac{5}{3} & \\  \mathrm{subject~to}&\frac{11}{3}x_1-\frac{1}{3}x_3-x_4&=\frac{16}{3}\\  &x_1,x_3,x_4&\ge 0.  \end{array}

目標函數引入的常數 -5/3 並不會影響結果,所以大可直接將它刪除。

 
在正式展開線性規劃的最佳解探索之旅前,我們將從代數與幾何兩種角度,運用線性代數概念與工具來界定最佳解所在的集合。這是下一篇要討論的主題。

 
註解

[1] 丹齊格 (George Dantzig) 於1947年提出第一個有效的線性規劃算法──單形法 (simplex method,或稱單純形法),被稱為線性規劃之父。他在1990年寫了一篇回憶文〈飲食問題〉The Diet Problem,裡面談到1930至1940年代圍繞在飲食問題的線性規劃發展歷程。故事背景是美國軍方打算用最少的花費來滿足大兵們的營養需求。斯蒂格勒 (George Stigler,1982年獲得諾貝爾經濟學獎) 是早期參與這個計畫的研究者之一,他提出了一個包含9個方程式,77個未知數的模型。由於當時還不存在系統化的解法,他發明一個巧妙的助探法 (heuristic),推測每人每年的飲食成本只要$39.93美元 (按1939年的物價)。1947年秋天,任職美國國家標準局 (National Bureau of Standards) 的拉德曼 (Jack Laderman) 嘗試用最新發展出的單形法來解決斯蒂格勒的問題。這是線性規劃領域第一次出現的「大型」計算工程。在那個沒有電腦的時代,拉德曼動用九名員工,倚靠手動計算器,大約花了120人工作日,算出最佳解是$39.69。斯蒂格勒推測的答案與最佳解僅相差$0.24。丹齊格評論:「不賴 (not bad)!」不過我不很確定他說的是自己提出的單形法不賴,還是斯蒂格勒的助探法不賴。

繼續閱讀:
Advertisements
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , , 。將永久鏈結加入書籤。

1 則回應給 線性規劃 (一):標準型問題

  1. ccjou 說道:

    在討論可行解集合(滿足所有約束等式與不等式的解)的性質與單形法之前,我們最好先瞭解一些線性代數很少討論的向量空間幾何知識,如凸組合、超平面和多胞形(polytope)。所以等我寫完這些介紹文之後才會有線性規劃(二)。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s