Минимакс в транспортных моделях тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Миронов, Анатолий Анатольевич

• Миронов, Анатолий Анатольевич
• доктор физико-математических наук
• 1998

Оглавление диссертации доктор физико-математических наук Миронов, Анатолий Анатольевич

ОГЛАВЛЕНИЕ

введение

глава 1. модели транспортного типа

с минимаксным критерием

§ 1. Транспортные модели

1.1. Равномерные матрицы и матричные множества

1.2. Примеры транспортных моделей с критериями

минимаксных типов

1.3. Усеченные транспортные многогранники

§ 2. Транспортные матрицы с ограничением для элементов

2.1. Разбиения пар векторов

2.2. Условия существования матриц с заданным ограничением

2.3. Критерий существования транспортной матрицы в форме несократимой системы неравенств

2.4. Алгоритмы построения транспортных матриц

§ 3. Характеристические уравнения для усеченных транспортных

многогранников

3.1. Общие свойства транспортных матриц

3.2. Примеры применений характеристических уравнений

глава 2. критерии минимаксного типа

§ 1. Условия единственности решения задачи минимизации

наибольшего элемента транспортной матрицы

1.1. Минимаксные значения и минимаксные матрицы

1.2. Условия единственности минимаксной матрицы

транспортного многогранника

1.3. Алгоритм вычисления минимаксного значения

§ 2. Наследственные свойства транспортных матриц

2.1. Наследственно минимаксные матрицы

2.2. Единственность наследственно минимаксной матрицы

транспортного многогранника

2.3. Минимизация равномерными минимаксными матрицами

2.4. Свойства равномерных матриц

2.5. Минимизация равномерными матрицами

§ 3. Наследственно минимаксные матрицы в транспортных задачах

с критериями минимаксных типов

3.1. Наибольшие элементы подматриц транспортной матрицы

и равномерность

3.2. Минимизация наследственно минимаксными матрицами

глава 3. целочисленные транспортные матрицы

§ 1. Целочисленные матрицы с общим ограничением

для элементов

1.1. Вспомогательные построения

1.2. Редукционный критерий существования транспортных матриц

1.3. Редукционные алгоритмы построения транспортных

матриц

§ 2. Матрицы, состоящие из нулей и единиц

2.1. Критерий существования и характеристические уравнения

2.2. Редукционные алгоритмы

Глава 4. экстремальные матрицы и фундаментальные

транспортные многогранники

§ 1. Экстремальные пары векторов и экстремальные матрицы

1.1. Экстремальные пары векторов

1.2. Экстремальные матрицы

1.3. Множества экстремальных матриц (и пар векторов)

одного порядка

1.4. Совершенные пары векторов и совершенные матрицы . 143 § 2. Алгебраические свойства экстремальных пар векторов

и экстремальных матриц

2.1. Операции над парами векторов и матрицами

2.2. Изоморфные дистрибутивные решетки фундаментальных систем пар векторов и матриц

§ 3. Метрические свойства экстремальных пар векторов

и экстремальных матриц

3.1. Метрики на множествах экстремальных пар векторов и

3.2. Изометрия фундаментальных систем пар векторов и

матриц

§ 4. Ядра и оболочки множеств транспортных матриц,

состоящих из нулей и единиц

4.1. Определения ядер и оболочек матричных множеств и критерий их нетривиальности

4.2. Взаимно дополнительные транспортные матрицы

4.3. Экстремальность ядер и оболочек матричных множеств

4.4. Алгоритмы построения ядер и оболочек

§ 5. Вероятностные свойства случайных транспортных матриц,

состоящих из нулей и единиц

5.1. Матрица вероятностей матричного множества

5.2. Матрица условных вероятностей матричного множества

5.3. Матрица математических ожиданий множества

целочисленных транспортных матриц

5.4. Экстремальные матрицы и матрицы вероятностей

6.1. Выпуклые оболочки фундаментальных систем

пар векторов и матриц

6.2. Фундаментальный транспортный многогранник

(пар векторов)

6.3. Фундаментальный транспортный многогранник

(равномерных матриц)

6.4. Произвольные равномерные транспортные матрицы

и фундаментальные транспортные многогранники

6.5. Минимаксные равномерные транспортные матрицы

и фундаментальные транспортные многогранники

6.6. Приложения фундаментальных транспортных

многогранников к классическим транспортным задачам

СПИСОК ЛИТЕРАТУРЫ

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

ВВЕДЕНИЕ

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

Настоящая диссертация посвящена моделям транспортного типа с минимаксным критерием. Несколько десятилетий назад была поставлена классическая (линейная) транспортная задача, в которой были заданы пункты производства продукта и пункты потребления этого продукта. Рассматривалась проблема перевозки продукта с минимальными затратами. Эта постановка повлекла за собой многочисленные распространения и обобщения.

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

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

