ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 4, с. 88-98
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 519.854.33
ИТЕРАТИВНЫЙ МЕТОД ДЛЯ ТРАНСПОРТНОЙ ЗАДАЧИ С ДОПОЛНИТЕЛЬНЫМИ ПУНКТАМИ ПРОИЗВОДСТВА И ПОТРЕБЛЕНИЯ И КВАДРАТИЧНЫМ ШТРАФОМ*
© 2013 г. А. А. Соколов, А. П. Тизик, В. И. Цурков
Москва, ВЦ РАН Поступила в редакцию 11.10.12 г., после доработки 21.03.13 г.
Ранее был предложен метод решения классической транспортной задачи в целочисленной постановке, основанный на декомпозиции исходной задачи на последовательность двумерных задач с последовательным пересчетом коэффициентов целевых функций. В настоящей работе метод распространяется на случай, когда имеются дополнительные пункты и стоимость соответствующих перевозок квадратично зависит от объемов перевозки. Тем самым алгоритм напрямую переносится на важный класс нелинейных задач транспортного типа.
Б01: 10.7868/80002338813040148
Введение. Известные алгоритмы решения транспортных задач основаны на методе улучшения плана в линейном программировании (см., например, [1, 2]). Транспортная специфика приводит к оригинальным конструкциям симплекс-метода. Однако распространение на более широкие транспортные постановки иногда сопровождается большими трудностями, где указанная специфика перестает давать прозрачные построения. В данной работе решается транспортная задача с дополнительными пунктами потребления и производства. Формально это приводит к появлению новых переменных в ограничениях. Даже рассмотрение линейного функционала на этих переменных серьезно усложняет алгоритмы на основе метода улучшения плана. Здесь же берутся квадратичные штрафы за перевозку продукта в дополнительные пункты потребления и из дополнительных пунктов производства. Исходная задача становится нелинейной. Как ее решать на основе симплекс-метода — вопрос не простой. Напомним, что стандартная схема симплекс-метода в применении к классической транспортной задаче предполагает запись таблицы, в клетках которой последовательно меняются значения неизвестных количеств перевозок. При этом строятся циклы, где переносятся количества продуктов, что соответствует изменению базисных и внебазисных переменных. Данная интерпретация при дополнительных производствах и потреблениях перестает работать. Здесь используется алгоритм, предложенный в [3], основанный на последовательном решении двумерных задач о ранце с лестничной структурой. Основой для этого метода являются подходы для оптимизации сетевых задач [4—6] с булевыми переменными. Указанный алгоритм напрямую распространяется на рассматриваемый в данной работе класс квадратичных задач транспортного типа с дополнительными пунктами потребления и производства.
1. Постановка задачи. Имеется, как и в классической транспортной задаче, т пунктов производства и п пунктов потребления. В каждом /-м пункте производства задан объем производства
а, / = 1, т , в каждому'-м задан объем потребления Ьу,' = 1, п . Кроме того, имеются еще п дополнительных пунктов производства. Каждыйу'-й дополнительный пункт производства может поставлять свою продукцию только у'-му пункту потребления. Объем производства в дополнительных пунктах производства не ограничен. Стоимость перевозки из у'-го дополнительного пункта производства квадратично зависит от объемов перевозки. Имеется также т дополнительных пунктов потребления. Каждому /-му дополнительному пункту потребления продукцию может поставлять только /-й обычный пункт производства. Объем потребления в дополнительных пунктах не ограничен. Необходимо минимизировать суммарные затраты на перевозки.
Формальная запись задачи имеет вид
* Работа выполнена при финансовой поддержке РФФИ (проект № 11-01-00781-а).
XXj + yi = ai, i = 1, m, (1.1)
j = i
m
Xxn+wj = bj, j =1 n, (1.2)
i = 1
m n
XXcijXij+Xdiyj+XejwjZ min' (L3) i = ij = 1 i = 1 j = 1
xij > 0, yi > 0, Wj > 0, cij > 0, di, ej — целые. (1.4)
Здесь Xjj — количество продукта, перевозимого из пункта j в пункт i; y i — количество продукта, доставляемого в дополнительный i-й пункт потребления; Wj — количество продукта, вывозимого из дополнительного j-го пункта производства. Кроме того, будем считать Су четными числами, что не ограничивает общности рассмотрения.
2. Метод решения задачи. Первый этап. Сформируем m + n одномерных задач. Первые m одномерных задач имеют вид (i = 1, m — фиксировано)
n
X Xij + yi = ai, (2.1)
j = 1
n
X cijXij + diy2 —min, (2.2)
j = 1
1c
cij = 0 < xij < min(ai, bj), xiJ-, yi > 0 — целые. (2.3)
Задачи (2.1)—(2.3) решаются следующим образом. Сравниваем й) с с1* = штс1 (, фиксирова-
у
но). Если й , > с1*, то полагаем х у* = ш1п(а,, Ьу*). При Ьу* < а, сравниваем й , с с1** = штс1. Если
] *] *
й , > с1**, то полагаем х*** = ш1п(а , — Ьу*, Ьу**) и т.д. Если имеет место неравенство й , < с1* (сразу или
после нескольких назначений линейных переменных), то ищется целочисленный минимум со-
2 1
ответствующего квадратного трехчлена: й1у1 + с^* (ш1п(а ,, Ьу*) — у,).
Обозначим через у* оптимальное значение у,. Тогда, очевидно, х у* = ш1п(а ,, Ьу*) — у;- . Если при этом (2.1) не является равенством, то далее задачи (2.1)—(2.3) решаются как линейные (см., например, [1]). Вторые п оптимизационных задач с одним ограничением имеют вид (у фиксировано)
т
X ХЧ+ ^ = ь1> (2.4)
I = 1 т
X+ ^ (2.5)
j c--
cij = -j-, 0 < Xij < min(a, bj). (2.6)
Здесь Ху, ж* > 0 — целые. Задачи вида (2.4)—(2.6) решаются вполне аналогично задачам вида (2.1)—(2.3).
Пусть все т + п задач вида (2.1)—(2.3) и (2.4)—(2.6) решены. Если объединение оптимальных решений всех т + п задач является допустимым решением исходной задачи (1.1)—(1.4), то, очевидно, тем самым получено оптимальное решение задачи (1.1)—(1.4). Если оптимальное реше-
n
ние задачи (1.1)—(1.4) не получено, то начинаем итерационный циклический процесс решения т х п оптимизационных задач с двумя ограничениями. Второй этап. Первая двумерная задача имеет вид
п
X Хц + У1 = а, (2.7)
] = 1 т
X Хя + = Ьъ (2.8)
i — 1
n m
Ci :Xi
XCyXij + XC21 Xii + е1 + diУ2 """ min, (2-9)
j — i i = i
0 < xj < min(bj). (2.10)
Здесь Xjj, yi > 0, w1 > 0 — целые. Задача (2.7)—(2.10) решается следующим образом. Единственной общей переменной в (2.7) и (2.8) является x11. Поэтому решение задачи (2.7)—(2.10) зависит от
i 2
соотношения между c11 = cii + cii и другими коэффициентами в целевой функции (2.9). Пусть
i 2 i 2
cii < min{ cij + cti, cij + ei, ca + di, di + ei}. (2.11)
i,j * i
Тогда, очевидно, что в оптимальном решении задачи (2.7)—(2.10) x11 = min(a1, ¿1), после чего задача (2.7)—(2.10) распадается на две одномерные, рассмотренные выше. Определим новые значения cji и c2n следующим образом. Возьмем целочисленные значения c^ и c12i , подчиняющи-
i2
еся условиям cii < d1, cii < e1. Пусть
i 2 i 2 cii = min{cij + cji, cij + ei, cii + di, di + ei} = di + ei.
i,j * i
Очевидно, что тогда c^ = d1, c2i = e1. При новых значениях cji и cf1 объединение оптимальных решений соответствующих одномерных задач будет совпадать с оптимальным решением задачи (2.7)—(2.10). В общем случае сначала, исключив из рассмотрения общую переменную, решаются две одномерные задачи. Далее вычисляются следующие величины: Ди0= d1 [(yf )2 — (yf —
- 1)2] + ej(wf )2 - (wf - 1)2], Д«1 = d1[(yf )2 - (yf - 1)2] + c2„i , Ды2 = cij. + e1[(wf )2 - (wf - 1)2], Ди3 = cj + c^ . Здесь yf , wf - значения переменных y1, w1 в оптимальных решениях одномерных задач без x11, тогда как c1 jf , cn - максимальные коэффициенты при положительных значениях переменных x1y- и x(1 соответственно. Если yf = 0 (или wf = 0), то в выписанных выше выражениях считаем, что yf - 1 = 0 (соответственно wf - 1= 0) и вычисляем max Дик.
0 < к < 3
Если max ДUk — Д«з и cn > c^-* + c;»i , то двумерная задача решена. При этом cn > c^-* и cn > c;»j .
0 < к < 3
Если max Дик — Д^з и cn — c^-* + ci# i , то, обозначив через xff и xf значения соответствую-
0 < к < 3
щих переменных в оптимальных решениях одномерных задач, в двумерную задачу запишем
i i i 2 2 ограничения x1y-„ + x11 = xj, xif1 + x11 = xn , cii = c1j* и cii = cif1 .
i2
Если max Дик = Ди3 и c11 < c^* + cfl , то x11 увеличивается на min{x1jf, xif1} (или до своего макси-
0 < к < 3
мума). Если при этом x11 достигает максимума, то решение двумерной задачи окончено и c^ < cj ,
2 2 -
c11 < cP1 . В противном случае пересчитываются Дик, к = 0, 3 , и процесс решения продолжается.
Если max Аик = Ди2, то при c11 > Ди2 решение двумерной задачи окончено и cu > c ly-*, еи >
0 < к < 3
> ех[(wf)2 - (w* - 1)2].
При c11 = Аи2 полагаем c^ = c Jy* , ch = e 1 [(w*)2 - (w* - 1 )2]. Записываем x 1 1 + x 1y* = x**, xn + + w1 = w* , x11 < 1. На этом решение двумерной задачи окончено. При c11 < Аи2 по минимуму квадратного трехчлена е1и2 + c11(a1 — и) + с1у*и находим новые значения w1, x11 и x1y*. Минимизация квадратного трехчлена осуществляется до наибольшего и, при котором Аи2 перестает быть максимумом. Далее вычисляются новые значения Аи0, Аи2 и, возможно, Аи3 (если новое значение x1y* = 0), и процесс решения продолжается.
Если max Аик = Аи1, то при c11 > Аи1 решение двумерной задачи окончено и c 1 1 > d1[(у* )2 —
0 < к < 3
- (у* - 1)2], cfi > c/*i.
Если c11 = Аи1, то ci1 = d1[(у* )2 — (у* — 1)2], cп = c;*1 и записываем x11 + x;*1 = x**1, x11 + y1 = = у* . Решение двумерной задачи на этом окончено.
При c11 < Аи1 по минимуму квадратного трехчлена d^2 + c11(a1 — и) + c;*1 u находим новые значения y1, x11 и x(*1. Здесь минимизация осуществляется до наибольшего и, при котором Аи1 перестает быть максимумом. Вычисляются новые значения Аи0, Аи1 и, возможно, Аи3 (если новое значение x(*1 = 0), и процесс решения продолжается.
Если max Аик = Аи0 > c11 и при решении одномерн^тх задач мы получили у* = r> 0 и w* = r +
0 < к < 3
+ p, p > 0, то для нахождения новых значений y1, x11 и w1 ищем минимум квадратного трехчлена
22 e1 (и + p) + c11 (min (a у, b1) - и) + d1 и . (2.12)
Минимизация (2.12) осуществляется до наибольшего целочисленного и, при котором Аи0 перестает быть максимумом. Глобальный минимум квадратного трехчлена (2.12) достигается при
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.