Алгебра симплекс — метода.
Существо метода состоит в следующем. Находим какое-нибудь базисное решение. Далее проверяем, не достигнут ли уже максимум целевой функции. Если нет, то ищем новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение q/. Затем процедуру повторяем. Для перехода к новому допустимому базисному решению одну из свободных переменных следует сделать базисной. При этом она станет отличной от нуля и будет возрастающей. Если какая либо свободная переменная входит в целевую функцию со знаком «+», т. е. при её увеличении целевая функция увеличивается, то максимум не достигнут и данную переменную следует сделать базисной (отличной от нуля).
Математическое описание.
Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. В данной главе рассматривается общий метод решения задач ЛП, называемый симплекс-методом .
Информация, которую можно получить с помощью симплекс-метода, не ограничивается лишь оптимальными значениями переменных.
Процесс решения задачи линейного программирования носит итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Процедуры, реализуемые в рамках симплекс-метода, требуют применения вычислительных машин — мощного средства решения задач линейного программирования .
Симлекс-метод — это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач.
Правая и левая части ограничений линейной модели могут быть связаны знаками. Кроме того, переменные, фигурирующие в задачах ЛП, могут быть неотрицательными или не иметь ограничения в знаке. Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме, которую назовем стандартной формой линейных оптимизационных моделей. При стандартной форме линейной модели.
1. Все ограничения записываются в виде равенств с неотрицательной правой частью;
2. Значения всех переменных модели неотрицательны;
3. Целевая функция подлежит максимизации или минимизации.
Покажем, каким образом любую линейную модель можно привести к стандартной.
