线性与整数规划模式之应用课件

Chapter3線性與整數規劃模式之應用ApplicationsofLinearandIntegerProgrammingModels1Chapter3線性與整數規劃模式之應用13.1LP在企業與政府之逐漸發展(p.140)有許多應用LP與ILP之成功案例四個目標:檢視LP可用之應用領域發展好的模型化技巧使用試算表產生結果說明與分析試算表報告結果成功案例：見(p.140)23.1LP在企業與政府之逐漸發展(p.140)有許成功建立模型之三項因素:熟悉度（Familiarity）簡單化(Simplicity)明確性(Clarity)3.2建立良好線性與整數規劃模式3成功建立模型之三項因素:3.2建立良好線性與整數規劃模式總和變數與限制式(P.142)

Summation

Variables

/Constraints範例生產三種機型電視機型每種機型分別使用2,3,and4磅塑膠可利用塑膠plastic為7000磅.任何機型不超過總產量之40%單位利潤分別為$23,$34,和$45.求生產計畫使得總利潤最大4總和變數與限制式(P.142)

SummationVar求解SolutionMax23X1+34X2+45X3S.T. 2X1+ 3X2+ 4X3

£7000不使用總和變數X1

£.4(X1+X2+X3) X2

£.4(X1+X2+X3)

X3

£.4(X1+X2+X3)

X1,X2,X3

³0使用總和變數X1+X2+X3=X4X1

£.4X4 X2

£.4X4

X3

£.4X4

X1,X2,X3,X4

³0總和變數與限制式

Summation

Variables

