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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Труды Петрозаводского государственного университета
Серия «Математика» Выпуск 13, 2006
УДК 519. 85
Р. В. Воронов, В. В. Поляков
ОБ ОДНОМ СВОЙСТВЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПСЕВДОИНТЕРВАЛЬНЫМИ ПЕРЕМЕННЫМИ
В статье показано, что число положительных переменных в оптимальном решении задачи линейного программирования с псевдоинтервальными переменными не превышает числа ограничений задачи.
В работах [1−3] было показано, что при моделировании технологических комплексов непрерывного действия в целях решения задач координации функционирования элементов технологической системы возникает следующая математическая задача:
должны выполняться для всех значений Xj, попадающих в интервалы:
(1)
jeN
ограничения
(2)
jeN
Xj € [wj — aj- Wj + aj ] при Wj & gt- aj, ] € Ы,
Xj € [0- Wj + aj] при 0 & lt- Wj & lt- aj, ] € Ж,
Xj = 0 при Wj =0, ] € Ж,
Wj & gt- 0, ] € Ж,
(3)
(4)
(5)
(6)
© Р. В. Воронов, В. В. Поляков, 2006
где Wj — основные переменные задачи, определяющие интервалы возможных значений переменных х, — х, — вспомогательные переменные, которые могут быть названы псевдоинтервальными, со срединными значениями интервалов Wj, необходимые для определения условий (2)-(5) (ограничения (2) должны выполняться для любого значения псевдоинтервальной переменной х, принадлежащего интервалу, определяемому соотношениями (3)-(5) — (Tj — положительная величина, определяющая ширину интервала значений 3-й псевдоинтервальной переменной) — а, 6*, с, — константы.
Задача (1)-(6) вследствие специфического характера переменных х, не является стандартной задачей, и требуется поиск методов ее решения. Как показано в [4], задача (1)-(6) преобразуется к следующей задаче нелинейного программирования, часть переменных которой — логические:
2 с, wj ^ max, (7)
jeN
(а, Wj + а+ o-jZj + а- WjZj + |а, 1 о, у,) & lt- 6*, г € М, (8)
jeN
о, у, & lt- Wj & lt- о, Zj + В, у,, 3 € Ж, (9)
Zj + у, & lt- 1, 3 € Ж, (10)
, У, € I0,1}, 3 € ^ (11)
Wj & gt- 0, 3 € Ж, (12)
где В, — большие числа, а преобразования «+» и «-» определяются следующим образом:
а, если, а & gt- 0,
0, иначе,
— а, если, а & lt- 0,
0, иначе.
Решение возникающей нелинейной задачи (7)-(12) может быть сведено к решению 31 (|Ж| - количество элементов множества Ж) задач линейного программирования, получаемых путем фиксации значений переменных у, и Zj. Таким образом, вычислительная сложность решения этой задачи экспоненциально зависит от числа основных пере-
менных, задача является вычислительно трудоемкой и, следовательно, требуется поиск более эффективных методов решения.
Далее будет доказано, что если задача (1)-(6) имеет решение, то, подобно задаче линейного программирования, существует оптимальное решение, содержащее не более |М | ненулевых переменных Wj. В этом случае решение нашей задачи может быть сведено к направленному перебору базисных решений задач вида:
cjWj ^ max, (13)
jEN
'-'-У^ aijWj + wj = bj, i € M, (14)
jEN
Wj & gt- 0, j € N, (15)
Wj & gt- 0, i € M, (16)
каждое из которых также содержит не более чем | M| ненулевых переменных. Здесь wj — дополнительные переменные, bj — правые огра-
ничения, вид которых уточняется ниже.
Теорема 1. Если задача (1)-(6) имеет решение, то существует ее решение, содержащее не более |М | положительных значений переменных Wj.
Доказательство. Пусть W* - оптимальное решение задачи (1)-(6). Введем в рассмотрение обозначения трех индексных множеств — одно для нулевых, два других — для положительных значений величин w*:
No = {j | j € N, w* = 0},
Ni = {j | j € N, 0 & lt- w* & lt- a j},
N2 = {j | j € N, w* & gt- aj}.
Так как для значений w* (j € N) выполнены условия (2)-(5), то справедливо неравенство:
53 a+ (w* + aj) + '-^2 ajj (w* + sign (ajj)aj) & lt- bj, i € M,
jeN i jeN
или
XI a+w* + X a+aj + ajjw* + X |ajj|aj & lt- bj, i € M,
jeN jeN jeN jeN
где
или, иначе,
+ i ajj, если ajj & gt- 0,
jj 0, в противном случае,
Y1 a+w* + X ajjw* & lt- bj- Y1 a+aj- X |ajj |aj, i € M. (17)
jeN jeN jeN jeN
Теперь мы получаем возможность рассмотреть следующую задачу линейного программирования, в которой срединные значения псевдо-интервальных переменных исходной задачи Wj (j € Ni U N2) выступают в качестве обычных переменных, причем N1 П N2 = 0, N С N, N2 С N, а wj — дополнительные переменные, необходимые для приведения задачи к каноническому виду:
cjWj ^ max, (18)
jeNuN
X a+wj + X ajjwj+щ = bj- a+aj- X |ajj |aj, i € M, (19)
jeN jeN jeN jeN
Wj & gt- 0, j € TVi U N2, (20)
wj & gt- 0, i € M. (21)
Рассмотрим оптимальное допустимое базисное решение (W, w) задачи (18)-(21), включающее переменные Wj (j € N1UN2) и wj (i € M).
Очевидно, что значение целевой функции (18) на решении г& amp- не меньше, чем значение целевой функции (1) на решении w* (в силу того, что гЪ является оптимальным решением задачи (18)-(21)). Покажем, что гЪ является решением задачи (1)-(6).
Может оказаться, что в решении гЪ некоторая базисная переменная гЪ, из множества Ж1 будет не меньше, чем о, что не согласуется с определением множества Ж1. Аналогичным образом, может оказаться, что некоторая переменная гЪ, из множества Ж2 будет меньше, чем о, что не согласуется с определением множества Ж2. Но мы можем на основе базисного решения гЪ задачи (18)-(21) сформировать новые множества Ж1 и Ж2, по аналогии с определением множеств Ж1 и Ж2:
Л = {313 € ж, 0 & lt- г, & lt- о,},
Ж2 = {313 € ж, г, & gt- о,}.
После этого нужно показать, что из равенств (19) следуют неравенства
X а+г + X а, г & lt-6 — X а+о — X |а,|о, г € M, (22)
,?N1 ,?N2 ,?N/1 ,?N2
что и будет сделано ниже.
Введем следующие обозначения:
Ж10 = {3 | 3 € Жь гЪ, = 0},
Ж11 = {313 € ЛЛ1, 0 & lt- г, & lt- о,},
Ж12 = {3 13 € Ж1, гЪ, & gt- о,},
Ж20 = {313 € Ж2, г, = 0},
Ж21 = {313 € ЛЛ2, 0 & lt- г, & lt- о,},
Ж22 = {3 13 € Ж2, г, & gt- о,},
с использованием которых перепишем неравенства (22) для переменных и), в следующем виде:
X а+г + X а, г & lt-
,?/^1ои7У& quot-11и7У"-12 ,?7У20и7У21иТУ22
& lt-6 — X а+о — X |а,|о, г € М.
,?/^1ои7У& quot-11и7У"-12 ,?7У2ои7У21иТУ22
Так как гЪ, = 0 для 3 € Ж10 и Ж20, то
X а+г + X а, г & lt-
,?^'-^11и7У'-12 ,?^1и2
& lt- 6* - ^ а+о, — ^ |а,|о, г € М.
,?-N^N12, ? N21 и N22
Если а, & lt- 0 для некоторых г € М и 3 € Ж21, то, так как гЪ, & lt- о, имеем а, гЪ, & gt- а*, о,. Вычтем слева и справа такие а, гЪ, и а, о, что не изменит знака неравенства. Получим:
X а+г + X а, г & lt-
,??^11и^1и7У12 ,?^^22
& lt- 6* - X а+о, — X |а,|о, г € М.
,? N11 и N21 и N12 ,?N22
Аналогичным образом, если а, & lt- 0 для некоторых г € М и 3 € Ж12, то, так как гЪ, & gt- о, имеем а, гЪ, & lt- а*, о,. Прибавим слева и справа такие а, гЪ, и а, о,. Получим:
X а+г + X а, г & lt-
,?N^N21 ,'-?N^N22
V- V- (23)
& lt- б* а+о — |а,|о, г € М.
,?^^11и7У21 ,?7У'-12и7У22
Получившееся неравенство (23) эквивалентно неравенству (22), так как
Ni = Nii и N21, N2 = Ni2 и N22.
Поскольку переменные, не входящие в множества Nii, Ni2, N2! и NN22, равны нулю, то для переменных W выполняются ограничения задачи (1)-(6) и, следовательно, Wj является решением псевдоинтер-вальной задачи (1)-(6). Набор переменных Wj является базисным для задачи (18)-(21) и, следовательно, среди этих переменных ненулевых не более чем |M |. ?
Таким образом, можно привести задачу в комбинаторной формулировке, эквивалентную задаче с псевдоинтервальными переменными
(1)-(6):
cjWj ^ max,
jeNiUN2
X a+j'-Wj + X ajjWj + Wj = bj — X a+j'-aj — X |ajj |aj, i € M,
jeNi jeN2 jeNi jeN2
Wj & gt- 0, j € Ni U N2,
|Ni U N2| & lt- |M|,
Ni П N2 = 0, Ni С N, N2 С N.
В этой задаче искомыми являются два дизъюнктных подмножества Ni и N2 множества N. Для каждых таких подмножеств допустимое базисное решение содержит не более |M| положительных значений переменных Wj.
Следовательно, если задача с псевдоинтервальными переменными имеет решение, то всегда существует такое оптимальное решение,
которое содержит не более |М | положительных значений основных переменных Wj. Таким образом, в этой части свойства оптимального решения задачи с псевдоинтервальными переменными подобны свойствам оптимального решения обычной задачи линейного программирования. Данное обстоятельство позволяет искать эвристические алгоритмы решения задачи (1)-(6), подобные симплексному методу и связанные с направленным перебором базисных решений задач линейного программирования вида (18)-(21).
Resume
The optimization task with linear constraints of pseudo-interval variables is discussed in the article. It is proofed that if the task has optimal solution, then there is a solution that has not more than M non-zero variables (M is the number of constraints of the task).
Список литературы
[1] Поляков В. В. Об одном подходе к моделированию задач оптимального планирования работы целлюлозно-бумажного производства / В. В. Поляков //I МНТК «Новые информационные технологии в ЦБП»: Тез. докл. Петрозаводск: Изд-во ПетрГУ, 1994. С. 33−34.
[2] Поляков В. В. Некоторые аспекты моделирования работы нефтехимического предприятия / В. В. Поляков, Т. С. Терновская // Труды ПетрГУ. Сер. Прикладная математика и информатика. 2002. Вып. 9. С. 39−46.
[3] Поляков В. В. О возможности использования задач оптимизации с интервальными решениями в оперативно-диспетчерском управлении / В. В. Поляков, С. В. Поляков, Е. А. Корольков //VI МНТК «Новые информационные технологии в ЦБП и энергетике»: Мат. конф. Петрозаводск: Изд-во ПетрГУ, 2004. С. 81−85.
[4] Визерова А. В. Задачи линейной оптимизации с абсолютными интервальными переменными / А. В. Визерова, Р. В. Воронов, В. В. Поляков- Петрозаводский государственный университет. Петрозаводск, 2005. 6 с. Деп. в ВИНИТИ 15. 02. 2005, е 224-В2005.
Петрозаводский государственный университет, математический факультет,
185 910, Петрозаводск, пр. Ленина, 33
E-mail: rvoronov@karelia. ru, poljakov. v@karelia. ru

ПоказатьСвернуть
Заполнить форму текущей работой