До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах icon

До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах




Скачати 111.49 Kb.
НазваДо питання про нелінійну та параметричну оптимізацію на комбінаторних множинах
Дата19.11.2012
Розмір111.49 Kb.
ТипДокументи

 УДК 519.85

ДО ПИТАННЯ ПРО НЕЛІНІЙНУ ТА ПАРАМЕТРИЧНУ ОПТИМІЗАЦІЮ

НА КОМБІНАТОРНИХ МНОЖИНАХ


О. Валуйська, О. Ємець, О. Пічугіна

Полтавський державний технічний університет ім. Ю.Кондратюка


Запропоновано поліноміальний алгоритм розв’язування лінійної параметричної задачі на множинах переставлень та розміщень. Наведено метод відшукання кількості різних розв’язків задачі, дано верхню оцінку цього числа. Розглянуто клас нелінійних задач, до яких належить нелінійна умовна задача оптимізації на переставленнях. Для заданого класу задач запропоновано метод зведення їх до задач опуклої оптимізації.

^ Ключові слова: нелінійна оптимізація, параметрична оптимізація, комбінаторна оптимізація, переставлення

Розглянемо проблеми оптимізації на комбінаторних множинах переставлень та розміщень. Підхід, який є в основі запропонованих методів, ґрунтується на зануренні цих множин в арифметичний евклідів простір, що дає змогу застосовувати до задач оптимізації геометричні властивості структур [1].

1. Параметрична лінійна оптимізація на множинах переставлень та розміщень

Пропонуємо ітераційний алгоритм пошуку всіх розв’язків двох класів лінійних параметричних задач оптимізації на переставленнях та розміщеннях – задач з параметром у цільовій функції та в елементах комбінаторних множин.

Нехай ^ Q – евклідова множина (e-множина) [1] всіх упорядкованих k-вибірок вигляду ( з мультимножини G={g1,…,g}, яка містить елементів, n з яких різні. Наприклад, якщо =k, то Q – загальна множина переставлень, інакше (тобто >k) Q – загальна множина розміщень. Розглянемо також Q' – е-множину k-вибірок вигляду ( з мультимножини G'={g'1,…,g'} з ' елементів, n' з яких різні.

Проаналізуємо лінійну параметричну задачу комбінаторної оптимізації такого вигляду:

знайти:

(1)

де , де .

Виконаємо занурення Q, Q' в Rk, внаслідок чого одержимо е-множини E, E' [1] і перетворимо (1) в лінійну параметричну е-задачу на множині E'' точок Rk:

знайти

(2)

де , xy – скалярний добуток векторів x, y.

Якщо c'=0, Q'= (отже, c''=c, x''=x, E''=E), то задача (2) є лінійною безумовною задачею на комбінаторних множинах переставлень та розміщень, розв’язок якої відомий [1], а саме: якщо елементи мультимножини та коефіцієнти цільової функції впорядковано:

(3)



у випадку, коли E – загальна множина переставлень , то

; (4)

коли E – загальна множина розміщень , то:

(5)

де s+r=k;

Якщо c'0 або Q', то задача (2) – загальне формулювання лінійної безумовної параметричної задачі на комбінаторних множинах, серед яких аналізуємо множини переставлень та розміщень.

Розглянемо два окремі випадки задачі (2):

задачу з параметром у цільовій функції (далі задача А), яку одержуємо з (2 ) при c'0, Q'=;

задачу з параметром в елементах мультимножини Q' (задача Б), яку одержуємо, прийнявши в (2) c'=0, Q'.

Метод викладений у вигляді ітераційного алгоритму, що запропонований тут, дає змогу знайти всі розв’язки задач типу А, Б та задачі (2) на загальних множинах переставлень та розміщень без використання методів лінійного програмування. Алгоритм є поліноміальним, кількість різних розв’язків задачі (2) оцінюємо числом порядку .

Розглянемо задачу А. Введемо поняття мультимножини точок площини (далі 2-мультимножини), її основи та первинної специфікації.

Означення. Нехай M, M' – мультимножини: |M|=|M'|=m. 2-мультимножиною M'' називають сукупність упорядкованих 2-вибірок вигляду

M''={m''i =(mi,m'i), mi M, m'i M',}.

Упорядкуємо лексикографічним порядком елементи M'':

(6)

Впорядкування (6) означає, що:

a)

б) якщо то

У разі, якщо вважатимемо, що упорядковані лексикографічним порядком, що позначаємо так: , .

Поняття основи і первинної специфікації 2-мультимножини вводимо за аналогією з мультимножиною [1].

Означення. Основою 2-мультимножини M'' називають кортеж S(M'') різних елементів M'', упорядкованих за лексикографічним порядком:

S(M'')=(e''1,…,e''k): .

Мультимножину ^ М'', утворену з М, M', позначатимемо M''=(M,M');

