= Solution
The assignment equalities parameterize every feasible <matrix> of the <linear programming relaxation> as
$$
x(t)=\begin{pmatrix}t&1-t\\1-t&t\end{pmatrix},\qquad0\leq t\leq1.
$$
The side totals and objective become
$$
a\cdot x=3+t,\qquad b\cdot x=6-t,\qquad c\cdot x=8+2t.
$$
The first side constraint gives $t\leq1/2$ and the second gives $t\geq1/2$, so the relaxation has the unique <feasible point>
$$
\boxed{x_{ij}=1/2\quad\text{for all }i,j,\qquad z_{LP}=9.}
$$
Direct elimination of the assignment equalities has solved this one-dimensional <linear program>. Its value matches the <Lagrangian dual problem> value because the retained assignment polytope is the <convex hull> of the two <integer> assignments; it does not make the side-constrained <integer> problem feasible.
Back to article page
