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

Торговая фирма продает товары в 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. Сформулируйте транспортную задачу закрытого типа.

2. Запишите задачу, двойственную к транспортной.

3. Сформулируйте алгоритм метода северо-западного угла.

4. Сформулируйте теоремы двойственности применительно к транспортной задаче.

5. Сформулируйте алгоритм решения задачи о назначениях.

Задание №16

Дата добавления: 2014-12-29