Integer Programming, Goal Programming, and Nonlinear Programming
10
To accompany Quantitative Analysis for Management, Twelfth Edition,
by Render, Stair, Hanna and Hale
Power Point slides created by Jeff Heyl
Copyright ©2015 Pearson Education, Inc.
After completing this chapter, students will be able to:
LEARNING OBJECTIVES
Copyright ©2015 Pearson Education, Inc.
10 – 2
Understand the difference between LP and integer programming.
Understand and solve the three types of integer programming problems.
Formulate and solve goal programming problems using Excel and QM for Windows.
Formulate nonlinear programming problems and solve using Excel.
10.1 Introduction
10.2 Integer Programming
10.3 Modeling with 0-1 (Binary) Variables
10.4 Goal Programming
10.5 Nonlinear Programming
CHAPTER OUTLINE
Copyright ©2015 Pearson Education, Inc.
10 – 3
Introduction
There are other mathematical programming models that can be used when the assumptions of LP are not met
A large number of business problems require variables have integer values
Many business problems have multiple objectives
Goal programming permits multiple objectives
Nonlinear programming allows objectives and constraints to be nonlinear
Copyright ©2015 Pearson Education, Inc.
10 – 4
Integer Programming
An integer programming model is one where one or more of the decision variables has to take on an integer value in the final solution
Three types of integer programming problems
Pure integer programming – all variables have integer values
Mixed-integer programming – some but not all of the variables will have integer values
Zero-one integer programming – special cases in which all the decision variables must have integer solution values of 0 or 1
Copyright ©2015 Pearson Education, Inc.
10 – 5
An integer programming model is one where one or more of the decision variables has to take on an integer value in the final solution
Three types of integer programming problems
Pure integer programming – all variables have integer values
Mixed-integer programming – some but not all of the variables will have integer values
Zero-one integer programming – special cases in which all the decision variables must have integer solution values of 0 or 1
Integer Programming
Copyright ©2015 Pearson Education, Inc.
10 – 6
Solving an integer programming problem is much more difficult than solving an LP problem
Solution time required may be excessive
Harrison Electric Company Example of Integer Programming
Company produces two products, old-fashioned chandeliers and ceiling fans
Both 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
Only 12 hours of wiring time and 30 hours of assembly time are available
Each chandelier produced nets the firm $7 and each fan $6
Copyright ©2015 Pearson Education, Inc.
10 – 7
Harrison Electric Company Example of Integer Programming
Production mix LP formulation
Copyright ©2015 Pearson Education, Inc.
10 – 8
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12 (wiring hours)
6X1 + 5X2 ≤ 30 (assembly hours)
X1, X2 ≥ 0
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced
Harrison Electric Company Example of Integer Programming
Copyright ©2015 Pearson Education, Inc.
10 – 9
6 –
5 –
4 –
3 –
2 –
1 –
| | | | | |
0 1 2 3 4 5 6
X1
X2
+
+
+
+
+
+
+
+
+ = Possible Integer Solution
6X1 + 5X2 ≤ 30
Optimal LP Solution
(X1= 3.75, X2 = 1.5, Profit = $35.25
2X1 + 3X2 ≤ 12
FIGURE 10.1 – Harrison Electric Problem
Harrison Electric Company Example of Integer Programming
Production planner recognizes this is an integer problem
First attempt at solving it is to round the values to X1 = 4 and X2 = 2
However, this is not feasible
Rounding X2 down to 1 gives a feasible solution, but it may not be optimal
This could be solved using the enumeration method
Generally not possible for large problems
Copyright ©2015 Pearson Education, Inc.
10 – 10
Harrison Electric Company Example of Integer Programming
Copyright ©2015 Pearson Education, Inc.
10 – 11
CHANDELIERS (X1) CEILING FANS (X2) PROFIT ($7X1 + $6X2)
0 0 $0
1 0 7
2 0 14
3 0 21
4 0 28
5 0 35
0 1 6
1 1 13
2 1 20
3 1 27
4 1 34
0 2 12
1 2 19
2 2 26
3 2 33
0 3 18
1 3 25
0 4 24
Optimal solution to integer programming problem
Solution if rounding is used
TABLE 10.1 – Integer Solutions to the Harrison Electric Company Problem
Harrison Electric Company Example of Integer Programming
Copyright ©2015 Pearson Education, Inc.
10 – 12
CHANDELIERS (X1) CEILING FANS (X2) PROFIT ($7X1 + $6X2)
0 0 $0
1 0 7
2 0 14
3 0 21
4 0 28
5 0 35
0 1 6
1 1 13
2 1 20
3 1 27
4 1 34
0 2 12
1 2 19
2 2 26
3 2 33
0 3 18
1 3 25
0 4 24
Optimal solution to integer programming problem
Solution if rounding is used
TABLE 10.1 – Integer Solutions to the Harrison Electric Company Problem
The optimal integer solution is less than the optimal LP solution of $35.25
An integer solution can never be better than the LP solution and is usually a lesser value
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 13
PROGRAM 10.1A – QM for Windows Input Screen for Harrison Electric Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 14
PROGRAM 10.1B – QM for Windows Solution Screen for Harrison Electric Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 15
PROGRAM 10.2 – Excel 2013 Solver Solution for Harrison Electric Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 16
PROGRAM 10.2 – Excel 2013 Solver Solution for Harrison Electric Problem
Solver Parameter Inputs and Selections Key Formulas
Set Objective: D5 By Changing cells: B4:C4 To: Max Subject to the Constraints: D8:D9 >= F8:F9 B4:C4 = integer Solving Method: Simplex LP R Make Variables Non-Negative Copy D5 to D8:D9
Mixed-Integer Programming Problem Example
Many situations in which only some of the variables are restricted to integers
Bagwell Chemical Company produces two industrial chemicals
Xyline must be produced in 50-pound bags
Hexall is sold by the pound and can be produced in any quantity
Both xyline and hexall are composed of three ingredients – A, B, and C
Bagwell sells xyline for $85 a bag and hexall for $1.50 per pound
Copyright ©2015 Pearson Education, Inc.
10 – 17
Mixed-Integer Programming Problem Example
Copyright ©2015 Pearson Education, Inc.
10 – 18
AMOUNT PER 50-POUND BAG OF XYLINE (LB) AMOUNT PER POUND OF HEXALL (LB) AMOUNT OF INGREDIENTS AVAILABLE
30 0.5 2,000 lb–ingredient A
18 0.4 800 lb–ingredient B
2 0.1 200 lb–ingredient C
Objective is to maximize profit
Mixed-Integer Programming Problem Example
Let X = number of 50-pound bags of xyline
Let Y = number of pounds of hexall
A mixed-integer programming problem as Y is not required to be an integer
Copyright ©2015 Pearson Education, Inc.
10 – 19
Maximize profit = $85X + $1.50Y
subject to 30X + 0.5Y ≤ 2,000
18X + 0.4Y ≤ 800
2X + 0.1Y ≤ 200
X, Y ≥ 0 and X integer
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 20
PROGRAM 10.3 – QM for Windows Solution for Bagwell Chemical Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 21
PROGRAM 10.4 – Excel 2013 Solver Solution for Bagwell Chemical Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 22
Solver Parameter Inputs and Selections Key Formulas
Set Objective: D5 By Changing cells: B4:C4 To: Max Subject to the Constraints: D8:D10 <= F8:F10 B4 = integer Solving Method: Simplex LP R Make Variables Non-Negative Copy D5 to D8:D10
PROGRAM 10.4 – Excel 2013 Solver Solution for Bagwell Chemical Problem
Modeling With 0-1 (Binary) Variables
Demonstrate how 0-1 variables can be used to model several diverse situations
Typically a 0-1 variable is assigned a value of 0 if a certain condition is not met and a 1 if the condition is met
This is also called a binary variable
Copyright ©2015 Pearson Education, Inc.
10 – 23
Capital Budgeting Example
Common capital budgeting problem – select from a set of possible projects when budget limitations make it impossible to select them all
A 0-1 variable is defined for each project
Quemo Chemical Company is considering three possible improvement projects for its plant
A new catalytic converter
A new software program for controlling operations
Expanding the storage warehouse
It cannot do them all
Copyright ©2015 Pearson Education, Inc.
10 – 24
Capital Budgeting Example
Objective is to maximize net present value of projects undertaken
subject to Total funds used in year 1 ≤ $20,000
Total funds used in year 2 ≤ $16,000
Copyright ©2015 Pearson Education, Inc.
10 – 25
PROJECT NET PRESENT VALUE YEAR 1 YEAR 2
Catalytic Converter $25,000 $8,000 $7,000
Software $18,000 $6,000 $4,000
Warehouse expansion $32,000 $12,000 $8,000
Available funds $20,000 $16,000
TABLE 10.2 – Quemo Chemical Company Information
Capital Budgeting Example
Decision variables
Copyright ©2015 Pearson Education, Inc.
10 – 26
X1 =
1 if catalytic converter project is funded
0 otherwise
X2 =
1 if software project is funded
0 otherwise
X3 =
1 if warehouse expansion project is funded
0 otherwise
Formulation
Maximize NPV = 25,000X1 + 18,000X2 + 32,000X3
subject to 8,000X1 + 6,000X2 + 12,000X3 ≤ 20,000
7,000X1 + 4,000X2 + 8,000X3 ≤ 16,000
X1, X2, X3 = 0 or 1
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 27
PROGRAM 10.5 – Excel 2013 Solver Solution for Quemo Chemical Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 28
PROGRAM 10.5 – Excel 2013 Solver Solution for Quemo Chemical Problem
Optimal Solution
X1 = 1, X2 = 0, X3 = 1
Fund the catalytic converter and warehouse projects but not the software project
NPV = $57,000
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 29
Solver Parameter Inputs and Selections Key Formulas
Set Objective: E5 By Changing cells: B4:D4 To: Max Subject to the Constraints: E8:E9 <= G8:G9 B4:D4 = binary Solving Method: Simplex LP R Make Variables Non-Negative Copy E5 to E8:E9
PROGRAM 10.5 – Excel 2013 Solver Solution for Quemo Chemical Problem
Limiting the Number of Alternatives Selected
One common use of 0-1 variables involves limiting the number of projects or items that are selected from a group
Suppose Quemo Chemical is required to select no more than two of the three projects regardless of the funds available
This would require adding a constraint
X1 + X2 + X3 ≤ 2
If they had to fund exactly two projects the constraint would be
X1 + X2 + X3 = 2
Copyright ©2015 Pearson Education, Inc.
10 – 30
Dependent Selections
At times the selection of one project depends on the selection of another project
Suppose Quemo’s catalytic converter could only be purchased if the software was purchased
The following constraint would force this to occur
X1 ≤ X2 or X1 – X2 ≤ 0
If we wished for the catalytic converter and software projects to either both be selected or both not be selected, the constraint would be
X1 = X2 or X1 – X2 = 0
Copyright ©2015 Pearson Education, Inc.
10 – 31
Fixed-Charge Problem Example
Often businesses are faced with decisions involving a fixed charge that will affect the cost of future operations
Sitka Manufacturing is planning to build at least one new plant and three cities are being considered
Baytown, Texas
Lake Charles, Louisiana
Mobile, Alabama
Copyright ©2015 Pearson Education, Inc.
10 – 32
Fixed-Charge Problem Example
Constraints
Total production capacity at least 38,000 units each year
Number of units produced at the Baytown plant is 0 if the plant is not built and no more than 21,000 if the plant is built
Number of units produced at the Lake Charles plant is 0 if the plant is not built and no more than 20,000 if the plant is built
Number of units produced at the Mobile plant is 0 if the plant is not built and no more than 19,000 if the plant is built
Copyright ©2015 Pearson Education, Inc.
10 – 33
Fixed-Charge Problem Example
Copyright ©2015 Pearson Education, Inc.
10 – 34
SITE ANNUAL FIXED COST VARIABLE COST PER UNIT ANNUAL CAPACITY
Baytown, TX $340,000 $32 21,000
Lake Charles, LA $270,000 $33 20,000
Mobile, AL $290,000 $30 19,000
TABLE 10.3 – Fixed and Variable Costs for Sitka Manufacturing
Fixed-Charge Problem Example
Decision variables
Copyright ©2015 Pearson Education, Inc.
10 – 35
X1 =
1 if factory is built in Baytown
0 otherwise
X2 =
1 factory is built in Lake Charles
0 otherwise
X3 =
1 if factory is built in Mobile
0 otherwise
X4 = number of units produced at Baytown plant
X5 = number of units produced at Lake Charles plant
X6 = number of units produced at Mobile plant
Fixed-Charge Problem Example
Formulation
Copyright ©2015 Pearson Education, Inc.
10 – 36
Minimize cost = 340,000X1 + 270,000X2 + 290,000X3
+ 32X4 + 33X5 + 30X6
subject to X4 + X5 + X6 ≥ 38,000
X4 ≤ 21,000X1
X5 ≤ 20,000X2
X6 ≤ 19,000X3
X1, X2, X3 = 0 or 1
X4, X5, X6 ≥ 0 and integer
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 37
PROGRAM 10.6 – Excel 2013 Solver Solution for Sitka Manufacturing Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 38
PROGRAM 10.6 – Excel 2013 Solver Solution for Sitka Manufacturing Problem
Optimal solution
X1 = 0, X2 = 1, X3 = 1, X4 = 0, X5 = 19,000, X6 = 19,000
Objective function value = $1,757,000
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 39
Solver Parameter Inputs and Selections Key Formulas
Set Objective: H5 By Changing cells: B4:G4 To: Min Subject to the Constraints: H8 >= J8 H9:H11 <= J9:J11 B4:D4 = binary E4:G4 = integer Solving Method: Simplex LP R Make Variables Non-Negative Copy H5 to H8:H11
PROGRAM 10.6 – Excel 2013 Solver Solution for Sitka Manufacturing Problem
Financial Investment Example
Simkin, Simkin, and Steinberg specialize in recommending oil stock portfolios
One client has the following specifications
At least two Texas firms must be in the portfolio
No more than one investment can be made in a foreign oil company
One of the two California oil stocks must be purchased
The client has $3 million to invest and wants to buy large blocks of shares
Copyright ©2015 Pearson Education, Inc.
10 – 40
Financial Investment Example
Copyright ©2015 Pearson Education, Inc.
10 – 41
STOCK COMPANY NAME EXPECTED ANNUAL RETURN ($1,000s) COST FOR BLOCK OF SHARES ($1,000s)
1 Trans-Texas Oil 50 480
2 British Petroleum 80 540
3 Dutch Shell 90 680
4 Houston Drilling 120 1,000
5 Texas Petroleum 110 700
6 San Diego Oil 40 510
7 California Petro 75 900
TABLE 10.4 – Oil Investment Opportunities
Financial Investment Example
Formulation
Maximize return = 50X1 + 80X2 + 90X3 + 120X4 + 110X5 + 40X6 + 75X7
subject to
X1 + X4 + X5 ≥ 2 (Texas constraint)
X2 + X3 ≤ 1 (foreign oil constraint)
X6 + X7 = 1 (California constraint)
480X1 + 540X2 + 680X3 + 1,000X4 + 700X5 + 510X6 + 900X7 ≤ 3,000 ($3 million limit)
Xi = 0 or 1 for all i
Copyright ©2015 Pearson Education, Inc.
10 – 42
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 43
PROGRAM 10.7 – Excel 2013 Solver Solution for Financial Investment Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 44
Solver Parameter Inputs and Selections Key Formulas
Set Objective: I5 By Changing cells: B4:H4 To: Max Subject to the Constraints: I7 >= K7 I8 <= K8 I9 = K9 I10 <= K10 B4:H4 = binary Solving Method: Simplex LP R Make Variables Non-Negative Copy I5 to I7:I10
PROGRAM 10.7 – Excel 2013 Solver Solution for Financial Investment Problem
Goal Programming
Firms often have more than one goal
In linear and integer programming methods the objective function is measured in one dimension only
It is not possible for LP to have multiple goals unless they are all measured in the same units
Highly unusual situation
Goal programming developed to supplement LP
Copyright ©2015 Pearson Education, Inc.
10 – 45
Goal Programming
Typically goals set by management can be achieved only at the expense of other goals
Establish a hierarchy of importance so that higher-priority goals are satisfied before lower-priority goals
Not always possible to satisfy every goal
Goal programming attempts to reach a satisfactory level of multiple objectives
May not optimize but have to satisfice
Copyright ©2015 Pearson Education, Inc.
10 – 46
Goal Programming
Main difference is in the objective function
Goal programming tries to minimize the deviations between goals and what can be achieved given the constraints
Objective is to minimize deviational variables
Copyright ©2015 Pearson Education, Inc.
10 – 47
Harrison Electric Company Revisited
Production mix LP formulation
Copyright ©2015 Pearson Education, Inc.
10 – 48
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12 (wiring hours)
6X1 + 5X2 ≤ 30 (assembly hours)
X1, X2 ≥ 0
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced
Harrison Electric Company Revisited
Moving to a new location and maximizing profit is not a realistic objective
A profit level of $30 would be satisfactory during this period
The goal programming problem is to find the production mix that achieves this goal as closely as possible given the production time constraints
Define two deviational variables
d1– = underachievement of the profit target
d1+ = overachievement of the profit target
Copyright ©2015 Pearson Education, Inc.
10 – 49
Harrison Electric Company Revisited
Single-goal programming formulation
Copyright ©2015 Pearson Education, Inc.
10 – 50
Minimize under or
overachievement = d1– + d1+
of profit target
subject to
$7X1 + $6X2 + d1– – d1+ = $30 (profit goal constraint)
2X1 + 3X2 ≤ 12 (wiring hours)
6X1 + 5X2 ≤ 30 (assembly hours)
X1, X2, d1–, d1+ ≥ 0
Minimize under or
overachievement = d1– + d1+
of profit target
subject to
$7X1 + $6X2 + d1– – d1+ = $30 (profit goal constraint)
2X1 + 3X2 ≤ 12 (wiring hours)
6X1 + 5X2 ≤ 30 (assembly hours)
X1, X2, d1–, d1+ ≥ 0
Single-goal programming formulation
Harrison Electric Company Revisited
Copyright ©2015 Pearson Education, Inc.
10 – 51
Analyze each goal to see if underachievement or overachievement of that goal is acceptable
If overachievement is acceptable, eliminate the appropriate d+ variable from the objective function
If underachievement is okay, the d– variable should be dropped
If a goal must be attained exactly, both d– and d+ must appear in the objective function
Extension to Equally Important Multiple Goals
Achieve several goals that are equal in priority
Goal 1: to produce a profit of $30 if 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
Copyright ©2015 Pearson Education, Inc.
10 – 52
Extension to Equally Important Multiple Goals
The deviational variables can be defined as
d1– = underachievement of the profit target
d1+ = overachievement of the profit target
d2– = idle time in the wiring department (underutilization)
d2+ = overtime in the wiring department (overutilization)
d3– = idle time in the assembly department (underutilization)
d3+ = overtime in the assembly department (overutilization)
d4– = underachievement of the ceiling fan goal
d4+ = overachievement of the ceiling fan goal
Copyright ©2015 Pearson Education, Inc.
10 – 53
Extension to Equally Important Multiple Goals
Management is unconcerned about d1+, d2+, d3–, and d4+ so these may be omitted from the objective function
New objective function and constraints
Copyright ©2015 Pearson Education, Inc.
10 – 54
Minimize total deviation = d1– + d2– + d3+ + d4–
subject to
$7X1 + $6X2 + d1– – d1+ = $30 (profit constraint)
2X1 + 3X2 + d2– – d2+ = 12 (wiring hours constraint)
6X1 + 5X2 + d3– – d3+ = 30 (assembly hours constraint)
X2 + d4– – d4+ = 7 (ceiling fan constraint)
All Xi, di variables ≥ 0
Ranking Goals with Priority Levels
In most goal programming problems, one goal will be more important than another
Lower-order goals considered only after higher-order goals are met
Priorities (Pis) are assigned to each deviational variable
P1 is the most important goal
P2 the next most important
P3 the third, and so on
Copyright ©2015 Pearson Education, Inc.
10 – 55
Ranking Goals with Priority Levels
Harrison Electric has set the following priorities for their four goals
Copyright ©2015 Pearson Education, Inc.
10 – 56
GOAL PRIORITY
Reach a profit as much above $30 as possible P1
Fully use wiring department hours available P2
Avoid assembly department overtime P3
Produce at least seven ceiling fans P4
Priority 1 is infinitely more important than Priority 2, which is infinitely more important than the next goal, and so on
Harrison Electric has set the following priorities for their four goals
Ranking Goals with Priority Levels
Copyright ©2015 Pearson Education, Inc.
10 – 57
GOAL PRIORITY
Reach a profit as much above $30 as possible P1
Fully use wiring department hours available P2
Avoid assembly department overtime P3
Produce at least seven ceiling fans P4
With ranking of goals considered, the new objective function is
Minimize total deviation = P1d1– + P2d2– + P3d3+ + P4d4–
Goal Programming with Weighted Goals
Priority levels assume that each level is infinitely more important than the level below it
However a goal may be only two or three times more important than another
Instead of placing these goals on different levels, they are placed on the same level but with different weights
The coefficients of the deviation variables in the objective function include both the priority level and the weight
Copyright ©2015 Pearson Education, Inc.
10 – 58
Goal Programming with Weighted Goals
Suppose Harrison decides to add another goal of producing at least two chandeliers
The goal of producing seven ceiling fans is considered twice as important as this goal
The goal of two chandeliers is assigned a weight of 1 and the goal of seven ceiling fans is assigned a weight of 2 and both of these will be priority level 4
The new constraint and objective function are
X1 + d5– – d5+ = 2 (chandeliers)
Minimize total = P1d1– + P2d2– + P3d3+ + P4(2d4–) + P4d5–
deviation
Copyright ©2015 Pearson Education, Inc.
10 – 59
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 60
PROGRAM 10.8A – Harrison Electric’s Goal Programming Analysis Using QM for Windows: Inputs
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 61
PROGRAM 10.8B – Summary Solution Screen for Harrison Electric’s Goal Programming Problem Using QM for Windows
Nonlinear Programming
The methods seen so far have assumed that the objective function and constraints are linear
However, there are many nonlinear relationships in the real world that would require the objective function and/or constraint equations to be nonlinear
Computational procedures for nonlinear programming (NLP) may only provide a local optimum solution rather than a global optimum
Copyright ©2015 Pearson Education, Inc.
10 – 62
Nonlinear Objective Function and Linear Constraints
The Great Western Appliance Company sells two models of toaster ovens, the Microtoaster (X1) and the Self-Clean Toaster Oven (X2)
They earn a profit of $28 for each Microtoaster no matter the number of units sold
For the Self-Clean oven, profits increase as more units are sold due to a fixed overhead
The profit function for the Self-Clean oven
21X2 + 0.25X22
Copyright ©2015 Pearson Education, Inc.
10 – 63
Nonlinear Objective Function and Linear Constraints
The objective function is nonlinear and there are two linear constraints on production capacity and sales time available
Copyright ©2015 Pearson Education, Inc.
10 – 64
Maximize profit = 28X1 + 21X2 + 0.25X22
subject to
X1 + X2 ≤ 1,000 (units of production capacity)
0.5X1 + 0.4X2 ≤ 500 (hours of sales time available)
X1, X2 ≥ 0
The objective function is nonlinear and there are two linear constraints on production capacity and sales time available
Nonlinear Objective Function and Linear Constraints
Copyright ©2015 Pearson Education, Inc.
10 – 65
Maximize profit = 28X1 + 21X2 + 0.25X22
subject to
X1 + X2 ≤ 1,000 (units of production capacity)
0.5X1 + 0.4X2 ≤ 500 (hours of sales time available)
X1, X2 ≥ 0
When an objective function contains a squared term and the problem constraints are linear, it is called a quadratic programming problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 66
PROGRAM 10.9 – Excel 2013 Solver Solution for Great Western Appliance NLP Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 67
Solver Parameter Inputs and Selections Key Formulas
Set Objective: E8 By Changing cells: B4:C4 To: Max Subject to the Constraints: E11:E12 <= G11:G12 Solving Method: GRG Nonlinear R Make Variables Non-Negative
PROGRAM 10.9 – Excel 2013 Solver Solution for Great Western Appliance NLP Problem
Both Nonlinear Objective Function and Nonlinear Constraints
The annual profit at a medium-sized (200-400 beds) Hospicare Corporation hospital depends on
The number of medical patients admitted (X1)
The number of surgical patients admitted (X2)
The objective function for the hospital is nonlinear
There are three constraints, two of which are nonlinear
Nursing capacity - nonlinear
X-ray capacity - nonlinear
Marketing budget required
Copyright ©2015 Pearson Education, Inc.
10 – 68
Both Nonlinear Objective Function and Nonlinear Constraints
Objective function and constraint equations
Copyright ©2015 Pearson Education, Inc.
10 – 69
Maximize profit = $13X1 + $6X1X2 + $5X2 + $1/X2
subject to
2X12 + 4X2 ≤ 90 (nursing capacity in thousands of labor-days)
X1 + X23 ≤ 75 (x-ray capacity in thousands)
8X1 – 2X2 ≤ 61 (marketing budget required in thousands of $)
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 70
PROGRAM 10.10 – Excel 2013 Solution to the Hospicare NLP Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 71
Solver Parameter Inputs and Selections Key Formulas
Set Objective: H8 By Changing cells: B4:C4 To: Max Subject to the Constraints: H11:H13 <= J11:J13 Solving Method: GRG Nonlinear R Make Variables Non-Negative Copy H8 to H11:H13
PROGRAM 10.10 – Excel 2013 Solution to the Hospicare NLP Problem
Linear Objective Function and Nonlinear Constraints
Thermlock Corp. produces massive rubber washers and gaskets like the type used to seal joints on the NASA Space Shuttles
It combines two ingredients, rubber (X1) and oil (X2)
The cost of the industrial quality rubber is $5 per pound and the cost of high viscosity oil is $7 per pound
Two of the three constraints are nonlinear
Copyright ©2015 Pearson Education, Inc.
10 – 72
Linear Objective Function and Nonlinear Constraints
Objective function and constraints
Copyright ©2015 Pearson Education, Inc.
10 – 73
Minimize costs = $5X1 + $7X2
subject to
3X1 + 0.25X12 + 4X2 + 0.3X22 ≥ 125 (hardness constraint)
13X1 + X13 ≥ 80 (tensile strength)
0.7X1 + X2 ≥ 17 (elasticity)
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 74
PROGRAM 10.11 – Excel 2013 Solution to the Thermlock NLP Problem
Using Software
Copyright ©2015 Pearson Education, Inc.
10 – 75
Solver Parameter Inputs and Selections Key Formulas
Set Objective: D5 By Changing cells: B4:C4 To: Min Subject to the Constraints: G10:G12 >= I10:I12 Solving Method: GRG Nonlinear R Make Variables Non-Negative Copy G10 to G11:G12
PROGRAM 10.11 – Excel 2013 Solution to the Thermlock NLP Problem
Copyright
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America.
1
1.6 The Role of Computers and Spreadsheet Models in the Quantitative Analysis Approach
1.7 Possible Problems in the Quantitative Analysis Approach
1.8 Implementation—Not Just the Final Step
1.1 Introduction 1.2 What Is Quantitative Analysis? 1.3 Business Analytics 1.4 The Quantitative Analysis Approach 1.5 How to Develop a Quantitative Analysis Model
CHAPTER OUTLINE
5. Use computers and spreadsheet models to perform quantitative analysis.
6. Discuss possible problems in using quantitative analysis.
7. Perform a break-even analysis.
1. Describe the quantitative analysis approach. 2. Understand the application of quantitative analysis
in a real situation. 3. Describe the three categories of business analytics. 4. Describe the use of modeling in quantitative
analysis.
After completing this chapter, students will be able to:
Introduction to Quantitative Analysis
1CHAPTER
LEARNING OBJECTIVES
M01_REND7331_12_SE_C01_pp2.indd 1 01/10/13 9:50 AM
1
1.6 The Role of Computers and Spreadsheet Models in the Quantitative Analysis Approach
1.7 Possible Problems in the Quantitative Analysis Approach
1.8 Implementation—Not Just the Final Step
1.1 Introduction 1.2 What Is Quantitative Analysis? 1.3 Business Analytics 1.4 The Quantitative Analysis Approach 1.5 How to Develop a Quantitative Analysis Model
CHAPTER OUTLINE
5. Use computers and spreadsheet models to perform quantitative analysis.
6. Discuss possible problems in using quantitative analysis.
7. Perform a break-even analysis.
1. Describe the quantitative analysis approach. 2. Understand the application of quantitative analysis
in a real situation. 3. Describe the three categories of business analytics. 4. Describe the use of modeling in quantitative
analysis.
After completing this chapter, students will be able to:
Introduction to Quantitative Analysis
1CHAPTER
LEARNING OBJECTIVES
M01_REND7331_12_SE_C01_pp2.indd 1 01/10/13 9:50 AM
Limits are used, and the best solution available after a certain time is presented.
Notice that only X must be integer, while Y may be any real number.