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

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

Дано:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Та = О

ТЬ - О

2 <, Тс < А

Td = 5 Tf - 9

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

302 Часть II. Применение языка Prolog в области искусственного интеллекта