Задача о назначениях является частным случаем транспортной задачи, в которой ресурсы (работы) соответствуют пунктам отправления, а объекты (станки) пунктам назначения. Все величины спроса и предложения при этом равны нулю



страница1/2
Дата17.04.2019
Размер0.79 Mb.
Название файлао назначениях.doc
ТипЗадача
  1   2

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

Задача о назначениях состоит в выборе такого распределения ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс. Такие задачи возникают при оптимизации распределения работ по станкам либо работникам.

Задача о назначениях является частным случаем транспортной задачи, в которой ресурсы (работы) соответствуют пунктам отправления, а объекты (станки) – пунктам назначения. Все величины спроса и предложения при этом равны нулю. Стоимость «транспортировки» - это стоимость выполнения работы. Специфичность ограничений позволяет использовать упрощенный метод решения задачи о назначениях, названный венгерским методом.

Алгоритм венгерского метода


  1. Получаем максимально возможное число нулевых элементов в матрице затрат С. Для этого из всех элементов каждой строки матрицы С вычитаем минимальный элемент соответствующей строки, в результате чего получаем матрицу С1. Затем из всех элементов каждого столбца матрицы С1 вычитаем минимальный элемент соответствующего столбца, в результате чего получаем матрицу С2.

  2. Если в каждой строке и каждом столбце матрицы С2 можно выбрать по одному нулевому элементу, то полученное расположение выбранных нулей соответствует оптимальному назначению.

  3. Если в п. 2 невозможно выбрать нули в матрице С2, то следует провести минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Далее выбирается наименьший невычеркнутый элемент  хij . Из каждого невычеркнутого элемента значение  хij вычитается, а к каждому элементу, стоящему на пересечении проведенных прямых  хij прибавляется .

  4. Переходим к шагу 2.

Минимально возможная суммарная стоимость назначений находится сложением элементов матрицы С, соответствующих выбранным в матрице С2 нулевым элементам.

Замечания

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

  2. Если количество ресурсов отличается от количества объектов, то следует ввести фиктивные ресурсы или фиктивные объекты, чтобы их было равное количество. При этом в качестве стоимости выполнения работ принимается заданный в условиях задачи штраф, а при его отсутствии принять стоимость равной, например, нулю.

  3. В том случае, когда в задаче о назначениях целевая функция максимизируется (например, дана производительность станков), матрицу С следует умножить на (-1), а затем ко всем элементам полученной матрицы прибавить такое число, чтобы получилась матрица с неотрицательными элементами (см. пример 5).

Пример 4. Задача Тр-3.

В цехе предприятия имеется 5 универсальных станков, которые могут выполнять 4 вида работ. Каждую работу единовременно может выполнять только один станок, и каждый станок можно загрузить только одной работой.


В таблице 3 даны затраты времени при выполнении станком определенной работы. Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты времени.

Таблица 3



Станок

Работа


1

2

3

4

5

1

5

3

6

6

4

2

5

7

7

5

4

3

8

9

5

9

8

4

6

5

5

9

5

Решение.

1. Из условия видно, что количество работ не соответствует количеству станков. Поэтому необходимо ввести фиктивную работу. Затраты времени при выполнении станком определенной работы примем равными нулю. Получаем:



Станок

Работа


1

2

3

4

5

1

5

3

6

6

4

2

5

7

7

5

4

3

8

9

5

9

8

4

6

5

5

9

5

ф

0

0

0

0

0

2. В каждой строке матрицы затрат времени при выполнении станком определенной работы С найдем минимум. Из элементов каждой строки вычтем найденное значение минимума и получим матрицу С1 :



min

; .

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



4. Минимальным количеством прямых (горизонтальных и вертикальных) в матрице С1 вычеркнем все нули. Среди невычеркнутых элементов матрицы выбираем минимальный cij=min{2,3,1,1,3,4,1,4} =1.
.

Из всех невычеркнутых элементов матрицы вычитаем cij, а ко всем дважды вычеркнутым элементам cij прибавляем. Получаем матрицу С2:





5. В полученной матрице С2 выбираем по одному нулю в каждой строке и в каждом столбце, расположение которых будет соответствовать рациональному распределению работ по станкам:

; .

6. Для того чтобы рассчитать минимизирующее суммарные затраты времени складываем соответствующие элементы матрицы С:

 cij = 3+5+5+5+0 =18.

Ответ. Первая работа выполняется на втором станке, вторая - на первом, третья - на третьем, четвертая - на пятом, без работы останется четвертый станок. Минимальные суммарные затраты времени равны 18-ти.

Пример 4. Задача Тр-3.

Служба занятости имеет в наличии шесть вакантных мест по разным специальностям, на которые претендуют пять человек. Проведено тестирование претендентов, результаты которого в виде балов представлены в таблице 4. Распределить претендентов на вакантные места таким образом, чтобы на каждое место был назначен человек с наибольшим набранным по тестированию баллом.

Таблица 4


Номер претендента

Специальность



1

2

3

4

5

1

5

3

5

7

4

2

6

4

6

5

5

3

4

8

7

9

3

4

7

7

5

6

8

5

5

3

4

7

6

6

6

5

6

4

7



Решение.

  1. Из условия видно, что количество специальностей не соответствует количеству претендентов. Поэтому необходимо ввести фиктивного претендента, результаты тестирования для которого будут равны нулю. Получим матрицу С, элементы которой умножим на (-1).

; .

К элементам полученной матрицы С1 прибавляем одно и тоже число, которое не меньше максимального значения элементов исходной матрицы С (в рассматриваемой задаче это число должно быть не меньше 9, например, 10), получаем матрицу С2: .

В каждой строке матрицы С2 найдем минимум cij , который вычтем из элементов этой строки, получим матрицу С3. В каждом столбце матрицы С3 найдем минимум cij , который вычтем из элементов этого столбца, получим матрицу С4.


Поделитесь с Вашими друзьями:
  1   2


База данных защищена авторским правом ©nedocs.ru 2017
обратиться к администрации

    Главная страница