線性規(guī)劃-基本概念

線性規(guī)劃--基本概念2-2學(xué)習(xí)目標(biāo)在讀完本章后，你應(yīng)該能夠：1. 解釋什么是「線性規(guī)劃」。2. 了解建構(gòu)試算表模式前所必須找出的三項(xiàng)核心問題。3. 指出及確認(rèn)線性規(guī)劃試算表模式中四種儲存格的目的。4. 根據(jù)問題描述于試算表中建構(gòu)線性規(guī)劃模式。5. 在試算表中表示線性規(guī)劃模型的代數(shù)式。6. 運(yùn)用圖解法求解雙變數(shù)線性規(guī)劃問題。7. 使用Excel求解線性規(guī)劃試算表模式。2-3偉伯玻璃公司產(chǎn)品組合問題偉伯公司發(fā)展以下的新產(chǎn)品：鋁框8呎玻璃門4呎6呎可雙面懸掛的木框窗戶公司擁有三間工廠：工廠1：生產(chǎn)鋁框及金屬器件工廠2：生產(chǎn)木框工廠3：生產(chǎn)玻璃并進(jìn)行門及窗戶的組裝問題：公司是否應(yīng)該從事新產(chǎn)品的生產(chǎn)？如果是的話，最佳的產(chǎn)品組合為何？2-4發(fā)展試算表模式步驟一：資料儲存格在試算表上輸入問題所有相關(guān)的資料使用一致性的欄與列儲存方式利用不同顏色來顯示這些「資料儲存格」（例如：淺色）是不錯的方法2-5發(fā)展試算表模式（續(xù)）步驟二：變動儲存格在試算表上替每個需要做的決策設(shè)置一儲存格若是你沒有特殊的起始解（initialvalues）考量，只要輸入0即可利用顏色與框線等來顯示這些「變動儲存格」（例如：淺色并加框線）是不錯的方法2-6發(fā)展試算表模式（續(xù)）步驟三：目標(biāo)儲存格發(fā)展一個方程式來定義模式的目標(biāo)基本上此方程式涉及資料儲存格與變動儲存格以便決定感興趣的數(shù)量（例如：總利潤或總成本）利用顏色來顯示這個儲存格（例如：深色并加粗框線）是不錯的方法2-7發(fā)展試算表模式（續(xù)）步驟四：限制式對于受限制的資源，在試算表某一儲存格中計算該資源使用量（輸出儲存格）在三個連續(xù)的儲存格中定義限制式。例如：若數(shù)量A<=數(shù)量B，將此三項(xiàng)（數(shù)量A、

<=、數(shù)量B）置于相鄰的儲存格2-8一組試驗(yàn)解偉伯問題試算表中將一組試驗(yàn)解（4扇門及3個窗戶）輸入于變動儲存格2-9偉伯玻璃公司之代數(shù)模式令 D=玻璃門的生產(chǎn)數(shù)量

W

=木框窗戶的生產(chǎn)數(shù)量最大化P=$300D+$500W受限于

D≤4

2W≤12

3D+2W≤

18且

D≥

0,W≥

02-10產(chǎn)品組合示意圖2-11滿足限制式：D

≥

0及W≥0之區(qū)域示意圖木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-12滿足D

≤4之非負(fù)解木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-13滿足2W

≤

12之非負(fù)解木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-14限制式3D+2W≤

18之邊界線木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-15改變右側(cè)值將產(chǎn)生一些平行的限制式邊界線木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-16滿足3D

+2W≤

18之非負(fù)解木框窗戶的產(chǎn)能玻璃門的產(chǎn)能2-17可行解區(qū)域之示意圖2-18目標(biāo)函數(shù)（P

