Модели параметрического программирования

Во многих задачах математического программирования исходные данные зависят от некоторого параметра. Такие задачи называются задачами параметрического программирования.

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

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

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

(6.1)

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

(6.2)

Здесь зависимость от параметра t носит линейный характер. Решение сформулированной задачи находят методами линейного программирования.

Процесс решения задачи параметрического программирования включает следующие этапы.

1. Считая значение параметра t равным некоторому числу t [ ] находят оптимальный план X* или устанавливают неразрешимость полученной задачи линейного программирования.

2. Определяют множество значений параметра t [ ] для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключаются из рассмотрения.

3. Полагают значение параметра t равным некоторому числу, принадлежащему оставшейся части промежутка [ ] и симплексным методом находят решение задачи линейного программирования.

4. Определяют множество значений параметра t, для которых новый оптимальный план остается оптимальным или задача неразрешима.

5. Вычисления повторяют до тех пор, пока не будут исследованы все значения параметра t [ ].

Пример. Предприятие для изготовления изделий А, В, С использует 3 вида сырья. Нормы расхода сырья каждого вида на производство единицы продукции каждого вида, а также цена изделия каждого вида приведены в таблице 3.15.

Изделие А, В и С могут производиться в любых количествах (т.к. сбыт обеспечен) в пределах выделенных ресурсов сырья.

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

Таблица 6.1 – Исходные данные

ЭММ. Целевая функция:

(6.3)

Ограничения:

(6.4)

(6.5)

(6.6)

Найдем решение симплекс-методом.

Оно имеет вид:

x₁=0 шт. x₂=8 шт. x₃=20 шт. F=400 р.

Установим возможные границы изменения цен каждого из изделий, внутри которых найденный оптимальный план не меняется. Предположим, что цена с₁ равна 9+t₁ р. Требуется найти такие значения параметра t₁, при которых оптимальный план остается неизменным. Построив симплекс-таблицу, можно найти что, оптимальный план остается неизменным при t₁ 5. Это означает, что предприятию нецелесообразно включать в план выпуск продукции изделий вида А при условии, что цена одного изделия не превышает 14 р. При этом предполагаем, что остальные исходные данные остаются без изменений.

Аналогично можно показать, что если цена с одного изделия вида. В изменяется в интервале 8 c₂ 20, то оптимальный план остается без изменений.

Также можно показать, что если цена 1-го вида изделий вида. С изменяется 8 c₃ 20, то оптимальный план остается неизменным.

При этом значение целевой функции, несмотря на неизменный оптимальный план, при различных значениях параметров t₁, t₂, t₃ будет различным.

Вопросы для самопроверки:

1. Определите область применения моделей параметрического программирования.

2. Покажите алгоритм решения задачи параметрического программирования.