Оптимизационные модели

Математические методы оптимизации, соответствующие алгоритмы и компьютерные программы можно рассматривать как эффективный элемент наукоемких технологий, разработка которых в различных областях в настоящее время особенно актуальна. Оптимизационные методы используются в исследовании операций и системном анализе, в планировании производственной деятельности, в проектировании различных объектов, в военном деле и т.д.

Недостаточность классической теории оптимизации вылилась во второй трети XX в. при необходимости решать задачи с ограничениями в виде неравенств, особенно при большом числе переменных. Последнее обстоятельство (большая размерность задач) преодолено разработкой численных методов решения систем алгебраических уравнений соответствующих компьютерных программ.

Задачи с ограничениями в виде неравенств, в которых равенство нулю частных производных вообще не является даже необходимым условием экстремума, потребовали работки новой теории оптимизации — теории математического программирования. Эта теория дает совокупность методов решения задач поиска экстремума функций многих переменных (целевая функция) при наличии ограничений (равенств или неравенств) на искомые неизвестные. Как правило, это численные (итерационные) годы. Их практическая реализация осуществляется в соответствующих алгоритмах и компьютерных программах.

Классические задачи на безусловный экстремум (при отсутствии ограничений вообще) или при наличии только ограничений-равенств также могут решаться методами математического программирования (как частный случай). Отсюда следует теоретическая и практическая значимость этих методов.

Наиболее известными и простыми являются методы линейного программирования, используемые в научных исследованиях и практической деятельности значительно чаще, чем методы нелинейного программирования. Но нелинейное программирование— это бурно раз­вивающийся раздел современной теории оптимизации, созданный практически в последние 30-40 лет. Сравни­тельно редкое практическое применение методов нели­нейного программирования объясняется именно этим об­стоятельством (а не отсутствием реальных практических задач), так как необходимо значительное время для освое­ния новых теорий широким кругом практиков и реализа­ции новых методов в конкретных алгоритмах и компью­терных программах. Более того, реализация методов нели­нейного программирования для решения задач большой размерности требует мощных компьютеров, которые по­лучили широкое распространение в нашей стране только в последние 10-15 лет.

Почти одновременно с линейным программированием (конец 40-х - начало 50-х годов прошлого века) был разра­ботан метод динамического программирования. В «компь­ютерную эпоху» он получил широкое применение в самых различных областях практики. Этот мощный метод оптими­зации далеко не универсальный. Известны безуспешные попытки его применения без должного анализа особенно­стей конкретной задачи оптимизации.

Отличительные признаки оптимизационных моделей:

• наличие одного или нескольких критериев оптималь­ности (критерий оптимальности — это признак, по
которому одно (или множество) решений задачи при­знается наилучшим); наиболее типичными критерия­ми в экономических оптимизационных задачах явля­ются: максимум дохода или прибыли, минимум из­держек, минимальное время для выполнения задания и другие;

• система ограничений, формируемая исходя из содер­жательной постановки задачи и представляющая собой
систему уравнений или неравенств.

Математически эти задачи относятся к задачам на ус­ловный экстремум. Постановка таких задач, представлен­ных в общем виде, выглядит следующим образом:

• найти условный максимум (или минимум) функции

Y = f (x₁x₂...x_n) → max (min), (1)

• при условии, что независимые переменные удовлетво­ряют ограничениям:

G (x₁,x₂...x_n) = 0. (2)

Функцию G называют функцией, задающей ограничения. Если в задаче на условный экстремум ограничения в виде системы уравнений G (x₁, x₂,..., х_n) = 0 заменить на ограниче­ния в виде неравенств и добавить требования (ограничения) неотрицательности переменных x₁ ≥0, x₂ ≥0,... х_n≥0, то полу­чим задачу математического программирования, в которой необходимо:

• найти максимум (или минимум) функции

f (x₁,x₂...x_n) →max(min) (3)

• при условии, что независимые переменные удовлетворяют системам ограничений:

g₁(x₁,x₂...x_n) ≤ 0

……………… (4)

g_n(x₁,x₂...x_n) ≤ 0

x₁≥0,x₂≥0,...,x_n≥0 (5)

В задаче математического программирования функцию f (x_b x₂..., х_n) также называют целевой функцией; систему неравенств (4) — специальными ограничениями задачи математического программирования, а неравенства (5) — общими ограничениями задачи линейного программирова­ния.