6 Workco must have the following number of workers available during the next three months: month 1, 20; month 2, 16; month 3, 25. At the beginning of month 1, Workco has no workers. It costs Workco $100 to hire a worker and

$50 to fire a worker. Each worker is paid a salary of

$140/month. We will show that the problem of determining a hiring and firing strategy that minimizes the total cost incurred during the next three (or in general, the next n)

months can be formulated as an MCNFP.

a Let xij number of workers hired at beginning of month i and fired after working till end of month j 1

(if j 4, the worker is never fired). Explain why the following LP will yield a minimum-cost hiring and firing strategy:

Transcribed Image Text:

min z = 50(x12x13x23) +100(x12+ X13 +14 + x23 +x24 + x34) +140(x12+23+ X34) +280(x13x24) + 420x14 s.t. (1) 12 +13+ X14 e = 20 (Month 1 constraint) (2) 13 +14 + x23 + x24e2 = 16 (Month 2 constraint) (3) x14x24x34 - e3 = 25 (Month 3 constraint) Xij0 b To obtain an MCNFP, replace the constraints in part (a) by i Constraint (1); ii Constraint (2) - Constraint (1); iii Constraint (3) - Constraint (2); iv (Constraint (3)). Explain why an LP with Constraints (i)-(iv) is an MCNFP. c Draw the network corresponding to the MCNFP ob- tained in answering part (b).