Содержание к диссертации
ВВЕДЕШ® 4
Глава I. ЦИКЛИЧЕСКИЕ ШОІІІЕСТВА И ЩЖЛЫ ПРОИЗВОЛЬНОЙ МАТРИЦЫ 13
§ І.І. Основные определения 13
§ 1.2. Симметрическая разность циклов 16
§ 1.3. Циклы, порожденные произвольным множеством элементов матрицы 23
§ 1.4. Циклы, порожденные множеством всех элементов матрицы Q- fcd-) n 28
§ 1.5. Циклы, порожденные опорным планом невырожденной транспортной задачи 30
Глава 2. ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ ЦИКЛОВ МАТРИЦЫ. УСЛОВИЯ ОПТИМАЛЬНОСТИ ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ 44
§ 2.1. ft -характеристика и ,5 -характеристика циклов, порожденных множеством всех элементов матрицы.
Использование этих характеристик при исследовании транспортных задач 44
§ 2.2. ft -характеристики циклов, порожденных произвольным множеством элементов матрицы. Условие оптимальности произвольного допустимого плана транс
портной задачи .53
§ 2.3. ft -характеристика циклов, порожденных опорным не распадающимся планом. Условие оптимальности опорного не распадающегося плана. Связь с методом потенциалов 58
Глава 3. СПЕЦИАЛЬНЫЕ • КЛАССЫ ТРАНСПОРТНЫХ ЗАДАЧ, ЭФФЕКТИВНО РАЗРЕШИМЫЕ АЛГОРИТМАМИ, ОСНОВАННЫМИ НА ПОНЯТИИ ЦИКЛА МАТРИЦЫ
§ З.І. Транспортные задачи со специальным видом матрицы стоимости перевозок 70
§ 3.2. Транспортные задачи со специальным видом векторов производства и потребления 73
ЛИТЕРАТУРА
Введение к работе
Как известно, транспортные задачи линейного программирования представляют собой математические модели важных практических задач, распространенных в различных сферах человеческой деятельности. Кроме задач о перевозках продуктов, к ним сводится много других ( см., например, [9] , [ю] , f29j , [32] ). Формулировка транспортной задачи и необходимые определения приведены в § I.I данной работы.
В настоящее время для решения транспортных задач разработано довольно много алгоритмов и, тем не менее, публикации по этой теме регулярно появляются в нашей стране и за рубежом. Объясняется это большим прикладным значением таких задач, а также тем, что их специфика открывает новые возможности алгоритмической реализации различных вычислительных методов. Основные методы решения этих задач систематически излагаются, например, в книгах [l] , /9 J , 28] , [29J и в ряде других работ.
Предельная простота условий транспортной задачи позволяет на основе любого общего метода линейного программирования получить менее трудоеїлкий специальный алгоритм для решения этой задачи. Эффективность полученного алгоритма зависит, в основном, от того, насколько полно учтена специфика задачи.
Существующие конечные алгоритмы решения транспортной задачи в матричной постановке можно разделить на две основные группы. Первая группа алгоритмов основана на наиболее популярном методе линейного программирования - методе последовательного улучшения плана. Вторая группа алгоритмов базируется на идеях последовательного сокращения невязок.
Типичными представителями первой группы алгоритмов являются метод потенциалов, который был предложен в работе Л.В.Канторовича и М.К.Гавурина [I9J и несколько позже Дж. Данцигом [ 37] , и метод Глейзала [ 7] .
К алгоритмам второй группы относится венгерский метод [21 , [24J , [30J .К этой же группе относится и метод вычеркивающей нумерации Брудно [ 4 J .
Многочисленные исследования последних лет, касающиеся транспортных задач, были связаны с изучением транспортных многогранников. Современное состояние этих исследований и библиографию по этому вопросу можно найти в монографии [I5j . Центральными результатами этих исследований являются результаты, связанные с оценкой диаметра и числа вершин транспортного многогранника.
Под диаметром многогранника понимается наименьшее целое К такое, что между любой парой его вершин существует цепь, состоящая из вершин и ребер многогранника, которая содержит не более К ребер. Относительно диаметра транспортного многогранника порядка ГП П доказано [и] , что он не превосходит числа fUt-. С точки зрения симплексного алгоритма, диаметр есть максимальное число итераций " наилучшего " алгоритма при " наихудшем " выборе начального плана.
Наиболее точно характеризует эффективность симплексного алгоритма так называемая высота транспортного многогранника. Под высотой многогранника понимается число ребер самой длинной цепи многогранника, вдоль которой некоторая линейная функция строго монотонна. С точки зрения симплексного алгоритма высота многогранника есть число итераций " наихудшего " алгоритма при неудачном выборе начального плана.
Найденная верхняя оценка диаметра транспортного многогранника говорит о том, что число итераций наилучшего симплексного алгоритма должно быть небольшим. Однако вопрос о существовании такого алгоритма остается открытым.
Заметим, что разработанные симплексные алгоритмы от транспортного многогранника берут начальную вершину, а сама работа алгоритма определяется не столько этим многогранником, а в большей степени матрицей стоимости перевозок данной транспортной задачи. Это становится наглядным, если проанализировать конкретный симплексный алгоритм решения транспортной задачи, например, метод потенциалов.
Как самостоятельный объект циклические множества матрицы, важнейшим частным случаем которых являются циклы, впервые исследо-валисн С.М.Швартиным в работе [ 34] . Основное внимание в этой работе уделено изучению мощностных характеристик множества циклов матрицы. В качестве приложения понятия цикла к исследованию транспортных задач доказан, в несколько другой формулировке, следующий критерий оптимальности плана транспортной задачи.
Полученные результаты в различных областях исследований транспортных задач говорят о перспективности и актуальности исследования циклической структуры матриц.
В данной работе рассматриваются три множества циклов матрицы, имеющих существенное значение в исследовании транспортных задач.
1. Множество 2_ (С) всех Циклов матрицы С, .
2. Множество 2л М) циклов матрицы С, , порожденных произвольным множеством I ч элементов этой матрицы.
3. Множество /__ ( Сх) Циклов матрицы С, порожденных множеством dy всех _д -существенных элементов матрицы Q , где _д есть некоторый опорный план невырожденной транспортной задачи, для которой d есть матрица стоимости перевозок.
Целью исследования является:
1. Построение для каждого из указанных множеств базисного множества циклов такого, чтобы любой цикл из рассматриваемого множества был представим в виде симметрической разности базисных циклов и вычисление К -характеристики этого цикла сводилось бы к вычислению Js -характеристик базисных циклов.
2. Нахождение на основе полученных представлений is. -характеристик специальных условий оптимальности плана транспортной задачи.
3. Построение эффективных алгоритмов нахождения оптимальных планов для специальных классов транспортных задач.
В первой главе диссертации находятся необходимые и достаточные условия того, чтобы симметрическая разность двух циклов была
- II циклом. Для указанных выше множеств циклов матрицы строятся базисные множества циклов. Эти базисные множества для множеств строятся аналогично построению фундаментального множества циклов для циклов графа (см. [з] , [25] , [2б] ).
Во второй главе рассматриваются К. - и р -характеристики циклов. Доказывается, что К. -характеристика произвольного цикла из множества КС) представима в виде линейной комбинации j -характеристик некоторого числа базисных циклов, а для вычисления Р -характеристик циклов из множества LKС Этакого базиса не существует. Исходя из этого выводятся некоторые свойства оптимальных планов транспортной задачи.
Для множества Z(M) показывается, что /ч-характеристика произвольного цикла из этого множества представима в виде суммы характеристик некоторого числа базисных циклов. Из этого следует одно специальное достаточное условие оптимальности плана транспортной задачи.
Аналогично вычисляется JC -характеристика любого цикла из множества с ( L»X/ • Отсюда выводятся необходимые и достаточные условия оптимальности плана транспортной задачи и устанавливается связь полученных условий с условиями оптимальности плана в методе потенциалов.
В третьей главе рассматриваются три специальных класса транспортных задач.
Первый класс содержит транспортные задачи, матрицу стоимости перевозок которых с помощью перестановки строк и столбцов можно привести к такому виду, что для любого цикла, выполняется условие . Доказывается, что после соответствующей перенумерации пунктов производства и потребления план, построенный по методу " северо-западного угла , будет оптимальным планом задачи из рассматриваемого класса. В 12 , этот класс, в частности, входят задачи с матрицами, аналогичными матрицам, введенным для задач комбинаторной оптимизации Д.А. Супру-ненко [27J , а также В.Я.Бурдюком и В.Н.Трофимовым [5] .