В диссертации представлен ряд практических моделей транспортного типа с минимаксным критерием. Характеристическими уравнениями исследуются матрицы-планы (транспортные матрицы) произвольной транспортной задачи с ограничением сверху для элементов. Построен алгоритм вычисления элементов этих матриц, достоинством которого является то, что любая такая матрица может быть получена этим алгоритмом. Введено естественное понятие равномерности матрицы: матрица транспортного многогранника называется равномерной, если равным парам координат соответствуют равные элементы матрицы, а парам с неменьшими координатами соответствуют неменьшие значения элементов. Показано, что в некоторых из указанных моделях минимакс достигается на равномерных матрицах. Одним из основных результатов диссертации является следующий. Для произвольного транспортного многогранника приведен алгоритм построения минимаксной матрицы, называемой наследственно минимаксной, у которой любая подматрица является минимаксной матрицей своего транспортного многогранника. Указанная матрица обладает свойствами: она относится к классу равномерных, является един-

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

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

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

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

Глава 1 посвящена моделям транспортного типа с минимаксным критерием, построению транспортных матриц с заданными условиями и методам исследований этих матриц. Здесь приведены конкретные модели и построены целевые функции, минимизируемые во второй главе.

Основоположником теории транспортных проблем является Ф. Хичкок [86]. Хотя и до него некоторые частные постановки исследовались

специалистами по транспорту [80]. Сфера применения транспортных моделей обширна. Сюда можно отнести проблемы, например, связанные с планированием производства и перевозок, с созданием вычислительных и информационных систем, с распределением ресурсов и запасов и т.д. [22, 60, 61, 85].

Классические транспортные задачи в большей степени относятся к области линейного программирования и математический аппарат решения этих задач хорошо отработан и известен [14, 60, 81, 89]. В настоящее время для решения практических задач приходится часто привлекать нелинейные модели транспортного типа [22, 36, 85], причем, и здесь иногда применяется линейный аппарат при линейной аппроксимации функционалов [3, 60]. В общем случае на множестве матриц транспортного многогранника задана произвольная целевая функция. Поэтому к задачам транспортного типа возможно применение аппарата математического программирования в полном объеме [2, 25, 27, 35, 62, 79]. И в зависимости от целевой функции экстремальные транспортные задачи можно отнести, например, к выпуклому [68, 74], динамическому [5, 30, 89—92], дискретному [33, 76, 88] программированиям.

В данной главе вводятся транспортные модели с критериями минимаксного типа [49, 53—55, 57]. Смешанный критерий-минимакс имеет широкое применение в теории исследования операций [18, 58, 66]. Этот критерий используется, например, в следующих областях: теория принятия решений, теория активных и иерархических систем, матричные игры [7—9, 63, 65].

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

Глава 1 состоит из трех параграфов. В § 1 рассмотрен ряд моделей транспортного типа и построены целевые функции, минимизируемые во

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

В параграфе для транспортных матриц введено естественное понятие равномерности, важность которого можно объяснить следующими обстоятельствами [53—55, 57]:

а) наследственно минимаксная матрица, отмеченная выше и построенная во второй главе, является равномерной;

б) экстремальные матрицы, определяющие в четвертой главе методы исследований транспортных многогранников и их матриц, — также равномерны;

в) ряд моделей транспортного типа с минимаксным критерием имеет своими решениями равномерные матрицы.

Построена функция, зависящая от координат пары неотрицательных векторов и от неотрицательной константы, применяемая во многих исследованиях диссертации. В частности, для транспортного многогранника, неотрицательность этой функции (при упорядоченности координат первого вектора по невозрастанию) гарантирует непустое множество матриц этого многогранника с заданным ограничением сверху для всех элементов. Указанную функцию можно получить, опираясь на теорему Гейла [11], которая применяется в потоковых задачах на сетях [83] и при исследованиях усеченных транспортных многогранников [19].

В § 2 получены необходимые и достаточные условия в форме несократимой системы неравенств [93], определяющие матрицы-планы транспортных задач с ограничением сверху для элементов. Множество таких матриц является частным случаем усеченных транспортных многогранников [19].

В параграфе приведены два алгоритма построения транспортных матриц с общим ограничением сверху для всех элементов [57]. Первый из них вычисляет вполне определенную матрицу (если заданный усеченный транспортный многогранник не является пустым). Применяя второй алгоритм, в зависимости от решения некоторых систем линейных неравенств, можно построить любую матрицу из указанных.

Для произвольной пары векторов, определяющей непустой транспортный многогранник, и любого положительного ограничения построена система неравенств [57]. Эта система не содержит избыточных неравенств и является критерием существования транспортной матрицы с заданным ограничением сверху для элементов. Сформулированные результаты распространены на случай целочисленных транспортных матриц.

В § 3 построены характеристические уравнения [53—55, 57], определяющие общие свойства всех матриц с ограничением для элементов.

Рассматриваются произвольные пары векторов, определяющие непустые транспортные многогранники. Для множества транспортных матриц, элементы которых имеют ограничение сверху, и соответствующей ему пары векторов, построены тождества [53—55, 57]. Эти тождества связывают элементы матриц с координатами векторов и задают общие свойства всех матриц этого множества. Рассмотрение этих соотношений, как характеристических уравнений от неизвестных элементов матриц, позволяет в одних случаях строить матрицы с заданными свойствами, а в других — запретить существование матриц с некоторыми условиями. В частности, эти уравнения в случае целочисленности матриц дают возможность (в сочетании с комбинаторными методами [72, 75, 77, 87]) оценить количество таких матриц.

