Предположим, что производство на следующей неделе разделено на фиксированные периоды времени или смены. Необходимо назначить сотрудников посменно, чтобы в каждой смене работало необходимое количество людей. Нельзя заполнить каждую смену независимо от других, потому что разрешены только определенные еженедельные графики. Например, человек не может работать пять смен подряд. Таким образом, нашу задачу более правильно рассматривать как назначение сотрудников на доступные графики работы, так что бы каждая смена обеспечивалась необходимым количеством персонала, а общее назначение персонала было наиболее экономично.
Мы можем удобно представить графики для этой задачи с помощью индексированного набора подмножеств смен:
set SHIFTS; # смены
param Nsched; # Номер расписания;
set SCHEDS = 1..Nsched; # набор расписаний
set SHIFT_LIST {SCHEDS} within SHIFTS;
Для каждого расписания j в наборе SCHEDS, смены сотрудника работающего по расписанию j, содержатся в наборе SHIFT_LIST[j]. Мы также указываем ставку оплаты на человека для каждого расписания и количество человек, необходимое для каждой смены:
param rate {SCHEDS} >= 0;
param required {SHIFTS} >= 0;
Переменная Work[j] представляет количество людей, назначенных для работы в каждом графике j, и минимизируем sum of rate[j]*Work[j] по всем графикам:
var Work {SCHEDS} >= 0;
minimize Total_Cost: sum {j in SCHEDS} rate[j]*Work[j];
Наконец, наши ограничения говорят о том, что общее количество сотрудников, назначенных на каждую смену, должно быть не менее требуемого количества:
subject to Shift_Needs {i in SHIFTS}:
sum {j in SCHEDS: i in SHIFT_LIST[j]} Work[j] >= required[i];
Слева мы берем сумму Work[j] по всем графикам j, так что i находится в SHIFT_LIST[j]. Эта сумма представляет общее количество сотрудников, назначенных для расписаний, содержащих смену i, и, следовательно, равно общему числу сотрудников, назначенных на смену i.
Неловкое описание ограничения в этой формулировке побуждает нас попробовать колоночную формулировку. Как и в наших предыдущих примерах, мы сначала объявляем цель и ограничения, но с пропущенными переменными:
minimize Total_Cost;
subject to Shift_Needs {i in SHIFTS}: to_come >= required[i];
Коэффициенты Work[j] появляются вместо этого в объявлении var. В целевой функции var имеет коэффициент rate[j]. В ограничениях членство в SHIFT_LIST[j] говорит нам именно то, что нам нужно знать: Work[j] имеет коэффициент 1 в ограничении Shift_Needs[i] для каждого i в SHIFT_LIST[j] и коэффициент 0 в других ограничениях. Это приводит нас к следующей краткой записи:
var Work {j in SCHEDS} >= 0, obj Total_Cost rate[j], coeff {i in SHIFT_LIST[j]} Shift_Needs[i] 1;
Полная модель имеет следующий вид:
set SHIFTS; # смены
param Nsched; # номер расписания;
set SCHEDS = 1..Nsched; # набор расписаний
set SHIFT_LIST {SCHEDS} within SHIFTS;
param rate {SCHEDS} >= 0;
param required {SHIFTS} >= 0;
minimize Total_Cost;
subject to Shift_Needs {i in SHIFTS}: to_come >= required[i];
var Work {j in SCHEDS} >= 0, obj Total_Cost rate[j], coeff {i in SHIFT_LIST[j]} Shift_Needs[i] 1;
В качестве конкретного примера этой модели представьте, что у вас есть три смены в день с понедельника по пятницу и две смены в субботу. Каждый день вам нужно 100, 78 и 52 сотрудника в первую, вторую и третью смены соответственно. Для простоты предположим, что стоимость на одного человека одинакова независимо от графика, так что можно просто минимизировать общее количество сотрудников, установив rate[j] в 1 для всех j.
Что касается расписаний, разумное правило составления расписаний может заключаться в том, что каждый сотрудник работает пять смен в неделю, но не более одной смены в течение любого 24-часового периода. Часть файла данных показана ниже. Мы не показываем весь файл, потому, что имеется 126 расписаний, которые удовлетворяют правилу! Получающаяся в результате линейная программа со 126 переменными не является трудной для решения:
MINOS 5.5: optimal solution found. 19 iterations, objective 265.6 ampl: option display_eps .000001; ampl: option omit_zero_rows 1; ampl: option display_1col 0, display_width 60; ampl: display Work; Work [*] := 10 28.8 30 14.4 71 35.6 106 23.2 123 35.6 18 7.6 35 6.8 73 28 109 14.4 24 6.8 66 35.6 87 14.4 113 14.4 ;
Как видите, оптимальное решение использует 13 графиков, некоторые в дробных количествах. (Существует много других оптимальных решений этой проблемы, поэтому полученные результаты могут отличаться.) Если округлить каждую дробь в этом решении до следующего наивысшего значения, мы получим довольно хорошее реальное решение, используя 271 сотрудника. Однако, чтобы определить, является ли это целочисленное решение - лучшим, необходимо использовать методы целочисленного программирования.
Удобство формулировки по столбцам в этом случае напрямую зависит от того, как мы решили представлять данные. Мы представляем, что разработчик моделей будет думать с точки зрения расписаний и будет пытаться добавлять, отбрасывать или изменять разные расписания, чтобы посмотреть, какие решения могут быть получены. Подмножества SHIFT_LIST[j] предоставляют удобный и лаконичный способ ведения расписаний в данных. Поскольку данные затем упорядочены по графикам, и для каждого расписания также имеется переменная, она оказывается проще - и для более крупных примеров - более эффективно - определять коэффициенты по переменной.
Модели такого типа используются для решения различных задач планирования. Для удобства можно использовать ключевое слово cover (в порядке from и to для сетей), чтобы указать коэффициент 1:
var Work {j in SCHEDS} >= 0, obj Total_Cost rate[j], cover {i in SHIFT_LIST[j]} Shift_Needs[i];
Некоторые из наиболее известных и самых крупных примеров - это планирование экипажей авиакомпаний, где переменные могут представлять распределение экипажей, а не отдельных лиц, смены становятся полетами, и для каждого полета требуется один экипаж. Затем у нас есть так называемая проблема покрытия множеств, в которой цель состоит в том, чтобы наиболее экономично охватить множество всех рейсов с подмножествами, представляющими расписания экипажа.
