Question $1(25$ marks$)$:

We want to assign exactly each of the nodes in the left$-$hand$-$side nodes to exactly one of the

right$-$hand$-$side nodes $($one to one assignment$).$ Use the Hungarian method to obtain the

minimum cost assignment.

Show each step clearly $(15$ pts$)$ and report an optimal solution $(5$ pts$)$ and its objective

value $(5$ pts$).$

The numbers on the arcs show the assignment costs. $($e$.$g$.$ assigning node $1$ to node $B$ costs $7)$

If there is no arc between two nodes, then assignment is not allowed between them. $($e$.$g$.$

assigning node $1$ to node $C$ is not allowed$)$ SOlve the following Linear Program graphically. Please carefully explain the steps and report an optimal solution.

Hint: Solving graphically often means that you are dealing with a model with atmost two decision variables. In light of this observation, look at the model carefully and attempt to first satisfy it

min $4$x$1+$x$2$

s$.$t

$3$x$1+$x$2-3$x$3-3$x$4\_>4$

x$1+$x$2+$x$3\_>6$

x$1+$x$4\_>4$

x$3,$x$4\_>1$

x$3,$x$4\_<mn\; id="EditorElement\_1310615">1</mn>$

x$1,$x$2\_>0$