Предмет математического программирования

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

Целевой функцией (показателем эффективности, критерием оптимальности) называют функцию, экстремальное значение которой нужно найти.

Экстремальным значением называют максимальное или минимальное значение.

Системой ограничений называют условия, которым должно удовлетворять решение задачи.

Математическая модель задачи – это постановка исходной задачи в виде целевой функции и системы ограничений.

Общая схема формирования экономико-математической модели

1) Выбор некоторого числа переменных величин, задание числовых значений которых однозначно определяет одно из возможных состояний исследуемого явления. Совокупность неизвестных величин будем обозначать , а полученные числовые значения для вектора будем называть решением или планом задачи.

2) Построение целевой функции. Это может быть прибыль, объем выпуска, затраты производства и т.д. Целевую функцию обозначим .

3)Построение (составление) системы ограничений.

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

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

, (1.1)

при ограничениях

, (1.2)

, (1.3)

, (1.4)

, (1.5)

где - заданные действительные числа.

Целевая функция (1.1) и ограничения (1.2)-(1.5) являются экономико – математической моделью задачи математического программирования.

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

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

Экстремальное значение целевой функции .

Оптимальное решение не обязательно единственно. Возможны случаи, когда оно не существует, когда имеется конечное или бесчисленное множество оптимальных решений.

Классификация методов математического программирования

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

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

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

3 Если на все или некоторые переменные наложено условие дискретности, например целочисленности ( = 0,1,2…), то такие задачи рассматриваются в разделе математического программирования, называемом дискретным, в частности целочисленным программированием (ЦП).

4 Если параметры целевой функции или системы ограничений изменяются во времени или процесс решения задачи имеет многошаговый характер, то такие задачи решаются методами динамического программирования (ДП).

В перечисленных выше разделах математического программирования предполагается, что вся информация о протекании процессов заранее известна и достоверна. Такие методы оптимизации называются детерминированными.

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

Дата добавления: 2014-01-11