X Международная студенческая научная конференция Студенческий научный форум - 2018

Пусть некоторая компания имеет четыре заказа в разных точках города А1, А2, А3, А4, которые необходимо назначить различным исполнителям В1, В2, В3, В4. В каждой точке по одному заказу. В таблице содержится информация о стоимости возможных назначений.

	В1	В2	В3	В4
А1	2	10	9	7
А2	15	4	14	8
А3	13	14	16	11
А4	4	15	13	19

Как следует распределить заказы по исполнителям, чтобы общая сумма затрат была минимальной? Такого рода задачи возникают повседневно. Для их решения удобно использовать средства Microsoft Office, в частности Microsoft Excel.

Для построения математической модели, во-первых, вводятся переменные x_ij, принимающие два значения: x_ij=0, если назначения нет и x_ij=1, если назначение есть. Во-вторых, принимаются ограничения на переменные задачи. Очевидно, что все переменные задачи неотрицательные. Кроме того, так как каждый заказ должен быть назначен только одному исполнителю и все заказы должны быть распределены, то должны выполняться следующие ограничения:

В-третьих, вводится целевая функция. Необходимо назначит заказы так, чтобы общая сумма затрат была минимальной. Суммарное количество затрат вычисляется по формуле

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

Таким же образом выглядит модель задачи о назначениях с промежуточным посредником.

Матрица затрат выглядит следующим образом

С11	С12	С13	С14	∞	∞	∞	∞
С21	С22	С23	С24	∞	∞	∞	∞
С31	С32	С33	С34	∞	∞	∞	∞
С41	С42	С43	С44	∞	∞	∞	∞
∞	∞	∞	∞	С55	С56	С57	С58
∞	∞	∞	∞	С65	С66	С67	С68
∞	∞	∞	∞	С75	С76	С77	С78
				С85	С86	С87	С88

Для нахождения оптимального плана назначения [3] удобно использовать надстройку поиска решений табличного процессора MS Excel, например

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

Литература

Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2007.

Красс М.С. Математика для экономических специальностей. М.: Дело, 2003.

Кремер Н.Ш. Исследование операций в экономике. М.: ЮНИТИ, 2006.

Код для цитирования: Скопировать