In the minimum-cost multicommodity-flow problem, we are given adirected graph G = (V,E), in which each edge (u, v) ∈ E has a nonnegativecapacity c(u, v) ≥ 0 and a cost (u, v). As in the multicommodity-flow problem,we are given k different commodities, K1, K2, . . . , Kk, where commodity i isspecified by the triple Ki = (si, ti, di). Here si is the source of commodity i, ti isthe sink of commodity i, and di is the demand, which is the desired flow value forcommodity i from si to ti. We define a flow for commodity i, denoted by fi, (sothat fi(u, v) is the flow of commodity i from vertex u to vertex v) to be a real-valued function that satisfies the flow-conservation, skew-symmetry, and capacityconstraints. We now define f(u, v) , the aggregate flow, to be sum of the variouscommodity flows, so that f(u, v) = Σki=1 fi(u, v). The aggregate flow on edge (u, v)must be no more than the capacity of edge (u, v).The cost of a flow is Σu,v∈V f(u, v), and the goal is to find the feasible flow ofminimum cost. Express this problem as a linear program.