Результаты этого параграфа применяются в построениях минимаксных, наследственно минимаксных и экстремальных матриц.

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

Моделям транспортного типа посвящена обширная литература [14, 27, 35, 62, 81]. Но, если в линейном случае разработаны эффективные точные методы решения транспортных задач, то в нелинейном, к настоящему времени, нет общих точных методов оптимизации. Наиболее изученной здесь является оптимизация целевых функций, являющихся выпуклыми или вогнутыми, что относится к области выпуклого программирования [2, 68, 74, 79]. При некоторых условиях возможно также применение методов динамического программирования [5, 30, 90]. Иногда хороший результат в оптимизации достигается аппроксимацией функционалов кусочно-линейными функциями [2, 60].

Минимаксные задачи имеют большое распространение в теории исследования операций [18, 58, 66]. Например, в [47, 48, 50, 51] минимаксный критерий применен к задачам в сетевой постановке. Во второй главе диссертаци минимаксные критерии исследуются в задачах транспортного типа [49, 53—55]. Здесь минимизируются все функционалы, заданные на матрицах транспортных многогранников [19—21, 32], построенные в первой главе. Отметим, что указанные функционалы являются выпуклыми функциями и, следовательно, эти задачи можно отнести к задачам выпуклой оптимизации.

Глава 2 содержит три параграфа. В § 1 построены (в форме системы линейных ограничений) необходимые и достаточные условия единственности минимаксной матрицы транспортного многогранника [57]. Приведены формулы вычисления элементов минимаксной матрицы в случае ее единственности. Очевидно, что тогда эта матрица — наследственно минимаксна.

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

В § 2 рассматриваются минимаксные матрицы, для которых минимаксность — наследственное свойство [57].

Каждая подматрица транспортной матрицы (т.е. матрицы с неотрицательными элементами) является транспортной матрицей. Поэтому свойст-

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

В параграфе для произвольного транспортного многогранника построена минимаксная матрица [54, 55, 57], у которой минимаксность — наследственное свойство. Поэтому указанная матрица называется наследственно минимаксной. Показано, что каждая наследственно минимаксная матрица — равномерна и единственна в своем транспортном многограннике. Здесь же выделен ряд функционалов, из построенных в первой главе, минимизируемых равномерными матрицами. Причем в каждом случае найдено численное значение минимума. В частности, для равномерной матрицы определена сумма наибольших элементов всех ее подматриц.

В § 3 показано, что все функционалы, рассматриваемые в диссертации, достигают минимума на наследственно минимаксной матрице [57]. Причем, эта матрица — единственное общее решение всех рассматриваемых задач минимизации.

Основным результатом параграфа является то, что для произвольного транспортного многогранника наследственно минимаксная матрица определяет единственное решение задачи минимизации суммы наибольших элементов всех подматриц транспортной матрицы. Так как наследственно минимаксная матрица — равномерна (второй параграф), то тем самым вычислен минимум суммы наибольших элементов всех подматриц матриц транспортного многогранника.

Основным понятием четвертой главы является экстремальная матрица. Там же показано, что любая экстремальная матрица — наследственно минимаксна.

В главе 3 рассматриваются целочисленные матрицы и алгоритмы их построения [49, 57].

Требование дискретности переменных присуще многим важным классам задач [34, 94, 95], что обеспечивает широкую область применения методов целочисленной оптимизации [24, 33, 67, 76, 88]. В качестве примеров отметим здесь известные задачу о ранце и задачу коммивояжера [34, 35, 60, 76]. Большинство методов решения задач целочисленного программирования основаны на сокращении перебора допустимых вариантов. Из них наиболее известными являются метод отсечений (алгоритм Гомори) и метод ветвей и границ [15, 17, 60, 88]. Указанные методы целочисленной оптимизации применяются и в транспортных задачах. Примерами транспортных моделей с ограничением на целочисленность переменных могут служить, например, задача назначения, задача целерас-пределения, а также общая задача, в которой переменные являются неделимыми средствами [14, 35, 37, 60, 81].

В этой главе все внимание уделяется построениям целочисленных транспортных матриц. Приведенные здесь методы можно применить в построениях матриц-планов (допустимых решений) в целочисленных моделях транспортного типа.

В § 1 приведен общий случай построения целочисленных матриц.

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

Условие целочисленности позволяет привести более наглядный и простой способ построения матриц с общим ограничением сверху. В параграфе содержится конструктивный критерий существования указанных матриц, заключающийся в последовательном вычислении элементов строк [49, 53—55, 57].

Отметим, что каждую целочисленную транспортную матрицу можно рассматривать, как матрицу смежностей двудольного мультиграфа, для которого координаты векторов, определяющие эту матрицу, являются степенями вершин [23, 49, 53, 57, 64]. Поэтому результаты параграфа

применимы и в построениях двудольных мультиграфов с заданным

ограничением на кратность ребер.

В § 2 рассматриваются матрицы, состоящие из нулевых и единичных

элементов.

Этот параграф можно рассматривать в качестве введения для четвертой главы. Здесь приведены следствия общих построений, относящиеся к матрицам, каждый элемент которых равен нулю или единице. Необходимые и достаточные условия для двух целочисленных векторов, при которых эти векторы определяют транспортную матрицу, состоящую из нулей и единиц, получены Гейлом [11, 19] и Райзером [69]. Эти условия эквивалентны условиям леммы 2.5 гл. 1 при целочисленности векторов и ограничении, равном единице. Отметим, что указанный результат получен в [83] применением задачи о допустимости потоков. Там же, представленный ниже, редукционный алгоритм построения рассматриваемых транспортных матриц определяется как правило (О, 1)-матрицы.

Матрицы, состоящие из нулей и единиц, составляют особый класс матриц. Ряд комбинаторных свойсв указанных транспортных матриц получен Райзером [70, 71]. Каждую такую матрицу можно также рассматривать как матрицу смежностей двудольного графа [4, 23, 57, 64]. Поэтому построения этого параграфа применимы в теории графов. Заметим также, что приведенные здесь утверждения являются следствиями результатов, касающихся построений симметричных (квадратных) матриц, состоящих из нулевых и единичных элементов [41—48, 50—53].

Глава 4 посвящена экстремальным матрицам, парам векторов, определяющих их, которые также называются экстремальными, и выпуклым оболочкам множеств из указанных объектов [57]. Приведены алгебраические и метрические свойства множеств экстремальных матриц и пар векторов (одного порядка). Построены методы исследований (один из которых — вероятностный) матриц, состоящих из нулевых и единичных элементов, экстремальными.

Модели транспортного типа, рассматриваемые в диссертации, являются замкнутыми [14, 67, 81]. Все такие задачи определены на множестве

неотрицательных матриц с фиксированными суммами элементов строк и столбцов. Множество таких матриц, называемое транспортным многогранником [19], задается парой неотрицательных векторов с равными суммами координат. Следовательно, построить замкнутую транспортную модель — это значит определить пару векторов, с указанными свойствами, и оптимизируемую целевую функцию. Отметим, что перестановкой строк и столбцов у всех матриц транспортного многогранника, можно упорядочить координаты определяющих их векторов по невозрастанию. Поэтому в четвертой главе рассматриваются, в основном, векторы с указанным порядком для координат (что не является ограничением общности).

Основным результатом для пар векторов, задающих области определения замкнутых транспортных задач, является следующий, основанный на теореме Крейна—Мильмана о крайних точках [12, 16]. Выделена система, называемая фундаментальной, из Спп+т пар целочисленных п и

т-координатных векторов, обладающая следующими свойствами [57]:

она содержит все те и только те пары из я и т-координатных векторов, каждая из которых определяет единственную транспортную матрицу, состоящую из нулей и единиц;

ее выпуклая оболочка содержит все пары векторов, определяющие транспортные матрицы с непревышающими единицы элементами;

все, принадлежащие ей, пары векторов являются (крайними) экстремальными [12, 16] для указанной выпуклой оболочки, называемой фундаментальным транспортным многогранником (пар векторов).

Из второго свойства следует, что любая пара векторов, задающая область определения произвольной замкнутой транспортной задачи, может рассматриваться, как принадлежащая фундаментальному транспортному многограннику возможно, с точностью до некоторого коэффициента с, О < с < 1. Третье свойство объясняет понятие экстремальности для пар векторов.

Любая экстремальная пара векторов определяет (единственную) экстремальную матрицу, состоящую из нулей и единиц. Основное внимание

в этой главе уделяется экстремальным матрицам и методам исследования этими матрицами произвольных, каждый элемент которых равен нулю или единице. Еще раз отметим важность класса матриц, состоящих из нулей и единиц. Матрицы этого класса находят применение в теории целочисленного программирования [33, 60, 67, 76, 88], в транспортных задачах [14, 24, 81], в коммуникационных сетях и в теории сетей связи [29, 40, 73], в теории автоматов [39, 59]. Например, в теории графов такая матрица может являтся матрицей инциденций, смежностей, циклов и разрезов [4, 6, 23, 64, 84].

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

Фундаментальной системе экстремальных пар из п и т-координатных векторов соответствует фундаментальная система экстремальных матриц порядка яхт, обладающая следующими свойствами [57]:

ее выпуклая оболочка содержит все равномерные транспортные матрицы порядка яхт, элементы которых не превосходят единицы;

все Спп+т ее матриц являются вершинами указанной выпуклой

оболочки, называемой фундаментальным транспортным многогранником (равномерных матриц).

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

Глава 4 состоит из шести параграфов. В § 1 приведены различные конструкции и условия, определяющие понятие экстремальности для пар векторов и матриц.

Любую матрицу порядка пХт, каждый элемент которой равен нулю или единице, можно рассматривать как распределение п элементов по т множествам. Поэтому такие матрицы играют большую роль в комбинаторике [77, 87]. Отметим здесь публикации [11, 69—71, 83], в которых достаточно полно изложена теория матриц, состоящих из нулей и единиц, с заданными суммами элементов строк и столбцов.

