Example 2: Fixed Charge ProblemExample 2: Fixed Charge Problem – contd.Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Example Fixed-Charge Problem:Defining the Objective FunctionDefining the Decision VariablesDefining the ConstraintsDefining the Constraints (cont’d)Finding Reasonable Values for M1Summary of the ModelExample 2: Fixed Charge ProblemA telecom company wants to offer new services to its customers. Each service can be offered in different amounts (e.g., with different bandwidth). The goal is to decide how much of each service is to be offered to maximize the total profit, such that the total cost remains within a given budget.The following information is available to formulate the problem:1Example 2: Fixed Charge Problem – contd.There are N potential services.If service i is offered, then it incurs a cost of ci per unit amount of service, plus a fixed charge ki; which is independent of the amount.Service i brings a profit of pi per unit amount of offered service.The total available budget is C:2Example 2: Fixed Charge Problem – contd.3Example 2: Fixed Charge Problem – contd.4Example 2: Fixed Charge Problem – contd.5Example 2: Fixed Charge Problem – contd.6Example 2: Fixed Charge Problem – contd.7Example 2: Fixed Charge Problem – contd.What will be the optimal solution, if the company decides to offer only a single service? (But we do not know in advance, which one will be the offered service.)Solution:Let i be the service that the company offers. Then the total profit will be pixi, as for all j ≠ i we have xj = 0: For any given i, the profit will be maximum, if xi is as large as possible. Since there is no other service in the considered case, therefore, service i will use the entire available budget C.This meanscixi + ki = C(Since obviously xi > 0 in this case, therefore, the fixed charge will be there.)8Example 2: Fixed Charge Problem – contd.9Example Fixed-Charge Problem:10Hours Required By:Operation Prod. 1 Prod. 2 Prod. 3 Hours AvailableMachining 2 3 6 600Grinding 6 3 4 300Assembly 5 6 2 400Unit Profit $48 $55 $50Setup Cost $1000 $800 $900Defining the Objective Function11Maximize total profit.MAX: 48X1 + 55X2 + 50X3 – 1000Y1 – 800Y2 – 900Y3Defining the Decision VariablesXi = the amount of product i to be produced, i = 1, 2, 3123 2, 1,= 0X if 0,0X if ,1Y iiiiDefining the Constraints13Resource Constraints2X1 + 3X2 + 6X3 <= 600 } machining6X1 + 3X2 + 4X3 <= 300 } grinding5X1 + 6X2 + 2X3 <= 400 } assemblyBinary ConstraintsAll Yi must be binaryNonnegativity conditionsXi >= 0, i = 1, 2, ..., 6Is there a missing link?Defining the Constraints (cont’d)14Linking Constraints (with “Big M”)X1 <= M1Y1or X1 - M1Y1 <= 0X2 <= M2Y2 or X2 - M2Y2 <= 0X3 <= M3Y3or X3 - M3Y3 <= 0If Xi > 0 these constraints force the associated Yi to equal 1.If Xi = 0 these constraints allow Yi to equal 0 or 1, but the objective will cause Solver to choose 0.Note that Mi imposes an upper bounds on Xi.It helps to find reasonable values for the Mi.Finding Reasonable Values for M115Consider the resource constraints2X1 + 3X2 + 6X3 <= 600 } machining6X1 + 3X2 + 4X3 <= 300 } grinding5X1 + 6X2 + 2X3 <= 400 } assemblyWhat is the maximum value X1 can assume? Let X2 = X3 = 0X1 = MIN(600/2, 300/6, 400/5) = MIN(300, 50, 80) = 50Maximum values for X2 & X3 can be found similarly.Summary of the Model16MAX: 48X1 + 55X2 + 50X3 - 1000Y1 - 800Y2 - 900Y3S.T.: 2X1 + 3X2 + 6X3 <= 600 } machining6X1 + 3X2 + 4X3 <= 300 } grinding5X1 + 6X2 + 2X3 <= 400 } assembly X1 - 50Y1 <= 0 X2 - 67Y2 <= 0 linking constraintsX3 - 75Y3 <= 0All Yi must be binaryXi >= 0, i = 1, 2,
View Full Document
Unlocking...