3.7. Применение задачи о назначениях к решению экономических проблем

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

Оптимальное исследование рынка

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

Определить время проведения опросов, при котором общее число опросов максимально.

Решение

Сведем данную задачу к задаче о назначениях.

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

Математическая модель задачи имеет следующий вид:

Функция характеризует суммарное число опросов. Его нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течение одного дня можно находиться только в одном месте. Для расчета модели венгерским методом надо перейти к противоположной функции

,

и в соответствующей таблице записывать значения с противоположным знаком.

Оптимальное использование торговых агентов

Торговая фирма продает товары в различных городах, покупательная способность жителей которых оценивается в усл. ед., . Для реализации товаров фирма располагает торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен; доля реализуемых-м торговым агентом покупательных способностей составляет, .Как следует распределить торговых агентов по городам, что­бы фирма получила максимальную выручку от продажи товаров?

Решение.

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

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

Управляющие переменные , , определяются по формуле

Математическая модель запишется в следующей форме:

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

4. Нелинейное программирование

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

В общем виде задача нелинейного программирования (ЗНП) формулируется следующим образом:

(4.1.1)

(4.1.2)

где

– управляющие переменные или решения ЗНП, ;

– фиксированные параметры, ;

, , – заданные функции от переменных.

Если и линейны, то (4.1.1), (4.1.2) переходит в задачу линейного программирования.

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

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

Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям, поэтому в данном пособии нелинейные модели и методы расчета рассмотрены до­статочно кратко.