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

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

При решении задачи линейного программирования графическим методом фактически перебирали все вершины многоугольной допустимой области. Такой перебор можно сократить, если учитывать линейность целевой функции, чтобы каждая следующая вершина была лучше предыдущей. Идея последовательного улучшения решения легла в основу симплекс-метода решения задач линейного программирования.

Для реализации симплекс-метода необходимо определить: 1) первоначальное допустимое решение задачи, 2) правило перехода к лучшему решению, 3) критерий проверки оптимальности найденных решений. Для этого составляются различные алгоритмы симплекс-метода. Рассмотрим один из них для нахождения максимального значения целевой функции на следующем примере.

Найти максимальное значение функции , если переменные удовлетворяют системе ограничений:

1. Вводим новые переменные , с помощью которых неравенства системы преобразуем в уравнения:

У коэффициентов целевой функции меняем знак или записываем ее в виде . Заполняем первую симплексную таблицу, в нулевой строке записываем х₁, х₂ и (свободные коэффициенты). В нулевом столбце – х₃, х₄, х₅ и F. Заполняем эту таблицу по полученной системе уравнений и преобразованной целевой функции.



	-2
		-1
	-2	-3

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

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

Для определения разрешающей строки свободные коэффициенты делим на соответствующие элементы разрешающего столбца и выбираем минимальное отношение, при этом отрицательные коэффициенты не берем. Имеем , вторая строка является разрешающей. Пересечение разрешающей строки и столбца дает разрешающий элемент – это 3.

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

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

Заполнение таблиц по таким правилам продолжаем до тех пор, пока не будет выполнен критерий. Имеем для нашей задачи еще две таблицы.

	х₁	х₄	b		х₃	х₂	b
х₃		-1		х₁
х₂				х₂
х₅				х₅
F	-4			F

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

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

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