The following is a textual specification of the linear programming problem that was just solved using the graphical method.
// File: cbars-01.rlp
// Title: Chocolate bar problem
// Author: Robin Snyder
// Created: 1997/11/22 08:03
// Updated: 1997/11/22 08:03
title "Chocolate bars"
author "Robin Snyder"
source "Robin Snyder"
linear program
var
x1 "Galaxy bars (lots)"
x2 "Continental bars (lots)"
max
2 x1 + 3 x2 "profit ($)"
st
3 x1 + 1 x2 <= 18 "milk (tons)"
1 x1 + 2 x2 <= 12 "cocoa (tons)"
3 x1 + 3 x2 <= 21 "sugar (tons)"
end
After being run, the output is as follows.
LPSolves (v0.1, 08-13-97)
Copyright (c) 1996 by Robin Snyder
File: F:\RLP\cbars-01.rlp
Time: 1997/11/22 at 09:37
Title: "Chocolate bars"
Author: "Robin Snyder"
Source: "Robin Snyder"
Variables:
1. x1 "Galaxy bars (lots)"
2. x2 "Continental bars (lots)"
Problem:
Maximize 2 x1 + 3 x2 "profit ($)"
Such that
3 x1 + x2 <= 18 "milk (tons)"
x1 + 2 x2 <= 12 "cocoa (tons)"
3 x1 + 3 x2 <= 21 "sugar (tons)"
End
Phase 1:
A basic feasible solution has been found.
Phase 2:
R E S U L T S : (* = basis variable)
-------------
Objective coefficient ranges: (solution unchanged)
Coefficient Lower Current Upper
of variable limit value limit
----------- ----- ------- -----
*x1 1.5 2 3 Galaxy bars (lots)
*x2 2 3 4 Continental bars (lots)
Solution (variable) results:
Reduced
Variable Value cost
-------- ----- -------
*x1 2 0 Galaxy bars (lots)
*x2 5 0 Continental bars (lots)
Shadow
Variable Value price
---------- ----- ------
*$3 7 0 Slack (milk (tons))
$4 0 -1 Slack (cocoa (tons))
$5 0 -0.333 Slack (sugar (tons))
Right hand side ranges: (solution unchanged)
Right side Lower Current Upper
constraint limit value limit
----------- ----- ------ -----
*1. 11 18 none milk (tons)
2. 8.5 12 14 cocoa (tons)
3. 18 21 25.2 sugar (tons)
Objective (overall) result:
Objective Value
--------- -----
z 19 profit ($)
Note that the optimum value of the objective function is the same as determined by the graphical method.
A
sensitivity analysis attempts to determine what effect a change in the parameters of the problem (the input) will have on the solution (the output) without solving the problem (e.g., running the corresponding program) again. Since the analysis is done after a solution to a given problem is determined, sensitivity analysis is often called
post-optimality analysis.
Some relevant questions involving LP sensitivity analysis are the following.
How will a change in the coefficient of the objective function affect the optimal solution?
How will a change in the RHS (Right Hand Side) value for a constraint affect the optimal solution?
Some relevant cost and price concepts are the following.
A sunk cost is a cost that is already committed and cannot be recovered. Since this cost is already incurred, the cost can, for the purposes of decision making, be considered free.
A relevant cost is a cost that has not yet been spent. That is, a decision needs to be made. Once spent, the cost becomes a sunk cost.
The shadow price is the change in the value of the optimal solution per unit increase in the value of the right-hand side associated with a constraint.
The dual price is the same as the shadow price for a maximization problem, negative of shadow price for a minimization problem.
Consider the following problem.
You have
100 minutes to take an exam. There are
10 questions worth
20 points each. You know that one question is particularly difficult for you to solve. It will take you
60 minutes to solve it completely. You estimate that all of the other questions taken together will take about
10 minutes each, or
90 minutes to solve them completely. You wish to maximize your score subject to the above constraints. Formulate this problem as a linear programming problem.
The entire problem hinges on a proper identification and definition of the variables involved. The following is an LP formulation of this problem.
// File: exam.rlp
// Title: Exam problem
// Author: Robin Snyder
// Created: 1997/11/22 09:39
// Updated: 1997/11/22 09:39
title "Exam time allocation problem"
author "Robin Snyder"
source "Robin Snyder"
linear program
var
x1 "fraction of 9 questions answered"
x2 "fraction of other question answered"
max
180 x1 + 20 x2 "total score"
st
90 x1 + 60 x2 <= 100 "overall time constraint"
x1 <= 1 "constraint of 9 questions"
x2 <= 1 "constraint of other question"
end
A solution to this problem is as follows.
LPSolves (v0.1, 08-13-97)
Copyright (c) 1996 by Robin Snyder
File: F:\RLP1\exam.rlp
Time: 1997/11/22 at 09:39
Title: "Exam time allocation problem"
Author: "Robin Snyder"
Source: "Robin Snyder"
Variables:
1. x1 "fraction of 9 questions answered"
2. x2 "fraction of other question answered"
Problem:
Maximize 180 x1 + 20 x2 "total score"
Such that
90 x1 + 60 x2 <= 100 "overall time constraint"
x1 <= 1 "constraint of 9 questions"
x2 <= 1 "constraint of other question"
End
Phase 1:
A basic feasible solution has been found.
Phase 2:
R E S U L T S : (* = basis variable)
-------------
Objective coefficient ranges: (solution unchanged)
Coefficient Lower Current Upper
of variable limit value limit
----------- ----- ------- -----
*x1 30 180 none fraction of 9 questions answered
*x2 0 20 120 fraction of other question answered
Solution (variable) results:
Reduced
Variable Value cost
-------- ----- -------
*x1 1 0 fraction of 9 questions answered
*x2 0.167 0 fraction of other question answered
Shadow
Variable Value price
---------- ----- ------
$3 0 -0.333 Slack (overall time constraint)
$4 0 -150 Slack (constraint of 9 questions)
*$5 0.833 0 Slack (constraint of other question)
Right hand side ranges: (solution unchanged)
Right side Lower Current Upper
constraint limit value limit
----------- ----- ------ -----
1. 90 100 150 overall time constraint
2. 0.444 1 1.111 constraint of 9 questions
*3. 0.167 1 none constraint of other question
Objective (overall) result:
Objective Value
--------- -----
z 183.333 total score
The 2-phase method is used. Phase 1 attempts to minimize a modified objective function (
z) to get a starting feasible solution (
z = 0 when minimized). Phase 2 uses the original objective function. At each step during these phases, a variable will enter the basis and another variable will leave the basis, such that the objective function is improved. Notice the change to the
z value in each step of each phase.
The sensitivity analysis for the right hand side indicates that the solution would not change until one (and only one) of the following were done.
The time were lowered to 90 minutes or raised to 150 minutes.
The fraction of time spent on the easy questions were reduced to 0.444 or raised to 1.111. This does not have a easily recognized physical interpretation.
The fraction of time spent on the hard question were reduced to 0.167 or raised to 1.0. Again, this does not have a easily recognized physical interpretation.
The sensitivity analysis for the coefficients indicates that the solution would not change until (pick one of these):
The value of the easy questions were reduced from 180 to 30.
The value of the hard question were raised from 20 to 120.
The solution for
x1 is
1.00, indicating that 100.0% of the time should be spent on the easy questions. The solution for
x2 is
0.167, indicating that 16.7%, or the remainder, of the time should be spent on the hard problem.
The maximum score for this problem, as stated, is
183 points (rounded).
1. What is sensitivity analysis and why is it important?
2. What is another name for sensitivity analysis?
3. What happens when a coefficient ci of the objective function z = c1 x1 + c2 x2 + ..., is changed? Be specific.
4. What happens when a right side coefficient bi of a constraint ai,1 x1 + ai,2 x2 + ... <= bi is changed? Be specific.
