О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных
The paper constructs and substantiates decomposition methods used to solve problems exactly and approximately. Such problems emerge when one investigates complicated integer optimization models with controllable and inexact data. Methods are based on approximation of initial problems by problems of...
Saved in:
| Date: | 2005 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Series: | Теорія оптимальних рішень |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/84932 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных / Н.В. Семенова // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 107-112. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84932 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-849322015-07-18T03:01:50Z О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных Семенова, Н.В. The paper constructs and substantiates decomposition methods used to solve problems exactly and approximately. Such problems emerge when one investigates complicated integer optimization models with controllable and inexact data. Methods are based on approximation of initial problems by problems of a simpler structure, unite and use the ideas of relaxation, linearization and the Kelley cutting plane methods. 2005 Article О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных / Н.В. Семенова // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 107-112. — Бібліогр.: 9 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84932 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
The paper constructs and substantiates decomposition methods used to solve problems exactly and approximately. Such problems emerge when one investigates complicated integer optimization models with controllable and inexact data. Methods are based on approximation of initial problems by problems of a simpler structure, unite and use the ideas of relaxation, linearization and the Kelley cutting plane methods. |
| format |
Article |
| author |
Семенова, Н.В. |
| spellingShingle |
Семенова, Н.В. О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных Теорія оптимальних рішень |
| author_facet |
Семенова, Н.В. |
| author_sort |
Семенова, Н.В. |
| title |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| title_short |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| title_full |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| title_fullStr |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| title_full_unstemmed |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| title_sort |
о решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84932 |
| citation_txt |
О решении задачи целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных / Н.В. Семенова // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 107-112. — Бібліогр.: 9 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT semenovanv orešeniizadačiceločislennojoptimizaciinavypuklyhmnožestvahvusloviâhneopredelennostidannyh |
| first_indexed |
2025-07-06T12:03:15Z |
| last_indexed |
2025-07-06T12:03:15Z |
| _version_ |
1836898997303771136 |
| fulltext |
Теорія оптимальних рішень. 2005, № 4 107
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Разработаны и обоснованы де-
композиционные методы точного
и приближенного решения задач,
возникающих при исследовании
сложных целочисленных оптими-
зационных моделей с управляемы-
ми и неточно заданными исход-
ными данными. Они основаны на
аппроксимации исходных задач
задачами более простой струк-
туры, объединяют и используют
идеи методов релаксации, линеа-
ризации, отсекающих плоскостей
Келли.
Н.В. Семенова, 2005
ÓÄÊ 519.8
Í.Â. ÑÅÌÅÍÎÂÀ
Î ÐÅØÅÍÈÈ ÇÀÄÀ×
ÖÅËÎ×ÈÑËÅÍÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ
ÂÛÏÓÊËÛÕ ÌÍÎÆÅÑÒÂÀÕ
 ÓÑËÎÂÈßÕ ÍÅÎÏÐÅÄÅËÅÍÍÎÑÒÈ
