Пример

Лекция

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

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

Матрица стоимостей С имеет вид С = (с_ij), где с_ij – затраты, связанные с назначением i -го ресурса на j -й объект, i = j = , где п – число объектов или ресурсов.

Обозначим:

	если i-й ресурс назначается на j-й объект; в противном случае.

Таким образом, решение задачи может быть записано в виде X = (x_ij).

Допустимое решение называется назначением. Оно строится путём выбора ровно одного элемента в каждой строке матрицы X = (x_ij) и ровно одного элемента в каждом столбце этой матрицы.

Элементы с_ij матрицы С, соответствующие элементам x_ij = 1 матрицы Х будем отмечать кружками:

С = (с_ij) = , X = (x_ij) =

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

при ограничениях:

x_ij = 0 или 1.

Алгоритм решения задачи

Рассмотрим метод, называемый венгерским алгоритмом. Он состоит из следующих шагов:

1) преобразование строк и столбцов матрицы;

2) определение назначения;

3) модификация преобразованной матрицы.

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

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

3-й шаг. Если допустимое решение, состоящее из нулей, не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьший невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведённых прямых.

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

Распределить ресурсы по объектам.

РЕШЕНИЕ. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим

2-й шаг. Ни одно назначение не получено, необходимо провести модификацию матрицы стоимостей.

3-й шаг. Вычёркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

min = 2.

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

Итак,

Ответ. Первый ресурс направляем на 3-й объект, второй – на 2-й объект, четвёртый – на 1-й объект, третий ресурс – на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на какой-то объект, то соответствующая стоимость полагается равной достаточно большому числу М.

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

4. Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

Планирование загрузки оборудования

с учётом максимальной производительности

станков

На предприятии пять станков различных видов, каждый из которых может выполнять пять различных операций по обработке деталей. Известна производительность каждого станка при выполнении каждой операции, заданная матрицей

.

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

РЕШЕНИЕ. Так как в задаче требуется определить max, а алгоритм метода дан для задач на min, умножим матрицу С на (-1). Сложим полученную матрицу, имеющую отрицательные коэффициенты, с положительным числом, например, с числом 10. Получим

Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Вычтем их из соответствующих элементов матрицы, получим

Так как назначение не получено, вычёркиваем строку 2, столбцы 2, 4, 5:

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

Оптимальное решение, соответствующее последней матрице, равно

Суммарная производительность: 6 + 6 + 3 + 6 + 7 = 28.

Таким образом, на первом станке надо делать 5-ю операцию, на втором – 1-ю операцию, на третьем – 4-ю операцию, на четвёртом – 3-ю операцию, на пятом – 2-ю операцию. Суммарная производительность: 28 деталей в единицу времени.

(Во время фронтального решения задачи студенты, хорошо понявшие алгоритм решения, могут самостоятельно решать предложенные задачи.)

Задача 1. Фирма имеет три механизма А_1, А₂, А₃, каждый из которых может быть использован на каждом из трёх видов работ В_1, В₂, В₃ с производительностью, заданной матрицей (в условных единицах)

.

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

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

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

.

Распределить людей на работу так, чтобы выполнить её с максимальной производительностью.

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

.

Как следует распределить заказы по базам, чтобы общая дальность транспортировки была минимальной?

Задача 4. Фирма объединяет три предприятия, каждое из которых производит 3 вида изделий.

Себестоимости каждого вида изделия в усл. ед. при изготовлении на каждом предприятии указаны в матрице

.

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

Задача 5. Компания разрабатывает план выпуска трёх новых видов продукции. Она уже владеет пятью предприятиями, и теперь на трёх из них должна производиться новые виды продукции – по одному виду на одно предприятие.

Даны издержки производства продукции, усл. ед.:

Предприятия

Вид продукции .

Издержки сбыта единицы продукции, усл. ед.:

.

Плановый объём годового производства, который позволил бы удовлетворить спрос, и себестоимость единицы продукции каждого вида приведены в табл.

Вид продукции	Плановый объём производства, шт.	Себестоимость, усл. ед.

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

Ответы

1. Задача имеет два решения. Одно из них:

3. Задача имеет несколько решений Одно из них:

5.

5. Задача имеет несколько решений Одно из них:

4. Задача имеет несколько решений Одно из них:

Дата добавления: 2014-01-11