Transcript Lecture (Feb 18)

Water Resources Development and Management
Optimization
(Linear Programming)
CVEN 5393
Feb 18, 2013
Acknowledgements
• Dr. Yicheng Wang (Visiting
Researcher, CADSWES during Fall
2009 – early Spring 2010) for
slides from his Optimization
course during Fall 2009
• Introduction to Operations
Research by Hillier and Lieberman,
McGraw Hill
How to Solve LP Problems
• Graphical Solution
• Simplex Method for Standard form LP
– Geometric Concepts
– Setting up and Algebra
– Algebraic solution of Simplex
• R-Resources
Prototype Model from Hillier and Lieberman
The Wyndor Glass Co. produces high-quality glass products, including windows and glass
doors. It has three plants.
Plant 1 produces Aluminum frames
Plant 2 produces wood frames
Plant 3 produces the glass and assembles the products.
The company has decided to produce two new products.
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4x6 foot double-hung wood framed window
Each product will be produced in batches of 20. The production rate is defined as the
number of batches produced per week.
The company wants to know what the production rate should be in order to maximize
their total profit, subject to the restriction imposed by the limited production
capacities available in the 3 plants.
To get the answer, we need to collect the following data.
(a) Number of hours of production time available per week in each plant for these two new
products. (Most of the time in the 3 plants is already committed to current products, so the
available capacity for the 2 new products is quite limited).
Number of hours of production time available per week in Plant 1 for the new products: 4
Number of hours of production time available per week in Plant 2 for the new products: 12
Number of hours of production time available per week in Plant 3 for the new products: 18
(b) Number of hours of production time used in each plant for each batch produced of each
new product (Product 1 requires some of the production capacity in Plants 1 and 3, but
none in Plant 2. Product 2 needs only Plants 2 and 3).
Number of hours of production time used in Plant 1 for each batch produced of Product 1: 1
Number of hours of production time used in Plant 2 for each batch produced of Product 1: 0
Number of hours of production time used in Plant 3 for each batch produced of Product 1: 3
Number of hours of production time used in Plant 1 for each batch produced of Product 2: 0
Number of hours of production time used in Plant 2 for each batch produced of Product 2: 2
Number of hours of production time used in Plant 3 for each batch produced of Product 2: 2
(c) Profit per batch produced of each new product.
Profit per batch produced of Product 1: $3,000
Profit per batch produced of Product 2: $5,000
The data collected are summarized in Table 3.1.
This is a linear programming problem of the classic product mix type.
Formulation as a Linear Programming Problem
To formulate the LP model for this problem, let
x1 = number of batches of product 1 produced per week
x2 = number of batches of product 2 produced per week
Z = total profit ( in thousands of dollars) from producing the two new products.
Thus, x1 and x2 are the decision variables for the model. Using the data of Table 3.1, we
obtain
(Plant 1:Total production time required)
(Production time available)
(Plant 2:Total production time required)
(Production time available)
(Plant 3:Total production time required)
(Production time available)
(4) Graphical Solution
The Wyndor Glass Co. example is used to illustrate the graphical solution.
Fig. 3.1 Shaded area shows values of (x1,
x2) allowed by x1 ≥ 0, x2 ≥ 0, x1 ≤ 4
Fig. 3.2 Shaded area shows values of
(x1, x2) , called feasible region
Fig. 3.3 The value of (x1, x2) that maximize 3x1 + 5x2 is (2, 6)
Common Terminology for LP Model
Objective Function:
The function being maximized or minimized is called the objective function.
Constraint:
The restrictions of LP Model are referred to as constraints.
The first m constraints in the previous model are sometimes called functional constraints.
The restrictions xj >= 0 are called nonnegativity constraints.
Feasible Solution:
A feasible solution is a solution for which all the
constraints are satisfied.
Infeasible Solution:
An infeasible solution is a solution for which at
least one constraint is violated.
Feasible Region:
The feasible region is the collection of all feasible
solutions.
A feasible solution is
located in the feasible
region. An infeasible
solution is outside the
feasible region.
Common Terminology for LP Model
No Feasible Solutions:
It is possible for a problem to have no feasible solutions.
An Example
Fig. 3.4 The Wyndor Glass Co.
problem would have no feasible
solutions if the constraint 3x1 +
5x2 ≤ 50 were added to the
problem.
In this case, there is
no feasible region
Common Terminology for LP Model
Optimal Solution:
An optimal solution is a feasible solution that has the maximum or minimum of the
objective function.
Multiple Optimal Solutions:
It is possible to have more than
one optimal solution.
An Example
Fig. 3.5 The Wyndor Glass Co.
problem would have multiple optimal
solutions if the objective function
were changed to Z = 3x1 + 2x2
Common Terminology for LP Model
Unbounded Objective:
If the constraints do not prevent
improving the value of the
objective function indefinitely in
the favorable direction, the LP
model is called having an
unbounded objective.
An Example
Fig. 3.6 The Wyndor Glass Co.
problem would have no optimal
solutions if the only functional
constrait were x1 ≤ 4, because x2 then
could be increased indefinitely in the
feasible region without ever reaching
the maximum value of Z = 3x1 + 2x2
Common Terminology for LP Model
Corner-Point Feasible (CPF) Solution:
A corner-point feasible (CPF) is a solution that lies at a corner of the feasible region.
Fig. 3.7 The five dots are the five
CPF solutions for the Wyndor Glass
Co. problem
Common Terminology for LP Model
Relationship between optimal solutions and CPF solutions :
Consider any linear programming problem with feasible solutions and a bounded feasible
region. The problem must posses CPF solutions and at least one optimal solution.
Furthermore, the best CPF solution must be an optimal solution. Therefore, if a problem
has exactly one optimal solution, it must be a CPF solution. If the problem has multiple
optimal solutions, at least two must be CPF solutions.
(2,6)
(4,3)
The prototype model has exactly one
optimal solution, (x1, x2)=(2,6), which
is a CPF solution
The modified problem has multiple
optimal solution, two of these optimal
solutions , (2,6) and (4,3), are CPF
solutions.
Matrix Standard Form of an LP Model
To help you distinguish
between matrices, vectors,
and scalars, we use
BOLDFACE CAPITAL
letters to represent matrices,
bold lowercase letters to
represent vectors, and
italicized letters in ordinary
print to represent scalars.
Tabular Standard Form of an LP Model
Transforming Any LP Model into the Standard Form
(1) Minimizing rather than maximizing the objective
Maximize
Z΄ = – Z
(2) Some functional constraints with a less-than-or-equal-to inequality
Introduce the concept of slack variables.
To illustrate, use the first functional constraint, x1 ≤ 4, in the Wyndor Glass
Co. problem as an example. x1 ≤ 4 is equivalent to x1 + x2=4 where x2 ≥ 0.
The variable x2 is called a slack variable.
(3) Some functional constraints with a greater-than-or-equal-to inequality
Introduce the concept of surplus variables.
For example, a functional constraint x1 – 2x2 ≥ 5 is equivalent to x1 – 2x2 – x3 = 5
where x3 ≥ 0.
The variable, x3 , is called a surplus variable.
Transforming Any LP Model into the Standard Form
(4) Deleting the nonnegativity constraints for some decision variables
Example 1
Original Model
Standard Form
Example 2
Original Model
(1) Set Z΄ = – Z .
Then the minimization of
Z becomes the
maximization of Z΄.
(2) Add a slack variable x6 to
the left-hand side of the first
functional constraints.
Standard Form
(3) Subtract a surplus variable
x7 from the left-hand side of
the second functional
constraints.
(4) Substitute x4 – x5 for x3
where x4 and x5 are
nonnegative variables.
1. Solving Linear Programming Problems: The Simplex Method
(1) The Essence of the Simplex Method
Geometric Concepts of Simplex Method
Constraint boundary : a line that
forms the boundary of the feasible
region.
Corner-point solutions: the points
of intersection.
The 8 points A, B, C, D, E, F, G,
and H are corner-point solutions.
The five points A, B, C, D and E are
the corner-point feasible solutions
(CPF solutions).
The points F, G and H are called
corner-point infeasible solutions.
H
B
C
G
D
A
E
F
Fig.4.1 Contraint boundaries and corner-point
solutions for the Wyndor Glass Co. Problem
Geometric Concepts of Simplex Method
In this example, each corner-point
solution lies at the intersection of
two constraint boundaries. For a
linear programming problem with n
decision variables, each of its
corner-point solutions lies at the
intersection of n constraint
boundaries.
Fig.4.1 Contraint boundaries and corner-point
solutions for the Wyndor Glass Co. Problem
Geometric Concepts of Simplex Method
Adjacent CPF Soluionts
For a two-variable problem, a constraint boundary = a line.
For a three-variable problem, a constraint boundary = a plane.
For an n-variable problem, a constraint boundary = a hyperplane
C
D
B
C
A
D
E
F
G
Optimality test
Z=36 at point C (2,6)
Z=27 at point D (4, 3)
Z=30 at point B (0, 6)
B
C
D
Solving the example
Z=0 at point A
B
C
Z=30 at point B
Z=36 at point C
A
D
Z=27 at point D
E
Z=12 at point E
The Key Solution Concepts
The Key Solution Concepts
The Key Solution Concepts
B
C
D
A
E
The Key Solution Concepts
B
A
C
D
E
(2) Setting Up the Simplex Method
Original Form of the Model
Augmented Form of the Model
Augmented Form of the Model
H
H
B
B
C
C
G
G
A
A
D
D
H(3,2)
H(3,2)
E
E
F
F
For example, H(3,2) is a solution for the original model, which yields the
augmented solution ( x1, x2, x3, x4, x5) = (3, 2 ,1 ,8, 5)
For example, G(4,6) is a corner-point infeasible solution, which yields the
corresponding basic solution ( x1, x2, x3, x4, x5) = (4, 5 ,0 ,0, -6)
The only difference between basic solutions and corner-point solutions is
whether the values of the slack variables are included
Relationship between Corner-Point Solutions and Basic Solutions
In the original model, we have
In the augmented model, we have
Corner-point solution
Basic solution
Corner-point feasible (CPF) solution
Basic Feasible (BF) solution
The corner-point solution (0,0) in
the original model corresponds to
the basic solution (0, 0, 4,12, 18) in
the augmented form, where x1 =0
and x2=0 are the nonbasic variables,
and x3=4, x4=12, and x5=18 are the
basic variables
H
B C G
D
A
E
F
Example:
The CPF solution (0,0) in the original model corresponds to the BF solution (0, 0,
4,12, 18) in the augmented form, where x1 =0 and x2=0 are the nonbasic variables,
and x3=4, x4=12, and x5=18 are the basic variables
Choose x1 and x4 to be the nonbasic variables that are set equal to 0. The three
equations then yield, respectively, x3=4, x2=6 , and x5=6 as the solution for the
three basic variables as shown below.
Example:
A(0,0) and B(0,6) are two CPF solutions
The corresponding BF solutions are
( x1, x2, x3, x4, x5) = (0, 0 ,4 ,12, 18) and
( x1, x2, x3, x4, x5) = (0, 6 ,4 ,0, 6)
A(0,0) and C(2,6) are two CPF solutions
The corresponding BF solutions are
( x1, x2, x3, x4, x5) = (0, 0 ,4 ,12, 18) and
( x1, x2, x3, x4, x5) = (2, 6 ,2 ,0, 0)
H
B
C
G
D
A
H(3,2)
E
F
The Algebra of the Simplex Method
Use the Wyndor Glass Co. Model to illustrate the algebraic
procedure
Initialization
Geometric interpretation
B
A
C
D
E
Algebraic interpretation
Optimality Test
Geometric interpretation
A(0,0) is not optimal.
Algebraic interpretation
The objective function:
The rate of improvement of Z
by the nonbasic variable x1 is 3
B
A
The rate of improvement of Z by
the nonbasic variable x2 is 5
C
D
E
Conclusion: The initial BF solution
(0,0,4,12,18) is not optimal.
Iteration1 Step1: Determining the Direction of Movement
Geometric interpretation
Move up from A(0,0)
to B(0,6)
B
A
C
D
E
Algebraic interpretation
Iteration1 Step2: Where to Stop
Geometric interpretation
Algebraic interpretation
Stop at B. Otherwise, it
will leave the feasible
region.
Step 2 determine how far
to increase the entering
basic variable x2.
B
A
C
D
E
Thus x4 is the leaving basic variable for iteration 1 of the example.
Iteration1 Step3: Solving for the New BF Solution
Geometric interpretation
The intersection of the
new pair of constraint
boundary: B(0,6)
Algebraic interpretation
Nonbasic variables
Basic variables
B
C
Nonbasic variables
A
D
E
Basic variables
(0)
Initial BF Solution
Nonbasic variables: x1= 0
(1)
x2= 0
(2)
Basic variables: x3= 4
x4 =12
(3)
x5= 18
(0)
New BF Solution
Nonbasic variables: x1= 0
(1)
x4= 0
(2)
Basic variables: x3= ？
(3)
x2 =6
Basic variables: x3= 4
x2 =6
x5= 6
x5= ？
Optimality Test
Geometric interpretation
B(0,6) is not optimal,
because moving from
B to C increases Z.
B
A
Algebraic interpretation
The objective function:
The rate of improvement of Z
by the nonbasic varialle x1 is 3
The rate of improvement of Z by
the nonbasic varialle x4 is -5/2
C
D
E
Conclusion: The BF solution
(0,6,4,0,6) is not optimal.
Iteration2
Step1: Determining the Direction of Movement
Choose x1 to be the entering basic variable
Step2: Where to Stop
The minimum ratio test
indicates that x5 is the
leaving basic variable
Step3: Solving for the New BF Solution
(0)
(1)
New BF Solution
(2)
Nonbasic variables: x1= 0, x4= 0
(3)
Basic variables: x3= 2, x2 =6, x1= 2
Optimality Test
The objective function:
The coefficients of the nonbasic variables x4 and x5 are negative.
Increasing either x4 or x5 will decrease Z, so (x1, x2, x3, x4, x5) =
(2, 6, 2, 0, 0) must be optimal with Z = 36.
B
A
C
D
E
In terms of the original form of the
problem (no slack variables), the
optimal solution is (x1, x2) = (2, 6) ,
which yields Z = 3x1+5x2=36.