LP Modeling

Programming here means Planning
Dennis Bricker Wuhan University of Technology & University of Iowa
LP Modeling
9/11/2004
page 1 of 18
linear function
f ( x1 , x2 , xn ) = c0 + ci xi
i =1
= c0 + c1 x1 + c2 x2 +
examples
+ cn xn
2 x 1 +5 x2 + x3 + 1 x1 3 x3
linear inequality
a x
i =1
i i
( or )
examples
x1 2 x2 5 2 x1 + x2 x3 10
LP Modeling
9/11/2004
page 2 of 18
In two dimensions, the graph of a linear equation is a line, and the graph of a linear inequality is a half-space (including the line).
To draw the graph of a linear inequality, first draw the graph of the equation, and then decide which side is the correct half-space by testing whether (0,0) is feasible.
In three dimensions, the graph of a linear equation is a plane. In n dimensions, the graph of a linear equation is a hyperplane.
LP Modeling
9/11/2004
page 3 of 18
Exercise
Graph the linear inequality:

X1 X 2 2
(Shade the region representing points which are feasible in both inequalities.)
LP Modeling
9/11/2004
page 4 of 18
(exercise, continued)
Graph the solutions of the pair of linear inequalities:
X1 X 2 2 X1 + 3 X 2 6 (Shade the region representing points which are feasible in both inequalities.)
LP Modeling
9/11/2004
page 5 of 18
linear programming (LP): an optimization problem for which we maximize or minimize a linear function of the decision variables (this function is called the objective function) the values of the decision variables must satisfy a set of constraints, each
consisting of a linear equation or linear inequality

a sign restriction, i.e., usually nonnegativity ( xi 0 ) but perhaps nonpositivity
( xi 0 ) , may be associated with each decision variable.

example:
maximize 2x1 + x2 subject to 3 x1 x2 6 2 x1 + 3 x2 12 x1 0, x2 0
LP Modeling
9/11/2004
page 6 of 18
maximize 2x1 + x2 subject to 3 x1 x2 6 2 x1 + 3 x2 12 x1 0, x2 0
Each point in the shaded feasible region satisfies all four inequality constraints (including nonnegativity) and represents a possible solution of the problem. The optimal solution is the feasible solution for which the objective function is largest.
LP Modeling
9/11/2004
page 7 of 18
By graphing the linear equations
2 X 1 + X 2 = 0 , 2 X 1 + X 2 = 4 , 2 X 1 + X 2 = 12 , etc., we see that the slope remains the same, but the line is shifted to the right.
How far to the right can the line be shifted while still including a feasible solution of the set of inequalities? The optimal solution is the corner farthest to the right, ( X 1 , X 2 ) = ( 6,0 ) . In fact, an optimal solution of an LP problem can always be found at a corner point!
LP Modeling
9/11/2004
page 8 of 18
Example: A manufacturer can make two products: P and Q. Each product requires processing time on each of four machines: A, B, C, and D. Each machine is available 24 hours per day = 1440 minutes per day. The profit per unit of products P and Q are $45 and $60, respectively. Maximum demand for products P and Q are 100/day and 40/day, respectively.
Machine \Product: A B C D Profit/unit
Unit Processing Time (minutes) P Q 20 10 12 28 15 6 10 15 45 60
Available (min.) 1440 1440 1440 1440
How much of each product should be manufactured each day in order to maximize profits?
LP Modeling
9/11/2004
page 9 of 18
Define the decision variables P = number of units/day of product P Q = number of units/day of product Q Objective: Maximize 45 P + 60Q ($/day) Constraints: do not exceed the available processing time on each machine: 20 P + 10Q 1440 12 P + 28Q 1440
15 P + 6Q 1440 10 P + 15Q 1440 do not produce more than the demand for the products: P 100 Q 40 a negative quantity of product is meaningless: P 0, Q 0
LP Modeling
9/11/2004
page 10 of 18
The maximum profit is obtained at the corner point ( P, Q ) = ( 58.9, 26.2 )

