18Chapter1WhatisOptimization?The graph of the function appears in Figure 1.12Figure1.12ANonconvexFunction:sin(x)+.5*abs(x-9.5)65(s'6-x)sqe*s* + (x)uls4321092468101214-1xIf you apply a traditional nonlinear solver to this model you might get one of three solutions: either x0,or x=5.235987,orx=10.47197.If you check theGlobal solveroption inLINGO,itwillreportthe solution x=10.47197and label it as a global optimum.Beforewarned that theglobal solver doesnot eliminatedrawback (a),namely,nonlinearmodels may takea long time to solvetoguaranteedoptimality.Nevertheless, theglobal solver maygivea verygood, even optimal, solution veryquicklybutthentakealongtimetoprovethatthereisnootherbettersolution1.10Problems1.Your firm produces two products,Thyristors ()and Lozenges (L),that compete for the scarceresources of your distribution system.For the next planning period, your distribution system hasavailable 6,o00 person-hours. Proper distribution of each T requires 3 hours and each L requires2hours.The profit contributions per unit are 40 and 30 for Tand L, respectively.Product lineconsiderationsdictatethatatleast1Tmustbesoldforeach2L's.(a)Draw thefeasible region and draw the profit line that passes through the optimum point.(b)Bysimplecommonsensearguments,whatistheoptimal solution?
18 Chapter 1 What is Optimization? The graph of the function appears in Figure 1.12. If you apply a traditional nonlinear solver to this model you might get one of three solutions: either x = 0, or x = 5.235987, or x = 10.47197. If you check the Global solver option in LINGO, it will report the solution x = 10.47197 and label it as a global optimum. Be forewarned that the global solver does not eliminate drawback (a), namely, nonlinear models may take a long time to solve to guaranteed optimality. Nevertheless, the global solver may give a very good, even optimal, solution very quickly but then take a long time to prove that there is no other better solution. 1.10 Problems 1. Your firm produces two products, Thyristors (T) and Lozenges (L), that compete for the scarce resources of your distribution system. For the next planning period, your distribution system has available 6,000 person-hours. Proper distribution of each T requires 3 hours and each L requires 2 hours. The profit contributions per unit are 40 and 30 for T and L, respectively. Product line considerations dictate that at least 1 T must be sold for each 2 L’s. (a) Draw the feasible region and draw the profit line that passes through the optimum point. (b) By simple common sense arguments, what is the optimal solution? Figure 1.12 A Nonconvex Function: sin(x)+.5*abs(x-9.5) -1 0 1 2 3 4 5 6 0 2 4 6 8 10 12 14 x sin(x) + .5*abs(x-9.5)
19WhatisOptimization?Chapter12.Graph thefollowing LP problem:Minimize4X+6Ysubject to5X+2Y≥123X+7Y≥13X≥0,Y≥0.Inaddition,plot theline4X+6Y=18and indicate the optimumpoint.3.TheVolkswagen Companyproduces twoproducts,theBug and the SuperBug,which shareproduction facilities. Raw materials costs are S600 per car for the Bug and $750 per car for theSuperBug.The Bug requires 4hours in the foundry/forge area per car; whereas, the SuperBug,because it uses newer more advanced dies, requires only 2 hours in the foundry/forge. The Bugrequires 2 hours per car in the assembly plant; whereas, the SuperBug, because it is a morecomplicated car,requires 3hoursper car in the assembly plant.Theavailable daily capacities inthe two areas are160 hours in thefoundry/forge and 180 hours in the assembly plant.Note,ifthere are multiple machines, the total hours available per day may be greater than 24. The sellingprice of the Bug at the factory door is $4800. It is $5250 for the SuperBug. It is safe to assumewhatevernumberofcars areproducedbythis factory can be sold.(a)Write the linearprogramformulation of thisproblem.(b) The above description implies the capacities of the two departments (foundry/forge andassembly) are sunk costs. Reformulate the LP under the conditions that each hour offoundry/forge time cost $90; whereas, eachhour of assembly time cost S60.Thecapacities remain as before. Unused capacity has no charge.4.The Keyesport Quarry has two different pits from which it obtains rock.The rock is run through acrusher to produce two products: concrete grade stone and road surface chat.Each ton of rockfrom the South pit converts into 0.75 tons of stone and 0.25 tons of chat when crushed.Rock fromthe North pit is of different quality.When it is crushed, it produces a"50-50"split of stone andchat.The Quarry has contracts for 60 tons of stone and 40 tons of chat this planning period.Thecost per ton of extracting and crushing rock from the South pit is1.6times as costly as from theNorth pit.(a)Whatarethedecisionvariables intheproblem?(b)There aretwoconstraintsforthis problem.Statethem in words.Graph the feasible region for this problem.()(d)Draw an appropriate objective function line on the graph and indicate graphically andnumericallytheoptimal solution.Suppose all the information given in the problem description is accurate. What additional(e)information might you wish to know before having confidence in this model?5.A problem faced by railroads is of assembling engine sets for particular trains. There are threeimportant characteristics associated with each engine type, namely, operating cost per hour,horsepower, and tractive power. Associated with each train (e.g., the Super Chief run fromChicago to Los Angeles) is a required horsepower and a required tractive power.The horsepowerrequired depends largely upon the speed required by the run; whereas, the tractive power requireddepends largely upon the weight of the train and the steepness of the grades encountered on therun.For a particular train, the problem is to find that combination of engines that satisfies thehorsepower andtractive powerrequirements at lowest cost
What is Optimization? Chapter 1 19 2. Graph the following LP problem: Minimize 4X + 6Y subject to 5X + 2Y t 12 3X + 7Y t 13 X t 0, Y t 0. In addition, plot the line 4X + 6Y = 18 and indicate the optimum point. 3. The Volkswagen Company produces two products, the Bug and the SuperBug, which share production facilities. Raw materials costs are $600 per car for the Bug and $750 per car for the SuperBug. The Bug requires 4 hours in the foundry/forge area per car; whereas, the SuperBug, because it uses newer more advanced dies, requires only 2 hours in the foundry/forge. The Bug requires 2 hours per car in the assembly plant; whereas, the SuperBug, because it is a more complicated car, requires 3 hours per car in the assembly plant. The available daily capacities in the two areas are 160 hours in the foundry/forge and 180 hours in the assembly plant. Note, if there are multiple machines, the total hours available per day may be greater than 24. The selling price of the Bug at the factory door is $4800. It is $5250 for the SuperBug. It is safe to assume whatever number of cars are produced by this factory can be sold. (a) Write the linear program formulation of this problem. (b) The above description implies the capacities of the two departments (foundry/forge and assembly) are sunk costs. Reformulate the LP under the conditions that each hour of foundry/forge time cost $90; whereas, each hour of assembly time cost $60. The capacities remain as before. Unused capacity has no charge. 4. The Keyesport Quarry has two different pits from which it obtains rock. The rock is run through a crusher to produce two products: concrete grade stone and road surface chat. Each ton of rock from the South pit converts into 0.75 tons of stone and 0.25 tons of chat when crushed. Rock from the North pit is of different quality. When it is crushed, it produces a “50-50” split of stone and chat. The Quarry has contracts for 60 tons of stone and 40 tons of chat this planning period. The cost per ton of extracting and crushing rock from the South pit is 1.6 times as costly as from the North pit. (a) What are the decision variables in the problem? (b) There are two constraints for this problem. State them in words. (c) Graph the feasible region for this problem. (d) Draw an appropriate objective function line on the graph and indicate graphically and numerically the optimal solution. (e) Suppose all the information given in the problem description is accurate. What additional information might you wish to know before having confidence in this model? 5. A problem faced by railroads is of assembling engine sets for particular trains. There are three important characteristics associated with each engine type, namely, operating cost per hour, horsepower, and tractive power. Associated with each train (e.g., the Super Chief run from Chicago to Los Angeles) is a required horsepower and a required tractive power. The horsepower required depends largely upon the speed required by the run; whereas, the tractive power required depends largely upon the weight of the train and the steepness of the grades encountered on the run. For a particular train, the problem is to find that combination of engines that satisfies the horsepower and tractive power requirements at lowest cost
20Chapter1WhatisOptimization?In particular, consider the Cimarron Special, the train that runs from Omaha to Santa Fe.Thistrain requires 12,000 horsepower and 50,000 tractive power units. Two engine types, the GM-Iand the GM-Il, are availablefor pulling this train.The GM-Ihas 2,o0ohorsepower,10,000 tractive power units, and its variable operating costs are S150 per hour.The GM-1I has3,000 horsepower, 10,000 tractive power units, and its variable operating costs are s180 per hour.The engine set may be mixed (e.g., use two GM-I's and three GM-I's).Write the linear program formulation of this problem.6.Graph the constraint lines and the objective function line passing through the optimum point andindicate thefeasible region for the Enginola problem when:(a)All parameters are as given except labor supply is 70 rather than 120.(b)All parameters are as given originally except the variable profit contribution of a Cosmois $40 instead of $30.7.5Consider the problem:Minimize4xi + 3x22x + X2 ≥ 10Subject to3x1 + 2x2 ≤ 6XI+ X2≥6x≥0,X2≥0Solve the problem graphically.8.The surgical unit of a small hospital is becoming more concerned about finances.The hospitalcannot control or set many of the important factors that determine its financial health.Forexample, the length of stay in the hospital for a given type of surgery is determined in large partby government regulation.The amount that can be charged for a given type of surgical procedureis controlled largely by the combination of the market and government regulation.Most of thehospital'ssurgicalproceduresareelective,sothehospitalhasconsiderablecontroloverwhichpatients and associated procedures are attracted and admitted to the hospital.The surgical unit haseffectively two scarce resources, the hospital beds available to it (70 in a typical week),and thesurgical suite hours available (165 hours in a typical week). Patients admitted to this surgical unitcan be classified into thefollowing three categories:SurgicalSuite HoursFinancialNeededPatientTypeDays of StayContribution32A$2405B1.5$225C63$425
20 Chapter 1 What is Optimization? In particular, consider the Cimarron Special, the train that runs from Omaha to Santa Fe. This train requires 12,000 horsepower and 50,000 tractive power units. Two engine types, the GM-I and the GM-II, are available for pulling this train. The GM-I has 2,000 horsepower, 10,000 tractive power units, and its variable operating costs are $150 per hour. The GM-II has 3,000 horsepower, 10,000 tractive power units, and its variable operating costs are $180 per hour. The engine set may be mixed (e.g., use two GM-I's and three GM-II's). Write the linear program formulation of this problem. 6. Graph the constraint lines and the objective function line passing through the optimum point and indicate the feasible region for the Enginola problem when: (a) All parameters are as given except labor supply is 70 rather than 120. (b) All parameters are as given originally except the variable profit contribution of a Cosmo is $40 instead of $30. 7. Consider the problem: Minimize 4x1 + 3x2 Subject to 2x1 + x2 t 10 3x1 + 2x2 d 6 x1 + x2 t 6 x1 t 0, x2 t 0 Solve the problem graphically. 8. The surgical unit of a small hospital is becoming more concerned about finances. The hospital cannot control or set many of the important factors that determine its financial health. For example, the length of stay in the hospital for a given type of surgery is determined in large part by government regulation. The amount that can be charged for a given type of surgical procedure is controlled largely by the combination of the market and government regulation. Most of the hospital’s surgical procedures are elective, so the hospital has considerable control over which patients and associated procedures are attracted and admitted to the hospital. The surgical unit has effectively two scarce resources, the hospital beds available to it (70 in a typical week), and the surgical suite hours available (165 hours in a typical week). Patients admitted to this surgical unit can be classified into the following three categories: Patient Type Days of Stay Surgical Suite Hours Needed Financial Contribution A 3 2 $240 B 5 1.5 $225 C 6 3 $425
21WhatisOptimization?Chapter1For example, each type B patient admitted will use (i)5 days of the 7 × 70 = 490 bed-daysavailable each week, and (i) 1.5 hours of the 165 surgical suite hours available each week.Onedoctor has argued that the surgical unit should try to admit more type A patients. Her argument isthat, "in terms of S/days of stay,type A is clearly the best, while in terms of S/(surgical suite hour),itisnotmuchworsethanBandC."Suppose the surgical unit can in fact control the number of each type of patient admitted eachweek (i.e.,they aredecision variables).Howmany ofeach type should beadmitted each week?Canyouformulate itas anLP?
What is Optimization? Chapter 1 21 For example, each type B patient admitted will use (i) 5 days of the 7 u 70 = 490 bed-days available each week, and (ii) 1.5 hours of the 165 surgical suite hours available each week. One doctor has argued that the surgical unit should try to admit more type A patients. Her argument is that, “in terms of $/days of stay, type A is clearly the best, while in terms of $/(surgical suite hour), it is not much worse than B and C.” Suppose the surgical unit can in fact control the number of each type of patient admitted each week (i.e., they are decision variables). How many of each type should be admitted each week? Can you formulate it as an LP?
2Solving Math Programs withLINGO2.1 IntroductionThe process of solving a math program requires a large number of calculations and is, therefore, bestperformed by a computer program. The computer program we will use is called LINGO. The mainpurpose of LINGOisto allow ausertoquicklyinputa modelformulation,solve it,assess thecorrectness or appropriateness of the formulation based on the solution, quickly make minormodifications to the formulation, and repeat the process. LINGO features a wide range of commands,anyof which may be invoked atanytime.LINGOcheckswhether aparticular command makes senseinaparticularcontextLINGO is available in two versions:1)a Windows-specific version, and2)a generic, text-based version.The text-based version runs under most popular operating systems, including Unix and Linux. Foreither version, additional information is availableto the user underthe Help menu item or Helpcommand.TheWindowscommandsarecoveredbrieflyhere.Afterthecommandssection.wewilshowyou howto enterand solvea simplemodel2.2LINGOforWindowsWhen LINGO for Windows starts, it opens a blank window known as a Model Window. The ModelWindow is whereyou“"do all yourwork".Output inLINGO is displayed in a Report Window.LINGOcan generate a number of reports pertaining to your model.The following is a list of all the commandsthat are available to you,mainly in themodel window.2.2.1 File MenuNEWF2DUse the NEW command from the File menu, press F2, or use the button to create a new Modelwindow.In theModel window,you can enter your model.23
23 2 Solving Math Programs with LINGO 2.1 Introduction The process of solving a math program requires a large number of calculations and is, therefore, best performed by a computer program. The computer program we will use is called LINGO. The main purpose of LINGO is to allow a user to quickly input a model formulation, solve it, assess the correctness or appropriateness of the formulation based on the solution, quickly make minor modifications to the formulation, and repeat the process. LINGO features a wide range of commands, any of which may be invoked at any time. LINGO checks whether a particular command makes sense in a particular context. LINGO is available in two versions: 1) a Windows-specific version, and 2) a generic, text-based version. The text-based version runs under most popular operating systems, including Unix and Linux. For either version, additional information is available to the user under the Help menu item or Help command. The Windows commands are covered briefly here. After the commands section, we will show you how to enter and solve a simple model. 2.2 LINGO for Windows When LINGO for Windows starts, it opens a blank window known as a Model Window. The Model Window is where you “do all your work”. Output in LINGO is displayed in a Report Window. LINGO can generate a number of reports pertaining to your model. The following is a list of all the commands that are available to you, mainly in the model window. 2.2.1 File Menu NEW F2 Use the NEW command from the File menu, press F2, or use the button to create a new Model window. In the Model window, you can enter your model