6. Взаимно-двойственные злп и их экономический смысл.

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

Рассмотрим формально две задачи Iи IIлинейного програм­мирования, представленные в таблице,абстрагируясь от содержа­тельной интерпретации параметров, входящих в их экономико-математические модели.

Обе задачи обладают следующими свой­ствами:

1. В одной задаче ищут максимум линейной функции, в другой – минимум.

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

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида " ",а в задаче минимизации – все неравенства вида " ".

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

5. Число неравенств в системе ограничений одной задачи совпа­дает с числом переменных в другой задаче.

6. Условия неотрицательности переменных сохраняются в обеих за­дачах.

Замечание. Если на -ю переменную исходной задачи наложено условие неотрицательности, то -е ограничение двойственной задачи будет неравенством, если же -я переменная может принимать как положительные, так и отрицательные значения, то -е ограничение двойственной задачи будет уравнением; аналогично связаны между собой ограничения исходной задачи и переменные двойственной.

Две задачи I и II линейного программирования, обладающие ука­занными свойствами, называются симметричными взаимно двойст­венными задачами.В дальнейшем для простоты будем называть их простодвойственными задачами.

Каждой задаче ЛП можно поставить в соответствие двойственную ей задачу.

Алго­ритм составления двойственной задачи:

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут мак­симум линейной функции, то все неравенства системы ог­раничений привести к виду "", а если минимум –к виду "". Для этого неравенства, в которых данное требование не выполняется, умножить на –1.

2. Составить расширенную матрицу системы  , в которую включить матрицу коэффициентов при переменных, стол­бец свободных членов системы ограничений и строку ко­эффициентов при переменных в линейной функции.

3. Найти матрицу  , транспонированную к матрице.

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

6. Взаимно-двойственные злп и их экономический смысл.

Теория двойственности в линейном программировании. Двойственный симплекс-метод

Каждой задаче линейного программирования соответствует другая задача, называемаядвойственной или сопряженной по от­ношению к исходной. Теория двойственности оказалась полезной для проведения качественных исследований задач линейного программирования.