Сформулируйте задачу в виде задачи ЦЛП, оптимальное решение которой определит наименьшее количество станций и их расположение. Найдите оптимальное решение, используя программу 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 предшествовать выполнению заказа или наоборот.

Поскольку все математические модели имеют дело лишь с совместными ограничениями, мы преобразуем ограничения типа или-или, введя дополнительную двоичную переменную

fl, если заказ i предшествует заказу j, уи=\п

(0, если заказ j предшествует заказу i.

При достаточно большом М ограничение типа или-или преобразуется в следующие два совместных ограничения.

My,j + [x,-xt)>Pj и M{\-yil) + {xl-xi)>pi.

Указанное преобразование гарантирует, что лишь одно из двух ограничений может быть активным в любой момент времени. Если ytj = 0, первое ограничение является активным, а второе - избыточным (так как его левая часть будет содержать величину М, которая намного больше р). Если у, =1, первое ограничение является избыточным, а второе - активным.

Рассмотрим теперь ограничения по срокам сдачи заказов. При заданной дате сдачи заказа введем в рассмотрение неограниченную по знаку переменную Sj. Тогда соответствующее ограничение примет вид

*,+Р,+ ,-<*,

Если Sj > 0, то заказ сдается в срок, если же sy < 0, получаем убытки, связанные с задержкой сдачи заказа. Используя стандартную замену

приводим ограничение к виду

xj + s)-s-l=dj-pj. Штраф за задержку сдачи заказа пропорционален s].

Математическая модель рассматриваемой задачи принимает следующий вид. Минимизировать z = 19л, + 12л; +34

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

х,-х2 + М</12>20, -ж, + х2- Му12 > 5 - М, х,-х3 + Му,3>15, -ж, + ж3 - Му13 > 5 - М, х2 - х3 + Му23> 15, -х2 + х3-М</23>20-М, xt + sl - s~ =25-5,

x2 + sl -s2 =22-20,

x3 + sl - sl = 35-15,

x x2, x3, sl, sj , sl, sl, sl, sl >0,

Ух2> У XV </23 = 0иЛи1-

Целочисленные переменные yl2, у13 и у23 введены для преобразования ограничений типа или-или в совместные ограничения. Конечная задача является частично-целочисленной задачей линейного программирования.

Для решения задачи выберем М = 100 - число, которое больше суммы времени изготовления всех трех заказов.

Оптимальным решением (полученным с помощью программы TORA, файл Ch9ToraEitherOrEx9-l-4.txt) является хг = 20, х2 = 0 и х3 = 25. Следовательно, оптимальной последовательностью выполнения заказов будет 2 -> 1 -> 3. В соответствии с оптимальным решением заказ 2 выполняется за время 0 + 5 = 5, заказ 1 - за время 20 + 5 = 25 и заказ 3 - за 25 + 15 = 40 дней. В результате выполнение заказа 3 задержано на 40 - 35 = 5 дней, что приводит к штрафу в размере 5 х 34 = 170 долл.

УПРАЖНЕНИЯ 9.1.4

1. Игральная доска состоит из девяти равных квадратов, расположенных 3x3. Требуется заполнить каждый квадрат числом из интервала от 1 до 9 таким образом, чтобы сумма чисел каждой строки, каждого столбца и каждой диагонали была равна 15. Определите числа в каждом квадрате для следующих случаев.

a) Числа в каждой строке и каждом столбце различны.

b) Числа во всех квадратах различны.

Запишите сформулированную задачу в виде задачи ЦЛП с ограничениями и решите ее с помощью программы TORA.

2. Станок используется для производства двух взаимозаменяемых видов продукции. Производительность станка позволяет за день изготовить не более 20 единиц продукции первого вида и 10 единиц второго вида. Существует альтернативная наладка станка, позволяющая ежедневно изготовлять не более 12 единиц продукции вида 1 и 22 единицы вида 2. Анализ рынка показывает, что максимальный суммарный спрос на два вида продукции составляет 35 единиц ежедневно. Предположим, что прибыль от производства единицы продукции первого и второго вида составляет 10 и 12 долл. соответственно. Какая из двух возможных настроек станка должна быть выбрана? Сформулируйте задачу в виде задачи ЦЛП и решите ее с помощью программы TORA. (Примечание. Сформулированная двухмерная задача может быть решена путем перебора возможных решений после графического построения пространства допустимых решений. Этого нельзя сделать в л-мерной задаче.)

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

Продукция Необходимое время (час./ед.) Необходимое сырье (фунты/ед.)

1 3 4

2 4 3

3 5 6

Доходы от производства единицы каждого вида продукции равны 25, 30 и 22 долл. соответственно. Компания имеет возможность организовать выпуск