4. Симплекс-метод

Позволяет найти решение задачи линейного программирования за гораздо меньшее число действий. Изложим идею метода.

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

При канонической форме записи многогранника условий из каждой его вершины исходит ребер. Выбирая одно ребро, мы выбрасываем из рассмотрения вершины, лежащие на остальных траекториях. Следовательно, за k шагов мы рассматриваем часть вершин, проходя мимо остальных. Нам надо найти искомую вершину среди вершин многогранника. Приравнивая число вершин величине получим, что минимум достигается примерно за шагов, т. е. достаточно быстро.

Выведем формулы шага. Первую вершину находим по формуле (46). Чтобы найти ребро, надо одну из внебазисных переменных сделать положительной; тогда координаты точек ребра можно выразить через нее из (45) при помощи обратной матрицы

(47)

остальные внебазисные координаты остаются равными нулю. Будем увеличивать до тех пор, пока одна из базисных координат не обратится в нуль. Это будет при

минимум ищется только среди тех индексов t, для которых ибо только эти координаты вдоль данного ребра уменьшаются и, следовательно, могут обратиться в нуль.

Если все суммы при данном отрицательны, то это ребро неограниченное и весь многогранник условий — тоже.

Подставляя найденное в формулы (47), получим координаты новой вершины и вычислим в ней значение функции . Поочередно меняя каждую внебазисную переменную, найдем все ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах L, и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине , то переместимся в наинизшую из новых вершин и повторим процесс. Если же , то минимум уже достигнут в исходной вершине.

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

Если эта величина отрицательна, то задача линейного программирования вообще не имеет решения Если же она неотрицательна, то это ребро не ведет к минимуму, и оно нас не интересует.

Нетрудно оценить, что для выполнения всех шагов и получения минимума требуется примерно до арифметических действий. Это уже приемлемо для крупных современных ЭВМ.

Симплекс-метод является примером высоко специализированного метода. Он пригоден только для нахождения минимума линейной функции в многомерном выпуклом многограннике определенного вида — симплексе. Зато он позволяет решать задачи с огромным числом переменных.