Лекции по методам оптимизации - файл n1.doc

Лекции по методам оптимизации
скачать (606.2 kb.)
Доступные файлы (1):
n1.doc1405kb.10.09.2008 11:56скачать
Победи орков

Доступно в Google Play

n1.doc

  1   2   3   4   5   6   7   8
Методы оптимизации


Построение математической модели


Поиск оптимальных решений


Корректировка

модели


Реальная задача


Выдача рекомендаций


Схема исследования


Математическая модель

Математическая модель — описание решаемой задачи в математических терминах.

Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции

W = f(X,Y),

где X = (x1,…, xn) — управляемые переменные,

Y = (y1,…, ym) — неуправляемые переменные (исходные данные).

Связь между переменными X и исходными данными Y выражается с помощью ограничений

 (X, Y)  0.

Виды моделей



Исследованием детерминированных моделей занимается математическое программирование (МП).
Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).


Задача оптимизации


(

)

Задача математического программирования











Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f(x) на множестве всех допустимых решений.

Задачи математического программирования




Транспортная задача

История математического программирования
Б.Т. Поляк, Институт проблем управления, Москва

История математического программирования в СССР: попытка анализа


История математического программирования


  1. Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России

  2. Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств

  3. А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)

  4. А.М. Ляпунов, 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с.

Главные научные центры по математическому программированию
Москва: МГУ, Центральный экономико-математический институт, Вычислительный центр
Киев: Институт кибернетики им. В.М. Глушкова
Новосибирск: Институт математики им. С.Л. Соболева Сибирского отделения РАН, Новосибирский государственный университет
Ленинград: Ленинградский государственный университет

Задача планирования производства

Вид

сырья



Нормы расхода сырья (кг) на одно изделие



Общее количество сырья на складе (кг)

А

В



I

II

III


12

4

13


4

4

12


300

120

252

Прибыль от
реализации

одного

изделия (у.е.)


30


40



  1   2   3   4   5   6   7   8


Методы оптимизации
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации