КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Пример. Перейти к исследованию новой симплексной таблицы (новая итерация)
Перейти к исследованию новой симплексной таблицы (новая итерация). Преобразование симплексной таблицы. Проверка условия неограниченности решения задачи ЛП и нахождение ведущей строки (ведущего элемента). Проверка оптимальности или нахождение ведущего столбца. § Если все коэффициенты в строке z-уравнения при небазисных переменных неотрицательны (коэффициенты в z-уравнении), то текущее базисное решение является оптимальным (условие оптимальности). § В противном случае на следующей итерации в число базисных переменных вводим небазисную переменную которой соответствует наименьший отрицательный коэффициент в строке , т.е. номер определяется по правилу: . Столбец под номером s называется ведущим столбцом симплексной таблицы.
§ Если в ведущем столбце симплексной таблицы s нет положительных коэффициентов, то значение задачи ЛП неограниченно (нет оптимального решения) — условие неразрешимости; § В противном случае (т.е. в ведущем столбце имеются положительные элементы) в качестве базисной переменной, которая исключается из числа базисных, выбирается та переменная , для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально, т.е. . Строка под номером r называется ведущей строкой, а элемент ars>0 –ведущим элементом (условие допустимости). § Используя эквивалентные преобразования таблицы (процедуру Гаусса) пересчитываем таблицу так, чтобы ведущий элемент новой симплекс-таблицы стал равным 1, а все остальные элементы ведущего столбца – равными 0. Обозначим верхним индексом 1 элементы новой симплексной таблицы. Тогда формулы пересчета коэффициентов примут вид:
Признак бесконечности множества допустимых решений. Если в -строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая небазисной переменной, то задача линейного программирования имеет бесконечное множество оптимальных планов. Признак неограниченности целевой функции. Если в -строке симплексной таблицы задачи линейного программирования на максимум есть отрицательная оценка и в столбце, соответствующем этой оценке, нет ни одного положительного элемента, то целевая функция на множестве допустимых решений задачи не ограничена сверху.
Таким образом, последовательность вычислений (итераций) следующая: Шаг 0. Находится начальное допустимое решение. Шаг 1. На основе условия оптимальности определяется переменная, вводимая в базис. Если таких переменных нет, то вычисления заканчиваются. Шаг 2. На основе условия допустимости выбирается исключаемая переменная. Шаг 3. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 1.
Итерации симплекс-метода для задачи Reddy Mikks (ведущие строки и столбцы выделены цветом)
Поскольку -строка не содержит отрицательных коэффициентов, соответствующих небазисным переменным , то полученное решение оптимально.
Обратите внимание, что последовательность базисных решений состоит в том, что итерационный процесс симплекс-метода начался в угловой точке А, затем, пройдя через точку В, закончился в крайней точке С — точке оптимума. Итерации соответствуют смежным крайним точкам границы области допустимых решений.
Ответ: ТЕМА 4. Двойственность в задачах линейного программирования
Дата добавления: 2014-12-29; Просмотров: 755; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |