Задача о назначениях (о выборе)

Постановка задачи и математическая модель Найти оптимальное распределение п работ между т исполнителями при заданной матрице эффективности С = (су)тхп9 где Су - характеризует в количественной форме эффективность выполнения у-ой работы ((у = /-м исполнителем (i = im) при следующих условиях:

а) каждый исполнитель может выполнять только одну работу;

б) каждая работа может выполняться только одним исполнителем.

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

Обозначим переменные Ху - выполнение выполнения j-й работы /-м исполнителем.

Переменные Ху должны удовлетворять системе ограничений:

и целевой функции

Эти условия определяют особенности формулировки и методов решения задачи о назначениях, которые сводятся к следующему.

  • 1. Суммы по строчкам и столбцам равны 1. Именно по этой причине задача вырождена.
  • 2. Переменные Ху могут принимать значение либо 1, либо 0. В противном случае теряется смысл задачи.
  • 3. Число строк должно быть равно числу столбцов, то есть работ должно хватить на всех исполнителей. Если это условие не выполняется, вводят фиктивные строку или столбец.

В силу вырожденное™ для решения задачи о назначениях лучше использовать компьютерные расчеты.

Задача 10.4

Пять работников швейного цеха учреждения УИС с номерами У;, N5 способны выполнить пять технологических операций с номерами Р/, p2v, Ps- В силу разной квалификации и профессиональных навыков на выполнение этих операций им потребуется различное время (табл. 10.4). Так, работник Р5 быстро и качественно выполняет все операции, кроме операции N3, а работник Р4 имеет довольно низ

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

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

Таблица 10.4

Время выполнения технологических операций работниками, мин

Технологические операции

Работники

Pi

р2

Рз

р4

р5

N,

21

26

27

29

20

n2

20

23

24

22

18

N3

22

25

26

27

24

N4

12

15

17

14

10

N5

15

13

19

16

12

Решение. Обозначим Ху - участие (1) либо неучастие (0) i-го работника в выполнении у'-ой технологической операции, а Су - время выполнения /-м работником у-й операции (у = й) (/ = й).

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

Условия, которым должны удовлетворять переменные Ху, можно разделить на две группы:

1) все технологические операции должны быть выполнены:

2) каждый работник должен быть задействован на выполнении отдельной операции:

3) условия неотрицательности переменных:

Критерий оптимальности - суммарное время выполнения работниками технологических операций - необходимо минимизировать:

Решение задачи о назначениях в Ms Excel

Рис. 10.3. Решение задачи о назначениях в Ms Excel

Результаты решения задачи 10.4 представлены на рисунке 10.3. По оптимальному плану минимум суммарного времени на выполнение всех технологических операций составит 92 минуты. Операции между работниками распределились следующим образом: работник Pj выполняет операцию работник Р2 выполняет операцию N5; работник Р3 выполняет операцию N3; работник Р4 выполняет операцию N2; работник Р5 выполняет операцию N4.

Отчет по устойчивости, полученный с оптимальным решением задачи, содержит двойственные оценки переменных (нормированные стоимости). Оценки переменных, вошедших в оптимальное решение, равны нулю. Переменные, которые не вошли в план, получили значимые положительные значения, варьирующие от 1 до 6. При корректировке оптимального решения можно ввести в план переменные с наименьшей нормированной стоимостью. Значение целевой функции при этом, конечно, увеличится, но несущественно. Так, оценки переменных х12 и х13 равные 1. Если ввести их в план, то есть поручить операцию Njработникам Р2 или Р3, то значение функционала увеличится на 1 минуту.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >