Короткий опис

1 МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ: МОДЕЛІ ОПТИМІЗАЦІЇ Begoña Vtorao Facultad CC. Математика.

програмування

Опис

ПРОГРАМУВАННЯ МАТЕМАТИКИ: МОДЕЛІ ОПТИМІЗАЦІЇ

Бегонья Віторіано [захищено електронною поштою] www.mat.ucm.es/

Факультет КК. Математика, Університет Комплутенсе, Pza. Ciencias 3, 28040 Мадрид http://www.mat.ucm.es

ОПТИМІЗАЦІЯ. 1 I.1. ОПЕРАЦІЙНЕ ДОСЛІДЖЕННЯ ТА ОПТИМІЗАЦІЯ. 1 I.2. ЛІТЕРАТУРА. 8

МАТЕМАТИЧНІ МОДЕЛІ ПРОГРАМУВАННЯ. 9

II.1. МОДЕЛЬ І МОДЕЛЮВАННЯ. 9 II.2. ЕТАПИ РОЗРОБКИ МОДЕЛІ. 10 II.3. ЛІТЕРАТУРА. 14 III.

ФОРМУЛЮВАННЯ ПРОБЛЕМ ОПТИМІЗАЦІЇ. п’ятнадцять

III.1. ХАРАКТЕРИСТИЧНІ МОДЕЛІ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ. 15 III.1.1. Проблема дієти. 15 III.1.2. Проблема транспортування. 18 III.1.3. Проблема перевалки. 20 III.1.4. Проблема призначення. 22 III.1.5. Проблема рюкзака (рюкзак). 23 III.1.6. Проблема покриття (комплект покриття). 23 III.1.7. Встановити проблему упаковки. 26 III.1.8. Проблема розділу (набір розділів). 26 III.1.9. Подорожній продавець Проблема TSP. 27 III.1.10. Проблема з фіксованою вартістю. 28 III.1.11. Моделювання обмежень за допомогою двійкових змінних. 29 III.1.11.1. Моделювання диз'юнкцій. 29 III.1.11.2. Моделювання логічних наслідків. 31 III.1.11.3. Моделювання умовних та/або складених пропозицій. 37 III.1.11.4. Моделювання товару за допомогою двійкових змінних. 42

III.1.12. Додаток: Модель присвоєння теплової групи. 43 III.1.13. Проблеми виробництва з еластичністю цін та/або витрат. 46 III.1.14. Проблема транспортування зі знижками за обсяг. 47 III.1.15. Вибір інвестиційного портфеля. 49 III.1.16. Проблеми з системою електроенергетики. 50 18.02.2010

III.2. ЛІТЕРАТУРА. 50 III.3. БІБЛІОТЕКА ПРОБЛЕМ. 51 III.4. РЕЗУЛЬТАТИ БІБЛІОТЕКИ ПРОБЛЕМ. 69 IV.

КОДУВАННЯ ПРОБЛЕМИ ОПТИМІЗАЦІЇ. 89

IV.1. МОДЕЛЮВАННЯ МОВ. 89 IV.1.1. Моделювання мов. 89 IV.1.2. Мови алгебраїчного моделювання. 92 IV.1.3. Список літератури. 94 IV.2. ДОСЛІДЖЕННЯ ВИПАДКІВ З EXCEL. 95 IV.2.1. Приклад справи. 95 IV.2.2. Випадок 1: Розподіл дизеля. 101 IV.2.3. Випадок 2: Водії метро. 102 IV.2.4. Випадок 3: Виробництво. 103 IV.3. МОДЕЛЮВАННЯ В ІГРАХ. 105 IV.3.1. Приклад транспорту. 105 IV.3.2. Приклад планування виробництва. 110 IV.3.3. Приклад послідовності замовлення на виконання робіт. 112 IV.3.4. Приклад мандрівного продавця. 113 IV.3.5. Приклад присвоєння теплових груп. 116 IV.3.6. Приклад оптимального потоку навантаження. 120 IV.4. ПРОГРАМУВАННЯ СТИЛЬНИХ ЕЛЕМЕНТІВ. 129 IV.4.1. Загальні. 129 IV.4.2. Специфіка GAMS. 140 IV.4.3. Список літератури. 148

