Introduction to Ontology and IDEs for Ontologies
Chapter 2
Introduction to Linear Programming
n
Linear Programming Problem
n
Problem Formulation
n
A Maximization Problem
n
Graphical Solution Procedure
n
Extreme Points and the Optimal Solution
n
Computer Solutions
n
A Minimization Problem
n
Special Cases
Linear Programming (LP) Problem
n
The
maximization
or
minimization
of some quantity is
the
objective
in all linear programming problems.
n
All LP problems have
constraints
that limit the degree
to which the objective can be pursued.
n
A
feasible solution
satisfies all the problem's
constraints.
n
An
optimal solution
is a feasible solution that results in
the largest possible objective function value when
maximizing (or smallest when minimizing).
n
A
graphical solution method
can be used to solve a
linear program with two variables.
Linear Programming (LP) Problem
n
If both the objective function and the constraints are
linear, the problem is referred to as a
linear
programming problem
.
n
Linear functions
are functions in which each variable
appears in a separate term raised to the first power and
is multiplied by a constant (which could be 0).
n
Linear constraints
are linear functions that are
restricted to be "less than or equal to", "equal to", or
"greater than or equal to" a constant.
Problem Formulation
n
Problem formulation or modeling
is the process of
translating a verbal statement of a problem into a
mathematical statement.
Guidelines for Model Formulation
n
Understand the problem thoroughly.
n
Describe the objective.
n
Describe each constraint.
n
Define the decision variables.
n
Write the objective in terms of the decision variables.
n
Write the constraints in terms of the decision variables.
Example 1: A Maximization Problem
n
LP Formulation
LP Formulation
Max 5
Max 5
x
x
1
1
+ 7
+ 7
x
x
2
2
s.t.
s.t.
x
x
1
1
<
<
6
6
2
2
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
19
19
x
x
1
1
+
+
x
x
2
2
<
<
8
8
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example 1: Graphical Solution
n
Constraint #1 Graphed
Constraint #1 Graphed
x
x
2
2
x
x
1
1
x
x
1
1
<
<
6
6
(6, 0)
(6, 0)
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Constraint #2 Graphed
Constraint #2 Graphed
2
2
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
19
19
x
x
2
2
x
x
1
1
(0, 6
(0, 6
1/3
1/3
)
)
(9
(9
1/2
1/2
, 0)
, 0)
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Constraint #3 Graphed
Constraint #3 Graphed
x
x
2
2
x
x
1
1
x
x
1
1
+
+
x
x
2
2
<
<
8
8
(0, 8)
(0, 8)
(8, 0)
(8, 0)
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Combined-Constraint Graph
Combined-Constraint Graph
2
2
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
19
19
x
x
2
2
x
x
1
1
x
x
1
1
+
+
x
x
2
2
<
<
8
8
x
x
1
1
<
<
6
6
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Feasible Solution Region
Feasible Solution Region
x
x
1
1
Feasible
Feasible
Region
Region
x
x
2
2
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Objective Function Line
Objective Function Line
x
x
1
1
x
x
2
2
(7, 0)
(7, 0)
(0, 5)
(0, 5)
Objective Function
Objective Function
5
5
x
x
1
1
+
+
7x
7x
2
2
= 35
= 35
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution
n
Optimal Solution
Optimal Solution
x
x
1
1
x
x
2
2
Objective Function
Objective Function
5
5
x
x
1
1
+
+
7x
7x
2
2
= 46
= 46
Optimal Solution
Optimal Solution
(
(
x
x
1
1
= 5,
= 5,
x
x
2
2
= 3)
= 3)
Summary of the Graphical Solution Procedure
for Maximization Problems
n
Prepare a graph of the feasible solutions for each of the
constraints.
n
Determine the feasible region that satisfies all the
constraints simultaneously..
n
Draw an objective function line.
n
Move parallel objective function lines toward larger
objective function values without entirely leaving the
feasible region.
n
Any feasible solution on the objective function line
with the largest value is an optimal solution.
Slack and Surplus Variables
n
A linear program in which all the variables are non-
negative and all the constraints are equalities is said to
be in
standard form
.
n
Standard form is attained by adding
slack variables
to
"less than or equal to" constraints, and by subtracting
surplus variables
from "greater than or equal to"
constraints.
n
Slack and surplus variables represent the difference
between the left and right sides of the constraints.
n
Slack and surplus variables have objective function
coefficients equal to 0.
Example 1: Standard Form
Max 5
x
1
+ 7
x
2
+ 0
s
1
+ 0
s
2
+ 0
s
3
s.t.
x
1
+
s
1
= 6
2
x
1
+ 3
x
2
+
s
2
= 19
x
1
+
x
2
+
s
3
= 8
x
1
,
x
2
,
s
1
,
s
2
,
s
3
>
0
Extreme Points and the Optimal Solution
n
The corners or vertices of the feasible region are
referred to as the
extreme points
.
n
An optimal solution to an LP problem can be found at
an extreme point of the feasible region.
n
When looking for the optimal solution, you do not
have to evaluate all feasible solution points.
n
You have to consider only the extreme points of the
feasible region.
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Example 1: Extreme Points
x
x
1
1
Feasible
Feasible
Region
Region
1
1
2
2
3
3
4
4
5
5
x
x
2
2
Computer Solutions
n
Computer programs designed to solve LP problems are
now widely available.
n
Most large LP problems can be solved with just a few
minutes of computer time.
n
Small LP problems usually require only a few seconds.
n
Linear programming solvers are now part of many
spreadsheet packages, such as
Microsoft Excel
.
Interpretation of Computer Output
n
In this chapter we will discuss the following output:
•
objective function value
•
values of the decision variables
•
reduced costs
•
slack/surplus
n
In the next chapter we will discuss how an optimal
solution is affected by a change in:
•
a coefficient of the objective function
•
the right-hand side value of a constraint
Example 1: Spreadsheet Solution
n
Partial Spreadsheet Showing Problem Data
Partial Spreadsheet Showing Problem Data
Example 1: Spreadsheet Solution
n
Partial Spreadsheet Showing Solution
Partial Spreadsheet Showing Solution
Example 1: Spreadsheet Solution
n
Interpretation of Computer Output
Interpretation of Computer Output
We see from the previous slide that:
We see from the previous slide that:
Objective Function Value = 46
Objective Function Value = 46
Decision Variable #1 (
Decision Variable #1 (
x
x
1
1
) = 5
) = 5
Decision Variable #2 (
Decision Variable #2 (
x
x
2
2
) = 3
) = 3
Slack in Constraint #1 = 1 (= 6 - 5)
Slack in Constraint #1 = 1 (= 6 - 5)
Slack in Constraint #2 = 0 (= 19 - 19)
Slack in Constraint #2 = 0 (= 19 - 19)
Slack in Constraint #3 = 0 (= 8 - 8)
Slack in Constraint #3 = 0 (= 8 - 8)
Reduced Cost
n
The
reduced cost
for a decision variable whose value is
0 in the optimal solution is the amount the variable's
objective function coefficient would have to improve
(increase for maximization problems, decrease for
minimization problems) before this variable could
assume a positive value.
n
The reduced cost for a decision variable with a positive
value is 0.
Example 1: Spreadsheet Solution
n
Reduced Costs
Reduced Costs
Example 2: A Minimization Problem
n
LP Formulation
LP Formulation
Min 5
Min 5
x
x
1
1
+ 2
+ 2
x
x
2
2
s.t. 2
s.t. 2
x
x
1
1
+ 5
+ 5
x
x
2
2
>
>
10
10
4
4
x
x
1
1
-
-
x
x
2
2
>
>
12
12
x
x
1
1
+
+
x
x
2
2
>
>
4
4
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example 2: Graphical Solution
n
Graph the Constraints
Graph the Constraints
Constraint 1
Constraint 1
: When
: When
x
x
1
1
= 0, then
= 0, then
x
x
2
2
= 2; when
= 2; when
x
x
2
2
= 0,
= 0,
then
then
x
x
1
1
= 5. Connect (5,0) and (0,2). The ">" side is
= 5. Connect (5,0) and (0,2). The ">" side is
above this line.
above this line.
Constraint 2
Constraint 2
: When
: When
x
x
2
2
= 0, then
= 0, then
x
x
1
1
= 3. But setting
= 3. But setting
x
x
1
1
to
to
0 will yield
0 will yield
x
x
2
2
= -12, which is not on the graph.
= -12, which is not on the graph.
Thus, to get a second point on this line, set
Thus, to get a second point on this line, set
x
x
1
1
to
to
any number larger than 3 and solve for
any number larger than 3 and solve for
x
x
2
2
: when
: when
x
x
1
1
= 5,
= 5,
then
then
x
x
2
2
= 8. Connect (3,0) and (5,8). The ">"
= 8. Connect (3,0) and (5,8). The ">"
side is to the right.
side is to the right.
Constraint 3
Constraint 3
: When
: When
x
x
1
1
= 0, then
= 0, then
x
x
2
2
= 4; when
= 4; when
x
x
2
2
= 0,
= 0,
then
then
x
x
1
1
= 4. Connect (4,0) and (0,4). The ">" side is
= 4. Connect (4,0) and (0,4). The ">" side is
above this line.
above this line.
Example 2: Graphical Solution
n
Constraints Graphed
Constraints Graphed
5
5
4
4
3
3
2
2
1
1
1 2 3 4 5 6
1 2 3 4 5 6
x
x
2
2
4
4
x
x
1
1
-
-
x
x
2
2
>
>
12
12
x
x
1
1
+
+
x
x
2
2
>
>
4
4
2
2
x
x
1
1
+ 5
+ 5
x
x
2
2
>
>
10
10
x
x
1
1
Feasible Region
Feasible Region
Example 2: Graphical Solution
n
Graph the Objective Function
Graph the Objective Function
Set the objective function equal to an arbitrary
Set the objective function equal to an arbitrary
constant (say 20) and graph it. For 5
constant (say 20) and graph it. For 5
x
x
1
1
+ 2
+ 2
x
x
2
2
= 20, when
= 20, when
x
x
1
1
= 0, then
= 0, then
x
x
2
2
= 10; when
= 10; when
x
x
2
2
= 0, then
= 0, then
x
x
1
1
= 4. Connect
= 4. Connect
(4,0) and (0,10).
(4,0) and (0,10).
n
Move the Objective Function Line Toward Optimality
Move the Objective Function Line Toward Optimality
Move it in the direction which lowers its value
Move it in the direction which lowers its value
(down), since we are minimizing, until it touches the
(down), since we are minimizing, until it touches the
last point of the feasible region, determined by the last
last point of the feasible region, determined by the last
two constraints.
two constraints.
Example 2: Graphical Solution
n
Objective Function Graphed
Objective Function Graphed
5
4
3
2
1
1 2 3 4 5 6
x
x
2
2
Min
Min
z
z
= 5
= 5
x
x
1
1
+ 2
+ 2
x
x
2
2
4
4
x
x
1
1
-
-
x
x
2
2
>
>
12
12
x
x
1
1
+
+
x
x
2
2
>
>
4
4
2
2
x
x
1
1
+ 5
+ 5
x
x
2
2
>
>
10
10
x
x
1
1
n
Solve for the Extreme Point at the Intersection of the
Solve for the Extreme Point at the Intersection of the
Two Binding Constraints
Two Binding Constraints
4
4
x
x
1
1
-
-
x
x
2
2
= 12
= 12
x
x
1
1
+
+
x
x
2
2
= 4
= 4
Adding these two equations gives:
Adding these two equations gives:
5
5
x
x
1
1
= 16 or
= 16 or
x
x
1
1
= 16/5.
= 16/5.
Substituting this into
Substituting this into
x
x
1
1
+
+
x
x
2
2
= 4 gives:
= 4 gives:
x
x
2
2
= 4/5
= 4/5
Example 2: Graphical Solution
Example 2: Graphical Solution
n
Solve for the Optimal Value of the Objective Function
Solve for the Optimal Value of the Objective Function
Solve for
Solve for
z
z
= 5
= 5
x
x
1
1
+ 2
+ 2
x
x
2
2
= 5(16/5) + 2(4/5) = 88/5.
= 5(16/5) + 2(4/5) = 88/5.
Thus the optimal solution is
Thus the optimal solution is
x
x
1
1
= 16/5;
= 16/5;
x
x
2
2
= 4/5;
= 4/5;
z
z
= 88/5
= 88/5
Example 2: Graphical Solution
n
Optimal Solution
Optimal Solution
5
4
3
2
1
1 2 3 4 5 6
x
x
2
2
Min
Min
z
z
= 5
= 5
x
x
1
1
+ 2
+ 2
x
x
2
2
4
4
x
x
1
1
-
-
x
x
2
2
>
>
12
12
x
x
1
1
+
+
x
x
2
2
>
>
4
4
2
2
x
x
1
1
+ 5
+ 5
x
x
2
2
>
>
10
10
Optimal:
Optimal:
x
x
1
1
= 16/5
= 16/5
x
x
2
2
= 4/5
= 4/5
x
x
1
1
Example 2: Spreadsheet Solution
n
Partial Spreadsheet Showing Problem Data
Partial Spreadsheet Showing Problem Data
Example 2: Spreadsheet Solution
n
Partial Spreadsheet Showing Formulas
Partial Spreadsheet Showing Formulas
Example 2: Spreadsheet Solution
n
Partial Spreadsheet Showing Solution
Partial Spreadsheet Showing Solution
Feasible Region
n
The feasible region for a two-variable LP problem can
be nonexistent, a single point, a line, a polygon, or an
unbounded area.
n
Any linear program falls in one of three categories:
•
is infeasible
•
has a unique optimal solution or alternate optimal
solutions
•
has an objective function that can be increased
without bound
n
A feasible region may be unbounded and yet there may
be optimal solutions. This is common in minimization
problems and is possible in maximization problems.
Special Cases
n
Alternative Optimal Solutions
Alternative Optimal Solutions
In the graphical method, if the objective function line
In the graphical method, if the objective function line
is parallel to a boundary constraint in the direction of
is parallel to a boundary constraint in the direction of
optimization, there are
optimization, there are
alternate optimal solutions
alternate optimal solutions
,
,
with all points on this line segment being optimal.
with all points on this line segment being optimal.
n
Infeasibility
Infeasibility
A linear program which is overconstrained so that no
A linear program which is overconstrained so that no
point satisfies all the constraints is said to be
point satisfies all the constraints is said to be
infeasible
infeasible
.
.
n
Unboundedness
Unboundedness
(See example on upcoming slide.)
(See example on upcoming slide.)
Example: Infeasible Problem
n
Solve graphically for the optimal solution:
Solve graphically for the optimal solution:
Max 2
Max 2
x
x
1
1
+ 6
+ 6
x
x
2
2
s.t. 4
s.t. 4
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
12
12
2
2
x
x
1
1
+
+
x
x
2
2
>
>
8
8
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example: Infeasible Problem
n
There are no points that satisfy both constraints, hence
this problem has no feasible region, and no optimal
solution.
x
x
2
2
x
x
1
1
4
4
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
12
12
2
2
x
x
1
1
+
+
x
x
2
2
>
>
8
8
3
3
4
4
4
4
8
8
Example: Unbounded Problem
n
Solve graphically for the optimal solution:
Solve graphically for the optimal solution:
Max 3
Max 3
x
x
1
1
+ 4
+ 4
x
x
2
2
s.t.
s.t.
x
x
1
1
+
+
x
x
2
2
>
>
5
5
3
3
x
x
1
1
+
+
x
x
2
2
>
>
8
8
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example: Unbounded Problem
n
The feasible region is unbounded and the objective
function line can be moved parallel to itself without
bound so that
z
can be increased infinitely.
x
x
2
2
x
x
1
1
3
3
x
x
1
1
+
+
x
x
2
2
>
>
8
8
x
x
1
1
+
+
x
x
2
2
>
>
5
5
Max 3
Max 3
x
x
1
1
+ 4
+ 4
x
x
2
2
5
5
5
5
8
8
2.67
2.67
Solving LP Problem:
Solving LP Problem:
Blue Ridge Hot Tubs
Blue Ridge Hot Tubs
A Graphical Approach
A Graphical Approach
MAX: 350X
MAX: 350X
1
1
+ 300X
+ 300X
2
2
S.T.:
S.T.:
1X
1X
1
1
+ 1X
+ 1X
2
2
<= 200
<= 200
9X
9X
1
1
+ 6X
+ 6X
2
2
<= 1566
<= 1566
12X
12X
1
1
+ 16X
+ 16X
2
2
<= 2880
<= 2880
X
X
1
1
>= 0
>= 0
X
X
2
2
>= 0
>= 0
Plotting the First Constraint
Plotting the First Constraint
Plotting the Second Constraint
Plotting the Second Constraint
Plotting the Third Constraint
Plotting the Third Constraint
X
2
Plotting A Level Curve of the
Plotting A Level Curve of the
Objective Function
Objective Function
A Second Level Curve of the
A Second Level Curve of the
Objective Function
Objective Function
Using A Level Curve to Locate
Using A Level Curve to Locate
the Optimal Solution
the Optimal Solution
Calculating the Optimal Solution
Calculating the Optimal Solution
n
The optimal solution occurs where the “pumps” and
“labor” constraints intersect.
n
This occurs where:
X
1
+ X
2
= 200
(1)
and
9X
1
+ 6X
2
= 1566
(2)
n
From (1) we have, X
2
= 200 -X
1
(3)
n
Substituting (3) for X
2
in (2) we have,
9X
1
+ 6 (200 -X
1
) = 1566
which reduces to X
1
= 122
n
So the optimal solution is,
X
1
=122, X
2
=200-X
1
=78
Total Profit = $350*122 + $300*78 = $66,100
Example of a Redundant Constraint
Example of a Redundant Constraint
Enumerating The Corner Points
Enumerating The Corner Points
Note: This technique will not
Note: This technique will not
work if the solution is unbounded.
work if the solution is unbounded.
Understanding How Things Change
Understanding How Things Change
See file
See file
Example.xls
Example.xls
Ontology is a detailed study of the nature of existence or reality, often represented in structured formats for various applications. Explore different Integrated Development Environments (IDEs) tailored for working with ontologies, from simple text editors to more advanced tools like Protégé and Web Protégé. Dive into the Manchester OWL syntax and data values and datatypes used in ontology development.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 2 Introduction to Linear Programming Linear Programming Problem Problem Formulation A Maximization Problem Graphical Solution Procedure Extreme Points and the Optimal Solution Computer Solutions A Minimization Problem Special Cases
Linear Programming (LP) Problem The maximization or minimization of some quantity is the objective in all linear programming problems. All LP problems have constraints that limit the degree to which the objective can be pursued. A feasible solution satisfies all the problem's constraints. An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing). A graphical solution method can be used to solve a linear program with two variables.
Linear Programming (LP) Problem If both the objective function and the constraints are linear, the problem is referred to as a linear programming problem. Linear functions are functions in which each variable appears in a separate term raised to the first power and is multiplied by a constant (which could be 0). Linear constraints are linear functions that are restricted to be "less than or equal to", "equal to", or "greater than or equal to" a constant.
Problem Formulation Problem formulation or modeling is the process of translating a verbal statement of a problem into a mathematical statement.
Guidelines for Model Formulation Understand the problem thoroughly. Describe the objective. Describe each constraint. Define the decision variables. Write the objective in terms of the decision variables. Write the constraints in terms of the decision variables.
Example 1: A Maximization Problem LP Formulation Max 5x1+ 7x2 s.t. x1 < 6 2x1+ 3x2< 19 x1+ x2< 8 x1, x2> 0
Example 1: Graphical Solution Constraint #1 Graphed x2 8 7 x1 < 6 6 5 4 3 2 (6, 0) 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Constraint #2 Graphed x2 8 (0, 6 1/3) 7 6 5 2x1 + 3x2 < 19 4 3 (9 1/2, 0) 2 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Constraint #3 Graphed x2 (0, 8) 8 7 x1 + x2 < 8 6 5 4 3 2 (8, 0) 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Combined-Constraint Graph x2 x1 + x2 < 8 8 7 x1 < 6 6 5 4 2x1 + 3x2 < 19 3 2 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Feasible Solution Region x2 8 7 6 5 4 3 Feasible Region 2 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Objective Function Line x2 8 7 (0, 5) Objective Function 5x1 + 7x2 = 35 6 5 4 3 2 (7, 0) 1 x1 1 2 3 4 5 6 7 8 9 10
Example 1: Graphical Solution Optimal Solution x2 Objective Function 5x1 + 7x2 = 46 8 7 Optimal Solution (x1 = 5, x2 = 3) 6 5 4 3 2 1 x1 1 2 3 4 5 6 7 8 9 10
Summary of the Graphical Solution Procedure for Maximization Problems Prepare a graph of the feasible solutions for each of the constraints. Determine the feasible region that satisfies all the constraints simultaneously.. Draw an objective function line. Move parallel objective function lines toward larger objective function values without entirely leaving the feasible region. Any feasible solution on the objective function line with the largest value is an optimal solution.
Slack and Surplus Variables A linear program in which all the variables are non- negative and all the constraints are equalities is said to be in standard form. Standard form is attained by adding slack variables to "less than or equal to" constraints, and by subtracting surplus variables from "greater than or equal to" constraints. Slack and surplus variables represent the difference between the left and right sides of the constraints. Slack and surplus variables have objective function coefficients equal to 0.
Example 1: Standard Form Max 5x1 + 7x2 + 0s1 + 0s2 + 0s3 s.t. x1 + s1 2x1 + 3x2 + s2 x1 + x2 = 6 = 19 + s3 = 8 x1, x2 , s1 , s2 , s3 > 0
Extreme Points and the Optimal Solution The corners or vertices of the feasible region are referred to as the extreme points. An optimal solution to an LP problem can be found at an extreme point of the feasible region. When looking for the optimal solution, you do not have to evaluate all feasible solution points. You have to consider only the extreme points of the feasible region.
Example 1: Extreme Points x2 8 7 5 6 5 4 4 3 Feasible Region 3 2 1 1 2 x1 1 2 3 4 5 6 7 8 9 10
Computer Solutions Computer programs designed to solve LP problems are now widely available. Most large LP problems can be solved with just a few minutes of computer time. Small LP problems usually require only a few seconds. Linear programming solvers are now part of many spreadsheet packages, such as Microsoft Excel.
Interpretation of Computer Output In this chapter we will discuss the following output: objective function value values of the decision variables reduced costs slack/surplus In the next chapter we will discuss how an optimal solution is affected by a change in: a coefficient of the objective function the right-hand side value of a constraint
Example 1: Spreadsheet Solution Partial Spreadsheet Showing Problem Data A B C D 1 2 3 4 5 6 LHS Coefficients Constraints #1 #2 #3 Obj.Func.Coeff. X1 1 2 1 5 X2 0 3 1 7 RHS Values 6 19 8
Example 1: Spreadsheet Solution Partial Spreadsheet Showing Solution A B C D 8 9 Optimal Decision Variable Values X1 5.0 X2 3.0 10 11 12 13 14 15 16 17 46.0 Maximized Objective Function Constraints #1 #2 #3 Amount Used 5 19 8 RHS Limits 6 19 8 <= <= <=
Example 1: Spreadsheet Solution Interpretation of Computer Output We see from the previous slide that: Objective Function Value = 46 Decision Variable #1 (x1) = 5 Decision Variable #2 (x2) = 3 Slack in Constraint #1 = 1 (= 6 - 5) Slack in Constraint #2 = 0 (= 19 - 19) Slack in Constraint #3 = 0 (= 8 - 8)
Reduced Cost The reduced cost for a decision variable whose value is 0 in the optimal solution is the amount the variable's objective function coefficient would have to improve (increase for maximization problems, decrease for minimization problems) before this variable could assume a positive value. The reduced cost for a decision variable with a positive value is 0.
Example 1: Spreadsheet Solution Reduced Costs Adjustable Cells Final Reduced Cost Objective Coefficient Allowable Increase Allowable Decrease 2 0.333333333 0.5 Cell $B$8 $C$8 Name Value X1 X2 5.0 3.0 0.0 0.0 5 7 2 Constraints Final Shadow Price Constraint R.H. Side Allowable Increase Allowable Decrease Cell $B$13 #1 $B$14 #2 $B$15 #3 Name Value 5 0 2 1 6 1E+30 1 1 19 8 19 8 0.333333333 1.666666667 5
Example 2: A Minimization Problem LP Formulation Min 5x1 + 2x2 4x1 - x2 > 12 x1 + x2 > 4 s.t. 2x1 + 5x2 > 10 x1, x2 > 0
Example 2: Graphical Solution Graph the Constraints Constraint 1: When x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5. Connect (5,0) and (0,2). The ">" side is above this line. Constraint 2: When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2 = -12, which is not on the graph. Thus, to get a second point on this line, set x1 to any number larger than 3 and solve for x2: when x1 = 5, then x2 = 8. Connect (3,0) and (5,8). The ">" side is to the right. Constraint 3: When x1 = 0, then x2 = 4; when x2 = 0, then x1 = 4. Connect (4,0) and (0,4). The ">" side is above this line.
Example 2: Graphical Solution Constraints Graphed x2 Feasible Region 4x1 - x2 > 12 5 x1 + x2 > 4 4 3 2x1 + 5x2 > 10 2 1 1 2 3 4 5 6 x1
Example 2: Graphical Solution Graph the Objective Function Set the objective function equal to an arbitrary constant (say 20) and graph it. For 5x1 + 2x2 = 20, when x1 = 0, then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0) and (0,10). Move the Objective Function Line Toward Optimality Move it in the direction which lowers its value (down), since we are minimizing, until it touches the last point of the feasible region, determined by the last two constraints.
Example 2: Graphical Solution Objective Function Graphed Min z = 5x1 + 2x2 x2 4x1 - x2 > 12 5 x1 + x2 > 4 4 3 2x1 + 5x2 > 10 2 1 1 2 3 4 5 6 x1
Example 2: Graphical Solution Solve for the Extreme Point at the Intersection of the Two Binding Constraints 4x1 - x2 = 12 x1+ x2 = 4 Adding these two equations gives: 5x1 = 16 or x1 = 16/5. Substituting this into x1 + x2 = 4 gives: x2 = 4/5
Example 2: Graphical Solution Solve for the Optimal Value of the Objective Function Solve for z = 5x1 + 2x2 = 5(16/5) + 2(4/5) = 88/5. Thus the optimal solution is x1 = 16/5; x2 = 4/5; z = 88/5
Example 2: Graphical Solution Optimal Solution Min z = 5x1 + 2x2 x2 4x1 - x2 > 12 5 x1 + x2 > 4 4 2x1 + 5x2 > 10 3 2 Optimal: x1 = 16/5 x2 = 4/5 x1 1 1 2 3 4 5 6
Example 2: Spreadsheet Solution Partial Spreadsheet Showing Problem Data A B C D 1 2 3 4 5 6 Obj.Func.Coeff. LHS Coefficients Constraints #1 #2 #3 X1 2 4 1 5 X2 5 -1 1 2 RHS 10 12 4
Example 2: Spreadsheet Solution Partial Spreadsheet Showing Formulas A B Decision Variables C D 9 10 11 Dec.Var.Values 12 13 14 15 Constraints 16 17 18 X1 X2 =B6*B11+C6*C11 Minimized Objective Function Amount Used =B3*$B$11+C3*$C$11 =B4*$B$11+C4*$C$11 =B5*$B$11+C5*$C$11 Amount Avail. =D3 =D4 =D5 #1 #2 #3 >= >= >=
Example 2: Spreadsheet Solution Partial Spreadsheet Showing Solution A B Decision Variables C D 9 10 11 Dec.Var.Values 12 13 14 15 Constraints 16 17 18 X1 3.20 X2 0.800 17.600 Minimized Objective Function Amount Used 10.4 12 4 Amount Avail. 10 12 4 #1 #2 #3 >= >= >=
Feasible Region The feasible region for a two-variable LP problem can be nonexistent, a single point, a line, a polygon, or an unbounded area. Any linear program falls in one of three categories: is infeasible has a unique optimal solution or alternate optimal solutions has an objective function that can be increased without bound A feasible region may be unbounded and yet there may be optimal solutions. This is common in minimization problems and is possible in maximization problems.
Special Cases Alternative Optimal Solutions In the graphical method, if the objective function line is parallel to a boundary constraint in the direction of optimization, there are alternate optimal solutions, with all points on this line segment being optimal. Infeasibility A linear program which is overconstrained so that no point satisfies all the constraints is said to be infeasible. Unboundedness (See example on upcoming slide.)
Example: Infeasible Problem Solve graphically for the optimal solution: Max 2x1 + 6x2 s.t. 4x1 + 3x2 < 12 2x1 + x2 > 8 x1, x2 > 0
Example: Infeasible Problem There are no points that satisfy both constraints, hence this problem has no feasible region, and no optimal solution. x2 2x1 + x2 > 8 8 4x1 + 3x2 < 12 4 x1 3 4
Example: Unbounded Problem Solve graphically for the optimal solution: Max 3x1 + 4x2 s.t. x1 + x2 > 5 3x1 + x2 > 8 x1, x2 > 0
Example: Unbounded Problem The feasible region is unbounded and the objective function line can be moved parallel to itself without bound so that z can be increased infinitely. x2 3x1 + x2 > 8 8 Max 3x1 + 4x2 5 x1 + x2 > 5 x1 2.67 5
Solving LP Problem: Blue Ridge Hot Tubs A Graphical Approach MAX: 350X1 + 300X2 S.T.: 1X1 + 1X2 <= 200 9X1 + 6X2 <= 1566 12X1 + 16X2 <= 2880 X1 >= 0 X2 >= 0
Plotting the First Constraint X2 25 0 (0, 200) 20 0 boundary line of pump constraint X1 + X2 = 200 15 0 10 0 50 (200, 0) 0 10 0 X1 0 15 0 20 0 25 0 50
Plotting the Second Constraint X2 (0, 261) 25 0 boundary line of labor constraint 9X1 + 6X2 = 1566 20 0 15 0 10 0 50 (174, 0) 0 10 0 X1 0 15 0 20 0 25 0 50
Plotting the Third Constraint X2 25 0 (0, 180) 20 0 15 0 boundary line of tubing constraint 12X1 + 16X2 = 2880 10 0 Feasible Region 50 (240, 0) 0 10 0 X1 0 15 0 20 0 25 0 50
Plotting A Level Curve of the Objective Function X2 25 0 20 0 (0, 116.67) objective function 350X1 + 300X2 = 35000 15 0 10 0 (100, 0) 50 0 10 0 X1 0 15 0 20 0 25 0 50
A Second Level Curve of the Objective Function X2 25 0 (0, 175) objective function 350X1 + 300X2 = 35000 20 0 objective function 350X1 + 300X2 = 52500 15 0 10 0 (150, 0) 50 0 10 0 X1 0 15 0 20 0 25 0 50
Using A Level Curve to Locate the Optimal Solution X2 25 0 objective function 350X1 + 300X2 = 35000 20 0 15 0 optimal solution 10 0 objective function 350X1 + 300X2 = 52500 50 0 10 0 X1 0 15 0 20 0 25 0 50
Calculating the Optimal Solution The optimal solution occurs where the pumps and labor constraints intersect. This occurs where: X1 + X2 = 200 and 9X1 + 6X2 = 1566 From (1) we have, X2 = 200 -X1 Substituting (3) for X2 in (2) we have, 9X1 + 6 (200 -X1) = 1566 which reduces to X1 = 122 So the optimal solution is, X1=122, X2=200-X1=78 Total Profit = $350*122 + $300*78 = $66,100 (1) (3) (2)
