Let G = (N, A) be a graph where N is the set of nodes and A is the set of arcs. We represent with (i, j) the arc that joins i to j. Assume that for any pair of nodes there is at most one are joining them. Consider the following logistics problem involving shipments of a certain product: Max. (ij)eA bij ij + (i) Xik - -(i) *ki = di, i V, s.t. 0xij Cij, (i, j) A, where: Tij is the amount of product that is sent from node i to node j. bij is the profit of sending one unit of product through arc (i, j). di is the offer (if positive) or demand (if negative) of node i, an integer value. Cij is the maximum amount of product that can circulate through arc (i, j), a nonnegative integer value. N+(i) = {kEN / (i, k) = A}. N-(i) = {kEN / (k, i) A}. ZieN di = 0. viEN Prove that this formulation has an integer optimal solution , that is, ij Z+ V(i, j) A.