VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

Данная задача носит название «задача о назначениях» и является частным случаем более общей транспортной задачи. Если число исполнителей равно числу выполняемых работ, то такая задача является сбалансированной, в противном случае - не сбалансированной. В случае сбалансированной задачи о назначениях выполняются два условия: каждый исполнитель выполняет только одну работу и каждая работа выполняется только одним исполнителем.

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

Рассмотрим следующий пример: имеется четыре исполнителя (И), которых необходимо распределить для выполнения четырех работ (Р) таким образом, что бы минимизировать суммарную себестоимость выполнения всех работ. Матрица себестоимостей С_4х4 имеет вид:

	Р1	Р2	Р3	Р4
И1	75	30	10	25
И2	20	35	40	50
И3	15	55	70	65
И4	25	30	20	100

Суммарная себестоимость выполнения всех работ, найденная по предложенному алгоритму, составила 10+20+55+100=185 условных единиц.

	Р1	Р2	Р3	Р4
И1	75	30	10	25
И2	20	35	40	50
И3	15	55	70	65
И4	25	30	20	100

 

При этом видно, что назначение на первых шагах исполнителя И₁ на работу Р₃, а исполнителя И₂ на работу Р₁ и т. д. привело к тому, что на последнем шаге нам "пришлось"  назначить исполнителя И₄ на работу Р₄ с максимальным значением себестоимости с_ij.

Получаемое значение суммарной себестоимости зависит при этом от порядка, в котором мы выполняем наши назначения. Если, при той же матрице себестоимости, мы будем выполнять последовательные назначения начиная с исполнителя И₄, то суммарная себестоимость составит уже 20+15+35+25=95 условных единиц, что демонстрирует следующая матрица

	Р1	Р2	Р3	Р4
И1	75	30	10	25
И2	20	35	40	50
И3	15	55	70	65
И4	25	30	20	100

 

Таким образом, алгоритм «выбирай на каждом шаге самого эффективного (неэффективного)» не может использоваться при принятии управленческих решений.

Решим задачу о назначениях с помощью электронных таблиц MS Excel, используя надстройку «Поиск решения», сформулировав ее как задачу линейного программирования.

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

1.     Определим неизвестные и их количество.

Рассмотрим переменные x_ij, которые равны 1, если i-й исполнитель назначен на выполнение j-ой работы  и  0, если он не назначен i=1,2,...,n j=1,2,...,n. Таким образом, значения x_ij образуют матрицу назначений X_nxn, состоящую из нулей и единиц.

2.     Запишем критерий оптимизации (целевую функцию) - суммарную эффективность (неэффективность) выполнения всех работ.

Целевая функция задачи о назначениях зависит от неизвестных пока переменных  x_ij и известны значений с_ij - эффективности (неэффективности) выполнения i-м исполнителем j-ой работы и запишется в следующем виде

3.     Сформулируем ограничения рассматриваемой задачи.

а) каждый исполнитель выполняет только одну работу. Выполнение данного условия означает, что каждая строка матрицы назначений Х содержит только одно значение равное единицы, а все остальные равны нулю. Т.е. сумма элементов каждой строки матрицы назначений Х равна 1, и это ограничение можно записать в виде системы n уравнений

или в общем виде

б) каждая работа выполняется только одним исполнителем. Выполнение данного условия означает, что каждый столбец матрицы назначений Х содержит только одно значение равное единицы, а все остальные равны нулю. Т.е. сумма элементов каждого столбца матрицы Х равна 1, и это ограничение можно записать в виде системы n уравнений

или в общем виде

 

в) двоичность (бинарность) переменных x_ij. Так как областью допустимых изменений каждой переменной являет­ся не множество целых неотрицательных чисел, а конечное множество (0,1)

   (4)

то мы получаем дискретную задачу оптимизации.

Таким образом, целевая функция (1) и ограничения (2-4) составляют математическую модель сбалансированной задачи о назначениях.

Решим пример, приведенный выше, с помощью ЭТ MS Excel, для чего:

1.     Запишем матрицу себестоимостей С_4х4.

2.     Сформируем матрицу назначений Х_4х4 с пока нулевыми значениями переменных x_ij.

3.     Дополним матрицу назначений Х4х4 столбцом справа и строкой снизу, в ячейки которых запишем формулу суммировании элементов строк и столбцов матрицы Х. Это понадобится нам при учете ограничений (2) и (3) задачи. При этом возможно использование кнопки «Сумма»

4.     Используя формулу (1), запишем целевую функцию - суммарную себестоимость выполнения всех работ. При этом возможно использование встроенной функции MS Excel «СУММПРОИЗВ».

 Т.к. все переменных x_ij пока равны нулю, то и вычисленное значение целевой функции - ноль.

Лист MS Excel с исходными данными для решения представлен ниже.

 

5.     С помощью команды Главного меню «Данные» вызвать диалоговое окно надстройки «Поиск решения» и выполнить необходимые установки.

 

6.     Щелчком по кнопке «Выполнить» запустить надстройку и сохранить полученное решение.

 

Анализ полученного решения показывает, что оно в точности совпадает с решением, полученным по алгоритму «выбирай на каждом шаге самого эффективного (неэффективного)», когда мы начали назначения с исполнителя И₄. Это говорит о том, что возможно интуитивное принятие оптимального решения, однако при увеличении размерности задачи и возрастании цены ошибки целесообразно применение математических методов и ЭВМ для принятия управленческих решений.

Рассмотрим теперь решение не сбалансированной задачи о назначениях, когда число исполнителей n не равно числу выполняемых работ m. При этом возможны два случая:

1)    число исполнителей n больше числа выполняемых работ m (n > m),

2)    число исполнителей n меньше числа выполняемых работ m (n < m).

В обоих случаях для решения не сбалансированной задачи ее сводят к сбалансированной, путем введения фиктивных работ или фиктивных исполнителей с нулевыми значениями с_ij - эффективности (неэффективности) выполнения i-м исполнителем j-ой работы. В первом случае, когда n > m, вводится k = n - m фиктивных работ P_m+1, P_m+2, ..., P_m+k. Во втором случае (n < m) - рассматриваются k = m - n фиктивных исполнителя И_n+1,И_n+2, ..., И_n+k.

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

 Анализ полученного решения показывает, что исполнители И₂ и И₅  к работам не допущены (назначены на выполнение фиктивных работ Р₅ и Р₆ соответственно). Оставшиеся исполнители обеспечили выполнение четырех работ с минимально возможной суммарной себестоимостью 10+15+30+30=85 условных единиц.

Рассмотрим последнюю задачу о назначениях, когда четыре исполнителя претендуют на выполнение шести работ (n < m). Лист MS Excel с исходными данными и  диалоговым окном надстройки «Поиск решения» представлены ниже.

 Анализ представленного ниже решения показывает, что работы Р₄ и Р₆ не выполняются, а четыре исполнителя распределены по оставшимся четырем работам таким образом, что минимальная суммарная себестоимость составила  10+20+10+30=70 условных единиц.

 

Код для цитирования: Скопировать