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

Задачи математического программирования – это задачи определения наилучшего решения из множества допустимых.

В общем виде постановка задачи математического программирования состоит в определении значений переменных х₁, х₂, …, х_n, при которых достигается максимум или минимум функции

(6.1)

при условиях:

(6.2)

Функция (6.1) называется целевой функцией, а условия (6.2) – ограничениями данной задачи. Запись в ограничениях означает, что возможен один из знаков , = или . В данной задаче n обозначает число переменных, а m - число ограничений.

Переменные задачи х₁, х₂, …, х_n могут иметь различный экономический смысл. Например, если предприятие выпускает три вида продукции, и нужно найти оптимальный план производства, то х₁, х₂, х₃ – количество продукции каждого вида, которое необходимо производить. Если в задаче необходимо найти наилучший состав рациона, в которую могут входить несколько составных компонентов (например, сено и силос в рационе коров), то х₁ и х₂ – количество каждого продукта, которое нужно включить в рацион (в данном случае, сена и силоса).

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

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

В зависимости от характера целевой функции f и функций ограничений _, говорят о различных видах задач математического программирования:

· если целевая функция задачи имеет линейный вид, а ограничения заданы в виде линейных уравнений или неравенств, то это задача линейного программирования. Пример линейного выражения:

5х₁+6х₂.

· если целевая функция и/или ограничения содержат нелинейные функции, то это задача нелинейного программирования. Пример нелинейных функций:

, х², , sin x, 1/x и т.д.

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

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