A personnel selection problem.

$($a$)$ A contractor is assembling a crew with six positions. The contractor will select the six people from among a dozen of the firm's cmployees who are willing to travel. Each of the dozen people who are eligible for the assignment has heen rankud according to effectiveness in each of the six slots. The selection problem is to chorse the six crew members from the $12$ eligible employees in such a way that the crew's total effectiveness is maximized. You are given the effectiveness $e_{11}$ of the $i$ th eligible employee in the jth position on the crew, in all $72$ parameters. The decision variables are

$x_{ij}=1,0$; it is $1$ if eligible employec $i$ is chosen for the $j$ th job on the crew, and $0$ otherwise.

Formulate this problem as a zero$-$one programming problem. Suppose this problem was solved as a continuous or relaxed linear programming problem. that is$.$ with the variables only constrained to be greater than or equal to zero. What evidence do you have that this problem, solved as a continuous LP$.$ will solve with all variables equal to zero or onc?

$($b$)$ As an added feature of this problem, the particular set of employees are well known to one another, and not all of them get along. In particular, employee five and employee nine, though individually valued by the company, have a longstanding dislike for one another, a dislike that makes them ineffective when working together and disruptive of the work of others. You still want to assemble the most effective crew but now you need to create a crew that does not have both employees five and nine.