Удовлетворение ограничений

Удовлетворение ограничений и логическое программирование

Проблема удовлетворения ограничений формулируется, как описано ниже.

Дано:

1) множество переменных;

2) области определения, из которых могут выбираться значения переменных;

3) ограничения, которым должны удовлетворять переменные.

Найти:

такие значения, присваиваемые переменным, которые удовлетворяют всем заданным ограничениям.

Часто существует несколько вариантов присваивания, удовлетворяющих ограничениям. В задачах оптимизации может быть определен критерий выбора вариантов присваивания, которые удовлетворяют ограничениям.

Как оказалось, подход, предусматривающий поиск значений переменных, удовлетворяющих ограничениям, и особенно его сочетание с логическим программированием, представляет собой инструментальное средство, которое может весьма успешно применяться для решения широкого круга задач. К типичным примерам таких задач относятся задачи планирования, снабжения и управления ресурсами на производстве, на транспорте и в складском хозяйстве. Для решения этих задач необходимо распределять ресурсы по процессам, например: автобусы по маршрутам; солдат по постам; экипажи по самолетам; бригады по поездам; врачей и медсестер по дежурствам и сменам и т.д.

Рассмотрим типичный пример из области планирования. Предположим, что имеются четыре задания, а, b, с и d, продолжительности которых составляют соответственно 2, 3, 5 и 4 часа. Между этими заданиями установлены ограничения предшествования: задание а должно предшествовать заданиям b и с, а задание b должно предшествовать заданию d (рис. 14.1). Задача состоит в том, чтобы найти значения времени начала выполнения соответствующих задач Та, Тb, Тс и Td таким образом, чтобы время завершения Tf выполнения всего расписания было минимальным. Допустим, что самым ранним временем запуска является 0.

Рис. 14.1. Ограничения предшествования между заданиями а, b, с, d

Соответствующую задачу удовлетворения ограничений можно формально определить, как описано ниже.

Переменные: Та, Тb, Тс, Td, Tf.

Области определения: все переменные — неотрицательные действительные числа.

Ограничения:

Та + 2 ≤ Тb. Задача а, на выполнение которой требуется 2 часа, предшествует b;

Та +2 ≤ Тс Задача а предшествует задаче с;

Тb + 3 ≤ Td. Задача b предшествует задаче d;

Тс + 5 ≤ Тf. Задача с завершается к моменту времени Tf;

Td + 4 < Tf. Задача d завершается к моменту времени Tf.

Критерий: минимизация значения Tf.

Эта задача удовлетворения ограничений имеет множество решений, причем все они позволяют обеспечить минимальное время завершения. Это множество решений можно определить следующим образом:

Та = 0

Тb = 0

2 ≤ Тс ≤ 4

Тd = 5

Tf = 9

Определены все значения времени начала, за исключением задания с, выполнение которого может начаться в любое время в интервале от 2 до 4.