Formulate a linear programming problem to solve the transportation problem. You are given as input:

Graph with vertices $$

and edges $$

$.$ Each undirected edge $(,)$

can be regarded as two edges $(,)$

and $(,)$

in opposite directions, if it is easier for your solution.

A cost $$:$$

associated with each edge such that $()>=0$

and is the cost of transporting one unit of oil along the edge.

A map $$:$$

mapping each vertex $$

to net supply $()$

$.($note that if $()<=0$

then it is considered a demand$).$

We suggest following steps on pencil$/$paper to formulate the problem.

$($a$)$ identify all the decision variables,

$($b$)$ write down the constraints, and

$($c$)$ write down the objective function.

Complete the python function calculateOptimalPlan that takes inputs:

n: number of vertices which are numbered $0,...,1$

;

edge$\_$list: a list of undirected edges $(,,)$

between vertices wherein $>=0$

is the cost of flow along the edge;

supplies: a list of size $$

where supplies$[$j$]$ is the supply $($or demand if negative$)$ at the jth vertex.

Your function must return a dictionary that maps edges $($i$,$j$)$ to the flow along the edge in the direction $->$

$.$

All flows must be non$-$negative.

If you specify a flow from $$

to $$

$,$ then your dictionary must have the key $($j$,$i$)$ mapped to the non$-$negative flow from $$

to $$

$.$

If an edge is not present in the dictionary, we will take the flow along it to be zero.

from pulp import $*$

def calculateOptimalPlan$($n$,$ edge$\_$list, supplies, debug$=$False$)$:

assert n $>=1$

assert all$(0<=$ i $<$ n and $0<=$ j $<$ n and i $!=$ j and c $>=0$ for $($i$,$j$,$c$)$ in edge$\_$list$)$

assert len$($supplies$)==$ n

# TODO: Formulate the LP for optimal transportation plan and return the solution as a dictionary

# from edges $($i$,$j$)$ to flow from i to j$.$

# If an edge is not present in the dictionary, we will take its flow to be zero.

# your code here

The tests should pass:

def test$\_$solution$($n$,$ edge$\_$list, supplies, solution$\_$map, expected$\_$cost$)$:

cost $=0$

outflows $=[0]*$n

inflows $=[0]*$n

for $($i$,$j$,$c$)$ in edge$\_$list:

if $($i$,$j$)$ in solution$\_$map:

flow $=$ solution$\_$map$[($i$,$j$)]$

cost $+=$ c $*$ flow

assert flow $>=0,$ f'flow on edge $\{($i$,$j$)\}$ is negative $-->\{$flow$\}\text{'}$

outflows$[$i$]+=$ flow

inflows$[$j$]+=$ flow

elif $($j$,$i$)$ in solution$\_$map:

flow $=$ solution$\_$map$[($j$,$i$)]$

cost $+=$ c $*$ flow

assert flow $>=0,$ f'flow on edge $\{($j$,$i$)\}$ in negative $-->\{$flow$\}\text{'}$

outflows$[$j$]+=$ flow

inflows$[$i$]+=$ flow

for $($i$,$ s$)$ in enumerate$($supplies$)$:

if s $>0$:

assert outflows$[$i$]-$ inflows$[$i$]<=$ s$,$ f'Vertex $\{$i$\}$ constraint violated: total outflow $=\{$outflows$[$i$]\}$ inflow $=\{$inflows$[$i$]\},$ supply $=\{$s$\}\text{'}$

else:

assert abs$($inflows$[$i$]-$outflows$[$i$]+$ s$)<=1$E$-2,$f'Vertex$\{$i$\}$ constraint violated: inflow $=\{$inflows$[$i$]\}$ outflow$=\{$outflows$[$i$]\},$ demand $=\{-$s$\}\text{'}$

if expected$\_$cost $!=$ None:

assert abs$($expected$\_$cost $-$ cost$)<=1$E$-02,$ f'Expected cost: $\{$expected$\_$cost$\},$ your algorithm returned: $\{$cost$\}\text{'}$

print$(\text{'}$Test Passed!$\text{'})$

n $=5$

edge$\_$list $=[$

$(0,1,5),(0,3,3),(0,4,4),$

$(1,2,9),(1,4,6),$

$(2,3,8),$

$(3,4,7)$

$]$

supplies $=[-55,100,-25,35,-40]$

sol$\_$map $=$ calculateOptimalPlan$($n$,$ edge$\_$list, supplies, debug$=$True$)$

test$\_$solution$($n$,$ edge$\_$list, supplies, sol$\_$map,$670)$

n $=10$

edge$\_$list $=[$

$(0,1,5),$

$(0,2,4),$

$(0,3,7),$

$(0,4,3),$

$(0,5,9),$

$(0,8,6),$

$(0,9,5),$

$(1,2,3),$

$(2,4,9),$

$(2,7,8),$

$(2,8,7),$

$(2,6,5),$

$(3,4,6),$

$(3,5,7),$

$(3,6,4),$

$(3,7,8),$

$(3,8,3),$

$(3,9,5),$

$(4,8,5),$

$(5,7,8),$

$(6,8,2),$

$(7,8,3),$

$(7,9,6),$

$(8,9,10)$

$]$

supplies$=[$

$20,$

$30,$

$-30,$

$-40,$

$10,$

$15,$

$20,$

$-35,$

$40,$

$-30$

$]$

sol$\_$map $=$ calculateOptimalPlan$($n$,$ edge$\_$list, supplies, debug$=$True$)$

test$\_$solution$($n$,$ edge$\_$list, supplies, sol$\_$map,$575)$