Лекции по методам оптимизации - файл n1.doc
Лекции по методам оптимизациискачать (606.2 kb.)
Доступные файлы (1):
| n1.doc | 1405kb. | 10.09.2008 11:56 | скачать |
- Смотрите также:
- Громницкий В.С. Лекции по методам оптимизации (Документ)
- Лекции по методам оптимизации (Лекция)
- Ответы по методам оптимизации (Шпаргалка)
- Лекции по методам оптимизации (Лекция)
- Григорьев В.А. Лекции по экспериментальным методам ядерной физики (Документ)
- Лекции - Методы оптимизации (Лекция)
- Лутманов С.В. Курс лекций по методам оптимизации (Документ)
- Измаилов А.Ф., Солодов М.В. Численные методы оптимизации (Документ)
- Ахназарова С.Л., Кафаров В.В. Методы оптимизации эксперимента в химической технологии (Документ)
- КП по методам оптимизации (Документ)
- Хворова Л.А., Жариков А.В. Сборник задач по методам оптимизации и вариационному исчислению (Документ)
- Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи (Документ)
n1.doc
Построение математической модели
Поиск оптимальных решений
Корректировка
модели
Реальная задача
Выдача рекомендаций
Схема исследования
Математическая модель
Математическая модель — описание решаемой задачи в математических терминах.
Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции
W = f(X,Y),
где X = (x1,…, xn) — управляемые переменные,
Y = (y1,…, ym) — неуправляемые переменные (исходные данные).
Связь между переменными X и исходными данными Y выражается с помощью ограничений
(X, Y) 0.
Виды моделей
детерминированные;
вероятностные;
игровые;
неполные (задачи в условиях неопределенности).
Исследованием детерминированных моделей занимается математическое программирование (МП).
Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).
Задача оптимизации
(
)Задача математического программирования
Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f(x) на множестве всех допустимых решений.
Задачи математического программирования
Транспортная задача
История математического программирования
Б.Т. Поляк, Институт проблем управления, Москва
История математического программирования в СССР: попытка анализа
История математического программирования
Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России
Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств
А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)
А.М. Ляпунов, 1857-1918, разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации
История математического программирования
5. Л.В. Канторович, 1912-1986, в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.
Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование.
С именем Канторовича Л.В.связаны следующие достижения:
Линейное программирование, 1939:
Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича.
Общие условия оптимальности, 1940
Техника функционального анализа, 1939-1948
История математического программирования
6. Г.Ш. Рубинштейн, ученик Канторовича Л.В., учитель д.т.н., проф. УГАТУ Мухачевой Э.А.
В 1961г. вышла книга Канторовича Л.В. и Рубинштейна Г.Ш., в которой давались математические формулировки задачи ЛП и приводились численные методы ее решения, были введены понятия двойственных переменных, которые назывались «объектно-обусловленными оценками».
7. В 50-е годы – интенсивные исследования в области ЛП.
Стали известны работы западных ученых: Дж. Данцига, Г.Куна, А. Таккера и др. по ЛП.
Выпущен первый учебник на русском языке по ЛП Юдиным Д.Б., Гольштейном Е.Г.
8. 60-е годы
Появилась общая теория двойственности для задач выпуклой оптимизации (Гольштейн Е.Г.), появились труды по стохастической оптимизации.
История математического программирования
Велись разработки ПО для реализации симплекс – метода для решения задачи ЛП (И.В. Романовский, А.А. Станевичус, и др, доцент УГАТУ А.П. Мартынов).
Появились численные методы решения специальных классов задач ЛП:
транспортная задача, методы декомпозиции, итеративные методы ЛП.
Практическое применение ЛП для социалистической экономики.
9. 70-80-е годы
Вводится новое понятие сложности оптимизационной задачи: установлены нижние границы для различных классов оптимизационных задач (Юдин Д.Б. и др.).
Было установлено: если метод имеет сложность, совпадающую с нижней границей, то он оптимален, т.е. не существует методов, которые решают все задачи класса быстрее (в отношении порядка).
Построен итеративный метод решения задачи ЛП, для которой была доказана полиномиальная сходимость (Хачиян Л.Г.)
Литература
1.Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во Ленинградский университет, 1939, 64с.
2. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. М.: Советское радио. 1964, 491с.
3. Карманов В.Г. Математическое программирование. М.: Наука, 1975, 272с.
4. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Изд-во «Наука», Сибирское отделение, 1987, 272с.
5. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984,174с.
6. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998, 217с.
7. Мухачева Э.А., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. Москва: Изд-во МАИ, 2004, 192с.
Главные научные центры по математическому программированию
Москва: МГУ, Центральный экономико-математический институт, Вычислительный центр
Киев: Институт кибернетики им. В.М. Глушкова
Новосибирск: Институт математики им. С.Л. Соболева Сибирского отделения РАН, Новосибирский государственный университет
Ленинград: Ленинградский государственный университет
Задача планирования производства
| ||||||||||||||
Методы оптимизации