Постановка задачи о назначениях

Сделаем содержательную постановку задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Q_i тонн груза (i = 1,2,…,n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве R_j тонн в месяц (j = 1,2,…,n).
Распределить автомобили по маршрутам так, чтобы минимизировать суммарную величину неиспользуемой провозной способности. Конкретизируем задачу (рис. 1). Пусть имеется 4 автомобиля и 4 маршрута. Характеристики провозных способностей автомобилей соответственно равны Q₁ = 30 т., Q₂ = 35 т., Q₃ = 5 т., Q₄ = 5 т. Характеристики потребностей потребителей соответственно равны R₁ = 25 т., R₂ = 32 т., R₃ = 5 т., R₄ = 4 т. Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Понятно, если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составим матрицу С, характеризующую издержки i -го автомобиля, в случае, если он будет назначен на j -й маршрут. Элементы маршрута будут равны:

Рис. 1 - Схема маршрутов

В таблице 1 приводятся оценки возможных транспортных издержек.
Таблица 1 - Оценки транспортных издержек

Сделаем математическую постановку задачи о назначениях.
Переменные. В качестве переменной введем величину

Ограничения. Каждый автомобиль i должен быть назначен только один раз на любой из маршрутов.
или.
На каждый маршрут j должен быть назначен один из автомобилей
или.
Целевая функция. В качестве целевой функции, подлежащей минимизации, выступают суммарные издержки на перевозку.
Модель задачи о назначениях примет вид:

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

Все предполагаемые алгоритмы поиска решения задачи о назначениях базируются на следующем утверждении: оптимальное решение задачи не изменится, если к любой строке или столбцу матрицы издержек прибавить (или вычесть) постоянную величину в силу того, что приоритет назначения не изменится. И весь алгоритм ведется на матрице издержек с соответствующими преобразованиями для получения в ней нулевых элементов, образующих систему так называемых «независимых нулей». Число независимых нулей равно размерности матрицы, а их расположение таково, что каждый из них встречается один раз в строке и один раз в столбце. Если такие независимые нули будут найдены, то в матрице решения в соответствии с их положением будут проставлены единицы. В матрице 1 нулевые элементы получены вычитанием наименьшего элемента в каждой строке.

(1)

Как только будут получены нулевые элементы, применяют различные алгоритмы: Мака, венгерский, минимальных линий. Рассмотрим процедуру вычеркивания нулевых элементов минимальным числом прямых линий. В матрице 2 показано, как используется это правило. Могут быть и другие варианты вычеркивания.

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

Значение целевой Z = 5 + 3 + 0 + 1 = 9. Оптимальное решение можно было получить и сразу, не применяя процедуру вычеркивания нулей, если в матрице 2 из столбца 4 вычесть минимальный элемент. Сделано было иначе только для демонстрации процедуры вычеркивания.

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

15 вопрос.