Faaliyetler İş Araştırma ve İktisat Integer Goal Programming To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 1 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Chapter 11 Integer, Goal, and Nonlinear Programming Prepared by Lee Revere and John LargeTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 2 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Learning Objectives Students will be able to: Understand the difference between 1. LP and integer programming. Understand and solve the three types 2. of integer programming problems. Apply the branch and bound method 3. to solve integer programming problems. Solve goal programming problems 4. graphically and using a modified simplex technique. Formulate nonlinear programming 5. problems and solve using Excel.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 3 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Chapter Outline 11.1 Introduction 11.2 Integer Programming 11.3 Modeling with 0-1 (Binary) Variables 11.4 Goal Programming 11.5 Nonlinear ProgrammingTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 4 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Introduction Integer programming is the extension of ? LP that solves problems requiring integer solutions. Goal programming is the extension of ? LP that permits more than one objective to be stated. Nonlinear programming is the case in ? which objectives or constraints are nonlinear. All three above mathematical ? programming models are used when some of the basic assumptions of LP are made more or less restrictive.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 5 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Summary: Linear Programming Extensions Integer Programming ? Linear, integer solutions ? Goal Programming ? Linear, multiple objectives ? Nonlinear Programming ? Nonlinear objective and/or ? constraintsTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 6 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Programming Solution values must be whole ? numbers in integer programming . There are three types of integer ? programs: pure integer programming; ? mixed-integer programming; and ? 0–1 integer programming. ?To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 7 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Programming (continued) The Pure Integer Programming 1. problems are cases in which all variables are required to have integer values. The Mixed-Integer Programming 2. problems are cases in which some, but not all, of the decision variables are required to have integer values. The Zero–One Integer Programming 3. problems are special cases in which all the decision variables must have integer solution values of 0 or 1.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 8 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Programming Example: Harrison Electric Company The Company produces two products ? popular with home renovators: old- fashioned chandeliers and ceiling fans. Both the chandeliers and fans require a two- ? step production process involving wiring and assembly. It takes about 2 hours to wire each ? chandelier and 3 hours to wire a ceiling fan. Final assembly of the chandeliers and fans requires 6 and 5 hours, respectively. The production capability is such that only ? 12 hours of wiring time and 30 hours of assembly time are available.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 9 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Programming: Example (continued) If each chandelier produced nets the firm $7 and each fan $6, Harrison ’ s production mix decision can be formulated using LP as follows: maximize profit = $7 X 1 + $6 X 2 subject to: 2 X 1 + 3 X 2 12 (wiring hours) 6 X 1 + 5 X 2 30 (assembly hours) X 1 , X 2 0 (nonnegative) X 1 = number of chandeliers produced X 2 = number of ceiling fans producedTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 10 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Programming: Example (continued) With only two variables and two constraints, the graphical LP approach to generate the optimal solution is given below: 6 X 1 + 5 X 2 30 + = Possible Integer Solution Optimal LP Solution ( X 1 = 3 3 / 4 , X 2 = 1 1 / 2 , Profit = $ 35.25 2 X 1 + 3 X 2 12To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 11 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 List of All Integer Solutions for Harrison Electric Co. Optimal solution Solution if rounding offTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 12 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Solution to Harrison Electric Co. (continued) Rounding off is one way to reach ? integer solution values, but it often does not yield the best solution. An important concept to ? understand is that an integer programming solution can never be better than the solution to the same LP problem. The integer problem is usually ? worse in terms of higher cost or lower profit.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 13 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method The Branch and Bound method ? breaks the feasible solution region into sub-problems until an optimal solution is found. There are Six Steps in Solving Integer ? Programming Maximization Problems by Branch and Bound. The steps are given over the next ? several slides.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 14 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method: The Six Steps Solve the original problem using LP. 1. If the answer satisfies the integer ? constraints, it is the optimal solution. If not, this value provides an initial ? upper bound. Find any feasible solution that meets 1. the integer constraints for use as a lower bound. Usually, rounding down each ? variable will accomplish this.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 15 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method Steps: (continued) Branch on one variable from Step 1 3. that does not have an integer value. Split the problem into two sub- ? problems based on integer values that are immediately above and below the non-integer value. For example, if X 2 = 3.75 was in the ? final LP solution, introduce the constraint X 2 4 in the first sub- problem and X 2 3 in the second sub- problem. Create nodes at the top of these new 4. branches by solving the new problems.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 16 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method Steps: (continued) 5. If a branch yields a solution to the LP a) problem that is not feasible , terminate the branch. If a branch yields a solution to the LP b) problem that is feasible, but not an integer solution, go to step 6.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 17 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method Steps: (continued) 5. ( continued) If the branch yields a feasible integer c) solution, examine the value of the objective function. If this value equals the upper bound, an optimal solution has been reached. If it is not equal to the upper bound, but exceeds the lower bound, set it as the new lower bound and go to step 6. Finally, if it is less than the lower bound, terminate this branch.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 18 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Branch and Bound Method Steps: (continued) Examine both branches again and 6. set the upper bound equal to the maximum value of the objective function at all final nodes. If the upper bound equals the lower • bound, stop. If not, go back to step 3. • Minimization problems involve reversing the roles of the upper and lower bounds.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 19 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Harrison Electric Co: Revisited Figure 11.1 shows graphically that the optimal, non-integer solution is X 1 = 3.75 chandeliers X 2 = 1.5 ceiling fans profit = $35.25 Since X 1 and X 2 are not integers, this ? solution is not valid. The profit value of $35.25 will serve as ? an initial upper bound . Note that rounding down gives X 1 = 3, ? X 2 = 1, profit = $27, which is feasible and can be used as a lower bound .To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 20 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Integer Solution: Creating Sub-problems The problem is now divided into two ? sub-problems: A and B . Consider branching on either variable ? that does not have an integer solution; pick X 1 this time. Subproblem A maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 4 Subproblem B maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 3To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 21 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Optimal Solution for Sub-problems Optimal solutions are: Sub-problem A : X 1 = 4; X 2 = 1.2, profit=$35.20 Sub-problem B: X 1 =3, X 2 =2, profit=$33.00 (see figure on next slide) Stop searching on the Subproblem B ? branch because it has an all-integer feasible solution. The $33 profit becomes the lower bound. ? Subproblem A ’ s branch is searched further ? since it has a non-integer solution. The second upper bound becomes $35.20, ? replacing $35.25 from the first node.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 22 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Optimal Solution for Sub-problemTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 23 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Sub-problems C and D Subproblem A ’ s branching yields Subproblems C and D . Subproblem C maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 4 X 2 2 Subproblem D maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 4 X 2 1To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 24 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Sub-problems C and D (continued) Subproblem C has no feasible solution ? at all because the first two constraints are violated if the X 1 4 and X 2 2 constraints are observed. Terminate this branch and do not ? consider its solution. Subproblem D ’ s optimal solution is ? X 1 = 4 , X 2 = 1, profit = $35.16. This non-integer solution yields a ? new upper bound of $35.16, replacing the original $35.20. Subproblems C and D , as well as the ? final branches for the problem, are shown in the figure on the next slide.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 25 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Harrison Electric ’ s Full Branch and Bound Solution To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 26 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Subproblems E and F Finally, create subproblems E and F and solve for X 1 and X 2 with the added constraints X 1 4 and X 1 5. The subproblems and their solutions are: Subproblem E maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 4 X 1 4 X 2 1 Optimal solution for E: X 1 = 4, X 2 = 1, profit = $34To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 27 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Subproblems E and F (continued) Subproblem F maximize profit = $7 X 1 + $6 X 2 Subject to: 2 X 1 + 3 X 2 12 6 X 1 + 5 X 2 30 X 1 4 X 1 5 X 2 1 Optimal solution for F: X 1 = 5, X 2 = 0, profit = $35To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 28 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Using Software to Solve Harrison Electric Co. Problem QM for Windows Analysis of Harrison Electric ’ s Problem Using Integer programming: Input Screen.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 29 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Using Software to Solve Harrison Electric Co. Problem (continued) Output Screen Using QM for Windows on Harrison Electric ’ s Integer Programming ProblemTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 30 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Goal Programming Firms usually have more than one goal. For ? example, maximizing total profit, ? maximizing market share, ? maintaining full employment, ? providing quality ecological management, ? minimizing noise level in the neighborhood, ? and meeting numerous other non-economic ? goals. It is not possible for LP to have multiple goals ? unless they are all measured in the same units (such as dollars), a highly unusual situation. ? An important technique that has been developed ? to supplement LP is called goal programming .To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 31 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Goal Programming (continued) Goal programming “satisfices,” ? as opposed to LP, which tries to ? “optimize.” Satisfice means coming as close as ? possible to reaching goals. The objective function is the main ? difference between goal programming and LP. In goal programming, the purpose is ? to minimize deviational variables, which are the only terms in the objective ? function.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 32 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Example of Goal Programming Harrison Electric Revisited Goals Harrison ’ s management wants to achieve, each equal in priority: Goal 1: to produce as much profit ? above $30 as possible during the production period. Goal 2: to fully utilize the available ? wiring department hours. Goal 3: to avoid overtime in the ? assembly department. Goal 4: to meet a contract requirement ? to produce at least seven ceiling fans.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 33 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Example of Goal Programming Harrison Electric Revisited Need a clear definition of deviational variables, such as : d 1 – = underachievement of the profit target d 1 + = overachievement of the profit target d 2 – = idle time in the wiring dept. (underused) d 2 + = overtime in the wiring dept. (overused) d 3 – = idle time in the assembly dept. (underused) d 3 + = overtime in the wiring dept. (overused) d 4 – = underachievement of the ceiling fan goal d 4 + = overachievement of the ceiling fan goal To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 34 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Ranking Goals with Priority Levels A key idea in goal programming is that one goal is more important than another. Priorities are assigned to each deviational variable. Priority 1 is infinitely more important than Priority 2, which is infinitely more important than the next goal, and so on.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 35 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Analysis of First GoalTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 36 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Analysis of First and Second GoalsTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 37 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Analysis of All Four Priority GoalsTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 38 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Goal Programming Versus Linear Programming Multiple goals (instead of one goal) ? Deviational variables minimized ? (instead of maximizing profit or minimizing cost of LP) “Satisficing” (instead of optimizing) ? Deviational variables are real (and ? replace slack variables)To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 39 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Initial Goal Programming Tableau C j Quantity Solution Mix 0 0 P 1 P 2 0 P 4 0 0 P 3 0 x 1 x 2 d 1 - d 2 - d 3 - d 4 - d 1 + d 2 + d 3 + d 4 + P 1 P 2 0 P 4 P 4 P 3 P 2 P 1 d 1 - d 2 - d 3 - d 4 - Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { 7 2 6 0 6 3 5 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 30 12 30 7 0 0 1 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 -2 3 -3 0 0 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 7 -7 6 -6 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 7 0 1 2 3 0 P i v o t C o l u m nTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 40 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Second Goal Programming Tableau C j Quantity Solution Mix 0 0 P 1 P 2 0 P 4 0 0 P 3 0 x 1 x 2 d 1 - d 2 - d 3 - d 4 - d 1 + d 2 + d 3 + d 4 + P 1 P 2 0 P 4 P 4 P 3 P 2 P 1 x 1 d 2 - d 3 - d 4 - Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { 1 0 0 0 6/7 9/7 -1/7 1 1/7 -2/7 -6/7 0 0 1 0 0 0 0 1 0 0 0 0 1 -1/7 +2/7 6/7 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 30/7 24/7 30/7 7 0 0 1 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 +1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 9/7 -9/7 -2/7 +2/7 1 0 0 0 0 0 2/7 -2/7 -1 +1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 7 0 24/7 0 P i v o t C o l u m nTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 41 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Final Solution to Harrison Electric ’ s Goal Programming C j Quantity Solution Mix 0 0 P 1 P 2 0 P 4 0 0 P 3 0 x 1 x 2 d 1 - d 2 - d 3 - d 4 - d 1 + d 2 + d 3 + d 4 + P 1 P 2 0 P 4 P 4 P 3 P 2 P 1 d 2 + x 2 d 1 + d 4 + Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { Z j C j - Z j { 8/5 6/5 1/5 -6/5 0 1 0 0 0 0 -1 0 -1 0 0 0 3/5 1/5 6/5 -1/5 0 0 0 1 0 0 1 0 1 0 0 0 -3/5 -1/5 -6/5 1/5 0 0 0 -1 6 6 6 1 -6/5 6/5 0 0 0 0 0 0 -1/5 1/5 1 0 0 0 0 0 1/5 -1/5 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 42 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Harrison Electric ’ s Goal Programming Using QM for Windows Final Tableau for Harrison Electric Using QM for Windows.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 43 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Harrison Electric ’ s Goal Programming Using QM for Windows Summary Solution Screen for Harrison Electric ’ s Goal Programming Problem Using POM-QM for Windows.To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 44 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming Nonlinear objective function, linear ? constraints Nonlinear objective function and ? nonlinear constraints Linear objective function and ? nonlinear constraintsTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 45 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming Nonlinear objective function, ? linear constraints Max: 28 X 1 + 21 X 2 + 0.25 X 2 2 Subject to: X 1 + X 2 1000 0.5 X 1 + 0.4 X 2 500To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 46 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 An Excel Formulation of Great Western Appliance ’ s Nonlinear Programming Problem. Nonlinear ProgrammingTo accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 47 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming Nonlinear objective function and ? nonlinear constraints. Max: 13 X 1 + 6 X 1 X 2 + 5 X 2 + X 2 –1 Subject to: 2 X 1 2 + 4 X 2 2 90 X 1 + X 2 3 75 8 X 1 – 2 X 2 61To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 48 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming The Problem has both Nonlinear Objective Function and Nonlinear Constraints. The solution to Great Western Appliance ’ s NLP Problem using Excel Solver:To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 49 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming The problem has both Nonlinear Objective Function and Nonlinear Constraints. An Excel Formulation of Hospicare Corp. ’ s NLP Problem:To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 50 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming The problem has both Nonlinear Objective Function and Nonlinear Constraints. Excel Solution to the Hospicare Corp. ’ s NLP Problem using Solver:To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 51 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming Linear objective function and ? nonlinear constraints Max: 5 X 1 + 7 X 2 Subject to: 3 X 1 + 0.25 X 1 2 + 4 X 2 + 0.3 X 2 2 125 13 X 1 + X 1 3 80 0.7 X 1 + X 2 17To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 52 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming The problem has both Linear Objective Function with Nonlinear Constraints. Excel Formulation of Thermlock ’ s NLP Problem:To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 53 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Nonlinear Programming The problem has both Linear Objective Function with Nonlinear Constraints. The solution to Thermlock ’ s NLP Problem Using the Excel Solver:To accompany Quantitative Analysis for Management, 9e by Render/Stair/Hanna 11- 54 © 2006 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 Computational Procedures - Nonlinear Programming Gradient method (steepest descent) ? Separable programming - linear ? representation of nonlinear problem Separable programming deals ? with a class of problems in which the objective and constraints are approximated by linear functions. In this way, the powerful simplex algorithm may again be applied. In general, work in the area of ? NLP is the most difficult of all the quantitative analysis models.