Lecture 3 Classic LP Examples.ppt
《Lecture 3 Classic LP Examples.ppt》由会员分享,可在线阅读,更多相关《Lecture 3 Classic LP Examples.ppt(35页珍藏版)》请在麦多课文档分享上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LECTURE3CLASSICLPEXAMPLESPPT
