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

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

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

Таким образом, задача о назначениях имеет вид:

(1)

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

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

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

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

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

Для перевозки грузов мы можем задействовать множество автомобилей . Каждый j -й автомобиль характеризуется грузоподъемностью и затратами на использование , которую мы будем называть арендной платой. Мы предполагаем, что в арендную плату включены все затраты, которые не зависят от пробега, времени использования и т.д. Чтобы учесть пробег автомобиля, маршрут должен состоять не только из списка клиентов, но также из последовательности их объезда по строгому маршруту следования. Но для данной задачи этот подход не представляется целесообразным по следующим причинам.

1. Задача маршрутизации транспортных средств (Vehicle Routing Problem − VPR), представляет из себя одну из сложнейших задач целочисленного программирования и не существует эффективных методов решения таких задач большой размерности, которые возникают на практике.

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

3. В связи с постоянными изменениями ситуации на дорогах, оптимальные маршруты следования изменяются. Оперативно отслеживать эти изменения не представляется возможным в силу причин перечисленных выше.

4. Опыт практического решения данной задачи показывает, что в тех случаях, когда клиенты расположены компактно, эффект от решения оптимальной маршрутизации незначителен. Причем решение на момент использования может стать неоптимальным или даже недопустимым.

Далее, предполагаем, что все клиенты требуют, чтобы их заказы были доставлены не позднее некоторого времени, причем время перемещения между клиентами и время их обслуживания (погрузка, разгрузка, оформление документов) одинаково. Это ограничение можно выразить простейшим способом – заданием максимального числа клиентов в каждом рейсе, скажем, величиной L.

Рассмотрим математическую формулировку этой задачи.

Введем переменные , принимающие значение . Очевидно, что принимает значение 1, если i -й клиент включен в рейс j -го автомобиля, и значение 0, если i -й клиент не включен в рейс j -го автомобиля.

Введем дополнительные переменные , представляющие собой затраты на транспортировку на j -м маршруте, , принимающие значения:

и рассмотрим задачу

(2)

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

(3)

Целевая функция (2) равна реальным транспортным расходам. Первая группа ограничений в системе (3) нам гарантирует, что все клиенты будут обслужены. Вторая группа ограничений в (3) одновременно гарантируют обслуживание только арендованными автомобилями и удовлетворение условий грузоподъемности. Третья группа ограничений в (3) − ограничения на количество обслуживаемых одним автомобилем клиентов, которые косвенно учитывают ограничения по времени доставки, и, наконец, последние две группы ограничений – это условия двоичности переменных и . Данная задача относится к классу обобщенных задач о назначениях (Generalized Assignment Problem – GAP).