Часть II issn 2072-0297

 2

---

151
“Young Scientist” .  #7 (66) .  May 2014
Technical Sciences
Задача о простом назначении. В выполнении n работ участвуют m человек, каждый из которых может выполнять 
лишь определенные работы из указанных. Требуется распределить работы, исходя из их специальностей, не допуская 
при этом выполнение одной и той же работы разными людьми. Укажем необходимые условия, при которых возможно 
такое назначение. Каждый должен иметь, по крайней мере, одну специальность; каждая пара должна иметь две раз-
личные специальности. Каждая группа из трех (или k) человек должна быть в состоянии выполнять, по меньшей мере, 
три (или k) различных работ. Иначе цель не может быть достигнута. Справедливо утверждение: назначение возможно 
тогда и только тогда, когда каждая группа в состоянии выполнять достаточное число работ; если группа 
состоит из k человек, то вместе они должны быть в состоянии выполнять, по меньшей мере, k работ.
На первый взгляд условие выглядит слабым: один квалифицированный человек в состоянии помочь всей группе вы-
полнить k работ. Однако это условие относится к каждой группе, включая и те, в которых этот человек не состоит. Если 
распределение работ невозможно, то всегда можно найти группу, для которой это условие выполняется. Начнем с кон-
струирования сети, имеющей пропускную способность m между каждым человеком и работами, которые он может вы-
полнять (исполнители подключаются к источнику, а работы — к стоку при помощи дуг с пропускной способностью 
J
; 
рис. 3).
Рис.
 3
Если суммарный поток станет m, то все дуги от источника будут заполнены, и все будут иметь работу. Если макси-
мальный поток окажется меньше m, то существует разрез с пропускной способностью меньше m, например, такой, 
что в группе S содержатся источник и узлы J
1
,…,J
k
. j
1
,…j
n
. Ни один из этих k человек не в состоянии выполнять другие ра-
боты. Иначе нашлась бы дуга с пропускной способностью m, пересекающая разрез. Так что пропускная способность 
разреза равняется m-k (от источника к оставшимся людям) плюс l (от этих работ к стоку), что в сумме даст m-k+l; это 
величина будет меньше m при 
k
l <
. Следовательно, определится группа из k человек, которая может выполнять лишь 
k
l <
работ. Если назначение окажется невозможным (поток оказался меньше m), то какая-то группа людей сдержи-
вает его.
Приведенные сетевые модели эффективно использовались при разработке информационных моделей человека-
оператора эргатической системы (как многоканальной системы управления; [5…7]).
Литература:
1. Данилов, А. М., Гарькина И. А., Домке Э. Р. Математическое и компьютерное моделирование сложных си-
стем. — Пенза: ПГУАС. — 2011. — 296 с.
2. Данилов, А. М., Домке Э. Р., Гарькина И. А. Формализация оценки оператором характеристик объекта управ-
ления / Информационные системы и технологии. — 2012. — № 2. — с. 5–10.
3. Будылина, Е. А., Гарькина И. А., Данилов А. М. Декомпозиция динамических систем в приложениях / Регио-
нальная архитектура и строительство. — 2013. — № 3. — с. 95–100.

---