线性与整数之应用课件.ppt

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

2、別使用2,3,and 4磅塑膠 可利用塑膠plastic為7000磅.任何機型不超過總產量之40%單位利潤分別為$23,$34,和$45.求生產計畫使得總利潤最大5 求解 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/Constraints6TV pr

3、oduction Solver 試算表試算表=SUM(B2:D2)總生產量決策變數百分比限制式塑膠限制式7 轉換成下列形式:(數學式子數學式子)關係式關係式 (常數常數)建立線性模型清單建立線性模型清單(p.145)A +2BA +2B2A +B+10-A +B 10 在形成數學符號之前先以說話形式形成一種關係 (某個式子某個式子)有某種關係有某種關係 (另一個式子或常數另一個式子或常數)8建立線性模型清單建立線性模型清單 關係式兩邊的單位必須要一致 適當使用總和變數 確認變數為 非負非負 Non-negative 整數整數 Integers 二元二元 Binary9 協助管理者做決策對於資源

4、之使用能有效率 應用領域包含:決定生產水準 排程輪班 加班 額外資源之成本效益3.4.線性規劃模式之應用線性規劃模式之應用 生產排程生產排程模型模型(Production Scheduling Models)10Galaxy Industries 擴張計畫擴張計畫 Galaxy Industries計畫增加產能並試銷兩種新產品 Data(見p.149,表3.1)可用塑膠數量3000 pounds 正常工作時間(Regular time)40 hours.加班時間(Overtime)32 hours.加班時間 成本每小時比正常工作時間多$18011 Data-continued 兩種新產品:大水

5、槍(Big Squirts)滲透者(Soakers)市場需求:Space Rays=總產量之50%.其他產品產量=總產量之40%.最小總產量1000 打/每週.Galaxy Industries 擴張計畫擴張計畫兩種舊產品:宇宙光 Space rays射擊手 Zappers12 Data-ContinuedPlasticProductionProductProfit(lbs)Time(min)Space Rays$1623Zappers$1514Big Squirts$2035Soakers$2246PlasticProductionProductProfit(lbs)Time(min)Spa

6、ce Rays$1623Zappers$1514Big Squirts$2035Soakers$2246 管理者希望週淨利潤(Net Weekly Profit)最大 需決定一週生產排程與加班時數Galaxy Industries 擴張計畫擴張計畫13 決策變數(Decision Variables)(p.150)X1=每週生產 Space Rays打數X2=每週生產 Zapper打數X3=每週生產 Big Squirts打數X4=每週生產 Soakers打數X5=每週排定加班overtime時數Galaxy Industries 擴張計畫擴張計畫 求解過程求解過程14 目標函數(Object

7、ive Function)週淨利潤Net Weekly Profit=銷售利潤the sale of products 加班成本extra cost of overtimeMaximize 16X1+15X2+20X3+22X4-180X5Galaxy Industries 擴張計畫擴張計畫 求解過程求解過程15 限制式(Constraints)(p.150)200X2 :200produced Zappers32X4 :32used hours Overtime240060X5-6X4+5X3+4X2+3x1or 60X5,+24006X4+5X3+4X2+3X1:available min

8、utes overtime)+time regular(of Numberminutes production of Number30004X4+3X3+X2+2X :3000usedplastic ofAmount 1Galaxy Industries 擴張計畫擴張計畫 求解過程求解過程16加入總和限制式X6 (產品組合限制式之用)X6=每週生產總數(in dozens),X6=X1+X2+X3+X4,or X1+X2+X3+X4-X6=0Galaxy Industries 擴張計畫擴張計畫 求解過程求解過程171000X61000least at is production Total0.

9、4X6X4production total of 40%Soakers of productionWeekly 0.4X6X3production total of 40%Squirts Big of productionWeekly 0.4X6X2production total of 40%Zappers of productionWeekly 0.5X6X1production total of 50%Rays Space of productionWeekly Galaxy Industries 擴張計畫擴張計畫 求解過程求解過程18完整數學模式Max 16X1+15X2+20X3+2

10、2X4 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 擴張計畫擴張計畫 求解過程求解過程19=SUM(B4:E4)PercentageConstraintsSUMPRODUCT($B$4:$F$4,B6,F6)Drag to G7:G10Galaxy Industries 擴張計畫擴張計畫 求解過求解過程程20Ga

11、laxy Industries 擴張計畫擴張計畫 求解過程求解過程(p.153p.154)負值如何解釋?213.5 整數線性規劃模型之應用整數線性規劃模型之應用(p.179)許多現實模型中至少一個決策變數為整數值 整數模型之分類 純整數線性模型Pure integer(AILP)：所有決策變數皆為整數 二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或 1)混合整數線性模型Mixed integer(MILP)：有些變數非整數或二元值22使用二元變數使用二元變數The use of binary variables in constraintsX 10 If a new h