=1,500）木框窗戶的生產(chǎn)率玻璃門的生產(chǎn)率可行區(qū)域2-19尋找最佳解2-20圖解法摘要畫出每個函數(shù)限制式的限制邊界線，利用原點(diǎn)（或其他不在線上的點(diǎn)）決定線的哪一邊才能滿足限制式。確定是否同時滿足所有的限制式，找出可行區(qū)域。求出目標(biāo)函數(shù)線的斜率，所有的目標(biāo)函數(shù)線的斜率要相同。以這個斜率，在可行區(qū)域內(nèi)往可改善目標(biāo)值的方向移動線段，直到此線段與可行區(qū)域只交于一點(diǎn)即停止移動，包含這條線段的直線即是最佳目標(biāo)函數(shù)線。在最佳目標(biāo)函數(shù)線上的可行點(diǎn)即為最佳解。2-21辨識目標(biāo)儲存格與變動儲存格從「工具」選單選擇「規(guī)劃求解」在「設(shè)定目標(biāo)儲存格」視窗中，選擇你想要最佳化的儲存格依據(jù)你是否要最大化或最小化目標(biāo)儲存格，選擇「最大值」或「最小值」在「變動儲存格」視窗中輸入所有變動儲存格2-22新增限制式若要輸入限制式，選擇限制式視窗右側(cè)的「新增」按鈕在「新增限制式」對話視窗中輸入限制式相關(guān)資料2-23完整的「規(guī)劃求解」對話視窗2-24一些重要的選項(xiàng)按「選項(xiàng)」鈕，并且選取「采用線性模式」以及「采用非負(fù)值」二個選項(xiàng)「采用線性模式」告訴規(guī)劃求解這是一個線性規(guī)劃模式「采用非負(fù)值」會將非負(fù)限制式加到所有變動儲存格2-25「規(guī)劃求解結(jié)果」對話視窗2-26最佳解2-27Profit&Gambit公司管理階層決定推動一個新的廣告活動，并把目標(biāo)鎖定在以下三種主要產(chǎn)品上：噴霧去漬劑液態(tài)洗衣精洗衣粉這個活動將運(yùn)用電視及平面媒體作廣告最根本的目標(biāo)是希望增加這些產(chǎn)品的銷售量管理階層為該廣告活動訂定以下目標(biāo)：去漬劑的銷售額至少要增加3%。洗衣精的銷售額至少要增加18%。洗衣粉的銷售額至少要增加4%。問題：目標(biāo)是要決定于各種媒體應(yīng)該廣告多少數(shù)量，在達(dá)到銷售目標(biāo)的前提下，使總成本最小化？2-28Profit&Gambit公司試算表模式2-29Profit&Gambit公司問題之代數(shù)模式令 TV=電視廣告的單位數(shù)量 PM=平面媒體廣告的單位數(shù)量最小化成本=TV+2PM(百萬美元)受限于去潰劑增加的銷售量： PM≥3

液狀洗衣精增加的銷售量：3TV+2PM≥

18洗衣粉增加的銷售量：–TV+4PM≥

4 TV

≥

0,PM

≥

02-30運(yùn)用圖解法電視廣告的單位數(shù)量平面媒體廣告的單位數(shù)量可行區(qū)域2-31最佳解電視廣告的單位數(shù)量平面媒體廣告的單位數(shù)量可行區(qū)域最佳解2-32圖解法摘要畫出每個函數(shù)限制式的限制邊界線，利用原點(diǎn)（或其他不在線上的點(diǎn)）決定線的哪一邊才能滿足限制式。確定是否同時滿足所有的限制式，找出可行區(qū)域。求出目標(biāo)函數(shù)線的斜率，所有的目標(biāo)函數(shù)線的斜率要相同。以這個斜率，在可行區(qū)域內(nèi)往可改善目標(biāo)值的方向移動線段，直到此線段與可行區(qū)域只交于一點(diǎn)即停止移動，包含這條線段的直線即是最佳目標(biāo)函數(shù)線。在最佳目標(biāo)函數(shù)線上的可行點(diǎn)即為最佳解。2-33一個生產(chǎn)問題原物料每周供給量：8個小木塊6個大木塊產(chǎn)品：桌子利潤=$20/桌子椅子利潤=$15/椅子2-34線性規(guī)劃線性規(guī)劃使用數(shù)學(xué)模式來找出對于各項(xiàng)活動最佳的資源配置以使得利潤最大或是成本最小令 T=桌子生產(chǎn)量

C=椅子生產(chǎn)量

最大化利潤

=($20)T+($15)C

受限于

2T

+C≤6大木塊

2T+2C≤

8小木塊

且

T≥

0,C≥

02-35圖形表示2-36線性規(guī)劃模式的組成元素資料儲存格變動儲存格（決策變數(shù)）目標(biāo)儲存格（目標(biāo)函數(shù)）限制式2-37線性規(guī)劃的四項(xiàng)假設(shè)線性（Linearity）不可分割性（Divisibility）確定性（Certainty）非負(fù)值（Nonnegativity）2-38何種情況下試算表模式為線性？所有方程式（輸出儲存格）必須具有以下形式：

=ax+by+cz+…

其中

a,b,c

為常數(shù)（資料儲存格）且

x,y,z

為變動儲存格若C1:C6為變動儲存格，

D1:D6為資料儲存格

