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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Граф на параболоид, зададен чрез 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.