Figure $1$: The graph for Question $3.$ Nodes on the left are supply nodes,

with the numbers inside indicating the supply. Nodes on the right are

demand nodes, with the numbers inside indicating the demand. Trans$-$

portation is only permitted ares and numbers on the arcs indicate

costs for transportation al Shat arc.

Figure $1$ illustrates a transportation problem with supply nodes

on the left, demand nodes on the right, and transportation costs

written on the arcs. The aim is to minimise costs.

$($a$)$ Number all supply nodes and all demand nodes. Then write

an equation that describes the total transportation cost in

terms all $x_{ij},$ where $x_{ij}$ is the quantity transported from sup$-$

ply node $i$ to demand node $j.$

$($b$)$ In terms of the $x_{ij}$ quantities, write all constraints for this

transportation problem that ensure all supplies and demands

are satisfied.

igure $2$: A basic feasible solution for Question $3($d$).$ The numbers on

be arcs indicate the flow along that arc. Arcs with zero flow are not

bown.

$($c$)$ For this transportation problem written in the form:

minimise $c^{t}x,$

subject $toAx,=b$

$,x,0,$

write all vectors and matrices, clearly identifying all elements.

$($d$)$ Figure $2$ shows a basic feasible solution for this transportation

problem. Confirm that this is a basic solution as well as a

feasible solution, and then calculate the objective.

$($e$)$ Write the dual of this transportation problem in equation

form, in terms of supplies $u_i,i=1,2,3,$ and demands $v_j,$

$j=1,2,3,4$ and slack variables $\frac{?}{\text{b}\text{a}\text{r}}(c{)}_{ij}.$ Then use complementary

slackness arguments to find a dual $($infeasible$)$ solution that

corresponds to the primal solution given in Question $3($d$).$

Confirm that you have found the corresponding dual solution

by showing it has the same objective value as the given primal

solution.

$($f$)$ Use the transportation simplex method to simultancously to

find the optimal primal solution and objective. As an initial

solution, use the basic feasible solution given in Question $3($d$).$

Draw a graph of your final solution $($only including nonzero

flows$).$