During the next three months, Shoemakers, Inc. must meet $($on time$)$ the following demands for shoes: month $1,1,000$ pairs; month $2,1,500$ pairs; month $3,1,800$ pairs. It takes $1$ hour of labor to produce a pair of shoes. During each of the next three months, the following number of regular$-$time labor hours are available: month $1,1,000$ hours; month $2,1,200$ hours; month $3,1,200$ hours. Each month, the company can require workers to put in up to $400$ hours of overtime. Workers are paid only for the hours they work, and a worker receives $$4$ per hour for regular$-$time work and $$6$ per hour for overtime work. At the end of each month, a holding cost of $$1\mathrm{.}50$ per pair of shoes is incurred for the remaining inventory.

$($a$)(20$ points$)$ Formulate a minimum cost network flow problem that can be used to

minimize the total cost incurred in meeting the demands of the next three months. A

formulation requires drawing the appropriate network and determining the cij$$s$,$ bi$$s

and the arc capacities. You do not have to write down the formulation explicitly.

$11$

$($b$)(10$ points$)$ How would you modify your answer in part $($a$)$ if demand could be

backlogged $($all demand must still be met by the end of month $3)$ at a cost of

$$20/$pair$/$month$?$ Draw the appropriate network and determine the cij$$s$,$ bi$$s and the arc

capacities. You do not have to write down the formulation explicitly.