3WhatisOptimization?Chapter1Figure1.1FeasibleRegionforEnginola60Astro Capacity、NCosmoCapacityA=60C=5050c40osLaborCapacitymFeasible30/A+2C=120Production0Combinationss20100102050603040708090100110120AstrosYou, thethoughtful reader,might observe there are many combinations of A and C,other than justA=0andC=50,that achieveS1500ofprofit.Indeed,if youplot theline20A+30C=1500and addit to the graph, then you get Figure 1.2. Any point on the dotted line segment achieves a profit of$1500.Any line of constant profit such as that is called an iso-profit line (or iso-cost in the case of acostminimizationproblem).If wenext talk with the manager of the Astro line,the responsemight be:"if you produce50Cosmos, you still have enough labor to produce 2o Astros.This would give a profit of30 × 50 + 20 ×x 20=s1900.That is certainly a respectable profit. Why don't we call it a day and gohome?"Figure1.2EnginolaWith"Profit =1500"50c。40sm 30os2020A+30C=1500100102030405060708090100110120Astros
What is Optimization? Chapter 1 3 Figure 1.1 Feasible Region for Enginola Feasible Production Combinations Astros 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 Cosmo Capacity C = 50 Labor Capacity A + 2 C =120 Astro Capacity A = 60 C o s m o s You, the thoughtful reader, might observe there are many combinations of A and C, other than just A = 0 and C = 50, that achieve $1500 of profit. Indeed, if you plot the line 20A + 30C = 1500 and add it to the graph, then you get Figure 1.2. Any point on the dotted line segment achieves a profit of $1500. Any line of constant profit such as that is called an iso-profit line (or iso-cost in the case of a cost minimization problem). If we next talk with the manager of the Astro line, the response might be: “If you produce 50 Cosmos, you still have enough labor to produce 20 Astros. This would give a profit of 30 u 50 + 20 u 20 = $1900. That is certainly a respectable profit. Why don’t we call it a day and go home?” Figure 1.2 Enginola With "Profit = 1500" Astros 0 10 20 30 40 50 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s 20 A + 30 C = 1500
4Chapter1WhatisOptimization?Our ever-alert reader might again observe that there are many ways of making $1900 of profit. Ifyou plot the line 20A + 30C= 1900 and add it to the graph, then you get Figure 1.3. Any point on thehigher rightmost dotted line segmentachieves a profit of s1900.Figure1.3Enginola with"Profit =1900"70 6050C0 40sm3020A+30C=1900os2010T0102030405060708090100110120AstrosNow, our ever-perceptivereader makes a leap of insight. As we increase our profit aspirations,thedotted line representing all points that achieve a given profit simply shifts in a parallel fashion. Whynot shift it as far as possible for as long as the line contains a feasible point? This last and best feasiblepoint is A = 60, C- 30. It lies on the line 20A + 30C = 2100. This is illustrated in Figure 1.4. Notice,even though the profit contribution per unit is higher for Cosmo, we did not make as many (3O)as wefeasibly could have made (50). Intuitively, this is an optimal solution and, in fact, it is.The graphicalanalysis of this small problem helps understand what is going on when we analyze larger problems.Figure1.4 Enginola with"Profit =2100"706050c0 40s20A+30C=2100m300S2010F0601020304050708090100110120Astros
4 Chapter 1 What is Optimization? Our ever-alert reader might again observe that there are many ways of making $1900 of profit. If you plot the line 20A + 30C = 1900 and add it to the graph, then you get Figure 1.3. Any point on the higher rightmost dotted line segment achieves a profit of $1900. Figure 1.3 Enginola with "Profit = 1900" Astros 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s 70 20 A + 30 C = 1900 Now, our ever-perceptive reader makes a leap of insight. As we increase our profit aspirations, the dotted line representing all points that achieve a given profit simply shifts in a parallel fashion. Why not shift it as far as possible for as long as the line contains a feasible point? This last and best feasible point is A = 60, C = 30. It lies on the line 20A + 30C = 2100. This is illustrated in Figure 1.4. Notice, even though the profit contribution per unit is higher for Cosmo, we did not make as many (30) as we feasibly could have made (50). Intuitively, this is an optimal solution and, in fact, it is. The graphical analysis of this small problem helps understand what is going on when we analyze larger problems. Figure 1.4 Enginola with "Profit = 2100" Astros 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s 70 20 A + 30 C = 2100
WhatisOptimization?Chapter151.3LinearityWe have now seen one example.We will return to it regularly.This is an example of a linearmathematical program, or LP for short. Solving linear programs tends to be substantially easier thansolving more general mathematical programs. Therefore, it is worthwhile to dwell for a bit on thelinearity feature.Linear programming applies directly only to situations in which the effects of the differentactivities in which we can engage are linear.For practical purposes, we can think of the linearityrequirement as consisting of three features:Proportionality. The effects of a single variable or activity by itself are proportional1.(e.g.,doubling the amount of steel purchased will double the dollar cost of steelpurchased).2.Additivity.The interactions among variables must be additive (e.g., the dollar amount ofsales is the sum of the steel dollar sales, the aluminum dollar sales, etc.; whereas theamount of electricity used is the sum of that used toproduce steel, aluminum, etc).3.Continuity.The variables must be continuous (i.e.,fractional values for the decisionvariables,suchas6.38,mustbeallowed).Ifboth2and3arefeasiblevaluesforavariable, then so is2.51.A model that includes the two decision variables“price per unit sold"and"quantity of units sold"isprobablynotlinear.Theproportionalityrequirementissatisfied.However,theinteractionbetweenthe two decision variables is multiplicative rather than additive (i.e., dollar sales =price x quantity,notprice+quantity)If a supplier gives you quantity discounts on your purchases, then the cost of purchases will notsatisfy the proportionality requirement (e.g., the total cost of the stainless steel purchased may be lessthan proportional to the amount purchased),A model that includes the decision variable "number of floors to build"might satisfy theproportionality and additivity requirements,butviolate the continuity conditions.Therecommendationto build 6.38 floors might be difficult to implement unless onehad a designer who was ingenious withsplit level designs.Nevertheless,the solution ofan LP mightrecommend suchfractional answers.The possible formulations to which LP is applicable are substantially more general than thatsuggested by the example. The objective function may be minimized rather than maximized; thedirection of the constraints may be ≥rather than ≤, or even -; and any or all of the parameters (e.g.,the2030,60.50.120.2,or1)maybenegativeinsteadofpositive.Theprincipalrestrictionontheclassof problems that can be analyzed results from the linearity restriction.Fortunately,as we will see later in the chapters on integer programming and quadraticprogramming, there are other ways of accommodating these violations of linearity
What is Optimization? Chapter 1 5 1.3 Linearity We have now seen one example. We will return to it regularly. This is an example of a linear mathematical program, or LP for short. Solving linear programs tends to be substantially easier than solving more general mathematical programs. Therefore, it is worthwhile to dwell for a bit on the linearity feature. Linear programming applies directly only to situations in which the effects of the different activities in which we can engage are linear. For practical purposes, we can think of the linearity requirement as consisting of three features: 1. Proportionality. The effects of a single variable or activity by itself are proportional (e.g., doubling the amount of steel purchased will double the dollar cost of steel purchased). 2. Additivity. The interactions among variables must be additive (e.g., the dollar amount of sales is the sum of the steel dollar sales, the aluminum dollar sales, etc.; whereas the amount of electricity used is the sum of that used to produce steel, aluminum, etc). 3. Continuity. The variables must be continuous (i.e., fractional values for the decision variables, such as 6.38, must be allowed). If both 2 and 3 are feasible values for a variable, then so is 2.51. A model that includes the two decision variables “price per unit sold” and “quantity of units sold” is probably not linear. The proportionality requirement is satisfied. However, the interaction between the two decision variables is multiplicative rather than additive (i.e., dollar sales = price u quantity, not price + quantity). If a supplier gives you quantity discounts on your purchases, then the cost of purchases will not satisfy the proportionality requirement (e.g., the total cost of the stainless steel purchased may be less than proportional to the amount purchased). A model that includes the decision variable “number of floors to build” might satisfy the proportionality and additivity requirements, but violate the continuity conditions. The recommendation to build 6.38 floors might be difficult to implement unless one had a designer who was ingenious with split level designs. Nevertheless, the solution of an LP might recommend such fractional answers. The possible formulations to which LP is applicable are substantially more general than that suggested by the example. The objective function may be minimized rather than maximized; the direction of the constraints may be t rather than d, or even =; and any or all of the parameters (e.g., the 20, 30, 60, 50, 120, 2, or 1) may be negative instead of positive. The principal restriction on the class of problems that can be analyzed results from the linearity restriction. Fortunately, as we will see later in the chapters on integer programming and quadratic programming, there are other ways of accommodating these violations of linearity
6Chapter1WhatisOptimization?Figure 1.5 illustrates some nonlinear functions. For example, the expression Xx Y satisfies theproportionality requirement, but the efects ofX and Yare not additive.In the expressionX?+2, theeffects of X and Yare additive, but the effects of each individual variable are not proportional.Figure1.5:NonlinearRelations4-X*X + Y*Y = 163Y2X*Y=1101111234X1.4AnalysisofLPSolutionsWhen you direct the computer to solve a math program, the possible outcomes are indicated inFigure 1.6.For a properly formulated LP, the leftmost path will be taken. The solution procedure will firstattemptto find a feasible solution (i.e.,a solution that simultaneously satisfies all constraints, but doesnot necessarily maximize the objective function).The rightmost,No Feasible Solution,path will betaken if the formulator has been too demanding.That is, two or more constraints are specified thatcannot be simultaneously satisfied.A simple example is the pair of constraints x≤2 and x≥3.Thenonexistence of afeasible solutiondoes not dependupon theobjectivefunction.It depends solely uponthe constraints.In practice,theNo Feasible Solution"outcome might occur in a large complicatedproblem in which an upper limit was specified on the number of productive hours available and anunrealistically high demand wasplaced on the number ofunits tobeproduced.An alternative messageto“No Feasible Solution"is"You Can't Have Your Cake and Eat It Too
6 Chapter 1 What is Optimization? Figure 1.5 illustrates some nonlinear functions. For example, the expression X u Y satisfies the proportionality requirement, but the effects of X and Y are not additive. In the expression X 2 + Y 2 , the effects of X and Y are additive, but the effects of each individual variable are not proportional. Figure 1.5: Nonlinear Relations 1.4 Analysis of LP Solutions When you direct the computer to solve a math program, the possible outcomes are indicated in Figure 1.6. For a properly formulated LP, the leftmost path will be taken. The solution procedure will first attempt to find a feasible solution (i.e., a solution that simultaneously satisfies all constraints, but does not necessarily maximize the objective function). The rightmost, “No Feasible Solution”, path will be taken if the formulator has been too demanding. That is, two or more constraints are specified that cannot be simultaneously satisfied. A simple example is the pair of constraints x d 2 and x t 3. The nonexistence of a feasible solution does not depend upon the objective function. It depends solely upon the constraints. In practice, the “No Feasible Solution” outcome might occur in a large complicated problem in which an upper limit was specified on the number of productive hours available and an unrealistically high demand was placed on the number of units to be produced. An alternative message to “No Feasible Solution” is “You Can’t Have Your Cake and Eat It Too
7WhatisOptimization?Chapter1Figure1.6SolutionOutcomesSolveLPFeasible(NotFeasible)Optimal SolutionUnboundedIf afeasible solution has been found,then theprocedureattemptsto find an optimal solution.IftheUnbounded Solution"termination occurs, it implies the formulation admits the unrealistic resultthat an infinite amount of profit can be made.A more realistic conclusion is that an importantconstraint has been omitted or theformulation contains a critical typographical error.Wecan solvetheEnginolaproblem inLINGObytypingthefollowing:MODEL:MAX=20*A+30*C;A<60;C <=50;A+2*C<=120;ENDWe can solve the problem in the Windows version of LINGO by clicking on the red “bullseye"icon.We can get thefollowing solution report by clicking on the"X-"icon":Objectivevalue:2100.000ValueReduced CostVariableA60.000000.00000c30.000000.00000RowDual PriceslackorSurplus12342100.000001.000000.000005.0000020.000000.000000.0000015.00000The output has three sections, an informative section,a“variables"section,and a“rows"section.The second two sections are straightforward.The maximumprofit solution is to produce 60 Astros and30 Cosmos for a profit contribution of s2,100.This solution will leave zero slack in row2 (theconstraint A≤60), a slack of 20 in row3 (the constraint C≤50),and no slack in row 4 (the constraintA+2C≤120).Note60+2×30=120The third column contains a number of opportunity or marginal cost figures.These are usefulby-products of the computations.The interpretation of these"reduced costs"and“dual prices"isdiscussed in the next section.The reduced cost/dual price section is optional and can be turned on oroffbyclickingonLINGOOptionsGeneral SolverDualComputationsPrices
What is Optimization? Chapter 1 7 Figure 1.6 Solution Outcomes If a feasible solution has been found, then the procedure attempts to find an optimal solution. If the “Unbounded Solution” termination occurs, it implies the formulation admits the unrealistic result that an infinite amount of profit can be made. A more realistic conclusion is that an important constraint has been omitted or the formulation contains a critical typographical error. We can solve the Enginola problem in LINGO by typing the following: MODEL: MAX = 20*A + 30*C; A <= 60; C <= 50; A + 2*C <= 120; END We can solve the problem in the Windows version of LINGO by clicking on the red “bullseye” icon. We can get the following solution report by clicking on the “X=” icon”: Objective value: 2100.000 Variable Value Reduced Cost A 60.00000 0.00000 C 30.00000 0.00000 Row Slack or Surplus Dual Price 1 2100.00000 1.00000 2 0.00000 5.00000 3 20.00000 0.00000 4 0.00000 15.00000 The output has three sections, an informative section, a “variables” section, and a “rows” section. The second two sections are straightforward. The maximum profit solution is to produce 60 Astros and 30 Cosmos for a profit contribution of $2,100. This solution will leave zero slack in row 2 (the constraint A d 60), a slack of 20 in row 3 (the constraint C d 50), and no slack in row 4 (the constraint A + 2C d 120). Note 60 + 2 u 30 = 120. The third column contains a number of opportunity or marginal cost figures. These are useful by-products of the computations. The interpretation of these “reduced costs” and “dual prices” is discussed in the next section. The reduced cost/dual price section is optional and can be turned on or off by clicking on LINGO | Options | General Solver | Dual Computations | Prices