<<
>>

ЗАДАЧА О НАЗНАЧЕНИЯХ

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

Возможные применения задачи о назначениях представлены в таблице.

Матрица стоимостей С имеет вид

где cij — затраты, связанные с назначением i–го ресурса на j–й объект, i = j = , где п — число объектов или ресурсов.

Обозначим:

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

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

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

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

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

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

Задача о назначениях является частным случаем транспортной задачи, в которой ai = bj = 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:

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

Ответ.

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

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

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

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

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

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме ЗАДАЧА О НАЗНАЧЕНИЯХ:

  1. 1.1. Понятие, задачи и система уголовного права
  2. 2 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  3. 2П ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  4. 2.1. ЗАДАЧИ О НАЗНАЧЕНИИ
  5. Задача распределения функций.
  6. 3.2. Средства решения образовательных, развивающих и воспитательных задач
  7. 8.1. Постановка задачи
  8. 8.3. Усложненные задачи транспортного типа
  9. § 67, Транспортная задача
  10.   ЗАДАЧИ ПОЗИТИВИЗМА И ИХ РЕШЕНИЕ 1868  
  11. Цели и задачи судебно-экспертного исследования.
  12. ПРОБЛЕМНОЕ ПОЛЕ И ЗАДАЧИ ФИЛОСОФИИ ТЕХНИКИ
  13. ОБЩИЕ ПРОБЛЕМЫ И ЗАДАЧИ ИЗУЧЕНИЯ ЯЗЫКА РУССКОЙ ХУДОЖЕСТВЕННОЙ ЛИТЕРАТУРЫ
  14. О ЗАДАЧАХ ИСТОРИИ ЯЗЫКА*
  15. ЗАДАЧИ УГОЛОВНОГО ПРАВА
  16. Приложение транспортных моделей к решению некоторых экономических задач