/Constraints5求解SolutionMax23X1+34X2+4TVproductionSolver試算表=SUM(B2:D2)總生產量決策變數百分比限制式塑膠限制式6TVproductionSolver試算表=SUM(B£³轉換成下列形式:(數學式子)[關係式](常數)建立線性模型清單

(p.145)A+2BA+2B2A+B+10

-A+B10在形成數學符號之前先以說話形式形成一種關係

(某個式子)[有某種關係](另一個式子或常數)

7£³轉換成下列形式:建立線性模型清單(p.145)A+建立線性模型清單關係式兩邊的單位必須要一致適當使用總和變數確認變數為非負Non-negative整數Integers二元Binary8建立線性模型清單關係式兩邊的單位必須要一致8協助管理者做決策對於資源之使用能有效率應用領域包含:決定生產水準排程輪班加班額外資源之成本效益3.4.線性規劃模式之應用─生產排程模型(ProductionSchedulingModels)9協助管理者做決策對於資源之使用能有效率3.4.線性規劃模式GalaxyIndustries擴張計畫GalaxyIndustries計畫增加產能並試銷兩種新產品Data(見p.149,表3.1)可用塑膠數量3000pounds正常工作時間(Regulartime)40hours.加班時間(Overtime)32hours.加班時間成本每小時比正常工作時間多$18010GalaxyIndustries擴張計畫GalaxyIData-continued兩種新產品:大水槍(BigSquirts)滲透者(Soakers)市場需求:SpaceRays=總產量之50%.其他產品產量<=總產量之40%.最小總產量1000打/每週.GalaxyIndustries擴張計畫兩種舊產品:宇宙光Spacerays射擊手Zappers11Data-continuedGalaxyIndustrData-ContinuedPlasticProductionProductProfit(lbs)

Time(min)SpaceRays$1623Zappers$1514BigSquirts$2035Soakers$2246PlasticProductionProductProfit(lbs)

Time(min)SpaceRays$1623Zappers$1514BigSquirts$2035Soakers$2246管理者希望週淨利潤(NetWeeklyProfit)最大

需決定一週生產排程與加班時數GalaxyIndustries擴張計畫12Data-ContinuedPlasticProduct決策變數(DecisionVariables)(p.150)X1=每週生產SpaceRays打數X2=每週生產Zapper打數X3=每週生產BigSquirts打數X4=每週生產Soakers打數X5=每週排定加班overtime時數GalaxyIndustries擴張計畫–求解過程13決策變數(DecisionVariables)(p.1目標函數(ObjectiveFunction)週淨利潤NetWeeklyProfit=銷售利潤thesaleofproducts–加班成本extracostofovertimeMaximize16X1+15X2+20X3+22X4-180X5GalaxyIndustries擴張計畫–求解過程14Maximize16X1+15X2+20X3+22X4限制式(Constraints)(p.150)

GalaxyIndustries擴張計畫–求解過程15GalaxyIndustries擴張計畫–求解過程15加入總和限制式X6(產品組合限制式之用)X6=每週生產總數(indozens),X6=X1+X2+X3+X4,or

X1+X2+X3+X4-X6=0GalaxyIndustries擴張計畫–求解過程16加入總和限制式X6(產品組合限制式之用)X6=每週生GalaxyIndustries擴張計畫–求解過程17GalaxyIndustries擴張計畫–求解過程17完整數學模式Max16X1+15X2+20X3+22X4–180X5 S.T. 2X1+ 1X2+ 3X3+ 4X4

£ 3000 3X1+ 4X2+ 5X3+ 6X4–

60X5 £

2400 X5

£ 32 1X2

³ 200 X1+ X2+ X3+ X4- - X6 =0

X1 -.5X6 = 0

X2 -.4X6 = 0 X3 -.4X6 =0 X4 -.4X6 = 0 X6 ³ 1000Xjarenon-negativeGalaxyIndustries擴張計畫–求解過程18完整數學模式Max16X1+15X2+20X3+=SUM(B4:E4)PercentageConstraintsSUMPRODUCT($B$4:$F$4,B6,F6)DragtoG7:G10GalaxyIndustries擴張計畫–求解過程19=SUM(B4:E4)PercentageSUMPRODUCGalaxyIndustries擴張計畫–求解過程(p.153~p.154)負值如何解釋?20GalaxyIndustries擴張計畫–求解過程(p3.5整數線性規劃模型之應用(p.179)許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pureinteger(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或1)混合整數線性模型Mixedinteger(MILP)：有些變數非整數或二元值213.5整數線性規劃模型之應用(p.179)許多現實模型使用二元變數

Theuseofbinaryvariablesinconstraints一個變數之決策結果分為“yes”/“no”,“good”/“bad”等.皆為二元分類說明22使用二元變數

Theuseofbinaryvaria範例以二元變數Y1

,Y2,Y3

表示三家工廠的每一家是否要建(Yi=1)或不建(Yi=0)

需求Requirement

二元Binary表示法

至少兩家工廠要被建立 Y1+Y2+Y3

³2

若工廠1要建，則工廠2不能建 Y1+Y2

£1

若工廠1要建，則工廠2也要建 Y1–Y2

£0

一間工廠要建，但不可以兩間工廠同時建 Y1+Y2=1

兩者都要或都不要建 Y1–Y2=0

工廠建設不可超過$17百萬其中個別成本為$5,$8,$10百萬 5Y1+8Y2+10Y3£17 使用二元變數(p.179)23範例使用二元變數(p.179)23範例(條件限制式)

工廠1生產鋼材可以製造兩種產品：產品1需要6磅重鋼材，產品2需要9磅重鋼材

若工廠1被建後，將有2000磅重鋼材可以利用此產品是否生產取決於工廠1是否建立，表示式如下

6X1+9X2

£2000Y1使用二元變數(p.180)若工廠1建立則Y1=1.限制式變為6x1+9X2£2000若工廠1不建則Y1=0限制式變為6x1+9X2£0,且X1=0,X2=024範例(條件限制式)使用二元變數(p.180)若工廠13.5.1人員排程模型(p.180)PersonnelSchedulingModels典型整數規劃問題，為分派人員或機器以達到最低的要求範圍這些模型有多於一期或以上可以利用的資源限制式(i.e.第t期可獲得資源數將影響第t+1期結果)253.5.1人員排程模型(p.180)PersonnSunset海灘市一週七天需要海灘救生員法律規定救生員每週工作5天且有兩天連假.

安全起見，每天平均每8000名遊客需提供一名救生員成本考量起見，雇用救生員人數越少越好Sunset海灘救生員的派任(p.181)

SunsetBeachLifeguardAssignments26Sunset海灘市一週七天需要海灘救生員Sunset海灘救生總結Summary排定連續五天救生員排程雇用救生員人數總數越少越好符合每天最低救生員需求量 Sun. Mon. Tue. Wed. Thr. Fri. Sat. 8 6 5 4 6 7 9Sunset海灘救生員的派任(p.181)

27總結SummarySunset海灘救生員的派任(p.181決策變數DecisionVariablesXi=第“i”排定救生員人數fori=1,2,…,7(i=1isSunday)

目標函數ObjectiveFunction救生員總人數最少限制式

Constraints確定每天有最低需求量的救生員.Sunset海灘救生員的派任(p.181~182)28決策變數DecisionVariablesSunset海

X7Sunset海灘救生員的派任

X6

X5

X4

X3Tue.Wed.Thu.Fri.SatSun.WhoworksonSaturday?WhoworksonFriday?

X2MonX3X4X5X6找出每天工作的救生員，逐步建立限制式29X7Sunset海灘救生員的派任Sunset海灘救生員的派任模式

Min X1+ X2+

X3+ X4+

X5+ X6+X7S.T.

X1+ X4+

X5+ X6+X7 ³ 8(Sun) X1+ X2+ X5+ X6+X7 ³ 6(Mon)

X1+ X2+ X3+ X6+X7 ³ 5(Tue)

X1+ X2+ X3+ X4+ X7 ³ 4(Wed)

X1+ X2+ X3+ X4+ X5 ³ 6(Tur)

X2+ X3+ X4+ X5+ X6

³ 7(Fri) X3+ X4+ X5+ X6+ X7 ³ 9(Sat)

所有變數為非負整數30Sunset海灘救生員的派任模式 Min X1+ X2Sunset海灘救生員的派任31Sunset海灘救生員的派任31Sunset海灘救生員的派任32Sunset海灘救生員的派任32TOTALLIFEGUARDS

最佳解組合LIFEGUARDSDAYPRESENTREQUIREDBEGINSHIFTSUNDAY981MONDAY860TUESDAY651WEDNESDAY541THURSDAY663FRIDAY772SATURDAY99210Note:Analternateoptimalsolutionexists.Sunset海灘救生員的派任33TOTALLIFEGUARDS最佳解組合LIF專案選擇模型由一群二元變數表示”“go/no-go”的決定

模型中包含元件有:預算Budget空間Space優先順序Priorityconditions3.5.2專案選擇模型

ProjectselectionModels34專案選擇模型由一群二元變數表示”“go/no-go”的決定Salem市議會的目標是最大化選民之支持度下合理分派預算資料中包含成本costs,可利用資源,計畫優順序.Salem市議會─專案選擇

SalemCityCouncil–ProjectSelection35Salem市議會的目標是最大化選民之支持度下合理分派預算Sa民調之結果X1X2X3X4X5X6X7X8X9Salem市議會─專案選擇(p.185)36民調之結果X1Salem市議會─專案選擇(p.185)3決策變數:

Xj-一組二元決策變數；ifaprojectjisselected(Xj=1)ornot(Xj=0)forj=1,2,..,9目標函數:

使經費之計畫總點數最大化限制式: Seethemathematicalmodel.Salem市議會─專案選擇(p.185)37決策變數:Salem市議會─專案選擇(p.185)3互斥性：警車與消防車購其一體育與音樂須在電腦設備購買前通過共同必要性：體育與音樂同時恢復或不恢復

最大預算不能超過$900,000

4個警察計畫中至多3個限制式通過

工作創造限制式：至少十個工作數量

Salem市議會─專案選擇(p.185~186)TheMathematicalModel

Max4176X1+1774X2+2513X3+1928X4+3607X5+962X6+2829X7+1708X8+3003X9

S.T. 400X1+ 350X2+ 50X3+ 100X4+ 500X5+ 90X6+ 220X7+ 150X8+ 140X9 £ 900

7X1+ X3+ 2X5+ X6+ 8X7+ 3X8+ 2x9 ³ 10

X1+ X2+ X3+ X4 £ 3

X3+ X5 = 1

X7- X8 = 0

X7- X9

³ 0 x8- x9

³ 0(Xi=0,1fori=1,2…,9)38互斥性：警車與消防車購其一體育與音樂須在電腦設備購買前通過共Salem市議會─專案選擇=SUMPRODUCT(B4:B12,E4:E12)=SUMPRODUCT(B4:B12,C4:C12)=SUMPRODUCT(B4:B12,D4:D12)=SUM(B4:B7)=B6+B8=B10-B11=B10-B12=B11-B1239Salem市議會─專案選擇=SUMPRODUCT(B4:B1Chapter3線性與整數規劃模式之應用ApplicationsofLinearandIntegerProgrammingModels40Chapter3線性與整數規劃模式之應用13.1LP在企業與政府之逐漸發展(p.140)有許多應用LP與ILP之成功案例四個目標:檢視LP可用之應用領域發展好的模型化技巧使用試算表產生結果說明與分析試算表報告結果成功案例：見(p.140)413.1LP在企業與政府之逐漸發展(p.140)有許成功建立模型之三項因素:熟悉度（Familiarity）簡單化(Simplicity)明確性(Clarity)3.2建立良好線性與整數規劃模式42成功建立模型之三項因素:3.2建立良好線性與整數規劃模式總和變數與限制式(P.142)

Summation

Variables

/Constraints範例生產三種機型電視機型每種機型分別使用2,3,and4磅塑膠可利用塑膠plastic為7000磅.任何機型不超過總產量之40%單位利潤分別為$23,$34,和$45.求生產計畫使得總利潤最大43總和變數與限制式(P.142)

SummationVar求解SolutionMax23X1+34X2+45X3S.T. 2X1+ 3X2+ 4X3

£7000不使用總和變數X1

£.4(X1+X2+X3) X2

£.4(X1+X2+X3)

X3

£.4(X1+X2+X3)

X1,X2,X3

³0使用總和變數X1+X2+X3=X4X1

£.4X4 X2

£.4X4

X3

£.4X4

X1,X2,X3,X4

³0總和變數與限制式

Summation

Variables

/Constraints44求解SolutionMax23X1+34X2+4TVproductionSolver試算表=SUM(B2:D2)總生產量決策變數百分比限制式塑膠限制式45TVproductionSolver試算表=SUM(B£³轉換成下列形式:(數學式子)[關係式](常數)建立線性模型清單

(p.145)A+2BA+2B2A+B+10

-A+B10在形成數學符號之前先以說話形式形成一種關係

(某個式子)[有某種關係](另一個式子或常數)

46£³轉換成下列形式:建立線性模型清單(p.145)A+建立線性模型清單關係式兩邊的單位必須要一致適當使用總和變數確認變數為非負Non-negative整數Integers二元Binary47建立線性模型清單關係式兩邊的單位必須要一致8協助管理者做決策對於資源之使用能有效率應用領域包含:決定生產水準排程輪班加班額外資源之成本效益3.4.線性規劃模式之應用─生產排程模型(ProductionSchedulingModels)48協助管理者做決策對於資源之使用能有效率3.4.線性規劃模式GalaxyIndustries擴張計畫GalaxyIndustries計畫增加產能並試銷兩種新產品Data(見p.149,表3.1)可用塑膠數量3000pounds正常工作時間(Regulartime)40hours.加班時間(Overtime)32hours.加班時間成本每小時比正常工作時間多$18049GalaxyIndustries擴張計畫GalaxyIData-continued兩種新產品:大水槍(BigSquirts)滲透者(Soakers)市場需求:SpaceRays=總產量之50%.其他產品產量<=總產量之40%.最小總產量1000打/每週.GalaxyIndustries擴張計畫兩種舊產品:宇宙光Spacerays射擊手Zappers50Data-continuedGalaxyIndustrData-ContinuedPlasticProductionProductProfit(lbs)

Time(min)SpaceRays$1623Zappers$1514BigSquirts$2035Soakers$2246PlasticProductionProductProfit(lbs)

Time(min)SpaceRays$1623Zappers$1514BigSquirts$2035Soakers$2246管理者希望週淨利潤(NetWeeklyProfit)最大

需決定一週生產排程與加班時數GalaxyIndustries擴張計畫51Data-ContinuedPlasticProduct決策變數(DecisionVariables)(p.150)X1=每週生產SpaceRays打數X2=每週生產Zapper打數X3=每週生產BigSquirts打數X4=每週生產Soakers打數X5=每週排定加班overtime時數GalaxyIndustries擴張計畫–求解過程52決策變數(DecisionVariables)(p.1目標函數(ObjectiveFunction)週淨利潤NetWeeklyProfit=銷售利潤thesaleofproducts–加班成本extracostofovertimeMaximize16X1+15X2+20X3+22X4-180X5GalaxyIndustries擴張計畫–求解過程53Maximize16X1+15X2+20X3+22X4限制式(Constraints)(p.150)

GalaxyIndustries擴張計畫–求解過程54GalaxyIndustries擴張計畫–求解過程15加入總和限制式X6(產品組合限制式之用)X6=每週生產總數(indozens),X6=X1+X2+X3+X4,or

X1+X2+X3+X4-X6=0GalaxyIndustries擴張計畫–求解過程55加入總和限制式X6(產品組合限制式之用)X6=每週生GalaxyIndustries擴張計畫–求解過程56GalaxyIndustries擴張計畫–求解過程17完整數學模式Max16X1+15X2+20X3+22X4–180X5 S.T. 2X1+ 1X2+ 3X3+ 4X4

£ 3000 3X1+ 4X2+ 5X3+ 6X4–

60X5 £

2400 X5

£ 32 1X2

³ 200 X1+ X2+ X3+ X4- - X6 =0

X1 -.5X6 = 0

X2 -.4X6 = 0 X3 -.4X6 =0 X4 -.4X6 = 0 X6 ³ 1000Xjarenon-negativeGalaxyIndustries擴張計畫–求解過程57完整數學模式Max16X1+15X2+20X3+=SUM(B4:E4)PercentageConstraintsSUMPRODUCT($B$4:$F$4,B6,F6)DragtoG7:G10GalaxyIndustries擴張計畫–求解過程58=SUM(B4:E4)PercentageSUMPRODUCGalaxyIndustries擴張計畫–求解過程(p.153~p.154)負值如何解釋?59GalaxyIndustries擴張計畫–求解過程(p3.5整數線性規劃模型之應用(p.179)許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pureinteger(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或1)混合整數線性模型Mixedinteger(MILP)：有些變數非整數或二元值603.5整數線性規劃模型之應用(p.179)許多現實模型使用二元變數

Theuseofbinaryvariablesinconstraints一個變數之決策結果分為“yes”/“no”,“good”/“bad”等.皆為二元分類說明61使用二元變數

Theuseofbinaryvaria範例以二元變數Y1

,Y2,Y3

表示三家工廠的每一家是否要建(Yi=1)或不建(Yi=0)

需求Requirement

二元Binary表示法

至少兩家工廠要被建立 Y1+Y2+Y3

³2

若工廠1要建，則工廠2不能建 Y1+Y2

£1

若工廠1要建，則工廠2也要建 Y1–Y2

£0

一間工廠要建，但不可以兩間工廠同時建 Y1+Y2=1

兩者都要或都不要建 Y1–Y2=0

工廠建設不可超過$17百萬其中個別成本為$5,$8,$10百萬 5Y1+8Y2+10Y3£17 使用二元變數(p.179)62範例使用二元變數(p.179)23範例(條件限制式)

工廠1生產鋼材可以製造兩種產品：產品1需要6磅重鋼材，產品2需要9磅重鋼材

若工廠1被建後，將有2000磅重鋼材可以利用此產品是否生產取決於工廠1是否建立，表示式如下

6X1+9X2

£2000Y1使用二元變數(p.180)若工廠1建立則Y1=1.限制式變為6x1+9X2£2000若工廠1不建則Y1=0限制式變為6x1+9X2£0,且X1=0,X2=063範例(條件限制式)使用二元變數(p.180)若工廠13.5.1人員排程模型(p.180)PersonnelSchedulingModels典型整數規劃問題，為分派人員或機器以達到最低的要求範圍這些模型有多於一期或以上可以利用的資源限制式(i.e.第t期可獲得資源數將影響第t+1期結果)643.5.1人員排程模型(p.180)PersonnSunset海灘市一週七天需要海灘救生員法律規定救生員每週工作5天且有兩天連假.

安全起見，每天平均每8000名遊客需提供一名救生員成本考量起見，雇用救生員人數越少越好Sunset海灘救生員的派任(p.181)

SunsetBeachLifeguardAssignments65Sunset海灘市一週七天需要海灘救生員Sunset海灘救生總結Summary排定連續五天救生員排程雇用救生員人數總數越少越好符合每天最低救生員需求量 Sun. Mon. Tue. Wed. Thr. Fri. Sat. 8 6 5 4 6 7 9Sunset海灘救生員的派任(p.181)

66總結SummarySunset海灘救生員的派任(p.181決策變數DecisionVariablesXi=第“i”排定救生員人數fori=1,2,…,7(i=1isSunday)

目標函數ObjectiveFunction救生員總人數最少限制式

Constraints確定每天有最低需求量的救生員.Sunset海灘救生員的派任(p.181~182)67決策變數DecisionVariablesSunset海

X7Sunset海灘救生員的派任

X6

X5

X4

X3Tue.Wed.Thu.Fri.SatSun.WhoworksonSaturday?WhoworksonFriday?

X2MonX3X4X5X6找出每天工作的救生員，逐步建立限制式68X7Sunset海灘救生員的派任Sunset海灘救生員的派任模式

Min X1+ X2+

X3+ X4+

X5+ X6+X7S.T.

X1+ X4+

X5+ X6+X7 ³ 8(Sun) X1+ X2+ X5+ X6+X7 ³ 6(Mon)

X1+ X2+ X3+ X6+X7 ³ 5(Tue)

X1+ X2+ X3+ X4+ X7 ³ 4(Wed)

X1+ X2+ X3+ X4+ X5 ³ 6(Tur)

X2+ X3+ X4+ X5+ X6

³ 7(Fri) X3+ X4+ X5+ X6+ X7 ³ 9(Sat)

所有變數為非負整數69Sunset海灘救生員的派任模式 Min X1+ X2Sunset海灘救生員的派任70Sunset海灘救生員的派任31Sunset海灘救生員的派任71Sunset海灘救生員的派任32TOTALLIFEGUARDS

最佳解組合LIFEGUARDSDAYPRESENTREQUIREDBEGINSHIFTSUNDAY9