Означення. Первинною специфікацією 2-мультимножини M'' називають кортеж [M''] кратностей () елементів S(M''): [M'']=( ,…, ).

Розглянемо 2-мультимножину С''=(C,C') коефіцієнтів цільової функції задачі (2): M={c1,…,ck}, M'={c'1,…,c'k}, M''={c''1,…,c''k}, m=k.

Виконаємо впорядкування (6) над елементами M'': Нехай |S(M'')|=k'', [M'']= ( ,…, )=(,…,).

Пропонуємо ітераційний алгоритм пошуку всіх розв’язків задачі А.

1. Розглянемо спочатку множину k-переставлень .

Визначимо, а потім впорядкуємо за неспаданням величини

. (7)

Умова типу (3) для параметричної задачі має вигляд:

. (8)

У сукупності з умовою вона означає, що (це виконано, наприклад, при ).

У разі збільшення t умова (8) може бути порушена, а вибір tij забезпечує виконання умови:



звідки випливає, що

,

і у випадку переходу параметра через і-та та j-та координати поточного оптимального розв’язку переставляються, внаслідок чого відбувається перехід до суміжної вершини багатогранника переставлень, яка є новим поточним оптимальним розв’язком задачі А.

2. Розглянемо множину k-розміщень .

Уведемо , . Умова типу (7) набуває вигляду

. (9)

Унаслідок чого в разі переходу параметра через відбувається перехід до суміжної вершини багатогранника розміщень, причому якщо:

а) , то і-та та j-та координати поточного оптимального розв’язку переставляються;

б) і=0, тоді: якщо в поточному оптимальному розв’язку , то в новому оптимальному розв’язку ; якщо в поточному оптимальному розв’язку , то в новому оптимальному розв’язку .

^ Алгоритм пошуку всіх розв’язків задачі А. Приймаємо . Оскільки коефіцієнти цільової функції можна вважати впорядкованими за неспаданням (6), то перший поточний розв’язок задачі А за заданого t визначають за формулами (4),(5).

Нехай , , тоді на задача А має єдиний розв’язок x*(1) , на  – єдиний розв’язок x*(2), який є новим поточним оптимальним розв’язком, і його одержують з x*(1) заміною однієї координати або переставленням двох координат за названим вище правилом, при t= tij x*(1), x*(2), а також довільна їхня опукла лінійна комбінація є оптимальним розв’язком задачі А.

Твердження. Кількість N різних розв’язків задачі А визначають за формулою

N=N0+1,

де N0 – кількість різних tij, визначених за формулою (7) або (9).

Оскільки і, то кількість N0 для множини переставлень не перевищує , для множини розміщень – числа , тобто алгоритм, який пропонуємо, є поліноміальним порядку k2/2.

Числові експерименти засвідчили, що ці оцінки будуть досить грубими, якщо коефіцієнти цільової функції – цілі числа, а k – велике.

По-перше, оцінку можна уточнити за допомогою однакових коефіцієнтів цільової функції, звідки маємо: для переставлень , для розміщень .

По-друге, оцінку можна уточнити завдяки однаковим tij (7), (9), що неважко бачити на рисунку, на якому зображено точки основи 2-мультимножини C, прямі, що проходять через пари точок, окрім паралельних до осі Ос (це забезпечує умова ). Кількість прямих з різним нахилом визначає число N0.

Наприклад, на рисунку показано 2-мультимножину C, що збігається зі своєю основою з =5 елементів: С=(A,B,C,D,E)=((1,1),(4,1),(5,2),(3,3),(4,4)).

Таблиця

t’ij

tij

x*1

x*2

x*3

x*4

x*5



Рисунок 1.

2



5

4

3

2

1

0,5

2

5

4

2

3

1

0

0,5

5

3

1

4

2

-1

0

5

2

1

4

3

-2

-1

3

1

2

4

5



-2

2

1

3

4

5

Кількість прямих, непаралельних до Oc, , тобто кількість усіх розв’язків задачі на переставленнях не перевищує N10. Цю оцінку можна суттєво зменшити, тому що прямих з різним нахилом , різних розв’язків задачі – 6. У таблиці наведено множину цих розв’язків для випадку G={1,2,3,4,5}, зазначено, які координати поточного розв’язку змінюються в разі переходу значення параметра через наступне значення tij. Інтервали, на яких розв’язок задачі визначений – (tij ,tij).

У випадку розв’язування задачі на переставленнях більшої вимірності, проте з тією самою основою C (наприклад, k=10, S(C)=((1,1),(4,1),(5,2),(3,3),(4,4)), [C]=(2,1,3,3,1), кількість різних розв’язків не змінюється. У разі розв’язування цієї задачі на розміщеннях () для визначення кількості різних розв’язків додатково проводимо прямі, що проходять через О, тому , різних розв’язків – 8.

У випадку розв’язання задачі Б, величини, аналогічні (7), (9), у G додається g0=0, , далі алгоритм аналогічний, верхня оцінка кількості розв’язків , а для задачі (1)-(2) на сполученнях та розміщеннях – відповідно.

2. Опукле продовження функцій у нелінійній оптимізації на переставленнях

Дослідимо задачу нелінійної оптимізації на множинах, що належать межі будь-якої сильно опуклої множини. Окремим випадком цієї задачі є задача нелінійної комбінаторної оптимізації на переставленнях з додатковими обмеженнями. Доведено, що ця задача зводиться до задачі опуклої (увігнутої) оптимізації в разі, якщо цільова функція двічі неперервно диференційована. Запропоновано метод пошуку еквівалентної задачі опуклої оптимізації.

Як відомо [2], d– опукла множина, якщо



Функція f(x) :  – опукла, якщо



Двічі неперервна диференційована функція f(x) (f(x) ) є опуклою, якщо її матриця Гесса додатно визначена

Перевірку додатної визначеності матриці можна виконати за критерієм Сильвестра. Це можна зробити за такою достатньою умовою.

Теорема. Нехай є квадратична форма



Тоді, якщо: 1) 2) то квадратична форма – додатно визначена.

Доведення. Введемо в розгляд величини i: 0iMi та , існування яких випливає з виконання умови 2 теореми. Тоді

==

+=

0.

Нехай d – опукла множина, для якої

D(x): , D(x); d={x: D(x)1}.

Межу множини d позначимо d, тоді d={x: D(x)=1}.

На функцію D(x) накладаємо умову сильної опуклості існує константа 0 така, що:



Означення. Функцію F(x) : будемо називати опуклим продовженням функції f(x) (див., наприклад [3]) з множини d в , якщо виконуються наступні умови

F(x) – опукла в ,

F(x)=f(x),  xd.

Формулювання задачі. Для довільної функції f(x) ставиться питання про існування функції F(x) – опуклого продовження f(x) з множини d в арифметичний евклідів простір . Наведемо конструктивний алгоритм побудови такої функції.

^ Перший етап.

Перейдемо від функції f(x) до функції Ф(x), яка задовольняє такі умови

Ф(x)=f(x)xd,

Ф(x) ,

частинні похідні другого порядку ^ Ф(x) обмежені в .

Очевидно, якщо f(x) задовольняє умову 3, то Ф(x)=f(x), інакше шукаємо Ф(x) так: уведемо допоміжну функцію g(y): , g(y) таку, що

g(0)=0, g(1)=1, g(y)yM, g (y) M, g (y)M,y0,

де M=const, Наприклад, g(y)=

Тоді Ф(x) визначимо за формулою

Ф(x)=f(g(D(x))x)=.

Другий етап

Перейдемо від функції Ф(x) до функції F(x):

F(x)= Ф(x)+P(D(x)-1)/,

де

1)

2)

3)

Функція F(x) є опуклим продовженням функції з множини d в арифметичний евклідів простір . Як бачимо, F(x) є двічі неперервно диференційованою функцією. Оскільки множина переставлень, як відомо (див., наприклад [1]) лежить на поверхні сфери в , то цей підхід застосовується до нелінійної оптимізації на переставленнях.

ЛІТЕРАТУРА

  1. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації: К., 1993.

  2. Рокафеллар Р. Выпуклый анализ. М., 1973.

  3. Яковлев С.В. Теория выпуклых продолжений функций на вершинах выпуклых многогранников// Журн. выч. математики и мат. физики. 1994. Т. 34. №7. С. 1112-1119.
^

Nonlinear and parametric optimization on combinatorial sets


O. Valuyska, O. Yemets, O. Pichugina

Poltava National Technical University named after Uriy Kondratuk


The polynomial method of solving linear optimization problem with parameter in target function on the sets of arrangements and combinations is proposed. The method of searching for amounts of different solutions of the problem is considered, upper estimation of this number is given. The class of nonlinear optimization problems with restrictions, for example, nonlinear optimization problem on combinations, is considered. The method of reducing of problems of this class to concave optimization problem is proposed.

Key words: nonlinear optimization, parametric optimization, combinatorial optimization, permutations

Стаття надійшла до редколегії дд.мм.рррр

Прийнята до друку


 © Валуйська О., Ємець О., Пічугіна О., 2002

Схожі:

До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconОпис модуля назва модуля: Теорія автоматичного керування
Сар та керування, математичний апарат теорії автоматичного керування; вміти складати математичні моделі сар, аналізувати стійкість...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconПро затвердження Переліку наукових спеціальностей На виконання Указу Президента України від 09. 12. 2010 n 1085 1085/2010
Про оптимізацію системи центральних органів виконавчої влади, відповідно до Положення про Міністерство освіти
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconЛюдмила Білоусько
Матеріалізовані засоби наочності як засіб розвитку комбінаторних здібностей старших дошкільників
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconПоложення про Міністерство освіти І науки, молоді та спорту України, затвердженого Указом Президента України від 08. 04. 2011 n 410 ( 410/2011 ), Положення про
Про оптимізацію системи центральних органів виконавчої влади, відповідно до Положення про Міністерство освіти
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconПолітичні та правові погляди бенжамена констана
Про стародавню свободу порівняно зі свободою сучасною" та "Курс конституційної політики", який побачив світ уже після смерті автора...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconРозпорядження грудня 2012 р. Кременчук № Про оптимізацію планування та захистів кандидатських І докторських дисертацій
З метою оптимізації планування та захистів кандидатських і докторських дисертацій професорсько-викладацьким складом університету...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconРішення питання про застосування примусових заходів медичного характеру. Нормативні акти кримінально-процесуальний кодекс України
Закінчення досудового слідства винесенням постанови про направлення справи до суду для вирішення питання про застосування примусових...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconРозпорядження «06» грудня 2012 р. Кременчук №23-р про оптимізацію управлінської організації науково-дослідної діяльності на кафедрах, інститутах І факультетах
З метою оптимізації управлінської організації науково-дослідної діяльності на кафедрах, факультетах та інститутах і підвищення інноваційності...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconЗавданнями фінансової стратегії є
Фінсова стратегія охоплює всі форми фінансової діяльності оптимізацію основних та оборотних запасів, формування та розподіл прибутку,...
До питання про нелінійну та параметричну оптимізацію на комбінаторних множинах iconМодуль: ергономіка
Мета курсу: формування системи теоретичних І прикладних знань по питанням ергономічного аналізу діяльності оператора, ергономічним...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи