По симплексному методу находится оптимальный план задачи

Целевая функция выражена через свободные члены и максимизирована.

Найден начальный опорный план задачи.

Задача должна быть приведена к каноническому виду, притом все элементы столбца свободных членов должны быть неотрицательными.

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

\ Одним из универсальных методов решения задач ЛП является симплекс-метод или метод последовательного улучшения плана. Если задача разрешима, то ее оптимальный план совпадает, по крайней мере, с одним из опорных решений системы ограничений. Именно этот опорный план и отыскивается симплекс-методом в результате упорядоченного перебора опорных решений. Упорядоченность понимается в том смысле, что при переходе от одного опорного плана к другому соответствующие им значения целевой функции возрастают (не убывают). Так как общее число опорных решений конечно, то через определенное число шагов будет либо найден опорный план, либо установлена неразрешимость задачи. Чтобы получить новый опорный план, первоначальный базис преобразовывают в новый. Для этого из первоначального базиса удаляют некоторую базисную переменную и вместо нее вводят другую из группы свободных.

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

Этапы решения задачи ЛП симплекс-методом:

Нахождение оптимального опорного плана

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

(2.49)

(2.50)

,. (2.51)

,. (2.52)

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

,,,

и подставим в выражение функции Z. Получим приведенные коэффициенты целевой функции:

.

Составим исходную симплекс-таблицу, записывая приведенные коэффициенты целевой функции в z -строку с противоположными знаками, а константу со своим знаком.

Симплекс-таблица:

1. Если в z -строке симплекс-таблицы, содержащей некоторый опорный план, нет отрицательных элементов (не считая свободного члена), то данный план оптимален и задача решена. К тому же, если в z -строке симплекс-таблицы, содержащей оптимальный план, нет нулевых элементов (не считая и элементов соответствующих базису ), то оптимальный план единственный. В противном случае задача ЛП имеет бесконечное множество решений.

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

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

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

5. Выполняют одну итерацию по замещению базисной переменной методом Жордана-Гаусса. Строят новую симплексную таблицу и переходят к первому пункту.

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

Пример 4.

Решить задачу из примера 1 симплекс-методом:

Решение.

Дата добавления: 2013-12-13