《线性与整数之应用课件.ppt》由会员分享，可在线阅读，更多相关《线性与整数之应用课件.ppt（39页珍藏版）》请在三一办公上搜索。
1、1,Chapter 3,線性與整數規劃模式之應用Applications of Linear and Integer Programming Models,2,3.1 LP在企業與政府之逐漸發展(p.140),有許多應用LP與ILP之成功案例四個目標:檢視LP可用之應用領域發展好的模型化技巧使用試算表產生結果說明與分析試算表報告結果成功案例：見(p.140),3,成功建立模型之三項因素:熟悉度（Familiarity）簡單化(Simplicity)明確性(Clarity),3.2 建立良好線性與整數規劃模式,4,總和變數與限制式(P.142)Summation Variables/Constr
2、aints,範例生產三種機型電視機型每種機型分別使用2,3,and 4磅塑膠可利用塑膠plastic為7000磅.任何機型不超過總產量之40%單位利潤分別為$23,$34,和$45.求生產計畫使得總利潤最大,5,求解 Solution,Max 23X1+34X2+45X3S.T.2X1+3X2+4X3 7000,總和變數與限制式Summation Variables/Constraints,6,TV production Solver 試算表,7,轉換成下列形式:(數學式子)關係式(常數),建立線性模型清單(p.145),A+2B,A+2B,2A+B+10,-A+B 10,在形成數學符號之前先
3、以說話形式形成一種關係(某個式子)有某種關係(另一個式子或常數),8,建立線性模型清單,關係式兩邊的單位必須要一致適當使用總和變數確認變數為非負 Non-negative整數 Integers二元 Binary,9,協助管理者做決策對於資源之使用能有效率應用領域包含:決定生產水準排程輪班加班額外資源之成本效益,3.4.線性規劃模式之應用 生產排程模型(Production Scheduling Models),10,Galaxy Industries 擴張計畫,Galaxy Industries計畫增加產能並試銷兩種新產品 Data(見p.149,表3.1)可用塑膠數量3000 pounds
4、正常工作時間(Regular time)40 hours.加班時間(Overtime)32 hours.加班時間 成本每小時比正常工作時間多$180,11,Data-continued兩種新產品:大水槍(Big Squirts)滲透者(Soakers)市場需求:Space Rays=總產量之50%.其他產品產量=總產量之40%.最小總產量1000 打/每週.,Galaxy Industries 擴張計畫,兩種舊產品:宇宙光 Space rays射擊手 Zappers,12,Data-Continued,Plastic,Production,Product,Profit,(lbs),Time(m
5、in),Space Rays,$16,2,3,Zappers,$15,1,4,Big Squirts,$20,3,5,Soakers,$22,4,6,Plastic,Production,Product,Profit,(lbs),Time(min),Space Rays,$16,2,3,Zappers,$15,1,4,Big Squirts,$20,3,5,Soakers,$22,4,6,管理者希望週淨利潤(Net Weekly Profit)最大 需決定一週生產排程與加班時數,Galaxy Industries 擴張計畫,13,決策變數(Decision Variables)(p.150)X
6、1=每週生產 Space Rays打數X2=每週生產 Zapper打數X3=每週生產 Big Squirts打數X4=每週生產 Soakers打數X5=每週排定加班overtime時數,Galaxy Industries 擴張計畫 求解過程,14,目標函數(Objective Function)週淨利潤Net Weekly Profit=銷售利潤the sale of products 加班成本extra cost of overtime,Maximize 16X1+15X2+20X3+22X4-180X5,Galaxy Industries 擴張計畫 求解過程,15,限制式(Constrai
7、nts)(p.150),Galaxy Industries 擴張計畫 求解過程,16,加入總和限制式X6(產品組合限制式之用),X6=每週生產總數(in dozens),X6=X1+X2+X3+X4,or X1+X2+X3+X4-X6=0,Galaxy Industries 擴張計畫 求解過程,17,Galaxy Industries 擴張計畫 求解過程,18,完整數學模式,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-.
8、5X6=0X2-.4X6=0X3-.4X6=0X4-.4X6=0X6 1000,Xj are non-negative,Galaxy Industries 擴張計畫 求解過程,19,Galaxy Industries 擴張計畫 求解過程,20,Galaxy Industries 擴張計畫 求解過程(p.153p.154),負值如何解釋?,21,3.5 整數線性規劃模型之應用(p.179),許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pure integer(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或 1)混合整數
9、線性模型Mixed integer(MILP)：有些變數非整數或二元值,22,使用二元變數The use of binary variables in constraints,一個變數之決策結果分為“yes”/“no”,“good”/“bad”等.皆為二元分類說明,23,範例以二元變數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兩者都要或都不要
10、建Y1 Y2=0工廠建設不可超過$17百萬 其中個別成本為$5,$8,$10百萬5Y1+8Y2+10Y3 17,使用二元變數(p.179),24,範例(條件限制式)工廠1生產鋼材可以製造兩種產品：產品 1需要 6磅重鋼材，產品 2需要 9磅重鋼材 若工廠1被建後，將有2000磅重鋼材可以利用此產品是否生產取決於工廠1是否建立，表示式如下 6X1+9X2 2000Y1,使用二元變數(p.180),25,3.5.1 人員排程模型(p.180)Personnel Scheduling Models,典型整數規劃問題，為分派人員或機器以達到最低的要求範圍這些模型有多於一期或以上可以利用的資源限制式(i
11、.e.第 t 期可獲得資源數將影響第 t+1期結果),26,Sunset海灘市一週七天需要海灘救生員法律規定救生員每週工作5天且有兩天連假.安全起見，每天平均每8000名遊客需提供一名救生員成本考量起見，雇用救生員人數越少越好,Sunset海灘救生員的派任(p.181)Sunset Beach Lifeguard Assignments,27,總結Summary排定連續五天救生員排程雇用救生員人數總數越少越好符合每天最低救生員需求量Sun.Mon.Tue.Wed.Thr.Fri.Sat.8 6 5 4 6 7 9,Sunset海灘救生員的派任(p.181),28,決策變數 Decision V
12、ariablesXi=第“i”排定救生員人數 for i=1,2,7(i=1 is Sunday)目標函數 Objective Function救生員總人數最少限制式 Constraints確定每天有最低需求量的救生員.,Sunset海灘救生員的派任(p.181182),29,X 7,Sunset海灘救生員的派任,X6,X5,X4,X3,Tue.Wed.Thu.Fri.Sat Sun.,Who works on Saturday?,Who works on Friday?,X2,Mon,X3X4X5X6,找出每天工作的救生員，逐步建立限制式,30,Sunset海灘救生員的派任模式,MinX1+
13、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)所有變數為非負整數,31,Sunset海灘救生員的派任,32,Sunset海灘救生員的派任,33,TOTAL LIFEGUARDS,Note:An alternate optimal solution exists.,Sunset海灘救生員的派任,34,專案選擇模型由
14、一群二元變數表示”“go/no-go”的決定 模型中包含元件有:預算Budget空間Space優先順序Priority conditions,3.5.2 專案選擇模型Project selection Models,35,Salem市議會的目標是最大化選民之支持度下合理分派預算資料中包含成本costs,可利用資源,計畫優順序.,Salem市議會專案選擇Salem City Council Project Selection,36,Salem市議會專案選擇(p.185),37,決策變數:Xj-一組二元決策變數；if a project j is selected(Xj=1)or not(Xj=0
15、)for j=1,2,.,9目標函數:使經費之計畫總點數最大化限制式:See the mathematical model.,Salem市議會專案選擇(p.185),38,互斥性：警車與消防車購其一,體育與音樂須在電腦設備購買前通過,共同必要性：體育與音樂同時恢復或不恢復,最大預算不能超過$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+140X9900 7X1+X3+2X5+X6+8X7+3X8+2x910 X1+X2+X3+X43X3+X5=1X7-X8=0X7-X90 x8-x9 0,(Xi=0,1 for i=1,2,9),39,Salem市議會專案選擇,=SUMPRODUCT(B4:B12,C4:C12)=SUMPRODUCT(B4:B12,D4:D12)=SUM(B4:B7)=B6+B8=B10-B11=B10-B12=B11-B12,
