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

Решение основной задачи линейного программирования геометрическим методом является наглядным в случае двух и даже трех переменных. Для случая же большего числа переменных геометрический метод становится невозможным. Так называемый симплекс-метод принадлежит к числу аналитических методов решения основной задачи линейного программирования. Симплексный метод - это метод целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечно число шагов расчета либо найти оптимальное решение, либо установить, что оптимальное решение не существует.

Основное содержание метода состоит в следующем:

1. Указать способ нахождения начального опорного решения.

2. Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции ближе к оптимальному.

3. Задать критерии, которые позволяют своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.

Система ограничений в вычислительных методах обычно задается системой линейных уравнений

(8)

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

Выразим через остальные переменные.

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

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

Переменные (неизвестные) x₁, x₂,…, x_r называются базисными, а весь набор { x₁, x₂,…, x_r } – базисом, остальные переменные называются свободными. Подставляя в линейную форму L вместо базисных переменных их выражения через свободные, получим

.

Теперь полагая все свободные переменные равными нулю, найдем значения базисных переменных: , ,…,. Таким образом, решение системы является допустимым – оно называется базисным. Для полученного базисного решения значение линейной формы L_Б = γ₀. Решение задачи с помощью симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б переходим к другому базису с таким расчетом, чтобы значение L_Б уменьшалось или, по крайней мере, не увеличивалось, т.е. .

Идею метода проследим на конкретных примерах.

Дата добавления: 2014-01-20