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

• Автор: Григорчук, Сергей Евгеньевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Ростов-на-Дону
• Количество страниц: 126 с.

СОДЕРЖАНИЕ
Введение.

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

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

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

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

классической задачи о назначении

4. Определение решений задачи о назначении

с помощью блокового индикатора

5. Определение решений задачи о назначении

с помощью циклового индикатора

6. Модели оптимицазионных задач, связанных с обобщенной задачей о назначении
Глава II. Алгоритмы вычисления цикловых индикаторов
матриц
1. Определение обобщенного циклового индикатора.
2. Цикловой индикатор оболочки единичной и подстановочной
матрицы.
3. Цикловые индикаторы теплицевых матриц
4. Вычисление циклового индикатора 5диагонального
циркулянта
5. Некоторые частные случаи.
6. Вычисление цикловых индикаторов 0,1матриц.
7. Улучшенный алгоритм вычисления циклового индикатора
перестановок с ограниченными позициями
8. Вычисление цикловых индикаторов матриц
с целыми элементами.
Глава III. Алгоритмы вычисления цикловых индикаторов пар перестановок с ограниченными позициями.
1. Основные понятия.
2. Вычисление преддиперманента
3. Об одном рекуррентном процессе перечисления Аматриц
4. Общий алгоритм вычисления диперманента и хроматического
диперманента
5. Вычисление диперманентов матриц с целыми элементами.
6. Понятие циклового индикатора пар противоречивых перестановок
с ограниченными позициями
7. Вычисление прединдикатора.6
8. Общий алгоритм
9. Вычисление цикловых индикаторов пар противоречивых
перестановок с ограниченными позициями.
. Алгоритм вычисления хроматического перманента
Шевелева случай к 3
. Вычисление 3хроматического перманента Шевелева
Заключение.
Литература


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