iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
0
AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列 第 10

Day 10 : 線性規劃問題(續)

接續昨天的內容,我們談到了線性規劃問題是一種凸性規劃問題,而被歸類為凸性規劃問題的好處是,區域最佳解為全域最佳解,且其解必出現在可行解區域的邊界上或頂點。但是,對於線性規劃問題的定義及一些專有名詞,尚未交代,今天就來將這部分補齊。

LP問題的定義

  1. 求函數最小值
  2. 所有限制條件均為等式限制
  3. 所有設計變數皆https://chart.googleapis.com/chart?cht=tx&chl=%5Cge%200(非負數)

線性限制條件的型式

三種可能的型式
https://chart.googleapis.com/chart?cht=tx&chl=a_%7Bi1%7Dy_1%20%2B%20a_%7Bi2%7Dy_2%20%2B%20%5Cdots%20%2B%20a_%7Bik%7Dy_k%20%5Cle%20b_i
https://chart.googleapis.com/chart?cht=tx&chl=a_%7Bi1%7Dy_1%20%2B%20a_%7Bi2%7Dy_2%20%2B%20%5Cdots%20%2B%20a_%7Bik%7Dy_k%20%3D%20b_i
https://chart.googleapis.com/chart?cht=tx&chl=a_%7Bi1%7Dy_1%20%2B%20a_%7Bi2%7Dy_2%20%2B%20%5Cdots%20%2B%20a_%7Bik%7Dy_k%20%5Cge%20b_i
其中https://chart.googleapis.com/chart?cht=tx&chl=b_i稱為resource limits, https://chart.googleapis.com/chart?cht=tx&chl=b_i%20%5Cge%200(非負數)
型式轉換

  1. 對於https://chart.googleapis.com/chart?cht=tx&chl=%5Cle的限制引入slack variable https://chart.googleapis.com/chart?cht=tx&chl=S_i, https://chart.googleapis.com/chart?cht=tx&chl=S_i%20%5Cge%200
    ex: https://chart.googleapis.com/chart?cht=tx&chl=3y_1%20-%202y_2%20%5Cle%205%20%5CRightarrow%203y_1%20-%202y_2%20%2B%20S%20%3D%205
  2. 對於https://chart.googleapis.com/chart?cht=tx&chl=%5Cge的限制引入surplus variable https://chart.googleapis.com/chart?cht=tx&chl=S_i, https://chart.googleapis.com/chart?cht=tx&chl=S_i%20%5Cge%200
    ex: https://chart.googleapis.com/chart?cht=tx&chl=y_1%20-%203y_2%20%5Cge%202%20%5CRightarrow%20y_1%20-%203y_2%20-%20S%20%3D%202

Unrestricted variable

假如一設計變數https://chart.googleapis.com/chart?cht=tx&chl=y_i為unrestricted in sign或free in sign,意指https://chart.googleapis.com/chart?cht=tx&chl=S_i, https://chart.googleapis.com/chart?cht=tx&chl=S_i%20%5Cge%200可為任意變數。此時令https://chart.googleapis.com/chart?cht=tx&chl=y_i%20%3D%20%7By_i%7D%5E%7B%2B%7D%20-%20%7By_i%7D%5E%7B-%7D,其中 https://chart.googleapis.com/chart?cht=tx&chl=y_i%5E%7B%2B%7D%20%5Cge%200https://chart.googleapis.com/chart?cht=tx&chl=y_i%5E%7B-%7D%20%5Cge%200皆為新增加的變數。
https://chart.googleapis.com/chart?cht=tx&chl=y_i%5E%7B%2B%7D%20%3E%20y_i%5E%7B-%7D%20%5CRightarrow%20y_i%20%3E%200
https://chart.googleapis.com/chart?cht=tx&chl=y_i%5E%7B%2B%7D%20%3C%20y_i%5E%7B-%7D%20%5CRightarrow%20y_i%20%3C%200
https://chart.googleapis.com/chart?cht=tx&chl=y_i%5E%7B%2B%7D%20%3D%20y_i%5E%7B-%7D%20%5CRightarrow%20y_i%20%3D%200

LP標準化型式

根據周志成老師的說法,我們之所以將問題寫成標準型,主要的原因是為了執行消去法以化簡線性方程組 (消去法不適用於線性不等式)。
min https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X)%20%3D%20c_1x1%20%2B%20c_2x_2%20%2B%20%5Cdots%20%2B%20c_nx_n
s.t.
https://chart.googleapis.com/chart?cht=tx&chl=a_%7B11%7Dx_1%20%2B%20a_%7B12%7Dx_2%20%2B%20%5Cdots%20%2B%20a_%7B1n%7Dx_n%20%3D%20b_1
https://chart.googleapis.com/chart?cht=tx&chl=a_%7B21%7Dx_1%20%2B%20a_%7B22%7Dx_2%20%2B%20%5Cdots%20%2B%20a_%7B2n%7Dx_n%20%3D%20b_2
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdots
https://chart.googleapis.com/chart?cht=tx&chl=a_%7Bm1%7Dx_1%20%2B%20a_%7Bm2%7Dx_2%20%2B%20%5Cdots%20%2B%20a_%7Bmn%7Dx_n%20%3D%20b_m
其中,https://chart.googleapis.com/chart?cht=tx&chl=b_i%20%5Cge%200, https://chart.googleapis.com/chart?cht=tx&chl=i%3D1%2C%20%5Cdots%20%2C%20m
https://chart.googleapis.com/chart?cht=tx&chl=x_j%20%5Cge%200, https://chart.googleapis.com/chart?cht=tx&chl=j%3D1%2C%20%5Cdots%20%2C%20n, https://chart.googleapis.com/chart?cht=tx&chl=n%20%3E%20m
以向量與矩陣型式表示,
min https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X)%20%3D%20%5Cbar%20C%5E%7BT%7D%5Cbar%20X
s.t.
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A_%7Bm*n%7D%20%5Cbar%20X_%7Bn*1%7D%20%3D%20%5Cbar%20b_%7Bm*1%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20b%20%5Cge%200, https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%20%5Cge%200, https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%20%3D%20%5Ba_%7Bij%7D%5D_%7Bm*n%7D

範例

將一般LP問題轉換成標準型式
max https://chart.googleapis.com/chart?cht=tx&chl=Z%20%3D%202y_1%20%2B%205y_2
s.t.
https://chart.googleapis.com/chart?cht=tx&chl=3y_1%20%2B%202y_2%20%5Cle%2012
https://chart.googleapis.com/chart?cht=tx&chl=2y_1%20%2B%203y_2%20%5Cge%206
https://chart.googleapis.com/chart?cht=tx&chl=y_1%20%3E%200, https://chart.googleapis.com/chart?cht=tx&chl=y_2unrestricted variable

1.拆解unrestricted variable(亦稱為自由變數),若變數https://chart.googleapis.com/chart?cht=tx&chl=y_2無任何限制,則為unrestricted variable
https://ithelp.ithome.com.tw/upload/images/20190911/20119600AcJB6hpAsz.jpg
2.使其滿足定義
https://ithelp.ithome.com.tw/upload/images/20190911/20119600EUwMMz1Gsh.jpg
3.以向量與矩陣表示
https://ithelp.ithome.com.tw/upload/images/20190911/20119600VQ1TPxpBwm.jpg

參考文獻

單形法
two phase simplex method


上一篇
Day 9 : 線性規劃問題(linear programming problem)
下一篇
Day 11 : 單形法(simplex method)的概念與解題步驟
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言