Linear Programming
Copyright © 2013 Pearson Education, Inc. Publishing as
Prentice Hall
Model Components
Decision variables X1, X2, X3,......Xn
Max
Objective function
Min
Constraints
Parameters
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Steps in application:
Identify problem
Formulate a mathematical model
Solve the model
Implementation
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Model Formulation Steps:
Step 1 : Clearly define the decision
variables
Step 2 : Construct the objective function
Step 3 : Formulate the constraints
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation
A Maximization Example (1 of 4)
• Product mix problem - Beaver Creek Pottery Company
• How many bowls and mugs should be produced to maximize profits
given labor and materials constraints?
• Product resource requirements and unit profit:
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation
A Maximization Example (2 of 4)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation
A Maximization Example (3 of 4)
• 40 hrs of labor per day
Resource Availability
• 120 lbs of clay
• X1 = number of bowls to produce per day
Decision Variables
• X2 = number of mugs to produce per day
• Maximize Z = $40X1 + $50X2
Objective function • Where Z = profit per day
Resource • 1X1 + 2X2 ≤ 40 hours of labor
Constraints • 4X1 + 3X2 ≤ 120 pounds of clay
Non-Negativity • X1 ≥ 0; X2 ≥ 0
Constraints:
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation
A Maximization Example (4 of 4)
• Complete Linear Programming Model:
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Feasible Solutions
• A feasible solution does not violate any of the constraints:
• Example: x1 = 5 bowls
x2 = 10 mugs
Z = $40X1 + $50X2 = $700
• Labor constraint check: 1(5) + 2(10) = 25 < 40 hours
• Clay constraint check: 4(5) + 3(10) = 70 < 120 pounds
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Infeasible Solutions
• infeasible solution violates at least one of the constraints:
• Example: X1 = 10 bowls
X2 = 20 mugs
• Z = $40X1 + $50X2 = $1400
• Labor constraint check: 1(10) + 2(20) = 50 > 40 hours
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Graphical Solution of LP Models
• Graphical solution is limited to linear programming models containing
only two decision variables (can be used with three variables but
only with great difficulty).
• Graphical methods provide visualization of how a solution for a
linear programming problem is obtained.
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Coordinate Axes
Graphical Solution of Maximization Model (1 of 12)
X2 is mugs
X1 is bowls
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Labor Constraint
Graphical Solution of Maximization Model (2 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Labor Constraint Area
Graphical Solution of Maximization Model (3 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Clay Constraint Area
Graphical Solution of Maximization Model (4 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Both Constraints
Graphical Solution of Maximization Model (5 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Feasible Solution Area
Graphical Solution of Maximization Model (6 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Objective Function Solution = $800
Graphical Solution of Maximization Model (7 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Alternative Objective Function Solution Lines
Graphical Solution of Maximization Model (8 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Optimal Solution
Graphical Solution of Maximization Model (9 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Optimal Solution Coordinates
Graphical Solution of Maximization Model (10 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Extreme (Corner) Point Solutions
Graphical Solution of Maximization Model (11 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Optimal Solution for New Objective Function
Graphical Solution of Maximization Model (12 of 12)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Slack Variables
• Standard form requires that all constraints be in the form of
equations (equalities).
• A slack variable is added to a ≤ constraint (weak inequality) to
convert it to an equation (=).
• A slack variable typically represents an unused resource .
• A slack variable contributes nothing to the objective function value.
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Linear Programming Model: Standard Form
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation – Minimization (1 of 8)
• Two brands of fertilizer available - Super-gro, Crop-quick.
• Field requires at least 16 pounds of nitrogen and 24 pounds of
phosphate.
• Super-gro costs $6 per bag, Crop-quick $3 per bag.
• Problem: How much of each brand to purchase to minimize total cost
of fertilizer given following data ?
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation – Minimization (2 of 8)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
LP Model Formulation – Minimization (3 of 8)
• Decision Variables:
X1 = bags of Super-gro
X2 = bags of Crop-quick
• The Objective Function:
Minimize Z = $6X1 + 3X2
Where: $6X1 = cost of bags of Super-Gro
$3X2 = cost of bags of Crop-Quick
• Model Constraints:
2X1 + 4X2 ≥ 16 lb (nitrogen constraint)
4X1 + 3X2 ≥ 24 lb (phosphate constraint)
X1, X2 ≥ 0 (non-negativity constraint)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Constraint Graph– Minimization (4 of 8)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Feasible Region– Minimization (5 of 8)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Optimal Solution Point– Minimization (6 of 8)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Surplus Variables – Minimization (7 of 8)
• A surplus variable is subtracted from a ≥ constraint to convert it to an
equation (=).
• A surplus variable represents an excess above a constraint
requirement level.
• A surplus variable contributes nothing to the calculated value of the
objective function.
• Subtracting surplus variables in the farmer problem constraints:
2X1 + 4X2 - S1 = 16 (nitrogen)
4X1 + 3X2 - S2 = 24 (phosphate)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Graphical Solutions – Minimization (8 of 8)
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Irregular Types of Linear Programming
Problems
• For some linear programming models, the general rules do not apply.
• Special types of problems include those with:
Multiple optimal solutions
Infeasible solutions
Unbounded solutions
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Multiple Optimal Solutions Beaver Creek
Pottery
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
An Infeasible Problem
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
An Unbounded Problem
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Characteristics of Linear Programming
Problems
• A decision amongst alternative courses of action is required.
• The decision is represented in the model by decision variables.
• The problem encompasses a goal, expressed as an objective function,
that the decision maker wants to achieve.
• Restrictions (represented by constraints) exist that limit the extent of
achievement of the objective.
• The objective and constraints must be definable by linear
mathematical functional relationships.
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Properties of Linear Programming Models
• The rate of change (slope) of the objective function and
Proportionality constraint equations is constant.
• Terms in the objective function and constraint equations
Additivity must be additive.
• Decision variables can take on any fractional value and are
Divisibility therefore continuous as opposed to integer in nature.
• Values of all the model parameters are assumed to be
Certainty known with certainty (non-probabilistic).
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Problem Statement
Example Problem No. 1 (1 of 3)
• Hot dog mixture in 1000-pound batches.
• Two ingredients, chicken ($3/lb) and beef ($5/lb).
• Recipe requirements: at least 500 pounds of “chicken”
at least 200 pounds of “beef”
• Ratio of chicken to beef must be at least 2 to 1.
• Determine optimal mixture of ingredients that will minimize costs.
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Solution
Example Problem No. 1 (2 of 3)
• Step 1: Identify decision variables.
X1 = lb of chicken in mixture
X2 = lb of beef in mixture
• Step 2: Formulate the objective function.
Minimize Z = $3X1 + $5X2
where Z = cost per 1,000-lb batch
$3X1 = cost of chicken
$5X2 = cost of beef
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Solution
Example Problem No. 1 (3 of 3)
• Step 3: Establish Model Constraints
X1 + X2 = 1,000 lb
X1 ≥ 500 lb of chicken
X2 ≥ 200 lb of beef
X1/X2 ≥ 2/1 or X1 – 2X2 ≥ 0
X1, X2 ≥ 0
• The Model: Minimize Z = $3X1 + 5X2
subject to: X1 + X2 = 1,000 lb
X1 ≥ 50
X2 ≥ 200
X1 – 2X2 ≥ 0
X1,X2 ≥ 0
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Example Problem No. 2 (1 of 3)
Constraint Equations
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Example Problem No. 2 (2 of 3)
Feasible Solution Space and Extreme Points
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
Example Problem No. 2 (3 of 3)
Optimal Solution Point
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall
