线性与整数之应用课件

Chapter 3線性與整數規劃模式之應用Applications of Linear and Integer Programming Models 1Chapter 3線性與整數規劃模式之應用13.1 LP在企業與政府之逐漸發展在企業與政府之逐漸發展(p.140)有許多應用LP與ILP之成功案例四個目標:檢視LP可用之應用領域發展好的模型化技巧使用試算表產生結果說明與分析試算表報告結果成功案例：見(p.140)23.1 LP在企業與政府之逐漸發展(p.140)有許成功建立模型之三項因素:熟悉度（Familiarity）簡單化(Simplicity)明確性(Clarity)3.2 建立良好線性與整數規劃模式建立良好線性與整數規劃模式3成功建立模型之三項因素:3.2 建立良好線性與整數規劃模式總和變數與限制式總和變數與限制式(P.142)Summation Variables/Constraints範例生產三種機型電視機型每種機型分別使用2,3,and 4磅塑膠可利用塑膠plastic為7000磅.任何機型不超過總產量之40%單位利潤分別為$23,$34,和$45.求生產計畫使得總利潤最大4總和變數與限制式(P.142)Summation Var求解 SolutionMax 23X1+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 .4X4X2 .4X4X3 .4X4 X1,X2,X3,X4 0總和變數與限制式總和變數與限制式Summation Variables/Constraints5求解 SolutionMax 23X1+34X2+4TV production Solver 試算表試算表=SUM(B2:D2)總生產量決策變數百分比限制式塑膠限制式6TV production Solver 試算表=SUM(B轉換成下列形式:(數學式子數學式子)關係式關係式 (常數常數)建立線性模型清單建立線性模型清單(p.145)A +2BA +2B2A +B+10-A +B 10 在形成數學符號之前先以說話形式形成一種關係 (某個式子某個式子)有某種關係有某種關係 (另一個式子或常數另一個式子或常數)7轉換成下列形式:建立線性模型清單(p.145)A +建立線性模型清單建立線性模型清單關係式兩邊的單位必須要一致適當使用總和變數確認變數為非負非負 Non-negative整數整數 Integers二元二元 Binary8建立線性模型清單關係式兩邊的單位必須要一致8協助管理者做決策對於資源之使用能有效率應用領域包含:決定生產水準排程輪班加班額外資源之成本效益3.4.線性規劃模式之應用線性規劃模式之應用 生產排程生產排程模型模型(Production Scheduling Models)9協助管理者做決策對於資源之使用能有效率3.4.線性規劃模式Galaxy Industries 擴張計畫擴張計畫Galaxy Industries計畫增加產能並試銷兩種新產品 Data(見p.149,表3.1)可用塑膠數量3000 pounds 正常工作時間(Regular time)40 hours.加班時間(Overtime)32 hours.加班時間 成本每小時比正常工作時間多$18010Galaxy Industries 擴張計畫Galaxy IData-continued兩種新產品:大水槍(Big Squirts)滲透者(Soakers)市場需求:Space Rays=總產量之50%.其他產品產量=總產量之40%.最小總產量1000 打/每週.Galaxy Industries 擴張計畫擴張計畫兩種舊產品:宇宙光 Space rays射擊手 Zappers11Data-continuedGalaxy IndustrData-ContinuedPlasticProductionProductProfit(lbs)Time(min)Space Rays$1623Zappers$1514Big Squirts$2035Soakers$2246PlasticProductionProductProfit(lbs)Time(min)Space Rays$1623Zappers$1514Big Squirts$2035Soakers$2246 管理者希望週淨利潤(Net Weekly Profit)最大 需決定一週生產排程與加班時數Galaxy Industries 擴張計畫擴張計畫12Data-ContinuedPlasticProduct決策變數(Decision Variables)(p.150)X1=每週生產 Space Rays打數X2=每週生產 Zapper打數X3=每週生產 Big Squirts打數X4=每週生產 Soakers打數X5=每週排定加班overtime時數Galaxy Industries 擴張計畫擴張計畫 求解求解過程過程13決策變數(Decision Variables)(p.1目標函數(Objective Function)週淨利潤Net Weekly Profit=銷售利潤the sale of products 加班成本extra cost of overtimeMaximize 16X1+15X2+20X3+22X4-180X5Galaxy Industries 擴張計畫擴張計畫 求解求解過程過程14Maximize 16X1+15X2+20X3+22X4限制式(Constraints)(p.150)Galaxy Industries 擴張計畫擴張計畫 求解求解過程過程15Galaxy Industries 擴張計畫 求解過程15加入總和限制式X6 (產品組合限制式之用)X6=每週生產總數(in dozens),X6=X1+X2+X3+X4,or X1+X2+X3+X4-X6=0Galaxy Industries 擴張計畫擴張計畫 求解求解過程過程16加入總和限制式X6 (產品組合限制式之用)X6=每週生Galaxy Industries 擴張計畫擴張計畫 求解過求解過程程17Galaxy Industries 擴張計畫 求解過程17完整數學模式Max 16X1+15X2+20X3+22X4 180X5S.T.2X1+1X2+3X3+4X4 30003X1+4X2+5X3+6X4 60X5 2400X5 321X2 200 X1 +X2 +X3+X4-X6=0X1-.5X6=0X2-.4X6=0X3-.4X6=0X4-.4X6=0X6 1000Xj are non-negativeGalaxy Industries 擴張計畫擴張計畫 求解求解過程過程18完整數學模式Max 16X1+15X2+20X3+=SUM(B4:E4)PercentageConstraintsSUMPRODUCT($B$4:$F$4,B6,F6)Drag to G7:G10Galaxy Industries 擴張計畫擴張計畫 求解求解過程過程19=SUM(B4:E4)PercentageSUMPRODUCGalaxy Industries 擴張計畫擴張計畫 求解求解過程過程(p.153p.154)負值如何解釋?20Galaxy Industries 擴張計畫 求解過程(p3.5 整數線性規劃模型之應整數線性規劃模型之應用用(p.179)許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pure integer(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或 1)混合整數線性模型Mixed integer(MILP)：有些變數非整數或二元值213.5 整數線性規劃模型之應用(p.179)許多現實模型使用二元變數使用二元變數The use of binary variables in constraints一個變數之決策結果分為一個變數之決策結果分為“yes”/“no”,“good”/“bad”等等.皆為二元分類皆為二元分類說明說明22使用二元變數The use of binary varia範例以二元變數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)Personnel Scheduling Models典型整數規劃問題，為分派人員或機器以達到最低的要求範圍這些模型有多於一期或以上可以利用的資源限制式(i.e.第 t 期可獲得資源數將影響第 t+1期結果)253.5.1 人員排程模型(p.180)PersonnSunset海灘市一週七天需要海灘救生員法律規定救生員每週工作5天且有兩天連假.安全起見，每天平均每8000名遊客需提供一名救生員成本考量起見，雇用救生員人數越少越好Sunset海灘救生員的派任海灘救生員的派任(p.181)Sunset Beach Lifeguard Assignments26Sunset海灘市一週七天需要海灘救生員Sunset海灘救生總結Summary排定連續五天救生員排程雇用救生員人數總數越少越好符合每天最低救生員需求量Sun.Mon.Tue.Wed.Thr.Fri.Sat.8 6 5 4 6 7 9Sunset海灘救生員的派任海灘救生員的派任(p.181)27總結SummarySunset海灘救生員的派任(p.181決策變數 Decision VariablesXi=第“i”排定救生員人數 for i=1,2,7 (i=1 is Sunday)目標函數 Objective Function救生員總人數最少限制式 Constraints確定每天有最低需求量的救生員.Sunset海灘救生員的派任海灘救生員的派任(p.181182)28決策變數 Decision VariablesSunset海 X 7X 7Sunset海灘救生員的派任海灘救生員的派任 X6X6 X5X5 X4X4 X3X3Tue.Wed.Thu.Fri.Sat Sun.Who works on Saturday?Who works on Friday?X2MonX3X4X5X6找出每天工作的救生員，逐步建立限制式29 X 7Sunset海灘救生員的派任 Sunset海灘救生員的派任模式海灘救生員的派任模式Min X1+X2+X3+X4+X5+X6+X7S.T.X1+X4+X5+X6+X78(Sun)X1+X2+X5+X6+X76(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+X2 Sunset海灘救生員的派任海灘救生員的派任31Sunset海灘救生員的派任31Sunset海灘救生員的派任海灘救生員的派任32Sunset海灘救生員的派任32TOTAL LIFEGUARDS 最佳解組合最佳解組合LIFEGUARDSDAYPRESENT REQUIRED BEGIN SHIFTSUNDAY981MONDAY860TUESDAY651WEDNESDAY541THURSDAY663FRIDAY772SATURDAY99210Note:An alternate optimal solution exists.Sunset海灘救生員的派任海灘救生員的派任33TOTAL LIFEGUARDS 最佳解組合LIF專案選擇模型由一群二元變數表示”“go/no-go”的決定 模型中包含元件有:預算Budget空間Space優先順序Priority conditions3.5.2 專案選擇模型專案選擇模型Project selection Models34專案選擇模型由一群二元變數表示”“go/no-go”的決定Salem市議會的目標是最大化選民之支持度下合理分派預算資料中包含成本costs,可利用資源,計畫優順序.Salem市議會市議會專案選擇專案選擇Salem City Council Project Selection35Salem市議會的目標是最大化選民之支持度下合理分派預算Sa民調之結果X1X2X3X4X5X6X7X8X9Salem市議會市議會專案選擇專案選擇(p.185)36民調之結果X1Salem市議會專案選擇(p.185)3決策變數決策變數:Xj-一組二元決策變數；if a project j is selected(Xj=1)or not(Xj=0)for j=1,2,.,9目標函數目標函數:使經費之計畫總點數最大化限制式限制式:See the mathematical model.Salem市議會市議會專案選擇專案選擇(p.185)37決策變數:Salem市議會專案選擇(p.185)3互斥性：警車與消防車購其一體育與音樂須在電腦設備購買前通過共同必要性：體育與音樂同時恢復或不恢復 最大預算不能超過$900,000 4個警察計畫中至多3個限制式通過 工作創造限制式：至少十個工作數量 Salem市議會市議會專案選擇專案選擇(p.185186)The Mathematical ModelMax 4176X1+1774X2+2513X3+1928X4+3607X5+962X6+2829X7+1708X8+3003X9S.T.400X1+350X2+50X3+100X4+500X5+90X6+220X7+150X8+140X9 900 7X1+X3+2X5+X6+8X7+3X8+2x9 10 X1+X2+X3+X4 3X3+X5=1X7-X8=0X7-X9 0 x8-x9 0 0(Xi=0,1 for i=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:B1