Задача об оптимальном назначении

Найти оптимальное распределение m работ между m исполнителями при заданной матрице C ={C_ij} (где C_ij характеризует в количественной форме эффективность выполнения i-ой работы j-м исполнителем) при дополнительных условиях:

1) каждый исполнитель может выполнить только одну работу;

2) каждая работа может исполняться только одним исполнителем.

В задаче используются двоичные (бинарные, булевы) переменные Х_ij.

Математическая модель задачи примет вид:

- выполняется первое условие. Это выражение можно интерпретировать как предложение трудовых ресурсов.

- выполняется второе условие. Это выражение можно интерпретировать как потребность в трудовых ресурсах.

Функция цели (максимальная общая эффективность):

Примечание: эта модель быть использована и при распределении работ между участками производства, оборудованием. Величины С_ij могут означать затраты средств, времени, тогда функция цели составляется на минимум.

Задача. На трех токарных станках различных типов можно выполнять три операции по обработке деталей. При этом за каждым из станков может быть закреплена лишь одна операция. Одна и та же операция может выполняться только одним станком. Зная время выполнения каждой операции на каждом из станков, которое задается матрицей , составить такое распределение выполняемых операций между станками, при котором суммарные затраты времени на обработку деталей стремятся к минимуму.

Решение. Введем обозначение:

Тогда:

закрепление за каждым станком только одной операции

закрепление за каждой операции за одним станком

закрепление за каждой из операций только одного станка

Минимум затрат времени на обработку:

f(x)= 2X₁₁+4X₁₂+6X₁₃+1X₂₁+3X₂₂+2X₂₃+7X₃₁+2X₃₂+4X₃₃→min

Результат можно представить в виде матрицы:

первый станок выполняет первую операцию, второй станок – третью операцию, третий станок – вторую операцию.

Минимальное время на обработку детали составит f(x)=6.

Задача формирования команд

Фирма, занимающаяся продажей оборудования для компьютерных сетей, имеет 10 специалистов по маркетингу и 10 техников-программистов которых необходимо объединить попарно (менеджер по маркетингу и техник) в команды по продаже оборудования, соответствующего нуждам конкретного клиента. Менеджер по работе с персоналом провел среди них тест Майера - Бриггса и определил индекс взаимной несовместимости между i-м маркетологом и j-м техником. Индекс варьирует от 20 (выраженная враждебность) до 1 (дружеские отношения). Результаты представлены в таблице индексов несовместимости.

Необходимо составить команды так, чтобы суммарный индекс несовместимости был бы минимальным.

С математической точки зрения данная задача похожа на предыдущую, за исключением необходимости минимизации функции цели.

Математическая модель задачи примет вид:

Функция цели (минимальная общая несовместимость):

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

- выполняется второе условие. Это выражение можно интерпретировать, как необходимость включить в каждую команду одного специалиста-техника.

Задача решается в табличном процессоре Excel с помощью программы Поиск решения. Исходные данные, включающие индексы несовместимости представлены на рис. 7. Результаты расчёта представлены на рис. 8. В итоговой таблице единицы соответствуют идеальному варианту составления малых групп для эффективного выполнения работы.

Отчет по занятию должен содержать:

1.Основные теоретические положения

2.Постановку задачи

3.Условие задачи

4.Математическую модель в общем виде

5.Математическое описание представленной задачи

Рис. 7. Исходные данные для формирования команд

Рис.8. Результаты формирования команд

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