Основные идеи симплексного метода

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

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

1. Если задача линейного программирования имеет оптимальное решение (единственное), то это решение является базисным. Если же оптимальное решение не единственное, то среди множества оптимальных решений все равно найдется базисное.

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

Казалось бы, алгоритм достаточно прост: надо построить все базисные решения для данной задач и выбрать из них наилучшее, для которого значение функции Z максимально (или минимально). Однако подобный алгоритм также практически нереализуем для сколько-нибудь серьезной задачи.

Отсюда вытекает вторая идея симплексного метода: получив некоторое базисное решение, выяснить, существует ли решение лучше. Если существует, то рассматривать именно лучшее решение, а не любое другое базисное решение.

Геометрически симплексный метод может быть интерпретирован как движение по соседним угловым точкам многогранника (многоугольника) решений.