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

На правах рукописи

Кузовлев Дмитрий Игоревич

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

01.01.09 - Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

5 дек гт

Москва 2013

005542011

005542011

Работа выполнена в Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук

доктор физико-математических наук, профессор

ЦУРКОВ Владимир Иванович ДИКУСАР Василий Васильевич, доктор физико-математических наук, главный научный сотрудник, Федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук; МОКРЯКОВ Алексей Викторович, кандидат физико-математических наук, доцент,

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «МАТИ — Российский государственный технологический университет имени К.Э.Циолковского» Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Тверской государственный университет» Защита состоится . 4Д 20года на заседании

диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительном центре им. A.A. Дородницына Российской академии наук» по адресу: 119333, г. Москва, ул. Вавилова, дом 40, конференц-зал в у/-'О

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Вычислительного центра им. A.A. Дородницына Российской академии наук.

Автореферат разослан Д j. 20года.

Научный руководитель:

Официальные оппоненты:

Ученый секретарь

диссертационного совета Д 002.017.02, /f) .

д.ф.-м.н., профессор /и^С в в- Рязанов

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

Уже прошло более 70 лет, как появились первые работы, где была поставлена и формализована транспортная задача. Центральным подходом в решении является метод улучшения плана (симплекс-метод линейного программирования). Специфика транспортной задачи предполагает рассмотрение таблицы, где в клетках записываются коэффициенты целевой функции и неизвестные количества перевозимой продукции из пунктов производства в пункты потребления. Переход от одного допустимого (базисного) решения к другому осуществляется с помощью построения цикла, в котором перемещается продукт, так что одна из клеток обнуляется. В результате осуществляется переход к базисному решению с меньшим значением функционала. Весьма распространённым в этом направлении является так называемый метод потенциалов, где переход к новому опорному решению осуществляется с помощью двойственных соотношений, которые для транспортной задачи имеют специфический вид. Широкое применение в транспортных постановках получил так называемый венгерский метод. В его основе лежит построение максимальных потоков через транспортную сеть с частично разрешёнными коммуникациями и последующее сокращение невязок. Известны также другие специальные методы. Например, предлагается применить двухуровневую технику метода декомпозиции Данцига-Вулфа для классической транспортной задачи. При этом исходная матрица условий разбивается по горизонтали таким образом, что верхний уровень решает независимые задачи с одним ограничением.

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

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

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

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

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

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

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

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

Технические науки: теория и практика (г. Чита, апрель 2012 г.);

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

Технические науки в России и за рубежом (II) (г. Москва, ноябрь 2012 г.).

Публикации. По материалам диссертации опубликованы шесть работ, из них четыре находятся в изданиях из перечня ВАК (вторая и последние три из цитированных).

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

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

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

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

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

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

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

Содержание работы

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

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

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

Рассмотрим классическую транспортную задачу:

л

2Х=Л„ / = 1,...,7И, О)

J=1 т

;=1 т

2,at=Yb. , (3)

Zw j

1=1 7=

m n

Х12^сихи^т{п- (4)

/=1 7=1

Предположим, что ClnЬj - целые положительные числа, а С^ -чётные неотрицательные числа при всех I = 1 ] — \,...,П .

Первый этап решения выглядит так. Вычислим сУ = С^. — Су / 2 и составим Ш оптимизационных задач с ограничениями (1):

п

£ с\ху min , i = 1,..., m; (5)

7=1

Х;у -целые, 0 < xtj < min(а„6Д ' = 1,-, W, j = 1,...,и (6)

Составим также ещё И оптимизационных задач с ограничениями (2) и (6):

т

-»min,, j = 1,...,и (?)

Задачи вида (1), (5), (6), и (2), (6), (7) решаются простым выбором нескольких наименьших коэффициентов целевой функции, а именно: пусть в задаче вида (1), (5), (6)

= тту с1у, тогда X. у< = тт(а., Ъ^ ), далее, если

с1. = С1'тогда хи~ = т1пЦ " Х-и-' К ) НТ-Д-

Точно так же решаются и задачи (2), (6), (7).

Предположим, что все П + Ш задач (1), (5), (6) и (2), (6), (7) решены. Объединение оптимальных решений всех П +171 одномерных задач назовём псевдорешением исходной транспортной задачи, а соответствующую сумму значений целевых функций - значением целевой функции псевдорешения. Значение целевой функции псевдорешения не превосходит значения целевой функции оптимального решения исходной транспортной задачи (1) -(4). Если объединение оптимальных решений всех П + ТП задач (1), (5), (6) и (2), (6), (7) (псевдорешение исходной транспортной задачи) является допустимым решением исходной задачи (I)—(4), то оно является её оптимальным решением.

Рассмотрим второй этап решения. Пусть объединение оптимальных решений П + ГП задач (1), (5), (6) и (2), (6), (7) не является допустимым решением исходной задачи (1)-(4). в этом случае строим итеративный процесс решения следующих двумерных оптимизационных задач. На

первом шаге выпишем первое ограничение из (1), (/ = 1 ), и первое

ограничение из (2), (_/ = 1):

171

у=1

1=1

Составим целевую функцию:

т п

IX*.,+Еспх.1 min (ю)

у=1 ,=1

и рассмотрим задачу (6), (8)—(10).

Выпишем первую из задач вида (1), (5), (6) и первую из задач (2), (6),

1 2

(7) с новыми величинами Си и Cli . Эти величины удовлетворяют

условиям: их сумма равна С,, , имеет место равенство сумм

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

Решение задачи (6), (8)—(10) является первым шагом итеративного процесса. На втором шаге этого процесса решается двумерная задача, формируемая из первого ограничения вида (1), т.е. / = 1 , и второго ограничения вида (2), т.е. j = 2. Далее, на третьем шаге, снова i' = 1, j — 3 и т.д. до j' = т . На ТП + 1 -м шаге полагаем Z' = 2, j = 1 и т.д. до i = n,j = m.

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

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

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

вывезшие весь свой продукт. Пусть из пункта производства в построенном максимальном потоке вывезен не весь продукт. Обозначим 1 -2

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

•1 -2

продукт из пункта . Очевидно, что пункты потребления ]х, , •■■

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

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

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

Остановимся на задаче с дополнительными пунктами производства и потребления. Пусть 1 -ый производитель товара (1</<т) может

поставлять товар не только каждому у -му потребителю (1 < у < и), но и своему индивидуальному I -му потребителю. Объём поставок товара I -му потребителю у( , в отличие от ] -х потребителей, не фиксирован. Он неотрицателен, разумеется, ограничен объёмом производства в / -ом пункте производства (0 < < а< I < т^.

Пусть также каждый ] -ый потребитель (1 < ] < П^ имеет возможность удовлетворить свои потребности за счёт поставки товара от своего индивидуального } -го поставщика (1 < ] < и) . Объём поставки у -му потребителю от индивидуального поставщика не

фиксирован и ограничен объёмом потребности у -го потребителя < < ,1 < у < и) . Пусть заданы стоимости поставки единицы товара от I -го поставщика ] -му потребителю

{су > 0,1 < г < ТП,\ < у < А?^ , а также заданы стоимости поставки единицы товара каждому индивидуальному потребителю (с11 >0,1 < / < /я) и стоимость поставки товара от индивидуального

поставщика > 0,1 < у < ^ . В заданных условиях необходимо

минимизировать общие расходы на перевозку товара при фиксированных объёмах производства у обычных поставщиков и фиксированных объёмах потребления у обычных потребителей. Формальная запись задачи имеет вид

п

2Х +У1 = апа1 >0Л<1<пг, (11)

7=1

т

+ = ЪрЪ} > ОД < ] < п, (12)

/=1

п т т п

ЕХ^л-++т1п > (13)

У=1 /=1 /=1 7=1

