Определение оптимального решения задач линейного программирования.

После получения опорного плана решения задач линейного программирования переходим к определению оптимального решения.

Оптимальноерешение – это решение, при котором целевая линейная функция принимает экстремальные значения – минимальное или максимальное.

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

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

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

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

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

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

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

Тема: Решение транспортной задачи