Chapter 3, Problem 47RP

Explanation of Solution

Formulation of LP to complete the given goal:

• Assume the following,
  • Let “${\text{P}}_{\text{mn}}$” be the number of police officers, who get days off for “m” and “n” of week for “$\text{m<n}$”.
    • Consider day “1” as Sunday, day “2” as Monday, day “3” as Tuesday, and “day “4” as Wednesday, day “5” as Thursday, day “6” as Friday, and day “7” as Saturday.
  • Notice that on Saturday “$\text{30}-\text{28=2}$” police officers should get the days off.
  • The police officers who getting Saturday off have “m” or “$\text{n=7}$”.
• The following Linear Programming (LP) formulation can be obtained by repeating the above reasoning and observing that those police officers getting consecutive days off have “$\left|\text{n}-\text{m}\right|=1$” or “$\text{m}=1$” and “$\text{n}=7$”,

  $\text{max}\text{z=}{\text{P}}_{\text{12}}+{\text{P}}_{\text{17}}+{\text{P}}_{\text{23}}+{\text{P}}_{34}+{\text{P}}_{45}+{\text{P}}_{56}+{\text{P}}_{67}$

  $\begin{array}{l}\text{S}\text{.T}\text{.}\\ {\text{P}}_{\text{17}}+{\text{P}}_{\text{27}}+{\text{P}}_{37}+{\text{P}}_{47}+{\text{P}}_{57}+{\text{P}}_{67}=2(denotestheconstraintonSaturday)\\ {\text{P}}_{\text{12}}+{\text{P}}_{13}+{\text{P}}_{14}+{\text{P}}_{15}+{\text{P}}_{16}+{\text{P}}_{17}=12(denotestheconstraintonSunday)\\ {\text{P}}_{\text{12}}+{\text{P}}_{\text{23}}+{\text{P}}_{24}+{\text{P}}_{25}+{\text{P}}_{26}+{\text{P}}_{27}=2(denotestheconstraintMonday\end{array}$