Итеративный алгоритм для класса оптимизационных задач транспортного типа тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Кузовлев, Дмитрий Игоревич

• Кузовлев, Дмитрий Игоревич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кузовлев, Дмитрий Игоревич

Оглавление

ВВЕДЕНИЕ

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

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

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

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

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

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

Апробация

Публикации

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

Результаты, выносимые на защиту

ГЛАВА 1. ОСНОВНЫЕ КОНСТРУКЦИИ ИТЕРАТИВНОГО

ПРОЦЕССА

1.1 Предварительные рассмотрения

Задача развития сети

Задача о ранце с лестничной структурой ограничений

1.2 Описание алгоритма

Первый этап решения

Второй этап решения

Третий этап решения

1.3 Пример 1.3

1.4 Обобщённые поставщики и потребители

1.5 Пример 1.5

1.6 Вычислительные тесты

ГЛАВА 2. ПРИМЕНЕНИЕ К ЗАДАЧАМ ТРАНСПОРТНОГО ТИПА

2.1 Задача с ограниченными пропускными способностями

Пример 2.1

2.2 Задача с дополнительными пунктами производства и

потребления

Постановка задачи

Алгоритм решения задачи

Формулы решения промежуточных двумерных задач

Пример 2.2

2.3 Задача с квадратичным функционалом

Постановка задачи

Метод решения задачи

2.4 Задача с запретами

ГЛАВА 3. ПРИМЕНЕНИЕ К РАСПРЕДЕЛИТЕЛЬНЫМ ЗАДАЧАМ

3.1 Задача о назначении

Пример 3.1.1

Обобщённые работы и исполнители

Пример 3.1.2

3.2 Задача с дополнительными работами и исполнителями

Постановка задачи

Метод решения

Пример 3.2

3.3 Задача о назначении с запретами

3.4 Задача о целераспределении для эффективной стрельбы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Итеративный алгоритм для класса оптимизационных задач транспортного типа»

Введение

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

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

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

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

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

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

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

Распространение метода улучшения плана для модификаций транспортных задач представляется нелёгким делом. Уже появление дополнительных переменных и функционалов на них вызывает усложнение

конструкций традиционной схемы симплекс-метода. Использование стандартной таблицы с перетеканием продукта по циклу невозможно. Ещё сложнее обстоит дело, когда, например, функционал на дополнительных переменных является нелинейным. Такая постановка рассматривается в диссертации. При этом алгоритм без каких-либо дополнительных процедур применяется как к задаче о назначении с дополнительными работами и исполнителями, так и в случае запретов.

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

Отправной точкой данной работы является анализ развития сетей связи с минимизацией капиталовложений при получении заданных потоков продукта. В соответствующих задачах большой размерности появляются булевы переменные, которые характеризуют тот факт, надо или не надо прокладывать каналы связи. Для смешанных частично-целочисленных задач применяются методы декомпозиции Бендерса, разделения переменных и т.д., см. например [28, 29]. Промежуточные задачи в алгоритмах понижающих размерность содержат большое количество булевых переменных - это так называемые многомерные задачи о ранце. Решение этих задач для практических размерностей вызывает большие трудности. Лишь в частных случаях удаётся построить эффективные алгоритмы. Один из таких случаев -это наличие лестничной структуры ограничений. Предлагаемый в [30] алгоритм последовательно решает двумерные задачи о ранце с зацеплениями. Возникает идея использовать эту технику для других классов задач с унимодулярными матрицами. Таким классом является задача транспортного типа. Предлагаемый алгоритм последовательно решает двумерные задачи с единственным зацеплением. Они берутся по одной из различных классов ограничений. В случае обобщённых поставщиков и потребителей в двумерных задачах зацепление может быть более сложным.

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

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

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

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

Апробация

Результаты, представленные в работе докладывались на семинарах в ВЦ РАН, МАТИ и на следующих научных конференциях:

Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Итеративный алгоритм для задачи о назначении // Технические науки: теория и практика: материалы междунар. заоч. науч. конф. (г. Чита, апрель 2012 г.). - Чита: Издательство Молодой ученый, 2012., С.41-43.

Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Итеративный метод решения транспортной задачи с ограниченными пропускными способностями // Труды

