Задача о назначениях Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С. - презентация

1 Задача о назначениях Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С.

2 Постановка задачи Требуется распределить m работ (или исполнителей) по n станкам. Работа i (i = 1,..., m), выполняемая на станке j (j = 1,..., n), связана с затратами c ij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

3 Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость c ij берется равной очень большому числу.

4 Матрица стоимостей C станки виды работ

5 Прежде чем решать такую задачу, необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.

6 Добавление станков Станки 12 Виды работ

7 Добавление станков Станки 123*3* Виды работ 157 ? ? ?

8 Добавление исполнителей Станки 123 Виды работ

9 Добавление исполнителей Станки 123 Виды работ * ???

10 Пусть x ij = 0, если j-я работа не выполняется на i-м станке, x ij = 1, если j-я работа выполняется на i-м станке. Таким образом, решение задачи может быть записано в виде двумерного массива X = (x ij ). Допустимое решение называется назначением.

11 Теперь задача будет формулироваться следующим образом: ;

12 Решение Решение описанной выше математической модели можно реализовать с помощью надстройки «Поиск решения» в Excel (см. пример «СР_3_1_Задача о назначениях (ответы).xlsx»). Кроме того задача может быть решена венгерским алгоритмом (см. пример «СР_3_1_Задача о назначениях (ответы).xlsx»: Задача 2). Выбирайте любой удобный для вас способ.

13 Венгерский алгоритм Шаг 1. Редукция строк и столбцов. Шаг 2. Определение назначений. Шаг 3. Модификация редуцированной матрицы. Примечания 1) Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк (столбцов), то существует полное назначение. 2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (–1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следует решать как задачу минимизации.

14 Задача размещения производства. Компания разрабатывает план выпуска трех новых видов продукциии. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукциии – по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукциии.

15 Вид продукциии Предприятие Вид продукции и Предприятие Издержки производства единицы продукциии (руб.): 2. Издержки сбыта единицы продукциии (руб.):

16 Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукциии каждого вида следующие: Вид продукциии Плановый объем производства Плановая стоимость (руб.)

17 Прибыль на единицу продукциии: Вид продукциии Предприятие –18– –6936–20–15–

18 Общая годовая прибыль (в тыс. руб.): Вид продукциии Предприятие –630– – –3200–

19 Оптимальное решение данной задачи следующее: производство первого вида продукциии назначается предприятию 4, второго вида – предприятию 1, третьего вида – предприятию 3, четвертого вида – предприятию 2, пятого вида – предприятию 5. Очевидно, что 2 последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна = 7892 (тыс. руб).

20 Оптимальное исследование рынка Группе, исследующей рынок, требуется получить данные из n различных мест. В ее распоряжении имеется n дней, и она предполагает провести по одному дню в каждом месте, проведя по а j опросов, j = 1, …, n. Вероятность успешного опроса в каждом месте задается матрицей Р. Элемент матрицы р ij характеризует вероятность успешного опроса в течении i-го дня в j-м месте, i = 1, …, n.

21 Необходимо определить: время проведения опросов, при котором общее число опросов максимально. Данная задача сводится к задаче о назначениях.

22 Введем величину r ij = p ij a j, показывающую число успешных опросов в в j-м месте в течение i-го дня. 1, если в i-й день опрос проводится в x ij = j-м месте; 0, в противном случае.

23 Математическая модель задачи имеет следующий вид: ; x ij {0;1}, i = 1,…, n ; j = 1,…, n.

24 Для расчета модели венгерским методом: необходимо перейти к противоположной функции: и в соответствующей таблице записывать значения r ij с противоположным знаком.

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

26 Решение этой проблемы может быть найдено с помощью задачи о назначениях. В качестве кандидатов выступают торговые агенты, в качестве работ – города. Введем параметр с ij = a i b j, характеризующий величину покупательных способностей, реализуемых i-м торговым агентом в j-м городе. Управляющие переменные x ij, i = 1,…, n; j = 1,…, n определяются по формуле: 1, если i-й агент направлен в j-й город; x ij = 0, в противном случае.

27 Математическая модель запишется в следующей форме: ; x ij {0;1}, i = 1,…, n ; j = 1,…, n. Для решения задачи венгерским методом надо, как и в предыдущем примере, перейти к противоположной функции.

28 О производстве, о загрузке оборудования, о загрузке корабля.