ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 1, с. 88-94
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 510.56, 510.647
НЕЛИНЕЙНАЯ ЦЕЛОЧИСЛЕННАЯ ТРАНСПОРТНАЯ ЗАДАЧА С ДОПОЛНИТЕЛЬНЫМИ ПУНКТАМИ ПРОИЗВОДСТВА
И ПОТРЕБЛЕНИЯ
© 2015 г. А. С. Есенков, В. Ю. Леонов, А. П. Тизик, В. И. Цурков
Москва, ВЦ РАН Поступила в редакцию 09.08.14 г., после доработки 16.09.14 г.
Декомпозиционный итеративный метод на основе последовательного решения двумерных задач с ограничениями из разных групп успешно применяется для случая наличия собственных производителей и потребителей в целочисленных транспортных задачах с выпуклыми целевыми функциями. С помощью введения новых переменных удается распространить конструкции алгоритма, где центральным местом является решение оптимизационных задач с двумя ограничениями. Подробный анализ этих задач представлен в данной работе.
Б01: 10.7868/80002338815010059
Введение. В [1] предложен метод решения целочисленной транспортной задачи на основе последовательного решения задач с двумя ограничениями. Алгоритм строится следующим образом. Рассматривается классическая транспортная задача с двумя группами ограничений (см., например, [2, 3]). Берутся по два ограничения из разных групп. Они имеют одну зацепляющуюся переменную и формируют задачу с двумя ограничениями (так называемую двумерную задачу). Эта задача легко решается и ее оптимальное значение целевой функции не меньше, чем сумма значений целевых функций, соответствующих задаче с одним ограничением. Коэффициент целевой функции двумерной задачи для зацепляющейся переменной разбивается на два слагаемых, и рассматриваются две задачи с одним ограничением. Разбиение коэффициента происходит таким образом, что сумма оптимальных значений целевых функций одномерных задач равна оптимуму двумерной задачи. Этот процесс повторяется для всех пар индексов транспортной задачи. В результате получаются так называемые псевдорешения, которые, вообще говоря, не допустимы к исходной задаче, но с возрастанием значения целевой функции. Доказано, что целевая функция на псевдорешениях не превосходит оптимального решения исходной задачи. Итак, повторяя большие итерации (циклы), имеем монотонный рост ограниченной последовательности. Когда этот рост прекращается, то имеются две возможности. Псевдорешения задают ограничения, которые удовлетворяют другим группам условий. В этом случае получим оптимум исходной задачи. В другой ситуации это не так, и строятся так называемые обобщенные поставщики и потребители. Это подробно описано в [4], и процесс продолжается для редуцированной транспортной задачи. В [1, 4] рассматриваются целочисленные линейные задачи, однако представленный подход может быть расширен на большой класс нелинейных задач.
В данной статье этот подход применяется для некоторой нелинейной целочисленной транспортной задачи, где у каждого поставщика кроме обычных потребителей имеется свой индивидуальный потребитель. У каждого потребителя помимо обычных поставщиков имеется свой индивидуальный поставщик. Стоимости перевозок в дополнительные пункты потребления и из дополнительных пунктов производства предполагаются дифференцируемыми выпуклыми вниз функциями от объема перевозки. Аналогичная постановка, но с квадратичной целевой функцией изучается в [5]. Основные идеи подхода представлены в [4], они используют также результаты [6—22]. Центральным местом данной работы является подробный анализ указанных промежуточных задач с двумя ограничениями.
1. Постановка задачи (линейный случай). Имеется, как и в классической транспортной задаче,
т обычных пунктов производства с объемом производства а, I = 1, т, и п пунктов потребления с
объемом потребления ¿у-, у = 1, п. Стоимость перевозки из обычных пунктов производства в обычные пункты потребления линейно зависит от объемов перевозки. Кроме того, у каждого 1-го
пункта производства имеется свой индивидуальный пункт потребления с объемом у. У каждого у -го пункта потребления также кроме обычных поставщиков имеется свой индивидуальный пункт производства с объемом му. Стоимость перевозки в дополнительные пункты потребления и из дополнительных пунктов производства линейно зависит от объемов перевозки.
Формальная запись задачи имеет вид
п
X Ху + у = а, г = 1, т, (1.1)
у = 1
т
X Ху + V] = Ьу, у = 1, п, (1.2)
г = 1
т п т п
+ XdУ + ^ ^ (1.3)
i = 1 у = 1 i = 1 у = 1
т п
X а = X Ьу,
i = 1 у = 1
а1 >0, Ьу > 0, ху > 0, у > 0, V] > 0, су > 0, г = 1,т, у = 1,п.
Все переменные и коэффициенты — целые. Здесь Ху — количество продукта, перевозимого из пункта производства с номером г в пункт потребления с номером у, у 1 — количество продукта, вывозимого из г -го пункта производства в дополнительный пункт потребления, Му — количество продукта, доставляемого в у-й пункт потребления из дополнительного пункта производства.
2. Свойства решения задачи (1.1)—(1.3). Заметим, что для всякого допустимого решения задачи (1.1)—(1.3) имеет место соотношение
т п
X у = X ^.
i = 1 у = 1
В самом деле, если бы (2.1) не имело места, то количество продукта, отправляемого всеми производителями обычным потребителям, не равнялось бы количеству продукта, полученного всеми потребителями от обычных производителей. Содержательно интерпретируя перевозку из г -го пункта производства некоторого количества продукта в свой дополнительный пункт потребления совместно с перевозкой такого же количества продукта в у -й пункт потребления из своего индивидуального пункта производства как альтернативный путь поставки продукта из г-го пункта производства в у -й пункт потребления, сравним стоимости перевозки единицы продукта по альтернативным путям.
Пусть для некоторых пар г0,у0,1 < г0 < т, 1 < у0 < п, имеет место неравенство й.0 + е.„ < с.у0. Тогда полагаем с' = с10 + е.0. Для всех остальных 1 <г< т, 1 < у < п полагаем с' = с у. Сформулиру-
г } 1 у
ем обычную транспортную задачу:
п
X Ху = а, г = 1, т, (2.2)
у = 1
т
X Ху = Ьу, у = 1, п, (2.3)
i = 1
m n
X X c'üxij ^ min' (2-4)
i = 1 j = 1
где at > 0,bj > 0,Xj > 0 — целые.
Очевидно, что по построению из оптимального решения задачи (2.2)—(2.4) можно сформировать оптимальное решение задачи (1.1)—(1.3). В самом деле, для этого достаточно положить
opt Ч 1 opt opt Ч 1 opt
y' = Z V и w/ = Z V,
J'.c'y < cy v.cv <сц
здесь x°f — значения xiy в оптимальном решении задачи (2.2)—(2.4). Значение остальных переменных в оптимальных решениях задач (1.1)—(1.3) и (2.2)—(2.4) совпадают.
3. Постановка задачи (нелинейный случай). Ограничения в нелинейной и линейной задачах совпадают. Отличие имеет место в целевой функции. Стоимости перевозки из i -го пункта производства при i = 1, m в свой индивидуальный пункт потребления задается дифференцируемой выпуклой вниз функцией f (yt), где f (0) = 0. Аналогично стоимость перевозки в j -й пункт потребления при j = 1, n из своего индивидуального пункта производства определяется дифференцируемой выпуклой вниз функцией gj (Wj), где gj (0) = 0. Формальная запись задачи имеет вид
m n m n
ZZ jy +Zf (yi)+Z gj (wj) ^ min (3Л)
i = 1 j = 1 i = 1 j = 1
при ограничениях (1.1), (1.2) и Xy > 0,yi > 0, Wj > 0, cy > 0 — целые.
Введем новые переменные yy > 0, Wy > 0, i = 1, m, j = 1, n согласно соотношениям
n m
yi = Z Уу , wj = Z WJ,
j = 1 i = 1
где Wy = uiy. После чего ограничения (1.1), (1.2) имеют вид
n
Z (xy + У y) = a, i = 1, m, (3.2)
y = 1
m
Z (Xij + Wij ) = j = 1n. (3.3)
i = 1
4. Метод решения нелинейной задачи. Задачу (3.1)—(3.3) будем решать декомпозиционным методом [1]. Последовательно циклически решаются mn двумерных оптимизационных задач, первая из которых имеет вид
n
Z (x1j + Уу ) = al, (4.1)
у = 1
m
Z(Xi1 + Wi1 ) = b1, (4.2)
i = 1
n m
Z Cy x1j + f1 y(y1 y)) + Z(Ci1Xi1 + g1(wi1>> ^ min, (4.3)
y = 1 i = 1
где c1y = c2 = Cyl 2,i = 1,m, j = 1,n.
Порядок вычислений при решении задачи (4.1)—(4.3) зависит от соотношения ее коэффициентов. Предположим, что
cn = ch + c21 < min(4 + c2). (4.4)
i *1 j * 1
Тогда решается задача
f1 (u) + g1 (u) + Cj (min(abb1) - u) ^ min, (4.5)
здесь u заменяет собой y11 и равное ему w11. Обозначим через u* минимум в (4.5). Пусть А/1 (u*) < min % и Ag1 (u*) < min Сд и b1 > a1,
1 < j < n 1 < i < m
j * 1 i * 1
здесь Af (u*) = f1 (u*) - f1 (u* - 1), Ag1 (u*) = g1 (u*) - g1 (u* -1). Тогда при подстановке решения (4.5) в (4.1) и (4.2) ограничение (4.1) выйдет на равенство. Для дальнейшего сформируем следующую подзадачу. Обозначим
1 .12 .2 c1 х - min c^, cii1 - min c(1
1 < j < n 1 < i < m
j * 1 i * 1
и будем искать u из условия
g1 (u* + u) + c21 (b1 - a1 - u) ^ min. (4.6)
Затем u* и x* из решения задачи (4.6) подставляем в (4.2). Если при этом (4.2) не выполняется как равенство, то формируется новая задача вида (4.6) и аналогично до тех пор, пока (4.2) не выполнится как равенство. По построению решения задачи (4.1)—(4.3) и в силу неравенства (4.4)
1 2
очевидно, что можно найти новые c11 и c11, удовлетворяющие неравенствам
1 ^ . 1 2^.2 cn s min cj и cn < min ca.
j * 1 i * 1
После чего становится ясным, что с новыми и c121 объединение оптимальных одномерных задач с ограничениями (4.1) и соответственно (4.2) будет совпадать с оптимальным решением двумерной задачи (4.1)—(4.3). Далее рассмотрим случай, когда после решения задачи (4.5) имеет
место неравенство А/1 (u*) > c^i. В качестве решения задачи (4.5) в этом случае принимается наибольшее целочисленное u, удовлетворяющее неравенству АД (u*) < cj. Затем для завершения работы с c11 и определения величины wy находится наибольшее целочисленное u, удовлетворяющее неравенству
с. + А, (и* + и)< еп. (4.7)
Обозначим через и** решение задачи (4.7). Заметим, что имеет место неравенство
с. + А, (и** + и* + 1)> сп, (4.8)
1 2
и новые с11 и с11 легко находятся из соотношении
1 + 2 _ с11 + с11 _ с11,
Сп < с. + А^и** + и* + 1), (4.9)
с^ < тт^л, А^и** + и* + 1)).
В соответствии с неравенством (4.8) переменная хп получает свое значение, а задача (4.1)— (4.3) превращается в одномерную и решается далее с использованием условии вида (4.6). И снова, в силу (4.9) объединение оптимал
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.