Исследование транспортных задач с помощью циклических множеств

• Автор: Заика, Виктор Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 88 c. : ил

ОГЛАВЛЕНИЕ п

ВВЕДЕШ®
Глава I. ЦИКЛИЧЕСКИЕ МНОЖЕСТВА И ЦИКЛЫ ПРОИЗВОЛЬНОЙ МАТРИЦЫ
§ І.І. Основные определения
§ 1.2. Сиьметрическая разность циклов
§ 1.3. Циклы, порожденные произвольным множеством элементов матрицы
§ 1.4. Циклы, порожденные множеством всех элементов
матрицы С -
§ 1.5. Циклы, порожденные опорным планом невырожденной
транспортной задачи
Глава 2. ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ ЦИКЛОВ МАТРИЦЫ. УСЛОВИЯ
ОПТИМАЛЬНОСТИ ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ
§ 2.Х. Я -характеристика и ^ -характеристика циклов,
порожденных множеством всех элементов матрицы. Использование этих характеристик при исследовании транспортных задач
§ 2.2. Я -характеристики циклов, порожденных произвольным множеством элементов матрицы. Условие оптимальности произвольного допустимого плана транспортной задачи
§ 2.3. Я. -характеристика циклов, порожденных опорным нераспадающимся планом. Условие оптимальности опорного нераспадающегося плана. Связь с методом
потенциалов
Глава 3. СПЕЦИАЛЬНЫЕ•КЛАССЫ ТРАНСПОРТНЫХ ЗАДАЧ, ЭФФЕКТИВНО РАЗРЕШИМЫЕ АЛГОРИТМАМИ, ОСНОВАННЫМИ НА ПОНЯТИИ ЦИКЛА МАТРИЦЫ

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

Как известно, транспортные задачи линейного программирования представляют собой математические модели важных практических задач, распространенных в различных сферах человеческой деятельности. Кроме задач о перевозках продуктов, к ним сводится много других (см., например, [9] , [ГО] , [29] , [32] ). Формулировка транспортной задачи и необходимые определения приведены в § 1.1 данной работы.
В настоящее время для решения транспортных задач разработано довольно много алгоритмов и, тем не менее, публикации по этой теме регулярно появляются в нашей стране и за рубежом. Объясняется это большим прикладным значением таких задач, а также тем, что их специфика открывает новые возможности алгоритмической реализации различных вычислительных методов. Основные методы решения этих задач систематически излагаются, например, в книгах [1] , [я] ,
[28] , [29] и в ряде других работ.
Предельная простота условий транспортной задачи позволяет на основе любого общего метода линейного программирования получить менее трудоемкий специальный алгоритм для решения этой задачи. Эффективность полученного алгоритма зависит, в основном, от того, насколько полно учтена специфика задачи.
Существующие конечные алгоритмы решения транспортной задачи в матричной постановке можно разделить на две основные группы. Первая группа алгоритмов основана на наиболее популярном методе линейного программирования - методе последовательного улучшения плана. Вторая группа алгоритмов базируется на идеях последовательного сокращения невязок.
Типичными представителями первой группы алгоритмов являются метод потенциалов, который был ггоедложен в работе Л.В.Канторовича

Из (2.1.4) и (2.1.5) получаем р р
ій&л=ііла ~ІЧі>
(2.1.6)
4=1 i=l
» | р -» а(р--г) - а[1пах(ргкс^)- к.^-]-цъ а-1.
Аналогичное утверждение справедливо и для циклов матрицы С].
Докажем, что для соответствующих циклов % и %. ранга £< К.
матриц б „ с 5 -характеристики равны, т.е.
Если цикл % не содержит элемента , то равенство $(%)*
= следует из построения матриц С и с . Если цикл
содержит элемент , а значит, и цикл 66 содержит элемент
С£ , то из определения соответствующих циклов X и “X следует, что либо С1Л^ € { С^, 5 . .. , с£гд } И 6 •,
либ° е Б&} И %.И46 {%*<’" *’
»С^ ]. Следовательно, переход от цикла %. к циклу %
изменяет /^-характеристику цикла на £ & . Учитывая неравенство
(2.1.6) и то, чтоО>3, получаем (К) ~ .
Остается показать, что среди соответствующих циклов ранга г-£Ч матриц С и С есть по крайней мере два таких цикла и 2Г , что #2:;* /Чгг; . В качестве таких циклов возьмем цикл £ % ={С1і}Сгі,-' • >ск+і>с„ , Сгг , Сг3)...,ге>1И1,Сл^}и соответствующий ему цикл £ = {См Аг,^’ • •>С&і,кіі>Сіі>Сі5>'*л>Сккн >£*41,і У
Из построения матриц С и С имеем
к-н к
= %я fi.CZ] ~ ’Щп ( У Сд ~
в то время как
^ (%)= ( У ,СІЛ. — У*,с±.і-ц ~ Ч-и ) ~
= = 1 Теорема доказана.
•4=/ -4
К-И
±-і і-і