ÄÀÍÍÛÕ*
Введение. В настоящее время математиче-
ские модели дискретной оптимизации охва-
тывают широкий круг прикладных задач,
которые возникают при принятии оптималь-
ных проектных, технологических и экономи-
ческих решений. Кроме того, ряд теоретиче-
ских проблем самой математики может быть
сформулирован в виде дискретных оптими-
зационных задач. Поэтому всё более возрас-
тает необходимость интенсивного развития
теории и методов поиска решений задач дис-
кретной оптимизации [1-6].
В классической постановке задачи дис-
кретной, в том числе и целочисленной, оп-
тимизации предполагается, что исходные
данные известны точно. Однако на практике
это осуществляется редко. Исходным дан-
ным присущи неопределенность, динамиче-
ский характер, зависимость от некоторых
параметров, которые поддаются регулирова-
нию, наличие погрешностей вычислений.
Это приводит к необходимости исследования
сложных моделей и разработки эффективных
методов решения задач целочисленной оп-
тимизации. При этом исходные данные та-
ких моделей могут интерпретироваться как
управляемые, неточно заданные, случайные.
______________________________________
*
Работа выполнена при поддержке Государственного фонда
фундаментальных исследований Украины (Проект Ф7/275-
2001)
Н.В. СЕМЕНОВА
108 Теорія оптимальних рішень. 2005, № 4
Задание неопределенности посредством фиксации возможной области из-
менения исходных данных задач с учетом типов этих данных позволило иссле-
довать различные постановки задач, описывающих разнообразные моделируе-
мые ситуации, и разработать эффективные методы их решения [3-6 ].
В данной статье представлены результаты разработки и обоснования мето-
дов точного и приближенного решения задач, возникающих при исследовании
сложных целочисленных оптимизационных моделей с управляемыми и неточно
заданными исходными данными и основанных на аппроксимации их задачами
более простой структуры. Эти методы являются декомпозиционными, объеди-
няют и используют идеи методов релаксации [7], линеаризации [8], отсекающих
плоскостей Келли [9].
Исследуемые задачи имеют следующий вид:
Р: max{extr cx | c ∈C}| x∈X},
где X={x∈Z
n
| fi(x)≤0 ∀ fi∈Fi, i=1,…m}, c ∈R
n
– вектор-строка; Zn
– пространство
n–мерных целочисленных векторов из Rn
, fi : R
n
→R
1
; Fi – множество выпуклых
непрерывно дифференцируемых функций, Fi ⊂C
1
, i∈Nm={1,…,m}.
Под экстремумом будем подразумевать максимум, если данные, опреде-
ляющие вектор с, управляемые, и соответственно минимум, если данные заданы
неточно.
Оптимальным решением задачи Р является пара ( xc , ), элементы которой
c ∈C, x ∈X удовлетворяют условию
∈≥∈
∈≥∈
=
случае противном в - }|min{}|min{
;еуправляемы векторе о данные если },|max{}|max{
CccxCcxc
сCccxCcxc
хс (1)
для всех (c, x), таких, что c ∈C, x∈X .
Обозначив x0 скалярную переменную, перепишем задачу Р таким образом:
max {x0 | ∃c ∈C: x0≤ c x, x0∈R
1
, x∈X}, (2)
если данные о векторе с управляемые, и
max {x0 | ∀c ∈C: x0≤ c x, x0∈R
1
, x∈X}, (3)
если информация о векторе с задана неточно.
Очевидно, что задачи (2), (3) эквивалентны соответственно следующим зада-
чам:
max {x0 | (x0, x) ∈ I
mNi∈
U I
Cc Ff ii∈ ∈
{x0≤ c x, fi(x)≤0
, x∈Z
n
}},
max {x0 | (x0, x) ∈ I
mNi∈
II
ii FfCc ∈∈
{x0≤ c x, fi(x)≤0
, x∈Z
n
}}. (4)
Определим множества Xi={x∈Z
n
| fi(x)≤ 0 ∀fi(x)∈Fi }, i∈Nm, Xi= I
mNi
iX
∈
.
В дальнейшем будем предполагать, что множество Х ограниченное.
Определим в пространстве D
n+1
=R
1
×Z
n
множества S={(x0, x) αc∈C x0≤ c x,
x0∈R
1
, x∈Z
n
}, G={(x0, x) ∈S | x∈X }, где
О РЕШЕНИИ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ ОПТИМИЗАЦИИ НА ВЫПУКЛЫХ МНОЖЕСТВАХ...
Теорія оптимальних рішень. 2005, № 4 109
α=
∀
∃
случае, противном в -
ые, управляем векторе о данные если , с
и рассмотрим задачу следующего вида:
max {x0 | (x0, x)∈G}. (5)
На основании вышеизложенного ясна взаимосвязь между исходной задачей
Р и задачей (5). Сформулируем полученные результаты в виде теоремы 1, уста-
навливающей эквивалентность этих задач.
Теорема 1. 1. Задача Р не имеет допустимых решений тогда и только тогда,
когда множество G пусто.
2. Если (c, x) − допустимое (оптимальное) решение задачи Р и x0≤ cx (x0=cx),
то (x0, x) − допустимое (оптимальное) решение задачи (5);
c – допустимое (оптимальное) решение задачи
max {c x | c ∈C}, (6)
если данные о векторе c управляемые, и
min {c x | c ∈C}, (7)
если они заданы неточно.
3. Если (x0, x) − допустимое (оптимальное) решение задачи (5), то для опти-
мального значения целевой функции задачи (6) или (7) выполняется соответст-
венно соотношение x0≤ c x (x0=c x). Если c − оптимальное решение задачи (6)
или (7), то (c, x) − допустимое (оптимальное) решение задачи Р.
Следует отметить, что решение задачи (5) вызывает большие трудности
вследствие того, что её допустимая область описывается огромным либо беско-
нечным числом ограничений, которые сами являются довольно сложными, поэ-
тому целесообразно применение здесь сочетания процедур релаксации [7] и ли-
неаризации [8]. Для задачи (5), в том случае, когда ей соответствует задача (3),
возможно упростить процесс решения посредством применения процедуры су-
жения допустимой области. Таким образом, оптимальное значение целевой
функции задачи (5) будет нижней (верхней) границей любой своей релаксации
(сужения).
Назовём величину ri(x)=max{fi(x)|fi(x)∈Fi}, i∈Nm, отклонением точки x∈Z
n
от
границы множества Xi, а величину r(x)=max {ri(x) | i ∈I} – отклонением точки
x∈Z
n
от границы множества X. Для некоторого вектора x
j
∈Z
n
, j =1,2,…, рас-
смотрим задачу МР, имеющую следующий вид:
максимизировать x0 (8)
при условиях
x0≤
kNj∈
extr сj
x, с
j
∈С, k=1, 2,…, (9)
lNj∈
max (
j
if (x
j
) +(
j
if )′ (x
j
) (x− x
j
)≤0,
j
if ∈Fi, i∈I ⊂Nm, l=1,2,…, (10)
x∈Z
n
. (11)
Н.В. СЕМЕНОВА
110 Теорія оптимальних рішень. 2005, № 4
Если в качестве экстремума подразумеваем минимум, то задача МР есть ре-
лаксацией задачи Р. Если же под экстремумом понимаем максимум, то ограни-
чения (9) являются сужением соответствующих ограничений задачи (3).
Обозначим G(МР) множество допустимых решений задачи МР.
Лемма. Для того, чтобы точка (x0, x) из множества G(МР) принадлежала
множеству G, необходимо и достаточно, чтобы выполнялись условия
x0≤extr{cx| с∈С}, (12)
r(x) ≤0. (13)
Доказательство. Пусть точка (x0, x) ∈G(МР) принадлежит также множеству
G, т.е. (x0, x) ∈S, откуда следует, что x0≤ max {c x | c ∈C}, если данные о векторе
с управляемые и x0≤min{cx | c∈C}, если данные заданы неточно. Следовательно,
выполняется неравенство (12). Условие (13) вытекает из принадлежности (x0, x)
множеству G и определения величины r(x). Достаточность условий (12), (13)
следует из определения множества G и отклонения r(x).
Теорема 2. Оптимальное решение (x0, x) задачи МР является оптимальным
решением задачи (5) тогда и только тогда, когда выполняются условие (13) и
x0=extr{cx| с∈С}. (14)
Доказательство. Согласно лемме, оптимальное решение задачи МР являет-
ся допустимым решением задачи (5) тогда и только тогда, когда выполняются
условия (12) и (13). По теореме 1 точка (x0, x) – оптимальное решение одной из
задач (6), (7) тогда и только тогда, когда (с, х) – оптимальное решение задачи (2)
или (3) и x0=сх. Следуя определению оптимального решения задачи Р, пара (с, х)
– оптимальное решение этой задачи тогда и только тогда, когда её элементы
с∈С, х∈Х , удовлетворяют условию (1) для всех (с, х), таких, что с∈С, х∈Х. Та-
ким образом, учитывая то, что x0 удовлетворяяет одновременно соотношениям
(1) и (12), следует справедливость равенства (14).
Алгоритм
1. Выбираем с
1
∈С, полагаем k, l=1, Q
1
={x∈
n
Z+ }, S
1
={x0,x}|x0≤с
1
x, x0∈R
1
,
x∈
n
Z }. Множества, описываемые ограничениями вида (10) и (9), представим
соответственно в виде множеств Ql
и S
k
.
2. Решаем задачу частично целочисленного программирования МР. Если
она недопустима, то на основании того, что ограничения (10) являются релакса-
цией ограничений fi(x)≤0
∀ fi(x)∈Fi задачи (5) и п.1 теоремы 1 заключаем, что
задача Р также недопустима. Этот случай возможен лишь для k=1. Иначе полу-
чаем допустимое ( оптимальное) решение ( l
x0 , x
l
) или информацию о том, что
целевая функция неограничена на допустимом множестве. Тогда в качестве ко-
ординат вектора xl
выбираем достаточно большие числа.
3. Находим отклонение r(x
l
) от границы множества Q и элемент fi∈U
Ii
iF
∈
,
для которого оно достигается. Если r(x
l
) ≤0, то согласно лемме (теореме 2)
О РЕШЕНИИ ЗАДАЧ ЦЕЛОЧИСЛЕННОЙ ОПТИМИЗАЦИИ НА ВЫПУКЛЫХ МНОЖЕСТВАХ...
Теорія оптимальних рішень. 2005, № 4 111
(
l
x0 , x
l
) – допустимое (оптимальное) решение задачи (5). Переходим к п.4, пола-
гая ( k
x0 , x
k
) = (
l
x0 , x
l
). В противном случае образуем множество Q
l+1
следующим
образом: Q
l+1
=Q
l
∩{ x∈R
n
| fi(x
l
)+ if ' (x
l
)(x−x
l
)≤0.
Заменяя l на l+1, переходим к п.2.
4. Решаем задачу линейного программирования вида max {c x
k
| c ∈C}, если
в исходной задаче Р данные, задающие вектор с, управляемые и min {c x
k
| c∈C},
если данные о векторе с заданы неточно. Пусть c
k+1
– найденное оптимальное
решение.
5. Если с
k+1
x
k
≥
k
x0 (с
k+1
x
k
=
k
x0 ), то алгоритм заканчивается. В соответствии с
леммой (теоремой 2) точка ( k
x0 , x
k
) – допустимое (оптимальное) решение задачи
(5). На основании п.2 теоремы 1 заключаем, что (с
k+1
, x
k
) – приближенное (опти-
мальное) решение задачи (5) со значением
k
x0 её целевой функции. Иначе обра-
зуем множество S
k+1
=S
k
∩{(x0,x) | x0≤с
k+1
x
k
}, если в условиях задачи Р extr=min, и
заменяя k на k+1, переходим к п. 2, иначе, заменяя k на k+1, переходим к п. 2.
Теорема 3. Если множество Х ограничено, то описанный алгоритм сходится
к приближенному (оптимальному) решению за конечное число шагов. Если за-
дача Р недопустима, то алгоритм заканчивается на первом шаге с заключением
о том, что задача недопустима.
Доказательство. Так как задача Р имеет конечное оптимальное решение, то
начиная с некоторого номера K, последовательность точек {x
k
} содержится в
ограниченном множестве. Следовательно, существует сходящаяся последова-
тельность {
lkx }. Из условия xi∈Z
n
, i=1,2,… следует, что множество точек {
lkx }
конечно, в силу чего можно выделить стационарную последовательность, т.е.
∃ l* такое,что ∀ l≥ l*
lkx = x , так как начиная с номера l* в задачу МР не вводится
ни одного нового ограничения вида (10). Это возможно лишь в случае, когда
x ∈Х. В п.5 алгоритма, если не выполняется условие (12) или (14), к задаче МР
добавляется новое ограничение вида (9) либо заменяется на лучшее. Их число не
превышает числа вершин многогранника С, так как ни один из векторов сk+1
до
выполнения условия (12) или (14) не может быть найден повторно.
Заключение. Построен и обоснован декомпозиционный метод точного и
приближенного решения сложных задач целочисленной оптимизации с управ-
ляемыми и неточно заданными данными, основанный на конструктивных ап-
проксимациях их задачами более простой структуры. Дальнейшее развитие дан-
ной работы будет направлено на разработку методов решения сложных цело-
численных оптимизационных задач с управляемыми исходными данными, что
приводит к постановкам задач на невыпуклых множествах. Будут получены
критерии допустимости и оптимальности решений указанных задач, исследова-
на их устойчивость.
Н.В. СЕМЕНОВА
112 Теорія оптимальних рішень. 2005, № 4
Н.В. Семенова
ПРО РОЗВ’ЯЗАННЯ ЗАДАЧ ЦІЛОЧИСЛОВОЇ ОПТИМІЗАЦІЇ НА ОПУКЛИХ
МНОЖИНАХ В УМОВАХ НЕВИЗНАЧЕНОСТІ ДАНИХ
Розроблені та обгрунтовані декомпозиційні методи точного та наближеного розв’язання за-
дач, що виникають при дослідженні складних цілочислових оптимізаційних моделей з керо-
ваними та неточно заданими даними. Вони основані на апроксимації вихідних задач задачами
більш простої структури, об’єднують та використовують ідеї методів релаксації, лінеаризації,
відтинаючих площин Келлі.
N.V. Semenova
SOLVING INTEGER OPTIMIZATION PROBLEMS ON CONVEX SETS UNDER DATA
UNCERTAINTY CONDITIONS
The paper constructs and substantiates decomposition methods used to solve problems exactly and
approximately. Such problems emerge when one investigates complicated integer optimization
models with controllable and inexact data. Methods are based on approximation of initial problems
by problems of a simpler structure, unite and use the ideas of relaxation, linearization and the Kelley
cutting plane methods.
1. Сергиенко И.В. Математические модели и методы решения задач дискретной опти-
мизации. – Киев: Наук. думка, 1988. – 472 с.
2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации. Проблемы, методы ре-
шения, исследования. – Киев: Наук. думка, 2003. – 263 с.
3. Семенова Н.В. Решение одной задачи обобщенного целочисленного программиро-
вания // Кибернетика. – 1984. – №5. – С. 25-31.
4. Рощин В.А., Семенова Н.В., Сергиенко И.В. Вопросы решения и исследования одно-
го класса задач неточного целочисленного программирования // Кибернетика. –
1989. – №2. – С. 42-46, 64
5. Рощин В.А., Семенова Н.В., Сергиенко И.В. Декомпозиционный подход к решению
некоторых задач целочисленного программирования с неточными данными // Журн.
вычисл. математики и мат. физики. – 1990. – 29, №5. – С. 786-791.
6. Сергиенко И.В., Рощин В.А., Семенова Н.В. Некоторые задачи целочисленного про-
граммирования с неоднозначно заданными данными и их решение // Проблемы
управления и информатики. – 1998. – №6. – С.116-123.
7. Лэсдон Л.С. Оптимизация больших систем. – М.: Наука, 1975. – 431 с.
8. Пшеничный Б.Н. Метод линеаризации. – М.: Наука, 1983. – 136 с.
9. Kelley J. The cutting plane method for solving convex program // SIAM J. – 1960. – 8,
N4. – P. 703-712.
Получено 25.03.2005
|