Общая характеристика симплекс-метода и подготовка модели к решению. Главная особенность исследования допустимого варианта на оптимальность и нахождения оптимального варианта. Основной анализ неразрешимости модели и неограниченности функционала в задачи.
Симплексный метод решения задачи линейного программированияСреди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение). Оптимальность достигается последовательным улучшением этого решения за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса (мы будем работать с его модифицированным вариантом) для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования. Направление перехода от одного опорного решения к другому выбирается на основе критерия оптимальности (целевой функции) исходной задачи. симплекс метод оптимальный функционалТеорема о допустимости: в таблице будет находиться допустимый вариант решения задачи, если среди свободных членов не будет отрицательных (элемент на пересечение столбца свободных членов и строки Z при анализе во внимание не принимается). Если вариант допустим, то перейдем на второй этап и исследуем его на оптимальность. Если нет, то попытаемся получить допустимый вариант, выбрав разрешающий элемент по следующему правилу: - выбор разрешающей строки: среди отрицательных свободных членов (кроме строки Z), выбрать больший по абсолютной величине. выбор разрешающего столбца: взять симплексные отношения, поделив свободный член разрешающей строки на каждый ее коэффициент: Наименьшее положительное из симплексных отношений укажет на столбец. Теорема об оптимальности: в таблице будет находиться оптимальный вариант, если среди коэффициентов строки Z не будет отрицательных при Z®max и не будет положительных при Z®min (элемент на пересечение столбца свободных членов и строки Z при анализе во внимание не принимается).В этом случае невозможно найти допустимый вариант (в разрешающей строке симплекс-таблицы нет ни одного отрицательного элемента). С экономической точки зрения это значит, что ограничения модели являются взаимоисключающими, противоречащими друг другу требованиями. В этом случае в симплекс-таблице находится допустимый, но не оптимальный вариант и в разрешающем столбце нет ни одного положительного элемента. Такая ситуация возникает в случае возможности неоднозначного выбора разрешающего элемента при соблюдении всех правил решения (т.е. разрешающим элементом в равной степени может выступать не одно значение). В симплекс-таблице будет находиться вырожденный вариант, если среди свободных членов (кроме строки Z), появится ноль.
План
Содержание
1. Общая характеристика симплекс-метода и подготовка модели к решению
2. Алгоритм симплекс-метода
3. Особые случаи в симплекс-методе
1. Общая характеристика симплекс-метода и подготовка модели к решению
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
