Симплексный метод - раздел Программирование, Линейное программирование Выше Были Рассмотрены Основные Теоремы Лп. Из Них Следует, Что Если Злп Имеет...
Выше были рассмотрены основные теоремы ЛП. Из них следует, что если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной точке многогранника решений и совпадает хотя бы с одним из допустимых базисных решений системы ограничений. Там же мы рассмотрели, что путем решения любой ЗЛП является перебор конечного числа допустимых базисных решений системы ограничений и выбор среди них того, на котором функция цели принимает оптимальное значение. Геометрически надо перебрать все угловые точки многогранника решений. Трудно осуществить, т.к. для реальных задач число ДБР хоть и конечно, но м.б. велико.
Число перебираемых ДБР можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже») предыдущего по значению целевой функции.
Предположим, точка А – исходное ДБР (допустимое базисное решение). Из чертежа видно, что от А выгодно перейти к В, а потом к С.
Идея последовательного улучшения решения легла в основу универсального метода решения ЗЛП – симплексного метода.
Впервые был предложен амер. ученым Дж. Данцигом в 1949 г., хотя идеи метода были разработаны Л. В. Канторовичем в 1939 году.
Метод используется для компьютерных расчетов.
Для реализации метода необходимо освоить три основных элемента:
§ способ определения первоначального ДБР задачи;
§ правило перехода к лучшему (не худшему) решению;
А х а х a nxn b... при n является плоскостью а при n gt ее обобщением в n мерном...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Симплексный метод
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Линейное программирование
Оптимизационная задача была сформулирована в общем виде: найти переменные х1, х2, …, хп, удовлетворяющие системе неравенств (уравнений)
φi
Понятие экономико-математической модели
Существует много различных определений понятия «модель», отличающихся друг от друга. Но это понятие знакомо каждому: игрушечный корабль – модель корабля, фотоснимок пейзажа, географическая карта –
Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного образца в количестве А единиц. Требуется изготовить из него L разных комплектующих изделий в количествах, пропорциональных числам b1, b2, …
Свойства задач ЛП
Выше в лекции по ЛП было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой.
Будем рассматрив
Геометрический метод решения задач ЛП
Итак, выше было доказано, что множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи нахо
Особые случаи симплексного метода
Неединственность оптимального решения (альтернативный оптимум):
Решим симплексным методом задачу:
F=3x1 + 3х2 à max
Симплексные таблицы
Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум.
I. После введения добавочных перемен
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов