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

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

Оглавление
ВВЕДЕНИЕ

Общая характеристика работы

Актуальность темы

Цели и задачи исследования

Научная новизна

Методы исследования

Практическая ценность

Апробация
Публикации

Структура работы

Результаты, выносимые на защиту
ГЛАВА 1. ОСНОВНЫЕ КОНСТРУКЦИИ ИТЕРАТИВНОГО
ПРОЦЕССА
1.1 Предварительные рассмотрения
Задача развития сети
Задача о ранце с лестничной структурой ограничений
1.2 Описание алгоритма
Первый этап решения
Второй этап решения
Третий этап решения
1.3 Пример 1.
1.4 Обобщённые поставщики и потребители
1.5 Пример 1.
1.6 Вычислительные тесты
ГЛАВА 2. ПРИМЕНЕНИЕ К ЗАДАЧАМ ТРАНСПОРТНОГО ТИПА
2.1 Задача с ограниченными пропускными способностями
Пример 2.

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

Введение
Общая характеристика работы
Уже прошло более 70 лет, как появились первые работы [1,2], где была поставлена и формализована транспортная задача. Впоследствии среди решённых практических задач линейного программирования более 80% относились к транспортной задаче и её модификациям, см. например [3-24]. Центральным подходом в решении является метод улучшения плана (симплекс-метод линейного программирования). Специфика транспортной задачи предполагает рассмотрение таблицы, где в клетках записываются коэффициенты целевой функции и неизвестные количества перевозимой продукции из пунктов производства в пункты потребления. Переход от одного допустимого (базисного) решения к другому осуществляется с помощью построения цикла, в котором перемещается продукт, так что одна из клеток обнуляется. В результате осуществляется переход к базисному решению с меньшим значением функционала. Весьма распространённым в этом направлении является так называемый метод потенциалов, где переход к новому опорному решению осуществляется с помощью двойственных соотношений, которые для транспортной задачи имеют специфический вид. Широкое применение в транспортных постановках получил так называемый венгерский метод. В его основе лежит построение максимальных потоков через транспортную сеть с частично разрешёнными коммуникациями и последующее сокращение невязок. Конструкции упомянутых подходов можно найти, например в [25, 26]. Известны также другие специальные методы. Так, в [27] предлагается применить двухуровневую технику метода декомпозиции Данцига-Вулфа для классической транспортной задачи. При этом исходная матрица условий разбивается по горизонтали таким образом, что верхний уровень решает независимые задачи с одним ограничением.
В данной работе предлагается метод решения задач транспортного типа, где последовательно решаются двумерные задачи с одной связывающей

В оптимальном решении этой задачи уп — хп + х]2 + х21 + х22 = 55 , ^21 = 0 .
У 22 = Х33 + Х34 + Х43 + Х44 + Х53 + Х55 = 60 ‘
На четвёртом шаге решается задача с ограничениями У 21 + У22 =
У12 У.22 — ^
В оптимальном решении этой задачи У12 = х1з + хы + х24 ~ 1 ^, Ун ~ ^ >
У 22 = Х33 + Х35 + Х43 + Х44 + Х54 + Х55 = 60‘
Заметим, что коэффициенты при переменных в целевых функциях одномерных задач во втором итеративном процессе не менялись, тем самым второй итеративный процесс окончен. Убедившись, что допустимое решение исходной задачи может быть реализовано с использованием лишь линий, участвующих в ограничениях, сформированных на первом и втором итеративных процессах, можем приступить к формированию оптимального решения. Оптимальное решение исходной транспортной задачи формируется по итогам первого и второго итеративных процессов процедурой получения допустимого решения исходной задачи:
хп + Х12 + Хп + Хн - 40 5 Х21 + х22 + х24 = 30, х33 + х35 = 20,
х43 -ь х44 15 х54 х33 25 Х|] у х2| — 35 Х|2 х22 —- 20,

х,3+х33+х4з =30 Х14 + х24 + х44 + х54 = 25 х35+х55 = 20,
Х11 Х12 Х21 Х22 =55 Х^ 3 Х14 ~ Х24 ^ ^
Х33 Х35 Х43 Х44 Х54 Х55 =
Окончательно имеем: