автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Минимакс в транспортных моделях

На правах рукописи

Миронов Анатолий Анатольевич

МИНИМАКС В ТРАНСПОРТНЫХ МОДЕЛЯХ

05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на сонскание ученой степени доктора физико-математических наук

Москва - 1998

Работа выполнена в Вычислительном Центре Российской Академии Наук

Официальные

оппоненты: - доктор экономических наук, профессор В.В. Лебедев доктор физико-математических наук, профессор В.В. Федорчук доктор .физико-математических наук, профессор В.Р. Хачатуров Ведущая организация: Институт проблем управления РАН

Защита состоится " ^^ иИ^/З'^ег^» 1998 г. на заседании Диссертационного Совета Д 002.32.05 при Вычислительном центра РАН по адресу: 117967, ГСП-1, Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан " ° " 1998 г.

Ученый секретарь Диссертационного

Совета Д 002.32.05

кандидат физико-математических наук | В.А. Бушенков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эти построения можно применить и для исследований множеств транспортных матриц, с непревышающими единицы элементами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цели исследования. Основными целями исследования диссертационной работы являются:

- построение замкнутых транспортных моделей с минимаксными критериями;

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

- создание различных методов для исследования транспортных матриц и усеченных транспортных многогранников;

- построение критерия единственности минимаксной матрицы транспортного многогранника;

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

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

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

Научйая новизна. Важнейшими достижениями диссертационной работы являются следующие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

д) любая транспортная матрица размерности п х т с точностью до перестановки строк и столбцов и с точностью до положительного коэффициента принадлежит множеству матриц 0](гц т) — {А'(А,В) : Х(А, В) € М(А, В), (А, В) € Ь(п,?п)}.

Теоретическая и практическая значимость работы состоит:

- в применении результатов в областях математическое программирование и исследование операций;

- в;Иостроении моделей транспортного типа с минимаксными критериями;

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

- в создании методов исследований транспортных многогранников и их матриц;

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

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

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

- в построении ограниченного множества матриц, содержащего с точностью до перестановки строк и столбцов и с точностью до положительного коэффициента любую транспортную матрицу.

Аппробадия работы и публикации. Результаты диссертационной работы докладывались и обсуждались:

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

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

По теме диссертации опубликовано 17 работ, среди которых - монография (в соавторстве) "Минимакс в транспортных задачах".

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Главы разбиты на параграфы, параграфы - па подпараграфы. Общин объем работы - 241 страница, включая 6 страниц списка литературы, содержащего 95 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Применяются следующие обозначения: для множеств векторов -= {А = (аи ... ,«„) : «,• > 0, 1 < « < г?}, = {А € : а,- > 1 < г < п (если п > 2)}, = {а е Щ. щ е г, 1 < г < п}, Т+ = {А е г^ пТг^,};

если для векторов А 6 Я!}., В 6 справедливо условие замкнутости

п т

1>=1>. (О

1=1 7=1

то матрицей-планом (транспортной матрицей) замкнутой транспортной задачи, определяемой векторами А, В, называется матрица

.Х(А,В) = (x¡j), Xi¡ > О, 1 < i < n, 1 < j < m, где

m n

Y^Xij = a¿, 1 < i < n, ]>>•; = i - i — m' ^

j=\ 1=1

для матричных множеств -

M(A,B) = {X(A,B)},

M(A,B;c) = {A'(A, B) arfj < с, 1 < 1 < n, 1 < j < m),

где с > 0, называемых транспортными многогранниками, последний из которых относится к классу усеченных, и, если А £ В £ Z"', с £ Z, то

Mz(А,В) = {Х(А, В) = : хц £ Z, 1 < i < n, 1 < j < m}, Мг(А,В;с)={Х(А,В)еМг(А,В)П1М(А,В;с)}.

Очевидно, что A/(A,B) ^ 0 (и A/z(A,B) ф 0) для любых векторов с неотрицательными координатами А и В, удовлетворяющими условию замкнутости (1), и каждая матрица из неотрицательных элементов (xij) является транспортной для векторов А и В, координаты которых определяются равенствами из (2).

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

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

Из множества М(А, В) выделяется подмножество матриц, обладающих специальным свойством.

Определение 1. Матрица ЛГ(А,В) = (a,-,j) называется равномерной, если для ее элементов и координат векторов А = (ai,. .. ,ап) £ Я" и В = (í>i,..., b,n) £ ñ™ справедливы следующие два условия:

а) если a¡ = ар и bj = Ья, то x,j = xpq, 1 < i, р < п, 1 < j, q < tn;

б) если а,- > ар и bj >bq, то x¡j > xpq, I < г, р < п, l < j, q < т.

Для множества равномерных матриц, определяемых векторами А

hJ3, вводится обозначение:

М{А, В) = {Х(А, В) £ М(А, В) : Л"(А,В) - равномерная матрица }.

Определение 2. Множество равномерных матриц М(А, В) называется равномерным матричным множеством или равномерным транспортным многогранником.

Важность определений 1 и 2 раскрывается во второй и четвертой главах.

Через А = (а\,... ,а„) обозначается вектор, построенный из координат вектора А = (щ ,... , ап) упорядочиванием их по невозрастанию (а,- > а,-+1, 1 < г < п— 1, если п > 2). Пусть А = (а],...,ап) Е и В = (Ь[,... ,ЬШ) 6 Я™. Каждую матрицы Л'(А,В) = можно

перестановкой строк и столбцов привести к матрице, обозначаемой Л'(А, В) = (;с0-), для которой

т п

у^ X,] = а,-, 1 < г < п, ^ хг] = Ь], \ < ] < т,

