7.3 Оптимизация задач распределения работ

Задача 2. На производстве возникают задачи распределения m работников для выполнения n видов работ таким образом, чтобы при известной продуктивности труда (или стоимости) с_ij i- м работником на j- й работе получить оптимальное решении, например, максимальную общую продуктивность работы; или минимальную суммарную стоимость выполненных работ при соблюдении имеющихся ограничений.

Задачи такого типа называют задачами с целочисленными булевыми переменными, так как в результате их решения искомые переменные х_ij могут принимать только одно из двух значений: 0 или 1. Это свойство переменных учитывают на этапе создания экранной формы для применения средства Поиск решения и при формировании набора ограничений к задаче.

Математическая модель оптимизации распределения работ похожа на модель транспортного типа:

Целевая функция: С = ∑ ∑ x_ij * с_ij → mах

Ограничения: ∑ x_ij = 1, ∑ x_ij = 1, i = 1, 2, 3, ... ,n;

j = 1, 2, 3,…, m; x_ij – целые; x_ij > = 0.

Но модель оптимизации распределения работ имеет и некоторые особенности:

- функция цели направлена к максимуму – общая продуктивность труда должна быть максимальная;

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

- каждая работа рассматривается как «потребитель» по отношению к работнику, требует загрузки только одного работника; но при этом все работы должны быть выполнены;

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

Технология подготовки решения задачи к оптимизации

1. Запускаем Excel. В ячейки Рабочего листа заносим: в диапазон клеток B4:F8 – исходные данные C_ij - продуктивность труда i-го работника, если он будет выполнять работу J (см. Рис.7.4).

2. Выделяем ячейки искомой матрицы распределения работ - клетки В11:F15 – зона искомых переменных x_ij, которым первоначально присваиваем начальные нулевые значения.

3. Формула целевой функции =СУММ(G4:G8) закрепляется за ячейкой G9. В диапазон клеток G4: G8 заносим формулы:

→ G4 =СУММПРОИЗВ(B4:F4; B11:F11), и далее копируем аналогичные формулы на диапазон клеток G5: G8.

4. В зоне ограничений в клетки Н11:Н15 вводим значения правых частей ограничений в строках, которые по условию должны быть равны единице. В диапазон ячеек G11: G15 вводим формулы для левых частей ограничений. В ячейку → G11 заносим формулу = СУММ(B11: F11) и далее ее копируем на диапазон клеток G12: G15.

5. Аналогичные действия выполняем для ввода на рабочий лист ограничений по столбцам. В диапазон клеток B17: F17 вводим значения правых частей ограничений (по условию они также должны быть равны единице). В клетки B16: F16 вводим формулы для левых частей ограничений по столбцам:

→ B16 =СУММ(В11: В15), далее эту формулу копируем на диапазон ячеек С16: F16.

6. Устанавливаем курсор на клетку целевой функции → G9 и задаем команду Сервис – Поиск решения. Заполняем диалоговое окно «Поиск решения» следующими данными (см. рис.7.5).

Рисунок 7.4. Фрагмент Рабочего листа MS Exсel с исходными данными

для оптимизации распределения работ

Рисунок 7.5. Диалоговое окно для задания параметров оптимизации

Первые три ограничения показывают, что искомые переменные должны быть целыми и булевыми – принимать значения только равные 0 или 1. Нажимая на кнопку «Выполнить» получаем на Рабочем листе результаты решения задачи (см. рис.7.6). Значение целевой функции – 22 единицы.

Рисунок 7.6. Результат оптимизации распределения работ