Исследование транспортных задач с помощью циклических множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

Глава I. ЦИКЛИЧЕСКИЕ МНОЖЕСТВА И ЦИКЛЫ ПРОИЗВОЛЬНОЙ МАТРИЦЫ

§ 1.1. Основные определения

§ 1.2. Симметрическая разность циклов

§ 1.3. Циклы, порожденные произвольным множеством элементов матрицы.

§ 1.4. Циклы, порожденные множеством всех элементов матрицы

§ 1.5. Циклы, порожденные опорным планом невырожденной транспортной задачи.

Глава 2. ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ ЦИКЛОВ МАТРИЦЫ. УСЛОВИЯ

ОПТИМАЛЬНОСТИ ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ

§ 2.1. Я. -характеристика и ¿> -характеристика циклов, порожденных множеством всех элементов матрицы. Использование этих характеристик при исследовании транспортных задач.

§ 2.2. Я, -характеристики циклов, порожденных произвольным множеством элементов матрицы. Условие оптимальности произвольного допустимого плана транспортной задачи.

§ 2.3. Я> -характеристика циклов, порожденных опорным нераспадающимся планом. Условие оптимальности опорного нераспадающегося плана. Связь с методом потенциалов.

Глава 3. СПЕЦИАЛЬНЫЕ • КЛАССЫ ТРАНСПОРТНЫХ ЗАДАЧ, ЭФФЕКТИВНО РАЗРЕШИМЫЕ АЛГОРИТМАМИ, ОСНОВАННЫМИ НА ПОНЯТИИ ЦИКЛА МАТРИЦЫ.

§ 3.1. Транспортные задачи со специальным видом матрицы стоимости перевозок

§ 3.2. Транспортные задачи со специальным видом векторов производства и потребления

Как известно, транспортные задачи линейного программирования представляют собой математические модели важных практических задач, распространенных в различных сферах человеческой деятельности. Кроме задач о перевозках продуктов, к ним сводится много других ( см., например, [9] , [ю] , [29] , [32] ). Формулировка транспортной задачи и необходимые определения приведены в § 1.1 данной работы.

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

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

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

Типичными представителями первой группы алгоритмов являются метод потенциалов, который был предложен в работе Л.В.Канторовича и М.К.Гавурина [ю] и несколько позже Дж. Данцигом [з?] , и метод Глейзала [~7] .

К алгоритмам второй группы относится венгерский метод [211 , 24] , [30] . К этой же группе относится и метод вычеркивающей нумерации Брудно [4] .

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

Под диаметром многогранника понимается наименьшее целое К такое, что между любой парой его вершин существует цепь, состоящая из вершин и ребер многогранника, которая содержит не более К ребер. Относительно диаметра транспортного многогранника порядка доказано [14] , что он не превосходит числа С точки зрения симплексного алгоритма, диаметр есть максимальное число итераций " наилучшего " алгоритма при " наихудшем " выборе начального плана.

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

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

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

Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций. Каждая итерация разбивается на два этапа. На первом этапе план Хкполученный в результате предыдущих итераций, цроверяется на оптимальность. Пусть ^ - множество -существенных элементов матрицы стоимости перевозок С = (сч Жданной транспортной задачи Ттп . Определим предварительные потенциалы: у Ь удовлетворяющие системе уравнений у ~ ^ для всех 6 (-гХк.

Теорема 0.1. Для оптимальности плана = ^задачи необходимо и достаточно существование чисел • • • , и

• • • , ^лг. таких, что -г^-^&Сс} для ¿ = . ,/я. ; /г - ^ - для ¿V е ,,,

Итак, если найденные предварительные потенциалы и , у =удовлетворяют теореме 0.1, то план !Х«опти-мальный, если же для некоторой пары индексов (¿,/7 V ^ V то план X, не оптимальный и в этом случае необходим переход ко второму этапу итерации. На втором этапе строится новый опорный план Ак^ > для которого значение транспортных расходов т п- ^ ц+) ^ 2 И хы ^ ^к

Г-'

Построение плана осуществляется следующим образом. Определим индексы 4> , /0 из условия и рассмотрим цикл матрицы

Z=/asif/ ос?, хи х.% где хСк) 6 f CcS^i TC-t}j \ и все элементы цикла ,кро

Ьь С Wi > ■ • • ■> ^LfJrJ ме CC- • > положительные. Пусть

Уменьшим все перевозки jz,- ■ t = ^ Z . P на a. а все neW* > /Q ревозки CCi j £ . p увежчим на ; В результате V получим новый опорный план J\k+i ( ¿J Л Для которого значение транспортных расходов

L, = U+ & (I Cku -1 ).

7? =/

Заметим, что здесь 2 = . , С^ , С^,. •• , j -цикл, составленный из элементов матрицы С • При этом C^j 6 J. . . ? Cipj } и все элементы цикла X , кроме С^ , являются ЗС -существенными элементами матрицы С . Так как Хк не оптимальный план, то ~ С ^ О 9 следовательно, ( см. [9] с. 116 или § 2.3 настоящей работы ) число Р

Cl\,- У Г.; <0

Им

Мь ? , &Л

Отсюда следует, что ^ •

Анализ построения плана показывает, что итерация метода потенциалов определяется некоторым множеством циклов матрицы С . Это множество циклов задается множеством X"-существенных

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

Как самостоятельный объект циклические множества матрицы, важнейшим частным случаем которых являются циклы, впервые исследо-валисн С.М.Швартиным в работе [*34] . Основное внимание в этой работе уделено изучению мощностных характеристик множества циклов матрицы. В качестве приложения понятия цикла к исследованию транспортных задач доказан, в несколько другой формулировке, следующий критерий оптимальности плана транспортной задачи.

Теорема 0.2. Пусть Чтп транспортная задача, для которой С = fc^tn - матрица стоимости перевозок, а X ~ ^^/^»и" Д°~ пустимый план, и пусть Сх ~ множество всех -существенных элементов матрицы С . План X оптимален тогда и только тогда, когда для любого цикла Z матрицы С , порожденного множеством , выполняется условие R.(2) 0 , 0 том, что исследования циклов матрицы могут дать интересные результаты в исследовании и решении транспортных задач, говорят результаты, связанные с возможностями понижения размерности задачи, полученные в работах ¡16] , [20] , ¡22] , [*3б] . Заметим, что в этих работах авторы либо не вводят понятия цикла матрицы либо называют его другим именем " петля " замкнутая цепь что, естественно, не влияет на существо вопроса.

С точки зрения циклов матрицы основная идея, на которой основаны результаты перечисленных работ, заключается в следующем. Пусть - транспортная задача, для которой С" (Q/J - матрица стоимости перевозок, ( > • • • > ^*- вектор производства и a,. ¿j - вектор потребления. Рассмотрим какую - либо пару строк матрицы С^ с номерами ¿у и <4 . Пусть на множестве номеров столбцов матрицы G определен порядок последовательностью J/ — > jn 1 Для которой выполняется условие: для любого циквыполняется условие Ц. (2) ~ + - - С^ ~ 0

Заметим, что для этого достаточно, чтобы выполнялись неравенства г - Г. . г. С • - — С- • ^ ¿г С; ! - С- •

Тогда, если существует число ^ , удовлетворяющее неравенствам то для задачи 1тп существует оптимальный план ^ I в котором перевозки ~ ^ для ^ ~ ••^•В противном случае, исходя из условия баланса, легко можно указать цикл ранга два, который будет противоречить условию оптимальности плана, сформулированного в теореме 0.2. Рассматривая всевозможные пары строк с номерами и ^ , ^ - 3, . ■ - у 9 в некоторых случаях можно получить план , в котором для некоторого / перевозки для " ^ • Я^/ I Ф ¿£ Тогда, полагая в плане X перевозку ^¿^ = ^ , можно пункт потребления исключить из рассмотрения и перейти к задаче меньшей размерности.

В случае задачи Тга или Тт этим методом аналитически получается оптимальный план [з5] • Заметим, что все эти результаты получаются из исследований только циклов ранга два.

Понятие цикла матрицы и его ^ -характеристики использовалось в работе [б] ( результат Л.В.Командиной ) для нахождения условий оптимальности плана транспортной задачи с дополнительными ограничениями. Эти условия аналогичны условиям, сформулированным в теореме 0.1.

