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

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

следующая:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а_rj <0.