Кратко описание

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

математика

Описание

ПРОГРАМИРАНЕ НА МАТЕМАТИКА: ОПТИМИЗАЦИОННИ МОДЕЛИ

Бегоня Виториано [имейл защитен] www.mat.ucm.es/

Факултет CC. Математика, Университет Комплутенсе, 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 of 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). Оптимизацията се състои в избор на алтернатива, която е по-добра в известен смисъл от другите възможни алтернативи. Това е концепция, присъща на всички изследвания на операциите. Въпреки това, определени техники на оперативното изследване се събират под името оптимизация или математическо програмиране, в което се предлагат модели, които обикновено са съставени от тези три съставки: •

целева функция Количествената мярка за функционирането на системата трябва да бъде оптимизирана (максимизирана или минимизирана). Като пример за целеви функции можем да споменем: минимизиране на променливите разходи за експлоатация на електрическа система, максимизиране на нетните ползи от продажбата на определени продукти, минимизиране на квадрата на отклоненията по отношение на някои наблюдавани стойности, минимизирането на материала, използван за производството на продукт и др.

ОПТИМИЗАЦИОННИ МОДЕЛИ

променливи Представят решенията, които могат да бъдат взети, за да повлияят на стойността на целевата функция. От функционална гледна точка те могат да бъдат класифицирани в независими или основни или контролни променливи и зависими или спомагателни или състоятелни променливи, въпреки че математически всички те са еднакви. В случай на електрическа система, те ще бъдат производствените стойности на генериращите групи или потоците през линиите. В случай на продажба, количеството на всеки продукт, произведен и продаден. В случай на производство на продукт, неговите физически размери.

ограничения Те представляват съвкупността от отношения (изразени чрез уравнения и неравенства), които определени променливи са принудени да удовлетворяват. Например, максималната и минималната експлоатационна мощност на генерираща група, производственият капацитет на завода за различните продукти, размерите на суровината на продукта и т.н. Решаването на оптимизационен проблем се състои в намирането на стойността, която трябва

вземете променливите, за да оптимизирате целевата функция, отговаряща на набора от ограничения. Методите за оптимизация могат да бъдат класифицирани на: класически методи (които са алгоритмите, които обикновено се обясняват в книгите за оптимизация) и метахевристични методи (които изглежда са свързани с това, което се нарича изкуствен интелект и имитират прости явления, наблюдавани в природата). Сред първите са линейни, смесени целочислени линейни, нелинейни, стохастични, динамична оптимизация и др. които са обяснени в документа. Втората група включва еволюционни алгоритми (генетични, наред с други), симулиран метод на отгряване, евристични търсения (метод табу, произволно търсене, алчни и др.) Или системи с много агенти. Съвсем общо и приблизително може да се каже, че класическите методи търсят и гарантират локален оптимум, докато метахевристичните методи имат специфични механизми за постигане на глобален оптимум, въпреки че не гарантират неговия обхват.

Следващата таблица показва общите математически изрази на някои видове оптимизационни задачи в рамките на класическите методи. Проблемите се различават по естеството на включените функции (линейни или нелинейни) и на променливите (реални/непрекъснати или цели/дискретни). Линейно програмиране