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

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

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

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

Управляющие переменные x_ij, i = 1,…, n; j = 1,…, n определяются по формуле

1 , если i-й агент направлен в j-й город;

x_ij =

0, в противном случае.

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

;

x_ij Î {0;1}, i = 1,…,n; j = 1,…,n.

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

1 Число n! называется факториалом числа n и вычисляется по формуле: Например,

1 См. определение в §2.2.