9. Нахождение оптимального варианта. Теорема об оптимальности.

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

Выбор разрешающего элемента:

Z→max

Разрешающий столбец: среди отрицательных коэффициентов строки Z выбрать наибольший по абсолютной величине. Пусть это будет С_S.

Разрешающая строка: поделить свободные члены на соответствующие коэффициенты, кроме строки Z, т.е. b₁ / a_1s; b₂ / a_2s; b_r / a_rs; b_m / a_ms. Наименьшее из положительных отношений укажет на разрешающую строку. Пусть это будет b_r / a_rs.

Z→min

Разрешающий столбец: среди положительных коэффициентов строки Z выбрать наибольший.

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

Выбирая описанным способом разрешающие элементы делаем шаги МЖИ до получения оптимально варианта.

Замечание. Если разрешающий элемент получен не по наименьшему положительному отношению, то в следующей таблице МЖИ будет снова недопустимый вариант.

10. Случай вырожденности в симплекс-методе.

Если среди свободных членов появляется 0, то мы имеем случай вырожденности (кроме строки Z).

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

11. Случай невозможности нахождения экстремального значения функций.

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

12. Случай неразрешимости модели

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

13. Решение модели со смешанной системой ограничений

Решение симплекс-методом моделей со смешанной системой ограничений, т.е. среди ограничений есть как строгие равенства, так и неравенства.

Сначала в качестве разрешающей строки взять строку, в которой записано строгое равенство. Разрешающий элемент в этой строке выбирается произвольно. В следующей таблице МЖИ после ее проверки столбец, соответствующий разрешающему, вычеркнуть. Такую процедуру повторить для каждого строгого равенства до их полного исключения. Затем в силу вступает симплекс-метод.

14.

Задачи модели которых отвечают пяти составляющим свойствам, называются двойственными относительно друг друга.Из двух двойственных задач одну берут в качестве прямой задачи,другую ей двойственную.Но общепринято в качестве прямой задачи брать основную задачу линейного программирования.

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

Алгоритм составления двойственной задачи:

1.тип экстремума целевой функции меняется

2.каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи

3.свободные члены исходной задачи становятся коэффиц-и при переменных в целевой функции двойственной задачи

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