Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Геометрическая интерпретация симплекс-метода
|
|
Из приведенных выше основных теорем линейного премирования следует, что если задача линейного премирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений.
На основании этого можно предложить достаточно простой метод решения задачи линейного программирования, который сводится к следующей принципиальной схеме:
· необходимо найти все опорные решения (точки многогранника), множество которых является конечным;
· вычислить для каждого из опорных решений значение целевой функции;
· сравнить значения целевой функции в каждом из опорных решений и выбрать оптимальное (максимальное или минимальное).
Теоретически данная схема приведет к нахождению оптимального решения, но практически ее осуществление связано с большими вычислительными трудностями.
Если же указанный перебор опорных решений производить направленно, т.е. на каждом из шагов улучшая (или, по крайней мере, не ухудшая) значение целевой функции, то число перебираемых опорных решений можно резко сократить, что в конечном итоге приводит к весьма существенному сокращению числа шагов при отыскании оптимума целевой функции. При использовании такой схемы, в отличие от первой, каждое последующее опорное решение выбирается таким образом, чтобы оно было лучше, (или, по крайней мере, не хуже) предыдущего, именно поэтому на каждом из шагов значение целевой функции улучшается (или, по крайней мере, не ухудшается).
Фундаментом универсального метода решения задач иного программирования, который называется симплекс-методом, является метод направленного перебора. (По латыни симплекс означает — простой, что в данном случае интерпретируется как простой выпуклый многогранник.)
Геометрическая интерпретация симплекс-метода состоит в последовательном переходе от одной вершины многогранника к другой (от первоначально выбранной вершины к одной из соседних вершин, а именно к той, у которой линейная функция принимает лучшее или, по крайней мере, не худшее значение). Этот процесс происходит до тех пор, пока не будет найдено оптимальное решение — вершина, где достигается оптимальное значение функции (если задача имеет конечный оптимум).
Идея симплекс-метода разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данциг в 1949 г. разработал симплекс-метод, позволяющий решить любую задачу линейного программирования.
В настоящее время на основе этого метода разработан пакет программ, с применением которого решаются задачи линейного программирования.
Вопросы для самоконтроля:
1.Основные элементы линейной алгебры. Их роль при построении модели.
2.Анализ моделей на чувствительность. Виды моделей.
Рекомендуемая литература:
1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.
2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996
Date: 2015-07-10; view: 1279; Нарушение авторских прав