Эксперт по сдаче вступительных испытаний в ВУЗах
ПРАКТИЧЕСКАЯ РАБОТА №4.
ЗАДАЧА О НАЗНАЧЕНИЯХ
Важной разновидностью транспортной задачи ЛП, является т. н. «задача о назначениях» Суть ее сводится к следующему. Пусть имеются
n кандидатов и
n работ.
Известны затраты
сij , связанные с выполнением
i -м кандидатом
j — й работы. Предполагается, что каждый кандидат может быть назначен только на одну работу и каждая работа может быть выполнена только одним кандидатом.
Требуется так распределить (назначить) кандидатов на работы, чтобы суммарные затраты были минимальны.
Эта задача возникает, например, при распределении работников фирмы на обслуживание клиентов, при распределении водителей по автомашинам, при распределении групп студентов по аудиториям и т.д.
Построение математической модели:
хi j =1, если
i -й кандидат назначен на
j— -ю работу
хi j =0, в противном случае.
По условию:
— каждый кандидат назначается только на одну работу,
j =1,…,n (4.1)
— каждая работа выполняется только одним кандидатом,
i = 1,…,n (4.2) (4.3)
Легко видеть, что модель соответствует модели транспортной задачи и может быть решена стандартным методом, скажем методом потенциалов, однако специальная форма записи модели позволила разработать более эффективный алгоритм решения задачи называемый
венгерским методом. Для решения
задачи на компьютере может быть использована стандартная процедура поиск решения Microsoft Excel (прил. 4), с той лишь разницей, что вместо свободных членов (запасов) матрицы ограничений транспортной задачи заносятся 1 (каждый кандидат может быть назначен только на одну работу).
Задана матрица затрат:
С =
Решить задачу о назначениях.
Ответ представить в графической форме
Ссылка на первоисточник:
http://kgims.ru
