5
$\begingroup$

I am looking for an answer to a question I can't quite get behind. (continuation of Linear Programming: Integer and non-integer decision variables)

I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\cdot q_t\tag1\\\text{s.t.}&\quad i_0=0\tag2\\&\quad i_{t-1}+q_t-i_t=d_t&\forall t\in T\tag3\\&\quad q_t\le c_t\cdot z_t&\forall t\in T\tag4\\&\quad \end{align}

Furthermore, the following table is given:

Period $t$ 1 2 3 4 5 6 7 8 9 10
demand $d_t$ 12 6 20 5 7 25 0 5 5 21
capacity $c_t$ 20 15 5 30 20 20 21 10 10 5
set-up costs $s_t$ 25 30 40 20 80 80 150 30 40 60
storage costs $h_t$ 6 5 4 5 6 9 9 6 5 4
production costs $p_t$ 5 3 7 2 1 10 15 2 1 5
production days $z_t$ 0 1 1 1 1 1 0 0 1 1

Decision variables are:

  • $q_t$: quantity in time $t$
  • $i_t$: inventory in time $t$

If I implement this problem in Excel and solve it with the Excel Solver I get an optimal solution and a sensitivity report which look like the following.

Period $t$ 1 2 3 4 5 6 7 8 9 10
quantity $d_t$ 18 15 5 23 20 0 0 10 10 5
inventory $c_t$ 6 15 0 18 31 6 6 11 16 0

![enter image description here

So far so good. However, what I don't understand are the reduced costs in this specific example. What is the practical interpretation of, for example, the reduced costs of 18 for 'Inventory Day 3'(marked in red in the sensitivity report)? And also, why have some variables which are not part of the solution (=non basis variable with value 0) reduced costs of 0 (also marked in red in the sensitivity report)?

$\endgroup$

1 Answer 1

5
$\begingroup$

The reduced costs (or marginal costs), tell you by how much the objective function will increase (or decrease), if the corresponding variable increases by one unit.

So if you are minimizing, the reduced costs of the variables of your optimal solution should all be non negative. Otherwise, increasing the value of the variable with negative reduced cost would decrease the objective function, contradicting the fact that the solution is optimal.

In your case, the reduced costs for 'Inventory Day 3' is $18$, and the corresponding value is $0$. This means that if the variable took value $1$, the objective function would increase by $18$ units.

Likewise for the variables with value $0$ and reduced cost $0$. You can make them "part of the solution" as you say, but it will have no impact on the objective function (it will increase by $0$ units).

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. That is exactly what I thought. However, when trying to set $i_3=1$ the objective function does not increase by $18$ but rather by $4$ which makes sense as $i_3$ has a factor of $4$ in the objective function. Likewise for the variables with $0$ as final value and $0$ as reduced costs. If I increase for example $q_6$ the objective function increases by $10$ as that is the factor of $q_6$ in the objective funktion. That is when I got confused and wondered if I understood something incorrectly. $\endgroup$
    – coar
    Nov 16, 2021 at 11:58
  • $\begingroup$ That's weird. But when you say you set $i_3=1$, which variable do you set to $0$ ? It will increase by $18$ only if it can (if it replaces the right variable). $\endgroup$
    – Kuifje
    Nov 16, 2021 at 12:22
  • 1
    $\begingroup$ @coar The interpretation of the reduced cost is the marginal rate at which the objective value changes if you force the specified variable to increase (or decrease) by 1 and then find the optimal adjustments to the remaining variables. Try setting a lower bound of 1 for day 3 inventory and then running Solver again on the modified problem, and see how much the optimal objective changes. $\endgroup$
    – prubin
    Nov 16, 2021 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.