Декомпозиционные методы решения задач дробно-линейного программирования

-2-
СОДЕРКАНИЕ
стр.
В в е д е н и е .......'................................. 4
Глава I. ДЕКОМПОЗИЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
СПЕЦИАЛЬНОЙ СТРУКТУРЫ ................... 17
§ 1.1. Задачи блочного программирования со связующими переменными и ограничениями ............... 17
§ 1,2. Сведение дробно-линейных блочных задач к решению линейных задач блочного программирования ..................................... 20
§ 1.3. Параметрический метод решения задач
дробно-линейного программирования ......... 24
§ 1.4. Принцип разложения по ограничениям с применением метода обобщенного градиентного
спуска .................................... 31
§ 1.5. Принцип разложения по переменным с применением метода обобщенного градиентного
спуска..................................... 39
§ 1.6. Метод решения обобщенной задачи дробнолинейного программирования ........................ 51
Глава 2. ДЕКОМПОЗИЦИОННЫЕ АЛГОРИТМЫ РЕШЕНИЯ
ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ТРАНСПОРТНОГО ТИПА....................... 55
§ 2.1. Алгоритмы решения дробно-линейных транспортных задач...................................... 55
§ 2.2. Производственно-транспортные задачи с
дробно-линейным функционалом .............. 71
-3-
§ 2.3. Алгоритмы решения распределительной задачи
дробно-линейного программирования .............. 82
Глава 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ПЕРЕВОЗОЧНОГО ПРОЦЕССА
НА АВТОМОБИЛЬНОМ ТРАНСПОРТЕ.................. 89
§ 3.1. Задачи оптимизации перевозочного процесса
на автомобильном транспорте ................... 89
§ 3.2. Определение годового клиентурного плана грузовых перевозок автотранспортных предприятий ................................................ 92
§ 3.3. Определение оптимальной структуры подвижного состава и его рациональное использование .................................................. 99
§ 3.4. Задача марпрутизации автомобильных грузовых перевозок ......................................... 105
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ................................ 114
ЦИТИРОВАННАЯ ЛИТЕРАТУРА..................................... 116
ПРИЛОЖЕНИЯ ................................................. 129
-4-
ВВЕДЕНИЕ
Значительное расширение областей применения вычислительной техники, более детальное описание моделируемых объектов и более высококачественный уровень использования экономико-математических моделей приводит к необходимости решения задач большой размерности. Поэтому проблема исследования и разработки эффективных методов решения подобных задач является достаточно актуальной и перспективной.
В практических задачах большой размерности матрицы условий, как правило, являются слабо заполненными и обладают специальной структурой, т.е. ненулевые элементы не разбросаны в них как попало, а локализованы в отдельных блоках, в соответствии с природой задачи и характером связей между ее переменными. Поэтому необходимо построить эффективные методы решения задач большой размерности, учитывающие структуру матрицы системы ограничений.
Одним из наиболее распространенных способов решения задач большой размерности, в котором эффективным образом учитывается структура матрицы ограничений, является применение декомпозиционных методов. Использование декомпозиционных методов позволяет свести решение задачи большой размерности к решению последовательности вспомогательных задач, каждая из которых в определенном смысле проще исходной.
В настоящее время получен ряд теоретических и практических результатов по разработке и использованию декомпозиционных методов решения задач математического программирования
-5-
большой размерности [13, 14, 16, 22, 26, 29, 44, 46, 56, 74,
81, 93 , 99, 109, ПО].
Одним из наиболее распространенных: методов является принцип декомпозиции Данцига-Вулфа [96], на основе которого разработаны вычислительные алгоритмы решения блочных задач линейного [26, 90, 92, 120], дробно-линейного [91, 100, 101, 104, 106] и нелинейного [26, 46, III, 112, 114] программирования. Этот метод позволяет свести исходную задачу к решению вспомогательной (координирующей) задачи некоторым общим алгоритмом, на каждом шаге которого решаются подзадачи для каждого блока в отдельности.
Другим декомпозиционным методом, который эффективно используется в последнее время для решения больших задач специальной структуры, является принцип разложения по переменным и ограничениям с применением метода обобщенного градиентного спуска (0ГС) [83]. Такой метод, построенный на основе функции Лагранжа и теории двойственности, позволяет свести решение исходной задачи к решению задачи безусловной оптимизации выпуклой или вогнутой функции (как правило недифференцируемой). Для решения задачи безусловной оптимизации используется метод 0ГС, на каждом шаге которого эффективно решается задача определения значений обобщенного градиента. На основе принципа разложения по переменным и ограничениям разработаны алгоритмы решения задач линейного и выпуклого программирования блочной структуры [I, 2, 17, 81-83, 85, 87, 88] и ряда практических задач [II,
78, 84, 89]..
В диссертационной работе эти методы обобщаются на задачи дробно-линейного программирования (ДЛП) большой размерности.
Необходимость разработки декомпозиционных методов решения задач ДЛП объясняется наличием математических моделей с дроб-
-6-
но-линейным функционалом [6, 7, 9, 34, 41, 42, 75, 77, 80], часто встречающихся в практике планирования и управления народным хозяйством. В таких моделях в качестве критерия оптимальности используются некоторые удельные технико-экономические показатели,такие, как себестоимость конечной продукции, фондоемкость, фондоотдача, рентабельность и др. Использование таких показателей приводит к необходимости решения общей задачи ДЛП, в которой требуется минимизировать или максимизировать отношение двух линейных функционалов при линейных ограничениях.
Для решения общей задачи ДЛП разработаны различные алгоритмы [10, 19, 22, 40, 73, 75, 79, 95, 97, 98, 100, 102, 107, 115, 116, 119, 121]. Эти алгоритмы могут быть разделены на две группы. К первой группе относятся алгоритмы, в которых симплекс-метод модифицируется для решения задач ДЛП [19, 79, 98, 100, 102, 107, Пб]. Ко второй группе относятся алгоритмы, в которых задача ДЛП сводится к решению одной, двух или конечной последовательности линейных задач. В [10, 40, 95, 121] с помощью введения дополнительной переменной и проведения соответствующего преобразования системы ограничений задача ДЛП сводится к решению одной или двух (в зависимости от знака знаменателя) задач линейного программирования. В [22, 97] задача ДЛП сводится к анализу и решению некоторой задачи параметрического линейного программирования на множестве исходных ограничений.
Для решения задач ДЛП специальной структуры разработаны соответствующие алгоритмы, в которых учитывается структура системы ограничений. Для решения задач блочной структуры в [91, 100, 105] приводятся алгоритмы, основанные на принципе декомпозиции Данцига-Вулфа, а в [15 ] - на методе параметри-
ческой декомпозиции. В [24, 75, 79, 101] рассматриваются задачи ДЛП транспортного типа, для решения которых приводятся алгоритмы метода потенциалов и принципа декомпозиции Данцига-Вулфа. Для решения задач размещения с дробными функционалами в [33, 45, 76] приводятся приближенные алгоритмы метода последовательных расчетов. В [7, 42, 49] рассматриваются дробно-линейные целочисленные задачи специальной структуры, для решения которых приводятся алгоритмы метода последовательного анализа вариантов.
Для многих из алгоритмов решения задач ДЛП не разработано соответствующее программное обеспечение, что не позволяет применять их при решении практических задач. Поэтому необходимо разработать такие декомпозиционные методы и алгоритмы, с помощью которых можно было бы решать дробно-линейные задачи, используя при этом имеющееся программное обеспечение, предназначенное для решения линейных задач.
Диссертационная работа посвящена вопросам исследования и разработки эффективных декомпозиционных методов решения задач ДЛП блочно-диагональной или специальной структуры большой размерности.
В работе рассматриваются:
- задачи ДЛП блочно-диагональной структуры со связующими ограничениями и связующими переменными;
- обобщенные задачи ДЛП;
- дробно-линейные транспортные задачи;
- задачи размещения с дробно-линейным функционалом.
Исследования, проводимые в диссертационной работе, охватывают не только разработку декомпозиционных методов и общих схем решения вышеуказанных задач, но и разработку соответствующих программ на ЭВМ с целью их применения при решении практи-
-8-
ческих задач оптимизации перевозочного процесса на автомобильном транспорте.
Диссертационная работа состоит из введения, трех глав, приложения и списка цитированной литературы.
В первой главе рассматриваются вопросы разработки декомпозиционных методов решения задач ДЛП блочно-диагональной структурі, основанные на принципе Данцига-Вулфа и схемах разложения по ограничениям и переменным с применением метода ОГС.
В § І.І приводится процедура преобразования задач математического программирования следующего вида:
Р(Хл,Хг>...,ХР1^) -----------> Упік
9ч(Хч) + Мы>
^ г. С Ха,") + На(.У) і £>г,
2рСУ) + 4<-у> &£р
Предложенная процедура состоит в том, что вводятся дополнительные переменные У] - V ), после чего исходная
задача преобразуется в эквивалентную задачу:
Р (* * > х г, ) —>• ^
Уз - У? а о , і = ,
5 л ( У Л ) + К Л С У 1 ) £ $>Л у
ЗгСХгЛ + Ы^г)
% *
Последняя задача имеет блочно-диагональную структуру со связующими ограничениями, удобную для применения декомпозиционных методов. Далее на примере задач линейного и дробно-линейного программирования показывается эффективность предложен-
-9-
ной процедуры.
В § 1.2 приводится метод сведения задач ДЛП блочно-диагональной структуры к линейной задаче аналогичной структуры. Для этого используются предложенная в § 1.1 процедура преобразования и метод "линеаризации", т.е. метод сведения дробно-линейной задачи к линейной. Предложенный метод позволяет использовать программное обеспечение линейных задач для решения дробно-линейных задач блочно-диагональной структуры.
Третий параграф первой главы посвящен вопросам модификации параметрического метода [22, 97] решения задач ДЛП, в котором дробно-линейная задача сводится к анализу и решению параметрической задачи линейного программирования. Предложенный алгоритм состоит в том, что решается конечная последовательность задач линейного программирования при соответствующем изменении значений коэффициентов целевой функции до тех пор, пока не совпадут значения дробно-линейного функционала на двух последовательных оптимальных планах линейной задачи. Его эффективность достигается за счет возможности использования программного обеспечения линейных задач, а также за счет сепарабельности линейного функционала при решении дробно-линейных задач блочно-диагональной структуры.
В § 1.4 исследуются вопросы применения схемы разложения по ограничениям при решении задач ДЛП. Для задачи минимизации дробно-линейного функционала
П
при ограничениях
о . ----
^ 7 с* ъ*»*,
строится функция Лагранжа
1(Х.и) = [С(х>* I “I II )]/ -2(Х)
и рассматривается задача максимизации кусочно-линейной вогнутой функции
1*си) *Г.1я">1-(х>ХП
Для максимизации функции 1_ Ш) используется метод ОГС, на каждой итерации которого значения обобщенного градиента определяются по формуле
= Т. *?№)]/2>(х*(тл) ,
где Х*(Ц0 - решение задачи Ьт 1.(Х}и) при фиксированных зна-чениях и-и .
Далее подобная схема используется для решения задач ДЛП блочно-диагональной структуры.
В § 1.5 приводятся алгоритмы решения задач ДЛП, построенные на базе схемы разложения по переменным с использованием метода ОГС. Сначала излагается принцип разложения по переменным для общей задачи дробно-выпуклого программирования, в которой переменные условно разбиты на две группы. Обосновываются формулы определения значений обобщенного градиента дробного функционала, позволяющие применить метод ОГС для нахождения минимума строго кваэивыпуклых функций. Приводится итерационный алгоритм метода ОГС решения задач дробно-выпуклого программирования.
-II-
Далее для задач ДЛП приводятся подробные алгоритмы принципа разложения по переменным. Для решения задачи ДЛП блочнодиагональной структуры со связующими ограничениями и переменными приводится двухуровневый алгоритм, в котором вначале применяется принцип разложения по переменным, а потом - принцип разложения по ограничениям.
Шестой параграф первой главы посвящен исследованию задачи обобщенного ДЛП вида: ^
21 Cj ocj Р(Х) - -^1 —> min
X dj X.J
iCajXj Ъ О tn,
( > dj ) € Sj , j ~ -<>n .
Для решения этой задачи приводится метод, построенный на базе принципа декомпозиции Данцига-Вулфа.
Во второй главе рассматриваются вопросы разработки эффективных алгоритмов решения задач ДЛП транспортного типа большой размерности. Для решения таких задач приводятся алгоритмы, основанные на методах вектора спада, покоординатного спуска, ОГС и параметрического программирования. Для большинства из приведенных алгоритмов разработано программное обеспечение и проведены экспериментальные расчеты.
В § 2.1 рассматриваются задачи ДЛП транспортного типа.
Для решения дробно-линейной транспортной задачи разработаны алгоритмы параметрического метода и метода ОГС. Приводятся результаты экспериментальных расчетов, из которых следует, что по алгоритму параметрического метода для нахождения оптималь-
-12-
ного решения дробно-линейной транспортной задачи необходимо решать в среднем по четыре линейные транспортные задачи. Метод ОГС эффективнее использовать при решении дробно-линейных транспортных задач, когда количество потребителей значительно превосходит количество поставщиков.
Для решения дробно-линейных транспортных задач, в которых отсутствуют ограничения поставки или потребления, приводятся алгоритмы, основанные на методе покоординатного спуска и на параметрическом методе.
Далее рассматривается одно из возможных обобщений транспортных задач для случая, когда функционал является суммой линейной и дробно-линейной функций, а именно:- минимизировать функционал
при ограничениях транспортного типа.
В § 2.2 рассматривается производственно-транспортные задачи, в которых необходимо минимизировать дробно-линейный фун-
Для решения этой задачи приводится приближенный алгоритм с использованием штрафных функций
кционал
при ограничениях
X - а1 , I
>
X ^ » з = 1>п >
т