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

Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i = 1,., m), выполняемая на станке j (j = 1,., n), связана с затратами c_ij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки — «пункты назначения». Предложение в каждом исходном пункте равно 1, т. е. a_i = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т. е. b_j = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна c_ij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость c_ij берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:

Прежде чем решать такую задачу, необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.

Пусть x_ij = 0, если j-я работа не выполняется на i-ом станке, x_ij = 1, если j-я работа выполняется на i-ом станке.

Таким образом, решение задачи может быть записано в виде двумерного массива.

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

Теперь задача будет формулироваться следующим образом:

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

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

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

Оптимальное назначение:

Практическая часть.

1. Решение задачи с помощью прикладной программы Excel.

Условие задачи.

Пусть производство продукции осуществляется на 4-х предприятиях А₁, А₂, А₃, А₄ а затем развозится в 5 пунктов потребления этой продукции B₁, B₂, B₃, B₄, B₅. На предприятиях A_i (i = 1, 2, 3,4) продукция находится соответственно в количествах a_i (условных единиц). В пункты B_j (j = 1, 2, 3, 4,5) требуется доставить b_j единиц продукции. Стоимость перевозки единицы груза (с учетом расстояний) из A_i в B_j определена матрицей.

Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Стоимость перевозки единицы продукции (в у. е.) с предприятий в пункты потребления приведена в таблице.

Таблица 1. Условие задачи.

Требуется минимизировать суммарные транспортные расходы по перевозке продукции.

Необходимо выполнить следующее:

• 1. Установить, является ли модель транспортной задачи, заданная таблицей, сбалансированной.
• 2. Разработать математическую модель задачи.
• 3. Найти минимальную стоимость перевозок, используя надстройку «Поиск решения» в среде MS Excel.

Решение:

1. Выполним проверку сбалансированности математической модели задачи. Модель является сбалансированной, так как суммарный объем производимой продукции в день равен суммарному объему потребности в ней:

=235+175+185+175; = 125+160+60+250+175.

• 175=175
• 2. Приступим к построению математической модели поставленной задачи. Неизвестными будем считать объемы перевозок.

Пусть х_ij — объем перевозок с i-го пункта поставки в j-й пункт потребления.

Суммарные транспортные расходы — это функция.

где сij — стоимость перевозки единицы продукции с i-го предприятия в j-й пункт потребления .

Неизвестные в этой задаче должны удовлетворять следующим ограничениям:

• 1. Объемы перевозок не могут быть отрицательными, т. е. ;
• 2. Поскольку модель сбалансирована, то вся продукция должна быть вывезена с предприятий, а потребности всех пунктов потребления должны быть полностью удовлетворены, т. е.

и .

Итак, имеем следующую функцию ЛП.

• 3. Приступаем к решению задачи на компьютере в программе Excel.
• 3.1 Откроем новый рабочий лист Excel.
• 3.2 В ячейки B3: F6 стоимость перевозок единицы груза.
• 3.3 В ячейках B16: F16 укажем формулы для расчета суммарной потребности продукции для j-го пункта, в ячейках G12: G15 — формулы суммарного объема производства i-го предприятия.
• 3.4 В ячейки B18: F18 заносим значения потребности продукции соответствующего пункта потребления, в ячейки H12: H15 заносим значения объема производства соответствующего предприятия.
• 3.5 В ячейку B20 занесем формулу целевой функции.

Рисунок 1. Условие задачи в программе Excel.

• 3.6 Выполним команду «Поиск решения». Откроется диалоговое окно «Поиск решения» .
• 3.7 В поле «Установить целевую ячейку» указываем ячейку, содержащую оптимизируемое значение. Установим переключатель Равный в положение минимальному значению.
• 3.8 В поле «Изменяя ячейки» мышью зададим диапазон подбираемых параметров $B$ 12: $F$ 15.
• 3.9 В поле «Ограничения» введем необходимые ограничения и нажмем на кнопку «Добавить», затем «Выполнить» .

Рисунок 2. Поиск решения.

Рисунок 3. Готовое решение.