Целочисленное сбалансирование трехмерной матрицы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Смирнов, Александр Валерьевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Ярославль
МЕСТО ЗАЩИТЫ
|
||||
|
2010
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
084612559
На правах рукописи
Смирнов Александр Валерьевич
Целочисленное сбалансирование трехмерной матрицы
Специальность 01.01.09 - Дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
1 1 НОЯ 2010
Ярославль - 2010
004612559
Работа выполнена на кафедре теоретической информатики Ярославского государственного университета им. П. Г. Демидова
Научный руководитель кандидат физико-математических наук,
профессор Рублев Вадим Сергеевич
Официальные оппоненты: доктор физико-математических наук,
профессор
Бондаренко Владимир Александрович
кандидат физико-математических наук Афраймович Лев Григорьевич
Ведущая организация Учреждение Российской академии наук
Вычислительный центр им. А. А. Дородницына РАН
Защита состоится «19» ноября 2010 г. в 14 часов на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете имени П. Г. Демидова по адресу: 150008 г. Ярославль, ул. Союзная, д. 144.
С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П. Г. Демидова. Автореферат разослан «15» октября 2010 г.
Ученый секретарь диссертационного совета
С.И. Яблокова
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы
Многие задачи дискретной оптимизации могут быть решены при помощи моделей и методов теории графов. Важным разделом теории графов является теория потоков Форда-Фалкерсона1. Наиболее известная задача теории потоков - задача о нахождении максимального потока в транспортной сети. Сведение к задаче о наибольшем потоке используется при решении ряда задач, одной из которых является задача целочисленного сбалансирования двумерной матрицы.
Различные задачи целочисленного сбалансирования возникают в сфере управления, экономики, финансов. В частности, подобная задача ставится при планировании железнодорожных грузоперевозок. Имеется матричный план по отправке вагонов, который группируется по некоторым показателям (например, направление, тип вагона, владелец вагона и т. п.). Данный план составляется на месяц и естественно является целочисленным. Однако вагоны необходимо отправлять ежедневно. При делении на количество дней в месяце план перестает быть целочисленным. Поэтому возникает проблема такого округления основных параметров, чтобы суммирующие показатели не выходили за определенные рамки. Данный план может быть представлен в виде ^-мерной матрицы, где к - это число показателей, по которым ведется суммирование.
Другой областью применения задач целочисленного сбалансирования является округление экономического плана (представленного, как некоторая «шахматка»), в котором ведется суммирование но разным показателям каких-либо удельных характеристик (нецелочисленных) и требуется округление до ближайших целых значений с сохранением балансовых округлений.
Также задачи целочисленного сбалансирования возникают в банковской сфере, например, в задаче оптимального округления плана валютных счетов. Имеется некий план валютных счетов, которые группируются по нескольким показателям (например, вид валюты, клиент, дата). Такой план при к показателях может быть представлен в виде А;-мерной сбалансированной матрицы, внутренними элементами которой являются величины счетов, а на боковых гранях стоят суммы по соответствующим показателям. При переводе одной
1 Форд Л. Р., Фалкерсоп Д. Р. Потоки в сетях. М.: Мир, 1966. 276 с.
валюты в другую возникает проблема округления величии счетов до целых чисел. Округление до ближайшего целого может привести к значительному расхождению в итоговой сумме, что ведет к определенным финансовым потерям. Поэтому необходим такой алгоритм целочисленного сбалансирования матрицы плана, чтобы расхождение в общей сумме было минимальным.
Задача целочисленного сбалансирования двумерной матрицы ставится следующим образом2. Пусть имеется матрица А размерности (п +1) х (т + 1) с вещественными элементами ау, для которой выполняются следующие условия баланса:
п т т п
«00 = 53 53 = 53 ^ е n)i а0} = b' Gl
¿=1 j—1 »=i
Ищется такая целочисленная матрица D, что выполняются условия:
dij G {LayJ, fayl} (г Е 07тг, j 6 0~7п); doo = L«oo + 0.5J;
п т rn п
doo = 5353 di0 = 536 M); doj = 53dii t? e m); ¡=1 i=l j=l ¿=1
Эта целочисленная матрица D называется сбалансированной для матрицы А. Без ограничения общности можно считать, что элементы исходной нецелочисленной матрицы А принадлежат полуинтервалу [0,1).
Задача целочисленного сбалансирования двумерного матричного плана может быть сведена к задаче нахождения максимального потока в транспортной сети. Максимальный поток в этой сети, найденный при помощи алгоритма Форда-Фалкерсона, будет индуцировать решение задачи целочисленного сбалансирования двумерной матрицы. Таким образом, задача целочисленного сбалансирования двумерной матрицы может быть решена за полиномиальное время.
Аналогичная задача сбалансирования может быть поставлена и в трехмерном случае. Имеется трехмерная вещественная матрица А с неотрицательными элементами а;;р (г 6 0, п, j G Ü, ш, р €Е 0, t), для которых выполнены условия баланса:
2Коршунова Н. N1., Рублев В. С. Задача целочисленного сбалансирования матрицы // Современные
щюблемы математики и информатики, вып. 3. Ярославль: ЯрГУ им. П.Г. Демидова. 2000. С. 145-150.
Кондаков А. С., Рублев В. С. Задача сбалансирования матрицы плана // Доклады Одесского Семи-
нара по дискретной математике. Южный научный центр HAH и МОН Украины. Вып. 2 (июль 2005).
Одесса: Астропринт, 2005. С. 24-20.
каждый элемент с некоторылш нулевыми индексами равен сумме всех элементов, для которых ненулевые индексы оставлены неизменными, а нулевые иидексы заменены вселт возможными ненулевыми значениями диапазонов соответствующих индексов.
Требуется так округлить элементы матрицы до целых значений сверху или снизу (элемент аооо округляется до ближайшего целого), чтобы остались неизменными условия баланса.
Построение модели, аналогичной двумерному случаю, здесь уже невозможно. В данной диссертационной работе рассмотрено обобщение теории потоков Форда-Фалкерсона, названное кратными потоками и задачей о нахождении максимального кратного потока. Показано, что задача целочисленного сбалансирования трехмерной матрицы может быть сведена к задаче о нахождении максимального кратного потока, удовлетворяющего определенным условиям разрешимости. Построен и обоснован алгоритм нахождения такого потока. Кроме того, доказана NР-попнотл задачи сбалансирования.
Также в работе рассмотрена задача минимизации ошибок округления в задаче целочисленного сбалансирования трехмерной матрицы. Данная задача является актуальной во многих практических задачах, где возникает необходимость целочисленного сбалансирования. Для задачи минимизации построен алгоритм решения и обоснованы все результаты.
Цель и задачи работы
Целью данной работы является исследование задачи целочисленного сбалансирования трехмерной матрицы. Среди основных задач выделяются:
1) исследование возможности простого сведения к потоковой задаче;
2) исследование вопроса разрешимости задачи сбалансирования;
3) построение алгоритма, который мог бы находить решение возможно более эффективным методом, чем общий метод решения задач целочисленного линейного программирования;
4) решение задачи минимизации ошибок округления при целочисленном сбалансировании;
5) изучение вопроса о сложности задачи сбалансирования.
Методы исследования
В диссертационной работе используются методы теории графов, теории линейного программирования. Также используются аналитические методы
доказательства сводимости дискретных задач.
Научная новизна
Все основные результаты являются новыми:
1) введены основные понятия теории кратных сетей и кратных потоков, обоснована теорема о разности двух полных потоков в сети кратности 2;
2) получено сведение задачи целочисленного сбалансирования к задаче о наибольшем кратном потоке в сети сбалансирования, удовлетворяющем условиям разрешимости;
3) получен и обоснован алгоритм нахождения максимального кратного потока указанного вида;
4) доказана iVP-полнота задачи целочисленного сбалансирования трехмерной матрицы;
5) построен и обоснован алгоритм минимизации ошибок округления в задаче целочисленного сбалансирования трехмерной матрицы.
Практическая значимость работы
Задача целочисленного сбалансирования трехмерной матрицы возникает в сфере управления, экономики, финансов. Построенные в данной работе алгоритмы позволят решать данные задачи. Кратные сети и кратные потоки могут быть приложимы к ряду задач дискретной оптимизации. В данной работе исследован класс кратных сетей целочисленного сбалансирования кратности 2, результаты могут в дальнейшем быть обобщены для сетей произвольной кратности к.
Апробация работы
Основные результаты работы докладывались на научном семинаре, проводимом на кафедре теоретической информатики ЯрГУ «Моделирование и анализ информационных систем» и обсуждались на научных конференциях:
1. «Дискретные модели в теории управляющих систем», VII международная конференция, Москва, 2006.
2. Одесский Семинар по дискретной математике, Одесса, 2006.
3. «Дискретная математика и ее приложения», IX Международный семинар, посвященный 75-летию со дня рождения академика О. Б. Лупано-ва, Москва, 2007.
4. Одесский Семинар по дискретной математике, Одесса, 2Ü07.
5. «Кибернетика и высокие технологии XXI века», IX международная научно-техническая конференция, Воронеж, 2008.
6. «Синтез и сложность управляющих систем», XVII Международная школа-семинар имени академика О. Б. Лунанова, Новосибирск, 2008.
7. «Дискретные модели в теории управляющих систем», VIII международная конференция, Москва, 2009.
8. «Молодежь. Наука. Инновации - 2009», 62 региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием, Ярославль, 2009.
9. «Дискретная математика и ее приложения», X Международный семинар, Москва, 2010.
10. «Синтаксис и семантика логических систем», 3-я Российская школа-семинар, Иркутск, 2010.
11. Одесский Семинар по дискретной математике, Одесса, 2010.
12. Семинар кафедры информатики и автоматизации научных исследований Нижегородского государственного университета им. Н. И. Лобачевского, Нижний Новгород, 2010.
Кроме того, программа MatrixBalancing для нахождения решения задачи целочисленного сбалансирования трехмерной матрицы получила свидетельство о государственной регистрации программы для ЭВМ (свидетельство №2010611519).
Работа «Задача целочисленного сбалансирования трехмерной матрицы» была награждена медалью «За лучшую научную студенческую работу» на Открытом конкурсе лучших научных работ студентов в области естественных, технических и гуманитарных наук (приказ Рособразования от 15 июня 2009 г. №641).
Исследования по теме диссертационной работы были отмечены дипломом за победу во Внутривузовском конкурсе лучших поисковых работ аспирантов
«Подготовка научно-педагогических кадров в научно-образовательных центрах вуза» 2009 года по направлению «Информатика».
Работа соискателя по теме диссертации поддержана ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (государственный контракт № П161).
Публикации
По теме диссертации опубликовано 15 научных работ, из них 3 в журналах из перечня ВАК. Список публикаций приведен в конце автореферата. В работах, написанных совместно с научным руководителем, соискателем полностью самостоятельно были получены следующие результаты: идея послойного алгоритма; алгоритм нахождения максимального кратного потока, отвечающего условиям разрешимости задачи сбалансирования, и его обоснование; алгоритм минимизации ошибок округления, основанный на обобщенном алгоритме пометок; сравнительный анализ алгоритмов целочисленного сбалансирования. Все остальные результаты получены в нераздельном соавторстве.
Структура и объем диссертации
Диссертационная работа состоит из введения, шести глав, заключения, двух приложений и списка литературы, содержащего 83 наименования. Диссертация содержит 17 рисунков. Объем диссертации без приложений и списка литературы составляет 86 страниц, общий объем - 177 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении дается обзор родственных задач (задача целочисленного сбалансирования двумерной матрицы, задачи оптимального округления). Для задачи целочисленного сбалансирования двумерной матрицы приводится схема сведения ее к задаче о наибольшем потоке в сети. Также рассматривается задача минимизации ошибок округления в задаче сбалансирования двумерной матрицы.
Кроме того, во введении приведены примеры практических задач, для решения которых необходимо найти решение задачи целочисленного сбалансирования матрицы.
В первой главе дается постановка задачи целочисленного сбалансирования трехмерной матрицы. Дана вещественная трехмерная матрица А размерности (п+1) х (т + 1) х (I +1) с элементами для которой выполнены
условия баланса:
п m t т t
.^000 = X/ ai0° = X aW» e n)í ¿=1 j—l p=l j'=l p=l
n t n m
aojo = aW (j 6 Vm); a00;> = ]L aW (p 6 M); ¡=1 p=l i—1 j=l
t m
а-ф = ]Г] aijp (i £ l~ñ, j e 1, m); a!0p = ^ aIJP (i e 1, n, p £ 1, í);
p=i j=i
fl
aojp = a.jp (j € ТТгтг, p £M). i=l
Ищется целочисленная сбалансированная матрица £) той же размерности, для которой выполнены условия:
dijp € {[a¡ipj, fa.jpl} (г 6 0~ñ, j £ 0~m, p € (Ц); ¿0oo = Laooo + 0.5J;
n m t m t
4ü0 = У^ У^ У^ diOO = X/ diip (¿ 6 n)¡ ¿=1 .7=1 p=l j—l p=l
n í n m
¿ojo = € V"); d00p = S (p 6 M);
i=l J?=l t=l J=1
t 171
dao = Yld»P ñ,j€l~m)\ di0p = Y^dijp (г € l,n, p <E l,í);
p=i j=i
П
¿Ojp = € P e
¿=1
Постановку задачи целочисленного сбалансирования трехмерной матрицы можно также дать в виде трехиндексной задачи линейного программирования. Пусть имеется вещественная трехмерная матрица А размерности (n-fl) х (m + 1) х (t + 1) с неотрицательными элементами a¡JP, для которой выполнены условия баланса. Ищется целочисленная сбалансированная матрица D, для которой выполняются ограничения:
п m t
У^У^ У^ djjp = Laooo + 0.5J; i— 1 j—1 р=1
т £
|а.'оо] < 5353- € Мг);
]=1 Р=1 п 4
|ао>о] < 5353^> - е
¡=1 р=1 п т
Ьоор] < ^ Кор! (Р € 1, £);
1=1 7=1
(
[ауо] < 53 ^Ур - 6 1'п' 3 6 1,
р=1 т
< Га;ор1 (г б 1,п, р б М);
п
КЛР] < 53 - О 6 Р е М);
¿=1
[аур] < <2ур < [аУр"1 (г € 1~~п, з £ 1,«г, р е М); и принимает минимальное значение критерий
п т Ь ¿=1 з=1 р=1
Обе постановки являются эквивалентными.
Построение модели, аналогичной двумерному случаю, для трехмерной матрицы уже невозможно, в связи с чем рассмотрен вопрос о сводимости в смысле «естественного» сведения. Это такое сведение, при котором по исходной трехмерной матрице будет строиться сеть; при этом каждому элементу аур матрицы будет соответствовать вершина сети, а пропускные способности дуг будут устанавливаться в зависимости от значений аур, причем все пропускные способности дуг должны быть целочисленными. Потребуем также, чтобы некоторое подмножество компонент оптимального решения потоковой задачи образовывало оптимальное решение задачи сбалансирования и задача сбалансирования не имела допустимого решения, если не имеет допустимого решения потоковая задача.
Теорема 1. Пусть п > 2, т > 2, р > 2. Тогда для задачи целочисленного сбалансирования трехмерной матрицы не существует «естественного» сведения к задаче о нахождении наибольшего потока.
Во второй главе вводится понятие кратных сетей и кратных потоков, производится сведение задачи целочисленного сбалансирования к задаче о наибольшем кратном потоке. Также доказывается теорема о разности двух полных кратных потоков в сети кратности 2.
Кратные потоки являются обобщением теории потоков Форда-Фалкерсоиа. При этом вводится целое к > 1, которое называется кратностью потока. В качестве сети рассматривается ориентированный мультиграф й(Х, и), между вершинами которого могут быть дуги одного из 3 видов:
1) обычная дуга и0 с пропускной способностью с(г1°), ноток по которой не связан с потоком по другим дугам; множество обычных дуг обозначим через
и
2) кратная дуга ик между двумя вершинами, которая состоит из к дуг одной ориентации с одинаковой пропускной способностью с(ик) и одинаковым потоком по каждой из них; множество кратных дуг обозначим через [/к;
3) связанная дуга и между двумя вершинами, которая связана с еще к — 1 дугой, имеющих одинаковый один из концов; множество связанных дуг, выходящих из одной вершины или входящих в одну вершину, будем называть мулътидугой ит\ пропускная способность всех связанных дуг одной мульти-дуги одинакова; поток по каждой связанной дуге из мультидуги одинаков; множество мультидуг обозначим через ¿7т.
Множество выходящих из вершины дуг может быть либо только кратными дугами, либо только одной мулътидугой (к связанных дуг), либо только обычными дугами.
Из источника Хо сети выходят только кратные дуги, а в сток г сети входит только одна мультидуга. Если из вершины выходят связанные дуги мультидуги, то в нее обязательно входит кратная дуга. Если в вершину входит мультидуга, то из нее может выходить только кратная дуга. Определенный таким образом мультиграф 17) с. пропускными способностями дуг назовем кратной (транспортной) сетью.
Кратным потоком по сети называется целочисленная функция, определенная на множестве дуг £/ = V и {/* и ит, для которой выполнены условия неотрицательности, ограниченности (пропускными способностями дуг) и неразрывности потока (в каждой вершине).
Величиной кратного потока называется сумма <рг входящего потока для стока г, равная сумме выходящего из источника потока.
Отметим, что при к = 1 кратная сеть превращается в обычную транспортную сеть, а кратный поток превращается в обычный поток по этой сети. Задача о наибольшем кратном потоке для кратной сети является обобщением задачи о наибольшем потоке для обычной транспортной сети.
Покажем теперь, каким образом задача целочисленного сбалансирования трехмерной матрицы может быть сведена к задаче о наибольшем кратном потоке.
Заметим, что без ограничения общности в задаче о целочисленном сбалансировании можно считать, что аур < 1 для всех ненулевых значений индексов г, ], р. В противном случае исходную матрицу А можно разложить на сумму матриц В + где В образована целыми частями элементов аур (г € 1,п, ] € 1,тп, р € 1,£) и значения элементов Ь{№ с нулевыми индексами находятся из условий баланса, а Р ~ В — А. Если Я - целочисленная сбалансированная матрица для Е, то П = В + II - целочисленная сбалансированная матрица для А. Это замечание позволяет считать, что йцр е {0,1} (г 6 Т~п, 3 е 17т, р € 17*).
Кратная сеть 6"(А', {/) целочисленного сбалансирования представлена на рис. 1 на следующей странице. Каждому элементу <щр матрицы А соответствует вершина сети х^р (на рисунке показаны только вершины со значениями индексов 0, 1 и гг,ш,4 соответственно для индексов г,],р). Кратные дуги отмечены жирными стрелками (для наглядности кратные дуги вместе с вершинами, которые они соединяют, показаны на рисунке дважды - в частях и Дг сети б). Связанные дуги мультидуг отмечены двойными стрелками и при этом вторая стрелка стоит у вершины, которая является общим концом связанных дуг мультидуги (в сток л входит мультидуга, образованная связанными дугами из г\ и г2, а из каждой вершины (г > 0, у > 0, р > 0) выходит мультидуга, образованная связанными дугами, одна из которых находится в части (?1, а другая - в части Каждой вершине хцр, где более чем 1 индекс имеет нулевые значения, соответствует дополнительная вершина а также вершинам г^ (к = 1,2) соответствуют дополнительные вершины г'к. Пропускные способности кратных дуг:
с(ж000,Ягоо) = 2[а;оо] (г 6 1,п); с(хооо, х'т) = 2 ^|аооо + 0.5] - ;
с(яооо>х»оо) = 2([а,оо] - |а»оо_|) (г £ 1 ,п);
Рис. 1. Кратная сеть целочисленного сбалансирования трехмерной матрицы
с(хт),Хф) = 2[ауо] (г е 1 ,п, 3 е 1,т); с(хт,х'т) = 2 ^аюо1 - ^Кж!^ (г € 1,гг);
Ф'юо^уо) = 2(Г«^о1 ~ К;о]) € М, 3 € 17т);
с(х^0,х^р) = 2[аур] (г е 17га, з е Т~т, р е 1, £)•
Пропускные способности связанных ;(уг для всех мультидуг из вершин ХуР равны [аур], а пропускные способности связанных дуг, входящих в вершину 2 : с{гк, г) = (а00о + 0.5] (к = 1,2). Пропускные способности обычных дуг:
фозр.^суо) = Кл>] 0' е 17т, реЦ);
с(щр,4зо) = Кзр! - К»] и е 17т, р 6 V); (
С1Х0]0> Що) = Га0;'о] - 0' е М"); фол), 21) = |.асуо] 0' е 1,т);
р=1
т
с(х<уо, 4) = Га0у0] - |ао;о] (з 6 1~т); гх) = [аода + 0.5] - ]Р|а<уо];
¿=1
а^оор) = [а»?] (ге1,п, р€ 1,4); с(ж,ор,^оор) = Га;ор1 - [аюр] (г £ р € 1,Ь)\
п
Ф'оор. ^оор) = [аоор! - (Р € М)'> фоор, ¿г) = КюР] (р € 1,4);
1=1
(
фоор,4) = Г«ооР] - 1°оор] (Р е М); с(4,22) = [аооо + 0.5] - ]Г|а0ор].
Р=1
Связь задачи целочисленного сбалансирования и задачи о максимальном кратном потоке устанавливается следующей теоремой.
Теорема 2. Если задача целочисленного сбалансирования трехмерной матрицы 1шеет решение, то оно индуцирует максимальный поток в кратной сети С следующем образом:
I) для каждой вершины являющейся концом кратной дуги, проходящий через нее поток равен 2¿¡]Р;
2) для каждой вершины х^р, являющейся концом обычной дуги, проходящий через нее поток равен
3) для вершины Хдцо проходящий через нее пот,ок равен с(жооо, хооо)>
4) для каждой вершины г^ (к = 1,2) проходящий через нее поток равен [а000 + а.5\;
5) для каждой вершины г'к (к — 1,2) проходящий через нее поток равен с(4,гк).
Справедливость теоремы 2 следует непосредственно из правил построения кратной сети целочисленного сбалансирования. Однако обратное утверждение неверно: не всякому максимальному кратному потоку величины 2{аооо + 0.5] соответствует решение задачи целочисленного сбалансирования матрицы. Поэтому дополнительно потребуем выполнение следующих условий, которые в дальнейшем мы будем называть условиями разрешимости:
1(хт,хцо) + 1{х'т,Ху0) > с(хюо,хт) (г 6 1 ,п, ] 6 1,т); /(щ-р, Що) + /(щ-р, х1уо) 2: с(Щр, Що) и € т, р € 1, (1)
1Ыор,Х00р) + /&0р,х'00р) > с(хг0р,хтр) (г 6 1,п, р £ М).
Здесь /(о, Ь) - это поток на соответствующей дуге. В дальнейшем дуги (яло.а^о). (хО:Р,Що), (^¿оР,з:оор) (г € ; 6 1 ,т, р € 1,*) мы будем называть основными, а дуги (^¿оо, ^чоо)' (х'юо>хчо), (Щр,хо}о)< (ХЦ0'Х0}0), (х^х'щ) (х'00р,х0ор) (г £ 1 ,п, £ 1,тп, р 6 1,0 мы будем называть дополнительными.
Справедливо следующее утверждение.
Теорема 3. Пусть максимальный кратный поток (р для сети С? имеет величину = 2|_аооо + 0-5] « выполнены условия разрешимости (1). Тогда данный поток индуцирует решение задачи целочисленного сбалансирования трехмерной матрицы следующим образом: положим с1^р равным
1) половине величины потока, проходящего через вершину х^р, если она является концом кратной дуги;
2) величине потока, проходящего через вершину х^р, если она является концом обычной дуги.
Объединяя вышесказанное, получаем следующий критерий разрешимости задачи сбалансирования.
Теорема 4. Для того, чтобы задача целочисленного сбалансирования имела решение, необходимо и достаточно, чтобы в сети целочисленного сбалансирования существовал максимальный кратный поток ip величины = 2[аооо + 0.5J, для которого выполняются условия разрешимости (1).
Теорема 4 устанавливает сведение задачи целочисленного сбалансирования к задаче о максимальном кратном потоке.
Объединение мультидуги ы™, идущей из вершин z%, z^ в г и двух путей Иг (г = 1,2), каждый из которых является ориентированным путем в соответствующей части Gr из вершины rcooo в вершину zr, назовем обобщенным путем, если каждый из путей /¿г проходит через одну и ту же вершину xilp с ненулевыми индексами г > 0, j > 0, р > 0.
Кратный поток назовем полным, если любой обобщенный путь из Хооо в z имеет дугу и (обычную, кратную или мультидугу), поток по которой равен ее пропускной способности /(и) = с(и].
Проекция Ci (г = 1,2) подграфа С на часть сети Ch - это часть подграфа С, образованная его вершинами и дугами, принадлежащими G;.
Так как части Gi (г = 1,2) сети G представляют собой обычные транспортные сети с источником хооо и стоком гг, то будем называть некоторый путь из гооо в % путем прорыва в части Gi, если f(u) < с(и) на прямых дугах и f(u) > 0 на обратных дугах этого пути.
Разрезом R в кратной сети G(X,U), отделяющим хооо и z, назовем множество вершин R, где яооо € R, & z € R {R = X\R). Число c(R) = Sxeß.yeß c(xi У) назовем пропускной способностью разреза R. Разрез Яо = arg min/e c(R) назовем минимальным разрезом.
Пусть в кратной сети определен некоторый поток tp величины ipz > 0. Кратным циклом в сети G(X, U), где X - множество вершин, U - множество дуг (обычных, кратных или мультидуг), назовем такой подграф C(X',U'), X' С X, U1 С U, для которого:
1) проекции С\ и Ci на части G\ и Gi соответственно есть объединение некоторых циклов, причем дуги, поток по которым ненулевой, могут проходиться в обратном направлении;
2) проекции С\ и Сч согласованы (одинаковы) на общей части подграфов Gi и С?2;
3) С\ представим в виде С\ = U{Ci), где С{ - некоторые циклы и С{ <fL
С{= V? ф к\ при этом для любой дуги и из С?х выполняется неравенство
О < /(и) + а+(и) ~ а'(и) < с(и),
где а+(и) - это число циклов С(, в которых дуга и проходится в прямом направлении, а а~(и) - это число циклов С^, в которых дуга и проходится в обратном направлении. Такое же условие должно выполняться и для Сг-
Обобщенным путем прорыва в сети (7(Х, С/) для некоторого кратного потока <р назовем такой подграф С/'), X' С X, V С II, для которого:
1) каждая из проекций £х и £2 на части б; и С'г соответственно есть объединение ровно одного пути прорыва из жооо в 2 и некоторых циклов, причем дуги, поток по которым ненулевой, могут проходиться в обратном направлении;
2) проекции и 52 согласованы (одинаковы) на общей части подграфов С?1 и С2;
3) представим в виде 5\ = и {С{}, где /хх - путь прорыва, С\ -некоторые циклы и С[ <£. С* Ф /с; при этом для любой дуги и из выполняется неравенство
О < /(и) + а+(и) - а"(и) < с(и),
где а+(и) - это число элементов множества ¿¿х и {С^в которых дуга и проходится в прямом направлении, а а~(и) - это число элементов множества /хх и {С^}, в которых дуга и проходится в обратном направлении. Такое же условие должно выполняться и для ¿>2;
4) 5 не содержит кратного цикла.
Рассмотрим теперь обычную сеть С(Х,и); X - множество вершин, С/
- множество дуг. </з(С/) - поток в сети (7), - его величина. с(и) ~ пропускная способность дуги и\ с{и) > /(и) > 0 - поток на дуге. /х(и) -поток, входящий или исходящий из вершины по дуге и. Пусть хо ~ источник, 2 - сток сети в(Х, II).
в<р^С{Х,ич>)- = (и|/(и) ф 0}.
Лемма 1. Пусть <р1{и), (р2(и) - потоки в сети С(Х,(1), причем <р\ < Пусть <р°(1/) = <р2(и) - <р1{и). Тогда граф = {&} и {О,-}, где {¿¿} множество всех путей прорыва из хо в г для потока 9?1, {5;} ф 0, а {С,-}
- множество всех циклов.
Лемма 2. Пустъ ^(и), <р2{и) - потоки в сети <3(Х, II), причем <р\ = ц>2г. Пусть найдутся такие дуги сети С(Х,[1), что потоки <р1(и), р2{и) на этих дугах различны. Пусть (р°(и) = р2(и) — <р1(и). Тогда граф (З^о = {Су}, где {Су} - множество всех циклов.
Перейдем теперь к кратным сетям. Так же, как и в случае обычной сети, обозначим Су = в(Х, 1/^); Щ = {и\/(и) ф 0}.
Теорема 5. Пусть ¿р1 (С/), <р2(и) - два полных потока в кратной сети в(Х, 17), причем < (р2. Пустъ <р°(и) = <р2{11) - у\и). Тогда граф = {5,} и {С^}, где {¿¿} - множество всех обобщенных путей прорыва из Жооо в г, а {Су} - множество всех кратных циклов. В случае, когда <рхг = <р2 = 4%°*, {$} - 0В третьей главе приведен и обоснован алгоритм нахождения максимального кратного потока для решения задачи целочисленного сбалансирования, рассмотрены примеры работы алгоритма.
Выполнение алгоритма разбивается на три больших этапа:
1) этап построения полного потока;
2) этап увеличения потока. Если полученный полный поток не является максимальным, то увеличиваем поток при помощи обобщенного алгоритма пометок (см. ниже) до тех пор, пока поток не станет максимальным;
3) этап коррекции потока. Если полученный максимальный поток имеет величину 2[аооо + 0.5], но не удовлетворяет условиям разрешимости (1), то выполняем коррекцию потока при помощи обобщенного алгоритма пометок до тех тюр, пока не будут выполнятся условия разрешимости (1), либо не будет показано, что подобная коррекция невозможна.
Алгоритм нахождения полного потока прост. На данном этапе увеличения потока можно добиваться, находя все возможные обобщенные пути прорыва из хооо в 2 через вершины хцр [г € 1,п, ] 6 1, т, р € 1, £) без обратных дуг и увеличивая поток по ним. В итоге будет получен полный поток.
Рассмотрим обобщенный алгоритм пометок. Идея алгоритма состоит в следующем: в проекциях вх и Сг поочередно строятся пути прорыва ¡1\ и Ц2 (возможно, в объединении с некоторыми циклами) до тех пор, пока пути в обеих проекциях не станут согласованными, либо же не останется вариантов для продолжения построения пути. В первом случае объединение и Ц2 с
мультидугой с концом в z даст обобщенный путь прорыва, во втором случае производится откат до «точки ветвления», после чего выполнение алгоритма возобновляется. Если точкой ветвления оказывается агооо и при этом хооо не помечена, то задача целочисленного сбалансирования не имеет решения.
Идея алгоритма этапа коррекции состоит в поиске кратных циклов в сети с максимальным потоком и изменении величины потока на дугах этих циклов. Каждый из этих циклов должен содержать хотя бы одну дугу, поток по которой не максимален. При построении очередного цикла запрещается уменьшать ноток по насыщенным основным дугам (т.е. но тем основным дугам и, для которых f{u) — с(и)). Для нахождения такого цикла выбирается произвольная ненасыщенная основная дуга и с помощью обобщенного алгоритма пометок находится обобщенный путь прорыва из конца этой дуги в ее начало. Объединение выбранной дуги и построенного пути прорыва дает искомый кратный цикл. Процесс построения циклов и изменения потока по ним происходит до тех пор, пока не будут выполнены условия разрешимости (1), либо же не будет установлена невозможность построения очередного цикла.
Теорема 6. Если задача целочисленного сбалансирования трехмерной матрицы имеет решение, то оно может быть найдено при помощи алгоритма нахождения максимального кратного потока для решения задачи сбалансирования.
В четвертой главе обосновывается iVP-полнота задачи целочисленного сбалансирования трехмерной матрицы.
Для доказательства JVF-полноты задачи целочисленного сбалансирования трехмерной матрицы рассматривается следующее сужение класса задач целочисленного сбалансирования:
m = t = n; a,jp € [0,1) (i € l,n, j € l,n, p G l,n);
71 П П П
am = У^У^ atjP <1 (¿6 17n); a,0j0 = ^ ^¡T aijp < 1 (j G 1, n); j=i p=i ¡=1 p=l n n
aoop = -1 (p 6
1=1 j=l
Задачу распознавания целочисленного сбалансирования, удовлетворяющего указанным соотношениям, назовем задачей ЦСЗ.
Мы покажем полиномиальное сведение к задаче ЦСЗ следующей классической Л^Р-полной задачи о З-сочетаниях3 (назовем ее ЗС):
Задано 3 множества 1, 3, Р с п элементами (можно считать, что I — 7 = Р = {1,...,п}) и подмножество М прямого произведения I х 3 х Р. Требуется определить, можно ли из М выбрать подмножество М', у элементов которого значение каж;дой координаты г, ] или р присутствует, ровно один раз.
Индивидуальную задачу, определяемую множеством М, назовем ЗСМ. Для задачи ЗСМ, определяемой множеством М, построим систему линейных неравенств:
хф = 0, (2)
6 < хц, < 1 - (п2 - 1)<$, (м,р)ем; (3)
и п
6 - X) -1' Р е ТГ"; (4)
¡=1 7=1 тг п
<5 < ^ ^ з 6 (5)
)=1 р=1
п п
7=1 р=1
2 п п п ^
¿=1 7=1 р=1
где г =
Особенностью построения полиномиального сведения является то, что мы не будем задавать функцию сведения индивидуальной задачи ЗС к индивидуальной задаче ЦСЗ в явном виде, а в качестве такой функции возьмем полиномиальный алгоритм решения системы линейных неравенств.
Лемма 3. Если индивидуальная задача ЗСМ имеет решение, то система
3Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с. Кагр R. Reducibility among combinatorial problems // R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum, 1972. P. 85-103.
(2)-(7) разрешима. Ее решение ьмеетп вид:
хчр = 1 - - 1)<5,
(М,р) ем'; (8)
{г,],р)еМ\М'- (9)
{1,3,р) £ М. (10)
Следствие. Если система (2)-(7), построенная по задаче ЗСМ, неразрешима, то задача ЗСМ также не имеет решения.
Лемма 4. Решение (8)-(10) системы (2)-(7) определяет одну из задач ЦСЗ, если положить а^р = х^р (г € 1 ,п; з е 1 ,п; р 6 1,п). Эта задача имеет решение:
Лемма 5. Если задача ЗСМ имеет решение М', то любое решение системы (2)-(7) определяет задачу ЦСЗ, которая имеет решение (11).
Лемма 6. Пусть индивидуальная задача ЦСЗ (назовем ее ЦСЗМ) имеет решением матрицу £). Положим М = {(г,з,р) \ а^р > 0}. Тогда индивидуальная задача ЗСМ, определяемая множеством М, имеет решение М' =
Лемма 7. Индивидуальная задача ЗСМ имеет решение тогда и только тогда, когда имеет решение задача ЦСЗМ, полученная как решение системы линейных неравенств (2)-(7) для данного множества М задачи ЗСМ.
Теорема 7. Задача целочисленного сбалансирования трехмерной матрицы является ИР-полиой.
В пятой главе проводится сравнительный анализ алгоритмов целочисленного сбалансирования (алгоритма нахождения максимального кратного потока, удовлетворяющего условиям разрешимости (1) (называемого в данной главе для удобства изложения обобщенным алгоритмом пометок), и первого алгоритма Гомори4) на основании результатов вычислительных экспериментов для различных классов тестов. На основании анализа статистики по проведенным вычислительным экспериментам делается вывод о том, что обобщенный алгоритм пометок является более эффективным на большинстве
4г:м., напр., Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М.: Наука, 1969. 308 с.
о' = {¿ур = 11 {1,з,р) е м'}.
(и)
примеров. Кроме того, можно отметить, что алгоритм пометок, как правило, работает лучше метода Гомори в случаях, когда целых сумм относительно мало, хотя полный перебор может возникнуть и в этих ситуациях. В случае же, когда целых сумм достаточно много, предпочтительнее оказывается алгоритм Гомори. Также лучше оказывается метод Гомори в тех случаях, когда решений нет (в методе пометок тогда неизбежен полный перебор).
Рекомендация по практическому применению рассмотренных алгоритмов может быть следующей:
1. Устанавливаем максимальное допустимое время выполнения алгоритма, зависящее от размерности матрицы и от производительности компьютера.
2. Определяем, какой из алгоритмов будет запущен первым. В случае наличия большого числа целых сумм целесообразно выбрать метод Гомори, в противном случае - алгоритм пометок.
3. Выполняем выбранный алгоритм до тех пор, пока не будет получен ответ, либо не будет превышено максимальное допустимое время.
4. Если было превышено допустимое время, то выполняем шаг 3 для второго алгоритма; если время опять превышается, выдаем ошибку.
В шестой главе рассмотрена задача минимизации ошибок округления в задаче целочисленного сбалансирования трехмерной матрицы, приведен и обоснован алгоритм ее решения. Также рассмотрен пример выполнения этого алгоритма.
В случае, когда задача целочисленного сбалансирования имеет несколько решений, возникает вопрос о поиске оптимального решения, то есть такого решения, сумма ошибок округления для которого будет минимальной.
Поставим задачу минимизации ошибок округления в задаче целочисленного сбалансирования трехмерной матрицы как задачу поиска такой целочисленной сбалансированной матрицы Д для которой сумма ошибок округления
п т I
ПРI
(12)
г=1 .7=1 р=1
будет минимальной.
Пусть в кратной сети целочисленного сбалансирования V), соответствующей некоторой матрице А, имеется максимальный кратный поток величины </э2 = 2йоось удовлетворяющий условиям разрешимости (1). Для каждой вершины вида (г € 1 ,п, ] ё 1 ,т, р 6 1,<) определим ошибку
ОС^р'.
/(^-УО] = 0) 1 , /(^-г^'О) ^-¿^р) = 2.
Определим суммарную ошибку потока <р(и), как величину
г=1 р=1
Заметим, что значение 5(</>) совпадает со значением функционала (12) для соответствующей матрицы V.
Определим теперь стоимость прохода через вершину х^р (г € 1,п, б 1 ,т, р € М):
1 2 йцр, =
Пусть в сети G(X, U) определен максимальный кратный поток </?(£/) величины <pz = 2с?ооо, удовлетворяющий условиям разрешимости (1). Пусть имеется кратный цикл С(Х\ U') в сети G(X,U), проходящий насыщенные дуги в обратном направлении, а ненасыщенные - в прямом направлении. Цикл C(X',U') назовем циклом отрицательной стоимости, если выполняется
AS = Е s(xHp) <
XíjpSX1
При этом при добавлении к потоку <p(U) цикла С{Х', U') суммарная ошибка S(ip) уменьшится на величину |AS|.
Теорема 8. Пусть в кратной сети целочисленного сбалансирования G(X, U), соответствующей некоторой матрице А, существуют два максимальных потока ip1(U) и (p2(U), причем = <р2 = 2c¿ooo w для обоих потоков выполнены условия разрешимости (1). Пусть S{tpl) > S(<p'¿). Тогда в сети G(X,U) с потоком tpl{U) существует цикл отрицательной стоимости.
Алгоритм решения задачи минимизации ошибок округления заключается в поиске циклов отрицательной стоимости в кратной сети целочисленного
сбалансирования, в которой определен максимальный поток, и добавлении этих циклов к потоку. Для поиска таких циклов используется модификация алгоритма этапа коррекции потока, введенного в главе 3. Процесс идет до тех пор, пока стоимости прохода через все вершины не станут неотрицательными, либо же не будет показана невозможность построения цикла отрицательной стоимости.
Теорема 9. Если задача целочисленного сбалансирования трехмерной матрицы имеет решение, то имеет решение и задача минимизации ошибок округления. Это решение может быть найдено при помощи указанного алгоритма.
В заключении приведены основные результаты, полученные в диссертационной работе.
В приложении А приводится и обосновывается утверждение о том, что пропускная способность минимального разреза в частях О г и С 2 кратной сети для задачи целочисленного сбалансирования трехмерной матрицы равна г!ооо .
В приложении В дается листинг программы МаЬгЬсВа1апаг^, реализующей два способа нахождения решения задачи целочисленного сбалансирования - алгоритм нахождения максимального кратного потока, удовлетворяющего условиям разрешимости (1), и первый алгоритм Гомори.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В данной диссертационной работе получены следующие результаты:
1) показано, что для задачи целочисленного сбалансирования трехмерной матрицы не существует эффективного сведения к задаче о максимальном потоке;
2) построено обобщение теории потоков Форда-Фалкерсона, названное кратными сетями и кратными потоками;
3) установлена сводимость задачи сбалансирования к задаче о нахождении максимального кратного потока, удовлетворяющего определенным условиям разрешимости. Показано, что выполнение данных условий разрешимости для максимального потока необходимо и достаточно для существования решения в задаче сбалансирования;
4) получен и обоснован алгоритм решения задачи о наибольшем кратном потоке данного вида;
5) доказана NP-полнота задачи целочисленного сбалансирования трехмерной матрицы;
С) рассмотрена задача минимизации ошибок округления в задаче целочисленного сбалансирования, приведен и обоснован алгоритм ее решения;
Таким образом, все цели, поставленные перед данным исследованием, достигнуты.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Рублев, В. С. Целочисленное сбалансирование 3-мерной матрицы плана / В. С. Рублев, А. В. Смирнов // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское 4-6 марта 2006 г.). - М.: МГУ, 2006. - С. 302-308.
2. Рублев, В. С. Целочисленное сбалансирование трехмерной матрицы плана и обобщенная теория потоков / В. С. Рублев, А. В. Смирнов // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. - Одесса: Астропринт, 2006. - Вып. 3.
- С. 38-46.
3. Рублев, В. С. Послойный алгоритм целочисленного сбалансирования трехмерной матрицы / В. С. Рублев, А. В. Смирнов // Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2007 г.). - М.: МГУ, 2007. - С. 351-353.
4. Рублев, В. С. Послойный алгоритм целочисленного сбалансирования трехмерной матрицы плана (тезисы) / В. С. Рублев, А. В. Смирнов // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. - Одесса: Друк, 2007. - Вып. 5.
- С. 44-45.
5. Рублев, В. С. Задача оптимального округления плана валютных счетов / В. С. Рублев, А. В. Смирнов // Кибернетика и высокие технологии XXI века. - Воронеж: НПФ «Саквоее», 2008. - Т. 1. - С. 112-123.
6. Рублев, В. С., Минимизация ошибок округления в задаче целочисленного сбалансирования трехмерной матрицы / В. С. Рублев, А. В. Смирнов
// Материалы XVII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). - Новосибирск: Изд-во Института математики, 2008. - С. 153-157.
7. Смирнов, А. В. О несводимости задачи целочисленного сбалансирования трехмерной матрицы к задаче о наибольшем потоке / А. В. Смирнов // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г.: Труды. - М.: Издательский отдел факультета. ВМиК МГУ им. М. В. Ломоносова; МАКС Пресс, 2009. - С. 270-273.
8. Смирнов, А. В. Целочисленное сбалансирование 3-мерной матрицы / А. В. Смирнов // Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации - 2009». 15 апреля 2009 г., Ярославль: Тезисы докладов. - Ярославль: Изд-во ЯГТУ, 2009. - С. 217.
9. Смирнов, А. В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель / А. В. Смирнов // Моделирование и анализ информационных систем. - 2009. - Т. 16, №3. - С. 70-76.
10. Смирнов, А. В. Сравнительный анализ алгоритмов целочисленного сбалансирования матрицы / А. В. Смирнов // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.). - М.: МГУ, 2010. - С. 430-432.
11. Смирнов, А. В. Задача целочисленного сбалансирования трехмерной матрицы и эффективность алгоритмов ее решения / А. В. Смирнов // Ярославский государственный университет имени П.Г. Демидова. Лучшие молодежные научно-исследовательские работы. 2009 год. - Ярославль: ЯрГУ, 2010. - С. 70-71.
12. Рублев, В. С. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения ./ В. С. Рублев, А. В. Смирнов //' Моделирование и анализ информационных систем. - 2010. - Т. 17, №2. -С. 72-98.
13. Рублев, В. С. ЫР-полнота задачи целочисленного сбалансирования 3-мерной матрицы / В. С. Рублев, А. В. Смирнов // Синтаксис и семантика логических систем: Материалы 3-й Российской школы-семинара. -Иркутск: Изд-во ГОУ ВПО «Восточно-Сибирская государственная академия образования», 2010. - С. 85-89.
14. Рублев, В. С. Задача целочисленного сбалансирования 3-мерной матрицы - Л'Р-трудиая / В. С. Рублев, А. В. Смирнов // Доклады Одесского семинара по дискретной математике. / Южный научный центр НАН и МОИ Украины. - Одесса: Астропринт, 2010. - Вып. 10. - С. 47-49.
15. Рублев, В. С. NР-полнота задачи целочисленного сбалансирования трехмерной матрицы / В. С. Рублев, А. В. Смирнов // ДАН. - 2010. - Т. 435, №3. - С. 301-303.
Работы [9), ¡12) и [15] опубликованы в рецензируемых журналах, входящих в перечень ВАК.
Подписано в печать 06.10.10. Формат 60x84/16. Бумага оф. Отпечатано на ризографе.
Тираж 100 экз. Заказ 34/10. Отдел оперативной полиграфии ЯрГУ 150000, Ярославль, ул. Советская, 14
Содержание.
Введение.
1 Постановка задачи.
2 Кратные сети и кратные потоки: обобщение теории потоков Форда-Фалкерсона.
2.1 Кратная сеть целочисленного сбалансирования.
2.2 Полный поток и обобщенный путь прорыва.
3 Алгоритм нахождения максимального кратного потока для решения задачи сбалансирования.
3.1 Предварительные замечания.
3.2 Описание алгоритма.
3.3 Примеры работы алгоритма.
3.4 Обоснование алгоритма.
4 А^Р-полиота задачи целочисленного сбалансирования трехмерной матрицы.
5 Сравнительный анализ алгоритмов целочисленного сбалансирования
5.1 Результаты вычислительных экспериментов для произвольных тестов.
5.2 Результаты вычислительных экспериментов для задач ЦСЗ
6 Минимизация ошибок округления в задаче целочисленного сбалансирования матрицы.
6.1 Задача минимизации ошибок округления и алгоритм ее решения
6.2 Пример работы алгоритма минимизации ошибок округления
Многие задачи дискретной оптимизации могут быть решены при помощи моделей и методов теории графов. Примеры приложений теории графов приведены, например, в [2, 7, 8, 16, 17, 18, 25, 34, 56, 57, 60]. Важным разделом теории графов является теория потоков Форда-Фалкерсона (см. [1, 31, 50, 59, 62]). Потоковые алгоритмы применяются для решения различных задач (см., например, [6, 9, 13, 26, 30, 33, 65, 72, 77, 80, 81]).
Наиболее известная задача теории потоков - задача о нахождении максимального потока в транспортной сети. Сведение к задаче о наибольшем потоке используется при решении ряда задач, одной из которых является задача целочисленного сбалансирования двумерной матрицы.
Различные задачи целочисленного сбалансирования возникают в сфере управления, экономики, финансов. В частности, подобная задача ставится при планировании железнодорожных грузоперевозок. Имеется матричный план по отправке вагонов, который группируется по некоторым показателям (например, направление, тип вагона, владелец вагона и т. п.). Данный план составляется на месяц и естественно является целочисленным. Однако вагоны необходимо отправлять ежедневно. При делении на количество дней в месяце план перестает быть целочисленным. Поэтому возникает проблема такого округления основных параметров, чтобы суммирующие показатели не выходили за определенные рамки. Данный план может быть представлен в виде /с-мерной матрицы, где к - это число показателей, по которым ведется суммирование.
Другой областью применения задач целочисленного сбалансирования является округление экономического плана (представленного, как некоторая «шахматка»), в котором ведется суммирование по разным показателям каких-либо удельных характеристик (нецелочисленных) и требуется округление до ближайших целых значений с сохранением балансовых округлений.
Также задачи целочисленного сбалансирования возникают в банковской сфере, например, в задаче оптимального округления плана валютных счетов (постановка такой задачи дана в [47]). Имеется некий план валютных счетов, которые группируются по нескольким показателям (например, вид валюты, клиент, дата). Такой план при к показателях может быть представлен в виде /¿-мерной сбалансированной матрицы, внутренними элементами которой являются величины счетов, а на боковых гранях стоят суммы по соответствующим показателям. При переводе одной валюты в другую возникает проблема округления величин счетов до целых чисел. Округление до ближайшего целого может привести к значительному расхождению в итоговой сумме, что ведет к определенным финансовым потерям. Поэтому необходим такой алгоритм целочисленного сбалансирования матрицы плана, чтобы расхождение в общей сумме было минимальным.
В работах [21, 24] была рассмотрена задача целочисленного сбалансирования двумерной матрицы. Пусть имеется матрица А размерности (п + 1) х (т+ 1) с вещественными элементами аг7-, для которой выполняются следующие условия баланса: п т гп п г € 1 ,п);
Ищется такая целочисленная матрица Б, что выполняются условия: dij G { [aij\, foyl} (íGO, n, j G 0, m); d00 = [а00 + 0.5J; n m тп n doo = 11, dl° = YL dij ^ e doj = dii Ü e ' i=1 J=1 j-1 г=1
Эта целочисленная матрица D называется сбалансированной для матрицы А. Без ограничения общности можно считать, что элементы исходной нецелочисленной матрицы А принадлежат полуинтервалу [0,1).
В [21, 24] показано, что задача целочисленного сбалансирования двумерного матричного плана может*быть сведена к задаче нахождения максимального потока в транспортной сети по следующим правилам:
1) Каждому элементу а^ матрицы А поставим в соответствие вершину сети Xij, а элементу аоо поставим в соответствие еще дополнительную вершину zoo
2) Соединим вход ж0 сети с каждой вершиной х¿o (i G 1,п) дугами пропускной способности [a¿oJ, а также с вершиной жоо дугой пропускной способности d00 - XXi KoJ •
3) Соединим вершину жоо с каждой из вершин Xíq (г G 1,п) дугами пропускной способности [a¿o] — |a¿oJ
4) Соединим со стоком z каждую из вершин xqj (j G 1, m) дугами пропускной способности [a0jj, а вершину z0о - дугой пропускной способности doo - Ej"Li LaoiJ •
5) Соединим с вершиной z00 каждую из вершин xqj (j G l,m) дугами пропускной способности faoj] — \aoj\
6) Соединим каждую из вершин Xíq (i G 1 ,п) со всеми вершинами х^ (i G 1, п, j G 1, га) дугами пропускной способности
7) Соединим с каждой вершиной xqj (j G 1 ,т) все вершины хц (i G l,n, j'E 1,т) дугами пропускной способности fa¿j].
Сеть целочисленного сбалансирования двумерной матрицы, построенная по данным правилам, изображена на рис. 1 (на рисунке показаны только вершины со значениями индексов 0, 1 и п,т соответственно для индексов м)
Л*11
Рис. 1. Сеть целочисленного сбалансирования двумерной матрицы
Пусть уэ - поток в построенной транспортной сети. Его величина не превосходит с?оо - суммы пропускных способностей дуг, выходящих из входа, или суммы пропускных способностей дуг, входящих в сток:
4>г < ^00
Покажем, что величина ¿оо определяет наименьшую пропускную способность разреза в сети. Каждый разрез делит все вершины транспортной сети на левую 01 и правую части и его можно описать двумя множествами вершин: = | г е 1,П, ХгО Е ОД, Т = {щ I 3 € 1дтг, Ху £ С/}.
Пропускная способность такого разреза R(S,T) = ^foiol + ЕК1 + \S\ ■ \Т\ > ies зет m п ЕгЕ+ ЕгЕ+ ЕЕ^ es 3=1 з&т i=i ies m п п тп ti m
ЕЕа^+ЕЕ а^+Е Е= Е Е ^+Е Е^ ЕЕ ies ¿=i ier ¿=i ¿es i=i ¿es J'eT ¿=i j=i и, так как R(S, T) - целое чис'ло, то n m r(S,T) > rEEayi = i=i j=i
Таким образом, минимальная пропускная способность разреза равна (¿сю и по теореме Форда-Фалкерсона (см. [59]) величина наибольшего потока в сети равна c¿oo
Пусть <р - наибольший поток в сети и f(x(j) (i G 0, п, j G 0,m) - величина потока, проходящего через вершину xij . Образуем матрицу D, для которой doo = Vz= Гаоо + 0.5], dij = f(xij) (i G 0~ñ, j G 0,ra).
Из условий неразрывности потока следует выполнение условий баланса и условий dij G {La¿jJ) ra¿jl} ^ 0,n, j G 0, m). Таким образом, задача сбалансирования двумерной матрицы всегда имеет решение и его можно получить, построив алгоритм на основе алгоритма пометок для решения задачи о наибольшем потоке.
В случае, когда задача целочисленного сбалансирования имеет несколько решений, возникает вопрос о нахождении сбалансированной матрицы D, наименее отклоняющейся от исходной (см. [24]). В качестве меры отклонения здесь естественно взять либо сумму абсолютных величин отклонений; либо сумму квадратов отклонений. Покажем, что эту задачу можно свести к решению некоторой задачи о наибольшем потоке минимальной стоимости для описанной выше транспортной сети со следующей функцией стоимости С, определенной на дугах сети: с(хго.Жу) = 1 - <2у (г е 1,71, 3 € 1,т)\ с = 0 для всех остальных дуг сети.
Покажем, что сбалансированная матрица I)0, соответствующая наибольшему потоку минимальной стоимости обращает в минимум функционалы
I п т
ЕЕ г=1 ,7 = 1
1п т
Е^--^)2- (2)
1=1 1=1
Пусть Б1 - сбалансированная целочисленная матрица, доставляющая минимум функционалу (1) и предположим противное: г=1 ]—1 ¿=1 j=l
Тогда
Ее1-ау) + Е < Е ^ ~ + Е аУ ■■
Разобьем каждую сумму на две:
4=1 4=0 4=0
1 - + Е ^ ~+ Е + Е <
4=1=4 4=^4 4=0=4 4=0^4 Е (1ау)+ Е (1ау)+ Е Е
4=1=4. 4=1^4 4=°=4
После приведения получим:
Е Е Е (!-%)+ Е
4=^4 4=0^4 откуда следует
1-2 а13)< 22 (1-2ау).
Так как обе матрицы сбалансированы, то число их нулевых элементов одинаково (как и единичных), а потому одинаково число элементов, которые для одной матрицы равны 0, а для другой равны 1, с числом элементов, которые для одной матрицы равны 1, а для другой равны 0. Поэтому из последнего неравенства получаем
22 аг? > Е
4=1*4 4=1 Так как матрица минимальна по стоимости, то
4=1 4=1 откуда получаем
Х-а>1])< Е С1"^) и далее агз < аV
4=1*4 4=1^Ч
Последнее неравенство противоречит неравенству (3), что и требовалось для доказательства минимальности функционала (1) для матрицы В0
Из минимальности стоимости г аго
22(1 - агз) = N0 + 0.5] -4=1 4=о следует максимальность Но значение функционала (2) п тп
22 Е^у -= I] ^ -+ Е 4 =
1=1 7 = 1 4=1 4=0 1 - 2 22 аг3 + 22 < + Е аЪ =соп^ -2 Е
4=1 4=1 4=1 4=0 4=1 агЗ при этом минимально, что и требовалось доказать.
Аналогичная задача сбалансирования может быть поставлена и в трехмерном случае (см., например, [41, 42, 45]). Имеется трехмерная вещественная матрица А с неотрицательными элементами (г £ 0, п, ] 6 0,ш, р € 0, £), для которых выполнены условия баланса: каждый элемент с некоторыми 7гулевыми индексами равен сумме всех элементов, для которых ненулевые индексы оставлены неизменными, а нулевые индексы заменены всеми возможными ненулевыми значениями диапазонов соответствующих индексов.
Требуется так округлить элементы матрицы до целых значений сверху или снизу (элемент аооо округляется до ближайшего целого), чтобы остались неизменными условия баланса. |
Данная задача намного сложнее двумерной, многие ее аспекты требуют серьезного изучения. Данная работа будет посвящена исследованию задачи целочисленного сбалансирования трехмерной матрицы. Среди основных инI тересующих нас вопросов выделим:
1) возможность простого сведения к потоковой задаче;
2) существование решения'в задаче сбалансирования;
3) построение алгоритма, который мог бы находить решение возможно боI лее эффективным методом, чем общий метод решения задач целочисленного линейного программирования;
4) решение задачи минимизации ошибок округления при целочисленном сбалансировании;
5) сложность задачи сбалансирования.
Наконец, отметим, что задачи целочисленного сбалансирования являются частным случаем задач оптимального округления. Классификация таких задач приведена, например, в [39]. В общем случае задача оптимального округления ставится следующим образом.
Задано множество А = {ai,. ., ап} основных значений, некоторое множество А его подмножеств Aj С А (j б 0, т) (назовем их подмножествами связей), включая исходное множество (А = {Aj \ А3 С А (j Е 1, т), Л о = А}), и множество D — {dj (j £ 0,m)} дополнительных значений, связывающих элементы каждого из соответствующих подмножеств: clj = Yla^A, (jGÜ~m).
Округление для (¿о считается 'заданным. Требуется округлить основные и дополнительные вещественные значения так, чтобы для множества X округленных основных значений, множества Y округленных дополнитель
I ных значений и подмножеств Х3 С X (j £ 0, га), состоящих из округленных элементов соответствующих подмножеств Aj выполнялись те же связи У] — Yhx%€XjXl (з ^ 0, ттг). В качестве критерия оптимальности берется минимизация суммы ошибок основных элементов при условии определенной близости I округлений дополнительных элементов: тг у3 - dj| < I {I G IN, j б 0,т) \xi ~ ai\ min •
Другой критерий оптимальности - минимизация суммы ошибок дополнительных элементов при условии близости округлений основных элементов т
Х{ — а;! < 1 (г € 1,п) ^^ \Уз — dj| —> min i=l рассматривается в задачах округления значительно реже.
Нетрудно заметить, что задача целочисленного сбалансирования ^-мерной матрицы при произвольном натуральном к является задачей оптимального округления. В работе [37] приведен еще один пример подобной задачи.
Заключение
В данной работе рассмотрена задача целочисленного сбалансирования трехмерной матрицы. Показано, что для этой задачи не существует эффективного сведения к задаче о максимальном потоке, в связи с чем построено обобщение теории потоков Форда-Фалкерсона, названное кратными сетями и кратными потоками. Установлена сводимость задачи сбалансирования к задаче о нахождении максимального кратного потока, удовлетворяющего определенным условиям разрешимости. Показано, что выполнение данных условий разрешимости для максимального потока необходимо и достаточно для существования решения в задаче сбалансирования. Получен и обоснован алгоритм решения задачи о наибольшем кратном потоке данного вида.
Также в работе показана А^Р-полнота задачи целочисленного сбалансирования трехмерной матрицы.
Кроме того, рассмотрена задача минимизации ошибок округления в задаче целочисленного сбалансирования, приведен и обоснован алгоритм ее решения.
Таким образом, получены ответы на все основные вопросы, интересовавшие нас в ходе исследования.
1. Адельсон-Вельский, Г. М. Потоковые алгоритмы / Г. М. Адельсон-Вельский, Е. А. Диниц, А. В. Карзанов. - М.: Наука, 1975. - 120 с.
2. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. Ижевск: НИЦ «РХД», 2001. - 288 с.
3. Афраймович, Л. Г. Многоиндексные задачи распределения ресурсов в иерархических системах / Л. Г. Афраймович, М. X. Прилуцкий // Автоматика и телемеханика. 2006. - №6. - С. 194-205.
4. Афраймович, Л. Г. Многопродуктовые потоки в древовидных сетях / Л. Г. Афраймович, М. X. Прилуцкий // Известия РАН. Теория и системы управления. 2008. - №2. - С. 57-63.
5. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - 536 с.
6. Вабенко, М. А. Быстрый алгоритм построения декомпозиции многополюсных потоков / М. А. Бабенко // Вестник Московского университета. Серия 1: Математика. Механика. 2006. - №2. - С. 52-53.
7. Басакер, Р. Конечные графы и сети / Р. Басакер, Т. Саати. М.: Наука, 1974. - 368 с.
8. Берж, К. Теория графов и ее приложения / К. Берж. М.: Изд-во ИЛ, 1962. - 320 с.
9. Водолазов, Н. Н. Об особенностях потока в сетях с барьерной достижимостью / Н. Н. Водолазов // Вестник ДГТУ. 2008. - Т. 8, №2. -С. 127-136.
10. Гасс, С. Линейное программирование (методы и приложения) / С. Гасс. М.: Физматгиз, 1961. - 304 с.
11. Голынтейн, Е. Г. Новые направления в линейном программировании / Е. Г. Голыптейн, Д. Б. Юдин. М.: Сов. радио, 1966. - 524 с.
12. Гофман, А. Д. Целочисленные граничные точки выпуклых многогранников / А. Д. Гофман, Д. Б. Краскал // Линейные неравенства и смежные вопросы. М.: Изд-во ИЛ, 1959. - 472 с.
13. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэ-ри, Д. Джонсон. М.: Мир, 1982. - 416 с.
14. Данциг, Д. Линейное программирование, его обобщения и применения / Д. Данциг. М.: Прогресс, 1966. - 600 с.
15. Евстигнеев, В. А. Применение теории, графов в программировании / В. А. Евстигнеев. М.: Наука, 1985. - 352 с.
16. Зыков, А. А. Основы теории графов / А. А. Зыков. М.: Наука, 1987.- 384 с.
17. Камерон, П. Теория графов, теория кодирования и блок-схемы / П. Камерон, Дж. ван Линт. М.: Наука, 1980. - 144 с.
18. Кнут, Д. Э. Искусство программирования, тт. 1,2,3 / Д. Э. Кнут. М.: Вильяме, 2000.
19. Ковалев, М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. Мн.: Изд-во БГУ, 1977. - 192 с.
20. Кондаков, А. С. Задача сбалансирования матрицы плана / А. С. Кондаков, В. С. Рублев // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. Одесса: Астропринт, 2005. - Вып. 2. - С. 24-26.
21. Корбут, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкелынтейн. М.: Наука, 1969. - 368 с.
22. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзёрсон, Р. Ривест, К. Штайн. М.: Вильяме, 2005. - 1296 с.
23. Коршунова, Н. М. Задача целочисленного сбалансирования матрицы / Н. М. Коршунова, В. С. Рублев // Современные проблемы математики и информатики. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. - Вып. 3.- С. 145-150.
24. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кри-стофидес. М.: Мир, 1978. - 432 с.
25. Кузьминова, M. В. Периодические динамические графы. Задача о максимальном потоке / М. В. Кузьминова // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки. -2008. №1. - С. 14-19.
26. Кук, Д. Компьютерная математика / Д. Кук, Г. Бейз. М.: Наука, 1990.- 384 с.
27. Кук, С. А. Сложность процедур вывода теорем / С. А. Кук // Кибернетический сборник, новая серия. М.: Мир, 1975. - Вып. 12 - С. 5-15.
28. Литвак, Б. Г. Задачи линейного программирования, допускающие сетевую постановку / Б. Г. Литвак, А. М. Раппопорт // Экономика и мат. методы. 1970. - Т. 6, вып. 4. - С. 594-604.
29. Лютаев, Д. А. Моделирование транспортной сети Владивостока на основе теории потокового равновесия / Д. А. Лютаев // Информатика и системы управления. 2006. - №2(12). - С. 17-28.
30. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника.- М.: Мир, 1981. 324 с.
31. Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл.- 2-е доп. изд. М.: Техносфера, 2004. - 368 с.
32. Миронов, А. А. Взвешенные графы с фиксированными степенями вершин и потоки в сетях / А. А. Миронов // Известия РАН. Теория и системы управления. 2007. - №3. - С. 81-84.
33. Ope, О. Теория графов / О. Ope. M.: Наука, 1980. - 336 с.
34. Пападимитриу, X. Комбинаторная оптимизация / X. Пападимитриу, К. Стайглиц. М.: Мир, 1984. - 512 с. .
35. Раскин, Л. Г. Многоиндексные задачи линейного программирования / Л. Г. Раскин, И. О. Кириченко. М.: Радио и связь, 1982. - 240 с.
36. Рублев, В. С. Минимизация ошибок округления плана / В. С. Рублев // Математика, кибернетика, информатика. Труды Международной конференции, посвященной памяти профессора А. Ю. Левина, 25-26 июня 2008 г. Ярославль: ЯрГУ, 2008. - С. 145-150.
37. Рублев, В. С. Потоковый алгоритм целочисленного сбалансирования матрицы / В. С. Рублев // Материалы VII Международного семинара «Дискретная математика и ее приложения» (29 января 2 февраля 2001 г.). Часть II. - М.: МГУ, 2001. - С. 185-187.
38. Рублев, В. С. TVP-полнота задачи целочисленного сбалансирования трехмерной матрицы / В. С. Рублев, А. В. Смирнов // ДАН. 2010. -Т. 435, №3. - С. 301-303.
39. Рублев, В. С. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения / В. С. Рублев, А. В. Смирнов // Моделирование и анализ информационных систем. 2010. - Т. 17, №2. -С. 72-98.172 I
40. Рублев, В. С. Целочисленное сбалансирование 3-мерной матрицы плана /' В. С. Рублев, А. В. Смирнов // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское 4-6 марта 2006 г.). М.: МГУ, 2006. - С. 302-308.
41. Рублев, В. С. Задача оптимального округления плана валютных счетов / В. С. Рублев, А. В. Смирнов // Кибернетика и высокие технологии XXI века. Воронеж: НПФ «Саквоее», 2008. - Т. 1. - С. 112-123.
42. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. -М.: Мир, 1984. 456 с.
43. Смирнов, А. В. Задача целочисленного сбалансирования трехмернойматрицы и сетевая модель / А. В. Смирнов // Моделирование и анализинформационных систем. 2009. - Т. 16, №3. - С. 70-76.
44. Смирнов, А. В. Сравнительный анализ алгоритмов целочисленного сбалансирования матрицы / А. В. Смирнов // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.). М.: МГУ, 2010. - С. 430-432.
45. Смирнов, А. В. Целочисленное сбалансирование 3-мерной матрицы /
46. Татт, У. Теория графов / У. Татт. М.: Мир, 1988. - 424 с.
47. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. -208 с.
48. Феллер, В. Введение в теорию вероятностей и ее приложения, тт. 1,2 /1. B. Феллер. М.: Мир, 1967.
49. Форд, Л. Р. Потоки в сетях / Л. Р. Форд, Д. Р. Фалкерсон. М.: Мир, 1966. - 276 с.
50. Харари, Ф. Теория графов / Ф. Харари. М.: Мир, 1973. - 304 с.
51. Хачиян, Jl. Г. Полиномиальный алгоритм в линейном программировании / Л. Г. Хачиян // ДАН СССР. 1979. - Т. 244, №5. - С. 1093-1096.
52. Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху. М.: Мир, 1974. - 520 с.
53. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. М.: Наука, 1986. - 384 с.
54. Bazaraa, M. Linear programming and network flows / M. Bazaraa, J. J. Jarvis. 2nd ed. - New York: John Wiley к Sons, 1990. - 684 p.
55. Bondy, J. A. Graph theory with applications / J. A. Bondy, U. S R. Murty. New York: American Elsevier, 1977. - 272 p.
56. Dantzig, G. B. Note on solving linear programs in integers / G. B. Dantzig // Naval Research Logistics Quarterly. 1959. - V.6, №1. - P. 75-76.
57. Dantzig, G. B. Application of the simplex method to a transportation problem / G. B. Dantzig // Activity Analysis of Production and Allocation / Editor: Т. C. Koopmans. New York: Wiley, 1951. - P. 359-373.
58. Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems / J. Edmonds, R. Karp // Journal of the Association for Computing Machinery. 1972. - V. 19, №2. - P. 248-264.
59. Ford, L. R. Maximal flow through a network / L. R. Ford, D. R. Fulkerson // Canadian Journal of Math. 1956. - №8. - P. 399-404.
60. Garey, M. R. Strong NP-completeness results: motivation, examples and implications / M. R. Garey, D. S. Johnson // Journal of the Association for Computing Machinery. 1978. - V. 25, №3. - P. 499-508.
61. Goldberg, A. V. Finding minimum-cost circulations by canceling negative cycles / A. V. Goldberg,' R. E. Tarjan // Journal of the Association for Computing Machinery. 1989. - V. 36, №4. - P. 388-397.
62. Gomory, R. E. An algorithm for integer solutions to linear programs / R. E. Gomory // Recent Advances Math. Program. New York, San Francisco, Toronto, London: McGraw-Hill Book Co., Inc., 1963. - P. 269302.
63. Gomory, R. E. Outline of an algorithm for integer solutions to linear programs / R. E. Gomory // Bull. Amer. Math. Soc. 1958. - V. 64, №5. - P. 275-278.
64. Gomory, R. E. Solving linear programming problems in integers / R. E. Gomory // Proc. Sympos. Appl. Math. 1960. - V. X. - P. 211215.
65. Gomory, R. E. An application of generalized linear programming to network flows / R. E. Gomory, T. C. Hu // Journal of the Society for Industrial and Applied Mathematics. 1962. - V. 10, №2. - P. 260-283.
66. Imai, H. On the practical efficiency of various maximum flow algorithms / H. Imai // Journal of the Operations Research Society of Japan. 1983. -V. 26, №1. - P. 61-83.
67. Karp, R. Reducibility among' combinatorial problems / R. Karp // Complexity of Computer Computations / Editors: R. E. Miller, J. W. Thatcher. New York: Plenum, 1972. - P. 85-103.
68. Lawler, E. Combinatorial optimization: networks and matroids / E. Lawler. Holt, Rinehart and Winston, 1976. - 384 p.
69. Lempitsky, V. Global optimization for shape fitting / V. Lempitsky, Y. Boykov // Proc. IEEE CVRP'07. IEEE Computer Soc, 2007 - P. 1-8.
70. Lombaert, H. A multilevel banded graph cuts method for fast image segmentation / H. Lombaert, Y. Sun, L. Grady, C. Xu // Proc. IEEE ICCV'05 IEEE Computer Soc., 2005. - V. 1. - P. 259-265.
71. Papadimitriou, C. H. On the complexity of integer programming / C. H. Papadimitriou // Journal of the Association for Computing Machinery. 1981. - V. 28, №4. - P. 765-768.
72. Picard, J. C. Minimum cuts and related problems / J. C. Picard, H. D. Ratliff // Networks 1975. - V. 5, №4. - P. 357-370.
