Модели оптимизационных задач, связанных с обобщенной задачей о назначениях тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Григорчук, Сергей Евгеньевич

• Григорчук, Сергей Евгеньевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Григорчук, Сергей Евгеньевич

Введение.

Глава I. Модель обобщенной задачи о назначении.

§ 1. Постановка классической задачи о назначении.

§ 2. Постановка обобщенной задачи о назначении.

§ 3. Применение для обобщенной задачи о назначении алгоритмов классической задачи о назначении.

§ 4. Определение решений задачи о назначении с помощью блокового индикатора.

§ 5. Определение решений задачи о назначении с помощью циклового индикатора.

§ 6. Модели оптимицазионных задач, связанных с обобщенной задачей о назначении.

Глава II. Алгоритмы вычисления цикловых индикаторов матриц.

§ 1. Определение обобщенного циклового индикатора.

§ 2. Цикловой индикатор оболочки единичной и подстановочной матрицы.

§ 3. Цикловые индикаторы теплицевых матриц.

§ 4. Вычисление циклового индикатора 5-диагонального циркулянта.

§ 5. Некоторые частные случаи.

§ 6. Вычисление цикловых индикаторов (ОД)-матриц.

§ 7. Улучшенный алгоритм вычисления циклового индикатора перестановок с ограниченными позициями.

§ 8. Вычисление цикловых индикаторов матриц с целыми элементами.

Глава III. Алгоритмы вычисления цикловых индикаторов пар перестановок с ограниченными позициями.

§ 1. Основные понятия.

§ 2. Вычисление преддиперманента.

§ 3. Об одном рекуррентном процессе перечисления Л^-матриц.

§ 4. Общий алгоритм вычисления диперманента и хроматического диперманента.

§ 5. Вычисление диперманентов матриц с целыми элементами.

§ 6. Понятие циклового индикатора пар противоречивых перестановок с ограниченными позициями.

§ 7. Вычисление прединдикатора.

§ 8. Общий алгоритм.

§ 9. Вычисление цикловых индикаторов пар противоречивых перестановок с ограниченными позициями.

§10. Алгоритм вычисления ^-хроматического перманента

B.C. Шевелева (случай к=3).

§11. Вычисление 3-хроматического перманента B.C. Шевелева.

Введение диссертации (часть автореферата) на тему «Модели оптимизационных задач, связанных с обобщенной задачей о назначениях»

Современные ЭВМ являются эффективным средством для исследователей в процессе математического моделирования сложных задач науки и техники. Поэтому в настоящее время количественные методы исследования проникают во все сферы человеческой деятельности и математические модели становятся средством познания.

Развитие вычислительной техники и исследования операций вызвало повышенный интерес к комбинаторной математике. Оно привело с одной стороны, к постановке новых комбинаторных задач, а с другой стороны дало эффективные способы их решения с помощью ЭВМ. Комбинаторные задачи, встречающиеся в различных областях знания, часто приводят к проблеме оптимизации. Задачи о потоке минимальной стоимости или транспортные задачи являются важной областью линейного программирования. К этим задачам относится большая часть многих конкретных промышленных и военных приложений линейного программирования. Задача о назначении (или задача выбора) является частым случаем стандартной транспортной задачи (или задачи Хитчкока). В силу вырожденности этой задачи алгоритм решения транспортной задачи применим, но неэффективен.

