Исследование операций в экономике

В теории математического программирования доказывается, что с любой задачей линейного программирования может быть связана другая, сопряженная с ней задача, которая называется двойственной по отношению к первоначальной. Первоначальную задачу называют при этом прямой (по отношению к двойственной). Коэффициенты последней строки в прямой задаче являются решением двойственной и наоборот, то есть объективно обусловленные оценки представляют результат решения двойственной задачи.
Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение х*, то другая также имеет оптимальное решение у*. При этом соответствующие им оптимальные значения целевых функций f*=f(x*) и g*=g(y*) равны.
Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.
Симплекс - метод представляет собой итеративную процедуру решения задач ЛП, записанных в стандартной форме, система уравнений в которой и с помощью элементарных операций над матрицами приведена к каноническому виду:
x1 + a1,m+1 xm+1 + ... + a1s xs+...+ a1n xn = b1;
x2 + a2,m+1 xm+1 + ... + a2s xs+...+ a2n xn = b2;
xm + am,m+1 xm+1 + ... + ams xs+...+ amn xn = bm.
Переменные x1, x2,...,xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (xm+1, ...,xn) называются небазисными переменными.