ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 4, с. 56-62
МЕТОДЫ ^^^^^^^^^^^^^^ ОПТИМИЗАЦИИ
УДК 586.6
ОПТИМИЗАЦИЯ СТРУКТУРЫ ПРОИЗВОДСТВЕННЫХ СИСТЕМ*
© 2007 г. В. М. Колбанов, В. Ю. Леонов, В. Г. Медницкий, Ю. В. Медницкий
Москва, ВЦ РАН, ЦЭМИ РАН Поступила в редакцию 10.12.06 г.
Показано, что оптимальные решения в одном классе задач линейного программирования с частично-целочисленными переменными можно построить на первом шаге метода декомпозиции Данци-га-Вулфа [1]. Использование этого результата позволяет существенно упростить алгоритмы оптимизации структуры производственных систем, причем независимо от размерности исходной задачи.
Введение. Конструкцию, с помощью которой строятся различные варианты задачи с фиксированными доплатами [2], наиболее просто получить, если каждой переменной Xj, j е J, в одном из канонических представлений [3] задачи линейного программирования (ЛП)
minj^CjXj £gjXj = b, i е I; Xj > 0, j е J J (0.1)
поставить в соответствие переменную дискретного типа
5j е { 0, 1}, j е J, (0.2)
полагая, что при 5j = 0 процесс1 j в (0.1) не используется (Xj = 0), а при 5j = 1 может использоваться с интенсивностью lj < Xj < т. В функционал задачи переменная 5j входит с коэффициентом ek, где kj -
условно-постоянные затраты, а e - коэффициент их приведения к переменной части функционала CjXj, пропорциональной интенсивности использования процесса. Заменяя (0.2) неравенствами
0 < 5j < 1, j е J, (0.3)
все указанные выше условия можно формализовать в задаче ЛП, приведенной вместе с двойственной задачей в табл. 1, где матрицы L, M -диагональные с элементами j т, j е J, на главных диагоналях, E0, E - единичные матрицы размерности |/|, J| и все компоненты вектора J в соответствии с (0.3) равны единице (в дальнейшем,
*
Работа выполнена при финансовой поддержке РФФИ (проект 06-01-81020).
1 С технико-экономическими параметрами c, kj, j, mj, gj , i е /.
2 Величина этих затрат не зависит от интенсивности использования процесса.
3 Во всех приводимых ниже таблицах NTV - имена и типы переменных; TR - типы ограничений; R/F - элементы правых частей (функционалов); MIN, MAX - направления поиска экстремума; <> - конец секции TR.
для краткости, такие задачи ЛП будем называть оценочными).
Если из табл. 1 исключить столбец с вектором г, то, как и в (0.1), остается равенство GX = Ь, которым в обычной интерпретации [3] формируются ограничения на объемы выпуска товарной продукции (b¡ > 0) или использования ресурсов и промежуточной продукции (Ь, < 0). В табл. 1 эти ограничения модифицированы к условиям рынка [4, 5], когда какая-то часть производственной программы может быть зафиксирована вектором Ь (в силу ранее заключенных контрактов, соглашений и т.д.), а часть, входящая в вектор г, остается свободной и может устанавливаться в оптимальном решении из экономических соображений. Так как добавленная стоимость [6] в любом допустимом решении оценочной задачи при ценах р, I е I, на продукцию и ресурсы равна рЬ + рг, но константу рЬ из критерия можно удалить, то максимизируется прирост прибыли при фиксированных значениях свободного параметра е и цен (табл. 1).
1. Постановка задачи. Если неравенства (0.3) из табл. 1 исключить, дополняя оставшиеся в оценочной задаче ограничения условиями (0.2), то в последней появятся булевы переменные, значения которых можно выбирать независимо друг от друга. Такая ситуация существует не всегда. Например, если нужно выбрать один процесс из некоторой их совокупности или при строительстве
Таблица 1
NTV z X 5 > 0 TR MIN
¥ Eq -G = -b
u > 0 -E L <
v > 0 E -M <
r > 0 E < J
TR = = > <>
MAX P -c -ek R/F
очередями, когда последующая может воити в допустимое решение только при наличии в нем предшествующей, то все такого рода особенности можно отобразить в табл. 1 с помощью дополнительных ограничении. Для краткости любую из таких задач будем называть исходной (или задачей ЧЦЛП из соответствующей таблицы). Таким способом можно построить довольно много различных задач, представляя каждую из них либо в форме оценочной задачи ЛП, либо задачи ЧЦЛП в обычноИ постановке (без вектора г) или модифицированной с помощью вектора г (как в табл. 1). Анализ этих задач в обычноИ постановке не очень интересен, так как рекомендовать для получения их оптимальных решениИ что-нибудь кроме общих методов дискретного или линеИно-го программирования [2, 3], как правило, не удается. Однако в модифицированной форме связь между задачами ЛП и ЧЦЛП нередко устроена так, что алгоритмы построения их оптимальных решениИ существенно упрощаются [4, 5]. Соответственно цель работы заключается в получении при исследовании некоторых задач ЛП в мо-дифицированноИ форме простых алгоритмов решения задач ЧЦЛП, возникающих на основе модели с фиксированными доплатами.
2. Независимый выбор вариантов. Поскольку в оценочноИ задаче из табл. 1 нет ограничениИ на знаки компонент вектора г, то в допустимых решениях двоИственноИ задачи выполняется равенство
Р = V, (2.1)
т.е. значения оценок Канторовича [7] для всех видов
продукции и ресурсов4 в любом из ее допустимых решениИ совпадают с внешними ценами, указанными в критерии оценочноИ задачи. Это существенно упрощает получение оптимальных решениИ двоИ-ственных задач ЛП из табл. 1. ДеИствительно пусть ] е J - вектор-столбец матрицы G,
= - С
V,
= тах[_0, £,]; и, = тах[_0, -еА,
(2.2) (2.3)
о, = Vjmj - и,1] - вк]; г, = тах[_0, о,(2.4)
а значения компонент векторов X, 5 находятся из условиИ
х = |т]5], если £] >0;
] [ I]5], если £] < 0; X] е ]5], т]5,], если е, = 0,
(2.5)
(2.6)
5] =
Г0, если о] < 0; [1, если о] > 0;
5 / е |_ 0, 1 ], если о = 0.
(2.7)
(2.8)
Как видно из (2.6) и (2.8), если о/£/ = 0, то подходящее значение для X; определено неоднозначно. Выбирая в каждом из таких случаев одно из них произвольно, после выполнения операциИ (2.2)-(2.8) для всех] е J получим одно из возможных значениИ вектора X, с которым, заканчивая вычисления, остается наИти вектор
г = GX - Ь. (2.9)
Теорема1. Любые наборы векторов г, X, 5 и V, и, V, г, построенные в (2.1)-(2.9), оптимальны в двоИственных задачах ЛП из табл. 1.
Независимо от выбора значениИ 5у в (2.8) и (или) Xj в (2.6) оба набора удовлетворяют с дополняющеИ нежесткостью всем ограничениям соответствующих двоИственных задач. Их оптимальность следует из общеИ теории ЛП [3].
Следствие! Если при каждоИ реализации в (2.1)-(2.9) возможности (2.8) 5j е {0, 1}, то лю-боИ из построенных таким способом наборов векторов г, X, 5 будет оптимален в задаче ЧЦЛП из табл.1.
По построению решение г, X, 5 допустимо в задаче ЧЦЛП из табл. 1, но по теореме 1 оно оптимально в оценочноИ задаче, а значит, и в задаче ЧЦЛП из табл. 1 [2].
Теперь покажем, что при условиях
0 < ¡^ < т< + ^; вк. > 0, ] е 3,
(2.10)
алгоритм (2.1)-(2.9) можно существенно упростить.
Лемма 1. При выполнении условиИ (2.10) неравенство 5j > 0 в оптимальном решении оценочноИ задачи из табл. 1 допустимо тогда и только тогда, когда выполняется неравенство
£] т] - в к] >
(2.11)
ДеИствительно, так как из (2.3) имеем V/ е J : VjUj = = 0, то значение о/ в (2.4) фактически находится из соотношениИ
о] =
[ет - вк], если > 0, еX - вк,, если е, < 0.
(2.12)
Здесь надо отметить, что при исключении из табл. 1 вектора г их значения пришлось бы вычислять в процессе оптимизации решениИ пары двоИственных задач ЛП общего
вида.
Если (2.11) нарушается, то из (2.10) и (2.12) о/ < 0, а 5j = 0 в силу (2.7). Если же (2.11) выполнено, то, как следует из (2.10), ^ > 0, в силу (2.11) и (2.12) о/ > 0, и таким образом либо 5j = 1 в соответствии с (2.7) или в случае (2.8) может быть выбрано в (0, 1] произвольно.
NTV z 8 > 0 TR MIN
¥ Eo -A = -b
r > 0 E < J
TR = > < >
MAX P —c R/F
Следствие 2. При выполнении условий (2.10) в оптимальном решении оценочной задачи из табл. 1 имеют место равенства
у =
mj8 j >
j e J.
(2.13)
утверждения позволяют вскрыть некоторые тонкости в механизме формирования оптимальных решениИ задачи ЧЦЛП из табл. 1.
Следствие 4. Если при условии (2.10) приемлемо любое значение е > 0, то в оптимальное решение задачи ЧЦЛП воИдут все процессы, для которых е- > 0 (и только они).
В соответствии с леммоИ 1 е- < 0 ^ 5,- = 0. Пусть е- > 0. В силу (2.10) значение ej > 0 можно выбрать так, чтобы выполнялось неравенство ет - е> 0. Если е - наименьшее из таких е, то в соответствии с (2.12) и (2.7) е > 0 ^ 8; =1.
Поскольку из (2.10) следует, что к > 0, то удобно ввести безразмерные показатели
Если 8j = 0, то множитель в правоИ части (2.13) можно выбрать как угодно. Если же 8j > 0, то, как было показано при доказательстве леммы 1, е- > 0 и значение Xj устанавливается в соответствии с первым условием в (2.5), откуда и получается равенство (2.13).
В задачах оптимизации развития производства [8] величинами с- > 0 обычно были заданы коэффициенты текущих затрат, а критериИ и матрица ограничениИ А = Щ/|| формировались значениями
полных приведенных затрат с], / е J, и объемов производства (а- > 0) или затрат (а- < 0). Формируя эти величины с помощью соотношениИ
С} = с]т] + вк}, ] е 3; А = ОМ, (2.14)
рассмотрим оценочную задачу, представленную в табл. 2.
Следствие 3. При выполнении условиИ (2.10) и (2.14) (где коэффициенты с- могут иметь любоИ знак) оптимальные решения задач ЧЦЛП из табл. 1 и 2 совпадают.
Так как в соответствии с (2.14) рА - С = еМ - ек, то оптимальные значения величин 5/, / е J в оценочноИ задаче из табл. 2 находятся из условиИ, указа-ных в лемме 1.
Таким образом, нижние границы I/ для оптимального решения оценочноИ задачи (или ЧЦЛП) из табл. 1 не существенны. Этот результат далеко не очевиден, так как, в принципе, оптимальное решение последнеИ из указанных задач можно искать перебором. На произвольном шаге п такого процесса для определения значениИ 5/, / е J, вместо (2.4), (2.7) (или (2.8)) будут использоваться равенства 5/ = 0,/ е J\Jn, и 5/ = 1,/ е Jn, где Jn, п е 1, 23 -некоторым образом упорядоченная совокупность всех подмножеств из Л Естественно ожидать, что величины е-, / е Jn, могут иметь любые знаки, и предвидеть, что в оптимальны
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.