В диссертации была дана постановка обобщенной задачи о назначениях и рассмотрены цикловые индикаторы (ОД)-матриц - производящие функции чисел перестановок с ограниченными позициями и заданной цикловой структурой - практическое применение которых связано с задачей о назначениях. Для каждой матрицы размерностью пхп задача о назначениях состоит в выборе п элементов - по одному в каждой строке и по одному в каждом столбце, таких, что их сумма минимальна. Обозначим выбранные элементы хи , x2j, ., хт, где ij,.,t - некоторая перестановка элементов 1,2,.,и. Таких перестановок - п\ , так что даже при минимальном количестве п решение полным перебором является недопустимо длинным . Вычисление цикловых индикаторов (ОД)-матриц позволяет исследовать разрешимость или число решений задачи о назначениях, решаемой как в рамках некоторого объединения предприятий (треста), так и одновременно внутри каждого входящего в него предприятия. Однако применение цикловых индикаторов оптимизирует решение лишь на перестановках, являющихся полными циклами и стало быть, не дает полного решения поставленной B.C. Шевелевым в конце статьи [32] обобщенной задачи о назначениях. Поэтому для решения обобщенной задачи о назначениях был введен блоковый индикатор, являющийся аналогом циклового индикатора. Если известна численность сотрудников по предприятиям (ти т2,., тг), то в блоковом индикаторе матрицы задачи о назначениях следует положить равными нулю все ^ , для которых / Ф тх, т2,.,тг . Если при этом блоковый индикатор окажется, не равен нулю, то задача разрешима и, как правило, имеет несколько альтернативных решений. Если же блоковый индикатор окажется равным нулю, то следует либо изменить распределение сотрудников по предприятиям, либо обучить некоторых сотрудников смежным профессиям (при этом нули матрицы задачи заменяются единицами), либо, наконец, сузить спектр работ или же организовать вакантные места, на которые принять новых специалистов. Автором разработан и реализован на ЭВМ алгоритм вычисления блокового индикатора, позволяющий найти число решений обобщенной задачи о назначении, а также алгоритм вычисления циклового индикатора для перестановок, являющихся полными циклами, позволяющий, кроме числа решений обобщенной задачи о назначении, находить и сами решения.

Приведены различные модели оптимизационных задач, связанных с обобщенной задачей о назначениях. Это применение обобщенной задачи о назначениях для локальных компьютерных сетей, для оптимизации продаж коммерческой компании и для модели о распределении заготовок деталей на станках.

Для исследования обобщенной задачи о назначении был применен следующий комбинаторный аппарат: перманенты и цикловые индикаторы матриц.

Перманенты представляют собой объект математического исследования, в настоящее время весьма распространенный, прежде всего в комбинаторике и линейной алгебре. Теория перманентов дважды стохастических матриц и (ОД)-матриц стала существенной и неотъемлемой частью комбинаторной математики, а именно того ее раздела, где рассматриваются матричные комбинаторные задачи. Интересные сами по себе проблемы, связанные с перманентами, приобрели актуальность также в связи с многообразными их приложениями - как математическими (например, в алгебре и теории вероятностей), так и в других отраслях знания (в квантовой теории поля, физической химии, статической физике).

Матрицы с элементами 0 и 1, т.е. (ОД)-матрицы играют важную роль в линейной алгебре, комбинаторике и теории графов.

Пионером в использовании перманентов в физике являлся Каяньелло, применивший их к проблеме перенормирования в квантовой теории поля. Наиболее важны приложения перманентов в тех областях физики и химии, где статистические методы применяются для изучения явлений, представляющих собой результат совместного действия очень большого числа однородных элементов.

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

Современное развитие комбинаторного анализа тесно связано с использованием производящих функций. Согласно Беллу {Bell Е.Т.), для использования этих функций в комбинаторике, естественно их считать инструментом алгебры последовательностей и поэтому, относить к алгебре, а не к анализу, несмотря на внешнее сходство с производящими функциями из анализа. Использование производящих функций намного сокращает объем необходимых преобразований, позволяет унифицировать многие результаты и тем самым дает возможность охватить значительно больший круг вопросов. Применяя производящие функции в качестве основного орудия комбинаторики, можно показать, что метод включения и исключения связан с использованием факториальных моментов (что должно представлять некоторый интерес для статистиков). Наконец, метод производящих функций хорошо согласуется с методом представления вероятностей, данного В. Феллером.

Определение комбинаторного анализа де Моргана утверждает, что коэффициенты производящих функций могут быть определены путем решения комбинаторных задач, но и комбинаторные задачи могут быть решены с помощью определения коэффициентов производящих функций. То есть производящая функция подходящего вида может являться важным средством унификации при исследовании комбинаторных проблем. Если комбинаторный анализ является методом для отыскания коэффициентов при сложных преобразованиях с производящими функциями, то и обратно эти функции можно рассматривать как порождающие соответствующие коэффициенты. Поэтому изучение производящих функций естественным образом связано с изучением коэффициентов, входящих в выражения для этих функций.

Известно, что цикловые индикаторы перестановок из п элементов, являющиеся производящими многочленами для чисел перестановок, принадлежащих заданному цикловому классу, т.е. имеющих заданное число циклов в зависимости от их длин, играют важную роль в решении многих комбинаторных задач, связанных с различными ограничениями на цикловую структуру таких перестановок.

