A restaurant during a particularly busy day intends to plan a schedule for its chefs. The restaurant schedules its chefs for 12 hours shifts. The beginning times for the shifts are 6:00am, 12:00pm and 6:00pm. A doctor beginning a shift of these times works for the next 12 hours. During normal and week day operations, the number of chefs needed varies depending on the time of the day. The restaurant staffing guidelines require the following minimum number of doctors on duty. 6:00am - 12:00pm needs 8 chefs.

12:00pm - 6:00pm needs 7 chefs. 6:00pm - 12:00am needs 5 chefs. Formulate a linear program finding the optimal chef allocation that minimizes the total number of chefs while meeting the shift demand. Note that the hour shift (12 hour) is longer than each single-time slot, implying that a chef must work on multiple time-slots.