Задача о назначениях

1

Задача о назначениях - одна из выделен- ных задач линейного программирования.

Вообще говоря, можно считать, что это частный случай транспортной задачи, для которой запасы поставщиков и потребности потребителей равны 1.

Если на примерах, это может быть задача назначения работников на должности (цель - максимальная эффективность или минимальные затраты), назначение машин на производственные линии и т.п., при этом один исполнитель может выполнять только одну

работу.

2

Так же как для решения транспортной задачи был разработан «свой» метод -потенциалов, так и для задачи о назначениях был создан более подходящий (более краткий) метод решения.

Чаще всего используется так называемый

венгерский метод решения задачи о назначениях.

3

Содержательная постановка

Пусть имеются n работников, которых необходимо обеспечить работой.

Пусть имеются n работ (рабочих мест), которые должны быть выполнены (заняты).

Известно tij - время, за которое i–й () работник выполняет j–ую () работу.

4

Таким образом известна матрица T – матрица временных затрат:

T – квадратная матрица.

5

Требуется назначить работников на рабочие места таким образом, чтобы:

- суммарное время выполнения работ было минимальным;

-все работники были заняты;

-все работы были выполнены;

-один работник выполнял только одну

работу;

- одна работа выполнялась только одним работником.

(Прочитать еще раз!!!)

6

Формальная постановка

Введем переменную xij ():

0 – если i-й работник не назначен j-ую на работу;

1 - если i-й работник не назначен j-ую на работу.

!!! Переменная – булева переменная.

7

Тогда время, потраченное на выполнение всего комплекса работ, будет определяться по формуле:

8

Очевидно, что ограничения, связанные с назначениями, выглядят, соответственно:

один работник выполняет одну работу

одна работа выполняется одним работником

9

Таким образом формальная постановка задачи имеет вид:

10