До сих пор с помощью циклового индикатора изучались либо перестановки без каких-либо ограничений на позиции, либо перестановки без неподвижных точек (беспорядки). Классические цикловые индикаторы перестановок (без ограничения на их позиций) были введены и активно использованы американскими математиками Дж. Риорданом и Ирв. Капланским.

Дж. Риорданом были рассмотрены перестановки из п элементов класса (&)=(&!,£2,.,&„), содержащие кх единичных циклов, кг двойных циклов и т.д.

Пусть С(к{,к2,.,кп) есть число перестановок из л элементов класса (к). Формула, определяющая общее число таких перестановок: п\

С(къкъ.,кп) = -т-г-т-, где кх+2к2+.+пк„ - п.

Производящая функция чисел С(к} ,к2,. ,кп) должна иметь вид многочлена от многих переменных, т.к. п видов циклов должны быть независимы. Этот факт выражается соотношением

Тогда,

А)— X п\

V1У V2у Vп

Эта сумма берется по всем целым к>0,1=1,.,п таким, что кх+2кг+.,+пкп = п , или, что то же самое, по всем разбиениям числа п.

Функция Сп (/1,/2,.--А) называется цикловым индикатором (указателем) симметрической группы.

Дж. Риорданом приведены результаты вычисления этого циклового индикатора для п=1 .9 и показана их связь с полиномами Белла и другие свойства. Так как каждая перестановка относится к некоторому цикловому классу, то сумма всех числовых коэффициентов в выражении для Сп равна п\ , т.е. С„ (1,1,.,1) = п\.

Риорданом также рассмотрены с помощью классических цикловых индикаторов такие задачи как: о числе перестановок из п элементов, состоящих из к циклов без учета их длины, о числе перестановок из п элементов, состоящих из к циклов, отличных от единичных, получены присоединенные числа Стирлинга первого и второго рода.

С теорией перестановок с ограничениями на позиции переставляемых элементов связаны такие задачи как задача о встречах, задача о гостях, задача о ладьях и аналогичные им. В общей форме задача о встречах состоит в подсчете числа перестановок из п различных элементов в соответствии с числом элементов, занимающих в них собственные позиции. С перестановками, фигурирующими в задаче о встречах, связана простейшая задача со следующим ограничением позиций: г'-му элементу запрещено занимать г-ю позицию. Родственной ей является задача, названная Э. Люка "задачей о гостях" или "задачей о супружеских парах" (problem des ménages). Эта задача состоит в подсчете числа способов размещения (за круглым столом) п супружеских пар при условии чередования мужчин и женщин и с запрещением жене сидеть рядом с мужем. Если жены уже рассажены (2п\ способами), то задача о гостях сводится к подсчету числа способов размещения мужей. Если перенумеровать мужей числами от 1 до п, то приведенная задача о гостях сводится к подсчету таких перестановок, в которых г'-й элемент не может занимать ни г'-ю, ни z+1-ю позиции (/=1,.,и-1) и п-й элемент не может занимать ни п-ю позицию, ни первую позицию (т.к. стол круглый). Иными словами, требуется перечисление перестановок, противоречивых перестановкам 12.п и 2Ъ.п\. Имеется также формулировка Тейта для этой задачи в случае прямоугольного стола, когда гости рассаживаются по одну сторону стола. Эти варианты задачи о гостях рассматривались Кэли и Мьюиром, Е. Гильбертом, Тушаром и Капланским.

Любые ограничения на позиции в перестановках могут быть изображены с помощью квадратной матрицы, в которой переставляемые элементы отмечаются номерами столбцов, а позиции - номерами строк. Крестик (или 0), проставленный на пересечении строки и столбца, означает соответствующее ограничение. Т.к. в квадратной матрице ограничений на позиции элементов перестановки размера п имеется п1 элементов, в каждом из которых может проставляться крестик (или 0) или нет (тогда 1), 2 то возможны 2п задач (сюда входят и перестановки без ограничений, когда ни один из элементов матрицы ограничений не отмечен крестиком или 0). Однако некоторые из задач не являются различными, т.к. при перечислении существенно относительное, а не абсолютное расположение крестиков. Кроме того, некоторые задачи не имеют существенного значения. Наиболее интересные задачи имеют схемы ограничений следующих типов: 1) "диагональные" и "лестничные", подобные упомянутым выше в задачах о встречах и гостях; 2) прямоугольные и 3) треугольные.

