整数线性规划模型建立ppt课件.ppt

《整数线性规划模型建立ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整數線性規劃模型建立使用二元變數Theuseofbinaryvariablesinconstraints一個變數之決策結果分為“yes”/“no”,“good”/“bad”等.皆為二元分類說明許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pureinteger(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或1)混合整數線性模型Mixedinteger(MILP)：有些變數非整數或二元值典型範例(PrototypeExample)DecisionVariablesObjectiveFun

2、ctionZ=TotalNetPresentValuesofthesedecisionsMaxZ=9X1+5X2+6X3+4X4DecisionNo“Yes”or“No”DecisionVariableNetPresentValueCapitalCost(million)1LA建工廠？X1$9$62SF建工廠？X2$5$33LA建倉庫？X3$6$54SF建倉庫？X4$4$2可用資金:$10(million)ConstraintDescriptions1.4項設備之總資金最多為＄102.該公司最多建造一間倉庫(互斥決策,MutuallyExculsive）3.公

3、司僅考慮在建廠的城市增設新倉庫(附屬方案,ContigentDecision）ConstraintModels6X1+3X2+5X3+2X4£10X3+X4£1X3£X1X4£X2MathModelMaxZ=9X1+5X2+6X3+4X4S.T.6X1+3X2+5X3+2X4£10X3+X4£1-X1+X3£0-X2+X4£0Xj£1Xj0X1,X2,X3,X4integersX1,X2,X3,X4binary範例說明二元變數Yi表示某家工廠是否要建(Yi=1)或不建(Yi=0)需求Requirement二元Binary表示法1.三家工廠中至少兩家工廠要被建

4、立Y1+Y2+Y3³22.若工廠1要建，則工廠2不能建Y1+Y2£13.若工廠1要建，則工廠2也要建Y1–Y2£04.一間工廠要建，但不可以兩間工廠同時建Y1+Y2=15.兩者都要或都不要建Y1–Y2=06.工廠建設不可超過$17百萬其中個別成本為$5,$8,$10百萬5Y1+8Y2+10Y3£17工廠1生產鋼材可以製造兩種產品：產品1需要6磅重鋼材，產品2需要9磅重鋼材若工廠1被建後，將有2000磅重鋼材可以利用此產品是否生產取決於工廠1是否建立，表示式如下6X1+9X2£2000Y1補充範例一(見講義)若工廠1建立則Y1=1.限制式變為6x1+9X2£20

5、00若工廠1不建則Y1=0限制式變為6x1+9X2£0,且X1=0,X2=0補充範例二：固定費用模型(見講義)(Fixed-ChargeModel)某工廠製造三種類型衣服：Shirts,Shorts,Pants。該廠必須租用機器來製造不同類型之衣服，-機器租金分別如下：Shirts用機器每週租金為$200，Shorts用機器每週租金為$150，Pants用機器每週租金為$100-製造衣服所需要勞力與布料的資料，以及其單位售價與單位製造成本分別如下表所示：勞力(每小時)布料(每單位)單位售價單位製造成本Shirts34$12$6Shorts23$8$4Pants

6、64$15$8DecisionVariablesX1=numberofshirtsproducedperweekX2=numberofshortsproducedperweekX3=numberofpantsproducedperweekZ=(12X1+8X2+15X3)-(6X1+4X2+8X3)-(200y1+150y2+100y3)=6X1+4X2+7X3-200y1-150y2-100y3WeeklyProfits=WeeklySalesRevenue-WeeklyProductionCost-WeeklyRenting(Setup)CostObjec

7、tiveFunctionMathModelMaxZ=6X1+4X2+7X3-200y1-150y2-100y3S.T.3X1+2X2+6X3£1504X1+3X2+4X3£160X1,X2,X3integersy1,y2,y3binaryConstraints:C1:Atmost150hoursoflaborscanbeusedperweek6X1+2X2+6X3<=150C2:Atmost160unitsofclothcanbeusedperweek4X1+3X2+4X3<=160以LP求解得到：X1=30X2=0X3=10y1=0y2=0y3=0MathM

8、odelMaxZ=6X1+4X2+7X