iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 9
2
AI & Data

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

Day 9 : 線性規劃問題(linear programming problem)

當一個問題被視為凸性規劃問題,那其解就是全域最佳解,因此我們會希望手邊的問題是凸性規劃問題。今天要介紹的線性規劃問題就是凸性規劃問題的一種。

線性規劃問題是指,目標函數與限制條件都是線性的。線性規劃在理論上趨於成熟,尤其是可以將其轉換成矩陣型式,利用電腦來計算求解,因而實用性日益廣泛與深入。

基本概念

  1. 假如一個線性規劃問題存在最佳解,則該最佳解為全域最佳解。
  2. 呈1,線性規劃問題的最佳解必將出現在feasible set的邊界上或邊界的頂點上。

範例

(請先忽略原始問題如何轉換成標準LP型式,將焦點著重在解的特性,後續會再講解如何轉換)
原始LP問題:
https://chart.googleapis.com/chart?cht=tx&chl=min%20f%20%3D%20-400x_1%20-%20600x_2
s.t.
https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%2B%20x_2%20%5Cle%2016
https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B28%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B14%7Dx_2%20%5Cle%201
https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B14%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B24%7Dx_2%20%5Cle%2011
https://chart.googleapis.com/chart?cht=tx&chl=x_1%2C%20x_2%20%5Cge%200
轉成標準型式
https://chart.googleapis.com/chart?cht=tx&chl=min%20f%20%3D%20-400x_1%20-%20600x_2
s.t.
https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%2B%20x_2%20%2B%20x_3%20%3D%2016
https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B28%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B14%7Dx_2%20%2B%20x_4%20%3D%201
https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B14%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B24%7Dx_2%20%2B%20x_5%20%3D%2011
https://chart.googleapis.com/chart?cht=tx&chl=x_i%20%5Cge%200%2C%20i%3D1%2C%20%5Cdots%2C%205
解聯立,並將https://chart.googleapis.com/chart?cht=tx&chl=x_1%2C%20x_2視為獨立變數,得通解為,
https://chart.googleapis.com/chart?cht=tx&chl=x_3%20%3D%2016%20-%20x_1%20-%20x_2
https://chart.googleapis.com/chart?cht=tx&chl=x_4%20%3D%201%20-%20%5Cfrac%7B1%7D%7B28%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B14%7Dx_2
https://chart.googleapis.com/chart?cht=tx&chl=x_5%20%3D%201%20-%20%5Cfrac%7B1%7D%7B14%7Dx_1%20%2B%20%5Cfrac%7B1%7D%7B24%7Dx_2
對LP問題的處理採用特殊的程序,即令https://chart.googleapis.com/chart?cht=tx&chl=p%20%3D%20n%20-%20m個變數為0,則可由現有的m個方程式解n個變數。由此程序所得之解稱為,基本解。

以本題為例,
https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%205, https://chart.googleapis.com/chart?cht=tx&chl=m%20%3D%203%20%5CRightarrow%20p%20%3D%205%20-%203%20%3D%202
若令https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%3D%20x_2%20%3D%200%20%5CRightarrow%20x_3%20%3D%2016, https://chart.googleapis.com/chart?cht=tx&chl=x_4%20%3D%201, https://chart.googleapis.com/chart?cht=tx&chl=x_5%20%3D%201%20%5Crightarrow%20A
若令https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%3D%20x_4%20%3D%200%20%5CRightarrow%20x_2%20%3D%2014, https://chart.googleapis.com/chart?cht=tx&chl=x_3%20%3D%202, https://chart.googleapis.com/chart?cht=tx&chl=x_5%20%3D%20%5Cfrac%7B5%7D%7B15%7D%20%5Crightarrow%20E
若令https://chart.googleapis.com/chart?cht=tx&chl=x_1%20%3D%20x_3%20%3D%200%20%5CRightarrow%20x_2%20%3D%2016, https://chart.googleapis.com/chart?cht=tx&chl=x_4%20%3D%20%5Cfrac%7B-2%7D%7B7%7D, https://chart.googleapis.com/chart?cht=tx&chl=x_5%20%3D%20%5Cfrac%7B1%7D%7B3%7D%20%5Crightarrow%20F(infeasible)
https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow基本解的數目為C5取2 = 10組
https://ithelp.ithome.com.tw/upload/images/20190910/20119600H6uAF0PKV4.jpg
凸多邊形ABCDE之邊界及其內部為可行解區域,D為最佳解。
10組基本解對應到,
1. A,B,C,D,E之五個頂點為基本可行解
2. F,G,H,I,J之五個點為基本不可行解

參考文獻

標準型問題
端點與基解
最佳基可行解定理


上一篇
Day 8 : 全域最佳化 - 凸函數
下一篇
Day 10 : 線性規劃問題(續)
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言