Лестничные схемы связаны с "латинскими прямоугольниками", впервые изученными Эйлером. Латинским прямоугольником называется прямоугольная матрица, в которой каждый ряд представляет собой перестановку из одних и тех же п элементов, причем в каждом столбце все различны. Латинский прямоугольник с двумя строками и п столбцами, можно нормировать, расположив элементы первой строки в естественном порядке (12. и). Такие латинские прямоугольники называют редуцированными. Тогда во второй строке могут содержаться только перестановки, фигурирующие в задаче о встречах. Число 2-строчных латинских прямоугольников L(2,ri) = п\К(2,п), а число редуцированных латинских прямоугольников K(2,n)=Dn , где Dn - число перестановок без единичных циклов. Более сложная зависимость существует между числом 3-строчных латинских прямоугольников и числом решений задачи о гостях. Дальнейшим усложнением является переход к схемам, подобным трехступенчатой лестнице, связанными в некотором смысле с 4-строчными латинскими прямоугольниками, о которых фактически известно очень мало.

Задача о ладьях состоит в определении числа способов размещения на шахматной доске к не угрожающих друг другу ладей. Любую задачу о перестановках с ограниченными позициями можно свести к задаче о ладьях на доске с соответствующими ограничениями позиций, т.е. некоторые позиции запрещены и отмечены крестиками. Ладейным многочленом доски М (квадратная (ОД)-матрица размера п) называется многочлен п к=1 гк - число способов размещения к неатакующих друг друга ладей на позициях единиц доски М. При к^п rk = per М (перманент М). Ладейные многочлены и техника, основанная на их свойствах, являются основным инструментом в важном разделе комбинаторного анализа, связанном с изучением перестановок с ограниченными позициями. В последние два десятилетия интерес к ладейным многочленам оживился, главным образом благодаря работам Гольдмана и др.

В настоящее время в теории перечисления перестановок получила с одной стороны, ладейная техника и, в частности, техника вычисления перманентов, позволяющая перечислять перестановки с ограниченными позициями. Однако, эта техника недостаточна в случае каких-либо ограничений на цикловую структуру перестановок. С другой стороны, хорошо известна техника, основанная на методе производящих функций и в настоящее время хорошо формализованная. Эта техника связана по существу с исследованием в различных случаях циклового индикатора подстановок и позволяет перечислять перестановки с различными ограничениями на их цикловую структуру, либо удовлетворяющие различным геометрическим условиям (числа подъемов, спадов и т.д.), но недостаточна в случае ограничений на позиции перестановок. Долгое время казалось, что эти направления комбинаторики перестановок мало совместимы. На пути к единству ладейной и индикаторной техники с помощью циклического многочлена (или цикломента) квадратной матрицы впервые Шевелевым был получен общий алгоритм перечисления перестановок с ограниченными позициями и фиксированным числом циклов.

Циклический многочлен или цикломент квадратной матрицы А={а^} порядка п :

Cycl{A; i) = П aio(i) = X ' aeSn i=1 j=1 \ J S П где

S„ - симметрическая группа подстановок степени п , |а| - число циклов подстановки су.

Коэффициенты цикломента в случае (ОД)-матриц перечисляют диагонали, состоящие из единиц, с фиксированным числом циклов. Задавая, как обычно, множество запрещенных позиций перестановки множеством позиций нулей некоторой (ОД)-матрицы, сводим решение задачи о числе перестановок с заданным ограничением позиций и заданным числом циклов к вычислению цикломента этой матрицы. Таким образом, любой алгоритм вычисления цикломента является одновременно и алгоритмом решения задачи о числе перестановок с заданным ограничением позиций и заданным числом циклов. Кроме того, этот алгоритм является алгоритмом параллельного вычисления детерминанта и перманента матрицы, так как Cycl(A; 1) =per А и Сус/(А; -1) - (-1)" det А .

B.C. Шевелевым были исследованы основные свойства цикломента, вычислены цикломент оболочки единичной и подстановочной матрицы, цикломент циркулянта а1п+Рк, где Р - матрица перестановки, соответствующая циклу (1,2,.,п), 1п - единичная матрица, а также цикломенты некоторых циркулянтов и цикломенты матриц, соответствующих циклическому и линейному варианту классической задачи Люка о супружеских парах. Для теплицевых матриц В.С.Шевелевым был развит метод коэффициентов вычисления цикломента.

Обобщим сказанное, указав, что до 1990 года по существу был известен лишь классический результат, связанный с явными и рекуррентными формулами вычисления циклового индикатора без ограничений на позиции и примыкающий к нему результат о цикловом индикаторе перестановок без неподвижных точек. С точки зрения терминологии, данной в диссертации, были изучены лишь классы перестановок с характеристическими матрицами A=J„ и A=J„-I, где in -пхп матрица из единиц, I - единичная матрица. Эти результаты приведены в работах Риордана, а также им рассмотрены некоторые классы перестановок с ограниченными позициями, но без каких-либо ограничений на цикловую структуру. В 1991 году B.C. Шевелев изучал (в терминологии, данной в диссертации) цикловой индикатор классов перестановок с ограничением позиций с характеристической (0,1)-матрицей в частом случае одной переменной и назвал его циклическим многочленом или цикломентом (ОД)-матрицы. Основной результат его работы состоял в обосновании возможности разложения цикломента полюбой строке (столбцу) матрицы путем применения операторов циклической престановки столбцов. Этот результат позволил впервые B.C. Шевелеву получить алгоритм перечисления перестановок с произвольным ограничением позиций и заданым числом циклов.

В дальнейших работах B.C. Шевелева была впервые решена в общем виде задача о перечислении перестановок с ограниченными позициями и заданным числом циклов. Автором, совместно с B.C. Шевелевым, было дано понятие обобщенного циклового индикатора и разработан и реализован на ЭВМ алгоритм вычисления обобщенного циклового индикатора произвольного класса перестановок с ограниченными позициями (см. гл. III §6). Автором также указан новый алгоритм вычисления циклового индикатора перестановок с ограниченными позициями, основанный на совершенно другой идее. Приводимая в главе II §7-8 реализация этого алгоритма на ЭВМ показала, что скорость счёта по новому алгоритму существенно выше. Кроме того, в настоящей работе вычислены явно цикловые индикаторы оболочки единичной и подстановочной матрицы, циркулянта а1п+Рк, где Р - матрица перестановки, соответствующая циклу (1,2,.,я), 1п - единичная матрица, а также вычислены цикловые индикаторы теплицевых матриц, цикловой индикатор 5-диагонального циркулянта, некоторых циркулянтов и цикловые индикаторы матриц, соответствующих циклическому и линейному вариантам классической задачи Люка о супружеских парах и обобщенным задачам.

Как известно, различные алгоритмы перечисления перестановок с ограниченными позициями являются по существу алгоритмами вычисления перманентов (ОД)-матриц. Сейчас имеется множество таких алгоритмов разной степени эффективности (алгоритмы Райзера, Гэла-Брайтберта, Каммингса и Уоллиса и др.). Автору, однако, неизвестны какие-либо алгоритмы перечисления пар противоречивых перестановок с ограниченными позициями, несмотря на очевидную актуальность и естественность постановки такой задачи. Это, по-видимому, связано со значительным увеличением сложности задачи. Автором был рассмотрен такой алгоритм - общий алгоритм вычисления диперманента, введённого В.С.Шевелевым. Этот алгоритм позволил также экспериментально подтвердить приведённые в [16] и пока ещё не доказанные гипотезы В.С.Шевелева для перманентов бинарных дважды стохастических матриц, являющиеся аналогами знаменитой классической гипотезы Ван дер Вардена, доказанной Г.П. Егорычевым и Д.И. Фаликманом.

Теория перестановок с ограниченными позициями является одним из важнейших разделов перечислительной комбинаторики. Переход от перестановок к парам перестановок ( и далее - к конечным наборам перестановок ) совершенно естествен и связан с перечислением латинских прямоугольников с ограничениями на позиции их элементов и классов их эквивалентности. Известно, что теория ^-строчных латинских прямоугольников даже без ограничений на позиции элементов ещё далека от своего завершения. По-видимому, вполне изученными (без ограничений на позиции) можно считать лишь случаи к= 2,3.

Случай 3-строчных редуцированных латинских прямоугольников соответствует парам перестановок, соответствующих их второй и третьей строкам. Автор решил изучить такие пары перестановок с произвольной системой ограничения на позиции и одновременно с произвольно заданной относительной цикловой структурой перестановок. С помощью циклового индикатора пар противоречивых перестановок получен чёткий не переборный алгоритм перечисления пар перестановок с указанными ограничениями и классов их эквивалентности.

В теории перманентов неотрицательных матриц важнейшую роль играют верхняя оценка - неравенство Минка-Брэгмана и нижняя оценка -неравенство Ван дер Вардена-Егорычева-Фаликмана. Доказательство этих оценок, высказанных первоначально Минком и Ван дер Варденом в форме гипотез, стимулировали развитие перманентов в последние десятилетия. B.C. Шевелевым в форме гипотез высказаны обобщения этих оценок для введенных им естественных обобщений перманента и названных ^-хроматическим перманентом и ^-перманентом. Суть обобщения состоит в суммировании вместо диагональных произведений, средних геометрических таких произведений для каждой выборки к непересекающихся диагоналей. Комбинаторный смысл таких обобщений состоит в том, что в случае (ОД)-матрицы обобщенные перманенты перечисляют либо ^-строчные латинские прямоугольники, либо (0,1)-матрицы, строчные и столбцовые суммы которых равны к, с заданной системой ограничений на позиции их элементов. Эти гипотетические неравенства типа Минка и Ван дер Вардена для обобщенных перманентов неотрицательных матриц являются естественным обобщением соответствующих оценок и переходят в них при к= 1. Также В.С.Шевелевым дано естественное обобщение класса бистохастических матриц, причем при к=\ неравенства гипотез совпадают с неравенством Ван дер Вардена - Егорычева - Фаликмана для перманентов бистохастических матриц. Автором был разработан и реализован на ЭВМ алгоритм вычисления ^-хроматического перманента, в случае Ь=3, позволивший экспериментально на некоторых (ОД)-матрицах подтвердить эти обобщенные гипотезы Шевелева.

Структура диссертации такова.

В главе I в §1-3 рассмотрены постановка классической задачи о назначении, постановка обобщенной задачи о назначении и ее решение с помощью алгоритмов классической задачи о назначении. В §4 дан алгоритм вычисления блокового индикатора, позволяющий найти число решений обобщенной задачи о назначении. В §5 дан алгоритм вычисления циклового индикатора для перестановок, являющихся полными циклами,, позволяющий, кроме числа решений обобщенной задачи о назначении, находить и сами решения. В §6 приведены модели оптимизационных задач, к которым применима обобщенная задача о назначениях.

В главе II рассмотрены цикловые индикаторы перестановок с ограниченными позициями. В этой главе используется одномерный метод коэффициентов B.C. Шевелева, примененный в [2,5] для вычисления циклических многочленов (цикломентов) теплицевых матриц и циркулянтов, к вычислению цикловых индикаторов этих матриц. В §1 дается определение обобщенного циклового индикатора квадратной матрицы над полем комплексных чисел. В §2 вычисляется цикловой индикатор оболочки единичной и подстановочной матрицы. В §3 показано построение циклового индикатора теплицевой матрицы и дается в теореме 1 его интегральное представление, позволяющее в ряде случаев получить рекуррентные формулы для цикловых индикаторов теплицевых матриц. В §4 обобщена формула для цикломентов 5-диагональных циркулянтов, имеющаяся в [6]. Вид формулы описывается в теореме 2. В §5 рассмотрены некоторые частные случаи представления циклового индикатора 5-диагональных циркулянтов.

В §6 дан рекурсивный алгоритм вычисления циклового индикатора произвольной (ОД)-матрицы максимального порядка п=12. Кроме того, приведены цикловые индикаторы задачи "Problem des ménages" и её обобщений и цикловые индикаторы некоторых циркулянтов, вычисленные по более простой программе, связанной с формулами (41)-(42) главы II §5. В §7 указан новый улучшенный рекурсивный алгоритм вычисления циклового индикатора перестановок с ограниченными позициями, основанный на совершенно другой идее. Приводимая в §8 реализация этого алгоритма на ЭВМ для матриц с целыми элементами максимального порядка п-12, показала, что скорость счёта по новому алгоритму существенно выше. Кроме того, приведены цикловые индикаторы для матриц А = J„ , J„-I ,J„-I-P, J„-I-P-P2, J„-I-P-P2-P3, где J„ - матрица nxn матрица, составленная из единиц , Р - (ОД)-матрица перестановки с единицами на местах (1,2),(2,3),.,(л-1,и),(и,1), I - единичная матрица.

