В дополнение к транспортным, существуют еще фиксированные затраты в объеме 10 ООО, 15 ООО и 12 ООО долл., связанные с 1, 2 и 3 заводом соответственно. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.

4. Повторите упражнение 3, предполагая, что спрос потребителей 2 и 3 уменьшился до 800 единиц.

Пример 9.1.3. Задача о покрытии

Для обеспечения безопасности студентов отдел безопасности американского университета устанавливает телефоны экстренного вызова на территории студенческого городка. Отделу желательно установить минимальное количество телефонов таким образом, чтобы на каждой из основных улиц этого городка был расположен по крайней мере один телефон. На рис. 9.1 представлены основные улицы (от А до К) студенческого городка.

Улица А

ев Я К

Улица В

®

Улица Е

ев Я Я

Улица С

ев Я К

Улица D

©

Рис. 9.1. Схема улиц студенческого городка

Логично расположить телефоны на пересечениях улиц так, чтобы каждый телефон мог обслуживать по меньшей мере две улицы. Из рис. 9.1 видно, что данное расположение улиц требует не более восьми телефонов.

Определим, что переменная х} равна 1, если телефон расположен на перекрестке / (j =1,2, 8), и 0 в противном случае.

Условия задачи требуют установки по меньшей мере одного телефона на каждой из 11 улиц (от А до К). Поэтому задачу можно сформулировать следующим образом.

Минимизировать г = хг + х2 + х3 + xt + xs + х6 + х7 + xs

при ограничениях

л;, + х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 автомобиль имеет грузоподъемность, достаточную для доставки грузов лишь потребителям 1, 2, 3 и 4. Следующая таблица содержит расстояния (в милях) между терминалом компании ABC и потребителями.

Необходимо выполнить дневные поставки пяти потребителям, минимизируя при этом пройденный суммарный путь. Оптимальное решение может быть таким, что один и тот же потребитель обслуживается более чем одним маршрутом. Но при реализации такого решения используется только один из этих маршрутов. Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя программу TORA.

2. Американский университет формирует комитет по рассмотрению жалоб студентов. В соответствии с указаниями, полученными из администрации, в эту комиссию необходимо включить по крайней мере одну женщину, одного мужчину, одного студента, одного администратора и одного преподавателя. Выдвинуты десять кандидатур (обозначенных для удобства буквами от а до ;). Принадлежность этих кандидатур к различным категориям отражена в следующей таблице.

Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой из указанных категорий. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.

3. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести городах. Однако в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.