Математическа оптимизация – Уикипедия

Граф на параболоид, зададен чрез f(x, y) = −(x² + y²) + 4. Глобалният максимум е при координати (0, 0, 4), които са индикирани с червена точка.

Математическа оптимизация, позната също и като математическото оптимиране или математическо програмиране в приложната математика, компютърната наука и мениджмънт изследванията, е селекцията на най-добрия елемент (според определен критерий) от някаква наличност от валидни алтернативи,^[1] изучаваща задачата за намиране на оптимална стойност (минимум или максимум) на функция при наложени ограничения.

Формално, екстремална задача е задачата за намиране на екстремум на функция

$f:X\rightarrow \mathrm {R} ^{1},X\subset \mathrm {R} ^{n}$ .

Функцията $f\,$ наричаме целева функция. Множеството от допустими решения $X\,$ , зададено чрез система неравенства и/или уравнения, наричаме система от ограничения.

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

Математическото оптимиране, с помощта на изчислителната техника, прави възможно решаването на голям брой икономически задачи и задачи от изключително значение за практиката. В това число Задача за търговския пътник, задача за назначенията, задача на вариационното смятане, задача за диетата и др.

Линейно оптимиране[редактиране | редактиране на кода]

Ако целевата функция и ограниченията са линейни, то имаме случай на линейно оптимиране – един от най-важните раздели на математическото оптимирането.

Задачата на линейното оптимиране винаги може да се запише в канонична форма:

${\begin{aligned}\min &z=c^{T}x\\&Ax=b,\\&x\geq 0.\end{aligned}}$

$A\ {\text{e}}\ n\times m$ матрица на ограниченията, $b\in \mathrm {R} ^{m}$ е вектор на ограниенията, $c\in \mathrm {R} ^{n}$ е вектор на целевата функция и $x\in \mathrm {R} ^{n}$ вектор на променливите.

Основен метод за решаването на екстремалната задача в линейното оптимиране е симплекс метода (или симплекс алгоритъма) и неговите разновидности: двойствен симплекс метод, мрежов симплекс метод, метод на амебата (или метод на Нелдър-Мийд) и др. Освен симплекс метод, съществуват и други (, в някои случаи дори по-бързи) методи като алгоритъм на Кармаркар и елипсоидаления метод.

История[редактиране | редактиране на кода]

Оптимирането води началото си от трудовете на Фурие от 1826, в които той изследва различни класове от неравенства. Канторович дава алгоритъм за решаване на конкретни оптимизационни задачи през 1939 и показва тяхното изключително значение за практиката. През 1975, за приноса си в теорията за оптималното разпределение на ресурси, той получава нобелова награда за икономика, ставайки един от малкото математици нобелови лауреати.

През 1947 Джордж Данциг, който по това време работи за военновъздушните сили на САЩ, разработва симплекс метода, като метод за решаване на задачи възникващи при планирането на въздушни операции. Данциг публикува метода през 1951 и с това слага началото на бурно развитие на дисциплината, продължаващо и до днес.

Източници[редактиране | редактиране на кода]

↑ ((en)) "The Nature of Mathematical Programming Архив на оригинала от 2014-03-05 в Wayback Machine.", Mathematical Programming Glossary, INFORMS Computing Society.

Тази страница частично или изцяло представлява превод на страницата Mathematical optimization в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

Допълнителна литература[редактиране | редактиране на кода]

Бонев, К., Лалова, Н., Иванов, А. Математическо моделиране, Изд. „Георги Бакалов“, Варна, 1989
Гольштейн, Е.Г., Юдин, Д.Б. Нови направления в линейното програмиране, Варна, 1972.
Dantzig, G. Linear Programming and Extensions, 1965, RAND Corp.
Дончев, А. Лекции по математическо оптимиране, София, 1978.
Зуховицки, С.И., Авдеева, Л.И. Линейно и изпъкнало програмиране, София, 1971, Наука и изкуство.
Канторович, Л.В. Математические метод в организации и планировании производства, Ленинград, 1939, Лен. гос. университет.
Кендеров, П., Христов, Г., Дончев, А. Математическо оптимиране, София, Унив. издателство „Св. Климент Охридски“, 1989.
Кънчев, К., Пенкова, Н., Бонев, К. Линейна алгебра и математическо програмиране, Варна, 1971.
Лалова, Н. Ръководство по математическо програмиране, София, 1980, Наука и изкуство.
Спиридонов, В. Изследване на операциите, София, 1973, Наука и изкуство.
Христов, Г., Калтинска, Р. Математическо оптимиране I част, София, Наука и изкуство, Серия „Съвременна математика“, 1972.

[1] ((en)) "The Nature of Mathematical Programming Архив на оригинала от 2014-03-05 в Wayback Machine.", Mathematical Programming Glossary, INFORMS Computing Society.

[1]