線性與整數(shù)之應(yīng)用課件

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

Summation

Variables

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

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

￡7000不使用總和變數(shù)X1

￡.4(X1+X2+X3) X2

￡.4(X1+X2+X3)

X3

￡.4(X1+X2+X3)

X1,X2,X3

30使用總和變數(shù)X1+X2+X3=X4X1

￡.4X4 X2

￡.4X4

X3

￡.4X4

X1,X2,X3,X4

30總和變數(shù)與限制式

Summation

Variables

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

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

-A+B10在形成數(shù)學(xué)符號(hào)之前先以說話形式形成一種關(guān)係

(某個(gè)式子)[有某種關(guān)係](另一個(gè)式子或常數(shù))

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

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

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

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

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

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

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

60X5 ￡

2400 X5

￡ 32 1X2

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

X1 -.5X6 = 0

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

Theuseofbinaryvariablesinconstraints一個(gè)變數(shù)之決策結(jié)果分為“yes”/“no”,“good”/“bad”等.皆為二元分類說明22使用二元變數(shù)

Theuseofbinaryvaria範(fàn)例以二元變數(shù)Y1

,Y2,Y3

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

需求Requirement

二元Binary表示法

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

32

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

￡1

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

￡0

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

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

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

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

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

6X1+9X2

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

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

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

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

目標(biāo)函數(shù)ObjectiveFunction救生員總?cè)藬?shù)最少限制式

Constraints確定每天有最低需求量的救生員.Sunset海灘救生員的派任(p.181~182)28決策變數(shù)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 3 8(Sun) X1+ X2+ X5+ X6+X7 3 6(Mon)

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

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

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

X2+ X3+ X4+ X5+ X6

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

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

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

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

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

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

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

使經(jīng)費(fèi)之計(jì)畫總點(diǎn)數(shù)最大化限制式: Seethemathematicalmodel.Salem市議會(huì)─專案選擇(p.185)37決策變數(shù):Salem市議會(huì)─專案選擇(p.185)3互斥性：警車與消防車購其一體育與音樂須在電腦設(shè)備購買前