Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Оптимізація (математика)



План:


Введення

Завданням оптимізації в математики, інформатики і дослідженні операцій називається завдання знаходження екстремуму ( мінімуму або максимуму) цільової функції в деякій області конечномерного векторного простору, обмеженої набором лінійних та / або нелінійних рівностей та / або нерівностей.

Математичне програмування - дисципліна, що вивчає теорію і методи розв'язання задачі оптимізації.


1. Постановка завдання оптимізації

В процесі проектування ставиться зазвичай завдання визначення найкращих, в деякому сенсі, структури чи значення параметрів об'єктів. Така задача називається оптимізаційної. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричної. Завдання вибору оптимальної структури є структурною оптимізацією.

Стандартна математична задача оптимізації формулюється таким чином. Серед елементів χ, що утворюють безлічі Χ, знайти такий елемент χ *, який доставляє мінімальне значення f (χ *) заданої функції f (χ). Для того, щоб коректно поставити завдання оптимізації необхідно задати:

  1. Допустиме безліч - безліч \ Mathbb {X} = \ {\ vec {x} | \; g_i (\ vec {x}) \ leq 0, \; i = 1, \ ldots, m \} \ subset \ mathbb {R} ^ n ;
  2. Цільову функцію - відображення f: \; \ mathbb {X} \ to \ mathbb {R} ;
  3. Критерій пошуку (max або min).

Тоді вирішити завдання f (x) \ to \ min_ {\ vec {x} \ in \ mathrm {X}} означає одне з:

  1. Показати, що \ Mathbb {X} = \ varnothing .
  2. Показати, що цільова функція f (\ vec {x}) не обмежена знизу.
  3. Знайти \ Vec {x} ^ * \ in \ mathbb {X}: \; f (\ vec {x }^*)= \ min_ {\ vec {x} \ in \ mathbb {X}} f (\ vec {x }) .
  4. Якщо \ Nexists \ vec {x} ^ * , То знайти \ Inf_ {\ vec {x} \ in \ mathbb {X}} f (\ vec {x}) .

Якщо минимизируемого функція не є опуклою, то часто обмежуються пошуком локальних мінімумів і максимумів: точок x 0 таких, що всюди в деякій їх околиці f (x) \ ge f (x_0) для мінімуму та f (x) \ le f (x_0) для максимуму.

Якщо допустимий безліч \ Mathbb {X} = \ mathbb {R} ^ n , То таке завдання називається завданням безумовної оптимізації, в іншому випадку - завданням умовної оптимізації.


2. Класифікація методів оптимізації

Методи оптимізації класифікують відповідно до завдань оптимізації:

  • Локальні методи: сходяться до якого-небудь локальному екстремуму цільової функції. У разі унімодальне цільової функції, цей екстремум єдиний, і буде глобальним максимумом / мінімумом.
  • Глобальні методи: мають справу з многоекстремальнимі цільовими функціями. При глобальному пошуку основним завданням є виявлення тенденцій глобального поведінки цільової функції.

Існуючі в даний час методи пошуку можна розбити на три великі групи:

  1. детерміновані;
  2. випадкові (стохастичні);
  3. комбіновані.

За критерієм розмірності допустимого безлічі, методи оптимізації ділять на методи одновимірної оптимізації та методи багатовимірної оптимізації.

По виду цільової функції і допустимого безлічі, завдання оптимізації та методи їх вирішення можна розділити на наступні класи:

  • Завдання оптимізації, в яких цільова функція f (\ vec {x}) і обмеження g_i (\ vec {x}), \; i = 1, \ ldots, m є лінійними функціями, вирішуються так званими методами лінійного програмування.
  • В іншому випадку мають справу з завданням нелінійного програмування і застосовують відповідні методи. У свою чергу з них виділяють дві приватні задачі:

За вимогами до гладкості і наявності у цільової функції приватних похідних, їх також можна розділити на:

  • прямі методи, що вимагають тільки обчислень цільової функції в точках наближень;
  • методи першого порядку : вимагають обчислення перших приватних похідних функції;
  • методи другого порядку: вимагають обчислення другий приватний похідних, тобто гессіана цільової функції.

Крім того, оптимізаційні методи діляться на наступні групи:

Залежно від природи множини X завдання математичного програмування класифікуються як:

Крім того, розділами математичного програмування є параметричне програмування, динамічне програмування і стохастичне програмування. Математичне програмування використовується при вирішенні оптимізаційних задач дослідження операцій.

Спосіб знаходження екстремуму повністю визначається класом завдання. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:

  • Визначення меж системи оптимізації
    • Відкидаємо ті зв'язки об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких рішення спрощується
  • Вибір керованих змінних
    • "Заморожує" значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з області допустимих рішень (керовані змінні)
  • Визначення обмежень на керовані змінні
    • ... (Рівності та \ або нерівності)
  • Вибір числового критерію оптимізації
    • Створюємо цільову функцію

3. Історія

Завдання лінійного програмування були першими детально вивченими завданнями пошуку екстремуму функцій при наявності обмежень типу нерівностей. В 1820 р. Ж. Фур'є і потім в 1947 р. Дж. Данциг запропонував метод спрямованого перебору суміжних вершин в напрямку зростання цільової функції - симплекс-метод, що став основним при вирішенні завдань лінійного програмування.

Присутність у назві дисципліни терміна "програмування" пояснюється тим, що перші дослідження і перші програми лінійних оптимізаційних задач були в сфері економіки, так як в англійській мові слово "programming" означає планування, складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, який існує між математичною постановкою завдання і її економічної інтерпретацією (вивчення оптимальної економічної програми). Термін " лінійне програмування "був запропонований Дж. Данцигом в 1949 р. для вивчення теоретичних та алгоритмічних задач, пов'язаних з оптимізацією лінійних функцій при лінійних обмеженнях. Тому найменування "Математичне програмування" пов'язано з тим, що метою вирішення завдань є вибір оптимальної програми дій.

