Экзамен - Билеты - 2004 / экз-ОЛ-венг-алгоритм-задание1

Российский химико-технологический университет им. Д.И.Менделеева

Кафедра Логистики и экономической информатики химических, нефтеперерабатывающих и нефтехимических предприятий

Специальная дисциплина «Основы логистики» ("О.Л.")

Тема «Применение «венгерского» алгоритма к поиску организационно-управленческого решения некоторых задач логистики, формализованных в виде «задачи о назначении (ЗОН)»

Задание 1

Для разработки логистической системы некоторой производственно-хозяйственной организации (ПХО) необходимо создать временную рабочую группу, в состав которой должны войти как сотрудники данной ПХО, так и эксперты со стороны. Группа должна состоять из 4-х человек, каждый из которых может занимать только одну должность. Разработаны должностные инструкции, определяющие круг обязанностей и уровень квалификации каждого члена указанной рабочей группы.

После собеседования с возможными кандидатами на участие в данном проекте осталось 4 наиболее подходящих по своим профессиональным качествам человек (X1, X2, X3, X4).

Для квалифицированного освоения работ на каждой из указанных 6 должностей (Y1,Y2,Y3,Y4) каждому кандидату необходимо затратить определённое время.

Каждому назначению (XiYi) поставим в соответствие время tij, которое необходимо i-му кандидату на освоение j-той должности. В свою очередь, время tij соответствует элементу aij во взвешенной матрице назначения [A]. Если назначение (XiYi) невозможно, то элемент aij = ∞.

Взвешенная матрица назначения [A] имеет вид (время дано в неделях):

9 10 ∞ 8

10 2 4 6

9 4 7 ∞

10 5 8 ∞

Требуется:

1. построить двудольный граф, отображающий все возможные варианты назначений;

2. показать на двудольном графе полное паросочетание, максимальное паросочетание, минимальное покрытие, минимальную опору;

3. с использованием «венгерского» алгоритма определить минимальное суммарное время освоения работ 6-тью кандидатами на 4-х должностях рабочей группы, создаваемой для разработки логистической системы ПХО.