В задачах комбинаторной оптимизации использование циклов матрицы позволило выделить специальный класс матриц, для которых задача о назначениях допускает более простое решение. Эти результаты получены в работах [п] , [12] , [13^ . Алгоритм определения принадлежности произвольной матрицы к этому специальному виду сформулирован в работе •

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

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

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

1. Множество 2(0 всех Циклов матрицы С •

2. Множество 2Г (М) циклов матрицы С , порожденных произвольным множеством М элементов этой матрицы.

3. Множество 2 Циклов матрицы Са » порожденных множеством всех X -существенных элементов матрицы , где X есть некоторый опорный план невырожденной транспортной задачи, для которой С есть матрица стоимости перевозок.

Целью исследования является:

1. Построение для каждого из указанных множеств базисного множества циклов такого, чтобы любой цикл из рассматриваемого множества был представим в виде симметрической разности базисных цикие Я -характеристики этого цикла сводилось бы к 2. -характеристик базисных циклов.

2. Нахождение на основе полученных представлений {ч. -характеристик специальных условий оптимальности плана транспортной задачи.

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

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

ЛОВ и БЫЧИСЛ вычислению циклом. Для указанных выше множеств циклов матрицы строятся базисные множества циклов. Эти базисные множества для множеств И. (С)и ад строятся аналогично построению фундаментального множества циклов для циклов графа (см. [з] , [25] , [зб] ).

Во второй главе рассматриваются £ - и -характеристики циклов. Доказывается, что ^ -характеристика произвольного цикла из множества КС) представима в виде линейной комбинации

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

Для множества КМ) показывается, что ^-характеристика произвольного цикла из этого множества представима в виде суммы

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

Аналогично вычисляется Я. -характеристика любого цикла из множества (Сх) . Отсюда выводятся необходимые и достаточные условия оптимальности плана транспортной задачи и устанавливается связь полученных условий с уславиями оптимальности плана в методе потенциалов.

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

Первый класс содержит транспортные задачи, матрицу стоимости перевозок которых с помощью перестановки строк и столбцов можно привести к такому виду, что для любого цикла «З^^д , , где р £ Ц. , С^ ^ | , выполняется условие К. (%) ^ О . Доказывается, что после соответствующей перенумерации пунктов производства и потребления план, построенный по методу " северо-западного уг-1ла',' будет оптимальным планом задачи из рассматриваемого класса. В

Гэтот класс, в частности, входят задачи с матрицами, аналогичными I матрицам,введенным для задач комбинаторной оптимизации Д.А. Супру-ненко [27] , а также В.Я.Бурдюком и В.Н.Трофимовым [5] .

Второй класс задач содержит задачи, векторы производства (С1{) .} и потребления ., Зп,) которых удовлетворяют условию: для любого £ , . , ггь?

Для третьего класса задач векторы производства и потребления удовлетворяют условию п-г,

-х

Для задач второго и третьего класса, на основе рассмотрения К- -характеристик циклов ранга два и три матрицы стоимости перевозок, строятся алгоритмы нахождения оптимального плана с тру-до емко стью 0 (т п)я

На защиту выносятся следующие результаты диссертационной работы:

1. Для множеств

2 (С), Z ( М) ,2 (СХ) циклов матрищ С найдены базисные множества циклов, позволяющие свести вычисление -характеристик циклов из указанных множеств к вычислению Я- -характеристик базисных циклов.

2. На основе представления ^ -характеристик циклов через ¡1- -характеристики базисных циклов найдены условия оптимальности плана транспортной задачи.

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

1. Аде ль сон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы. - М.: Наука, 1975. - 119 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

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

4. Брудно А.Л. Решение транспортной задачи методом вычеркивающей нумерации. В кн.: Применение ЦВМ в экономике. - М.: АН СССР, 1962, с. 17-38.

5. Бурдюк В.Я., Трофимов В.Н; Обобщение результатов Гильморе и Гомори по решению задачи коммивояжера. Изв. АН СССР Техн. ки-берн., 1976, №3, с. 16-32.

6. Гкбасов Р., Кириллова Ф.М. Методы линейного программирования, ч.2. Транспортные задачи. Минск, 1978. - 239 с.

7. Глейзал А. Алгоритм для решения проблемы транспортировки.- Математика, т.2, И, 1958, с. 131-137.