с0 > 0,4 > 0,еу > 0,7,. > 0, > 0,1 <1<т,\<]<п. (14)

Первый этап строится по аналогии со стр. 8.

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

п

у=1

т

(i6)

;=1

(в ограничениях вида (11) полагается / = 1, а в ограничениях вида (12)

-.7 = 1)

п т

Yf\jx\j + + + т min. (17)

7=1 f-1

Здесь могут иметь место три случая. Первый случай:

, + (18)

Тогда полагаем X,, = 1ШП ) , одно из двух ограничений

выходит при этом на равенство далее задача (15)-(17) по существу превращается в одномерную задачу. После решения задачи (15)-(17) Л 2

найдем новые Си и Сп сначала из системы уравнений

min |min cXj ,d^-cln- min

minc^Vc,2,,

V м J

I 2 C11 + C11 = CU

Затем, при необходимости, округлим max^CjpC,2, j до

ближайшего целого в меньшую сторону, а min^C,',,^2, j - в большую сторону. Второй случай:

с,, = min |mm cXj ,dx j + min ^min c\, e{ j. ( i 9)

Пусть для определённости, <2, < и двойные минимумы в (19)

достигаются при J — J и 1 = 1 соответственно. В этом случае вместо решения выписываем уравнения

X,, +.Х * — ax,Xu + — min^bpür » j . Далее, как и в

предыдущем случае, задача (15)-(17) решается как одномерная.

1 _ 1 2 _ 2 Выписываем новые значения С,, — С , и С,, — С „ .

11 \j 11 / 1

Если двойные минимумы в (19) равны dx и б,, уравнения вместо решения имеют вид Xjj + ух — ах,Ххх + Wj ~ Ьх. Выписываем новые значения коэффициентов при Ххх в одномерных задачах C|j = dx,Cxl — . Если первый двойной минимум в (19) равен dx, а второй достигается на некотором 1 = I , то соответствующие уравнения имеют вид X,, + У\ — а.х,Ххх =min|i1,fl, j и ,

1 _ 1 2 _

соответственно, Сх, — С^ » и С^ ~ Третий случай:

сх j > minclXj, dx j + min^min cfx, ex j.

Временно исключим из рассмотрения Хх j, полагая равным нулю, и

решим две получившиеся одномерные задачи. Если имеет место неравенство

( Л (

cu > тах

та*c\pdX{ ^ v *и»о у

+ тах (тах с\, еХ(при и,>0) ,

\ ха>о )

то тем самым двумерная задача решена. Далее, найдём новые с\х и С^х сначала из системы уравнений

max тахс,1,,^ Л>0) V *и>°

С,, + С[ [ С, J,

-с,1, =max(maxcf„e1( w>0))-c,2,-\ *11>0 /

Округлим до целого так же, как и во втором случае. Если имеет место равенство

си = m ах i m ах с,'у, d] {при ,1 + max (max cj,^ w>0)),

\ x\jx> у \ */i>o /

то, очевидно, что у решаемой задачи оптимальное решение не

единственно и Хи может принимать целочисленные значения от 0 до min^a, ,Ь{ j в сумме с X , (может быть у^) или X (может быть

Wl ) соответственно. Здесь и Ь^ - остатки от Cly и Ъ^ перед

назначением последних положительных значений переменных в

соответствующих одномерных задачах. Этот факт мы запишем в виде

_ * _ *

ограничений Xj , + X , — ¿7, (возможно, Xj, + ух — а^ ) и

_ , * _ , * 12

хп + Х_» — О, (возможно, Х,| + Wj — Ох ). Коэффициенты Сц и Сц

в этом случае принимают значения с', = с| » (или cjj — dx ) и

2 2 2 1 2 С л (или сц ~ )• Если Сц < С^ , + Ct^ , то, очевидно, в

оптимальной решении двумерной задачи должно иметь место неравенство Xj j > 0. Предположим, что X » = X, . Обнуляя X , и

Х,^, полагаем Xfl — ПИП^Я^ ^ . Одно из ограничений при этом

выйдет на равенство и далее задача становится одномерной. Теперь

пусть, для определённости, X , .В этом случае обнуляем X» ,

1 j /I /I

увеличиваем Хп на X, , X , уменьшаем на X» и переходим в illy (1

1 •* 1

сравнению С, j и суммы С » + С,, % , где I — 1 - номер следующей

Ч {> -iji

ненулевой переменной в оптимальном решении соответствующей одномерной задачи. Если имеет место равенство С., = с' , + С, „ ^ ,

и (/-1)1

то выписываем ограничения. Если имеет место неравенство

С,, > С1 » + С, „ х , то процесс нахождения значения X,, окончен. 1у -1|1 11

1 2

Учитывая, что X » > X, , новые значения С, ■ и С,, определим 1 у /I " 11

1 _ 1 2 _ 1

следующим образом: Си — С * ,Си — Сц — С » .

Теорема 1. Объединение оптимальных решений двух одномерных задач, сформированных по итогам решения задачи (15)-(17) будет совпадать с оптимальных решением задачи (15)-(17).

Заметим, что сумма значений целевых функций в оптимальных решениях одномерных задач, сформированных после решения двумерной задачи (15)-(17), будет не меньше чем сумма значений целевых функций этих же одномерных задач до объединения их в двумерную задачу.

На втором шаге снова полагаем / = 1, но у = 2. Далее, на третьем шаге / = 1, у' = 3 , и так далее до 1 = 1 ,у' = т. На т + 1 шаге полагаем / = 2, = 1 и т.д. до I = П, у' = Ш . После тп -го шага итерационного процесса снова полагаем /= 1, ] = 1 , то есть

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

Итерационный процесс окончен, когда сумма значений целевых функций во всех 171 + П одномерных задачах перестает возрастать.

Предположим, что в итоге все УП + П одномерные задачи имеют единственное решение. Тогда, очевидно, имеет место утверждение.

Теорема 2. Объединение оптимальных решений одномерных задач является оптимальным решением исходной задачи (11)-(14).

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

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

В третьей главе метод распространяется на распределительные задачи.

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

Итак, имеем задачу о назначении:

п

(20)

п

(21)

п п

1=1 ]=1

X,. - целые, О < X;. < 1, 1 < г,у < п . (23)

Здесь используется известная интерпретация. Имеются П работ и П исполнителей. С^ - количество рабочих часов, которые затрачивает I -й

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

рабочего времени на выполнение всех П работ. Первый этап аналогичен стр. 8.

На втором этапе строим итеративный процесс решения следующих двумерных оптимизационных задач. На первом шаге выпишем первые

ограничения из (20) и из (21), (/ = 1), и первое ограничение из (21):

п

2>1у= 1. (24)

7=1 п

5>,.=1- (25)

/=1

Составим целевую функцию: п п

У=1 '=1

и рассмотрим задачу (24)-(26).

При решении задачи (24)-(26) могут иметь место три случая. Первый случай:

сп <тту/117+тт,1с; (27)

Тогда полагаем Л^ 1 = 1 и задача (24)-(26) решена. После

I 2

решения задачи (24)-(26) найдём новые С1 ( и сначала из системы уравнений

С,, + С, [ с,, ,

minv*i C\j - cl\ = min;*i cn - cn • Затем, при необходимости, округлим шах {,) до

ближайшего целого в меньшую сторону, а - в большую

сторону.

Второй случай: Пусть

сп = min^, c\j + min^, с\ (28)

1 -12*2 Тогда обозначим С . = ШШ^, С,у и С.^ = ГП1П(>1 С., , вместо

решения выписываем ограничения Xjj + Х^^. =1 , Хц 4- X., ( = 1 .

1 _ 1 2 _ 2 Вычисляем новые значения Сj, — С . иСц-С^.

Третий случай:

С„ (29)

Тогда, очевидно, что Х^.. = 1, Х..^ = 1 и задача (24)-(26) решена. 1 2

Далее, найдём новые Сп и Сп из системы уравнении

1 2 _ с\ 1 с\ 1 — сп '

1 _ 1 _ 2 _ 2 CXj' C\\~Cf\ сп '

Округлим до целого так же, как и во втором случае. Сформируем с 1 2

новыми значениями С, j и С,, две одномерные задачи. Первая задача

п

2>J,*ly -» min (30)

j=i

при ограничениях (1.6), (2.1) и вторая задача

п ;=1

при ограничениях (25).

Имеет место следующее утверждение.

Теорема 3. Во всех вышеперечисленных случаях (выполняется соотношение (27), (28) или (29) ) объединение оптимальных решений

1 2

одномерных задач (24), (30) и (25), (31) с новыми значениями Си и Сп

является оптимальным решением двумерной задачи (24)-(26).

Решение задачи (24)-(26) является первым шагом итеративного процесса. На втором шаге решается двумерная задача, формируемая из первого ограничения вида (20), т.е. I — 1, и второго ограничения вида (21), т.е. ]' = 2. Далее, на третьем шаге, снова / = 1, у = 3 и т.д., до

] — П . На П + 1 -ом шаге полагаем / = 2 , ] = 1 и т.д. до

2

1 = П , у = П . После П -го шага итерационного процесса снова полагаем / = 1 в ограничениях вида (20) и ] = 1 в ограничениях вида

(21), то есть, ограничения будут такими же как и на первом шаге пошагового процесса. Целевая функция будет той, которая получится к

этому П +1 -му шагу. Как уже отмечалось, в результате итерационного процесса сумма значений целевых функций

2 п

одномерных задач возрастает.

Пусть цикл окончен. Предположим, что в итоге все

2 п

одномерные

задачи имеют единственное решение. Тогда справедлив критерий оптимальности.

Теорема 4. Объединение решений одномерных задач является оптимальным решением исходной задачи о назначении (20)-(23).

Рассмотрим далее другую возможность - во всех одномерных задачах по итогам цикла получены ограничения на переменные, т.е.

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

Теорема 5. Любое допустимое решение редуцированной задачи о назначении, полученной в результате пошагового процесса есть её оптимальное решение.

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

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

Заключение

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

^ 2

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

Список публикаций по теме диссертации

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

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

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

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

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

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

Кузовлев Дмитрий Игоревич

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

Подписано в печать 14.11.2013 Формат бумаги 60x84 1/16 Уч.-изд. л.З .Усл.-печ. 1 Тираж 100 экз. Заказ 24

Отпечатано на ротапринтах в Федеральном государственном бюджетном учреждением науки Вычислительный центр им. A.A. Дородницына Российской академии наук 119333, Москва, ул. Вавилова,40

На правах рукописи

04201454415

КУЗОВЛЕВ Дмитрий Игоревич

ИТЕРАТИВНЫЙ АЛГОРИТМ ДЛЯ КЛАССА ОПТИМИЗАЦИОННЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА

01.01.09 - Дискретная математика и математическая кибернетика

диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель

доктор физико-математических наук профессор Цурков Владимир Иванович

Москва 2013

Оглавление

ВВЕДЕНИЕ.............................................................................................................3

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

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

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

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

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

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

Апробация....................................................................................................6

Публикации.................................................................................................7

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

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

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

ПРОЦЕССА..........................................................................................................10

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

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

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

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

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

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

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

1.3 Пример 1.3.............................................................................................27

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

1.5 Пример 1.5.............................................................................................31

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

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

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

Пример 2.1...............................................................................................42

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

потребления.......................................................................................................48

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

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

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

Пример 2.2...............................................................................................54

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

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

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

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

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

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

Пример 3.1.1............................................................................................77

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

Пример 3.1.2............................................................................................81

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

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

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

Пример 3.2...............................................................................................87

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

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

ЗАКЛЮЧЕНИЕ.................................................................................................107

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

Введение

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

Уже прошло более 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 Предварительные рассмотрения

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