В параграфе выделен класс пар векторов, каждая из которых определяет единственную транспортную матрицу, состоящую из нулей и единиц. Указанные пары векторов и матрицы называются экстремальными. Показано, что матричные понятия экстремальность, равномерность и наследственная минимаксность эквивалентны в классе матриц, каждый элемент которых равен нулю или единице. Приведены и другие критерии экстремальности и вычислено количество экстремальных матриц (экстремальных пар векторов), имеющих общий порядок. Заметим, что аналогичные результаты для квадратных симметричных матриц, состоящих из нулей и единиц (матриц смежностей графа), получены в [42, 44—46, 52, 56].

В § 2 используется алгебраическое понятие дистрибутивной решетки [26, 31, 57, 78]. Рассматриваются экстремальные пары векторов и экстремальные матрицы одного порядка. Для элементов указанных множеств введены отношения порядка и по две бинарные операции. Показано, что тогда фундаментальные системы пар векторов и матриц образуют изоморфные дистрибутивные решетки. Отметим, что в [42, 44, 52, 56] аналогичный результат получен для специального класса квадратных симметричных матриц, состоящих из нулей и единиц, и определяющих их векторов.

Отношение порядка и две бинарные операции для матриц, построенные здесь, применяются в четвертом параграфе.

В § 3 на множествах экстремальных пар векторов и экстремальных матриц одного порядка построены метрические функции [1, 28]. Относительно этих метрик между фундаментальными системами пар векторов и матриц существует естественная изометрия. Показано, что метрики

согласованы с частичными порядками для элементов фундаментальных систем экстремальными матрицами или парами векторов.

В § 4 представлен метод (ядер и оболочек) исследования множеств транспортных матриц, состоящих из нулей и единиц, экстремальными матрицами. Для множества указанных матриц из одного транспортного многогранника определены и построены две матрицы, называемые ядром и оболочкой, удовлетворяющие условиям [57]:

а) ядро и оболочка—экстремальные матрицы (связанные отношением порядка);

б) ядро и оболочка «заключают» между собой любую рассматриваемую матрицу транспортного многогранника;

в) функция метрики от матриц — ядро и оболочка принимает наименьшее значение среди всех пар экстремальных матриц, для которых справедливо второе условие;

г) относительно отношения порядка для матриц, ядро является «наибольшей» экстремальной матрицей, содержащейся в каждой рассматриваемой, а оболочка — «наименьшей» экстремальной матрицей, содержащей любую рассматриваемую.

Эти построения можно применить и для исследований множеств транспортных матриц, с непревышающими единицы элементами. Отметим, что в [42, 44, 52, 56] аналогичные конструкции получены для множеств квадратных симметричных матриц, каждый элемент которых равен нулю или единице.

В § 5 построены вероятностные методы исследования множеств транспортных матриц, состоящих из нулей и единиц [57]. Результаты этого параграфа можно рассматривать, в частности, как относящиеся к методам исследования матричных множеств экстремальными матрицами. Объектом исследования являются множества транспортных матриц, состоящих из нулей и единиц, определяемых заданными парами векторов. Любая матрица указанного множества (которое, как очевидно, конечно) полагается случайной и равновероятной [13, 82]. Исходя из равномерного распределения, для произвольной допустимой пары индексов определяется (классическим образом) вероятность того, что соответствующий элемент

случайной матрицы равен единице. Тем самым определяется матрица вероятностей матричного множества. Показано, что матрица вероятностей принадлежит тому же транспортному многограннику, что и рассматриваемые матрицы [57].

Все единичные и все положительные элементы матрицы вероятностей определяют, соответственно, ядро и оболочку заданного матричного множества. Вероятностные методы позволяют строить специальные экстремальные матрицы (обобщающие ядро и оболочку), что дает возможность более детального исследования матричных множеств. Также показана возможность применения вероятностных методов в исследовании множеств целочисленных транспортных матриц. Отметим, что в [45] получены аналогичные результаты для классов графов с заданными наборами степеней вершин, т.е. для классов квадратных симметричных матриц, состоящих из нулей и единиц.

§ 6 посвящен выпуклым оболочкам всех экстремальных пар векторов и матриц с общим порядком [57]. Основные результаты параграфа изложены выше.

Предложенные конструкции определяют методы исследований пар векторов (задающих области определения транспортных задач) и равномерных матриц экстремальными: любые равномерные матрицы, с непревышающими единицы элементами, и соответствующие им пары векторов можно представить в виде линейных комбинаций из экстремальных с неотрицательными коэффициентами, сумма которых равна единице. Отметим, что в [42, 56] применением теоремы Крейна—Мильмана о крайних точках, получены аналогичные результаты для взвешенных графов и векторов, определяющих степени вершин этих графов.

Показаны возможные применения фундаментальных транспортных многогранников в задачах оптимизации.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Для матриц произвольного транспортного многогранника с общим ограничением элементов сверху

а) построен критерий существования в форме несократимой системы линейных неравенств;

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

в) представлен метод исследования множеств таких матриц характеристическими уравнениями.

2. Построены (в форме линейных ограничений) необходимые и достаточные условия единственности минимаксной матрицы транспортного многогранника.

