043_Методы оптимизации

Description
http://stackoverflow.com/questions/3956950/c-c-implementation-of-simplex-method

Please download to get full document.

View again

of 31
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Documents

Publish on:

Views: 9 | Pages: 31

Extension: PDF | Download: 0

Share
Transcript
  Содержание  1 Тема 1   Введение. Оптимизация и исследование операций  2 2 Тема  2 Классические методы оптимизации  4 2.1. Функции одной переменной  4 2.2. Функции многих переменных  5 2.3. Метод Лагранжа для оптимизации с ограничениями в виде равенств  7 2.4. Оптимизации с ограничениями в виде неравенств   (графический метод)  9 2.4.1. Оптимизации с ограничениями в виде неравенств (условия Куна - Таккера)  9 МРК №1  13 3 Тема 3 Задачи линейного планирования  14 3.1. Построение математических моделей, приводящих к задачам ЛП  14 3.1.1. Оптимальный план выпуска изделий  14 3.1.2. Задача о наилучшей диете  16 3.2. Графический метод решения задачи ЛП  3.3. Симплекс - метод  3.4. Транспортная   задача  20 3.4.1. Закрытая транспортная задача  20 3.4.2. Метод   потенциалов для решения закрытой транспортной задачи  21 3.4.3. Открытая транспортная задача   МРК №2  4 Тема 4    Численные методы нелинейной оптимизации  4.1. Метод прямого перебора  4.2. Метод Ньютона  4.3. Методы нулевого порядка  4.4. Метод градиентов  4.5. Методы нелинейного программирования  5 Тема 5   Дополнительные разделы методов оптимизации  6 Тема 6   Вариационное исчисление и оптимальное управление      Лекция 1. Введение. Оптимизация и исследование операций   В самом широком смысле под оптимизацией подразумевается поиск наилучшего из возможного в данной ситуации. Из этого определения следует , что оптимизация реальна только тогда, когда есть возможность выбора поиска лучшего варианта разрешения проблемы, порождаемой  рассматриваемой ситуацией. Если такого выбора нет, об оптимизации говорить не имеет смысла.   По своей природе   человек всегда стремится достичь в своей жизни наилучшего: высокого заработка, правильного расхода денег, наименьшего  расхода энергии и т.п. В поисках воплощения в жизнь своих целей, для анализа вариантов люди привлекали математику. В результате появились математические модели реального мира, в которых на языке математики описывались те или иные ситуации. Общим для этих моделей было то, что в них поиск наилучших вариантов сводился к поиску наилучшего(экстремального) значения функции. Такие модели получили название экстремальных задач, а функции –    оптимизируемых.   Первые экстремальные задачи были сформулированы античной наукой. Они касались максимизации площадей и объемов. Так, в легенде о финикийской царевне Дидоне, основавшей около 825 года до н.э. город Карфаген, говорится, что царевна попросила у местного князя столько земли, сколько может покрыть бычьей шкурой. Разрезав шкуру на тонкие полоски и связав их   в один длинный ремень, Дидона окружила им максимальную площадь земли и основала на ней крепость Бирса(шкура). Таким образом в этой легенде речь идет о задаче максимизации площади S , охватывемой кривой заданной длины L (длина ремня сшитого из полосок бычьей шкуры).   Известна также экстремальная задача Эвклида: в данный треугольник вписать параллелограмм наибольшей площади.   В XVI появляются первые экстремальные задачи алгебраического содержания. В частности, широко известной стала задача итальянского математика Н.Тартальи:разделить число 8 на два числа так, чтобы произведение этих чисел на их разность было максимальным. Решение задачи сводится к поиску максимального значения кубического трехчлена у=х(8 - х)(2х - 8) на открытом интервале 0< x <8. В связи с тем, что в те времена дифференциальное исчисление не было известно, задача, по - видимому,  решалась приближенно, методом последовательного деления отрезка (0,8) пополам.   Только после открытий известных математиков П.Ферма, И.Ньютона,Г.Лейбница постепенно начал формироваться общий подход к  решению экстремальных задач, использующий дифференцирование оптимизируемых функций.    Формулировка в конце XVII века И.Бернулли задачи о брахистохроне положила начало изучению нового класса экстремальных задач –    вариационному исчислению. В вариационном исчислении рассматривается поиск экстремумов функционалов, заданных на множестве непрерывных функций. Основной вклад в решение таких задач, функционалы которых заданы на ограниченных множествах (задач на условный экстремум) внес французский математик Ж.Лагранж, предложивший знаменитое правило множителей сначала для задач вариационного исчисления (1788 г.), а затем для аналитических функций(1797 г.). Это правило широко используется и в настоящее время, как в практическом аспекте, так и теоретических исследованиях. В частности на него опиралась группа советских математиков, возглавляемая Л.Понтрягиным, при разработке математической теории оптимального управления   и известного «принципа максимума Понтрягина».   До начала 40 - х годов ХХ века экстремальные задачи формулировались преимущественно в области математики, физики, техники. Однако в конце 30- х годов появляются задачи из совершенно новой области –    экономики, науки о рациональном ведении хозяйства в собственном деле, фирме, отрасли, государстве. Одна из первых постановок экстремальных задач экономического содержания принадлежит советскому математику Л.Канторовичу, впоследствии лауреату Нобелевской премии в области экономики.   Она изложена в его книге «Математические методы организации и планирования производства» (1939 г.).   Формулируемые   задачи представляли собой совершенно новый класс экстремальных задач на условный экстремум, не поддающийся решению методом Лагранжа и, таким образом, требующие совершенно новых подходов к поиску наилучших значений оптимизируемых функций. В течение 50 -70- х годов прошлого века экономистами - прикладниками, математиками и инженерами были сформулированы и решены тысячи экстремальных задач из области управления предприятиями, отраслью, дорожно - транспортными, энергетическими, коммуникационными и вычислительными сетями.   Созданы универсальные методы решения задач линейного, нелинейного и дискретного программирования. Для решения задач динамического характера, в которых неизвестные переменные являются функциями времени, предложены и развиты два общих подхода –    принцип максимума Л.Понтрягина и динамическое программирование Р.Беллмана. При этом общим, что объединяло новые задачи, было то, что оптимизация в них сводилась к наилучшему распределению и использованию различных  ресурсов: материальных, трудовых, финансовых, временных.   Исследования и разработки в указанной области достигли такого уровня, что постепенно оформились в самостоятельную дисциплину, получившую название «исследование операций». По современным воззрениям исследование операций –    это наука о методах оптимального  управления организационными системами, широко используя математику для обоснования рациональных управленческих решений.   При всем многообразии исследование операций как метод совершенствования управления включает следующие этапы:  1)   содержательную постановку задачи   и выбор критерия оптимизации ; 2)   ее математическую формулировку;  3)   определение методов решения математической задачи;  4)    разработку алгоритма ее решения;  5)   экспериментальное исследование на реальных данных;  6)   внедрение найденного управления в жизнь.   Каждый из этапов важен в процессе решения оптимизационной задачи. Так, если неправильно поставлена задача или выбран неправильный критерий оптимизации, то как бы точно не была построена математическая модель, какой   бы эффективный метод или алгоритм не использовался бы,  решение будет неверным. В то же самое время при правильно поставленной задаче, выбранном критерии оптимизации, адекватно построенной математической модели, если использован не тот алгоритм решения, то    результаты будут неточными.   Исследование математических моделей оптимизации может быть произведено с использованием различных методов. Применение того или иного метода зависит от вида математической модели, от ее размерности и других факторов. Под математической моделью понимается совокупность соотношений (например, формул, уравнений, неравенств, логических условий, операторов и т.д.), описывающих рассматриваемую задачу, ограничения, критерий оптимизации (целевую функцию). В практике  решения задач оптимизации используются различные методы исследования математической модели. При этом ни один из них не является универсальным с точки зрения применимости к решению той или иной задачи оптимизации.   Выделяют следующие основные методы исследования математических моделей оптимизации: 1)аналитический4 2) численное моделирование 3) методы случайного поиска.   Аналитический метод, как правило, дает наглядную картину процесса и характеризующих его параметров. Однако, построение математической модели, удобной для аналитического моделирования –    трудная задача. Искусство исследователя как раз и состоит в том, чтобы в процессе построения математической модели обеспечить возможность ее исследования аналитическими методами (метод дифференциального исчисления, метод множителей Лагранжа и т.д.). Если аналитическое исследование затруднительно, то используют другие способы.   Исследование с помощью численных методов и ЭВМ менее наглядно по сравнению с аналитическим, но класс моделей, пригодных для исследования численными методами, значительно шире. Результаты исследования   (таблицы, графики и т.д.) менее компактны по сравнению с
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks