Геометрическая интерпретация симплексного метода

Выше рассмотрены основные теоремы линейного программирования, из которых следует, что если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Там же был указан путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор, в конце концов, приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т. е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, не хуже), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума , уменьшение – при отыскании минимума ).

Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере.

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

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования- симплексного метода (лат. simplex – простой, простейший выпуклый многогранник в n-мерном пространстве с n+1 вершиной, например, тетраэдр в 3-мерном пространстве).

Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).

 

 

Рис. 6.7. Область допустимых решений

 

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым Л. В. Канторовичем.

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

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

· способ определения какого-либо первоначально допустимого базисного решения задачи;

· правило перехода к лучшему (точнее не худшему) решению;

· критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.