3. Приведен алгоритм вычисления наследственно минимаксной матрицы (любая ее подматрица — минимаксна в соответствующем транспортном многограннике), некоторыми из свойств которой являются следующие:

а) любой транспортный многогранник содержит одну и только одну такую матрицу;

б) эта матрица является равномерной (т.е. равным парам координат соответствуют равные элементы, а парам с неменьшими координатами соответствуют элементы с неменьшими значениями);

в) эта матрица определяет единственное решение в задаче минимизации суммы наибольших элементов всех подматриц транспортной матрицы;

г) указанная в п. в) сумма вычислена для произвольной наследственно минимаксной матрицы.

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

5. а) Приведены необходимые и достаточные условия, при которых для пары векторов существует единственная транспортная матрица,

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

б) Если координаты векторов упорядочены по невозрастанию, то в классе матриц, состоящих из нулевых и единичных элементов, понятия «экстремальность», «наследственная минимаксность» и «равномерность» — эквивалентны.

в) Подсчитано, что количество экстремальных матриц (пар векторов) порядка пХт равно Спп .

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

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

6. Построен вероятностный метод исследования множеств матриц из п. 5г. Показано, что этот метод обобщает метод ядер и оболочек.

7. Выпуклые оболочки Ь(п, т) и М(п, т) множеств экстремальных пар векторов и экстремальных матриц, имеющих порядок пХга, называются фундаментальными транспортными многогранниками (пар векторов и равномерных матриц). Смысл, вкладываемый в понятия экстремальность и фундаментальность, содержится в следующих утверждениях (координаты векторов, имеющих размерности п и т., упорядочены по невозрастанию):

а) каждые экстремальные пары векторов и матрица являются вершинами своих фундаментальных транспортных многогранников;

б) пара векторов принадлежит Ь(п га) тогда и только тогда, когда для нее существует транспортная матрица, элементы которой не превосходят единицы; матрица принадлежит М(п т) тогда и только тогда, когда она является равномерной и ее элементы не превосходят единицы;

в) каждая пара векторов, для которой существует транспортная матрица, и каждая равномерная матрица с точностью до некоторого коэффициента принадлежат Ь(п, т) и М(п, т)\

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

По теме диссертации опубликованы научные статьи [41—56] и монография [57] (в соавторстве). Результаты докладывались и обсуждались

на семинаре кафедры «Прикладная математика» МГАТУ им. К.Э.Циолковского (руководители — проф. В.А.Кондратьев, проф. Л.А.Муравей) — ноябрь 1995 г., март 1997 г.;

на научно-исследовательском семинаре каф. «Общая топология и геометрия» МГУ им. М.В.Ломоносова (руководитель — В.В.Федорчук) — ноябрь 1996 г.

Список литературы диссертационного исследования доктор физико-математических наук Миронов, Анатолий Анатольевич, 1998 год

СПИСОК ЛИТЕРАТУРЫ

1. Александров П.С. Введение в общую теорию множеств и функций.— М.: Гос. изд-во технико-теоретической литературы, 1948.—411 с.

2. Алексеев В.М., Тихомиров В.М., Фомин C.B. Оптимальное управление.—М.: Наука, 1979.—430.

3. Астахов Н.Д., Федосеев A.B., Чан Ван Хунг. О применениии ускоренных алгоритмов решения задач транспортного типа.—М.: ВЦ РАН, 1994.—50 с.

4. Басаккер Р., Саати Т. Конечные графы и сети.—М.: Наука, 1974,—366 с.

5. Веллман Р. Динамическое программирование.—М.: ИЛ, 1960.—400 с.

6. Берж К. Теория графов и ее применения.—М.: ИЛ, 1962.—319 с.

7. Бурков В.Н. Математические основы теории активных систем.—М.: Наук, 1977.—255 с.

8. Бурков В.Н., Опойцев В.Н. Метаигровой подход к управлению иерархическими системами //Автоматика и Телемех.—1974.—№1.— С. 103—114.

9. Теоретико-игровые вопросы принятия решений /Под ред. H.H. Воробьева.—Ленинград: Наука, 1978.—128 с.

10. Гаврилов Г.П., Сапоженко A.A. Задачи и упражнения по курсу дискретной математики.—М.: Наука, 1992.—406 с.

11. Гейл (Gale D.) A theorem on flow in networks //Pacific J. Math.—1957.—V. 7.—P. 1073-1082.

12. Глазман И.М., Любич Ю.И. Конечномерный линейный анализ.—М.: Наука, 1969.—476 с.

13. Гнеденко Б.В. Курс теории вероятностей.—М.: Физматгиз, 1961.—406 с.

14. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа.—М.: Наука, 1969.—382 с.

15. Гомори (Gomory R.E.). An Algorithm for integer solutions for linear programs, in recent advaces in mathematical programming //Mc Graw— Hill.—1963.—P. 269—302.

16. Данфорд H., Шварц Дж. Т. Линейные операторы (общая теория).— М.: «Мир», 1962,—895 с.

17. Дейкин (Dakin R.J.). A tree search algorithm for mixed integer programming problems //Compuer J.—1965.—Y. 8.—P. 250—255.