В главе III рассмотрены важные цикловые характеристики классов пар перестановок с ограниченными позициями.

В §1 даны понятия диперманента и хроматического диперманента квадратной матрицы и рассмотрены связанные с ними классы матриц. В §2 определяется матричная функция - преддиперманент. В §3 рассмотрены способы перечисления Л^-матриц. В §4 даны алгоритмы вычисления диперманента и хроматического диперманента. В §5 дан рекурсивный алгоритм вычисления диперманента и хроматического диперманента матриц с целыми элементами максимального порядка п= 11. Кроме того, приведены значения диперманента и хроматического диперманента для матриц А = J„, J„-I, J„-I-P, J„-I-P-P2, J„-I-P-P2-P3. В §6 определяются цикловой индикатор пар противоречивых перестановок и цикловой индикатор Л^-матриц. В §7 рассматривается вычисление прединдикатора. В §8 дается общий алгоритм вычисления цикловых индикаторов пар противоречивых перестановок с ограничениями на их позиции. В §9 приведен рекурсивный алгоритм вычисления цикловых индикаторов С(2)( Ап ; tj,. ,t„ ) и Л(2)( А„ ; t2,. ,tn ) пар противоречивых перестановок на матрице с целыми элементами максимального порядка п-10. Также приведены цикловые индикаторы для матриц А = J„ , J-I, J„-I-P, 4-I-P-P2, J„-I-P-P2-P3.

В §10 указан алгоритм вычисления ^-хроматического перманента, введенного B.C. Шевелевым, в случае к=3. В §11 приведена программа вычисления 3-хроматического перманента и его значения для матриц А = J„, J„-I, J„-I-P, J„-I-P-P2,1+P+P2 .

Основные результаты диссертации докладывались на Всероссийской школе-коллоквиум по стохастическим методам геометрии и анализа (Абрау-Дюрсо, 1994), Третьей Всероссийской школе - коллоквиум по стохастическим методам (Туапсе, 1996), на внутривузовских научных конференциях Ростовского государственного строительного университета (1992-1999), на научном семинаре кафедры высшей математики Ростовского государственного строительного университета.

Заключение диссертации по теме «Теоретические основы информатики», Григорчук, Сергей Евгеньевич

Основные результаты, выносимые на защиту, состоят в следующем:

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

2. Для теплицевых матриц, имеющих широкое приложение в математической физике, получено интегральное представление их индикаторов.

3. На основе обобщенного аналога теоремы Лапласа разработан и реализован алгоритм вычисления обобщенного циклового индикатора для перестановок с ограниченными позициями.

4. Введены новые понятия циклового индикатора пар противоречивых перестановок и циклового индикатора Л2-матриц, приведен и общий алгоритм вычисления этих характеристик.

5. Получены новые, более эффективные, алгоритмы вычисления диперманента и хроматического диперманента, 3-хроматического перманента произвольной матрицы, являющегося обобщением перманента и диперманента.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Григорчук, Сергей Евгеньевич, 2000 год

1. Шевелев B.C. О циклических многочленах квадратных матриц // Докл. АН УССР.-1991.-№ З.-С. 27-31.

2. Шевелев B.C. Перечисление перестановок с ограниченными позициями и фиксированным числом циклов // Дискрет, мат.-1992.-Т.4, № 2.-С. 3-32.

3. Шевелев B.C. Перечисление перестановок с ограниченными позициями и произвольно фиксированной цикловой структурой /Деп. ВИНИТИ 21.10.92,№ 3062-В92.

4. Shevelyov V.S. Computing Cycloc Indicators of Permutations with Confined Displacements // Dokl. Akad. Nauk Ukrainy -1993.-№ 7.

5. Шевелев B.C. Метод коэффициентов вычисления перманента теплицевых матриц и циркулянтов /Деп. ВИНИТИ 24.02.87, № 1300-В87.

6. Шевелев B.C. Некоторые вопросы перечисления перестановок с ограниченными позициями // Итоги науки и техники .- Сер. Теория вероятн. Мат.статистика. Теор. кибернетика: 1992.-Т.30.-с. 113-177.

7. Шевелев B.C. Формула для per(J„-I-P г ) / Деп. ВИНИТИ 02.10.86, № 6974-В86.