以下何者可能為LP模式的一部分？SUMPRODUCT(D1:D6,C1:C6)SUM(C1:C6)C1*SUM(C4:C6)SUMPRODUCT(C1:C3,C4:C6)IF(C1>3,2*C3+C4,3*C3+C5)IF(D1>3,C1,C2)MIN(C1,C2)MIN(D1,D2)*C1ROUND(C1)2-39為何使用線性規(guī)劃？線性規(guī)劃模式較易于（較有效率）求解最好的（最佳的）解確保可以找到（若存在的話）可以產(chǎn)生有用的敏感度分析相關(guān)資訊許多問題本質(zhì)上是線性的2-40發(fā)展試算表模式步驟一：資料儲存格在試算表上輸入問題所有相關(guān)的資料使用一致性的欄與列儲存方式利用不同顏色來顯示這些「資料儲存格」（例如：淺藍(lán)色）是不錯的方法2-41發(fā)展試算表模式(續(xù))步驟二：變動儲存格在試算表上替每個需要做的決策設(shè)置一儲存格若是你沒有特殊的起始解（initialvalues）考量，只要輸入0即可利用顏色與框線等來顯示這些「變動儲存格」（例如：黃色并加框線）是不錯的方法2-42發(fā)展試算表模式（續(xù)）步驟三：目標(biāo)儲存格發(fā)展一個方程式來定義模式的目標(biāo)基本上此方程式涉及資料儲存格與變動儲存格以便決定感興趣的數(shù)量（例如：總利潤或總成本）利用顏色來顯示這個儲存格（例如：橙色并加粗框線）是不錯的方法2-43發(fā)展試算表模式（續(xù)）步驟四：限制式對于受限制的資源，在試算表某一儲存格中計算該資源使用量（輸出儲存格）在三個連續(xù)的儲存格中定義限制式。例如：若數(shù)量A<=數(shù)量B，將此三項(xiàng)（數(shù)量A、

<=、數(shù)量B）置于相鄰的儲存格2-44定義目標(biāo)儲存格從「工具」選單選擇「規(guī)劃求解」在「設(shè)定目標(biāo)儲存格」視窗中，選擇你想要最佳化的儲存格依據(jù)你是否要最大化或最小化目標(biāo)儲存格，選擇「最大值」或「最小值」2-45辨識變動儲存格在「變動儲存格」視窗中輸入所有變動儲存格你可以將游標(biāo)點(diǎn)一下儲存格位址或是直接輸入位址若有多組變動儲存格，以逗號將其隔開2-46新增限制式若要輸入限制式，選擇限制式視窗右側(cè)的「新增」按鈕在「新增限制式」對話視窗中輸入限制式相關(guān)資料2-47一些重要的選項(xiàng)按「選項(xiàng)」鈕，并且選取「采用線性模式」以及「采用非負(fù)值」二個選項(xiàng)「采用線性模式」告訴Solver這是一個線性規(guī)劃模式「采用非負(fù)值」會將非負(fù)限制式加到所有變動儲存格2-48解在按下「求解」后，你將會看到以下四則訊息其中之一：「規(guī)劃求解找到一解，可滿足所有的限制式及最佳狀況」「規(guī)劃求解找不到合適的解」「儲存格所設(shè)的值并不收斂」「線性模式的假設(shè)并不成立」2-49以圖解法求解線性規(guī)劃問題將問題建構(gòu)成為一個線性規(guī)劃模式畫出限制式找出可行解區(qū)域畫一條與目標(biāo)函數(shù)平行的直線（Z

=a）找出最佳解2-50范例#1最大化Z=3x1+5x2

受限于

x1

≤4 2x2≤

12

3x1+2x2≤

18

且

x1≥

0,x2≥

02-51范例#2最小化Z=15x1+20x2

受限于

x1

+2x2≥10 2x1–3x2≤

6

x1+x2≥

6

且

x1≥

0,x2≥

02-52范例#3最大化Z=x1+x2

受限于

x1

+2x2=8

x1–x2≤

0

且

x1≥

0,x2≥

02-53線性規(guī)劃解之特性最佳解必定落在可行解區(qū)域的邊緣線性規(guī)劃有四種可能的結(jié)果：找到唯一最佳解存在有無窮多組最佳解不存在可行解有無窮大（或無窮小的）目標(biāo)函數(shù)值（沒有最佳解）若一個

LP模式有最佳解，則此解必定落在端點(diǎn)（cornerpoint）上若一個

LP模式有許多組最佳解，則其中至少有二組解會落在端點(diǎn)上2-54范例#4（多組最佳解）最小化Z=6x1+4x2

受限于

x1

≤4

2x2

≤12 3x1+2x2≤18

且

x1≥

0,x2≥

02-55范例#5（無可行解）最大化Z=3x1+5x2

受限于

x1

≥5

x2≥4 3x1+2x2≤

18

且