More Linear Programming ModelsOverviewSlide 3Slide 4Scheduling Postal WorkersFormulating as an LPThe linear programOn the selection of decision variablesSome Enhancements of the ModelSlide 10Slide 11What is the Revised Linear Program?PowerPoint PresentationAnother EnhancementSlide 15Slide 16Slide 17A non-linear objective that often can be made linear.Slide 19Another non-linear objective that often can be made linear.Slide 21Slide 22A ratio constraint:Other enhancementsSlide 25Math Programming and Radiation TherapyRadiation Therapy OverviewSlide 28Conventional RadiotherapySlide 30Slide 31Goal: maximize the dose to the tumor while minimizing dose to the critical areaRecent AdvancesTomotherapy: a diagramRadiation Therapy: Problem StatementDisplay of radiation levelsLinear Programming ModelMore on the LPLinear ProgramAn LP modelWhat to do if there is no feasible solutionOptimal Solution for the LPAn Optimal Solution to an NLPFurther considerationsThe pigskin problem (from Practical Management Science)The pigskin problem (continued)On the formulationMIT and James Orlin © 20031More Linear Programming ModelsMIT and James Orlin © 20032OverviewApplications–personnel scheduling–radiation therapy–production and inventory managementGoals–get practice in recognizing and modeling linear constraints (and non-linear constraints)–use of models in practiceMIT and James Orlin © 20033Overview5 in 7 scheduling problem–The model–Practical enhancements or modifications–Two non-linear objectives that can be made linear–A non-linear constraint that can be made linearRadiation treatments and Math Programming–Overview of how math programming arises in radiation treatment design–Formulation as math programs–Discussion issuesMIT and James Orlin © 20034Overview5 in 7 scheduling problem–The modelMIT and James Orlin © 20035Scheduling Postal WorkersEach postal worker works for 5 consecutive days, followed by 2 days off, repeated weekly.Day Mon Tues Wed Thurs Fri Sat Sun Demand 17 13 15 19 14 16 11 Minimize the number of postal workers (for the time being, we will permit fractional workers on each day.)MIT and James Orlin © 20036Formulating as an LPSelect the decision variables–Let x1 be the number of workers who start working on Monday, and work till Friday–Let x2 be the number of workers who start on Tuesday …–Let x3, x4, …, x7 be defined similarly.MIT and James Orlin © 20037The linear programMinimize z = x1 + x2 + x3 + x4 + x5 + x6 + x7subject tox1 + x4 + x5 + x6 + x7  17Day Mon Tues Wed Thurs Fri Sat Sun Demand 17 13 15 19 14 16 11 x1 + x2 + x5 + x6 + x7  13 x1 + x2 + x3 + x6 + x7  15 x1 + x2 + x3 + x4 + x7  19 x1 + x2 + x3 + x4 + x5  14 x2 + x3 + x4 + x5 + x6  16 x3 + x4 + x5 + x6 + x7  11 xj  0 for j = 1 to 7MIT and James Orlin © 20038On the selection of decision variablesWould it be possible to have yj be the number of workers on day j?–Workers on day j is at least dj. –Each worker works 5 days on followed by 2 days off.Conclusion: sometimes the decision variables incorporate constraints of the problem. –Hard to do this well, but worth keeping in mind–We will see more of this in integer programming.MIT and James Orlin © 20039Some Enhancements of the ModelSuppose that there was a pay differential. The cost of workers who start work on day j is cj per worker. Minimize z = c1 x1 + c2 x2 + c3 x3 + … + c7 x7MIT and James Orlin © 200310Overview5 in 7 scheduling problem–The model–Practical enhancements or modificationsMIT and James Orlin © 200311Some Enhancements of the ModelSuppose that one can hire part time workers (one day at a time), and that the cost of a part time worker on day j is PTj.Let yj = number of part time workers on day jMIT and James Orlin © 200312What is the Revised Linear Program?subject tox1 + x4 + x5 + x6 + x7  17x1 + x2 + x5 + x6 + x7  13 x1 + x2 + x3 + x6 + x7  15 x1 + x2 + x3 + x4 + x7  19 x1 + x2 + x3 + x4 + x5  14 x2 + x3 + x4 + x5 + x6  16 x3 + x4 + x5 + x6 + x7  11 xj  0 for j = 1 to 7z = x1 + x2 + x3 + x4 + x5 + x6 + x7MinimizeMIT and James Orlin © 200313Minimize z = x1 + x2 + x3 + x4 + x5 + x6 + x7subject tox1 + x4 + x5 + x6 + x7 + y1  17x1 + x2 + x5 + x6 + x7 + y2  13 x1 + x2 + x3 + x6 + x7 + y3  15 x1 + x2 + x3 + x4 + x7 + y4  19 x1 + x2 + x3 + x4 + x5 + y5  14 x2 + x3 + x4 + x5 + x6 + y6  16 x3 + x4 + x5 + x6 + x7 + y7  11 xj  0 , yj  0 for j = 1 to 7+ PT1 y1 + PT2 y2 + … + PT7 y7MIT and James Orlin © 200314Another EnhancementSuppose that the number of workers required on day j is dj. Let yj be the number of workers on day j. What is the minimum cost schedule, where the “cost” of having too many workers on day j is -fj(yj – dj), which is a non-linear function?NOTE: this will lead to a non-linear program, not a linear program.We will let sj = yj – dj be the excess number of workers on day j.MIT and James Orlin © 200315What is the Revised Linear Program?subject tox1 + x4 + x5 + x6 + x7  17x1 + x2 + x5 + x6 + x7  13 x1 + x2 + x3 + x6 + x7  15 x1 + x2 + x3 + x4 + x7  19 x1 + x2 + x3 + x4 + x5  14 x2 + x3 + x4 + x5 + x6  16 x3 + x4 + x5 + x6 + x7  11 xj  0 for j = 1 to 7z = x1 + x2 + x3 + x4 + x5 + x6 + x7MinimizeMIT and James Orlin © 200316Minimizez = f1(s1) + f2(s2) + f3(s3) + f4(s4) + f5(s5) + f6(s6) + f7(s7)subject tox1 + x4 + x5 + x6 + x7 - s1 = 17x1 + x2 + x5 + x6 + x7 - s2 = 13 x1 + x2 + x3 + x6 + x7 - s3 = 15 x1 + x2 + x3 + x4 + x7 - s4 = 19 x1 + x2 + x3 + x4 + x5 - s5 = 14 x2 + x3 + x4 + x5 + x6 - s6 = 16 x3 + x4 + x5 + x6 + x7 - s7 = 11 xj  0 , sj  0 for j = 1