Note: I clearly erred in drawing the isoquant line for the profit!
LP Modeling
9/11/2004
page 11 of 18
The graphical method for solving an LP problem is useless for problems with more than 2 (possibly 3) decision variables
Problems occurring in the real world may involve a million decision variables and thousands of constraints!
We will study computational methods for solving linear programming problems.
LP Modeling
9/11/2004
page 12 of 18
LINGO is a software package for solving LP problems.
(by default, variables are assumed to be nonnegative.)
LP Modeling
9/11/2004
page 13 of 18
SOLUTION:
Global optimal solution found at step: Objective value:
2 4221.818
Variable P Q Row 1 2 3 4 5 6 7
Value 58.90909 26.18182 Slack or Surplus 4221.818 0.0000000 0.0000000 399.2727 458.1818 41.09091 13.81818
Reduced Cost 0.0000000 0.0000000 Dual Price 1.000000 1.227273 1.704545 0.0000000 0.0000000 0.0000000 0.0000000
LP Modeling
9/11/2004
page 14 of 18
That is, the manufacturer will maximize profits by producing 58.9 units of P and 26.18 units of Q each day (assuming fractional units are possible). This plan will yield a profit of $4221.818/day.
Row 1 2 3 4 5 6 7
Slack or Surplus 4221.818 0.0000000 0.0000000 399.2727 458.1818 41.09091 13.81818
Dual Price 1.000000 1.227273 1.704545 0.0000000 0.0000000 0.0000000 0.0000000
This plan will use all of the available time on machines A and B, i.e.,
S A = SB = 0 but unused time on machines C & D will be 399.27 and 458.18, respectively,
LP Modeling
9/11/2004
page 15 of 18
that is, SC = 399.2727 and S D = 458.1818 .
LP Modeling
9/11/2004
page 16 of 18
Computational Methods for Solving LPs It is more convenient to work with linear equations rather than linear inequalities. Define slack variables S A , S B , SC & S D to be the unused processing time on machines A, B, C & D, respectively. Then, for example, the inequality constraint for machine A is equivalent to the linear equation and nonnegativity restriction: 20 P + 10Q 1440 20 P + 10Q + S A = 1440 & S A 0
LP Modeling
9/11/2004
page 17 of 18
Thus we obtain the system of equations (& simple bounds on the variables):
20 P + 10Q 1440 12 P + 28Q 1440 15 P + 6Q 1440 10 P + 15Q 1440
= 1440 20 P + 10Q + S A 12 P + 28Q + SB = 1440 + SC = 1440 15 P + 6Q + S D = 1440 10 P + 15Q 0 P 100, 0 Q 40, S A 0, S B 0, SC 0, S D 0
Next we will review computational methods for solving systems of linear equations!
LP Modeling
9/11/2004
page 18 of 18

LP Modeling

Uploaded by

Copyright:

Available Formats

LP Modeling

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

LP Modeling

Uploaded by

Copyright:

Available Formats

Programming here means Planning

Dennis Bricker Wuhan University of Technology & University of Iowa

Graph the linear inequality:

Graph the solutions of the pair of linear inequalities:

consisting of a linear equation or linear inequality

( xi 0 ) , may be associated with each decision variable.

maximize 2x1 + x2 subject to 3 x1 x2 6 2 x1 + 3 x2 12 x1 0, x2 0

maximize 2x1 + x2 subject to 3 x1 x2 6 2 x1 + 3 x2 12 x1 0, x2 0

By graphing the linear equations

Machine \Product: A B C D Profit/unit

Unit Processing Time (minutes) P Q 20 10 12 28 15 6 10 15 45 60

Available (min.) 1440 1440 1440 1440

The maximum profit is obtained at the corner point ( P, Q ) = ( 58.9, 26.2 )

We will study computational methods for solving linear programming problems.

LINGO is a software package for solving LP problems.

(by default, variables are assumed to be nonnegative.)

Global optimal solution found at step: Objective value:

Slack or Surplus 4221.818 0.0000000 0.0000000 399.2727 458.1818 41.09091 13.81818

Dual Price 1.000000 1.227273 1.704545 0.0000000 0.0000000 0.0000000 0.0000000

that is, SC = 399.2727 and S D = 458.1818 .

20 P + 10Q 1440 12 P + 28Q 1440 15 P + 6Q 1440 10 P + 15Q 1440

= 1440 20 P + 10Q + S A 12 P + 28Q + SB = 1440 + SC = 1440 15 P + 6Q + S D = 1440 10 P + 15Q 0 P 100, 0 Q 40, S A 0, S B 0, SC 0, S D 0

You might also like