Классификация оптимизационных задач

Классификационные признаки по отношению к математической модели включают следующие ее составные части:

ü исходные данные;

ü искомые переменные;

ü характер зависимости целевой функции.

Исходными данными для математической модели являются выражение для целевой функции, ограничения и граничные условия. Если при составлении модели точные значения исходных данных (разумеется, кроме значений варьируемых параметров – они не являются исходными данными!) известны, такие данные называют детерминированными. Однако в жизни, например, в достаточно распространенных задачах распределения ресурсов точное значение имеющегося ресурса, а также других элементов, входящих в модель, может быть заранее неизвестно. В таких случаях эти элементы модели являются случайными величинами.

По физической сущности варьируемые параметры могут принимать непрерывные и целочисленные значения. Например, в задаче распределения мебели между отделами некоторого учреждения вряд ли будет признано допустимым решение о выделении некоему отделу 3, 14 шкафа: количество шкафов должно быть целым числом. В то же время решение, предусматривающее введение в рацион кормления животных 33, 7 г минеральных добавок на 1 кг корма не вызовет никакой отрицательной реакции: по смыслу весовые величины могут принимать непрерывные значения. Кроме того, в задачах выбора оптимального варианта в качестве варьируемых параметров выступает еще одна группа переменных, которые могут принимать только определенные значения из некоторого множества непрерывных или целочисленных значений. Такие переменные называют дискретными.

И, наконец, по характеру зависимости между переменными (как в целевой функции, так и в ограничениях) различают линейные и нелинейные модели. Линейными называют такие зависимости, в которые переменные входят в первой степени, и над ними выполняются только операции сложения или вычитания. Если же переменные входят в выражение не в первой степени либо с ними выполняются другие действия, такие зависимости называются нелинейными.

Примером линейной зависимости является следующее выражение для целевой функции:

,

а нелинейной зависимости – выражение для ограничения

.

Таким образом, оптимизационные задачи и математические методы их решения с учетом упомянутых признаков могут быть разбиты на следующие классы:

Таблица 4.1 – Классификация оптимизационных задач

4.3 Типы задач линейного программирования

К задачам линейного программирования относится широкий класс инженерных и экономических задач. Приведем лишь несколько классических примеров.

Транспортная задача. Имеется несколько пунктов производства и потребления некоторого продукта. Для каждого из пунктов производства задан объем производства, а для каждого пункта потребления – объем потребления. Известна также стоимость перевозки из каждого пункта производства в каждый пункт потребления единицы продукта. Требуется составить план перевозок продукта, в котором все пункты потребления были бы обеспечены необходимыми продуктами, ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальной.

Задача о выборе оптимального меню. Имеется набор некоторых продуктов, обладающих определенной калорийностью. Известны также количества белков, жиров и углеводов для каждого из этих продуктов и их стоимость. Требуется составить меню, удовлетворяющее требованиям калорийности и сбалансированности питательных продуктов, и при этом минимизирующее суммарную стоимость.

Задача о назначениях. Имеется несколько должностей и соответствующее количество претендентов на эти должности. Назначение i -го претендента на j -ую должность связано с затратами C [ i, j ]. Требуется распределить претендентов по должностям так, чтобы суммарные затраты были минимальны.

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

Задачи линейной алгебры. Методы линейного программирования позволяют решать различные системы линейных уравнений.