Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. - М.: Наука, 1981.

2. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. - М.: Наука, 1969.

3. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. - М.: Издательский дом Вильяме , 2004.

КОМПЛЕКСНЫЕ ЗАДАЧИ

3.1. Небольшой консервный завод производит пять типов консервов на основе трех видов свежих фруктов. Завод имеет два производственных цеха, которые при необходимости могут наращивать выпуск продукции. В настоящее время производственные цеха работают в одну смену, но без труда могут перейти на двух- или трехсменную работу. Реальным ограничением наращивания выпуска продукции является только объем поставляемых на переработку свежих фруктов. Поскольку объемы холодильных камер ограничены, желательно, чтобы все фрукты перерабатывались в течение рабочего дня.

Молодой аналитик, специалист по исследованию операций, горит желанием увеличить уровень производства этого завода. После анализа производственной ситуации он сформулировал задачу линейного программирования. Задача включает пять переменных (для пяти видов продукции) и три ограничения (для трех видов сырья). Теория ЛП говорит о том, что в задаче с пятью переменными и тремя ограничениями оптимальное решение не может содержать более трех базисных переменных. Следовательно, оптимальное решение предполагает производство не более трех видов продукции. Ага, - подумал

аналитик, - производство этой компании явно не оптимально.

Он добился встречи с менеджером по производству для обсуждения построенной модели ЛП. Менеджер, подробно ознакомившись с задачей, нашел, что модель адекватно отображает сложившуюся производственную ситуацию.

Аналитик объяснил, что согласно теории ЛП, поскольку задача имеет только три ограничения, оптимальный план производства не должен содержать более трех видов продукции, и поэтому завод должен прекратить выпуск двух бесприбыльных видов продукции. Менеджер, внимательно выслушав аналитика, сказал, что его компания не может прекратить выпуск двух видов продукции, так как это не выгодно предприятию. Но, чтобы согласовать теорию и практику, он предложил добавить в модель еще два ограничения, тогда будет пять ограничений, и в этом случае оптимальное решение должно разрешить производство всех пяти видов продукции.

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

Как разрешить этот парадокс ?

3.2. Транспортная компания, специализирующаяся на перевозках грузов, имеет множество терминалов, расположенных в стратегических точках по всей

Комплексные задачи

территории США.* Когда грузы поступают на терминал, они сортируются: часть груза, предназначенная местному потребителю, ему же и поступает, остальной груз отправляется к следующему терминалу. Терминальные доки обслуживают как постоянные, так и временные работники, набираемые по найму. Постоянным работникам гарантирована 40-часовая рабочая неделя. Они работают в одну из трех стандартных смен непрерывно в течение пяти дней, но их рабочая неделя может начаться в любой день недели. Временные работники нанимаются на любое количество рабочих часов при пиковых поступлениях грузов, превышающих возможности их обработки постоянными работниками.

Грузы могут поступать на терминалы в любое время, причем неравномерно в течение суток. Изучение статистических данных показывает, что распределение поступления грузов примерно одинаково каждую неделю, и пик поступления грузов обычно приходится на конец недели (пятница-воскресение). Политика компании требует, чтобы грузы задерживались на терминалах не более, чем на 16 часов.

Разработайте модель, с помощью которой можно было бы назначать в рабочие смены постоянных работников и нанимать временных.

Эта задача основана на исследованиях, проводимых автором для национальной транспортной компании.

ГЛАВА 4

ДВОЙСТВЕННОСТЬ И АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

Мы уже встречались с анализом чувствительности (на элементарном уровне) в разделе 2.3. В этой главе мы подробнее рассмотрим методы анализа чувствительности, основанные на теории двойственности.

4.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

Исходную задачу линейного программирования будем называть прямой. Двойственная задача - это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи. В этом разделе рассмотрены правила построения двойственных задач.

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

Максимизировать или минимизировать целевую функцию г = при ограничениях