Всероссийской научной конференции, посвященной 60-летию ТТИ ЮФУ (ТРТИ, ТРТУ) "Современные проблемы математического моделирования, супервычислений и информационных технологий (СПМиИТ-2012)", Таганрог: 25-29 июня 2012 г., Известия ЮФУ. Технические науки, № 6 (131). 2012 г., С.252-255.

Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Задача о назначении с дополнительными работами и исполнителями // Технические науки в России и за рубежом (И): материалы междунар. заоч. науч. конф. (г. Москва, ноябрь 2012 г.). - Москва: Буки-Веди, 2012., С. 16-18.

Публикации

По материалам диссертации опубликованы помимо указанных ещё три работы [32-34], так что четыре находятся в изданиях из перечня ВАК (вторая из вышеперечисленного списка и три цитированных).

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

Работа состоит из настоящего введения, трёх глав, заключения, списка литературы. Объём диссертации 112 страниц.

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

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

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

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

Результаты, выносимые на защиту

1. Представлены конструкции итеративного декомпозиционного метода на основе последовательного решения двумерных задач, а также пересчёта

коэффициентов целевой функции для построения одномерных целочисленных задач.

2. Исследован случай, когда финальная система ограничений не имеет решений. Сформулировано правило введения обобщённых потребителей и поставщиков для запуска нового цикла итеративного процесса.

3. Даётся распространение подхода для широкого класса задач транспортного типа. Вводится постановка с собственными потребителями и поставщиками с линейными и квадратичными стоимостями за перевозки в эти пункты. Представлены конструкции алгоритма для указанных моделей.

4. Итеративный метод распространяется для задач о назначении различных типов. Даётся конкретизация для классической задачи о назначении, а также для случая дополнительных работ и исполнителей, равно как и при наличии запретов. Представлено применение метода для задач целераспределения при эффективной стрельбе.

Глава 1.

Основные конструкции итеративного процесса

Рассматривается классическая транспортная задача на минимум в целочисленной постановке. Строится итеративный метод её решения. Берутся ограничения из разных наборов индексов и составляются двумерные задачи. Они имеют единственную общую переменную. Приводятся формулы решения этих задач. После пересчёта значений целевых функций строится пара одномерных задач. Затем переходим к следующей двумерной задаче. Этот процесс повторяется. Алгоритм строит последовательность решений с монотонным ростом функционала. В итоге получается либо единственное оптимальное решение исходной задачи, либо транспортная система ограничений, когда можно найти допустимые решения. Они дают исходный оптимум. Если указанная система не совместна, то решается задача о максимальном потоке, и по определённому правилу формируются обобщённые поставщики и потребители. Процесс повторяется с уменьшенной по размеру системой транспортных ограничений.

1.1 Предварительные рассмотрения

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

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

учётом целочисленности некоторых переменных. Для задач применяются методы декомпозиции Данцига-Вулфа (процедура генерации столбцов), разделение переменных Бендерса, алгоритмы блочного целочисленного программирования и т.д. [28, 29, 36].

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

Задача развития сети

Имеется неориентированная сеть [35], заданная своим множеством узлов и линий, соединяющих некоторые пары узлов. Для каждой линии задаются её пропускная способность (количество каналов). Для некоторого подмножества пар узлов данной сети задана потребность в каналах для потока между ними. Различные пары узлов обмениваются потоками различных продуктов. Таким образом речь идёт о многопродуктовом потоке в сети. Заранее неизвестно, реализуем ли в сети заявленный многопродуктовый поток. Ставим задачу максимизировать коэффициент удовлетворения заявленного многопродуктового потока на существующей сети. Если этот коэффициент больше или равен единице в оптимальном решении, то требуемый многопродуктовый поток может быть реализован на сети. В противном случае ставим задачу найти места строительства новых линий и их пропускные способности затем, чтобы добавление этих линий позволило реализовать заявленный многопродуктовый поток при минимуме ресурсов на строительство новых линий.

Формализация сводится к следующей линейной частично-целочисленной задаче:

т _

1=1

Х^/ ^ Ъ1 + ' =

I уе5,

I

