рос решил осуществить такой же план и, повторив деление на три части оставшейся суммы, присвоил себе еще и монету, которая осталась после деления. На третью ночь третий матрос взял третью часть того, что осталось, и одну дополнительную монету, которая осталась после деления. Когда корабль достиг берега, старший помощник капитана разделил остаток денег поровну между тремя матросами и снова осталась одна монета. Старший помощник отложил эту монету в сторону и вручил матросам предназначенные им равные части. Сколько денег было в самом начале? Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя программу TORA. (Совет. Задача имеет бесконечно много целочисленных решений. Предположите для удобства, что следует определить минимальную сумму денег, которая удовлетворяет условиям задачи. Увеличивая затем полученное решение на 1, рассмотрите его как нижнюю границу и получите новое минимальное решение. Продолжая таким образом, можно найти формулу для общего решения.)

7. Имеются следующие слова, состоящие из трех букв: AFT, FAR, TVA, ADV, JOE, FIN, OSF и KEN. Предположим, что буквам алфавита приписаны числа (метки), начиная с А = 1 и заканчивая Z = 26. Каждое слово помечается числом, равным сумме числовых меток составляющих его трех букв. Например, слово AFT имеет метку 1 + 6 + 20 = 27. Необходимо выбрать пять из заданных восьми слов таким образом, чтобы получить максимальную суммарную метку. Вместе с тем выбранные пять слов должны удовлетворять следующему условию: (сумма меток первых букв) < (сумма меток вторых букв) < (сумма меток третьих букв).

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

8. Фирма, специализирующаяся на грамзаписи песен, заключила договор с восходящей звездой эстрады на запись восьми песен. Продолжительность песен равна 8, 3, 5, 5, 9, 6, 7 и 12 минут соответственно. Фирма планирует использовать для записи двусторонние кассеты. Каждая сторона имеет длительность звучания 30 минут. Фирма намерена распределить песни на две стороны кассеты сбалансированным образом. Это значит, что продолжительность звучания песен на каждой стороне кассеты должна быть примерно одинаковой (насколько это возможно). Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение.

9. Рассмотрите задачу из предыдущего упражнения, предположив, что характер мелодий песен диктует условия, согласно которым третья и четвертая песни не могут быть записаны на одной стороне кассеты. Сформулируйте задачу в виде задачи ЦЛП. Возможно ли использование 25-минутной (для каждой стороны) кассеты для записи 8 песен? Если нет, используйте модель ЦЛП, чтобы определить минимальную емкость кассеты для записи.

Пример 9.1.2. Задача с постоянными затратами

Три телефонные компании предложили мне подписаться на их услуги по дальней связи в пределах Соединенных Штатов. Услуги компании MaBell стоят 16 долл. в месяц плюс 0,25 долл. за каждую минуту связи. Компания PaBell оценивает свои услуги в 25 долл. в месяц, но имеет поминутную оплату в 0,21 долл. Что касается компании BabyBell, месячная плата равна 18 долл., а стоимость минуты связи - 0,22 долл. Мои телефонные звонки на дальние расстояния в среднем составляют обычно 200 минут в месяц. Предполагается, что я не вношу помесячной платы, если не использую телефон для звонков на дальние расстояния, и что я могу распределять звонки между тремя компаниями, как мне хочется. Как я должен использовать три компании, чтобы минимизировать свой месячный телефонный счет?

Эта задача может быть легко решена без использования методов ЦЛП. Тем не менее поучительно сформулировать ее как целочисленную задачу.

Пусть

л:, - количество минут разговора (на дальние расстояния) в месяц через компанию MaBell,

х2- количество минут разговора в месяц через компанию PaBell, х3- количество минут разговора в месяц через компанию BabyBell, (/, = 1, если х, > 0, и у, = 0 при х, = 0, у2 = 1, если х2 > 0, и у2 = 0 при х2 = 0, у3 = 1, если х3 > 0, и у3 = 0 при х3 = 0.

Для обеспечения равенства ys = 1 при положительном значении переменной xj используем ограничение х Myjt j - 1, 2, 3, где М- достаточно большое число, которое не должно ограничивать величину х. Так как звонки на дальние расстояния занимают около 200 минут в месяц, т.е. х1 < 200 для всех j, поэтому достаточно положить М= 200.

Теперь можно сформулировать следующую задачу.

Минимизировать г = 0,25л:, + 0,21х2 + 0,22х3 + 16у, + 2Ьу2 + 18у3 при ограничениях

х, + х2 + х3 = 200,

<200г/

x2<200j/2, х3<200у3,

гл. у 2 г/3 = 0или 1-

Формулировка задачи показывает, что помесячная /-я оплата за пользование телефоном является частью целевой функции г лишь при условии У,= , которое по определению может выполняться лишь тогда, когда х} > 0. Если в оптимальном решении будет Xj = 0, то минимума функции z (с учетом положительности коэффициента при у} можно достичь только при равенстве нулю yjt что и требуется.

Оптимальным решением данной задачи (получено с помощью TORA, файл Ch9ToraFixedChargeEx9-l-2.txt) является х3 = 200, у3 = 1, все остальные переменные равны нулю. Это значит, что копания BabyBell должна быть выбрана для

услуг по дальней связи. Следует подчеркнуть, что информация, которую несет значение переменной j/3 = 1, является избыточной, так как такой же результат следует из хг > 0 (= 200). В самом деле, основной причиной использования переменных / у2 и у3 является лишь учет месячной платы за телефон. В сущности, только эти двоичные переменные преобразуют исходную нелинейную задачу в частично-целочисленную, поддающуюся аналитическому решению.

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

УПРАЖНЕНИЯ 9.1.2

1. Компания планирует производство некоторой продукции на трех станках, которой должно быть изготовлено не менее 2000 единиц. Минимальная производительность любого станка равна 500 единиц. Следующая таблица содержит необходимую информацию для рассматриваемой задачи.

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

2. Нефтедобывающая компания изучает вопрос о бурении четырех нефтяных скважин на двух нефтеносных участках. Издержки подготовки к бурению на каждом участке и затраты на бурение скважины ; на участке i (i=l, 2; j=l, 2, 3, 4) приведены в следующей таблице.

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

3. Рассматриваются три промышленных участка для размещения обрабатывающих заводов, которые снабжают своей продукцией трех потребителей. Данные об объемах производства продукции, объемах потребления и себестоимости (в долл.) перевозки продукции от заводов к потребителям содержатся в следующей таблице.

1 2 3 Объем производства

Спрос 1200 1700 1600