ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2007, том 43, № 2, с. 111-117
МЕТОДЫ ОПТИМИЗАЦИИ
ДВУХСТОРОННИЙ ИТЕРАЦИОННЫЙ ПРОЦЕСС ОПРЕДЕЛЕНИЯ ПРИБЛИЖЕННОГО ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ С ОГРАНИЧЕННЫМИ МОЩНОСТЯМИ
© 2007 г. Б. И. Алибеков
(Махачкала)
Рассматривается многоэкстремальная задача размещения с нелинейной функцией цели и линейными ограничениями. Выпуклая вверх исходная функция цели заменяется кусочно-линейной функцией, и исходная задача сводится к частично-целочисленной приближенной задаче. Для решения приближенной задачи предлагается двухсторонний итерационный метод определения плана, близкого к оптимальному плану. На каждой итерации решаются транспортные задачи и определяется локально-оптимальное решение исходной задачи. Используя полученное локально-оптимальное решение приближенной задачи, можно осуществить покоординатное двухстороннее сужение области допустимых решений исходной задачи. С помощью оптимального решения задачи размещения с ограниченными мощностями сужается область допустимых решений задачи размещения с ограничениями на мощности в вариантной постановке. Определяется план, принадлежавший новой области, полученной путем исключения из множества допустимых решений некоторых неоптимальных планов, доставляющий минимум целевой функции исходной задачи. Оценивается снизу значение целевой функции, соответствующее полученному решению. Приводятся описание алгоритма решения задачи размещения и анализ эффективности метода по экспериментальным расчетам.
1. ВВЕДЕНИЕ
Рассматривается обобщенная задача размещения. В отличие от классической постановки многоэкстремальная задача размещения имеет ограничение сверху по мощностям перерабатывающих предприятий и нелинейные функции производственных затрат в непрерывной и вариантной форме. Допускается случай, когда функция ф/у) = ^(у^/у, (где Ц - производственные функции, у, - мощности) не возрастает для всех у, > 0. Часто в экономических задачах увеличение мощности производства приводит к уменьшению производственных издержек на единицу перерабатываемого сырья. В задачах с большими размерами приходится строить итерационный процесс, где на каждой итерации необходимо исследовать локальные задачи для определения локально-оптимального решения. При этом используются свойства функцииЦ). В классических задачах размещения допускается, что функцииимеют вид= А, sign(yj) + gj(yj), где gj(yj) -строго вогнутые или линейные неотрицательные и возрастающие функции текущих производственных затрат, а А, - положительные фиксированные производственные затраты (капиталовложения). Для такого класса функцийфункция ф7(у7) не возрастает при у, > 0. Следовательно, наше допущение не сужает, а расширяет класс решаемых задач.
2. ОПРЕДЕЛЕНИЯ ПРИБЛИЖЕННОГО ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ С ОГРАНИЧЕННЫМИ МОЩНОСТЯМИ
Экономико-математическая формулировка задачи размещения имеет вид (Алибеков, 1975): в некоторой области (республике, районе и т.д.) имеются т пунктов производства сырья и п пунктов его переработки. К пунктам переработки относятся действующие предприятия и предприятия, которые планируется строить или расширить. Зная объем производства сырья а, > 0 в каждом пункте ¡, себестоимость транспортировки единицы сырья с,, функцию расходаf(yj) переработки сырья у, и максимально допустимую мощность , предприятий, надо определить план х = ||х,||т х п распределения сырья между предприятиями так, чтобы суммарные затраты на транспортировку и переработку были минимальными, т.е. найти план х = ||х,||т х п, минимизирующий функцию
т п п
* (х) = XX с1]х1] + X f](y]) (1)
i =11 = 1 1 = 1
при условиях
n
XX'J = a, i = 1' •••' m; (2)
j = i
m
Xxy = yj- v-' j =1'-'n; (3)
i = 1
x- > 0; i = 1' •..' m; j = 1, • .., n. (4)
Для решения задачи (1)-(4) автор предлагает двухсторонний итерационный метод определения плана, близкого к оптимальному. Аналогичный односторонний итерационный метод приводится в (Алибеков, 1975), общая схема метода изложена в (Алибеков, 2002), а формальное описание двухстороннего метода определения оптимального плана многоэкстремальной задачи типа размещения - в (Алибеков, 1979). Обозначим через
In m т
x: XXij = at; XXij - v-; x- > 0; i = 1, • .., m; j = 1, • .., n
j =1 i =1
множество планов, удовлетворяющих соотношениям (2)-(4). Имеет место следующая теорема. Теорема 1. Если Hx непустое множество и y^1 = max{yr : yr = Xm = i x*r; T1(x*) = min { Tj(x)}},
x e Hx
y(r2) = max{yr : y.=xm= 1 x*r; t2(x*)=niin {ад^ „де ti(x)=xn=1' j Ф r xm= 1 cij) x-+Xm= 1 c<> x.+/r(yr),
T2(x) = Xn =1'j,rXm=1 cjxj + Xm=1 Cir^ir + /.(уЛ cj > c?); i = 1 .. m;j = 1, .. r - 1 r + 1, .. n,
(1) V'm (1) ^ (2) V'm (2) то имеет место неравенство yr = X. = 1 xir > yr = X. = 1 xir .
Мощность любого предприятия ограничена снизу некоторой величиной. Поэтому исследуем
функцию /Öj), j = 1, ..., n, на интервале 0 < 5 - yj - ß = max{ vj}, полагая /(yj) = при 0 < yj < 5 и
j
yj > ß, /(y) = 0 при yj = 0. Предположим, что функция /(y) - кусочно-непрерывная, а ф-(у) = /(у)/у- - не возрастающая для всех у- из интервала 5 - y- - ß. В интервале 5 - y- - ß выберем p точек так, чтобы 5 = bl < ... < bp < bp + 1 = ß + £, где e > 0 - малое число. Функция /(yj) непрерывна на каждом отрезке [bk, bk + J.
Обозначим ё,к = (Ьк + 1 - Ьк) 1^ +1 ф;- (()&, = ф/5). Тогда (1)-(4) можно аппроксимировать следующей задачей: найти план х = ||хг:/||т хп, минимизирующий функцию
р л
z(x) = XX c-+X dJkXik
i = 1 j = 1V k=1 /
x- (5)
при ограничениях (2)-(4) и условии, что Х,к = 1, если у, е [Ьк, Ьк + 1), в остальных случаях Х,к = 0. На практике/(у,) задается не в аналитической форме, а в виде таблицы. Таким образом, построенная нами приближенная задача - это реальная экономическая задача, в которой производственные затраты на единицу перерабатываемого сырья заданы в табличном виде. К такой задаче применим метод динамического программирования, согласно которому для каждого у, для
которого X" = 1 У, = ХГ= 1 а', 0 - У, - V, решается соответствующая транспортная задача. Число
транспортных задач будет очень велико, поэтому этот метод практически не пригоден. Ниже описан приближенный метод решения задачи (2)-(5), где число транспортных задач не превышает п х р. Если бы заранее были известны оптимальные значения мощностей у,, можно было бы заменить /(у,) соответствующими линейными аппроксимациями и, решив получившуюся транспортную задачу, получить точное решение (2)-(5).
Предлагается использовать следующий процесс. Пусть у, - оптимальные значения мощностей у, , = 1, ..., п; с, - соответствующие им линеаризованные транспортные коэффициенты
функции (5): с, = с, + , где О, определяются условиями Ь§ < у, < Ьо.+1;, = 1, ..., п. Последовательно для г = 1, ..., п вычисляются значения мощностей уг оценивающие уг сверху и снизу. В этих целях для, = 1, ..., п;, Ф г выбираем первую аппроксимацию функциит.е. берем у = 1 (у = 1,р - 1, 2,р - 2, ..., [р|2],р - [р|2], где у - номер аппроксимации, [р|2] - целая часть числар|2, тем самым мы строим функцию, где коэффициенты при неизвестных х, фиксированы, а при хг могут меняться), и минимизируем функцию
п т / т / р \\
^г(х) = X Х(с,+,х, +
, = 1, , Ф г1 = 1
Чг = 1
сгг + X dгkK. \ к = 1
гк
(6)
на множестве
Нх = 1 х : X хг, = а; X хг, < ^; хЧ > 0; 1 = 1 "" т; , = 1'
, = 1
г = 1
Затем выбираем ее последнюю аппроксимацию, т.е. у = р - 1, и еще раз решаем задачу минимизации функции (6) (см. (Алибеков, 2002)) на множестве Нх. Решив пару задач, определяем планы х(у, г), х(р - у, г) е Нх, доставляющие минимум функции (6), у = 1, ..., [р|2]. Очевидно, что имеет место неравенство с, + dj1 > с, + djo > с, + djP - ь так как фДу,) = f](yj)lyj - невозрастающая функция для всех у, из интервала 5 < у, < р. Следовательно, из теоремы 1 следует неравенство
уг( 1, г) = Xх,г( 1, г)> уг = Xх,г > уг(р -1, г) = X х,г(р -1, г).
г = 1 г = 1 1 = 1
В (6) нелинейной является лишь составляющая с номером г. Минимум (6) на множестве Нх можно получить за конечное число итераций, каждая из которых состоит в решении транспортной задачи. Сначала, = г для fг(yг) выбирается т-аппроксимация, где т = тгп(О, р - 1), а О определяется из условия ЬО < ,г < ЬО + Пусть у(1) (у),, = 1, ..., п, - значения мощностей, полученные в результате решения соответствующей транспортной задачи. При у = 1 транспортные издержки находятся из формул:
с, '(у) = , 1) = сч + dn, , Ф г; с!;)(р - у) = 4\р-1) = с^ + djp
, Ф г,
4%) = с,+1
„(1)
(р - У) = с, + <
с^ = с^ = сгг + dгт, т = min(О,р - 1), а О определяется из условия ЬО < ,г < ЬО + Оставив для всех , Ф г прежнюю линейную аппроксимацию, для, = г возьмем аппроксимацию с номером ю^) (номер интервала, которому принадлежит у^)). Решив соответствующую транспортную задачу, получим
.(2)
.(2)
у, , причем уг > уг2. Теперь для, = г возьмем аппроксимацию ю^, где Ь (2) < у г' < Ь (2) ,, и
Юг Юг + 1
решим новую транспортную задачу и т.д. Процесс заканчивается, как только у^ (где 5 - номер
итерации) и у^ +1) попадут в один и тот же интервал. В этом случае транспортные задачи двух последовательных итераций 5 и 5 + 1 будут идентичны и их оптимальные решения совпадут. Таким образом, число итераций, необходимых для минимизации (6) на множестве Нх, не превосходит р.
При минимизации (6), используя теорему 1, можно сужать область Нх, вводя после решения очередной задачи и получения значенияуг = уг(у, г), уг = уг(р - у, г), г = 1, ..., п ограничения вида
.(2)
X хгг < уду, г), X хгг > уЛр - У> г), У = ^ ...Др/2] .
Таким образом, будут решаться задачи:
^(х(т, г)) = тт^тг(х); т = у; р - у,
Н (г)
т
т
т
т
т
г = 1
г = 1
Н(г) = {X : X е Их, £Т=1 ^ <У(Ъу), ХГ=1 хч <- ^Л] = 1, ••, г + 1}; У = 1, ..., [р/2];у/т, г) =
где Н(г) = {х : х
= ХГ= 1 хг (т, г); ||х(т, г)||Г х п(т, г), т = у,р - у, - оптимальные планы задач (7).
Если бы были известны те у, для которых 0у (у у) = 1 или 0у (у у) = р - 1 (номер интервала, которому принадлежит оптимальное значение уу), то, увеличив номер аппроксимации у или уменьшив р - у на единицу для остальных у и применив снова описанный выше процесс, мы получили бы боле
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.