8. Шевелев B.C. Интегральные представления, оценки и рекуррентные формулы для перманентов теплицевых матриц и циркулянтов / Деп. ВИНИТИ 09.07.87, № 4876-В87.

9. Metropolis N., Stein M.L., Stein P.R. Permanents of cyclic (0,l)-matrices // J. Combin. Theory -1969. -№ 4. C.291-321.

10. Ю.Шевелев B.C. Некоторые новые результаты, гипотезы и проблемы в теории перманентов / Деп. ВИНИТИ 14.11.89, № 6828-В89.

11. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. -384 с.

12. Шевелев B.C. Основная теорема о последовательностях перманентов циркулянтов, порождаемых к-мерными арифметическими векторами, и ее применения // Докл. АН. УССР.-1990.-№9,с.28-32.

13. Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ., 1963.-287с.

14. Курош А.Г. Курс высшей алгебры. М.: Физматгиз, 1963.-432с.

15. Тараканов В.Е. Комбинаторные задачи и (ОД)-матрицы. М.: Наука, 1985.-192 с.

16. Шевелев B.C. Об аналогах гипотезы Ван дер Вардена для диперманентов. / Деп. в ВИНИТИ 12.07.95, № 2133-В95

17. Райзер Г. Дж. Комбинаторная математика. М.: Мир, 1966.-154 с.

18. Тараканов В.Е. Комбинаторные задачи на бинарных матрицах // Комбинаторный анализ. М.: Изд-во МГУ, 1980. -Вып.5.- С.4-15.

19. Good I.J., Crook J.F. The enumeration of arrays and a generalization related to contingency tables. // Discrete Math.-1977-v.19, № 1.-P.23-45

20. Шевелев B.C. Вероятностное доказательство формулы Гуда и

21. Крука для числа (ОД)-матриц класса А2п . В кн. Всероссийская школа-коллоквиум по стохастическим методам геометрии и анализа

22. Абрау-Дюрсо, 25 сент.-2 окт. 1994): Тезисы докладов. М.: ТВП.-1994.-С.128-129.

23. Шевелев B.C. Редуцированные латинские прямоугольники и квадратные матрицы с одинаковыми суммами в строках и столбцах // Дискретная математика.-1992.-Т.4, вып.1.- С.91-110.

24. Григорчук С.Е., Шевелев B.C. Вычисление цикловых индикаторов теплицевых матриц и циркулянтов / Деп. ВИНИТИ 05.07.93, № 1849-В93.

25. Григорчук С.Е., Шевелев B.C. Ещё один алгоритм вычисления циклового индикатора перестановок с ограниченными позициями // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки. 1997 № 2, С. 11-13

26. Григорчук С.Е., Шевелев B.C. Общий алгоритм перечисления пар противоречивых перестановок с ограниченными позициями и классов их эквивалентности (алгоритм вычисления диперманентов) /Деп. ВИНИТИ 14.11.95, №3017-В95.

27. Григорчук С.Е., Шевелев B.C. Алгоритм вычисления циклового индикатора пар противоречивых перестановок с ограниченными позициями // Известия высших учебных заведений. СевероКавказский регион. Естественные науки. 1997 № 3, С.23 -35

28. Шевелев B.C. О числах ^-строчных латинских прямоугольников и Акп -матриц с ограничениями на позиции элементов и оценках типа Минка и Ван дер Вардена для них / Деп. ВИНИТИ 28.11.95, № 3146-В95

29. Липский В. Комбинаторика для программистов. М.: Мир, 1988.-с.24-33

30. Григорчук С.Е. Вычисление k-хроматического перманента Шевелева (случай к=3). В кн. Третья Всероссийская школа-126коллоквиум по стохастическим методам (Туапсе, 17сент.- 24сент. 1996): Тезисы докладов. М.: ТВП.-1996.-С.49-51

31. Григорчук С.Е., Шевелев B.C. О применении "блокового индикатора" к обобщенной задаче о назначении. // Известия Ростовского государственного строительного университета. Естественные науки. 1999 № 4, С. 167-172.

32. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.-479 с

33. Минк X. Перманенты. М.: Мир, 1982.-213 с.

34. Шевелев B.C. Развитие ладейной техники для вычисления цикловых индикаторов (ОД)-матриц // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки.- 1996. -№ 4.-С.21-28.