Классические методы решения задачи линейного программирования

Одним из классических методов решения задачи линейного программирования является симплекс-метод. Существо симплекс-метода состоит в следующем. Находим какое-либо допустимое базисное решение. Его можно найти, приняв какие-либо переменных за свободные, приравняв их нулю и решив систему уравнений (3.3). Если при этом некоторые из базисных переменных окажутся отрицательными, то нужно выбрать другие свободные переменные, т.е. перейти к новому базису.

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

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