For the picture galleries the plans of which are given in Fig. 1, find the smallest number of attendants who, if placed in the various doorways connect two adjacent rooms, can supervise all rooms. Use integer programming and the simplex method to solve.
<image 1>
['1 attendant', '2 attendants', '3 attendants', '4 attendants']
(a) Minimize x1 + x2 + x3 + x4 + x5, subject to: x1 + x2 $\ge $ 1, x1 + x4 $\ge $ 1, x4 + x5 $\ge $ 1, x2 + x3 + x5 $\ge $ 1. xj = 1 or 0, j = 1, ..., 5. (b) Minimize x1 + x2 + x3 + x4 + x5 + x6,  subject to: x1 + x2 $\ge $ 1, x1 + x3 $\ge $ 1 x2 + x3 + x4 + x5 $\ge $ 1 x4 + x6 $\ge $ 1, x5 + x6 $\ge $ 1 xj = 1 or 0 j = 1, ...,6. Answers (Fig. 2):