This notebook shows how to solve the PT-COMPANY example from Section 8.1 of Hillier and Lieberman:

Three Canneries $C_1,\ldots,C_3$ produce $s_1,\ldots,s_3$ units of canned peas which are to be distributed to warehouses $W_1,\ldots,W_4$ with demand $d_1,\ldots,d_4$ at unit cost of transportation $c_{ij}$ where $i=1,\ldots,3$ and $j=1,\ldots,4$.

The task is to minimize the total cost of transportation.

To implement the transportation problem in Pyomo, we start as usual, setting up the environment and defining the data (numbers as in Hillier and Lieberman).

In [1]:
from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk")
In [2]:
C = [1, 2, 3]
W = [1, 2, 3, 4]
d = {1:80, 2:65, 3:70, 4:85}
s = {1:75, 2:125, 3:100}
c = {(1,1):464, (1,2):513, (1,3):654, (1,4):867,
     (2,1):352, (2,2):416, (2,3):690, (2,4):791,
     (3,1):995, (3,2):682, (3,3):388, (3,4):685}

model = ConcreteModel()

For the transportation problem, our decision variable is $x_{ij}$, the number of units shipped from cannery $C_i$ to warehouse $W_j$. In Pyomo, we can add any number of indices to the decision variables:

In [3]:
model.x = Var(C, W, within=NonNegativeReals)

Now we define the objective function as usual; summation over both indices is implemented in a natural fashion.

In [4]:
model.z = Objective(expr = sum(c[i,j]*model.x[i,j] for i in C for j in W), sense=minimize)

For the supply and demand constraints, we use rules.

In [5]:
def supply_rule (model, i):
    return sum(model.x[i,j] for j in W) <= s[i]

model.supply = Constraint(C, rule=supply_rule)

def demand_rule (model, j):
    return sum(model.x[i,j] for i in C) >= d[j]

model.demand = Constraint(W, rule=demand_rule)

Now we request getting dual outputs, solve, and look at the solution. First, the $x_{ij}$:

In [6]:
model.dual = Suffix(direction=Suffix.IMPORT)
results = opt.solve(model)
model.x.get_values()
Out[6]:
{(1, 1): 0.0,
 (1, 2): 20.0,
 (1, 3): 0.0,
 (1, 4): 55.0,
 (2, 1): 80.0,
 (2, 2): 45.0,
 (2, 3): 0.0,
 (2, 4): 0.0,
 (3, 1): 0.0,
 (3, 2): 0.0,
 (3, 3): 70.0,
 (3, 4): 30.0}

Then, the total cost of transportation:

In [7]:
model.z.expr()
Out[7]:
152535.0

In the following, we access the model duals, or shadow prices. First the demand duals. The $j$th dual indicates the marginal increase in total cost if the demand at warehouse $W_j$ is increased by one unit.

In [8]:
for j in W:
    print(j, model.dual[model.demand[j]])

1 449.0
2 513.0
3 570.0
4 867.0

Now the supply duals. The $i$th dual indicates the marginal increase of total cost when the supply at cannary $C_i$ is increased by one unit.

In [9]:
for i in C:
    print(i, model.dual[model.supply[i]])

1 0.0
2 -96.9999999999999
3 -182.0

Note that the supply duals are negative, as an increase in supply in those canneries where the supply constraint is binding will result in a decrease of total cost. In the usual dual formulation of the transportation problem, which is equivalent, the dual variables are taken as positive and the negative sign is written explicitly into the dual objective function.