Введение к работе
Актуальность темы. Математическое моделирование является одним из основных методов исследования в различных областях знаний. Сфера применения транспортных моделей обширна. Сюда можно отнести проблемы, например, связанные с планированием производства и перевозок, с созданием вычислительных и информационных систем, с распределением ресурсов и запасов и т.д. Задачи транспортного типа составляют раздел теории математического программирования и исследования операций. Транспортные модели широко применяются в различных сферах деятельности. В терминах транспортной модели формулируется большое количество содержательных задач, например, задача назначения, распределительная задача, задача о максимальном потоке и т.д. В настоящее время разработаны эффективные методы для решения транспортных задач многих типов.
Основоположником теории транспортных проблем является Ф. Хичкок. Хотя и до него некоторые частные постановки исследовались специалистами по транспорту.
Здесь вводятся транспортные модели с критериями минимаксного типа. Смешанный критернй-минимакс имеет широкое применение в теории исследования операций. Этот критерий используется, например, в следующих областях: теория принятия решений, теория активных и иерархических систем, матричные игры.
Классические транспортные задачи в большей степени относятся к области линейного программирования и математический аппарат решения отих задач хорошо отработан и известен. В настоящее время для решения практических задач приходится часто привлекать нелинейные модели транспортного типа, причем, и здесь иногда применяется линейный аппарат при линейной аппроксимации функционалов. В общем случае на множестве матриц транспортного многогранника задана произвольная целевая функция. Поэтому к задачам транспортного типа возможно применение аппарата математического программирования в полном объеме. II в зависимости от целевой функции экстремальные транспортные задачи можно отнести, например, к выпуклому, динамическому, дискретному программированпям.
Настоящая диссертация посвящена замкнутым моделям транспортного типа с минимаксным критерием. Несколько десятилетий назад была поставлена классическая (линейная) транспортная задача, в которой были заданы пункты производства продукта и пункты по-
треблення этого продукта. Рассматривалась проблема перевозки продукта с минимальными затратами. Эта постановка повлекла за собой многочисленные распространения и обобщения.
В отличие от упомянутой постановки критерий минимума затрат заменяется на минимаксный. В частности, на классе матриц с неотрицательными элементами с заданными суммами элементов строк и столбцов ищется матрица, у которой наибольший элемент является минимальным. Простота постановки претендует на то, что эту задачу можно также считать классической. Смысл минимаксного критерия в этом случае можно интерпретировать следующим образом. Предположим, что время на перевозку продукта из пункта в пункт пропорционально количеству этого продукта. Тогда минимакс означает минимум по времени всех перевозок продукта в этой транспортной модели. Данная постановка также будет иметь большое число обобщений и распространений.
Указанный выше минимакс может быть найден методами линейного программирования. В диссертации приведен алгоритм вычисления минимакса, основанный в выборе наибольшего решения из некоторого множества линейных уравнений с одним неизвестным, количество которых не превосходит количества элементов рассматриваемых матриц. Теоретическое обоснование этого алгоритма и алгоритма вычисления элементов минимаксной матрицы заключено в построении характеристических уравнений, определяющих общие свойства всех матриц с заданным ограничением для элементов, которое потом и станет минимаксным. Метод распространен на случай целочисленных переменных. Построен эффективный (редукционный) алгоритм вычисления целочисленной матрицы, у которой наибольший элемент минимален. Минимаксные матрицы применены в теории транспортных многогранников. Установлен обширный класс транспортных матриц (равномерные матрицы), являющийся выпуклой оболочкой некоторого конечного множества минимальных (экстремальных) матриц, состоящих из нулей и единиц. Построены необходимые и достаточные условия в форме системы линейных соотношений, определяющие единственность минимаксной матрицы транспортного многогранника.
В диссертации представлен ряд конкретных моделей транспортного типа с минимаксным критерием. Все минимизируемые в диссертации функционалы, заданные на матрицах произвольного транспортного многогранника, можно описать следующим образом, разбив их
на три класса. К первому классу относятся три целевые функции: наибольший элемент матрицы, сумма наибольших элементов всех строк и сумма наибольших элементов всех столбцов. Суммы функционалов первого класса определяют целевые функции второго класса. Целевые функции третьего класса образуются суммированием функционалов на первого или второго классов по всем подматрицам транспортной матрицы.
Построена функция, зависящая от координат пары неотрицательных векторов и от неотрицательной константы, применяемая во многих исследованиях диссертации. В частности, для транспортного многогранника, неотрицательность этой функции (при упорядоченности координат первого вектора по невозрастанию) гарантирует непустое множество матриц этого многогранника с заданным ограничением сверху для всех элементов. Указанную функцию можно получить, опираясь на теорему Гейла, которая применяется в потоковых задачах на сетях и при исследованиях усеченных транспортных многогранников. Эта функция участвует в построении характеристических уравнении, указанных выше, которые определяют один из методов исследования матриц усеченных транспортных многогранников. Рассмотрение этих уравнений от неизвестных элементов матриц позволяет в одних случаях строить матрицы с заданными свойствами, а в других - запретить существование матриц с некоторыми условиями. В частности, эти уравнения в случае целочисленности матриц дают возможность (в сочетании с комбинаторными методами) оценить количество таких матриц.
В диссертации приведены два алгоритма построения транспортных матриц с общим ограничением сверху для всех элементов. Первый из них вычисляет вполне определенную матрицу (если заданный усеченный транспортный многогранник не является пустым). Применяя второй алгоритм, в зависимости от решения некоторых систем линейных соотношений, можно построить любую матрицу из указанных. Для произвольной пары векторов, определяющей непустой транспортный многогранник, и любого положительного ограничения построена система неравенств. Эта система не содержит избыточных неравенств и является критерием существования транспортной матрицы с заданным ограничением сверху для элементов. Сформулированные результаты распространены на случай целочисленных транспортных матриц.
Введено естественное понятие равномерности матрицы: матрица транспортного многогранника называется равномерной, если равным парам координат соответствуют равные элементы матрицы, а парам с неменьшими координатами соответствуют неменьшие значения элементов. Показано, что в некоторых из указанных моделях минимакс достигается на равномерных матрицах. Одним из основных результатов диссертации является следующий. Для произвольного транспортного многогранника приведен алгоритм построения минимаксной матрицы, называемой наследственно минимаксной, у которой любая подматрица является минимаксной матрицей своего транспортного многогранника. Указанная матрица обладает свойствами: она относится к классу равномерных, является единственной в любом транспортном многограннике и определяет минимум для всех рассматриваемых здесь задач транспортного типа.
Выше отражен один из возможных критериев минимаксного типа, определяемый на транспортных многогранниках. Приведем еще один пример. Функционалом на матрицах произвольного транспортного многогранника является сумма наибольших элементов всех подматриц транспортной матрицы. Здесь только отметим, что решение этой оптимизационной задачи единственно и достигается на наследственно минимаксной матрице. Отдельно рассматриваются пары целочисленных векторов, определяющие транспортные многогранники, и целочисленные матрицы. Специфика целочисленности позволяет привести более простой и наглядный алгоритм построения матриц с общим целочисленным ограничением сверху для элементов. Приведен алгоритм, определяющий любую такую матрицу заданного транспортного многогранника. Выделен случай для матриц, состоящих из нулевых и единичных элементов.
В диссертации большей частью рассматриваются транспортные многогранники, определяемые векторами с координатами, упорядоченными по невозрастанию, что не ограничивает общности. Большое внимание уделяется матрицам, состоящим из 0 и 1. Эти матрицы играют важную роль в комбинаторике, так как любую такую матрицы порядка п х т можно рассматривать как распределение п элементов по т множествам.
Выделен класс пар векторов с координатами, упорядоченными по невозрастанию, каждая из которых определяет единственную транспортную матрицу, состоящую из нулей и единиц. Указанные пары векторов и матрицы называются экстремальными. Показано, что ма-
тричные понятия экстремальность, равномерность и наследственная минимаксность' эквивалентны в классе матриц, каждый элемент которых равен нулю или единице (при упорядоченности координат по невозрастанию). Приведены и другие критерии экстремальности и вычислено количество экстремальных матриц (экстремальных пар векторов), имеющих общий порядок.
Используется алгебраическое понятие дистрибутивной решетки. Рассматриваются экстремальные пары векторов и экстремальные матрицы одного порядка. Для элементов указанных множеств введены отношения порядка и по две бинарные операции. Показано, что тогда множество экстремальных пар векторов и матриц образуют изоморфные дистрибутивные решетки. На множествах экстремальных пар векторов и экстремальных матриц одного порядка построены метрические функции. Относительно этих метрик между множествами экстремальных пар векторов и матриц существует естественная изоме-трия. Показано, что метрики согласованы с частичными порядками для элементов из множеств экстремальных матриц или пар векторов.
Указанные выше бинарные операции определяют метод (ядер и оболочек) исследования множеств транспортных матриц, состоящих из нулей и единиц, экстремальными матрицами. Для множества указанных матриц из одного транспортного многогранника определены и построены две матрицы, называемые ядром и оболочкой, удовлетворяющие условиям:
а) ядро и оболочка- экстремальные матрицы (связанные отноше
нием порядка);
б) ядро и оболочка "заключают" между собой любую рассматри
ваемую матрицу транспортного многогранника;
в) функция метрики от матриц - ядро и оболочка принимает наи
меньшее значение среди всех пар экстремальных матриц, для которых
справедливо второе условие;
г) относительно отношения порядка для матриц, ядро является
"наибольшей" экстремальной матрицей, содержащейся в каждой рас
сматриваемой, а оболочка - "наименьшей" экстремальной матрицей,
содержащей любую рассматриваемую.
Эти построения можно применить и для исследований множеств транспортных матриц, с непревышающими единицы элементами.
Построены вероятностные методы исследования множеств транспортных матриц, состоящих из нулей и единиц. Полученные результаты можно рассматривать, в частности, как относящиеся к мето-
дам исследования матричных множеств экстремальными матрицами. Объектом исследования являются множества транспортных матриц, состоящих из нулей и единиц, определяемых заданными парами векторов. Любая матрица указанного множества (которое, как очевидно, конечно) полагается случайной и равновероятной. Исходя из равномерного распределения, для произвольной допустимой пары индексов определяется (классическим образом) вероятность того, что соответствующий элемент случайной матрицы равен единице. Тем самым определяется матрица вероятностей матричного множества. Показано, что матрица вероятностей принадлежит тому же транспортному многограннику, что и рассматриваемые матрицы.
Все единичные и все положительные элементы матрицы вероятностей определяют, соответственно, ядро и оболочку заданного матричного множества. Вероятностные методы позволяют строить специальные экстремальные матрицы (обобщающие ядро и оболочку), что дает возможность более детального исследования матричных множеств. Также показана возможность применения вероятностных методов в исследовании множеств целочисленных транспортных матриц. Основным результатом для пар векторов (координаты упорядочены по невозрастанию), задающих области определения замкнутых транспортных моделей, является следующий, основанный на теореме Крейна-Мильмана о крайних точках. Выделена система, называемая фундаментальной, из С+т экстремальных пар п и ??1-коордпнатных векторов, обладающая следующими свойствами:
она содержит все те и только те пары из п и т-координатных векторов, каждая из которых определяет единственную транспортную матрицу, состоящую из нулей и единиц;
ее выпуклая оболочка содержит все пары векторов, определяющие транспортные матрицы с непревышающими единицы элементами;
все, принадлежащие ей, пары векторов являются (крайними) экстремальными для указанной выпуклой оболочки, называемой фундаментальным транспортным многогранником (пар векторов).
Из второго свойства следует, что любая пара векторов, задающая область определения произвольной замкнутой транспортной задачи, может рассматриваться, как принадлежащая фундаментальному транспортному многограннику, возможно, с точностью до некоторого коэффициента с, 0 < с < 1. Третье свойство объясняет понятие экстремальности для пар векторов.
Фундаментальной системе экстремальных пар из п и т-координатных векторов соответствует фундаментальная система экстремальных матриц порядка п х т, обладающая следующими свойствами:
ее выпуклая оболочка содержит все равномерные транспортные матрицы порядка п х т, элементы которых не превосходят единицы;
все С„+т ее матриц являются вершинами указанной выпуклой оболочки, называемой фундаментальным транспортным многогранником (равномерных матриц).
Из первого свойства следует, что любая равномерная транспортная матрица может рассматриваться, как принадлежащая фундаментальному транспортному многограннику, возможно, с точностью до коэффициента с, 0 < с < 1. Поэтому здесь заключен метод исследования произвольных равномерных матриц экстремальными. Отметим, что второе свойство содержит смысл, вкладываемый в понятие экстремальности для матриц.
Предложенные конструкции определяют методы исследований пар векторов (задающих области определения транспортных задач) и равномерных матриц экстремальными: любые равномерные матрицы, с непревышающими единицы элементами, и соответствующие им пары векторов можно представить в виде линейных комбинаций из экстремальных с неотрицательными коэффициентами, сумма которых равна единице. Отметим, что любая транспортная матрица с точностью до перестановки строк и столбцов и с точностью до положительного коэффициента является матрицей, определяемой парой векторов из фундаментального транспортного многогранника пар векторов.
Показаны возможные применения фундаментальных транспортных многогранников в моделях оптимизации.
Введено понятие равномерной транспортной модели, областью определения которой является множество равномерных матриц. Решение любой равномерной транспортной задачи выражается линейной комбинацией экстремальных матриц.
Заметим, что все результаты диссертации применимы в теории двудольных взвешенных графов и в задачах оптимизации на сетях, имеющих двудольную структуру.
Цели исследования. Основными целями исследования диссертационной работы являются:
построение замкнутых транспортных моделей с минимаксными критериями;
разработка алгоритмов вычисления элементов транспортных матриц с заданными условиями;
создание различных методов для исследования транспортных матриц и усеченных транспортных многогранников;
- построение критерия единственности минимаксной матрицы
транспортного многогранника;
построение наследственно минимаксной матрицы, минимизирующей многие транспортные задачи с минимаксным критерием;
применение теоремы Крейна-Мильмана о крайних точках в создании конечных множеств из стандартных (экстремальных) пар векторов и матриц, задающих области определения любой замкнутой транспортной модели;
определение транспортных моделей, в которых оптимальные решения выражаются (выпуклыми) линейными комбинациями экстремальных матриц. ,
Научная новизна. Важнейшими достижениями диссертационной работы являются следующие.
1. Для матриц произвольного транспортного многогранника с об
щим ограничением элементов сверху
а) построен критерий существования в форме несократимой си
стемы линейных неравенств;
б) представлен алгоритм вычисления элементов, которым может
быть построена'любая матрица из указанных;
в) представлен метод исследования множеств таких матриц харак
теристическими уравнениями.
-
Построены (в форме линейных ограничений) необходимые и достаточные условия единственности минимаксной матрицы транспортного многогранника.
-
Приведен алгоритм вычисления наследственно минимаксной матрицы (любая ее подматрица - минимаксна в соответствуюшем транспортном многограннике), некоторыми из свойств которой являются следующие:
а) любой транспортный многогранник содержит одну и только одну такую матрицу;
б) ота матрица является равномерной (т.е. равным парам коорди
нат соответствуют равные элементы, а парам с неменьшими коорди
натами соответствуют элементы с неменьшими значениями);
в) эта матрица определяет единственное решение в задаче мини
мизации суммы наибольших элементов всех подматриц транспортной
матрицы;
г) указанная в п. в) сумма вычислена для произвольной наслед
ственно минимаксной матрицы.
4. В случае целочисленности векторов, определяющих непустой
транспортный многогранник, представлен наглядный алгоритм по
строения целочисленной транспортной матрицы с общим ограниче
нием элементов сверху.
5. а) Приведены необходимые и достаточные условия, при которых
для пары векторов существует единственная транспортная матрица,
состоящая из нулей и единиц. При упорядоченности координат векто
ров по невозрастанию такие пары векторов и матрицы называются
экстремальными.
б) Если координаты векторов упорядочены по невозрастанию,
то в классе матриц, состоящих из нулевых и единичных элемен
тов, понятия "экстремальность", "наследственная минимаксность" и
"равномерность" - эквивалентны.
в) Подсчитано, что количество экстремальных матриц (пар векто
ров) порядка п х т равно С"+т.
г) Предложен метод исследования множеств матриц, состоящих из
нулей и единиц и принадлежащих одному транспортному многогран
нику, экстремальными матрицами (метод ядер и оболочек).
д) На множествах экстремальных пар векторов и матриц одного по
рядка введены по две бинарные операции, относительно которых ука
занные множества образуют изоморфные дистрибутивные решетки.
-
Построен вероятностный метод исследования множеств матриц из п. 5г. Показано, что этот метод обобщает метод ядер и оболочек.
-
Выпуклые оболочки L(n,m) и М(п,т) множеств экстремальных пар векторов н экстремальных матриц, имеющих порядок п х т, называются фундаментальными транспортными многогранниками (пар векторов и равномерных матриц). Смысл, вкладываемый в понятия экстремальность и фундаментальность, содержится в следующих утверждениях (координаты векторов, имеющих размерности п и т, упорядочены по невозрастанию):
а) каждые экстремальные пара векторов и матрица являются вер
шинами своих фундаментальных транспортных многогранников;
б) пара векторов принадлежит L(n, in) тогда и только тогда, ко
гда для нее существует транспортная матрица, элементы которой не
превосходят единицы; матрица принадлежит М{п,т) тогда и только
тогда, когда она является равномерной и ее элементы не превосходят
единицы;
в) каждая пара векторов, для которой существует транспортная
матрица, и каждая равномерная матрица с точностью до некоторого
коэффициента принадлежат L(n,m) и М{п,т)\
г) транспортная модель называется равномерной, если оптими
зируемый функционал рассматривается только на равномерных ма
трицах транспортного многогранника н решение любой равномерной
транспортной модели выражается матрицей, являющейся выпуклой
линейной комбинацией экстремальных матриц (вершин из М(п,т)),
возможно, с некоторым положительным коэффициентом;
д) любая транспортная матрица размерности п х т с точностью
до перестановки строк и столбцов и с точностью до положительного
коэффициента принадлежит множеству матриц 01 (ті, т) — {А'(А,В) :
X(A,B)eAf(A,B),(A,B),ei(n,ra)).
Теоретическая и практическая значимость работы состоит:
в применении результатов в областях математическое программирование и исследование операции;
ё'построении моделей транспортного типа с минимаксными критериями;
- в определении и построении наследственно минимаксной ма
трицы, минимизирующей многие транспортные модели с минимак
сным критерием;
в создании методов исследований транспортных многогранников и их матриц;
в представлении любой пары векторов, определяющей непустой транспортный многогранник, в форме (выпуклой) линейной комбинации экстремальных пар;
-' в созданий широкого класса (равномерных) матриц, каждая ii:j которых может быть представлена в форме (выпуклой) линейной комбинации экстремальных;
в построении специальных (равномерных) транспортных моделей, решения которых определяются (выпуклыми) линейными комбинациями экстремальных матриц;
в построении ограниченного множества матриц, содержащего с точностью до перестановки строк и столбцов и с точностью до положительного коэффициента любую транспортную матрицу.
Аппробация работы и публикации. Результаты диссертационной работы докладывались и обсуждались:
на семинаре кафедры "Прикладная математика" МГАТУ им. К.Э. Циолковского (руководители - проф. В.А. Кондратьев, проф. Л.А. Муравей) - ноябрь 1995 г., март 1997 г.;
на научно-исследовательском семинаре каф. "Общая топология и геометрия" МГУ им. М.В. Ломоносова (руководитель - В.В. Федор-чук) - ноябрь 1996 г.
По теме диссертации опубликовано 17 работ, среди которых - монография (в соавторстве) "Минимакс в транспортных задачах".
Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Главы разбиты на параграфы, параграфы - на подпараграфы. Общий объем работы - 241 страница, включая 6 страниц списка литературы, содержащего 95 наименований.