# Transportation problem
#
# Ships goods from plants to markets at least cost. With integer supplies
# and demands the constraint matrix is totally unimodular, so the LP optimum
# is already integral — the classic demonstration that not every
# whole-number answer needs integer variables.
#
# Technique: Supply rows, demand rows and continuous shipment quantities on
# every origin-destination pair.
#
# On this instance the optimum is 19 (minimisation), confirmed
# independently by two phase simplex before publication.
#
# Reference: Hitchcock, F. L. (1941). The distribution of a product from
# several sources to numerous localities. Journal of Mathematics and Physics
# 20(1–4), 224–230. doi:10.1002/sapm1941201224
model m
set S = {1, 2}
set D = {1, 2}
const c = {{2, 4},
{5, 1}}, forall i in S, forall j in D
const s = {9, 9}, forall i in S
const d = {6, 7}, forall j in D
var 0 <= x <= infty, forall i in S, forall j in D
min sum_{i in S}{sum_{j in D}{c_{i,j} * x_{i,j}}}
constr sum_{j in D}{x_{i,j}} <= s_{i}, forall i in S
constr sum_{i in S}{x_{i,j}} >= d_{j}, forall j in D
end
import elytica
Read this through MCP: read with path: "formulations/transportation", or resource hlpl://formulations/transportation.