Здесь ^ означает номер элемента сети (узла и линии). Индекс У - это номер варианта прохождения совокупного продукта через сеть. Коэффициент

ац - это необходимое количество каналов в / -м элементе при / -м варианте прохождения потока. уц = {ОД} принимает нулевое значение, если в / -м элементе не добавляется канал, и единичное, если добавляется. -количество добавляемы каналов. - список вариантов увеличенных каналов в /-м элементе. сц - стоимость увеличения канала 1-й линии 7-го варианта.

Щ - неизвестная величина, являющаяся коэффициентом использования у -го варианта пропускаемого через сеть потока. 6, - количество каналов в / -м элементе сети.

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

При ограниченных капиталовложениях математическая постановка такова. Владелец сети предоставляет потребителям (соединяемым парам узлов) каналы, взимая тарифную плату за каждый предоставленный канал. Тариф различен для различных пар узлов. Себестоимость эксплуатации одного канала в каждой линии передачи также может быть различной. Рыночный спрос на предоставление каналов между парами узлов ограничен сверху. У владельца для развития сети имеется ограниченная сумма средств. На эти средства могут быть построены новые линии, переоборудованы узлы.

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

Здесь используются обозначения: Уф - переменная, принимающая

значения 0 или 1 (1 соответствует строительству или переоборудованию / - го

элемента сети по Р -му варианту, 0 - его отсутствию), (Л^ - приращение

емкости / - го элемента сети при переоборудовании или строительстве по Р -

му варианту, Сф - стоимость / - го элемента сети при переоборудовании или

строительстве по Р -му варианту, ]У - сумма выделенных средств на капиталовложения.

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

ЕЕ^Л <м=1,м+м

к=1

Ч

где fs - целые числа, величина потока (количество каналов) для У^-ой корреспондирующей пары узлов по двум независимым путям ^ Е ^ , равно единице , если / - й элемент сети входит в один из двух путей

и нулю в противном случае.

Условие ограниченности капиталовложений запишется следующим образом:

м+и

/=1 р

Целью является максимизация прибыли владельца, которая запишется следующим образом:

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

Задача о ранце с лестничной структурой ограничений

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

Далее кратко излагается эффективный метод точного решения многомерных задач о ранце для одного частного вида матриц ограничений, состоящих из 0 и 1 [30].

Рассмотрим многомерную задачу о ранце

п

(1.1)

п

Ее,х,. —» тах, аи > 0, Ь > 0, с. > 0

] ] ' и 7 1 7 ]

У=1

I = 1, К ,т; у =1,К ,п;

(1.2)

} - принимают значения 1 или 0.

Теорема 1.1.1. Пусть существуют такие X. > 0, что

т

У Xj = 1 для ] = 1, К ,п

(1.1.3)

и оптимальные решения задач

п

ЕЛ'.с.х, —» шах

У У 7

(1.1.4)

/я

YJaijxj<bi

(1.1.5)

при всех [ = 1,...,Ш совпадают. Тогда оптимальное решение задачи (1.1.1), (1.1.2) может быть составлено из оптимальных решений задач (1.1.4), (1.1.5). Легко привести примеры, доказывающие, что не всякая многомерная задача о ранце может быть так решена.

Рассмотрим многомерную задачу о ранце следующей специальной лестничной структуры

А

2>у<&2

(1.1.6)

Jr+1 >Jr, г = 1,К ,т-1 Л+1 ~Л+1 >Л-Р Г = 2,К ,/и-1

% г = 1,К ,т -целые, с} >0, 7 =1,К

Решение задачи (1.1.6) может быть представлено в соответствии с теоремой 1.1.1. Если рассматриваемая задача одномерна, то есть содержит одно ограничение, то ее решение может быть получено просто выбором

шах х J в количестве которые имеют наибольшие коэффициенты С' ■ в

целевой функции.

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

Алгоритм решения лестничной задачи с тремя ограничениями выглядит следующим образом. Решается задача с двумя первыми ограничениями. Производится разбиение её на две одномерные задачи, объединение оптимальных решений которых совпадает с оптимальным решением двумерной задачи. Далее решается двумерная задача со вторым и третьим ограничениями (часть коэффициентов целевой функции изменены при разбиении предыдущей задачи на одномерные). Эта двумерная задача также разбивается на две одномерные задачи. Сравнение оптимального

решения одномерной задачи со вторым ограничением после решения двумерной задачи с первым-вторым ограничениями с оптимальным решением этой же задачи после решения двумерной задачи со вторым-третьим ограничениями показывает, что список переменных, равных единице среди переменных , общих для второго и третьего ограничений во втором случае будет не длиннее, чем в первом случае (на эти переменные были наложены дополнительные ограничения). Этот факт с неизбежностью отразится на состоянии одномерной задачи с этим, вторым ограничением. Коэффициенты целевой функции при переменных, общих для второго-третьего ограничений будут не превосходить этих же коэффициентов в этой же одномерной задаче после решения двумерной задачи с первым-вторым ограничениями. Отсюда следует, что во второй раз решенная задача с первым-вторым ограничением удлинит список единиц среди переменных, общих для первого и второго ограничений. Следовательно, коэффициенты целевой функции при переменных, общих для первого и второго ограничений в одномерной задаче с первым ограничением увеличатся (т.к. коэффициенты целевой функции при переменных, присутствующих лишь в первом ограничении, не меняются), а у одномерной задачи со вторым ограничением, соответственно - уменьшатся. Процесс монотонен, целочислен, следовательно, конечен. В [30] детально описан переход к четырём, пяти и т.д. ограничениям. Важно, что идеи последовательного решения двумерных задач с зацеплениями будут использоваться в дальнейшем при построении алгоритма для транспортных постановок.

1.2 Описание алгоритма

Рассмотрим следующую классическую транспортную задачу (см., например, [4]):

я

(1.2.1)

Y^X^J=bJ> 7= и-,«, (1.2.2)

1=1

т п

lla^=llbJ , (1.2.3)

1=1 7=1

т п

(1-2.4)

/=1 7=1

Предположим, что С11 ? Ь} . целые положительные числа, а С^ - чётные

неотрицательные числа при всех / = у = , что не ограничивает

общности рассмотрения.

Здесь используется известная интерпретация. Имеются т пунктов производства и п пунктов потребления однопродуктового неделимого

товара, который перевозится в количестве из пункта производства с

номером / в пункт потребления с номером у . Целью является минимизация

затрат, где Сц - стоимость перевозки единицы продукта из пункта / в пункт } ■

В зависимости от исходных данных задача решается в один два или более этапов

Первый этап решения

1 2

Вычислим Су = су = су /2 и составим Ш оптимизационных задач с ограничениями (1.2.1):

п

Т,С1Хи ~>т1п . (1.2.5)

У=1

Ху -целые, 0<хгу < тт(л.,Ь}), / = 1,...,т; у = 1,...,п (1.2.6)

Составим также ещё У1 оптимизационных задач с ограничениями (1.2.2) и (1.2.6):

т

у = 1,..., п (1.2.7)

1=1

Задачи вида (1.2.1), (1.2.5), (1.2.6), и (1.2.2), (1.2.6), (1.2.7) решаются простым выбором нескольких наименьших коэффициентов целевой функции, а именно: пусть в задаче вида (1.2.1), (1.2.5), (1.2.6)

с1. = тЧ С1 > тогда V = пипЦ, Ъ^ ),

далее, если

С = С1> тогда V- - ттЦ - х1ф,Ъ^) и т. д.

Точно так же решаются и задачи (1.2.2), (1.2.6), (1.2.7).

Предположим, что все п + т задач (1.2.1), (1.2.5), (1.2.6) и (1.2.2), (1.2.6), (1.2.7) решены. Объединение оптимальных решений всех П + т одномерных задач назовём псевдорешением исходной транспортной задачи, а соответствующую сумму значений целевых функций - значением целевой функции псевдорешения. Очевидно, что значение целевой функции псевдорешения не превосходит значения целевой функции оптимального решения исходной транспортной задачи (1) -(4), причём этот факт не зависит

от способа разбиения каждого С на два слагаемых.

