Interpretation of Reduced Costs

Question

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

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)?

Answer 1

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).