Chapter 3 - Introduction to Linear Programming
Order of coverage 3.1, 3.4 through 3.12, 3.2 and 3.3
Definition: A Linear Programming (LP) problem is an optimization problem where we have limited resources to allocate across competing activities.
LPs have the following 3 characteristics:
1. Decision variables.
2. A linear objective function which is to be either maximized or minimized.
3. A set of linear constraints, where each constraint must be either a linear equation or a linear inequality.
A function f(x1, x2, ... , xn) of x1, x2, ..., xn is a linear function if and only if for some set of constants c1, c2, ... , cn, f(x1, x2, ... , xn) = c1x1 + c2x2 + ... + cnxn
ex.
f(x1, x2) = 3x1 - 5x2 is linear
f(x1, x2) = x12 + 8x1x2 - x3 is not linear
Example: Determining the product mix for Whirlpool dishwashers.
Standard / 20 / 10
Deluxe / 40 / 12
Super Deluxe / 60 / 15
Decision - Choose product mix of the three washer models. Variables - x1, x2, x3
Objective - Maximize Profit.
Constraints - Total labor hours available.
Steps to formulate a LP problem.
Step 1 Read the problem through once quickly.
Step 2 Define the decision variables.
Step 3 Write down what we know.
Step 4 What is the objective (in sentence form)? Max or min? Of what?
Step 5 Write the objective function.
Step 6 What are the constraints (in sentence form)?
Step 7 Write the constraints.
Step 8 Verify.
Ex. Problem 1, Section 3.1, pg. 56
Step 1
Read the problem through once quickly.
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Assumptions for an LP to be an appropriate representation of a real-life problem
(1) The Proportionality and Additivity Assumptions
Objective Function
1. The contribution to the objective function from each decision variable is proportional to the value of the decision variable.
ex. $10 profit/unit sale
selling 2 units yields twice as much profit as selling 1 unit
2. The contribution to the objective function for any variable is independent of the values of the other decision variables.
ex. corn $3/bushel x1
wheat $4/bushel x2
regardless of the x1 value, x2 will contribute $4/bushel
Constraints
Both assumptions hold similarly.
(2) The Divisibility Assumption
Each decision variable can assume fractional values (otherwise Integer Programming - Chapter 9)
(3) The Certainty Assumption
The objective function coefficients, technological coefficients, and RHS parameters are known with certainty.
Feasible and Optimal Solutions
The feasible region for an LP is the set of all points satisfying the constraints.
ex. (1) x1 + x2 ³ 6
(2) x2 £ 3
x1 = 5 and x2 = 2 x1 = 1 and x2 = 6
is feasible is not feasible
(1) 7 ³ 6 Ö (1) 7 ³ 6 Ö
(2) 2 £ 3 Ö (2) 6 £ 3
For a maximization/minimization problem, an optimal solution to an LP is the point in the feasible region with the largest/smallest objective function value.
Formulating LPs
Read the examples carefully in 3.4 - 3.12.
Some of the common problems are:
1. The Diet Problem
2. The Production Scheduling and Inventory Control Problem
3. The Blending Problem
4. The Routing and Assignment Problem
In each of these problems, often the most difficult and important step is defining the decision variables. These variables represent the decisions that need to be made.
· We can also think of them as being the independent vs. dependent variables.
· If we know the values of the decision variables we have the information we need to implement a plan of action.
Remember, there can be more than one correct way to formulate the problem.
Be careful to make sure that the units of measure match! Ex: In constraints.
The Heart Valve Problem - Problem 2, pg. 73, Section 3.4
Step 1
Read the problem through once quickly.
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Verify.
Automobile product mix problem. Additional problem 1.
Step 1
Read the problem through once quickly.
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Verify.
Staff Scheduling Problem - Problem 5 pg. 76, Section 3.5
Step 1
Read the problem through once quickly.
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Verify.
Multiperiod Inventory Problem - Problem 3 pg. 103, Section 3.10
Step 1
Read the problem through once quickly.
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8
Verify.
The Blending Problem - Problem 54, pg 121
Step 1
Read the problem through once quickly.
Step 2
Let HO = barrels of heating oil sold
G = barrels of gasoline sold
J = barrels of jet fuel sold
C1 = barrels of crude 1 purchased
C2 = barrels of crude 2 purchased
HO1 = barrels of distilled 1 used for heating oil
HO2 = barrels of distilled 2 used for heating oil
NJ = barrels of naptha used for jet fuel
NG = barrels of naptha used for gasoline
DO1 = barrels of distilled 1 sent through cracker
DO2 = barrels of distilled 2 sent through cracker
CO1G= barrels of cracked oil 1 used for gasoline
CO2G= barrels of cracked oil 2 used for gasoline
CO1J = barrels of cracked oil 1 used for jet fuel
CO2J = barrels of cracked oil 2 used for jet fuel
Step 3 - See Diagram
Step 4
maximize Ole’s daily profit
Step 5
max z = 18G + 16J + 14HO - 12.1C1 - 10.1C2 - 0.15DO1
- 0.15DO2
Step 6
Amount of crude oil purchased.
Amount of oil which can be distilled.
Cracker capacity.
Octane levels of heating oil, gasoline, and jet fuel.
Demand for heating oil, gasoline, and jet fuel
Step 7
C1 £ 10,000 Crude 1 Purchased
C2 £ 10,000 Crude 2 Purchased
C1 + C2 £ 15,000 Distillation Capacity
DO1 + DO2 £ 5,000 Cracker Capacity
4HO1 + 5HO2 ³ 4.5HO Heating Oil Octane
8NG + 9CO1G + 6CO2G ³ 8.5G Gasoline Octane
8NJ + 9CO1J + 6CO2J ³ 7J Jet Fuel Octane
HO ³ 3000 Heating Oil Demand
G ³ 3000 Gasoline Demand
J ³ 3000 Jet Fuel Demand
All variables ³ 0 Sign restriction
“Balancing” or “Conservation” Constraints
0.6C1 + 0.4C2 = NJ + NG Naptha Production
0.3C1 + 0.2C2 = HO1 + DO1 Distilled Oil 1 Production
0.1C1 + 0.4C2 = HO2 + DO2 Distilled Oil 2 Production
0.8DO1 + 0.7DO2 = CO1G + CO1J Cracked 1 Production
0.2DO1 + 0.3DO2 = CO2G + CO2J Cracked 2 Production
HO1 + HO2 = HO Heating Oil Production
NG + CO1G + CO2G = G Gasoline Production
NJ + CO1J + CO2J = J Jet Fuel Production
Step 8
Verify.
Chap 3 - 34
Graphical Solutions to a Two-Variable LP Problem
Ex. problem 1, section 3.2, pg. 64
From previous notes:
max z = 30x1 + 100x2
st 4x1 + 10x2 £ 40 (1)
x1 + x2 £ 7 (2)
10x1 ³ 30 (3)
x1 ³ 0 (4)
x2 ³ 0 (5)
Find the feasible region.
Now find the optimal solution.
This is the point within the feasible region with the largest value of z, where:
z = 30x1 + 100x2
To do this, graph a line on which all points have the same z value.
In a maximization problem, this line is called an isoprofit line.
In a minimization problem, this line is called an isocost line.
To do this, pick a point in the feasible region and calculate z.
Next, make z equal to this value and calculate the slope of the isoprofit/isocost line.
Ex. of Isoprofit Line
select (4, 1)
z = 30x1 + 100x2
z = 30(4) + 100(1)
z = 220
220 = 30x1 + 100x2
100x2 = 220 - 30 x1
x2 =
This is equivalent to: y = mx + b
where m = slope = -30/100
b = y-intercept = 220/100
All other isoprofit/isocost lines will lie parallel to this line.
Push the line in the northeast direction to maximize, or in the southwest direction to minimize.
The point where the isoprofit/isocost line last intersects the feasible region is the optimal point.
Find the most northeastern point.
Is point B the most northeastern point?
It occurs at the intersection of constraints (1) and (2). To find x1 and x2, solve these equations simultaneously.
4x1 + 10x2 = 40 (1)
x1 + x2 = 7 (2)
(2) x1 = 7 - x2
(1) 4(7 - x2) + 10x2 = 40
28 - 4x2 + 10x2 = 40
6x2 = 12
x2 = 2
(2) x1 = 7 - 2
x1 = 5
The z value at x1 = 5, x2 = 2 is:
z = 30(5) + 100(2)
z = 350
Is point A the most northeastern point?
It occurs at the intersection of constraints (2) and (4). To find x1 and x2, solve these equations simultaneously.
x1 + x2 = 7 (2)
x2 = 0 (4)
(2) 0 + x1 = 7
x1 = 7
The z value at x1=7, x2=0 is:
z = 30(7) + 100(0)
z = 210
Point B has a z value of 350, so eliminate point A from further consideration.
Is point C the most northeastern point?
It occurs at the intersection of constraints (1) and (3). To find x1 and x2, solve these equations simultaneously.
4x1 + 10x2 = 40 (1)
10x1 = 30 (3)
(3) x1 = 3
(1) 4(3) + 10x2 = 40
10x2 = 28
x2 = 2.8
The z value at x1 =3, x2 = 2.8 is:
z = 30(3) + 100(2.8)
z = 370
Therefore, point C is optimal.
Binding and Nonbinding Constraints
A constraint is binding if the LHS and the RHS are equal when the optimal values of the decision variables are substituted into the constraint.
Otherwise the constraint is nonbinding.
This idea is important for sensitivity analysis.
In our example at the optimal point C, (3, 2.8):
(1) 4x1 + 10x2 £ 40 40 £ 40 binding
(2) x1 + x2 £ 7 5.8 £ 7 nonbind.
(3) 10x1 ³ 30 30 ³ 30 binding
(4) x1 ³ 0 3 ³ 0 nonbind.
(5) x2 ³ 0 2.8 ³ 0 nonbind.
You can see this visually on the graph.
Note - The feasible region contains an infinite number of points. Why did we only look at points A, B, and C?
Convex Sets and Extreme Points
A set of points S is a convex set if the line segment joining any pair of points in S is wholly contained in S.
ex.
convex nonconvex
For any convex set S, a point P in S is an extreme point (or a corner point) if each line segment that lies completely in S and contains the point P has P as an endpoint of the line segment.
ex.
A, B, C, D are extreme points
E is not an extreme point
LP Optimal Solutions
It can be shown that if an LP has an optimal solution, it will occur at an extreme point. Hence, only these points need to be evaluated.
Return to graph.
Special Cases of LPs
(1) No feasible solutions - infeasible.
(2) Infinite number of optimal solutions - multiple or alternative.
(3) Unbounded - usually due to an error in the model formulation.
Infeasible Solution
Problem 1, Section 3.3, pg 69
max z = x1 + x2
st x1 + x2 £ 4 (1)
x1 - x2 ³ 5 (2)
x1 ³ 0 (3)
x2 ³ 0 (4)
Infinite Number of Optimal Solutions
This occurs when the isoprofit/isocost line intersects with a line segment corresponding to a binding constraint.
Problem 2, Section 3.3, pg 69
max z = 4x1 + x2
st 8x1 + 2x2 £ 16 (1)
5x1 + 2x2 £ 12 (2)
x1 ³ 0 (3)
x2 ³ 0 (4)
Unbounded Solution
Problem 3, Section 3.3, pg 70
max z = -x1 + 3x2
st x1 - x2 £ 4 (1)
x1 + 2x2 ³ 4 (2)
x1 ³ 0 (3)
x2 ³ 0 (4)
In conclusion, graphical solutions are nice and give useful insights into how we solve LPs. However, most real-life LP problems have more than two variables, thus the graphical method becomes impractical.
Chap 3 - 34