л;, + х2 > 1 (улица А),
х2 + х3 > 1 (улица В),
xt + x6 > 1 (улица С),
х7 + хе>1 (улица D),
х6 + х7 > 1 (улица £),
x2 + л;6 > 1 (улица F),
хг + хе > 1 (улица G),
x4 + л;7 > 1 (улица Н),
х2 + xt > 1 (улица /),
xs + xs > 1 (улица J),
д:3 + х& > 1 (улица ЛГ),
xt = 0 или 1,= 1, 2,8.
В соответствии с оптимальным решением задачи (полученным с помощью программы TORA, файл Ch9ToraSetCoverEx9-l-3.txt) необходимо установить телефоны на перекрестках 1, 2, 5 и 7.
Рассмотренная выше модель является типичным представителем общего класса задач, именуемых задачами о покрытии. В этой модели все переменные являются двоичными. Все коэффициенты левой части каждого ограничения равны 0 или 1, а правая часть ограничений имеет вид ">1". Целевая функция всегда имеет вид с1х1 + сгх2 + ...+спхп, где с;>0 для всех j = 1, 2 п, и подлежит минимизации. В рассмотренном примере с; = 1 для всех Однако если величина с; будет равна стоимости установки телефона на ;-м перекрестке, то эти коэффициенты могут принимать значения, отличные от 1.
УПРАЖНЕНИЯ 9.1.3
1. Компания ABC занимается доставкой грузов пяти потребителям. Можно выбрать следующие маршруты перевозки грузов.
Маршрут | Потребители |
| 1, 2, 3, 4 |
| 4, 3, 5 |
| 1, 2, 5 |
| 2, 3, 5 |
| 1, 4, 2 |
| 1, 3, 5 |
Эти маршруты определяются грузоподъемностью автомобиля, доставляющего грузы. Например, на маршруте 1 автомобиль имеет грузоподъемность, достаточную для доставки грузов лишь потребителям 1, 2, 3 и 4. Следующая таблица содержит расстояния (в милях) между терминалом компании ABC и потребителями.
Необходимо выполнить дневные поставки пяти потребителям, минимизируя при этом пройденный суммарный путь. Оптимальное решение может быть таким, что один и тот же потребитель обслуживается более чем одним маршрутом. Но при реализации такого решения используется только один из этих маршрутов. Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя программу TORA.
2. Американский университет формирует комитет по рассмотрению жалоб студентов. В соответствии с указаниями, полученными из администрации, в эту комиссию необходимо включить по крайней мере одну женщину, одного мужчину, одного студента, одного администратора и одного преподавателя. Выдвинуты десять кандидатур (обозначенных для удобства буквами от а до ;). Принадлежность этих кандидатур к различным категориям отражена в следующей таблице.
Категория | Кандидатуры |
Женщины | а, о, с, d, в |
Мужчины | f, 9, h, i, j |
Студенты | a, b, c, j |
Администраторы | e, f |
Преподаватели | d, g, h, i |
Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой из указанных категорий. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.
3. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести городах. Однако в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.
Сформулируйте задачу в виде задачи ЦЛП, оптимальное решение которой определит наименьшее количество станций и их расположение. Найдите оптимальное решение, используя программу TORA.
4. Сокровища короля Тута находятся в музее в Новом Орлеане. План музея, состоящего из нескольких комнат, соединенных открытыми дверями, показан на рис. 9.2. Сторож, находящийся у двери, может наблюдать за двумя смежными комнатами. Администрация музея заинтересована, чтобы в каждой комнате присутствовал сторож, но число сторожей должно быть минимальным. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.
I I I
-I г
I Т т
Рис. 9.2. План музея
Пример 9.1.4. Ограничения типа "или-или"
Машиностроительная компания использует один станок для выполнения трех заказов. Время выполнения, а также срок сдачи каждого заказа даны в приведенной ниже таблице. Сроки сдачи заказов вычисляются от начальной даты, т.е. предполагаемого начала выполнения первого заказа.
Заказ | Время выполнения заказа (дни) | Срок сдачи заказа (дни) | Штраф за задержку заказа (долл./день) |
| | | |
| | | |
| | | |
Требуется определить последовательность выполнения заказов, которая минимизирует штраф за задержку сдачи заказов.
Определим переменную х/ как дату завершения заказа /, измеряемую в днях от начальной даты. Задача имеет два типа ограничений: 1) ограничения, которые гарантируют, что никакие два заказа не выполняются одновременно; 2) ограничения по срокам сдачи заказов. Сначала рассмотрим первый тип ограничений.
Два заказа i и /, время выполнения которых pt и pjt не будут выполняться одновременно, если
или xt > Xj + Pj, или х} > xt + pt,
в зависимости от того, будет ли заказ i предшествовать выполнению заказа или наоборот.