Комплексные задачи
территории США.* Когда грузы поступают на терминал, они сортируются: часть груза, предназначенная местному потребителю, ему же и поступает, остальной груз отправляется к следующему терминалу. Терминальные доки обслуживают как постоянные, так и временные работники, набираемые по найму. Постоянным работникам гарантирована 40-часовая рабочая неделя. Они работают в одну из трех стандартных смен непрерывно в течение пяти дней, но их рабочая неделя может начаться в любой день недели. Временные работники нанимаются на любое количество рабочих часов при пиковых поступлениях грузов, превышающих возможности их обработки постоянными работниками.
Грузы могут поступать на терминалы в любое время, причем неравномерно в течение суток. Изучение статистических данных показывает, что распределение поступления грузов примерно одинаково каждую неделю, и пик поступления грузов обычно приходится на конец недели (пятница-воскресение). Политика компании требует, чтобы грузы задерживались на терминалах не более, чем на 16 часов.
Разработайте модель, с помощью которой можно было бы назначать в рабочие смены постоянных работников и нанимать временных.
Эта задача основана на исследованиях, проводимых автором для национальной транспортной компании.
ГЛАВА 4
ДВОЙСТВЕННОСТЬ И АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ
Оптимальное решение задачи линейного программирования определяется теми условиями, которые нашли отражение в модели в момент ее формирования. В реальной жизни условия, формирующие модель, не остаются неизменными. В связи с этим особое значение приобретают средства, позволяющие оценить изменения в оптимальном решении, вызванные изменениями в параметрах исходной модели. Таким средством является анализ чувствительности. Он предлагает эффективные вычислительные методы, позволяющие изучить динамическое поведение оптимального решения.
Мы уже встречались с анализом чувствительности (на элементарном уровне) в разделе 2.3. В этой главе мы подробнее рассмотрим методы анализа чувствительности, основанные на теории двойственности.
4.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ
Исходную задачу линейного программирования будем называть прямой. Двойственная задача - это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи. В этом разделе рассмотрены правила построения двойственных задач.
При изложении теории двойственности часто рассматривают формулировки двойственной задачи в зависимости от различных видов прямой задачи, которые определяются типами ограничений, знаками переменных (неотрицательные или свободные, т.е. без ограничения в знаке) и типом оптимизации (максимизация или минимизация целевой функции). Такая "привязка" двойственной задачи к исходной не всегда оправдана (см. упражнение 4.1.7). В этой книге приводится единая формулировка двойственной задачи, применимая ко всем видам прямой задачи. В основу такой формулировки положена стандартная форма прямой задачи (см. раздел 3.1). Напомним, что задача ЛП в стандартной форме записывается следующим образом.
Максимизировать или минимизировать целевую функцию г = при ограничениях
В состав п переменных х} входят также дополнительные переменные. Стандартная форма задачи ЛП предполагает выполнение следующих условий.
1. Все ограничения записаны в виде равенств с неотрицательной правой частью.
2. Все переменные неотрицательны.
3. Оптимизация определяется как максимизация или минимизация целевой функции.
Стандартная форма задачи ЛП порождает стандартную таблицу симплекс-метода. Поэтому, как будет показано ниже, решение двойственной задачи можно получить непосредственно из симплекс-таблицы, соответствующей оптимальному решению прямой задачи. Таким образом, определив двойственную задачу на основе стандартной формы прямой задачи, после вычислений симплекс-метода мы автоматически получаем решение двойственной задачи.
Переменные и ограничения двойственной задачи формируются путем симметричных структурных преобразований прямой задачи по следующим правилам.
1. Каждому из т ограничений прямой задачи соответствует переменная двойственной задачи.
2. Каждой из п переменных прямой задачи соответствует ограничение двойственной задачи.
3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи становятся коэффициентами ограничения двойственной задачи, соответствующей этой переменной, а правая часть формируемого ограничения равна коэффициенту при этой переменной в выражении целевой функции.
4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.
Графически эти правила представлены в табл. 4.1.
Таблица 4.1. | Формирование двойственной задачи из прямой | |
Переменные | | Переменные прямой задачи | | | |
двойственной | | | | | | |
задачи | | | | | | |
| | | ... в,; | a-in | | |
| | | | | | щшшшш |
| | | | | | шШШШШШШШШШФШ |
| | | j-e ограничение двойственной задачи | Коэффициенты целевой функции двойственной задачи |
Правила, определяющие тип оптимизации и ограничений, а также знак переменных двойственной задачи, приведены в табл. 4.2. Напомним, что в прямой задаче все ограничения записаны в виде равенств с неотрицательными правыми частями и все переменные неотрицательны.