Systems Optimization
Linear Programming
Systems Optimization
Linear Programming
If an LP has more than two decision variables, the
range of values for a rhs (or objective function
coefficient) for which the basis remains optimal cannot
be determined graphically.
These ranges can be computed by hand but this is often
tedious, so they are usually determined by a packaged
computer program. MPL and LINDO will be used and
the interpretation of its sensitivity analysis discussed.
Note: sometimes Excel provides erroneous results
Systems Optimization
Linear Programming
Dual or Shadow
prices are the
amount the
optimal z-value
improves if the
rhs of a
constraint is
increased by one
unit (assuming
no change in
basis).
Dual variables
c1 cost
Reduced
is the amount the
objective function
coefficient for
variable i would
have to be
increased for
there to be an
b2
alternative
optimal solution.
More later
Systems Optimization
Linear Programming
c1
Allowable ranges (w/o
changing basis) for
the x1 coefficient
(c1) is:
0 c1 7.5
b2
What about c2? And b1 and b3?
Allowable range (w/o
changing basis) for
the rhs (b2) of the
second constraint is:
6 b2 18
Lindo Sensitivity Analysis
Allowable ranges in
terms of increase and
decrease
(w/o changing basis)
for the x1 coefficient
(c1) is:
0 c1 7.5
Systems Optimization
Linear Programming
Consider the following maximization problem. Winco sells
four types of products. The resources needed to produce one
unit of each are:
Product Product Product Produc Availabl
1
2
3
t4
e
Raw
material
4600
Hours of
labor
5000
Sales price
$4
$6
$7
$8
To meet customer demand, exactly 950 total units must be
produced. Customers demand that at least 400 units of product 4
be produced. Formulate an LP to maximize profit.
Let xi = number of units of product i produced by Winco.
The Winco LP formulation:
max z = 4x1 + 6x2 +7x3 + 8x4
s.t.
x1 + x2 + x3 + x4 = 950
x4 400
2x1 + 3x2 + 4x3 + 7x4 4600
3x1 + 4x2 + 5x3 + 6x4 5000
x1,x2,x3,x4 0
LINDO output and
sensitivity
analysis
example(s).
Reduced cost
is the amount the
objective function
coefficient for
variable i would
have to be
increased for
there to be an
alternative
optimal solution.
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
X1
X2
X3
X4
ROW
2)
3)
4)
5)
NO. ITERATIONS=
VALUE
0.000000
400.000000
150.000000
400.000000
REDUCED COST
1.000000
0.000000
0.000000
0.000000
SLACK OR SURPLUS
0.000000
0.000000
0.000000
250.000000
DUAL PRICES
3.000000
-2.000000
1.000000
0.000000
RANGES IN WHICH THE BASIS IS UNCHANGED:
LINDO sensitivity
analysis example(s).
OBJ COEFFICIENT RANGES
VARIABLE
Allowable range (w/o
changing basis) for
the x2 coefficient
(c2) is:
5.50 c2 6.667
CURRENT
ALLOWABLE
ALLOWABLE
COEF
INCREASE
DECREASE
X1
4.000000
1.000000
INFINITY
X2
6.000000
0.666667
0.500000
X3
7.000000
1.000000
0.500000
X4
8.000000
2.000000
INFINITY
RIGHTHAND SIDE RANGES
Allowable range (w/o
changing basis) for
the rhs (b1) of the first
constraint is:
850 b1 1000
ROW
CURRENT
ALLOWABLE
ALLOWABLE
RHS
INCREASE
DECREASE
950.000000
50.000000
100.000000
400.000000
37.500000
125.000000
4600.000000
250.000000
150.000000
5000.000000
INFINITY
250.000000
Shadow prices
are shown in the
Dual Prices
section of
LINDO output.
Shadow prices
are the amount
the optimal zvalue improves if
the rhs of a
constraint is
increased by one
unit (assuming
no change in
basis).
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
X1
X2
X3
X4
ROW
2)
3)
4)
5)
NO. ITERATIONS=
VALUE
0.000000
400.000000
150.000000
400.000000
REDUCED COST
1.000000
0.000000
0.000000
0.000000
SLACK OR SURPLUS
0.000000
0.000000
0.000000
250.000000
DUAL PRICES
3.000000
-2.000000
1.000000
0.000000
Interpretation of shadow prices for the Winco LP
ROW
SLACK OR SURPLUS
DUAL PRICES
2)
0.000000
3.000000
(overall demand)
3)
0.000000
-2.000000
(product 4 demand)
4)
0.000000
1.000000
(raw material availability)
5)
250.000000
0.000000
(labor availability)
Assuming the allowable range of the rhs is not violated, shadow (Dual) prices
show: $3 for constraint 1 implies that each one-unit increase in total demand
will increase net sales by $3. The -$2 for constraint 2 implies that each unit
increase in the requirement for product 4 will decrease revenue by $2. The $1
shadow price for constraint 3 implies an additional unit of raw material (at no
cost) increases total revenue by $1. Finally, constraint 4 implies any additional
labor (at no cost) will not improve total revenue.
Shadow price signs
1. Constraints with symbols will always have
nonpositive shadow prices.
2. Constraints with will always have nonnegative
shadow prices.
3. Equality constraints may have a positive, a
negative, or a zero shadow price.
Managerial Use of Shadow Prices
The managerial
significance of shadow
prices is that they can
often be used to
determine the
maximum amount a
manager should be
willing to pay for an
additional unit of a
resource. Reconsider
the Winco to the right.
What is the most
Winco should be
willing to pay for
additional units of raw
material or labor?
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
raw
material
labor
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
COST
X1
X2
X3
X4
VALUE
ROW
2)
3)
4)
5)
NO. ITERATIONS=
REDUCED
0.000000
400.000000
150.000000
400.000000
1.000000
0.000000
0.000000
0.000000
SLACK OR SURPLUS
0.000000
0.000000
0.000000
250.000000
DUAL PRICES
3.000000
-2.000000
1.000000
0.000000
Managerial Use of Shadow Prices
The shadow price for raw
material constraint (row 4)
shows an extra unit of raw
material would increase
revenue $1. Winco could
pay up to $1 for an extra
unit of raw material and be
as well off as it is now.
Labor constraints (row 5)
shadow price is 0 meaning
that an extra hour of labor
will not increase revenue.
So, Winco should not be
willing to pay anything for
an extra hour of labor.
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
COST
X1
X2
X3
X4
VALUE
ROW
2)
3)
4)
5)
NO. ITERATIONS=
REDUCED
0.000000
400.000000
150.000000
400.000000
1.000000
0.000000
0.000000
0.000000
SLACK OR SURPLUS
0.000000
0.000000
0.000000
250.000000
DUAL PRICES
3.000000
-2.000000
1.000000
0.000000