
Linear Programming 31
Determine if the LP is unbounded or not. If it is, specify a sequence of
vectors x
(k)
such that the objective function −→ −∞ as k −→ ∞.
Exercise 1.8
Suppose that there are 4 different projects and 4 workers and each worker
must be assigned a project and each project must be assigned a worker. It
costs $20 an hour for a worker. The following table gives the time required (in
hours) for each worker i to complete a particular project j:
Project 1 Project 2 Project 3 Project 4
Worker 1 7 3 6 10
Worker 2 5 4 9 9
Worker 3 6 4 7 10
Worker 4 5 5 6 8
(a) Formulate this problem of assigning workers and jobs at minimum cost
as a linear program.