Виділення класу екстремальних задач, визначених лінійним функціоналом на безлічі, що задається лінійними обмеженнями, слід віднести до 30-х років ХХ століття. Одними з перших, що досліджували в загальній формі завдання лінійного програмування, були: Джон фон Нейман, знаменитий математик і фізик, що довів основну теорему про матричних іграх і вивчив економічну модель, що носить його ім'я; радянський академік, лауреат Нобелівської премії (1975 р.) Л. В. Канторович, сформулювавши ряд завдань лінійного програмування і запропонував (1939 р.) метод їх вирішення (метод дозволяють множників), незначно відрізняється від симплекс-метода.

В 1931 р. угорський математик Б. Егерварі розглянув математичну постановку і вирішив задачу лінійного програмування, що має назву "проблема вибору", метод вирішення отримав назву " угорського методу ".

Л. В. Канторовичем спільно з М. К. Гавуріним в 1949 г розроблений метод потенціалів, який застосовується при вирішенні транспортних завдань. У наступних роботах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лур 'є, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдіна, Є. Г. Гольштейну та інших математиків та економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем. Методів лінійного програмування присвячено багато робіт зарубіжних вчених. В 1941 р. Ф. Л. Хітчкок поставив транспортну задачу. Основний метод розв'язання задач лінійного програмування - симплекс-метод - був опублікований в 1949 г Дж. Данцигом. Подальший розвиток методи лінійного і нелінійного програмування отримали в роботах Г. Куна (англ.), А. Таккера (англ.), Гассе (Gass SI), Чарнеса (Charnes A.), Біла (Beale EM) і ін

Одночасно з розвитком лінійного програмування велика увага приділялася завданням нелінійного програмування, в яких або цільова функція, або обмеження, або те й інше нелінійні. У 1951 р була опублікована робота Куна і Таккера, в якій наведені необхідні і достатні умови оптимальності для вирішення задач нелінійного програмування. Ця робота стала основою для подальших досліджень у цій області.

Починаючи з 1955 г опубліковано багато робіт, присвячених квадратическому програмування (роботи Біла, Е. Баранкіна (Barankin E.) і Дорфмана (Dorfman R.), Франка (Frank M.) і Вольфа (Wolfe P.), Г. Марковіца та ін.) У роботах Денніса (Dennis JB), Розена (Rosen JB) і Зонтендейка (Zontendijk G.) розроблені градієнтні методи вирішення задач нелінійного програмування.

В даний час для ефективного застосування методів математичного програмування і рішення задач на комп'ютерах розроблені алгебраїчні мови моделювання, представниками якими є AMPL і LINGO.


Література

  1. Абакаров А.Ш., Сушков Ю.А. Статистичне дослідження одного алгоритму глобальної оптимізації - Праці ФОРА, 2004.
  2. Акулич І. Л. Математичне програмування в прикладах і завданнях: Учеб. посібник для студентів економ. Пец. вузів - М .: Вища школа, 1986.
  3. Гілл Ф., Мюррей У., Райт М. Практична оптимізація. Пер. з англ - М .: Світ, 1985.
  4. Жіглявскій А.А., Жілінкас А. Г. Методи пошуку глобального екстремуму - М .: Наука, Физматлит, 1991.
  5. Карманов В. Г. Математичне програмування = Математичне програмування - Изд-во фіз.-мат. літератури, 2004.
  6. Корн Г., Корн Т. Довідник з математики для науковців та інженерів - М .: Наука, 1970. - С. 575-576.
  7. Коршунов Ю.М., Коршунов Ю. М. Математичні основи кібернетики - М .: Вища школа, 1972.
  8. Максимов Ю.А., Філліповская Є. А. Алгоритми рішення задач нелінійного програмування - М .: МІФІ, 1982.
  9. Максимов Ю. А. Алгоритми лінійного та дискретного програмування - М .: МІФІ, 1980.
  10. Плотніков А. Д. Математичне програмування = експрес-курс - 2006. - С. 171. - ISBN 985-475-186-4.
  11. Растригина Л. А. Статистичні методи пошуку - М ., 1968.
  12. Хемді А. Таха Введення в дослідження операцій = Operations Research: An Introduction - 8 видавництво .. - М .: "Вільямс", 2007. - С. 912. - ISBN 0-13-032374-8.
Методи оптимізації
Одномірні Метод золотого перерізу Дихотомія Метод парабол Перебір по сітці Метод Фібоначчі Трійчастий пошук
Прямі методи Метод Гаусса Метод Нелдера - Міда Метод Хука - Дживса Метод конфігурацій Метод Розенброка
Першого порядку Градієнтний спуск Метод Зойтендейка Покоординатного спуск Метод спряжених градієнтів Квазіньютоновскіе методи
Другого порядку Метод Ньютона Метод Ньютона - Рафсона
Стохастичні Метод Монте-Карло Імітація відпалу Еволюційні алгоритми Генетичні алгоритми Диференціальна еволюція Мурашиний алгоритм Метод рою частинок
Методи лінійного
програмування
Симплекс-метод Алгоритм Гоморі Метод еліпсоїдів Метод потенціалів
Методи нелінійного
програмування
Послідовне квадратичне програмування

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Оптимізація
Пошукова оптимізація
Комбінаторна оптимізація
Оптимізація (інформатика)
Оптимізація запитів СУБД
Метод Гаусса (оптимізація)
Локальний пошук (оптимізація)
G2 (математика)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru