什麼是線性規劃呢

若目標函數為線性函數

且可行解區域的邊界為直線

解決這類問題的方法

稱為線性規劃

接著我們就試著利用線性規劃

來解決在現實生活中

來解決在現實生活中

可能遇到的問題吧

某汽車公司有A B兩家裝配廠

組裝大小兩型的汽車

若A廠每小時可組裝

9輛大型車與3輛小型車

B廠每小時可組裝

4輛大型車與8輛小型車

今公司接到客戶訂單

欲訂購120輛大型車

與120輛小型車

試問這兩家裝配廠

各工作幾小時

才能使所費總工作時數最少

設A裝配廠工作x小時

B裝配廠工作y小時

因為A裝配廠每小時

可以組裝9輛大型車

工作x小時可組裝9x輛大型車

B裝配廠每小時

可以組裝4輛大型車

工作y小時可以組裝4y輛大型車

大型車共可組裝

9x加4y輛

要大於等於120

才能滿足客戶的需求

因為A裝配廠每小時

可以組裝3輛小型車

工作x小時可以組裝3x輛小型車

B裝配廠每小時

可以組裝8輛小型車

工作y小時可以組裝8y輛小型車

小型車共可組裝

3x加8y輛

要大於等於120

才能滿足客戶的需求

因為x跟y代表時間

所以必須大於等於0

而我們想求總工作時數P

等於x加y的最小值

如此一來就將題目化成求

二元一次聯立不等式組的

可行解區域中

目標函數的最小值的問題

接著就可以利用前兩支影片學過的

平行線法或頂點法來解題

首先畫出二元一次聯立不等式組的

可行解區域

然後畫出平行直線系x加y等於k

因為x的係數1大於0

且y的係數1大於0

所以越往左下方平移k值越小

從圖中可以觀察出

和可行解區域相交的直線當中

通過點

將代入P可得

P等於8加12等於20

因此最小值為20

由此可知

當A裝配廠工作8小時

B裝配廠工作12小時

有最少總工作時數20小時

某連鎖麵包企業有A B兩座

製作麵包的烘焙廠

及甲 乙兩間店面

現知A烘焙廠有500個麵包

B烘焙廠有460個麵包

今天甲 乙兩店面

分別需要麵包360個及400個

而運費如右表

若現在從A烘焙廠運x個到甲店面

運y個到乙店面

可使所需運費最少

求x y的值及此時所需運費

由題目可知從A烘焙廠運x個到甲店面

運y個到乙店面

因為甲店面需要360個麵包

所以必須再從B烘焙廠

運360減x個到甲店面

因為乙店面需要400個麵包

所以必須再從B烘焙廠

運400減y個麵包到乙店面

A烘焙廠須運送出x加y個麵包

而A烘焙廠有500個麵包

所以x加y小於等於500

B烘焙廠須運送出

括號360減x加上括號400減y個麵包

而B烘焙廠有460個麵包

所以括號360減x加上括號400減y

小於等於460

麵包的個數必須是大於等於0的整數

所以x大於等於0

y大於等於0

360減x大於等於0

400減y大於等於0

x y為整數

求運費P等於5x加4y

加上10乘以括號360減x

加上8乘以括號400減y

等於-5x減4y加6800的最小值

將二元一次不等式化簡後

可以得到x加y小於等於500

x加y大於等於300

x大於等於0

y大於等於0

x小於等於360

y小於等於400

x y為整數

接著畫出聯立不等式組的可行解區域

發現可行解區域是一個封閉的多邊形

可得頂點為

因此可以利用頂點法來求其解

將頂點代入P

分別求出其值

如表格所示

由表格可以得知

當x等於360 y等於140時

有最少運費4440元

目標函數為線性函數

且可行解區域的邊界為直線

解決這類問題的方法稱為線性規劃

利用線性規劃解題的步驟

根據題意設未知數

根據題意將條件限制

列出二元一次不等式

若條件有x大於等於0

y大於等於0時

須列出x大於等於0

y大於等於0

繪製可行解區域

使用頂點法或平行線法求解