ТЕМА 2 Решение задач оптимального планирования симплекс-методом

 

Обобщенная схема решения задач оптимального планирования симплекс-методом

следующая:

1 Приведение задачи к каноническому виду.

2 Нахождение исходного базисного решения, составление симплексной таблицы.

З Проверка базисного решения на оптимальность.

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

Вычислительная схема прямого алгоритма симплекс-метода состоит из следующих шагов:

1 Просматриваются знаки всех элементов оценочной строки Z . Если в задаче на максимум все Zj > 0, то задача решена: допустимое базисное решение оптимально, mах Z = Z0. Если не все Zj > 0, то осуществляется переход к шагу 2.

2 Среди всех отрицательных элементов оценочной строки в задаче на максимум находится наибольшее по абсолютной величине и соответствующий ему столбец выбирается в качестве ключевого. Если в ключевом столбце элементы <0, то целевая функция неограниченна, mах Z = . Решение окончено. Если не ни элементы <0, то переходим к шагу 3.

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

4 Выполняется преобразование симплексной таблицы по формулам [14, с.22} и осуществляется переход к шагу 1.

Вычислительная схема двойственного симплекс-метода состоит из следующих шагов:

 

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

2 Среди отрицательных элементов bi выбирается величина, наибольшая по абсолютной величине. Этому элементу соответствует ключевая строка.

3 В ключевой строке проверяются знаки всех элементов аrj .

Если все аrj >= 0, то решение окончено, задача неразрешима.

Если найдется хотя бы один коэффициент аrj <0, то осуществляется переход к шагу 4.

4 Среди отрицательных элементов аrj, ключевой строки выбирается элемент аrк, для которого и называется ключевым.

5 Выполняется преобразование симплексной таблицы и переход к шагу 1.

Если в исходной задаче имеются отрицательные элементы среди элементов столбца свободных членов и Z - строки одновременно, то решение задачи состоит из двух этапов:

сначала с помощью двойственного симплекс - метода исключаются все хi < 0, затем оптимальное решение находится прямым симплекс - методом. Следует только на первом этапе изменить шаг 4 алгоритма следующим образом.

4. Среди отрицательных элементов аrj ключевой строки выбирается элемент аrк, для которого ,

аrj <0.