МОДЕЛІ ОПТИМІЗАЦІЇ

I.1. Оперативні дослідження та оптимізація "В останнє десятиліття нові досягнення в алгоритмах були настільки ж важливими, як і вражаючі досягнення в галузі комп'ютерних технологій" Джордж Л. Немгаузер (1994).

«Удосконалення технологій в алгоритмах, мовах моделювання, програмному та апаратному забезпеченні зробило методологію доступною, простою у використанні та швидкою. Отже, настала доба оптимізації »Джордж Л. Немгаузер (1994).

Іспанською мовою переклад цього слова простий, але незвично використовувати його для назви

цей метод лінійної оптимізації. два

На веб-сайті http://www.e-optimization.com/directory/trailblazers/dantzig/ ви можете знайти короткий зміст

його досягнення, а також інтерв’ю на різні теми, включаючи відеозображення.

МОДЕЛІ ОПТИМІЗАЦІЇ

більше перспектив ділового адміністрування. [Сарабія, 1996] забезпечує достатню теоретичну базу, щоб мати змогу вирішити сукупність проблем, пов'язаних з порядку денним оперативних досліджень. До провідних журналів, що займаються питаннями оптимізації, належать: Інтерфейси, Дослідження операцій, Наука про управління, Європейський журнал операційних досліджень, Математика досліджень операцій, OR/MS Today, Математичне програмування, INFORMS Journal on Computing, Journal of Operational Research Society, Omega, Journal of Теорія оптимізації та додатки,

енциклопедія досліджень операцій, яка може служити початковою консультацією та посиланням на певну тему, див. [Gass, 2001]. Крім того, інформацію про теми оперативних досліджень можна знайти за адресами Іспанського товариства статистики та досліджень операцій (SEIO) (www.seio.es) Асоціації європейських операційних дослідницьких товариств (EURO) (www.euroonline). org), Міжнародної федерації дослідницьких операційних товариств (IFORS) (www.ifors.org) та Інституту досліджень операцій та наук про менеджмент (INFORMS) (www.informs.org). Оптимізація полягає у виборі альтернативи, яка в якомусь сенсі краща за інші можливі альтернативи. Це концепція, властива всім операційним дослідженням. Однак певні методики, типові для досліджень операцій, зібрані під назвою оптимізації або математичного програмування, в яких пропонуються моделі, які, як правило, складаються з цих трьох інгредієнтів: •

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

МОДЕЛІ ОПТИМІЗАЦІЇ

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

обмеження Вони представляють сукупність відносин (виражених за допомогою рівнянь та нерівностей), яким певні змінні змушені задовольняти. Наприклад, максимальна та мінімальна робоча потужність генераційної групи, виробничі потужності заводу для різних видів продукції, розміри сировини продукту тощо. Розв’язання задачі оптимізації полягає у пошуку вартості, яка повинна

візьмемо змінні для оптимізації цільової функції, що задовольняє набір обмежень. Методи оптимізації можна класифікувати на класичні методи (це алгоритми, які зазвичай пояснюються в книгах з оптимізації) та метаевристичні методи (які, як видається, пов’язані з тим, що називали штучним інтелектом, і імітують прості явища, що спостерігаються в природі). Серед перших - лінійна, змішана ціла лінійна, нелінійна, стохастична, динамічна оптимізація тощо. що пояснюються в документі. До другої групи належать еволюційні алгоритми (генетичні, серед інших), імітований метод відпалу, евристичні пошуки (метод табу, випадковий пошук, жадібні тощо) або багатоагентні системи. Дуже загальним та наближеним чином можна сказати, що класичні методи шукають і гарантують локальний оптимум, тоді як метаевристичні методи мають конкретні механізми досягнення загального оптимуму, хоча вони не гарантують його сфери застосування.

У наступній таблиці наведено загальні математичні вирази деяких типів задач оптимізації в рамках класичних методів. Проблеми розрізняються за характером задіяних функцій (лінійних чи нелінійних) та змінних (реальних/безперервних або цілих/дискретних). Лінійне програмування