18. Демьянинов В.Ф. Малоземов B.H. Введение в минимакс.—М.: Наука, 1972.—368 с.

19. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация.—М.: Наука, 1981.—342 с.

20. Емеличев В.А., Кононенко А.М. Об одном классе транспортных многогранников //Изв. АН БССР сер. физ.-матем. наук.—1971.— № 3.—С.21—23.

21. Емеличев В.А., Кравцов М.К, Крачковский А.П. О некоторых классах транспортных многогранников //ДАН СССР.—1978,—Т. 241, № 3.— С. 34—37.

22. Злотов А.В., Ким КВ., Мгерян Г.М., Хачатуров В.Р. Алгоритмическое и программное обеспечение решения задач оперативного планирования транспортных перевозок.—М.: ВЦ АН СССР, 1989.—30 с.

23. Зыков A.A. Теория конечных графов.—Новосибирск: Наука, 1969.— 544 с.

24. Журавлев Ю.И. Об одном классе алгоритмов над конечными множествами //ДАН СССР.—1963. Т. 151, № 5. С. 1025—1028.

25. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач.—М.: Наука, 1974.—479 с.

26. Калужнин Л.А. Введение в общую алгебру.—М.: Наука, 1973.—384 с.

27. Карманов В.Г. Математическое программирование. — М.: Наука, 1986,—288 с.

28. Келли Дж. Л. Общая топология.—М.: Наука, 1968.—384 с.

29. Клейнрок Л. Коммуникационные сети.—М.: Наука, 1970.—256 с.

30. Краснощекое П.С., Петров A.A. Принципы построения моделей.—М.: Изд-во МГУ, 1983,—264 с.

31. Кон П. Свободные кольца и их связи.—М.: «Мир», 1975.—422 с.

32. Кононенко А.М., Трухановский H.H. О транспортных многогранниках с максимальным числом вершин //Изв. АН БССР, сер. физ.-матем. наук,—1978.—№ 5.—С. 23—25.

33. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование.— М.: Наука, 1969.—368 с.

34. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров.—М.: «Энергия», 1980.—342 с.

35. Кузнецов A.B., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование.—Минск: «Высшая школа», 1994.— 288 с.

36. Кун X., Таккер А. (Kuhn H.W., Tucker A.W.). Nonlinear programming in J. Neyman //(ed.), Proceedings of the second berkley symposium on mathemathical statistics and probability.—Berkly: University of California Press., 1951.—P. 481—492.

37. Леонтьев B.K. О числе оптимальных планов в задачах о назначениях //Журн. проблем кибирнетики.—1978.—№ 34.—С. 36—43.

38. Маркус М., Минк X. Обзор по теории матриц и матричных неравенств.—М.: Наука, 1972.—С. 232.

39. Мелихов А.Н. Ориентированные графы и конечные автоматы.—М.: Наука, 1971.—416 с.

40. Мизин И.А., Уринсон Л.С., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений.—М.: Изд-во «Связь», 1972.—319 с.

41. Миронов A.A. О реализуемости множества целых неотрицательных чисел степенями вершин графа //Тр. МИИТа, 1976, вып. 510. С. 68—77.

42. Миронов A.A. Геометрия точек пространства Rn, реализуемых в граф //УМН, 1977. Т. 32, № 6. С. 231-232.

43. Миронов A.A. Некоторые свойства наборов чисел реализуемых в граф //Тр. МИИТа, 1979, вып. 640. С. 115—120.

44. Миронов A.A. О реализуемости наборов чисел в граф и свойства графов с заданным набором степеней //Тр. Горьковского Государственного университета, 1981.—С. 76-97.

45. Миронов A.A. О вероятностных свойствах случайного графа с заданным набором степеней вершин //Изв. АН СССР. Техн. кибернетика.—1990.—№ 4. С. 180-188.

46. Миронов A.A., Цурков В.И. Графическое представление многоуровневых иерархических структур //Изв. АН СССР. Техн. кибернетика.— 1991.—№ 3. С. 148-155.

47. Миронов A.A. О свойствах наборов степеней вершин обобщенных графов //ДАН. 1992. Т.324, 5. С. 959-963.

48. Миронов A.A. Обобщенные графы с ограничениями для степеней вершин //ДАН,— 1993. Т.ЗЗЗ, 4. С. 437-439.

49. Миронов А.А., Цурков В.И. Класс распределительных задач с минимаксным критерием //ДАН.—1992.—Т. 336, № 1.—С. 35—38.

50. Миронов А.А,Цурков В.И. Сетевые модели с фиксированными параметрами на узлах связи. I //Изв. РАН. Техн.кибернетика.— 1993.-4 с. 212-223.

51. Миронов А.А.,Цурков В.И. Сетевые модели с фиксированными параметрами на узлах связи. II //Изв. РАН. Техн.кибернетика.— 1993.—6.—С. 3-14.

52. Миронов А.А., Цурков В.И. Аппроксимация и декомпозиция экстремальными графами //РАН. Журн. вычисл. математики и мат. физики.—1993.—Т. 33, № 2. С. 283-298.

