Содержание к диссертации
Введение
2. Задача о равномерном назначении. Формулировка и обобщения . 9
3. Задача о равномерном назначении работ относительно матрицы обязательных назначений 14
3.1. Постановка задачи 14
3.2. Постановка Л/-задачи 15
3.3. Характеристическое свойство решения задачи РНМО 20
4. Задача о равномерном назначении работ относительно вектора желательных назначений . 27
4.1. Постановка задачи 27
4.2. Эквивалентность задач РНОВ и РНМО 28
4.3. Взаимное сведение и обобщение задач РНМО и РНОВ. 31
5. Задача о равномерном назначении минимальной стоимости . 35
6. План равномерного назначения работ. 38
6.1. Определение и основные свойства плана назначений . 38
6.2. Основное свойство плана равномерного назначения работ 39
7. Задача о минимальной стоимости равномерного назначения работ 43
7.1. Решение задачи МСРН для однокомпонентного плана 43
7.2. Решение задачи МСРН для двухкомпонентного плана 47
7.3. Свойства решения задачи МСРН 56
Заключение. 73
Литература 74
- Характеристическое свойство решения задачи РНМО
- Эквивалентность задач РНОВ и РНМО
- Определение и основные свойства плана назначений
- Решение задачи МСРН для двухкомпонентного плана
Введение к работе
Диссертационная работа посвящена изучению некоторых обобщений задачи о назначениях - одной из классических задач дис7 кретной математики. Классическая задача о назначениях формулируется следующим образом. Имеется конечное число исполнителей каждый из которых должен быть занят в некоторый из дней C?l,C?2j ->dn.
Стоимость занятости в день dj исполнителя Ь{ равна Cjj. Нужно распределить исполнителей по дням, то есть назначить по одному работнику на каждый день так, чтобы, во-первых, были заняты все дни и, во-вторых, минимизировать затраты. Данная задача широко исследована в работах таких известных математиков как Х.Кун (см. [28]), Н.Кристофидес (см. [11]), Э. Эгервари (см. [24]) и многих других. Были получены эффективные алгоритмы решения классической задачи о назначениях, в частности Венгерский метод решения, усовершенствованная схема алгоритма глобального поиска для квадратичной задачи о назначениях приведена в работах Васильева И.Л. и Киселева В.Д. (см. [2], [7]). Многие задачи дискретной оптимизации, сводятся к классической задаче о назначениях, классификации таких задач посвящены работы Abreu N., Netto Р., (см. [20]) Angel Е. (см. [21]-[23]), Korvin А. (см. [26], [27]) и других. Кроме того были сформулированы и исследованы свойства различных ее обобщений, которые невозможно свести к классической, и решение которых не является тривиальным.
Одним из таких обобщений является задача альтернативного распределения разнотипных средств (АРРС) исследованная Коротким Ю.Г. Селютиным В.А. и др. (см.[4], [9], [10], [17]). Внешне ее постановка близка к классической задаче о назначениях, в которой количество исполнителей и работ одинаково. Отличие задачи АРРС состоит в разрешении неоднократного назначения исполнителей, т.е. совместительства. Это разветвляет структуру множества возможных значений и увеличивает его мощность, что принципиально усложняет задачу. Разработан алгоритм решения задачи АРРС, дающий конечное точное решение. Он относится к классу "ветвей и границ". Общая идея метода состоит в последовательном разбиении исходного множества решений на подмножества с последующими оценкой и отбрасыванием неперспективных, выделении перспективных подмножеств и в дальнейшем их расчленении. В диссертационной работе также рассматривается задача о назначениях с возможностью совместительства.
Исследовались различные частные случаи задачи о назначениях. Например, в работах Воскресенского Е.А., Добровольского Н.М. и Симонова А.С. (см.[3]) исследуется задача о назначения следующего вида. Имеется квадратная матрица размерности пхп такщ чисел, что любой их набор из п чисел, составленный по одному числу из каждой строки и столбца, имеет одну и туже сумму. Требуется найти алгоритм получения набора, имеющего наименьшую дисперсию среди всех возможных наборов, при условии, что числа, стоящие в строках и столбцах матрицы, образуют арифметическую прогрессию. В диссертационной работе также рассматривается квадратичное отклонение от средней занятости, но по отношению к числу работ, назначенному каждому исполнителю.
Многие обобщения задачи о назначениях формулируются в виде практических заданий, их решение ищется исходя из специфических условий работы предприятия или организации. Большое количество обобщений классической задачи о назначениях исследованы в работах Стрекаловского А.С. (см. [18]), Кузнецовой А.А. (см. [12]) (квадратичная задача о назначениях); Козловского В.А., Козловского Э.А. (см. [8]); Кумагиной Е.А., Прилуцкого М.Х. (за- дача распределения ресурсов)(см. [13], [14], [15]),Ямпольского Л.С., Бондаренко В.Н. (см. [1], [19]) и других.
Суть обобщения, рассмотриваемого в данной диссертационной работе, заключается в том, что исполнитель может быть занят несколько дней (число исполнителей и дней может не совпадать), но выполнение работ должно быть распределено между исполнителями примерно одинаково. Отсюда возникла задача построения равномерного назначения, то есть необходимо распределить весь объем работы между исполнителями так, чтобы каждый работник выполнял примерно одинаковый объем работ и при этом затраты на выполнение всего объема были минимальны. В качестве критерия равномерности чаще выбирают минимизацию среднеквадратичного отклонения от средней занятости, хотя могут быть рассмотрены и другие критерии (например, минимизация максимального отклонения от средней занятости исполнителей). Введение сразу двух функционалов оптимизации приводит к тому, что такие задачи не удается свести к классической задаче о назначениях. Более того, не во всех задачах присутствует или является приоритетным функционал стоимости. Свойства задачи о равномерном назначении работ и алгоритм ее решения были представлены Рублевым B.C. (см.[16]). Было доказано, что критерий минимизации среднеквадратичного отклонения от средней занятости является более сильным по сравнению с другими критериями равномерности. Им же были сформулированы обобщения задачи о равномерном назначении, исследованию которых посвящена диссертационная работа.
В зависимости от того, какая из характеристик - минимальность стоимости или равномерность назначения является приоритетной, формулируются различные задачи. Если приоритетной является равномерность, то формулируется задача о минимальной стоимости равномерного назначения (МСРН), если на первом месте минимальность стоимости, то - задача о равномерном на- значении работ минимальной стоимости (РНМС). Основной сложностью в задаче МСРН является сохранение минимальной стоимости при оптимизации равномерности назначения. Исследование этой задачи привело к формулировке новых обобщений задачи о назначениях, частным случаем одного из которых является задача МСРН. А именно, были сформулированы задачи о равномерном назначении относительно обязательных назначений (РНМО) и равномерном назначении относительно вектора желательных назначений (РНОВ).
Задача РНМО состоит в нахождении равномерного назначения при условии, что некоторые исполнители обязательно должны выполнять конкретные работы. К этой задаче легко сводится задача МСРН, существует полиномиальный алгоритм сведения, а для ре: шения задачи РНМО существует алгоритм полиномиальной трудоемкости, основанный на сведении к максимальному потоку в двудольном графе.
Задача РНОВ является еще одним "естественным" обобщением задачи о равномерном назначении. Задается вектор, в котором для каждого работника указан объем работ, который он должен был бы выполнить. Требуется построить такое назначение, чтобы каждый работник выполнял объем работ, наиболее приближенный к желательному. Решение этой задачи состоит в сведении ее к задаче РНМО, представлен эффективный алгоритм сведения.
Задача РНМС решена для двух частных случаев - однокомпонентного и двукомпонентного планов распределения. Представлены полиномиальные алгоритмы решения задачи РНМС для двух-компонентного и однокомпонентного планов.
Все указанные обобщения задачи представляют большой практический интерес. Например, на предприятии нередко возникает необходимость в планируемый период так распределить бригады, чтобы себестоимость производимой продукции была возможно меньшей, при этом бригады были нагружены равномерно с уче- том их графиков работы в планируемый период (учет некоторых обязательных назначений) и загруженности в предшествующий период (учет желательного количества назначений). Отсутствие четких и эффективных алгоритмов решения таких задач приводит либо к выбору неоптимального решения, либо к значительным временным затратам, связанным с перебором. Поэтому построение эффективных алгоритмов решения всех указанных задач является актуальным и составляет одну из целей работы. Другой целью является исследование свойств описанных задач, обосновывающих эффективность алгоритмов решения.
В диссертационной работе формулируются и исследуются свойства и строятся алгоритмы решения для обобщений задачи о равномерном назначении работ, частным случаем которых являются результаты исследований Рублева B.C.
В главе 2 представлены постановки задач, рассматриваемые в диссертационной работе, введены основные обозначения.
Характеристическое свойство решения задачи РНМО
Теорема 2.1» Матрица назначений X является решением задачи РНМО тогда и только тогда, когда любая ее Al-срезка является решением А1-задачи. Доказательство. Необходимость. Пусть матрица Z - решение задачи РНМО. Тогда для любой ее Л/-срезки выполняются условия (2),(9),(10),(11), то есть любая Л-срезка является матрицей назначений /-задачи. Остается показать, что Л/-срезка матрицы Z максимизирует значение функционала (12). Предположим противное. Пусть матрица X является А1 -срезкой исхо нет восстанавливаемых элементов (гги1 = 1) и элемент %\xjx будет как раз лишней единицей. Так как до восстановления (это следует из (13) — (14)), то при восстановлении найдется строка р, для которой Xpjx = 0 и zpjx = 1. Образуем матрицу ТУ, заменив, элемент vPjl на 0, то есть 2 случай: q 1 и Ziqjq = 1. Заметим, что в случаях 2 и 3 не относятся к восстанавливаемым элементы Vitjt(\/t Є l,g — 1), по скольку количество единиц матрицы X в столбцах jt (Vt q) рав но Sjv а если бы при получении матрицы X элемент Z(tjt (\/t q) был заменен на 0, то количество единиц в столбце jt матрицы X стало бы меньше Sj, что противоречит (17). Поэтому при восста новлении единицы в строках it(t Є 2,q — 1) количество единиц не изменится, то есть После восстановления количество единиц в столбце jq ровно Sjt, а в строке ip уменьшится, так как Vjqjq_l = &ziqjq-i = ! Поэтому для этого случая можно взять W = V и р = q. 3 случай: q 1 и Ziqjq = 0. После восстановления количество единиц в столбце увеличится на 1 (станет больше Sjq). Следователь но, найдется строка с номером р, такая, что элемент vPjq восста навливается (то есть xpjq — 0, a zPjq = 1). Образуем W, заменив элемент vpjq на 0, то есть Итак, во всех случаях построено требовавшееся преобразование к матрице W. Необходимость доказана. Достаточность. Пусть матрица назначений X удовлетворяет свойству оптимальности ее Л/-срезок для соответствующих А1-задач, а матрица Z является решением задачи о равномерном рас писании работ. Обозначим через щ(У) (г = 0,1,2,...) количество строк матрицы У из 0 и 1дной матрицы Z, причем в матрице X число ее ненулевых элементов не максимально. В этом случае для данной матрицы можно построить цепочку элементов (13) с выполнением для нее условий (14) — (17).
Построим матрицу У, используя преобразование матрицы (18). Далее мы покажем, как построить преобразование матрицы Y в матрицу W, которая является матрицей назначения и, для которой количество единиц в любой строке, кроме двух (с номерами i\ и некоторым р) такое же, как и для матрицы Z, а для выделенных строк выполняются условия: Таким образом, мы получили, что }{W) f(Z), и, следовательно, Z не минимизирует функционал /, что противоречит предположению о равномерности назначения. Для построения матрицы W образуем из матрицы Y матрицу V, восстановив все единицы, замененные на нули при получении Л/-срезки, то есть поскольку в строке і\ нет восстанавливаемых элементов (гги1 = 1) и элемент %\xjx будет как раз лишней единицей. Так как до восстановления (это следует из (13) — (14)), то при восстановлении найдется строка р, для которой Xpjx = 0 и zpjx = 1. Образуем матрицу ТУ, заменив, элемент vPjl на 0, то есть 2 случай: q 1 и Ziqjq = 1. Заметим, что в случаях 2 и 3 не относятся к восстанавливаемым элементы Vitjt(\/t Є l,g — 1), по скольку количество единиц матрицы X в столбцах jt (Vt q) рав но Sjv а если бы при получении матрицы X элемент Z(tjt (\/t q) был заменен на 0, то количество единиц в столбце jt матрицы X стало бы меньше Sj, что противоречит (17). Поэтому при восста новлении единицы в строках it(t Є 2,q — 1) количество единиц не изменится, то есть После восстановления количество единиц в столбце jq ровно Sjt, а в строке ip уменьшится, так как Vjqjq_l = &ziqjq-i = ! Поэтому для этого случая можно взять W = V и р = q. 3 случай: q 1 и Ziqjq = 0. После восстановления количество единиц в столбце увеличится на 1 (станет больше Sjq). Следователь но, найдется строка с номером р, такая, что элемент vPjq восста навливается (то есть xpjq — 0, a zPjq = 1). Образуем W, заменив элемент vpjq на 0, то есть Итак, во всех случаях построено требовавшееся преобразование к матрице W. Необходимость доказана. Достаточность. Пусть матрица назначений X удовлетворяет свойству оптимальности ее Л/-срезок для соответствующих А1-задач, а матрица Z является решением задачи о равномерном рас писании работ. Обозначим через щ(У) (г = 0,1,2,...) количество строк матрицы У из 0 и 1, содержащих ровно і единиц. Тогда Для доказательства достаточно показать, что так как в этом случае Из формулы (22) будет следовать, что f(X) = f(Z), что и требуется. Обозначим через pi[X) количество единиц А /-срезки матрицы X. Из доказанного условия необходимости следует pi(X) = Pi(Z). Поскольку значения Рі{Х) не убывают при увеличении /, то найдется значение / = 1тах Для которого Отсюда следует, что что доказывает справедливость равенства (23). Поскольку при / = 2,3,... Л(1 — 1)-срезка А /-срезки матрицы X является А(1 — 1)-срезкой матрицы X, то справедливы равенства Добавляя очевидные равенства:
Эквивалентность задач РНОВ и РНМО
В задаче о назначении задан дополнительно вектор "желательного" числа работ для каждого работника. Определение 13. Вектор назовем вектором желательных назначений. Введем функционал равномерности назначения относительно вектора желательных назначений Н. где X - матрица назначений. Определение 14. Назовем задачей о равномерном назначении работ относительно вектора желательных назначений (РНОВ) следующую задачу. Заданы: вектор S числа работ на каждый день, матрица Я возможностей каждого работника на каждый день, удовлетворяющие (1), и вектор Н желательных назначений. Требуется построить матрицу назначений X, минимизирующую функционал образом задача, превращается в задачу о равномерном назначении работ, исследованную Рублевым B.C. (см.[16]). Теорема 3.1. Пусть задача РНМО определена заданием вектора числа работ S, матрицей возможностей R и матрицей обязательных назначений А, а задача РНОВ определяется заданием вектора числа работ S+, матрицей возможностей Я+ и вектором желательных назначений Н для таких же значений параметров пит. Пусть ограничения обеих задач связаны следующими условиями: 1). R+ = R-A, 2). s+ = Sj - Егп=і a(j (j Є T m), 3). hi = const - КІ{А) (і Є Туп). Тогда справедливы следующие утверждения: 1). Если Х+ - решение задачи РНОВ, то X Х+ + А - решение задачи РНОМ, причем задачи РНОВ, причем Птах = Піах П{. гЄІ,п Пусть матрицы У и У+ - решения, соответственно, задач РНМО и РНОВ, связанных условиями теоремы, и пусть У = У+ + А. Тогда Из этого следует, что /+{У+) и /(У) различаются на константу, которая не зависит от выбора У и У+, а потому из минимальности значения /(У) следует минимальность значения /+(У+) и наоборот.
Теорема доказана. 4.3. Взаимное сведение и обобщение задач РНМО и РНОВ. Теорема 3.1 дает возможность свести одну задачу к другой. 1. Сведение задачи РНМО к задаче РНОВ. Пусть мы имеем задачу РНМО, заданную матрицей возможностей R, вектором числа работ 5 и матрицей обязательных назначений А. Положим Получим задачу РНОВ, заданную матрицей возможностей 7?+, вектором числа работ на каждый день S+ = (5+,5+,... ,5+г) и вектором желательных назначений Н = (Лі, Л2,..., Лп). Поскольку исходные данные этих задач РНМО и РНОВ удовлетворяют условиям теоремы 3.1, то на основании решения Х+ задачи РНОВ строим решение задачи РНМО по формуле X = Х+ + А Решением полученной задачи РНОВ будет следующая матрица Х+: Полученная матрица, согласно доказанных выше утверждений, будет решением задачи РНОМ для R, S, А. 2.Сведение задачи РНОВ к задаче РНМО. Пусть мы имеем задачу РНОВ, заданную матрицей возможностей R+, вектором числа работ 5+ и вектором желательного числа работ Н. Пусть max гітпт == niax/ij. іЄІ,п Расширим матрицу R+, добавив hmax нулевых столбцов, вектор S+, добавив hmax нулевых компонент и число дней m увеличим на hmax дней. Образуем матрицы Д R и вектор S задачи РНМО следующим образом: Поскольку ограничения обеих задач удовлетворяют условиям теоремы 3.1, то по полученному решению X задачи РНМО строим матрицу Х+ — X — А и, отбросив hmax последних столбцов матрицы Х+, получим решение (25). Пример 2. Пусть задана задача РНОВ для следующих матрицы возможностей R, вектора работ S и вектора желательных назначений Н: щего вида: Отметим, что матрица X не является оптимальным решением задачи о равномерном назначении работ, поскольку, например, матрица Y следующего вида удовлетворяет следующим соотношениям: Следовательно, Y - оптимальное решение задачи о равномерном назначении, но не оптимальное решение задачи РНОВ, а X, напротив, оптимальное решение задачи РНОВ, но не оптимальное решение задачи о равномерном назначении работ. Заметим, что при hi = К (г Є 1, п), определенная таким образом задача, превращается в задачу о равномерном назначении работ, исследованную
Рублевым B.C. (см.[16]). Теорема 3.1. Пусть задача РНМО определена заданием вектора числа работ S, матрицей возможностей R и матрицей обязательных назначений А, а задача РНОВ определяется заданием вектора числа работ S+, матрицей возможностей Я+ и вектором желательных назначений Н для таких же значений параметров пит. Пусть ограничения обеих задач связаны следующими условиями: 1). R+ = R-A, 2). s+ = Sj - Егп=і a(j (j Є T m), 3). hi = const - КІ{А) (і Є Туп). Тогда справедливы следующие утверждения: 1). Если Х+ - решение задачи РНОВ, то X Х+ + А - решение задачи РНОМ, причем задачи РНОВ, причем Птах = Піах П{. гЄІ,п Пусть матрицы У и У+ - решения, соответственно, задач РНМО и РНОВ, связанных условиями теоремы, и пусть У = У+ + А. Тогда Из этого следует, что /+{У+) и /(У) различаются на константу, которая не зависит от выбора У и У+, а потому из минимальности значения /(У) следует минимальность значения /+(У+) и наоборот. Теорема доказана. 4.3. Взаимное сведение и обобщение задач РНМО и РНОВ. Теорема 3.1 дает возможность свести одну задачу к другой. 1. Сведение задачи РНМО к задаче РНОВ. Пусть мы имеем задачу РНМО, заданную матрицей возможностей R, вектором числа работ 5 и матрицей обязательных назначений А. Положим Получим задачу РНОВ, заданную матрицей возможностей 7?+, вектором числа работ на каждый день S+ = (5+,5+,... ,5+г) и вектором желательных назначений Н = (Лі, Л2,..., Лп). Поскольку исходные данные этих задач РНМО и РНОВ удовлетворяют условиям теоремы 3.1, то на основании решения Х+ задачи РНОВ строим решение задачи РНМО по формуле X = Х+ + А Решением полученной задачи РНОВ будет следующая матрица Х+: Полученная матрица, согласно доказанных выше утверждений, будет решением задачи РНОМ для R, S, А. 2.Сведение задачи РНОВ к задаче РНМО. Пусть мы имеем задачу РНОВ, заданную матрицей возможностей R+, вектором числа работ 5+ и вектором желательного числа работ Н. Пусть max гітпт == niax/ij. іЄІ,п Расширим матрицу R+, добавив hmax нулевых столбцов, вектор S+, добавив hmax нулевых компонент и число дней m увеличим на hmax дней. Образуем матрицы Д R и вектор S задачи РНМО следующим образом: Поскольку ограничения обеих задач удовлетворяют условиям теоремы 3.1, то по полученному решению X задачи РНМО строим матрицу Х+ — X — А и, отбросив hmax последних столбцов матрицы Х+, получим решение исходной задачи РНОВ.
Определение и основные свойства плана назначений
Введем понятие плана назначений работ. План назначений включает в себя данные о том, сколько работников должны выполнять конкретный объем работ. Имеется в виду - сколько человек должны работать один день, сколько - два дня и так далее. Такое представление позволяет рассматривать некоторые частные случаи решения обобщений задачи о назначении. Вообще говоря, план назначения уже использовался в доказательстве достаточности основного характеристического свойства задачи РНМО. В этой части диссертации это понятие будет формализовано, и на его основе будет произведено доказательство ряда утверждений. Кроме того, будет сформулировано и доказано свойство, связывающее функционал равномерного назначения (5) и план равномерного назначения. Определение 16. Назовем планом назначения работ Р(Х), построенном на основе матрицы назначения X, следующую последовательность пар: Пример 6. План назначения работ для матрицы назначений X следующего вида: Для такого назначения план будет выглядеть следующим образом: То есть два работника должны выполнять объем работ, равный единице, один работник должен быть занят два дня, и один работник - три дня. Лемма 1. Пусть Р(Х) - план назначения, тогда для любого і Є 1,п найдется t Є 1,/ такое, что Kj(X) = bt. Доказательство леммы тривиально следует из определения плана назначения работ, точно так же как и следующее равенство: Формулу функционала равномерности (5) можно переписать в терминах плана назначения Р(Х) следующим образом: и эти записи эквивалентны. Отсюда вытекает следующая очевидная лемма. Лемма 2. Пусть X и У - матрицы назначения. Тогда, если Определение 17. Назовем план Р(Х) планом равномерного назначения или равномерным планом, если X - матрица равномерного назначения. Следующая теорема 5.1. является основополагающей для использования плана назначения. Она позволяет применять план назначения для решения задач наравне с функционалом равномерности Теорема 5.1. Если существуют X, У - различные матрицы равномерного назначения, то Р{Х) = P(Y). Доказательство.
Предположим противное. Пусть X, Y - матрицы равномерного назначения такие, что 1) Пусть bp b . Обозначим через д номер такой, что: Ьр следующие соотношения Обозначим через Xі — Ьр-срезку 1 матрицы X, а через Y — Ьр-срезку матрицы У. Так как X, Y - равномерные назначения, то по характеристическому свойству равномерного назначения 2 следует, что Случай 4) доказывается аналогично случаю 3). Теорема доказана. Далее везде под словом план мы будем подразумевать план равномерного назначения и обозначать его Р, если иное не оговорено дополнительно. Теорема 5.1. показывает, что план является инвариантом для задачи о равномерном назначении работ, поскольку не зависит от выбора матрицы равномерного назначения. Задача РНМС, в которой главным критерием являлась минимизация стоимости (4), была исследована выше. В этой части работы будет рассмотрена задача, приоритетным в которой является функционал равномерности назначения (5). Иначе говоря, среди всех равномерных назначений требуется найти самое дешевое. Кроме того, предметом изучения в данном разделе диссертации станут решения для частных случаев задачи МСРН при однокомпонентним и двухкомпонентном планах, которые, по мнению автора, являются основными для декомпозиции общей задачи МСРН. Напомним формулировку задачи МСРН, приведенную в первой части. Определение 18. Назовем задачей о минимальной стоимости равномерного назначения работ (МСРН) следующую задачу. Заданы вектор S числа работ на каждый день, матрица R возможностей каждого работника на каждый день, удовлетворяющие (1), и матрица С стоимостей выполнения работ. Требуется построить матрицу X равномерного назначения работ, минимизирующую (4). Определение 19. Решение задачи МСРН назовем равномерным назначением минимальной стоимости. Рассмотрим задачу МСРН, в которой все работники выполняют одинаковое количество работ. Если использовать введенную в данной работе терминологию, то это означает, что план равномерных назначений данной задачи будет состоять только из одной компоненты или однокомпонентным. В таком случае решение этой задачи заключается в сведении ее к задаче о потоке минимальной стоимости в транспортной сети. Пусть план равномерного назначения является однокомпонентным, то есть Р = {(ai, Ь\)}.
Решение задачи МСРН для двухкомпонентного плана
Доказательство. Предположим противное, пусть X - равномерное назначение и Р{Х) ф P(Z). Положим Р(Х) = {(a{,6J) t Є 1,1}, очевидно, что I 2. Из определения плана назначения следует, что Пусть q такое, что b q Ь\ + 1 b q+1. Введем следующие обознаТогда Получили противоречие с условием оптимальности срезок равномерного назначения X. Лемма доказана. Определение 20. Назовем цепью матрицы назначений X последовательность такую, что выполняются следующие условия: и не существует последовательности, удовлетворяющей условиям (ЗО), (31) и содержащей данную. Определение 21. Цепь назовем циклом, если і\ = і\. Пример 9. Пусть матрица возможностей R и вектор работ S имеют вид: Решением такой задачи о равномерном назначении работ будет матрица X следующего вида: Цепью данной матрицы назначений будет следующая последовательность Последовательность будет циклом этой матрицы. Далее в работе основное внимание будет сосредоточено на том, как произвольную матрицу равномерного назначения можно привести к решению задачи МСРН с помощью некоторых преобразований, уменьшающих стоимость назначений. Каждое из этих преобразований будет связано с построением цепи или цикла матрицы и потому будем называть его применением цепи, уменьшающее стоимость. Будет доказано, что, во-первых, изменения в матрице равномерного назначения, получаемые за счет применения цепей, уменьшающих стоимость, не влияют на равномерность назначения, и, во-вторых, для любой матрицы равномерного назначения, не являющейся решением задачи МСРН, существует цепь, уменьшающая стоимость.
Определение 22. Будем говорить, что к матрице назначений X применена цепь 7 или Y = j(X), если Из определения цепи/цикла и преобразования (32) следует, что Vij rij (V г Є l,n, V j Є 1,77г). Очевидно, что для матрицы Y выполняются условия: Вернемся к нашему примеру 9. Если к матрице X применить цепь 7i, то будет получена матрица Y\ следующего вида: Применение к матрице X цикла 72 даст в итоге матрицу Y : Следующее утверждение характеризует важное свойство цепи матрицы равномерного назначения. Лемма 2. Пусть X - матрица равномерного назначения. Тогда для любой цепи 7 матрицы X выполняется следующее утверждение: Y = уХ - матрица равномерного назначения тогда и только тогда, когда К (Х) = Kim(Y). Доказательство. Необходимость. Пусть X, Y - матрицы равномерного назначения. Тогда Получили Кц(Х) — Kim(Y) = О, что доказывает необходимость. Достаточность. По условию Леммы 2 и свойствам (43) Откуда следует f(X) — f(Y). Это показывает, что Y - матрица равномерного назначения и, следовательно, достаточность и вся лемма доказаны. В силу двухкомпонентности плана назначения условие леммы 2 Кц(Х) = Kim(Y) эквивалентно условию Kh{X) Kijn(X). Таким образом, нам удалось показать, что применение к матрице X цепи 7 такой, что К Х) Кігп(Х), не изменяет равномерности назначения. Определение 23. Обозначим через А\ - множество непересекающихся циклов и цепей матрицы равномерного назначения X, таких, что для любой цепи выполняется условие К (Х) К{т{Х), а для любого цикла К {Х) = К{т(Х). Заметим также, что поскольку цепи не пересекаются, то последовательность их применения к мартрице X не имеет значения. Лемма 3. Пусть X, Y - различные матрицы равномерного назначения. Тогда существует такое множество непересекающихся цепей и циклов Ах, что Y = А(Х). Доказательство. Доказательство данной леммы представим в виде алгоритма нахождения множества Ад-. 0. Обнулить в матрицах совпадающие элементы и положить 1. Если матрицы X и Y нулевые, то множество Ад- построено. В противном случае выбрать строку it : Kit{X) Kit(Y). Если такой строки нет, то выбрать любую не нулевую строку.