Теорема 1.2.1. Если объединение оптимальных решений всех п + т задач (1.2.1), (1.2.5), (1.2.6) и (1.2.2), (1.2.6), (1.2.7) (псевдорешение исходной транспортной задачи) является допустимым решением исходной задачи (1.2.1)—(1.2.4), то оно является оптимальным решением задачи (1.2.1)—(1.2.4).

Доказательствотеоремы 1.2.1. Предположим противное. Так как объединение оптимальных решений п + т одномерных задач является допустимым решением задачи (1.2.1)-(1.2.4), то значение целевой функции в оптимальном решении задачи (1.2.1)—(1.2.4) будет строго меньше суммы значений целевых функций в оптимальных решениях п + т одномерных задач. Подставив оптимальное решение транспортной задачи в п + т одномерных задач, получим, что, по крайней мере, в одной из

Список литературы диссертационного исследования кандидат наук Кузовлев, Дмитрий Игоревич, 2013 год

Список литературы

1. Толстой А. Н., Методы устранения нерациональных перевозок при планировании. «Социалистический транспорт» 9, 28—51 (1939).

2. Хичкок (Hitchcock F. L.). Distribution of a product from several sources to numerous localities. J. Math. Phys. 20, 224— 230 (1941).

3. Брудно A. Jl., Решение транспортной задачи методом вычеркивающей нумерации. В сб. «Применение ЦВМ в экономике», Изд. АН СССР, 1962, стр. 17—38.

4. Гавурин М. К., Рубинштейн Г. III., Сурин С. С., Об оптимальном использовании производственных средств при выполнении нескольких видов работ (обобщенная транспортная задача). АН СССР, СО, экономико-математическая серия, вып. 1, (1965) стр. 7—34.

5. Глейзал (Qleyzal А.), Алгоритм для решения проблемы транспортировки, «Математика» 2, 1 (1958).

6. Голыптейн Е. Г., Транспортная задача и ее обобщения. Сб. «Методы и алгоритмы решения транспортной задачи», Госстат- издат, 1963.

7. Голыптейн Е. Г., Юдин Д. Б., Об одном классе задач планирования народного хозяйства Сб. «Проблемы кибернетики», 5, 1961, стр. 165—182:

8. Данциг (Dantzig G. В.), Application of the simplex method to a transportation problem. Activity analysis of production and allocation, ed. Т. C. Koopmans, Cowles Commission Monograph, 13, Wiley, New York, 1951, стр. 359—373.

9. Журавлев Г. E., Методы решения задач на наилучшее использование и рациональный выбор машин автотракторного парка колхозов и совхозов. Материалы к конференции по опыту и перспективам применения математических методов и ЭВМ в планировании. АН СССР, СО, 1962.

10. Канторович JI. В., Гавурин М. К. Применение математических методов в вопросах анализа грузопотоков. В сб. «Проблемы повышения эффективности работы транспорта», Изд. АН СССР, 1949, стр. 110—138.

11. Каплан А Б., Перспективы применения математических методов для комплексного регулирования вагонного парка железных дорог. Труды научного совещания по применению математических методов в экономических исследованиях и планировании, т. V, Планирование и эксплуатация на транспорте, Изд. АН СССР, 1961.

12. Кун (Kuhn Н. W.), Венгерский метод решения задачи о назначениях. Сб. «Методы и алгоритмы решения транспортной задачи», Госстатиздат, 1963.

13. Кун (Kuhn Н. W.), Некоторые видоизменения венгерского метода для задачи о назначениях. Сб. статей «Методы и алгоритмы решения транспортной задачи», Госстатиздат, 1963.

14. Лебедев С. С., Алгоритм решения распределительной задачи. Сб. «Экономико-математические методы», вып. II, «Наука», 1965, стр. 247—267.

15. Лурье А. Л., Алгоритм решения распределительной задачи. Сб. статей под редакцией В. С. Немчинова «Применение математики в экономических исследованиях», т. II, Соцэкгиз, 1962.

16. Лурье А. Л., Алгоритм решения транспортной задачи путем приближения условно-оптимальными планами. Сб. «Вычислительная математика», 1961, № 7, стр. 151—160.

17. Малков У. X., Алгоритм решения распределительной задачи. Сб. «Вычислительная математика и математическая физика», 2, 2, 358—366 (1962).

