$(25$ pts$)$ For parts $($a$)$ and $($b$)$ formulate one or more linear programming constraints to

capture the stated condition. Introduce, and clearly define, additional decision variables if

necessary.

$($a$)(9$ pts$)$ Let x$\_($j$),$j$=1,2,$dots,n$,$ be decision variables satisfying the following constraints:

$\backslash$sum$\_($j$=1)^$n $|$x$\_($j$)-$a$\_($j$)|+$max$\_($i$)=1,2,$dots,m$\{\backslash$sum$\_($j$=1)^$n b$\_($ij$)$x$\_($j$)\}+$max$\_($i$)=1,2,$dots,m$\{\backslash$sum$\_($j$=1)^$n c$\_($ij$)$x$\_($j$)\}<=$d

x$\_($j$)>=0,$AAj$=1,2,$dots,n

Rewrite these constraints using $($a reasonable number of$)$ linear programming constraints.

$($b$)(8$ pts$)$ Let s$\_($i$)$ denote the supply at origin iinI, and let d$\_($j$)$ denote the demand at

destination jinJ, where these supplies and demands are integer$-$valued and total supply

equals total demand. Let x$\_($ij$)$ be a decision variable denoting the $($nonnegative$)$ continuous

volume that we ship from i to j$.$ Not all i$-$j combinations are possible, and so you should

introduce set notation to capture this fact. Using this notation write data$-$independent linear

programming constraints that limit the amount shipped out of each origin to be at most

its supply, and linear programming constraints that require the amount shipped to each

destination to be at least its demand.

$($c$)(8$ pts$)$ Continuing with part $($b$),$ suppose we seek to minimize an objective function

which is linear in the x$\_($ij$)$ variables. And, suppose the linear program has a unique optimal

solution. Are we ensured that we would obtain integer$-$valued solutions when solving the

linear program? If yes, explain why this is the case. If no$,$ then are there further conditions

under which we can be sure that we would obtain integer$-$valued solutions?