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

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

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

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

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

.

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

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

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

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

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

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

матрица на ограниченията, е вектор на ограниенията, е вектор на целевата функция и вектор на променливите.

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

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

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

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

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

  1. ((en)) "The Nature of Mathematical Programming," 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.