53. Миронов А.А.,Цурков В.И. Транспортные и сетевые задачи с минимаксным критерием //РАН. Журн. вычисл. математики и мат. физики.—1995.—Т. 35.— С. 24-45.

54. Миронов А.А.,Цурков В.И. Задачи транспортного типа с минимаксным критерием //А и Т.—1995.—С. 109-118.

55. Миронов А.А.,Цурков В.И. Транспортные задачи с минимаксным критерием //ДАН.—1996,—Т. 346—С. 1-4.

56. Миронов А.А. Равномерные обобщенные графы //ДАН—1996. Т. 351, № 4.

57. Миронов А.А., Цурков В.И. Минимакс в транспортных задачах.—М.: Наука, 1997.—400 с.

58. Моисеев Н.Н.(ред). Современное состояние теории исследования операций.— М.: Наука, 1979.—464 с.

59. Моисил Г р. К. Алгебраическая теория дискретных автоматических устройств.—М.: Наука, 1963.—324 с.

60. Моудер Дж., Элмаграби С. Исследование операций. Методологические основы и математические методы. Т. 1.—М.: Мир, 1981.—712 с.

61. Моудер Дж., Элмаграби С. Исследование операций. Модели и применения, Т. 2.—М.: Мир, 1981.—678 с.

62. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование.—Новосибирск: Наука, 1977.—320 с.

63. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение.—М.: Наука, 1970.—707 с.

64. Нечепуренко М.И. (ред.). Алгоритмы и программы решения задач на графах и сетях.—Новосибирск: Наука, 1990.—515 с.

65. Оуэн Г. Теория игр.—М.: Мир, 1971.—230 е..

66. Панос М. Пардалос (Panos М& Paréalos). Minimax and Applications& University of Minnesota$ and Institute of Applied Mathematics, Academia Sinica, Beijing, PRC, 1995. 308 p.

67. Пропой A.M. Элементы теории оптимальных дискретных процессов.— М.: Наука, 1973,—256 с.

68. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи.—М.: Наука, 1980.—320 с.

69. Райзер (Ryser HJ.). Combinatorial properties of matrices of zeros and ones //Cañad. J. Math.—1957.—V. 9.—P. 371—377.

70. Райзер (Ryser H.J.). The term rank of a. matrix //Cañad. J Math.—1958,—V, 10,—P. 57—65.

71. Райзер (Ryser H.J.). Traces of mtrices of zeros and ones //Cañad. J. Math.—1960.—V. 12.—P. 463—476.

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

73. Рогинский Б.Н. (ред.). Теория сетей связи.—М.: «Радио и связь», 1981.—192 с.

74. Рокафеллар Р. Выпуклый анализ.—М.: Мир, 1973.—470 с.

75. Рыбников К.А. (ред.). Комбинаторный анализ. Задачи и упражнения.—М.: Наука, 1982.—365 с.

76. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы.—М.: «Мир», 1973.—302 с.

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

78. Сикорский Р. Булевы алгебры.—М.: «Мир», 1969.—375 с.

79. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации.—М.: Наука, 1986.—326 с.

80. Толстой А.Н. Методы устранения нерациональных перевозок при планировании //Социалистический транспорт. — 1939. — № 9. — С. 28—51.

81. Триус Е.Б. Задачи математического программирования транспортного типа.—М.: Современное радио, 1967.—208 с.

82. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1.—М.: «Мир», 1984.—527с.

83. Форд Л., Фалкерсон Д. Потоки в сетях.—М.: «Мир», 1966.—276 с.

84. Харари Ф. Теория графов,—М.: ИЛ, 1963.—300с.

85. Хачатуров В.Р., Монтлевич В.М. Решение нелинейных производственно—транспортных задач с неделимыми потребителями.—М.: ВЦ АН СССР, 1987,-24 с.

86. Хичкок (Hitchcjck F.L.) Distribution of a product from several sources to numerous localities //J. Math. Phys.—1941—V. 20.—P. 224—230.

87. Холл M. Комбинаторика.—M.: «Мир», 1970.—424 с.

88. Ху Т. Целочисленное программирование и потоки в сетях.—М.: «Мир», 1974.—520 с.

89. Цурков В.И. Декомпозиция в задачах большой размерности.—М.: Наука, 1981.—352 с.

90. Цурков В.И. Динамические задачи большой размерности.—М.: Наука, 1988.—288 с.

91. Цурков В.И., Литвинчев И.С. Оптимизация и исследование операций. Декомпозиция в динамических задачах с перекрестными связями, ч.

1.—М.: Наука, 1994.—176 с.

92. Цурков В.И., Литвинчев И.С. Оптимизация и исследование операций. Декомпозиция в динамических задачах с перекрестными связями, ч.

2.—М.: Наука, 1994.—176 с.

93. Черников С.Н. Линейные неравенства.—М.: Наука, 1968.—488 с.

94. Яблонский C.B., Лупанов О.Б. (ред.). Дискретная математика и математические вопросы кибернетики. Т. 1.—М.: Наука, 1974.—312 с.

95. Яблонский C.B. Введение в дискретную математику.—М.: Наука, 1979.—272 с.