iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 11
0
AI & Data

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

Day 11 : 單形法(simplex method)的概念與解題步驟

單形法是Danzig教授在二次大戰時發展出來,基本上是以LP問題的幾何特性,配合聯立方程組與高斯喬登消去法,可以求出LP的最佳解。

定理

  • 對任一LP問題,其可行解所成之集合為凸集合,該凸集合之頂點對應到基本可行解
  • 令大小為mxn的係數矩陣https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A具有全列數秩(full row rank),即https://chart.googleapis.com/chart?cht=tx&chl=rank(%5Cbar%20A)%20%3D%20m,則
  1. 若存在一個可行解,則存在一個基本可行解
  2. 若存在一個最佳可行解,則存在一個最佳基本可行解

在求解 LP 時不必把全部的可行端點找出來,只要搜尋到下一個端點比目前的端點好,持續搜尋就保證可以找到整體最佳解,而不會只找到局部最佳解。

正準型式(Cononical form)

求解https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%20%5Cbar%20X%20%3D%20%5Cbar%20b之前,先將其整理為正準型式,如下:
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20I_%7B(m)%7D%20%5Cbar%20X_%7B(m)%7D%20%2B%20%5Cbar%20Q%20%5Cbar%20X_%7B(n-m)%7D%20%3D%20%5Cbar%20b or https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X_%7B(m)%7D%20%20%2B%20%5Cbar%20Q%20%5Cbar%20X_%7B(n-m)%7D%20%3D%20%5Cbar%20b
其中,https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20I_%7B(m)%7D為mxm之單位矩陣
https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20可得https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%20%20%5Cbar%20X%20%3D%20%5Cbar%20b%20之通解為https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X_%7B(m)%7D%20%3D%20%5Cbar%20b%20-%20%5Cbar%20Q%20%5Cbar%20X_%7B(n-m)%7D
上式若設定非基變數https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X_%7B(n-m)%7D%20%3D%20%5Cbar%200(零向量) https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow 可得基解為https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X_%7B(m)%7D%20%3D%20%5Cbar%20b
如右側之https://chart.googleapis.com/chart?cht=tx&chl=b_i%20%5Cge%200,則該基解即為基本可行解。

對於"基"的理解,可以把它當作是線性代數中的基底,而基變數就是基所對應的變數。

Pivot step

將基變數與非基變數互相交換的過程,稱為Pivot step。
Pivot column https://chart.googleapis.com/chart?cht=tx&chl=%5Crightarrow Pivot row https://chart.googleapis.com/chart?cht=tx&chl=%5Crightarrow Pivot element

範例

上述講了一堆,我們還是直接從範例來解釋求解過程。
https://ithelp.ithome.com.tw/upload/images/20190913/20119600kDqlq4tsU1.jpg
https://ithelp.ithome.com.tw/upload/images/20190913/20119600TO1SfkiTg7.jpg
(i) simplex method的基本要求之一就是,將目標函數表示成非基變數的函數,而變數之前的係數稱為reduced cost coefficients,以符號https://chart.googleapis.com/chart?cht=tx&chl=C_%7Bj%7D'表式。以本例而言,https://chart.googleapis.com/chart?cht=tx&chl=C_%7B1%7D'%20%3D%20-2, https://chart.googleapis.com/chart?cht=tx&chl=C_%7B2%7D'%20%3D%20-1
(ii) simplex method的啟動需要一組基可行解,以本例而言,非基變數:https://chart.googleapis.com/chart?cht=tx&chl=x_%7B1%7D%20%3D%200, https://chart.googleapis.com/chart?cht=tx&chl=x_%7B2%7D%20%3D%200相當於圖解法中的A點(在可行區域內),基變數:https://chart.googleapis.com/chart?cht=tx&chl=x_%7B3%7D%20%3D%2012, https://chart.googleapis.com/chart?cht=tx&chl=x_%7B4%7D%20%3D%204, https://chart.googleapis.com/chart?cht=tx&chl=x_%7B5%7D%20%3D%204,目標函數值: https://chart.googleapis.com/chart?cht=tx&chl=f%20%3D%200
https://ithelp.ithome.com.tw/upload/images/20190913/20119600Pk1ZFmIGfq.jpg
https://ithelp.ithome.com.tw/upload/images/20190913/201196002SiuWm1mXM.jpg
https://ithelp.ithome.com.tw/upload/images/20190913/20119600xkCNorpgKR.jpg
(iii) 最佳解檢驗,如對應非基變數之https://chart.googleapis.com/chart?cht=tx&chl=C_%7Bj%7D'%20%5Cge%200,且對應基變數之https://chart.googleapis.com/chart?cht=tx&chl=C_%7Bj%7D'%20%3D%200,則最佳解以求得。
https://ithelp.ithome.com.tw/upload/images/20190913/20119600eXgVUEcS4Z.jpg
經由基本列運算設法將Pivot element由2變成1,同行元素(https://chart.googleapis.com/chart?cht=tx&chl=a_%7B11%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=a_%7B31%7D)變為0,同列元素跟著改變。另外,將https://chart.googleapis.com/chart?cht=tx&chl=C_%7B1%7D'%20%3D%20-2變成https://chart.googleapis.com/chart?cht=tx&chl=C_%7B1%7D'%20%3D%200,因為https://chart.googleapis.com/chart?cht=tx&chl=x_1已變成基變數。
上表令https://chart.googleapis.com/chart?cht=tx&chl=x_2%20%3D%20x_4%20%3D%200,得基解https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%3D%202, https://chart.googleapis.com/chart?cht=tx&chl=x_3%20%3D%204, https://chart.googleapis.com/chart?cht=tx&chl=x_5%20%3D%202
其中(https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%3D%202, https://chart.googleapis.com/chart?cht=tx&chl=x_2%20%3D%200)對應到D點為最佳基本可行解

在進行單形法求解之前需確認,限制條件是否都滿足,https://chart.googleapis.com/chart?cht=tx&chl=Ax%20%5Cle%20b 的型式。若不滿足(如https://chart.googleapis.com/chart?cht=tx&chl=Ax%20%3D%20b or https://chart.googleapis.com/chart?cht=tx&chl=Ax%20%5Cge%20b),則需用二階段單形法求解。

單型法的迭代步驟

  1. 選擇第一個基
  2. 求出基可行解(頂點)
  3. 帶入目標函數,檢驗是否為最佳解
  4. 變換下一個基,回到步驟2

上一篇
Day 10 : 線性規劃問題(續)
下一篇
Day 12 : 無限制條件之非線性規劃問題
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言