Лабораторная работа № 3. Послеоптимизационный анализ решения задач линейного программирования

Цель лабораторной работы: Использование методов линейного программирования для решения конкретных экономических задач и

проведения послеоптимизационного исследования оптимального решения.

Теоретический обзор

Основная задача линейного программирования формулируется следующим образом:

 max                                                                   (1)

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

                                                                     (2)

Двойственные задачи линейного программирования

Построение двойственной задачи

Пусть имеем общую задачу линейного программирования, записанную в произвольной форме

 max

                                                              (3)

 

Двойственная задача по отношению к задаче (3) запишется в виде

 min

                                                              (4)

 

При построении двойственной задачи соблюдаются следующие правила:

1. каждому i-му ограничению задачи (3) соответствует переменная y_i задачи (4), и, наоборот, каждому j-му ограничению двойственной задачи (4) соответствует переменная x_j задачи (3);

2. матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием;

3. свободные члены ограничений задачи (3) являются коэффициентами при соответствующих переменных целевой функции двойственной задачи (4); аналогично коэффициенты целевой функции задачи (3) совпадают со свободными членами системы ограничений двойственной задачи (4);

4. если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется;

5. в задаче (3) ограничения-неравенства следует записывать со знаком ≤, а для задачи (4) – со знаком ≥;

6. если на j-ю переменную задачи (3) наложено условие неотрицательности, то j-е ограничение задачи (4) будет неравенством. В противном случае j-е ограничение будет равенством; аналогично связаны между собой ограничения задачи (3) и переменные задачи (4).

Двойственные оценки и их назначение

Теорема 1 (теорема об оценках). В оптимальном решении двойственной задачи значения переменных  численно равны частным производным  для исходной задачи.

Данная теорема позволяет определить приращение целевой функции при малых изменениях свободных членов D системы ограничений, то есть,

Df@(y*,D )= ,

где y* - оптимальное решение двойственной задачи, y*=().

Если в план включаются новые виды продукции, то их оценка производится по формуле

Если <0, то новый вид продукции улучшает план. При >0 нецелесообразно вводить новый вид продукции.

Послеоптимизационный анализ решения ЗЛП

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