Тема 8. Задачи математического программирования

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

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

f(х₁,х₂, …, х_n) → max(min) (9.1)

при условиях

_,

, (9.2)

…

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

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

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

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

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

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

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

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

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

Наиболее разработанными являются методы решения з адач линейного программирования [1]. В общем виде задача линейного программирования заключается следующем: найти значения переменных х₁, х₂, …, х_n, доставляющие оптимальное значение целевой функции:

F=c₁x₁+c₂x₂+... +с_nх_n®min (max) (9.3)

при выполнении ограничений:

а₁₁х₁+а₁₂х₂+ …+а_1nх_n{£, =, ³}b₁

а₂₁ х₁+а₂₂х₂+ …+а_2nх_n{£, =, ³}b₂

……… (9.4)

а_m1х₁+а_m2x₂+ …+а_mnх_n{£, =, ³}b_m

x_j>=0, (i=1…n) (9.5)

где а_ij, b_i, c_j –заданные постоянные величины, m – число уравнений, n – число переменных.

Ограничения (9.5) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х₁, х₂, …, х_n. Например, если под x_i понимается количество продукции вида i, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным.

Систему ограничений (9.4) называют функциональными ограничениями, а ограничения (9.5) – прямыми. Вместе ограничения (9.4) и (9.5) определяют область допустимых решений.

Набор значений переменных х_1, х_2,…,х_n, при котором выполняются все ограничения, называется допустимым решением или планом. Допустимое решение, при котором функция F принимает оптимальное значение, называется оптимальным.

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

Пример 8.1. Цех может выпускать два вида продукции: шкафы и тумбы для телевизора. На каждый шкаф расходуется 3,5 м стандартных ДСП, 1 м листового стекла и 1 человеко-день трудозатрат. На тумбу — 1 м ДСП, 2 м стекла и 1 человеко-день трудозатрат. Материальные и трудовые ресурсы ограничены: в цехе работают 150 рабочих, в день нельзя израсходовать больше 350 м ДСП и более 240 м стекла. Прибыль от продажи 1 шкафа составляет 200 у.е., а тумбы — 100 у.е.

Какое количество шкафов и тумб должен выпускать цех, чтобы сделать прибыль максимальной?

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