7 = 1 ¿=1

где А = (а1,...,а„), В = (£>!,...,6т). Поэтому без ограничения общности, во многих транспортных задачах для множества матриц Л/(А,В) можно предполагать упорядоченность координат векторов А и В по невозрастанию.

В следующей главе строются алгоритмы минимизации функционалов:

«МЛ'(А, В) Ф2(Х(А,В)

Ф3(Л'(А,В)

Ф4(Л'(А,В)

Ф5(Л'(А,В) Фб(Л'(А,В) Ф7(Л'(А, В) Ф8(А'(А, В)

'.7

ь1] 1

= ^ шах ,

7=1

= ^^ тах х^ + ^^ шах х,} , ¿ = \ ' ¿=1 3

т

= таха1,^- + 2, тахж,^,

т п

= тах х,] + ^^ шахх'1;- + ^^ тах

1,3 7 = 1 ' г'=] ;

£ ф2(у')' Г £ ОТ (Л'(А,В))

ГеОТ(А'(А,В))

УбЩЛ'(А,В))

(3)

(4)

(5)

(6)

(7)

(8) (9)

п

Ф9(А'(А,В)) = ]Г Ф1 (У)+ £ Ф2(К), (11)

Уеяп(Х(А,в)) yerai(x(A.,B))

Ф10(А(А,В)) = £ ф1(Г)+ £ фз(Г)- (12)

Уе9Л(Х(А.,В)) У'еЩХ(А,В))

где A G R+, В £ Щ, Х(А,В) = (х,;) G М(А,В) и 2Л(А'(А,В)) -множество всех подматриц матрицы А(А, В) €Е М(А,В). Для целевых функций (3)—(12) очевидно, что

Ф3(Х(А, В)) = Ф2(Х(А, В)) + Ф2(Л'(В, А)), Ф4(А(А,В)) = Ф1(А'(А,В)) + Ф2(Л'(А,В)), Ф5(А(А,В)) = Ф1(А(А,В)) + Ф3(А(А,В)), ФЭ(А(А,В)) = Ф8(А(А,В)) + Ф6(А(А,В)), Ф10(А(А, В)) = Ф8(А(А, В)) + Ф7(Л'( А, В)).

Минимизируется также функционал (3) в классе целочисленных транспортных матриц, определяемой парой целочисленных векторов:

Фг(А(А,В)) = maxxij, Х(А,В) - (*у) G Mz(А,В), (13)

где А = (ai,... ,а„) € 1 < г < п, В = (6Ь ...,6m) G Z?, 1 < j < т.

Вводятся для пар векторов две естественные операции. Если а £ R, А, С е Rn и В, D 6 Rm, то «(А, В) = (aA, аВ) и (А, В) + (С, D) = (А + С,В -f D). Очевидно, что эти операции для пар векторов согласованы с операциями над матрицами-планами транспортных задач. Если a > 0 и матрицы Х(А,В), A'(C,D) имеют общий порядок, то aX(A,B) = A'(aA,aB) и Х(А,В) + A(C,D) = X(A + C,B + D). __ Очевидно, что М(А, В), М(А, В), А/(А, В; с),

А/(А,В;с) = AÍ(A,В)ПЛ/(А, В; с) являются выпуклыми множествами (многогранниками). Также легко видеть, что функционалы (3)—(12) -выпуклые функции. Отсюда следует, что задачи минимизации функционалов (3)—(12) можно отнести к экстремальным выпуклым задачам.

Для векторов А = (aj,..., an) £ /£+, В = (6Ь ... ,6m) 6 ñ™ (условие замкнутости не предполагается), и значений с, к, где с > 0 и к £ Z, 1 < к < п, рассматривается функция

i —' bj>ck i<k

участвующая во многих исследованиях диссертации.

Для функции (14) применяются следующие равносильные выражения:

т к к

<5fc(A,B;c) = ^Pmin(6j,c&) - ^я,- = ^ bj + cklk(В;с) - У]я,,

j = 1 1 = 1 bj<c к ( = 1

где /*(В;с) - количество координат вектора В = (6i,..., 6m), значения которых не меньше, чем ск: /*(В;с) = |{j : bj > ск, 1 < j < m}|.

В §2 для условия А/(А,В;с) ф 0 строится критерий в форме системы линейных ограничений, несодержащей избыточных соотношений, и создаются алгоритмы вычисления элементов матриц из

М(А,В;с).

Следствием теоремы Гейла, применяемой в исследованиях усеченных транспортных многогранниках, является утверждение.

Лемма 1. Пусть А € Я'|, В £ . Множество М(А,В;с) ф 0 (или Mz(A,B;c) ф 0) тогда и только тогда, когда ¿¿(А, В; с) > 0 при всех к € Z, 1 < к < п - 1.

Для пары векторов А, В, удовлетворяющих (1), где А 6 R+ и <5it(A,B;c) > 0 при всех к, рассматривается специальное разбиение на две пары А',В' и А", В": А ' = (я],..., яр), А = (ар+1 > ■ ■ • > ап), SP(A, В; с) = min{ö^(A; В; с) : 1 < к < п - 1} и В = В'+ В", В' = (6j,..., b'm), bj = bj — cp, если bj > cp, bj — 0, если bj < cp. Показывается, что

6k(A',B';c) = Sp+k(A,B;c)-Sp(A,B;c), 1 < к < n - p,

Sk(A",B";c) = 6i(A,B;c), 1 < к < p.

Строится любой вектор D = (di,...,dm) € Я+ такой, что d\ + ... + dm = 6P{А, В; с) и В* = В' + D, b) + dj < c(n - p), 1 < j < m, В** = B" - D e R+. Показывается, что вектор D всегда существует (в частности, D - нулевой вектор, если <5Р(А, В; с) — 0) и каждый такой вектор D определяет две пары векторов А', В* и А", В**, удовлетворяющих условию замкнутости (1) для которых функция (14) неотрицательна при всех допустимых значениях к.

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

Конструкция, приведенная выше, является основной в алгоритмах построения матриц из М(А,В;с). Она позволяет свести вычисление матрицы к вычислениям 1-строчных матриц. Различным векторам

D соответствуют различные матрицы из М(А,В;с), причем, каждой матрице из М(А, В; с) соответствует свой вектор D. На основании этого строится алгоритм вычисления любой матрицы их М(А,В;с).

Также в диссертации строится алгоритм, несвязанный с решением системы линейных ограничений, определяющей вектор D, приводящий к единственной матрице. В этом случае для вектора D £ R™ полагается dm+1 = 0 и

dm_¿ = min {ср, сп — ср, bm-i, сп — 6m_¿, 6р(А, В; с)—

т+1

- £ dj), 0<г<т-1, (15)

j=m-i+l

Если А, В - целочисленные векторы и с 6 Z, то соответствующий алгоритм определяет любую целочисленную матрицы из Aíz(A,B;c). Заметим, что в этом случае вектор (15) - целочисленный.

В лемме 1 для проверки условия М{А, В; с) ф 0 содержится система из п — 1 неравенств. Как показывается в диссертации, неотрицательность функции (14) заведомо справедлива при достаточно малых и больших значениях к и нет надобности проверять эти неравенства для тех значений к, при которых а^ = a¡¡+i- Для А € В 6 R™ и с > О строится множество индексов 7(А,В;с): к' = тах{& : ск < min{6j}}, к" = min{Ar: ск > тах{&.,•}}, к* = к' +1, к= fc" - 1 и

/(А, В; с) = {к*, к**} U {к: к* < к < к*', Ък >ак+1}.

Теорема 1. Пусть для векторов А £ В £ R.™ справедливо условие замкнутости (]).

а) Л/(А, В; с), Mz{A, В; с) ф 0 тогда и только тогда, когда, либо 7(А,В;с) ф 0, либо, если /(А,В;с) ф 0, то 6*(А,В;с) > 0 при всех Ае/(А,В;с).

б) Если /(А, В; с) ф 0 и I С /(А, В; с), I ф /(А, В; с), то существуют векторы, удовлетворяющие (1), С £ Щ., D £ R™ такие, что /(C,D;c) = i(A,B;c), ¿jt(C,D;c) > 0 при всех k £ I и M(C,D; с) ф 0.

В §3 раскрывается матричный смысл функции (14). Для произвольной матрицы Х(А,В) = (z,j) из Л/(А,В;с) или из Mz(A,B;c) и к £ Z, 1 < к < п, рассматриваются подматрицы X' = (Xi¡), 1 < i < к, bj > ск, X" = (x¡j), к < i < и, bj < ск. Пусть s(A') - сумма элементов матрицы X, причем, s(X) — 0, если матрица X не существует.

Теорема 2. Если А/(А,В;с) ф 0 (или А-/г(А,В;с) ф %), то для любой матрицы из Л'(А,В) из Л/(А, В; с) (или из Мг(А, В; с)) справедливо соотношение

¿¿(А, В; с) = ск1к(Л; с) — в(Л'') + .ч(Х"), 1 < к < п. (16)

(Определение 3. Уравнение (16) называется характеристическим для матричных множеств А/(А,В;с), М2((А, В; с).

Характеристические уравнения определяют общие свойства всех матриц из А/(А,В;с), Л/г(А,В;с), а значения функции (14) определяют возможные различия между этими матрицами. Применение уравнений (16) позволяет строить матрицы из множеств М(А,В;с) и Л/г(А,В;с) с заданными свойствами, определяемые переменными I; £ 2, «(^г/) и я(Х"). Задавая значения переменным «(Х') и «(А'") и "распределяя" эти значения по элементам подматриц X' и X", характеристические уравнения (16) также можно использовать в построении всех матриц из Л/г(А, В; с). Причем, чем меньше значения функции (14), тем меньше решений имеет уравнение (16), тем проще устроено матричное множество Л/^(А,В;с). Очевидно, что характеристические уравнения позволяют приводить оценки для количества матриц из Л/2(А,В;г). Из очевидного неравенства ¿^(А.,В;с) < <">*(А,В;с) следует, что исследование матриц и матричных множеств характеристическими уравнениями наиболее удобно проводить, когда вектор А € И+.

В случае А £ п ¿¿(А,В;с) = тш{£ : ¿¿-(А, В; с)} показывается, что для любого решения в', в" уравнения (16) (удовлетворяющего естественным ограничениям) существует матрица Л'(А,В) £ А/(А,В;с), для которой «(А'') = в(Х") = в". В частности, справедлива теорема.

Теорема 3. Пусть А Е Щ., В £ Я™. Если множество матриц Л/(А,В;с) ф 0 и ¿р(А,В;с) = 0 при некотором р £ 1 < р < п, ср < тах{6; : 1 < ] < гп}, то для элементов любой матрицы (х= Л'(А,В) £ А/(А,В;с) справедливо

_ / с> 1 < г < р, > ср, Х'3 ~ 1 0, р < г < п, Ь^ < ср.

В главе 2 минимизируются функционалы (3)-(13), приводится критерий единственности минимаксной матрицы, строится наследственно минимаксная матрица.

В §1 опредёляется минимаксное значение, строются необходимые и достаточные условия, при которых минимаксная матрица - единственна, и минимизируются значения функционалов (3) и (13).

Определение 4.

а) Величина с(А,В) = min шаха;,-,

Ог0-)6М(А,В) i,j

= min <í>i(X(A,B)) = minie : AÍ(A,B;c) Ф 0) называется

X(A,B)6AÍ(A,B) v V " 1 V . W 7- J

минимаксом (минимаксным значением) множества М(А, В).

б) Матрицы из М{А, В; с(А, В)) называются минимаксными.

В следующих двух утверждениях содержатся критерии минимаксности и свойства минимаксных матриц.

Теорема 4. Пусть векторы А £ В £ ñ™ удовлетворяют условию (1) и с > 0. Для того, чтобы с = с(А, В) необходимо и достаточно, чтобы выполнялись следующие условия для функции (Ц): а) функция ¿t(A,B;c) > 0 при всех k £ Z, 1 < к < п; б) существует р £ Z, 1 < р < п, ср < max{6j : 1 < j < т}, для которого 5р (А, В; с) = 0.

Теорема 5. Пусть Х(А, В) = (x{j) - минимаксная матрица, где А £ RI, В £ R^.

а) Если р и q такие индексы, что ар = max{a¡ : 1 < г < п} и Ья — таx.{bj : 1 < j < т}, то хря = с(А,В).

б) Для элементов матрицы Х(А,В) = (xij), построенной из матрицы Х(А,В) перестановкой строк (А £ имеет место

с(А,В), если существует k £ Z,

для которого k > i, ск > bj и ¿jt(A,B;c) = 0, 0, если существует к £ Z,

для которого к < г, ск > bj и <5д.(А,В;с) = 0.

В диссертации строются два критерия для |Л/(А,В; с(А, В))| = 1, один из которых включает тривиальный случай |М(А,В)| = 1, а другой (приведенный здесь) справедлив в случае |М(А,В)| = оо.

Теорема 6. Пусть М(А,В;с) ф 0 и А'(А,В) £ М(А,В;с), где А £ R+, п > 2, В £ R™, т >2, а2 > 0, 62 > 0. Обозначим р0 = 0, ¿Ро(А,В;с) = 0 и t = £ Z : 1 < k < n,6k(A,B;c) = ü,ck < 6i}|. Матрица X(A,B) = (xpí) является единственной матрицей множества Aí(A,B;c) (и с — с(А, В)) тогда и только тогда, когда t > 1 и, если pi, p¡ £ Z, 0 < i < t - все последовательные значения, при которых epi < bi и ¿p.(A,B;c) = 0, то /(B;c,p,_i) - /р>(В;с) < 1

в случае p¡ — p¡_i > 1, 1 < i < t, и pt + 1 = max{í : 1 < i < n, a¡ > 0} б случае /(В; c,pt) > 1 (где /(В; с, к) — |{j : bj > ск, 1 < j < m}|j.

Для Л'(А, В) £ М(А, В; с(А, В)), где |М(А, В; с(А, В))| = 1, в диссертации строится формула, определяющая все элементы матрицы Л'(А, В). Отметим частный случай теоремы 6.

Теорема б'. Если А £ В £ R+ , где п,т > 2, й2,Ьп > 0 удовлетворяют (1) и 6к( А, В; с(А, В)) = 0 при всех к. 1 <к<п, то \М(А, В; с(А, В))| = 1.

Очевидно, что с(А,В) = 0 тогда и только тогда, когда А и В -ненулевые векторы, и с(А,В) = с(А,В). Пусть В € ñ+, где ¿i > 0. Отметим индексы тех координат вектора В, прп которых отмеченные координаты больше последующих (если Ьг > Ьт) и положим, что т' -индекс последней положительной координаты вектора В: Т(В) = {к £ Z Л < к <т - \ ,Ък > bk+¡] U {т'}. Обозначим t = |Т(В)|. Положим k¡ £ Т(В), где 1 < i < t, к{ < ki+], 1 < i < t - 1 (если t > 1).

Для ненулевых векторов А £ В £ F¿+ и пары чисел к £ k¿ £ Т(В), где 1 < к < п, 1 < г < t рассмотрим систему соотношений

tn bj к '

-£«,• = о, j=1 j=1 ¿=1

i 1 < к < íi, 1 < г < t, (17)

c(k,ki)k < bki,

. c(k, k¡)k > bk¡+], i ф t,

с единственной неизвестной величиной c(k,ki). Если решение c(k,ki) этой системы существует, то оно единственно, так как первое уравнение системы линейно относительно c(k,ki). Если у системы (17) нет решений, то положим с(к,к{) = 0.

Теорема 7. Для ненулевых, удовлетворяющих (I), векторов А £ В £ /£+ справедливо равенство с(А,В) = max{c(fc, k¡) : 1 < k < < п, ki ЕТ(В)}.

Определение 5. а) Пусть векторы А £ и В £ имеют равные суммы координат. Величина cv(А, В) = min {maxía:,-, :

(ги)бЛЫА,В)1

1 < г' < 1 < j < m,{xij) £ Mz(A,B)}} =

min Фг(Х(А,В)) = minie £ Z : A/Z(A,B) ф 0} называется

Л-(А,В)еМл(А.,В)

(целочисленным) минимаксом множества М%(А, В), б) Матрицы из множества Mz(A, В; с^(А, В)) называются минимаксными (в классе целочисленных матриц из М7{ А, В)).

Теорема 8. Для ненулевых, удовлетворяющих (1), векторов А £ £+) В £ справедливо равенство сг{А, В) = тах{]с(£, &,•)[: 1 < к < п, € Т(В)}, где ]а[ - наименьшее целое число, не меньшее числа а.

В теоремах 7 и 8 заключены алгоритмы вычислений минимаксных значений, минимизирующих функционалы Ф1(Х(А,В)) и Фг(Х(А,В)).

В §2 для произвольного транспортного многогранника строится минимаксная матрица, у которой минимаксность - наследственное свойство и:выделяется ряд функционалов из (3)-(12), минимизируемых равномерными матрицами.

Определение 6. Минимаксная матрица называется наследственно минимаксной, если каждая ее подматрица является минимаксной матрицей (своего транспортного многогранника).

Алгоритм построения наследственно минимаксной матрицы приводится в диссертации для векторов А 6 В 6 Я+ (что не ограничивает общности) и основывается на теоремах 5 и 7. Теорема 7 вычисляет минимакс с(А,В), а теорема 5 определяет элементы матрицы равные с(А, В) или 0. Теорема 5 также определяет (если не все элементы еще вычислены) два транспортных многогранника (возможно, один) для которых опять применяются теоремы 5 и 7. И т.д. Тем самым строится матрица, обозначаемая Л'(А,В).

Теорема 9. Матрица Х(А,В) является наследственно минимаксной.

Теорема 10. Каждый транспортный многогранник содержит одну и только одну наследственно минимаксную матрицу.

Очевидно, что наследственно минимаксная матрица минимизирует функционал (3). Следующие утверждения полезны при вычислении оптимальных значений некоторых функционалов.

Лемма 2. Любая наследственно минимаксная матрица является равномерной.

Лемма 3. Любая подматрица равномерной матрицы является равномерной матрицей.

Последнее утверждение показывает, что равномерность - наследственное свойство для матриц, и позволяет вычислить значения функционалов Ф(А'(А,В)), где г = 2,3,7, от равномерных матриц. В частности справедливо утверждение.

Лемма 4. Для любой равномерной матрицы А"(А,В) £ М(А, В), где А £ R+, В € , справедливо:

Ф3(А'(А, В)) = тах{а,- : 1 < i < n} + max{6;- : 1 < j <' т}\' '

п т

Ф7(А'(А,В)) = 2т-' + 2п-1^2т-'Ъ.

к=\ к-1

В диссертации показывается, что правые части равенств леммы 4 являются минимальными значениями функционалов (3), (7) и эти функционалы минимизируются каждой равномерной матрицей.

В §3 показывается, что наследственно минимаксная матрица - это единственное решение минимизации функционалов (10)-(12), и вычисляются минимальные значения указанных функционалов.

Теорема 11. Для векторов А £ Щ., В £ Ä+, удовлетворяющих

(1), имеет место <i>g(A'(A, В)) > <J>s(A'(A,B)) для любой матрицы А'(А, В) ф А'(А,В) и

* п ТП ~

где наследственно минимаксная матрицаХ(А, В) = (ajj) построена

из (наследственно минимаксной) матрицыХ(А,Л) = (xij) перестановкой строк и столбцов, при которой А £ R+, В £ R+. Из теоремы 11 и лемм 2, 4 следует утверждение. Теорема 12. Пусть векторы А, В удовлетворяют условию теоремы 11. Тогда

min Ф9(А'(А,В)) = ФЧ(А'(А,В)) < ФЭ(А'(А,В)),

A'(A,D)6AffA,D)

min Ф,о(Х(А, В)) = Ф10(Л'(А, В)) <Ф10(А(А, В)),

Л'(А,В)ЁЛГ(А,В)

где А'(А, В) ф А'(А,В);

* Л — ~ п т ~

ФЭ(А(А,В)) = Ф9(Л'(А,В))= Е Е

i — 1 J — 1

ж £ ~ ~ п гп ~

Фю(А'(А, В)) = Фю(А'(А, В)) = Е Е +

1 = 1j=l

п т _

+ Е 2n-tat)+2n-1 Е 2m-*6fc.

k = \ k =1 Отметим, если транспортный многогранник содержит единственную минимаксную матрицу (теорема 6), то эта матрица - наследственно минимаксна. В главе 4 применяются минимаксные матрицы,

состоящие из 0 и 1, являющиеся единственными минимаксными матрицами своих транспортных многогранников.

В главе 3 рассматриваются целочисленные пары векторов и матрицы. Приведенные методы применимы в построениях матриц в целочисленных моделях транспортного типа.

В §1 строится алгоритм вычисления целочисленной транспортной матрицы с общим ограничением сверху для элементов. Здесь можно воспользоваться и алгоритмами первой главы, которыми, в частности, можно строить целочисленные минимаксные матрицы (применив теорему 8). Условие целочисленности позволяет привести более простые и наглядные правила построения матрицы. Конструкция алгоритма заключена в последовательном вычислении элементов строк.

Пусть В £ Z+, а,с Е Z, а,с> 0. Построим последовательность из

а + 1 векторов (если это возможно) Bit = (ß[k\ ■ ■ ■ > ßm 0 < Ar < а, где В0 = - ■ ■ ,ßm = В = (bi,..., bm) и при переходе от вектора В* к вектору Bfc.|_i, 0 < к < а — 1 (если а > 1) на единицу уменьшается одна и только одна любая положительная координата ß\k^ вектора Bjt, удовлетворяющая условию ß^ = таx{ßjk^ : 1 < j < гп, ß(o) _ ß(k) < c-j Если A e T0 обозначим a(1) = (a2,...,an),

B^ = B0l. Пара векторов А, В называется с-приводимой, если для нее существует пара векторов А^1', BÜ,l\ которая называется главной (с\\)-редукционной для А,В. Если п J> 2 и А^1', В^ - с-приводимая пара векторов, то существует =(а3,... ,ап),

в!2) = (В^)!^ = (в!1))^ - (с; 2)-редукционная пара векторов. Если построена А^-1', - (с, к — 1)-редукционная пара векторов, то положим А^ = (А^-1^1-' = (etjt+i, • • •, ап), Bi*) = (Bi*-^)!0 = (B*_1)at - (с; &)-редукционная пара векторов для А,В (к < п). Переход от A(fc_1), к A(fc), называется к-редукционным шагом. Основным результатом параграфа является следующий.

Лемма 5. Если векторы А € Z+, В £ Z™ удовлетворяют (1) и с £ Z, с > 0, то Мг(А,В;с) ф 0 тогда и только тогда, когда пара векторов А, В - с-приводима и с-приводима каждая главная (с; к)-редукционная пара векторов А^к\ построенная на к-редукционном шаге, 1 < k < п — 1.

В лемме 5 заключены жесткие правила в алгоритме построения матрицы А'(А,В) = {х^) £ Л/;?(А,В;с) ф 0:

= ь -£1 <з <™> = №)> 1 <г'<

к<{

В §2 применяются методы предыдущего параграфа в случае с = 1. Исследуются пары векторов и матрицы, состоящие но 0 и 1, функцией (14), где с = 1:

тп к

й,(А, В; 1) = ~ - *) - 1 < * < п; (18)

.7 = 1 Ь>к ¡ = 1

приводятся леммы 1 и 5 при с — 1 и строится редукционный алгоритм, определяющий матрицу из А, В; 1). Этот параграф может рассматриваться как введение для четвертой главы.

В главе 4 рассматриваются специальные (экстремальные) матрицы, состоящие из 0 и 1, и пары векторов, определяющих их. Эти матрицы применяются в транспортных моделях и методах исследования транспортных многогранников и их матриц.

В §1 исследуются пары векторов, транспортные многогранники которых содержат одну и только одну матрицу, состоящую из 0 и 1, и соответствующие им указанные матрицы. Подсчитываются количества таких пар векторов и матриц одного подрядка.

Определение 7. Пара векторов А € Z + и В £ Z+ называется экстремальной, если 6^(А,В; 1) = 0 для всех кЕЕ,1<к<п.

Теорема 13. Пусть А £ и В £ удовлетворяют условию (1). Множество Л/^(А,В; 1) состоит из единственной матрицы тогда и только тогда, когда А, В - экстремальная пара векторов.

Определение 8. Если А, В - экстремальная пара векторов, то единственная матрица Л'(А,В) из Л/^(А,В;1) называется экстремальной.

В диссертации приводится и редукционный критерий экстремальности.

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

—^ ——т

Теорема 14. Пусть А Е Z+ и В £ Z+

и А'(А,В) = (г^) £ Л/^(А,В;1) ф 0. Для экстремальности пары

векторов А,В необходимо и достаточно, чтобы

{1, 1 < г' < п, \ <з< /¿(В; 1), О, 1 < г < л, /¿(В; 1) < ) < т.

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

Определение 9. Матрица X = (ху) 1 < г < 71, 1 < ] < т, называется экстремальной, если каждый ее элемент ху равен нулю или единице и для всех г, 1 < г < п, 1 < < т, имеет место: из равенства £у = 1 следует, что хрч = 1 при любых р, д, 1 < р < г, 1 < 9 < , а. из равенства ху = 0 следует, что хря — 0 при любых р, г/, г < р < п, 1 < д < т.

В параграфе строются и другие условия экстремальности. Например, справедлива теорема.

Теорема 15. Если А 6 и В £ г" к Мг{А,В;1) ф 0, то эквивалентны матричные понятия равномерность, наследственная минимаксность и экстремальность.

Введем обозначения множеств экстремальных нар векторов и матриц:

Е ' — {(Е,Г) : Е £ V £ Z+, (Е,Г) - экстремальная пара векторов },

Ёп,т = {А(Ё,1Г) = (ху):_(Ё,Г) € £ М2(Ё,Ё; 1)}.

Теорема 16, |"Г,т| = \Еп,т\ = С£+т. _^ ^

Определение 10. Множества экстремальных пар векторов Е и экстремальных матриц Еп<т называются фундаментальными системами (пар векторов и матриц).

В §2 и §3 устанавливаются алгебраические и метрические свойства фундаментальных систем пар векторов и матриц.

Для А,В, С,Б £ Яп и Л' = (ху), У = (?/у), 1 < г < п, 1 < ^ < т, положим: А < В, если а,- < ¿¿, 1 < г < п, и А < В при А < В и А ф В; (А,В) < (С,Б), если А < С, В < Б, и (А,В) < (С,Б) при (А,В) < (С,Б) и (А,В) ф (С,Б); АСУ, если Ху < у,, 1 < i < п, 1 < ^ < т, и А' С У при А' С У и X ф У. Очевидно, что множества Е ' и ЕП:ГП с отношениями для элементов "<" и "С" образуют частично упорядоченные множества. В диссертации показывается, что для экстремальных пар векторов отношение порядка достаточно установить только у первых или только у вторых векторов.

Для векторов А, В £ R" введем две операции: А V В = Си А Л В = D, где с,- = max(a¿,''¿) и d¡ — min(a¿, 6¿), Г < i < п. Перенесем эти операции на пары векторов, имеющих общий порядок: (А, В) V (С, D) = (А V С, В V D), (А, В) Л (C,D) = (А Л С, В Л D). Для матриц Л' = (x{j) и Y — (yij) одного порядка положим X U Y = (rnax(x,j, j/,j)), Л' П Y = min(zt;)). Множества Е ' и Еп,т замкнуты относительно этих операций. Более того (в дальнейшем #(E,F) - экстремальная матрица, образованная экстремальной парой векторов (Е, F)), справедлива лемма.

Лемма 6. Если (Ёь F), (E2,F2) £ Е 'т, vio

~н(Ё\, Fi) и 772(E2,f2) = 77'((EbFi) v (e2,f2)), U1(EuF1)f)U2(E2,F2) = 77"((Ei,Fi) A (E2,F2)).

Из леммы следует теорема.

Теорема 17. Частично упорядоченные множества Е ' и Еп т соответственно с операциями " V ", " А " и " U " П " образуют изоморфные дистрибутивные решетки, причем, изоморфизмом является отображение <р: Е —► Еп<т, где v?((E,F)) = Я(Е, F).

Для А, В, С, D £ Кп и А' = (x¿-),Y = (уи), 1 < i < п, 1 < j < т, положим:

n п т

р(А,В) = Е к - М- '-(А-,У) = ЕЕ - уу I.

>=i ¿=u=i (19)

/?((A,B),(C,D)) = (p(A,C)+/>(B,D))/2.

Лемма 7. Функции р({А, В), (С, D^ и r(X ,Y) являются метриками на множествах Е ' и Епт, причем ^((Ej^FiJ, (Е2, F2))МЁьЁ2) = p(Fi,F2) и /)((Ei,F2), (Ё2, F2)) = = r(//1(E1,F1),W2(E2,F2)).

Из леммы 7 следует теорема.

Теорема 18. Метрические пространства Е ' и En¡m с метриками, определяемыми (19), являются изометрическими, причем, изометрией является отображение : Е —> Еп т, где

y?(E,F) = 77(E,F).

В §4 строится метод исследования (метод ядер и оболочек) матриц из Л/^(А,В; 1) экстремальными матрицами.

Определение 11. Для А £ ~Z\ и В £ ¿f^, MZ(A,B;1) ф 0 матрицы (порядка п х т) R(А, В) = Р) АДА, В),

A'(A,D)eAíz(A,B;l)

0(A,B) = U Х(А,В) называются ядром и оболочкой

X(A,B)eAíz(A,B;l) матричного множества А/г(А,В;1).

В следующей теореме заключены основные свойства ядра и оболочки и определены условия не тривиальности этих матриц (Н(0), Я( 1) - матрицы, состоящие только из нулей и только из единиц).

Теорема 19. Пусть А £ Z.+ и В EZ+ и Mz(A, В; 1) 0.

а) R(А,В), 0(А,В) - экстремальные матрицы из En¡m.

б) r(ñ(A, В), 0(А, В)) = _ {г (77', 77") : 77' С X С 77" :

я',я"ее„ m

Л'еМг(А,В;1)}.

в) Если bi > 1, то ядро J£(A,B) ф Н(0), тогда и только тогда, когда существует р £ Z, 1 < р < п, для которого р < Ь\ и 6р(А, В; 1) = 0.

г) Если Ьт < п, то при bm > 1, ап > 1 оболочка 0(А,В) ф Н( 1), тогда и только тогда, когда существует р £ Z, 1 < р < п — 1, для которого р < Ь\, /р(В; 1) < т и 5Р(А, В; 1) = 0.

В параграфе конструируются алгоритмы вычисления ядер и оболочек (без применения определения 11), основанные на строении функции (18), и приводятся примеры построения матриц Л(А,В) и 0(А,В), определяющих общие свойства матриц из Mz{А,В;1) (и из

Mz( А,В;1)).

В §5 разрабатываются вероятностные методы исследования целочисленных транспортных матриц.

Для Mz(А,В;1) ф 0 обозначим g(A,B) = \MZ(A, В; 1)|, 9p¿(A,В) = |{Х(А,В) = (х0) : Х(А,В) £ A/Z(A,B;1), xpk = 1}| и p0(A,B) = g¡j(A,B)/g(A,B).

Определение 12. Матрица Р(А,В) = (p¡j(А,В)), 1 < i < п, 1 < j < т, называется матрицей вероятностей множества случайных матриц из Mz(А, В; 1) ф 0, А £ В £ Z?.

. Основные свойства матрицы вероятностей содержатся в теореме.

Теорема 20. Матрица Р(А, В) является равномерной и принадлежит М(А,В; 1) (Р{А, В) £ М(А,В; 1)/ Если А £ и В £ , то для k, q, 1 < к < ti, 1 < q < т, справедливо следующее.

а) Вероятность p¿.?(A,B) = 1 тогда и только тогда, когда существует р £ Z, 1 < р < Ъ\, при котором р > к, /р(В;1) > q и

<5р(А,В;1) = 0.

б) Если > 0, то вероятность ркч{А, В) = 0 тогда и только

тогда, когда существует р£ 2, 1 < р < к, при котором 1р(А; 1) < ц

и йр(А,В; 1) = 0.

Отметим, что каждый элемент матрицы Р(А,В) - это рациональное число и, если, например, рд.?(А,В) = а/Ь - несократимая дробь, то ?(А,В) = йЬ,йе г.

В диссертации строются матрицы условных вероятностей, применение которых с формулой полной вероятности позволяет проводить более детальное исследование матриц из Л/г (А, В; 1). Строится также метод, обобщающий метод ядер и оболочек.

Для Л/г(А,В;с) ф 0 обозначим ?(А,В;с) = \Мг{А, В; с)|, Чрк(А,В;с,й) = |{Л'(А,В) = (ху) : Л'(А,В) € Мг(А,В;с), хрк = <*|, рц(А,В;с,Н) = (?г;(А, В; с, <1)/ц(А, В; с, с1) и

p¡j(A, В; с) — ^^ dpij(A, В;с, d), 1 < г < п, l<j<

m,

d= i

Определение 13. Матрица Р(А,В;с) = (p¡j(A, В; с)), 1 < г < п, 1 < j < 771, называется матрицей математических ожиданий для элементов случайных матриц из A/z(A,B;c) ф 0, А £ Z+, В £ Z™.

Теорема 21. Если A/z(A,B;c) ф 0, то Р(А,В;с) S М(А,В;с).

В диссертации рассматриваются различные примеры применений теорем 20 и 21.

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

Перенумеруем все элементы фундаментальных систем Е ' и En¡rn от 0 до 1_(теорема 16): Т ™ = {(Ё*, Ffc): 0 < fe < C£+m - 1},

Еп,т = {Nk(Ek,Fk): 0<k< Q+m - 1}.

Многогранники, являющиеся замкнутыми выпуклыми оболочками фундаментальных систем экстремальных пар векторов и экстремальных матриц Е ' и En¡m, соответственно обозначим L{n,m) и Л/(71, т):

L{n,m)= |(А,В) :(А,В)= £ fv,(ËbFfc)|, (20)

М(п,т) = : X =

где а*, 0 < & < С£+т — 1 - произвольные коэффициенты, удовлетворяющие условиям

«*>0, 0<*<С£+т-1, ^ = (22)

к—О

Рассмотрим также следующие образования:

Ь'(п,т) = {(А, В) : А £ В £ Я™ М{А, В; 1) ф 0}, М'(п, т) =

= {Х(А, В) : А £ В £ , Х(А, В) £ М(А, В; 1), М(А,В;1)^0}.

Основным утверждением параграфа является теорема, для доказательства которой применяется теорема Крейна-Мильмана о крайних точках.

Теорема 22. а) Ь(п,т) = Ь'(п,т), М(п,тп) = М'(п,т).

б) Все элементы (экстремальные пары векторов) из фундаментальной системы Е ' (и только они) являются вершинами многогранника Ь(п,т), заданного условиями (20) и (22).

в) Все элементы (экстремальные матрицы) из фундаментальной системы Еп^т (и только они) являются вершинами матричного многогранника М(п,т), заданными условиями (21) и (22).

В теореме 22 раскрывается смысл понятия экстремальности для пар векторов и матриц.

Определение 14. а) Многогранник Ь(п,т) называется фундаментальным транспортным многогранником (пар векторов).

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

Определение 15. Любая замкнутая транспортная модель, областью определения которой является множество равномерных матриц М(А,В), называется равномерной.

Так как любая пара векторов А £ В £ (упорядо-

ченность координат по невозрастанию не ограничивает общности), удовлетворяющая (1), с точностью до положительной константы

£ акНк( Е^М, (21)

к = О I

принадлежит L(n,m), то решение любой равномерной транспортной модели выражается (выпуклой) линейной комбинацией экстремальных матриц. Более того, любая транспортная матрица, размерность которой п х m, с точностью до перестановки строк и столбцов и с точностью до положительного коэффициента принадлежит 01 (71,771 ) = {А'(А, В) 6 М{А, В): (А, В) € L(n,m)}. Справедлива теорема.

Теорема '23. Пусть A G Л™, В G R™, М( А, В) ф 0, A'(A-iB) = (x¿j) ~ произвольная матрица из А-/(А,В) и а = max{j;,j : 1 < i < п, 1 < j < ?л} > 0. Тогда для любого ß, 0 < ß < п, имеет место X(Ä,B)/ß G 01 (71,771), где X(Ä,B) -матрица, образованная из матрицы А'(А,В) перестановкой строк и столбцов.

На основании, приведенных выше утверждений, в диссертации рассматриваются различные транспортные модели.

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

Список опубликованных работ

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

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

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

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

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

1990. №4. С. 180-188.

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

1991. №3. С. 118-155."

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 24.03.98 У .-печ.л. 2. TYipa>K 100 эко. Заказ jj^

Отпечатано в фото множительной мастерской Геологического факультета МГУ

A.A. Миронов

i, щ

-

ja

л

/

о

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

МИРОНОВ АНАТОЛИЙ АНАТОЛЬЕВИЧ МИНИМАКС В ТРАНСПОРТНЫХ МОДЕЛЯХ

Специальность:

05.13.18 — Теоретические основы математического моделирования, численные методы, комплексы программ

Диссертация на соискание ученой степени доктора физико-математических наук

Москва-1998 г.

ОГЛАВЛЕНИЕ

введение.....................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

матриц.......................................110

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

матриц...................................155

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

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

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

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

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

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

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

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

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

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

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

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

5.4. Экстремальные матрицы и матрицы вероятностей .... 198 § 6. Фундаментальные транспортные многогранники ....... 203

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

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

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

Глава 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]. Эти тождества связывают элементы матриц с координатами векторов и задают общие свойства всех матриц этого множества. Рассмотрение этих соотношений, как характеристических уравнений от неизвестных элементов матриц, позволяет в одних случаях строить матрицы с заданными свойствами, а в других — з