12、ealth care plan is adopted If it is notX 1 If a new police station is built downtown0 If it is notX 1 If a particular constraint must hold0 If it is not 一個變數之決策結果分為一個變數之決策結果分為“yes”/“no”,“good”/“bad”等等.皆為二元分類皆為二元分類 說明說明23 範例 以二元變數Y1,Y2,Y3 表示三家工廠的每一家是否要建(Yi=1)或不建(Yi=0)需求Requirement二元二元Binary表示法表示法至少兩家

13、工廠要被建立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)24 範例(條件限制式)工廠1生產鋼材可以製造兩種產品：產品 1需要 6磅重鋼材，產品 2需要 9磅重鋼材 若工廠1被建後，將有2000磅重鋼材可以利用 此產品是否生產取決於工廠1是否建立，表示式如下 6X1+9X2 2000Y1使用二元變數使用二元變數(p.180

14、)若工廠1 建立則 Y1=1.限制式變為6x1+9X2 2000若工廠1 不建則 Y1=0限制式變為6x1+9X2 0,且X1=0,X2=0253.5.1 人員排程模型人員排程模型(p.180)Personnel Scheduling Models 典型整數規劃問題，為分派人員或機器以達到最低的要求範圍 這些模型有多於一期或以上可以利用的資源限制式(i.e.第 t 期可獲得資源數將影響第 t+1期結果)26 Sunset海灘市一週七天需要海灘救生員 法律規定救生員每週工作5天且有兩天連假.安全起見，每天平均每8000名遊客需提供一名救生員 成本考量起見，雇用救生員人數越少越好Sunset海灘救

15、生員的派任海灘救生員的派任(p.181)Sunset Beach Lifeguard Assignments27 總結Summary 排定連續五天救生員排程 雇用救生員人數總數越少越好 符合每天最低救生員需求量Sun.Mon.Tue.Wed.Thr.Fri.Sat.8 6 5 4 6 7 9Sunset海灘救生員的派任海灘救生員的派任(p.181)28 決策變數 Decision VariablesXi=第“i”排定救生員人數 for i=1,2,7 (i=1 is Sunday)目標函數 Objective Function救生員總人數最少 限制式 Constraints確定每天有最低需求量

16、的救生員.Sunset海灘救生員的派任海灘救生員的派任(p.181182)29Sunset海灘救生員的派任海灘救生員的派任Tue.Wed.Thu.Fri.Sat Sun.Who works on Saturday?Who works on Friday?X2MonX3X4X5X6找出每天工作的救生員，逐步建立限制式30Sunset海灘救生員的派任模式海灘救生員的派任模式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

17、+X2+X3+X4+X5 6(Tur)X2+X3+X4+X5+X6 7(Fri)X3+X4+X5+X6+X7 9(Sat)所有變數為非負整數31Sunset海灘救生員的派任海灘救生員的派任32Sunset海灘救生員的派任海灘救生員的派任33TOTAL LIFEGUARDS 最佳解組合最佳解組合LIFEGUARDSDAYPRESENTREQUIRED BEGIN SHIFTSUNDAY981MONDAY860TUESDAY651WEDNESDAY541THURSDAY663FRIDAY772SATURDAY99210Note:An alternate optimal solution exist

18、s.Sunset海灘救生員的派任海灘救生員的派任34 專案選擇模型由一群二元變數表示”“go/no-go”的決定 模型中包含元件有:預算Budget 空間Space 優先順序Priority conditions3.5.2 專案選擇模型專案選擇模型Project selection Models35 Salem市議會的目標是最大化選民之支持度下合理分派預算 資料中包含成本costs,可利用資源,計畫優順序.Salem市議會市議會專案選擇專案選擇Salem City Council Project Selection36民調之結果X1X2X3X4X5X6X7X8X9Salem市議會市議會專案選擇

19、專案選擇(p.185)37 決策變數決策變數: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)38互斥性：警車與消防車購其一體育與音樂須在電腦設備購買前通過共同必要性：體育與音樂同時恢復或不恢復 最大預算不能超過$900,000 4個警察計畫中至多3個限制式通過 工作創造限制式：至少十個工作數量 Salem市議會市議會專案選擇專案選擇(p.1

20、85186)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)39Salem市議會市議會專案選擇專案選擇=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-B12