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

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

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

изучаващ задачата за намиране на оптималмна стойност (минимум или максимум) на функция при наложени ограничения.

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

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

Функцията $f\,$ наричаме целева функция. Множеството от допустими решения $X\,$, зададено чрез система неравенства и/или уравнения, наричаме система от ограничения. Разделението на видовете оптимиране се обуславя от типа на целевата функция и ограниченията на задачата. Най-често използувани в практиката са: линейно оптимиране, нелинейно (квадратично, хиперболично) оптимиране , целочислено оптимиране, изпъкнало оптимиране, матрични игри и др. Математическото оптимиране, с помощта на изчислителната техника, прави възможно решаването на голям брой икономически задачи и задачи от изключително значение за практиката. В това число транспортната задача, задача за назначенията, задача на вариационното смятане, задача за диетата и др.

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

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

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

$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 и с това слага началото на бурно развитие на дисциплината, продължаващо и до днес.

Източници

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

Допълнителна литература

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