8. Голынтейн Е.Г. Транспортная задача и ее обобщения. В сб.: Методы и алгоритмы решения транспортной задачи. - М.: Гос-статиздат, 1963, с. 3-34.

9. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. г,382 с;!10; Данциг Дж.Б. Линейное программирование, его обобщения и применения, М.: Прогресс, 1966. - 600 с.

10. Дейнеко В. Г.- Специальный случай задачи о назначениях.В сб.: Исследования по современным проблемам суммирования и приближения функций и их цриложениям. Днепропетровск, ДГУ, 1979, с. 80-83.

11. Дейнеко В.Г. Некоторые методы и алгоритмы решения задач комбинаторной оптимизации. Дис. . канд. физ.-мат. наук.- Днепропетровск, 1981. 144 с.

12. Емеличев В.А., Кравцов М.К. Некоторые вопросы понижения размерности транспортной задачи. Изв. АН БССР сер. физ.-мат. наук, 1976, №, с. 130-131.

13. Заика В.В., Швартин С.М. Числовые характеристики циклов матрицы. Ж. вычисл. матем. и матем. физ., 1981, т.21, №6,с. 1423-1429.

14. Заика В.В., Швартин С.М. 0 циклах, порождаемых опорными планами транспортной задачи. Ж. вычисл. матем. и матем. физ., 1982, т.22, И, с. 78-89.

15. Канторович Л.В., Гавурин М.К. Применение математических методов в вопросах анализа грузопотоков. В кн.: Проблемы повышения эффективности работы транспорта. - М.: АН СССР, 1949,с.110-138.

16. Кравцов М.К. К вопросу понижения размерности транспортной задачи. Изв. АН БССР, сер. физ.-мат. наук, 1973, №2, с. 59-62.

17. Кун Г. Венгерский метод решения задачи о назначениях.- В кн.: Методы и алгоритмы решения транспортной задачи. М.: Гос-статиздат, 1963, с. 35-52.

18. Курцевич К.А., Кравцов М.К. Метод понижения размерности транспортной задачи линейного программирования. В кн.: Математические методы решения экономических задач. - М.: Наука, 1974.

19. Лурье А.Л. Алгоритм решения транспортной задачи путем приближения условно-оптимальными планами. Ж. вычисл. матем. иматем. физ., 1961, т.1, Р7, с, 151-160.

20. Манкрес Д. Алгоритм решения задачи выбора и транспортной задачи. В кн.: Методы и алгоритмы решения транспортных задач. - М. : Госстатиздат, 1963, с. 73-79.

21. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

22. Романовский И.В. Алгоритмы решения экстремальных задач.- М.: Наука, 1977. 352 с.

23. Супруненко Д.А. 0 значениях линейной формы на множестве подстановок. Кибернетика, 1968, №2, с. 59-63.

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

25. Форд Л., шалкерсон Д; Потоки в сетях. М.: Мир, 1966.- 276 с.

26. Форд Л., Фалкерсон Д. Решение транспортной задачи. В сб.: Методы и алгоритмы решения транспортной задачи. - М.: Госстатиздат, 1963, с. 61-72.

27. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

28. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. 520 с.;

29. Швартин С.М. Исследование устойчивости транспортных задач. Я. вычисл. матем. и матем. физ., 1978, т.18, №1,с.235-240.

30. Швартин С.М. О циклических множествах. Ж. вычисл. матем. и матем. физ., 1979, т.19, №1, с. 189-203.

31. Adolphoun D. L., Thomas G. N. Lj^ar time algorithm for a 2 x n transportation problem. SIAM I. Сотр. 1977, 6, N3,p. 481 486.

32. Intrator I., Engelberg A. Sensitivity analysis as a means of redusing the clemensionality of a certiain class oftransportation 'problems. Naval. Res. Log. Quart., 1980, 27, N2, p. 297-313.

33. Dantzig G.B. Application of the simplex method to a transportation problem.-Activity analysis of production and allocation, ed, T.C.Koopmans, Cowles Commission Monograph, 13, Wiley, New York, 1951» p. 359-373.

34. Hitchcock F.L. Distribution of a product from several saurces to numerous localities, I. Math. Phus. 1941, N20, p. 224- 230.