- •Послеоптимизационный анализ решения задач
- •Введение
- •Введение 3 Лабораторная работа № 3. Послеоптимизационный анализ решения задач линейного программирования 4
- •Приложение. Рекомендации по использованию excel и matlab 16
- •1.1.3 Двойственные оценки и их назначение
- •1.2 Послеоптимизационный анализ решения злп
- •1.2.1 Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.
- •2 Порядок выполнения лабораторной работы
- •3 Задания для лабораторного практикума
- •3. (Определение оптимального ассортимента)
- •6. (Задача о раскрое)
- •7. (Определение оптимального плана производства)
- •Литература
- •Приложение. Рекомендации по использованию excel и matlab
- •4 Решение задач математического программирования средствами excel
- •4.1 Ввод условий задачи линейного программирования
- •4.2 Работа в диалоговом окне Поиск решения
- •4.3 Анализ оптимального решения.
1.1.3 Двойственные оценки и их назначение
Теорема 1 (теорема об оценках). В оптимальном решении двойственной задачи значения переменных численно равны частным производным для исходной задачи.
Данная теорема позволяет определить приращение целевой функции при малых изменениях свободных членов системы ограничений, то есть,
f(y*, )= ,
где y* - оптимальное решение двойственной задачи, y*=( ).
Если в план включаются новые виды продукции, то их оценка производится по формуле
Если <0, то новый вид продукции улучшает план. При >0 нецелесообразно вводить новый вид продукции.
1.2 Послеоптимизационный анализ решения злп
Для любой практической задачи линейного программирования недостаточно просто найти оптимальное решение, но целесообразно проводить анализ на чувствительность – исследование зависимости оптимального решения от параметров целевой функции и условий - ограничений. В общем случае приемы, используемые при этом анализе, достаточно просты, хотя и несколько громоздки.
1.2.1 Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.
Под допустимыми понимают такие изменения этих коэффициентов, при которых оптимальный базис рассматриваемой ЗЛП (т.е. базис при последней итерации симплекс – метода, соответствующий оптимальному решению) остается оптимальным.
Пусть изменениям подвергнется коэффициент . Обозначим через Jб, Jнеб множество индексов базисных и небазисных векторов в оптимальном плане x0 соответственно.
Найдем значения оценок после изменения cr для двух случаев:
r Jнеб , тогда
для всех j≠r ;
для j=r ; (5)
2) r Jб,
jJнеб (6)
Очевидно, что для сохранения оптимальности прежнего плана при изменениях коэффициента cr необходимо и достаточно сохранение знаков оценок для всех небазисных переменных. Поэтому из условий ≥0 в соответствии с формулами (5) и (6) можно определить допустимые изменения коэффициента , при которых сохраняется прежнее оптимальное решение. Если одновременно изменяются несколько коэффициентов, то
получим соотношения, аналогичные (6), в которых оценки будут функциями уже нескольких параметров (δ1, δ2,., δr). Решая совместно систему неравенств вида (c1, c2,.,cr)≥0, jJнеб, находим условия для , при которых прежний оптимальный базис сохраняется.
1.2.2 Определение диапазонов допустимых изменений параметров , i=1,…,n.
В задачах распределительного типа величина характеризует предельно возможный объем потребления i-го ресурса. Изменение значений свободных членов приводит к увеличению или уменьшению Fmax . Это изменение Fmax определяется величиной решения двойственной задачиy* и может быть оценено таким образом только тогда, когда при изменении величин b оптимальный план исходной задачи остается неизменным.
Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение
xопт= A-1x b.
Предположим, что мы изменили вектор ресурсов b=|| bi || на bн=b+ ∆b и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение
xн = А-1хbн = А-1х(b+∆b).
Если все компоненты xiн ≥ 0, то это решение xн = [xiн] оптимально (т.е. оптимальный базис не изменился).