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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,Chapter 3,線性與整數規劃模式之應用,Applications of Linear and Integer Programming Models,1,Chapter 3線性與整數規劃模式之應用1,3.1 LP,在企業與政府之逐漸發展,(p.140),有許多應用,LP,與,ILP,之成功案例,四個目標,:,檢視,LP,可用之應用領域,發展好的模型化技巧,使用試算表產生結果,說明與分析試算表報告結果,成功案例：見,(p.140),2,3.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,求解,Solution,Max 23X,1,+34X,2,+45X,3,S.T,.,2X,1,+3X,2,+4X,3,7000,不使用總和變數,X,1,.4(X,1,+X,2,+X,3,),X,2,.4(X,1,+X,2,+X,3,),X,3,.4(X,1,+X,2,+X,3,),X,1,X,2,X,3,0,使用總和變數,X,1,+X,2,+X,3,=X,4,X,1,.4X,4,X,2,.4X,4,X,3,.4X,4,X,1,X,2,X,3,X4,0,總和變數與限制式,Summation,Variables,/Constraints,5,求解 SolutionMax 23X1+34X2+4,TV production Solver,試算表,=SUM(B2:D2),總生產量,決策變數,百分比限制式,塑膠限制式,6,TV production Solver 試算表=SUM(B,轉換成下列形式,:,(,數學式子,),關係式,(,常數,),建立線性模型清單,(p.145),A +2B,A +2B,2A +B+10,-A +B 10,在形成數學符號之前先以說話形式形成一種關係,(,某個式子,),有某種關係,(,另一個式子或常數,),7,轉換成下列形式:建立線性模型清單(p.145)A +,建立線性模型清單,關係式兩邊的單位必須要一致,適當使用總和變數,確認變數為,非負,Non-negative,整數,Integers,二元,Binary,8,建立線性模型清單關係式兩邊的單位必須要一致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.,加班時間 成本每小時比正常工作時間多,$180,10,Galaxy Industries 擴張計畫Galaxy I,Data-continued,兩種新產品,:,大水槍,(Big Squirts),滲透者,(Soakers),市場需求,:,Space Rays=,總產量之,50%.,其他產品產量,=,總產量之,40%.,最小總產量,1000,打,/,每週,.,Galaxy Industries,擴張計畫,兩種舊產品,:,宇宙光,Space rays,射擊手,Zappers,11,Data-continuedGalaxy Industr,Data-Continued,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,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,擴張計畫,12,Data-ContinuedPlasticProduct,決策變數,(Decision Variables)(p.150),X,1,=,每週生產,Space Rays,打數,X,2,=,每週生產,Zapper,打數,X,3,=,每週生產,Big Squirts,打數,X,4,=,每週生產,Soakers,打數,X,5,=,每週排定加班,overtime,時數,Galaxy Industries,擴張計畫,求解過程,13,決策變數(Decision Variables)(p.1,目標函數,(Objective Function),週淨利潤,Net Weekly Profit,=,銷售利潤,the sale of products,加班成本,extra cost of overtime,Maximize 16X,1,+15X,2,+20X,3,+22X,4,-180X,5,Galaxy Industries,擴張計畫,求解過程,14,Maximize 16X1+15X2+20X3+22X4,限制式,(Constraints)(p.150),Galaxy Industries,擴張計畫,求解過程,15,Galaxy Industries 擴張計畫 求解過程15,加入總和限制式,X,6,(,產品組合限制式之用,),X6=,每週生產總數,(in dozens),X6=X1+X2+X3+X4,or,X1+X2+X3+X4-X6=0,Galaxy Industries,擴張計畫,求解過程,16,加入總和限制式X6 (產品組合限制式之用)X6=每週生,Galaxy Industries,擴張計畫,求解過程,17,Galaxy Industries 擴張計畫 求解過程17,完整數學模式,Max 16X,1,+15X,2,+20X,3,+22X,4,180X,5,S.T,.,2X,1,+1X,2,+3X,3,+4X,4,3000,3X,1,+4X,2,+5X,3,+6X,4,60X,5,2400,X,5,32,1X,2,200,X,1,+X,2,+X,3,+X,4,-X,6,=0,X,1,-.5X,6,=0,X,2,-.4X,6,=0,X,3,-.4X,6,=0,X,4,-.4X,6,=0,X,6,1000,X,j,are non-negative,Galaxy Industries,擴張計畫,求解過程,18,完整數學模式Max 16X1+15X2+20X3+,=SUM(B4:E4),Percentage,Constraints,SUMPRODUCT($B$4:$F$4,B6,F6)Drag to G7:G10,Galaxy Industries,擴張計畫,求解過程,19,=SUM(B4:E4)PercentageSUMPRODUC,Galaxy Industries,擴張計畫,求解過程,(p.153p.154),負值如何解釋,?,20,Galaxy Industries 擴張計畫 求解過程(p,3.5,整數線性規劃模型之應用,(p.179),許多現實模型中至少一個決策變數為整數值,整數模型之分類,純整數線性模型,Pure integer(AILP),：,所有決策變數皆為整數,二元整數線性模型,Binary(BILP),：,所有決策變數皆為二元數,(0,或,1),混合整數線性模型,Mixed integer(MILP),：,有些變數非整數或二元值,21,3.5 整數線性規劃模型之應用(p.179)許多現實模型,使用二元變數,The use of binary variables in constraints,一個變數之決策結果分為,“yes”,/,“no”,“good”,/,“bad”,等,.,皆為二元分類,說明,22,使用二元變數The use of binary varia,範例,以二元變數,Y,1,Y,2,Y,3,表示三家工廠的每一家是否要建,(Y,i,=1),或不建,(Y,i,=0),需求,Requirement,二元,Binary,表示法,至少兩家工廠要被建立,Y,1,+Y,2,+Y,3,2,若工廠,1,要建，則工廠,2,不能建,Y,1,+Y,2,1,若工廠,1,要建，則工廠,2,也要建,Y,1,Y,2,0,一間工廠要建，但不可以兩間工廠同時建,Y,1,+Y,2,=1,兩者都要或都不要建,Y,1,Y,2,=0,工廠建設不可超過,$17,百萬,其中個別成本為,$5,$8,$10,百萬,5Y1+8Y2+10Y3,17,使用二元變數,(p.179),23,範例使用二元變數(p.179)23,範例,(,條件限制式,),工廠,1,生產鋼材可以製造兩種產品：,產品,1,需要,6,磅重鋼材，產品,2,需要,9,磅重鋼材,若工廠,1,被建後，將有,2000,磅重鋼材可以利用,此產品是否生產取決於工廠,1,是否建立，表示式如下,6X,1,+9X,2,2000Y,1,使用二元變數,(p.180),若工廠,1,建立則,Y,1,=1.,限制式變為,6x,1,+9X,2,2000,若工廠,1,不建則,Y,1,=0,限制式變為,6x,1,+9X,2,0,且,X,1,=0,X,2,=0,24,範例(條件限制式)使用二元變數(p.180)若工廠1,3.5.1,人員排程模型,(p.180)Personnel Scheduling Models,典型整數規劃問題，為分派人員或機器以達到最低的要求範圍,這些模型有多於一期或以上可以利用的資源限制式,(i.e.,第,t,期可獲得資源數將影響第,t+1,期結果,),25,3.5.1 人員排程模型(p.180)Personn,Sunset,海灘市一週七天需要海灘救生員,法律規定救生員每週工作,5,天且有兩天連假,.,安全起見，每天平均每,8000,名遊客需提供一名救生員,成本考量起見，雇用救生員人數越少越好,Sunset,海灘救生員的派任,(p.181)Sunset Beach Lifeguard Assignments,26,Sunset海灘市一週七天需要海灘救生員Sunset海灘救生,總結,Summary,排定連續五天救生員排程,雇用救生員人數總數越少越好,符合每天最低救生員需求量,Sun.Mon.Tue.Wed.Thr.Fri.Sat.,8 6 5 4 6 7 9,Sunset,海灘救生員的派任,(p.181),27,總結SummarySunset海灘救生員的派任(p.181,決策變數,Decision Variables,X,i,=,第,“i”,排定救生員人數,for i=1,2,7 (i=1 is Sunday),目標函數,Objective Fu