18. Манкрес (Munkres J.), Алгоритм решения задачи выбора и транспортной задачи. Сб. «Методы и алгоритмы решения транспортной задачи», Госстатиздат, 1963, стр. 73—79.

19. Мовшович С. M., Об одной задаче планирования перевозок неоднородных взаимозаменяемых продуктов. Сб. «Применение математики в экономических исследованиях», т. 3, «Мысль», 1965.

20. Олейник Ю. А. Решение задачи о транспортировке на ЭВМ методом приближения условно-оптимальными планами. АН СССР, ВЦ, 1960.

21. Савин В П., Опыт применения математических методов и ЭЦВМ в эксплуатационных расчетах на речном транспорте. Материалы к конференции по опыту и перспективам применения математических методов и ЭВМ в планировании, АН СССР, СО, 1962.

22. Форд, Фулкерсон (Ford L. R., Fulkerson D. R.), Алгоритм одновременного решения прямой и двойственной задач для проблемы Хичкока с ограниченными пропускными способностями. Сб. «Методы и алгоритмы решения транспортной задачи», Госстатиздат, 1963.

23. Форд, Фулкерсон (Ford L. R., Fulkerson D. R.), A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. Nav. Res. Logist Quart. 4, 1, 45— 54 (1957).

24. Форд JI.P., Фулкерсон Д.Р., Решение транспортной задачи. Сб. «Методы и алгоритмы решения транспортной задачи», Госстатиздат, 1963. стр. 61—72.

25. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа, М. : Наука, 1969 г.

26. Триус Е. Б., Задачи математического программирования транспортного типа, Изд-во «Советское радио», 1967

27. Вильяме (Williams А. С.), A treatment of transportation problems by decomposition. L. Soc. Ind. Appl. Math. 10, 1, 35—48 (1962).

28. Лэсдон Л.С. Оптимизация больших систем. М.:Наука, 1975.

29. Цурков В.И. Декомпозиция в задачах большой размерности. М. :Наука, 1981.

30. Думбадзе Л.Г., Тизик А.П. Многомерная задача о ранце специальной лестничной структуры // Известия РАН. Теория и системы управления. 1996. №4., с. 119-122.

31. Юдин Д.Б. Математические методы управления в условиях неполной информации. М.: Советское радио, 1974.

32. Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Метод последовательных изменений параметров функционала при решении задачи о назначении // Известия Российской академии наук. Теория и системы управления. 2011. №6. С.67-78.

33. Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Декомпозиционный алгоритм для решения транспортной задачи с ограниченными пропускными способностями // Мехатроника, автоматизация, управление. 2012. № 1. С.45-48.

34. Тизик А.П., Кузовлев Д.И., Соколов A.A. Метод последовательной модификации функционала для транспортной задачи с дополнительными пунктами производства и потребления // Вестник ТвГУ. Серия прикладная математика. 2012. №4. С.91-98.

35. Думбадзе Л.Г., Тизик А.П., Тресков Ю.П. Задача эффективной эксплуатации сети связи // Известия РАН, Теория и системы управления. 2003. №6. С.113-116.

36. Авербах И.Л, Цурков В.И. Оптимизация в блочных задачах с целочисленными переменными. М.:Наука, 1995.

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

38. А.П.Тизик, В.И.Цурков Метод последовательной модификации функционала для решения транспортной задачи // Автомат, и телемех. 2012. V.l. Р.148-158.

39. Тизик А.П., Цурков В.И. Декомпозиционная методика для одного класса задач блочного программирования // ЖВМиМФ. 1989. Т.29. №10.

40. Тизик А.П., Цурков В.И. Оптимальное распределение каналов на сети связи // Изв. АН СССР. Техн. кибернетика. 1989. №4.

41. Думбадзе Jl.Г. Разработка методов и алгоритмов в задачах оптимального использования и развития сетей: Дисс. ...канд. физ.-мат. наук. М.: ВЦ РАН, 2007.

42. A.A. Соколов, А.П. Тизик, В.И. Цурков. Итеративный метод для транспортной задачи с дополнительными пунктами производства и потребления и квадратичным функционалом // Известия РАН, Теория и системы управления. 2013, № 4, с. 88-98.