1、Lecture 3 Classic LP Examples,Topics Employee scheduling problem Energy distribution problem Feed mix problem Cutting stock problem Regression analysis Model Transformations,Macrosoft has a 24-hour-a-day, 7-days-a-week toll free hotline that is being set up to answer questions regarding a new produc
2、t. The following table summarizes the number of full-time equivalent employees (FTEs) that must be on duty in each time block.,Interval,Time,FTEs,1,0-4,15,2,4-8,10,3,8-12,40,4,12-16,70,5,16-20,40,6,20-0,35,Employee Scheduling,Macrosoft may hire both full-time and part-time employees. The former work
3、 8-hour shifts and the latter work 4-hour shifts; their respective hourly wages are $15.20 and $12.95. Employees may start work only at the beginning of 1 of the 6 intervals. Part-time employees can only answer 5 calls in the time a full-time employee can answer 6 calls. (i.e., a part-time employee
4、is only 5/6 of a full-time employee.) At least two-thirds of the employees working at any one time must be full-time employees.,Formulate an LP to determine how to staff the hotline at minimum cost.,Constraints for Employee Scheduling,Decision Variables,xt = # of full-time employees that begin the d
5、ay at the start of interval t and work for 8 hours yt = # of part-time employees that are assigned interval t,x1 + x6,2,3,2,3,.,.,.,2,3,xt 0, yt 0 t =1,2,6,At least 2/3 workers must be full time,More constraints:,Nonnegativity,(x6 + x1 + y1),x1 + x2,(x1 + x2 + y2),(x5 + x6 + y6),x5 + x6,An agricultu
6、ral mill produces a different feed for cattle, sheep, and chickens by mixing the following raw ingredients: corn, limestone, soybeans, and fish meal.These ingredients contain the following nutrients: vitamins, protein, calcium, and crude fat in the following quantities:,Ingredient, i,Vitamins,Protei
7、n,Calcium,Crude Fat,Corn,8,10,6,8,Limestone,6,5,10,6,Soybeans,10,12,6,6,Fish Meal,4,18,6,9,Let aik = quantity of nutrient k per kg of ingredient i,Nutrient, k,Feed Mix Problem,The mill has (firm) contracts for the following demands.,Demand (kg),Cattle,Sheep,Chicken,10,000,6,000,8,000,There are limit
8、ed availabilities of the raw ingredients.,Supply (kg),Corn,Limestone,Soybeans,Fish Meal,6,000,10,000,4,0,00,5,000,The different feeds have “quality” bounds per kilogram.,Vitamins,Protein,Calcium,Crude fat,min max,min max,min max,min max,Cattle,6 -,6 -,7 -,4 8,Sheep,6 -,6 -,6 -,4 8,Chicken,4 6,6 -,6
9、-,4 8,si,dj,The above values represent bounds: ljk and ujk,Constraints,Cost per kg of the raw ingredients is as follows:,Corn,Limestone,Soybeans,Fish meal,cost/kg, ci,20,12,24,12,Formulate problem as a linear program whose solution yields desired feed production levels at minimum cost.,Indices/sets,
10、i I,ingredients corn, limestone, soybeans, fish meal ,j J,products cattle, sheep, chicken feeds ,k K,nutrients vitamins, protein, calcium, crude fat ,Costs and Notation,Data,dj,demand for product j (kg),si,supply of ingredient i (kg),ljk,lower bound on number of nutrients of type k per kg of product
11、 j,upper bound on number of nutrients of type k per kg of product j,cost per kg of ingredient i,aik,number of nutrients k per kg of ingredient i,Decision Variables,xij,amount (kg) of ingredient i used in producing product j,ujk,ci,min,cixij,s.t.,xij 0,xij = dj,xij si,“ j J,iI,jJ,iI,“ i I,jJ,“ i I, j
12、 J,LP Formulation of Feed Mix Problem,Raw Materials,Qualities,Blended commodities,corn, limestone,soybeans, fish meal,protein, vitamins,calcium, crude fat,feed,butane, catalytic,reformate,heavy naphtha,octane, volatility,vapor pressure,gasoline,pig iron,ferro-silicon,carbide, various,alloys,carbon,m
13、anganese,chrome content,metals,2 raw ingredients,1 quality,1 commodity,Generalization of feed Mix Problem Gives Blending Problems,Three special orders for rolls of paper have been placed at a paper mill. The orders are to be cut from standard rolls of 10 and 20 widths.,Order,Width,Length,1,5,10,000,
14、2,7,30,000,3,9,20,000,Assumption: Lengthwise strips can be taped togetherGoal: Throw away as little as possible,Trim-Loss or Cutting Stock problem,Problem: What is trim-loss?,Decision variables: xj = length of roll cut using pattern, j = 1, 2, ?,7,10,9,5,5,20,5000,10,roll,20,roll,x1,5,2,0,0,4,2,2,1,
15、0,0,7,0,1,0,0,1,0,2,1,0,9,0,0,1,0,0,1,0,1,2,Trim loss,0,3,1,0,3,1,1,4,2,x2,x3,x4,x5,x6,x7,x8,x9,Patterns Possible,Minimize Trim Loss + Overproduction,min,z =,3x2,+,x3,+,3x5,+ x6,+ x7,+,4x8,+ 5y1 + 7y2 + 9y3,s.t.,2x1,+,4,x4,+,2x5,+ 2x6,+ x7 y1,=,10,000,x2,+,x5,+,2x7,+ x8, y2,=,30,000,x3,+,x6,+,x8,+ 2
16、x9, y3,=,20,000,xj 0, j = 1,9; yi 0, i = 1, 2, 3,where yi is overproduction of width i,+ 2x9,Alternative Formulation,Minimizing Piecewise Linear Convex Functions,Definition of convexity Examples of objective functions1. f (x) = maxk=1,p (ckx + dk)2. f (x) = j=1,n cj|xj|, cj 0 for all j3. f (x) = sep
17、arable, piecewise linear, convex,Definition of a Convex/Concave Function,A function f : n is called convex if for every x and y n, and every 0,1, we have f (x + (1 )y) f (x) + (1 )f (y)A function f : n is called concave if for every x and y n, and every 0,1, we have f (x + (1 )y) f (x) + (1 )f (y)If
18、 f (x) is convex, then f (x) is concave,Minimizing the Maximum of Several Affine Functions,Problem: min maxk=1,p (ckx + dk)s.t. Ax bTransformed problem:min zs.t. z ckx + dk, k = 1,pAx b,x,f(x) = max,Problems Involving Absolute Values: Minimizing the L1-Norm,Problem: min j=1,n cj|xj|, cj 0 for all js
19、.t. Ax b,Data Fitting Example,Problem: We are given p data points of the form (ak, bk), k = 1,p, where ak n and bk , and wish to build a model that predicts the value of the variable b from knowledge of the vector a. Assume a linear model: b = ax + x0, where (x, x0) is a parameter vector to be deter
20、mined. Error: Given a particular values of (x, x0), the residual (predictive error) at the k th data point is defined by |akx + x0 bk|. Objective: Find values of (x, x0) that best explain the available data; i.e., minimize the error.,Data Fitting Example (contd),Model 1: Minimize the largest residua
21、l min maxk |akx + x0 bk|Transformed model 1: min zs.t. z akx + x0 bk , k = 1,pz akx x0 + bk , k = 1,pModel 2: Minimize the sum of residuals min k=1,p |akx + x0 bk| Transformed model 2: min k=1,p zks.t. zk akx + x0 bk , k = 1,pzk akx x0 + bk , k = 1,p,Data (a,b) = (1,2) , (3,4) , (4,7) ,We want to “f
22、it” a linear function b = ax + x0 to these data points; i.e., we have to choose optimal values for x and x0.,7,6,5,4,3,2,1,1 2 3 4 5,b,a,Constrained Regression,Objective: Find parameters x and x0 that minimize the maximum absolute deviation between the data ak and the fitted line bk = akx + x0.,bk,a
23、nd,bk,In addition, were going to impose a priori knowledge that the,slope of the line must be positive. (We dont know about the intercept.),Decision variables,x = slope of line,known to be positive,x0 = b-intercept,positive or negative,observed value,Predicted value,Let z = max |bk - bk| : k = 1, 2,
24、 3 ,Optimization model:,min z,where bk = akx + x0,Objective function:,s.t. z |bk - bk|, k = 1, 2, 3,min max |bk - bk| : k = 1, 2, 3 ,Nonlinear constraints:,b1,-,b1,=, 1x + x0 2 ,b2,-,b2,=, 3x + x0 4 ,b3,-,b3,=, 4x + x0 7 ,z ,z ,z ,Letting x0 = x0+ - x0-, x0+ 0, x0- 0, we finally get ,min z,s.t.,x +
25、x0+ - x0- - z,x, x0+, x0-, z 0, x x0+ x0- - z,3x + x0+ - x0- - z,- 3x - x0+ x0- - z,4x + x0+ - x0- - z,- 4x - x0+ x0- - z,Separable Piecewise Linear Functions,Model: min f (x) = f1(x1) + f2(x2) + . . . + fp(xp) For each xj we are given r break points: 0 aj1 aj2 . . . ajr Let cjt be the slope in the
26、interval aj,t-1 xj ajt for t =1,r+1, where aj0= 0 and aj,r+1 = Let yjt be the portion of xj lying in the tth interval, t = 1,r+1,xj,aj1,aj2,ajr,fj(xj),aj,r-1,0,Transformation for fj(xj),Let xj = yj1 + yj2 + . . . + yj,r+1 Model:min cj1yj1 + cj2yj2 + . . . + cj,r+1 yj,r+1 + f1(x1) + . . .s.t. 0 yj1 a
27、j10 yj2 aj2 aj1. . .0 yjr ajr aj,r-10 yj,r+1and for every t, if yjt 0, then each yjk is equal to its upper bound ajk aj,k-1, for all k t.,Austin Municipal Power and Light (AMPL) would like to determine optimal operating levels for their electric generators and associated distribution patterns that w
28、ill satisfy customer demand. Consider the following prototype system,Plants,The two plants (generators) have the following (nonlinear) efficiencies:,Plant 1, 0, 6 MW, 6MW, 10MW,Unit cost ($/MW),$10,$25,Plant 2, 0, 5 MW,5MW, 11MW,Unit cost ($/MW),$8,$28,For plant 1, e.g., if you generate at a rate of
29、 8MW (per sec), then the cost ($) is = ($10/MW)(6MW) + ($25/MW)(2MW) = $110.,2,1,3,2,1,Demand sectors,Demand requirements,4 MW,7 MW,6 MW,Energy Generation Problem (with piecewise linear objective),Formulate an LP that, when solved, will yield optimal power generation and distribution levels.,Decisio
30、n Variables,= power generated at plant,1 at operating level 1,1,2,x21,2,1,x22,2,2,= power sent from plant,1 to demand sector 1,1 ,2,1,3,2,1,2,2,2,3,Problem Statement and Notation,w11,w12,w13,w21,w22,w23,x11,x12,Formulation,min,10x11 + 25x12 + 8x21 + 28x22,s.t.,w,11,+,w,12,+,w,13,w,21,+,w,22,+,w,23,w
31、,11,+,w,21,= 4,w,12,+,w,22,= 7,w,13,+,w,23,= 6,0 x11 6, 0 x12 4 0 x21 5, 0 x22 6 w11, w12, w13, w21, w22, w32 0,Note that we can model the nonlinear operating costs as an LP only because the efficiencies have the right kind of structure. In particular, the plant is less efficient (more costly) at hi
32、gher operating levels. Thus the LP solution will automatically select level 1 first.,= x11 + x12,= x21 + x22,Flow balance,Demand,The above formulation can be generalized for any number of plants, demand sectors, and generation levels.,Indices/Sets,i I,plants,demand sectors,generation levels,Data,Cik
33、 = unit generation cost ($/MW) for plant i at level k,uik = upper bound (MW) for plant i at level k,dj = demand (MW) in sector j,Decision Variables,xik = power (MW) generated at plant i at level k,wij = power (MW) sent from plant i to sector j,j J,k K,General Formulation of Power Distribution Proble
34、m,min,s.t.,wij,=,cikxik,xik, xik uik “ i I, k K0 wij “ i I, j J,wij = dj,kK,iI,kK,jJ,“ i I,“ j J,iI,General Network Formulation,Model Transformations,Direction of optimization:Minimize c1x1 + c2x2 + + cnxn Maximize c1x1 c2x2 cnxn,Unrestricted variables: xj = y1j y2j where y1j 0, y2j 0,Constant term
35、in objective function ignore,Nonzero lower bounds on variables: xj lj replace with xj = yj + lj where yj 0,Nonpositive variable: xj 0 replace with xj = yj where yj 0,What You Should Know About LP Problems,How to formulate various types of problems. Difference between continuous and integer variables. How to find solutions. How to transform variables and functions into the standard form.,
