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

整數線性規劃模型建立使用二元變數The use of binary variables in constraints一個變數之決策結果分為一個變數之決策結果分為“yes”/“no”,“good”/“bad”等等.皆皆為二元分類為二元分類說明說明許多現實模型中至少一個決策變數為整數值整數模型之分類純整數線性模型Pure integer(AILP)：所有決策變數皆為整數二元整數線性模型Binary(BILP)：所有決策變數皆為二元數(0或 1)混合整數線性模型Mixed integer(MILP)：有些變數非整數或二元值典型範例(Prototype Example)Decision VariablesObjective Function Z=Total Net Present Values of these decisionsMax Z=9X1+5X2+6 X3+4X4Decision No“Yes”or“No”Decision VariableNet Present ValueCapital Cost(million)1LA建工廠？X1$9$62SF建工廠？X2$5$33LA建倉庫？X3$6$54SF建倉庫？X4$4$2可用資金:$10(million)Constraint Descriptions 1.4項設備之總資金最多為10 2.該公司最多建造一間倉庫 (互斥決策,Mutually Exculsive）3.公司僅考慮在建廠的城市增設新倉庫 (附屬方案,Contigent Decision）Constraint Models6X1+3X2+5X3+2X4 10 X3+X4 1 X3 X1 X4 X2 Math ModelMax Z=9X1+5X2+6X3 +4X4S.T.6X1+3X2+5X3 +2X4 10 X3 +X4 1 -X1 +X3 0 0 -X2 +X4 0 0 Xj 1 1 X j 0 0 X1 ,X2 ,X3,X4 integersX1 ,X2 ,X3,X4 binary範例說明二元變數Yi 表示某家工廠是否要建(Yi=1)或不建(Yi=0)需求Requirement二元二元Binary表示法表示法 1.三家工廠中至少兩家 工廠要被建立Y1+Y2+Y3 2 2.若工廠1要建，則工廠2不能建Y1+Y2 1 3.若工廠1要建，則工廠2也要建Y1 Y2 0 4.一間工廠要建，但不可以兩間工廠同時建 Y1+Y2=1 5.兩者都要或都不要建Y1 Y2=0 6.工廠建設不可超過$17百萬 其中個別成本為$5,$8,$10百萬5Y1+8Y2+10Y3 17 工廠1生產鋼材可以製造兩種產品：產品 1需要 6磅重鋼材，產品 2需要 9磅重鋼材 若工廠1被建後，將有2000磅重鋼材可以利用此產品是否生產取決於工廠1是否建立，表示式如下 6X1+9X2 2000Y1補充範例一(見講義)若工廠1 建立則 Y1=1.限制式變為6x1+9X2 2000若工廠1 不建則 Y1=0限制式變為6x1+9X2 0,且X1=0,X2=0補充範例二：固定費用模型(見講義)(Fixed-Charge Model)某工廠製造三種類型衣服：Shirts,Shorts,Pants。該廠必須租用機器來製造不同類型之衣服，-機器租金分別如下：Shirts用機器每週租金為$200，Shorts用機器每週租金為$150，Pants用機器每週租金為$100 -製造衣服所需要勞力與布料的資料，以及其單位售價與單位製造成本分別如下表所示：勞力(每小時)布料(每單位)單位售價單位製造成本Shirts34$12$6Shorts23$8$4Pants64$15$8Decision VariablesX1=number of shirts produced per weekX2=number of shorts produced per weekX3=number of pants produced per week Z=(12X1+8X2+15X3)-(6X1+4X2+8X3)-(200y1+150y2+100y3)=6X1+4X2+7X3 -200y1-150y2-100y3 Weekly Profits=Weekly Sales Revenue-Weekly Production Cost-Weekly Renting(Setup)CostObjective FunctionMath ModelMax Z=6X1+4X2+7X3 -200y1-150y2-100y3S.T.3X1+2X2+6X3 150 4X1+3X2+4X3 160 X1 ,X2 ,X3 integers y1 ,y2 ,y3 binaryConstraints:C1:At most 150 hours of labors can be used per week6X1+2X2+6X3=150C2:At most 160 units of cloth can be used per week4X1+3X2+4X3 0,then yi=1We have X1=M*y1X2=M*y2X3=1City 2 City 1,City 2,City 6X1+X2+X6=1City 3City 3,City 4 X3+X4 =1City 4City 3,City 4,City 5 X3+X4+X5=1City 5City 4,City 5,City 6 X4+X5+X6=1City 6City 2,City 5,City 6 X2+X5+X6=1Math ModelMin Z=X1+X2+X3 +X4+X5+X6S.T.X1+X2 1 1 X1+X2 +X6 1 1 X3 +X4 1 1 X3 +X4+X5 1 1 X4+X5+X6 1 1 X2 +X5+X6 1 1 X1 ,X2 ,X3,X4 ,X5 ,X6 binary 以LP求解得到：X1*=0X2*=1X3*=0X4*=1X5*=0 X6*=0With Z*=2專案選擇模型由一群二元變數表示”“go/no-go”的決定 模型中包含元件有:預算Budget空間Space優先順序Priority conditions補充範例四：專案選擇模型(見講義)(Project Selection Model)A市議會的目標是最大化選民之支持度下合理分派預算資料中包含成本costs,可利用資源,計畫優順序.A市議會專案選擇民調之結果X1X2X3X4X5X6X7X8X9A市議會專案選擇決策變數決策變數:Xj-一組二元決策變數；if a project j is selected(Xj=1)or not(Xj=0)for j=1,2,.,9目標函數目標函數:使經費之計畫總點數最大化限制式限制式:See the mathematical model.A市議會專案選擇 互斥性：警車與消防車購其一體育與音樂須在電腦設備購買前通過共同必要性：體育與音樂同時恢復或不恢復 最大預算不能超過$900,000 4個警察計畫中至多3個限制式通過 工作創造限制式：至少十個工作數量 The Mathematical Model(Xi=0,1 for i=1,2,9)Max 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整數規劃模式彙整1.二選一限制式(Either-Or Constraints)Either 6X1+2X2+6X3=150or X1+3X2+4X3=100 6X1+2X2+6X3=150 X1+3X2+4X3=100+M 6X1+2X2+6X3=150+My X1+3X2+4X3=100 +M(1-y)y=0 or 1 (y is called Auxiliary Variable)6X1+2X2+6X3=150+M X1+3X2+4X3 0,then yi=1 If Xi=0,then yi=0 i=1,2,3 4.兩工廠中只能選擇一個工廠 生產 (Either-or Constraints）Constraint Models X1 M y1 X2 M y2 X3 M y3 y1+y2+y3 23X1+4X2+2X3 30+M(1-y4)4X1+6X2+2X3 40+M(1-y5)y4+y5=1 Math ModelMax Z=5X1+7X2+3X3S.T.X1 7 X2 5 X3 9 X1 -M y1 0 X2 -M y2 0 X3 -M y3 0 y1+y2 +y3 2 3X1 +4X2 +2X3 30+M(1-y4)4X1 +6X2 +2X3 40+M(1-y5)y4 +y5 =1X1,X2 ,X3,integersy1 ,y2,y3,y4,y5 binaryTwo Fallacies of IP1.Having finite number of feasible solutions ensures that the problem is solvable?BIP with n variables 2n solutions to be considered Exponential Growth of the difficulty of the problemBest algorithms cannot be guaranteed to solve even relatively small problemsTwo Fallacies of IP(2)Removing feasible solutions for LP will make it easier to solve?All feasible solutions are corner-point feasible(CPF)solutions that are optimal for the overall problem.CPF is the key to the remarkable efficiency of the simplex methodComputational Difficulty for IPNumber of integer variablesAny special structure in the problemDefinition LP relaxation The LP problem obtained by omitting all integers or binary constraints on variables.Pitfalls for IPRounding may cause infeasibilityRounding solution will not be the optimal solutionSolution Methods for LIP1.Enumerations(Heuristic Algorithms)Try all possible computationsEfficient for large problemsCannot guarantee to find an optimal solutionMeta-heuristic e.g.Tabu Search,Simulated Annealing,Genetic Algorithm etc.al.Solution Methods for LIP2.Branch&Bound (i)Observation:if the optimal solution of the LP relaxation of a pure IP are integers,then the optimal solution for the LP relaxation is also optimal solution for the IP.Example 1 Max Z=3X1+2X2 s.t.2X1 +X2 6 X1,X2 0,integersOptimal solution for LP relaxation：X*1=0X*2=6With Z=12Optimal solution for IP problem：X*1=0X*2=6With Z=12Branch&Bound(Divide&Conquer)Example 2 Max Z=8X1+5X2 s.t.X1 +X2 6 9X1 +5X2 45 X1,X2 0,integersOptimal LP solution for LP relaxation(Sub-problem 1)：X*1=3.75X*2=2.25With Z=165/4Sub-problem 1t=1Sub-problem 2:Sub-problem 1+X1 4Sub-problem 3:Sub-problem 1+X1 3Optimal LP solution for LP relaxation(Sub-problem 2)：X*1=4X*2=9/5With Z=41t=2Sub-problem 4:Sub-problem 1+X1 4+X2 2Sub-problem 5:Sub-problem 1+X1 4+X2 1Optimal LP solution for LP relaxation(Sub-problem 4 is fathomed w with infeasible solution)t=3Optimal LP solution for LP relaxation(Sub-problem 5)X*1=40/9X*2=1With Z=365/9t=4t=4LIFO rules 作分枝動作Sub-problem 6:Sub-problem 5+X1 5Sub-problem 7:Sub-problem 5+X1 4Optimal LP solution for LP relaxation(Sub-problem 7)X*1=5X*2=0With Z=40 Fathomed with LB=37 40t=6t=5t=6Optimal LP solution for LP relaxation(Sub-problem 7)X*1=4X*2=1With Z=37Fathomed with Lower Bound(LB)=37t=5Candidate solution with LB=37Candidate solution with LB=40Sub-problem 3:Sub-problem 1+X1 3Optimal LP solution for LP relaxation(Sub-problem 3)X*1=3X*2=3With Z=39 LB=40Fathomed with Z LBt=7Branch&Bound(Conclusion)Step 1:If it is not necessary to branch on a sub-problem,it is fathomedFathomed Conditions:(1)Sub-problem is infeasible (2)Sub-problem yields an optimal solution (3)the optimal z-value for the sub-problem current LBStep 2:when to eliminate a sub-problem?The sub-problem is infeasibleThe z-value for the sub-problem current LBExample 3 (Knapsack Problem)Max Z=16X1+22X2+12X3+8X4 s.t.5X1 +7X2+4X3 +3X4 14 X1 ,X2 ,X 3 ,X4 binary X4=0 Branching on sub-problem 9 could never yield a z-value greater than LB=42Optimal Solution