Consider the problem:
$$ \left.\begin{array}{rrcl} \max & z = 5x_1 + 4.5x_2 + 6x_3\\ \text {s.t.:} & & & \\ & 6x_1 +5x_2 +8x_3 \leq 60\\ & 10x_1 +20x_2 +10x_3 \leq 150 \\ & x_1 \leq 8\\ & x_1,x_2,x_3 \geq 0 \end{array}\right\} $$
In [3]:
using JuMP
m = Model()
# Define variable
@variable(m, x[1:3] >= 0)
@constraints m begin
6x[1] + 5x[2] + 8x[3] <= 60
10x[1] + 20x[2] + 10x[3] <= 150
x[1] <= 8
end
@objective(m, Max, 5x[1] + 4.5x[2] + 6x[3])
print(m)
In [5]:
solve(m)
println("Optimal Profit: ", getobjectivevalue(m))
println("Optimal Solution: ", getvalue(x))
In [6]:
writeLP(m, "problem4.lp")
In [1]:
!less problem4.lp
In [2]:
!glpsol --cpxlp problem4.lp --ranges problem4.sen
In [3]:
!less problem4.sen
Suppose that the first two constraints are changed from linear inequalities into equality constraints. What is the change in the optimal solution value? Try figuring out the correct answer first. You may solve the LP again to verify whether your initial answer was correct.
Answer: Both the constraint are used to find the optimal solution. So neither the optimal solution nor the value will change if we chage inequalties to equality constraints.
Suppose that the first constraint of the original problem is multiplied by two. That is, we modify the first constraint so that it is $12x_1+10x_2+16x_3≤120$. Which of the following statements is correct? (Try to determine the correct answer first via direct reasoning. Subsequently, you can solve the problem again and generate a new sensitivity report).
Answer: The optimal solution and value will not change but the shadow price shoud change by a factor of 1/2.
Let $P$ denote the model from PART B in which we have changed the first two constraints into equality constraints. Let $Q$ denote the model in which we change the second constraint, but keep all other variables and constraints unchanged. In $Q$, we replace the constraint: $10x_1+20x_2+10x_3=150$ by the constraint $16x_1+25x_2+18x_3=210$. That is, we replace the second constraint from P by the sum of the first two constraints. Problem $Q$ is equivalent to Problem $P$ in the sense that it has the same optimal solution and the same optimal objective value. However, you will find that the shadow prices for $P$ and $Q$ are different. Let $p_1,p_2,p_3$ denote the shadow prices for Problem $P$. Let $q_1,q_2,q_3$ be the shadow prices Problem $Q$. Which of the following answers is correct? You may solve Problem Q and generate the sensitivity report to determine your answer. The correct answer will likely be surprising. See if you can reason through why it is correct.
In [3]:
using JuMP
P = Model()
# Define variable
@variable(P, x[1:3] >= 0)
@constraints P begin
6x[1] + 5x[2] + 8x[3] == 60
10x[1] + 20x[2] + 10x[3] == 150
x[1] <= 8
end
@objective(P, Max, 5x[1] + 4.5x[2] + 6x[3])
writeLP(P, "problem4-p.lp")
print(P)
In [4]:
using JuMP
Q = Model()
# Define variable
@variable(Q, x[1:3] >= 0)
@constraints Q begin
6x[1] + 5x[2] + 8x[3] == 60
16x[1] + 25x[2] + 18x[3] == 210
x[1] <= 8
end
@objective(Q, Max, 5x[1] + 4.5x[2] + 6x[3])
writeLP(Q, "problem4-q.lp")
print(Q)
In [1]:
!glpsol --cpxlp problem4-p.lp --ranges problem4-p.sen
In [2]:
!glpsol --cpxlp problem4-q.lp --ranges problem4-q.sen
In [3]:
!less problem4-p.sen
In [4]:
!less problem4-q.sen
$p_1 = .78571$ and $p_2 = .02857$ Also, $q_1 = .75714$ and $q_2 = .02857$
EXPLANATION
$q_1=p_1−p_2;q_2=p_2;q_3=p_3.$
Here is one way of figuring it out. Suppose that we consider $p_1$. This is the increase in the optimal objective value of $P$ if we increase the RHS of the first constraint from 60 to 61 and leave all other data unchanged. If we were to make this change in $P$, to get an equivalent change in $Q$, we need to change the RHS of the first constraint of $Q$ to 61, AND we would need to change the RHS of the second constraint of $Q$ to 211. Thus $p_1=q_1+q_2$.
Now consider $p_2$. This is the increase in the optimal objective value of $P$ if we increase the RHS of the second constraint from 150 to 151 and leave all other data unchanged. If we were to make this change in problem $P$, to get an equivalent change in $Q$, we would need to change the RHS of the second constraint of $Q$ to 211. Thus $p_2=q_2$. We now substitute $p_2$ for $q_2$ in the equality $p_1=q_1+q_2$, and obtain $q_1=p_1−p_2$.
In [ ]: