Решение задач линейного программирования
Наиболее простым и распространенным методом решения канонической задачи линейного программирования до сих пор является симплекс-метод, предложенный в 40-е годы прошлого века Дж. Данцигом. Геометрически идею симплекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче линейного программирования является некоторое многогранное множество и-мерного векторного пространства (в частном случае n = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начинается с некоторой начальной вершины (начального опорного плана) многогранного множества. Специальным образом выясняется, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина находится, то она и принимается за следующее приближение. После этого вновь исследуются соседние вершины для полученного приближения и т. д. до тех пор, пока не будет получена вершина, среди соседних вершин которой не существует вершины с лучшим значением целевой функции. Такая вершина является оптимальной. Она соответствует оптимальной точке (оптимальному решению) задачи линейного программирования.
В настоящее время разработан широкий круг различных численных методов решения задач линейного программирования, каждый из которых учитывает ту или иную специфическую особенность имеющейся задачи линейного программирования.
Кроме симплекс-метода имеются и другие методы решения специальных задач ЛП: метод потенциалов, Венгерский метод, двойственный симплекс-метод, метод обратной матрицы (модифицированный симплекс-метод) и др.
Идея симплекс-метода состоит в следующем. На начальном этапе выбирается любая начальная вершина G и определяются все выходящие из нее ребра. Далее перемещаются вдоль того из ребер, по которому функция увеличивается (при поиске максимума) и попадают в следующую вершину многогранника, образующего область допустимых решений. Находят выходящие из нее ребра и повторяют процесс. Когда приходят в такую вершину, в которой вдоль всех выходящих из нее ребер функция убывает, то максимум найден.
Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. То есть нужно представить задачу в канонической форме.
Решение задачи при помощи симплекс-метода распадается на ряд шагов. В каждой вершине многогранника будет m ненулевых координат, которые образуют базис. Остальные (n-m) координат входят в набор небазисных (свободных) переменных. На каждом k-м шаге от данного базиса Бk переходят к другому, новому базису Бk+1 с таким расчетом, чтобы значение функции f(x) увеличивалось, т. е. fБk+1≥fБk. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Бk* , для которого fБ(k*) есть искомый максимум для линейной функции f, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.
Пусть мы имеем задачу линейного программирования:
Целевая функция вида:
и ограничения
, 
Переобозначим свободные коэффициенты ограничений aj0=bj. Приведем матрицу ограничений к каноническому виду:
(2.4)
Используя метод Гаусса - Жордана, приведем записанную систему к виду, где выделены базисные переменные. Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений и др. задач.
Задачи линейного программирования, решаемые с помощью симплекс-метода, основываются на представлении решения в табличной форме. Рассмотрим последовательность действия при решении задачи линейного программирования.
По последней системе ограничений и целевой функции в каноническом виде построим симплекс-таблицу.
Таблица 4.1. Симплекс-таблица
| С | С1 | С2 | С3 | … | Сj | … | Cn | … | |||
| Bx | A0 | A1 | A2 | A3 | … | Aj | … | An | An+1 | … | An+m |
| xn+1 | a10 | a11 | a12 | a13 | … | a1j | … | a1n | … | ||
| xn+2 | a20 | a21 | a22 | a23 | … | a2j | … | a2n | … | ||
| … | … | … | … | … | … | … | … | … | … | … | |
| xn+i | ai0 | ai1 | ai2 | ai3 | … | aij | … | ain | … | ||
| … | … | … | … | … | … | … | … | … | … | … | |
| xn+m | am0 | am1 | am2 | am3 | … | amj | … | amn | … | ||
| L | a00 | a01 | a02 | a03 | … | a0j | … | a0n | a0m+1 | … | a0m+n |
Все дальнейшие преобразования связаны с изменением содержания этой таблицы.
Нижняя строка элементов аок, к = 0,…,m+п называется индексной. Элементы индексной строки вычисляются следующим образом:
означает номер соответствующей строки.
Поскольку на первом шаге заполнения таблицы все элементы сn+i равны нулю, то элементам индексной строки присваиваются значения соответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. аok= -Ск. Последняя строка таблицы служит для определения направляющего столбца.
Элемент а00 равен значению целевой функции, которое вычисляется по формуле 
- номер базисной переменной (индексация идет по строкам таблицы).
В столбце Вх записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные {хп+к }, к =1,…,n. В дальнейшем фиктивные переменные необходимо вывести из базиса.
В столбец С записываются коэффициенты при хп+к,; на первом шаге значения этих коэффициентов равны нулю.
Далее выполняются преобразования в соответствии с алгоритмом симплекс -метода.
Алгоритм симплекс-метода:
Этап 1. Находится начальное допустимое базисное решение
Этап 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.
2.1. В последней строке симплекс-таблицы находят наименьший элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим.
Этап 3. На основе условия допустимости выбирается исключаемая переменная.
3.1. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке. То есть разрешающая строка соответствует той из базисных переменных, которая будет увеличиваться меньше других. Если таких переменных нет (все ai,вед. ≤0), то задача неразрешима.
3.2. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
3.3. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к элементам последней строки симплекс-таблицы.
Этап 4. Методом Гаусса - Жордана вычисляется новое базисное решение. Переход к этапу 1.
4.1. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот.
4.2. Вычисление элементов новой таблицы выполняется так.
Новая ведущая строка =текущая разрешающая строка / разрешающий элемент.
Для элементов остальных строк:
Новая строка = текущая строка – ее коэффициент в разрешающем столбце ×новая разрешающая строка.
4.2. Как только получится таблица, в которой в последней строке все элементы положительны, считается, что максимум найден. Максимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.