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

• Автор: Соломон, Дмитрий Ильич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Кишинев
• Количество страниц: 146 c. : ил

В в е д е н и е

Глава I. ДЕКОМПОЗИЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

СПЕЦИАЛЬНОЙ СТРУКТУРЫ

§ 1.1. Задачи блочного программирования со связующими переменными и ограничениями

§ 1.2. Сведение дробно-линейных блочных задач к решению линейных задач блочного программирования

§ 1.3. Параметрический метод решения задач

дробно-линейного программирования

§ 1.4. Принцип разложения по ограничениям с применением метода обобщенного градиентного
спуска
§ 1.5. Принцип разложения по переменным с применением метода обобщенного градиентного
спуска
§ 1.6. Метод решения обобщенной задачи .дробнолинейного программирования
Глава 2. ДЕКОМПОЗИЦИОННЫЕ АЛГОРИТМЫ РЕШЕНИЯ
ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ТРАНСПОРТНОГО ТИПА
§ 2.1. Алгоритмы решения дробно-линейных транспортных задач
§ 2.2. Производственно-транспортные задачи с
дробно-линейным функционалом

§ 2.3. Алгоритмы решения распределительной задачи
дробно-линейного программирования
Глава 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ПЕРЕВОЗОЧНОГО ПРОЦЕССА
НА АВТОМОБИЛЬНОМ ТРАНСПОРТЕ
§ 3.1. Задачи оптимизации перевозочного процесса
на автомобильном транспорте
§ 3.2. Определение годового клиентурного плана грузовых перевозок автотранспортных предприятий
§ 3.3. Определение оптимальной структуры подвижного состава и его рациональное использование
§ 3.4. Задача маршрутизации автомобильных грузовых перевозок
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ

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

шения задачи (5.22)-(5.25) методом ОГС необходимо:
I. Решить задачу ДЛП р р
~ (5.2б)
^х3 - ^ > (5.27)
Х3 > О , п - <Гр (5.28)
параметрическим методом, при фиксированных Т] =УН
Пусть - оптимальное решение задачи:
С с3 ~ — _/л } Х3 —> т1ут_
4-6^5), хз >о,
а ^3 (ик) - оптимальное решение двойственной к ней задачи:
? С;-ТГк^-тис^,
уим *0,
где - значение параметра^ , для которого Х{ик)в|Х}1ик)3оптимальное решение задачи (5.26)-(5.28).
2. Определить значения обобщенного градиента по формуле
Сг (ик) *(£ - II АзХ} (Х7К))/2>(X (Пк), у ).
3. Найти новые значения
ик+1 - т ( о Р ик + к* £ № )), гДе к * - величина шага.
Следует заметить, что так как внутренняя задача (5.22)-(5.25) решается приближенно, то значения обобщенного градиента функции Ф(У) в точке У - У ^ определяется с некоторой погреш-