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

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

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

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

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

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

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

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

Линейно оптимиране

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

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

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

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

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

История

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

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