Об одной задаче оптимизации дробно-линейной функции на перестановках
Досліджено задачу знаходження екстремуму функції на множині перестановок. Функція цілі — це відношення двох лінійних форм, кожна з яких є прямою в багатовимірному просторі. Запропоновано метод розв’язання задачі, що ґрунтується на частковій упорядкованості значень функції. The problem under study is...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2010 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/210721 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Об одной задаче оптимизации дробно-линейной функции на перестановках / Г.А. Донец, Л.Н. Колечкина // Проблемы управления и информатики. — 2010. — № 2. — С. 31-41. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859812955013513216 |
|---|---|
| author | Донец, Г.А. Колечкина, Л.Н. |
| author_facet | Донец, Г.А. Колечкина, Л.Н. |
| citation_txt | Об одной задаче оптимизации дробно-линейной функции на перестановках / Г.А. Донец, Л.Н. Колечкина // Проблемы управления и информатики. — 2010. — № 2. — С. 31-41. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Досліджено задачу знаходження екстремуму функції на множині перестановок. Функція цілі — це відношення двох лінійних форм, кожна з яких є прямою в багатовимірному просторі. Запропоновано метод розв’язання задачі, що ґрунтується на частковій упорядкованості значень функції.
The problem under study is to find the extremum of a function on the set of permutations. The objective function is defined as a ratio of two linear forms each being a straight line in multi-dimensional space. The method solution is offered based on partial ordering of the function values.
|
| first_indexed | 2025-12-17T12:04:35Z |
| format | Article |
| fulltext |
© Г.А. ДОНЕЦ, Л.Н. КОЛЕЧКИНА, 2010
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 31
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
И МЕТОДЫ ОПТИМИЗАЦИИ
УДК 519.1
Г.А. Донец, Л.Н. Колечкина
ОБ ОДНОЙ ЗАДАЧЕ ОПТИМИЗАЦИИ
ДРОБНО-ЛИНЕЙНОЙ ФУНКЦИИ
НА ПЕРЕСТАНОВКАХ
Введение
Значительное расширение областей применения вычислительной техники
и более детальное использование экономико-математических моделей приводит к
необходимости решения сложных задач большой размерности. Представляют ин-
терес задачи, в которых целевая функция является дробно-линейной [1, 2], т.е.
в качестве функции векторного критерия используется отношение двух линейных
функций. Такие функции применяются в задачах оптимизации некоторых относи-
тельных показателей качества: себестоимость, рентабельность, производитель-
ность, трудоемкость и т.д. Модели, использующие указанные критерии, отобра-
жают тенденции постоянного снижения себестоимости из расчета на единицу
продукции и повышение качественных показателей производства при увеличении
его масштабов.
Дробно-линейные критерии часто используются, например, в финансовой де-
ятельности, при планировании корпораций, там, где необходимо минимизировать
отношение долга к собственным средствам, максимизировать отношение выпуска
продукции на одного работающего, в управлении банковского баланса, где необ-
ходимо минимизировать отношение рискованных вложений к капиталу, максими-
зировать отношение реального капитала к требуемому капиталу, отношение за-
кладных на жилье к общей сумме закладных и др. Следует заметить, что множе-
ства — области допустимых решений задачи с дробно-линейной функцией — во
многих задачах имеют комбинаторные свойства. Задачи на комбинаторных кон-
струкциях — перестановках, размещениях, разбиениях и т.д. — интересны тем,
что область допустимых решений представляет собой некоторый комбинаторный
многогранник, свойства которого изучены и исследованы. Знание специфических
свойств комбинаторного многогранника дает возможность использовать их для
построения новых и усовершенствования существующих методов решения ком-
бинаторных оптимизационных задач. Многогранники тесно связаны с теорией
графов и их свойствами. Использование свойств графов комбинаторных много-
гранников может послужить повышению эффективности «традиционных»
и разработке новых методов комбинаторной оптимизации. Комбинаторные моде-
ли могут применяться для решения оптимизационных задач, которые возникают
при оптимальном размещении на графах.
Цель данной работы — построение метода решения задачи комбинаторной
оптимизации с дробно-линейной целевой функцией на допустимом множестве
перестановок для нахождения вершины перестановочного многогранника, кото-
32 ISSN 0572-2691
рая отвечает заданному значению целевой функции на основании установленной
взаимосвязи между комбинаторным множеством перестановок и графом переста-
новочного многогранника. Настоящая публикация — продолжение работ [3–6],
в которых рассматриваются алгоритмы на графах.
1. Постановка задачи и основные определения
Задачи на комбинаторных конструкциях можно сформулировать так: имеется
n-множество элементов, на нем задается конечное множество комбинаторных кон-
фигураций }....,,,{}{ 21 ri aaaA В данном случае под комбинаторной конфи-
гурацией ri aaa ...,,, 21 будем понимать перестановки, сочетания, комбинации,
различные последовательности и т.п. На множестве A задается функция ).(xF
Требуется отыскать экстремум )(xF и элементы множества A, которые этот экс-
тремум доставляют. Сама формулировка экстремальных комбинаторных задач
диктует выбор операций, применяемых для их решения. Во-первых, надо выбрать
подходящий метод исчерпывающей генерации множества A и располагать соот-
ветствующим множеством значений функции ).(xf Во-вторых, надо развить ме-
тодику сравнения этих значений и выделения из них максимального или мини-
мального. Операция перебора практически редко оказывается осуществимой, так
как число возможных комбинаций может быть слишком велико. Трудности, свя-
занные с перебором вариантов и сравнением значений, весьма значительные.
Именно они и препятствовали развитию некоторой части комбинаторного анали-
за, несмотря на ее очевидную актуальность [7].
Общая схема связи экстремальных комбинаторных задач с методами линей-
ного программирования выглядит примерно так: элементы i интерпретируют
как точки евклидова пространства, чтобы «целевая» функция )(xf стала линей-
ной формой. Как правило, такие задачи решаются методами линейного програм-
мирования, если функция линейная. Если же функция дробно-линейная, то, как
правило, применяются методы линеаризации функции, т.е. сведение ее к линей-
ной форме. Далее рассматривается задача нахождения экстремума этой функции
на выпуклой оболочке заданных точек — на выпуклом многограннике. Очевидно,
что экстремум линейной формы на многограннике достигается в одной из вер-
шин, которые входят во множество рассматриваемых элементов. Особенностью
комбинаторных задач при таком сведении останется то, что при нахождении ре-
шения следует ограничиваться лишь точками с целочисленными координатами.
Тогда решение комбинаторных экстремальных задач представляет собой переста-
новку )...,,,( 21 naaa чисел ,...,,2,1 n множество которых обозначим .nP Такой
переход от параметрической формы задания выпуклого многогранника к анали-
тической имеет большое значения для задач дискретной оптимизации, так как
позволяет сформулировать их в терминах линейного программирования, но, как пока-
зывает практика, это не всегда оправдано. Подзадачей сформулированной выше
задачи может быть определение гамильтонова пути, который отражает изменение
значения дробно-линейного функционала на множестве перестановок. Много-
гранник гамильтоновых путей графа является гранью многогранника гамильтоно-
вых путей полного графа. Как известно, перестановочный многогранник можно
представить в виде графа, который описан в работе [5]. В этом графе вершины
представляют собой множество всех перестановок ,nP а две вершины образуют
дугу ,21
pp если ),()( 21 pfpf ,, 21 nPpp и если перестановка 2p получена
из 1p с помощью транспозиции двух элементов. Тогда для подобных графов
можно сформулировать следующую задачу:
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 33
найти множество перестановок, в которых значение целевой функции равно
заданному значению, т.е.
),(arg xFx
nPx
где .)( yxF Такие задачи рассмотрены в [5, 6] для случая, когда целевая функ-
ция линейная. В данной работе функция представляется в дробно-линейном виде
как отношения двух линейных форм, что значительно усложняет задачу. Тогда
сформулированная выше задача сводится к нахождению множества точек — пе-
рестановок, в которых достигается заданное значение дробно-линейного функци-
онала
,
)(
)(
arg)(arg
xg
xf
xFx
nn PxPx
(1)
где ).(xFy
2. Свойства дробно-линейных функций
Отметим некоторые свойства дробно-линейной функции, полезные для даль-
нейшего решения задачи.
Дробно-линейная функция ),/(),()( 00 dxdcxcxF не является ни
вогнутой, ни выпуклой. Однако поверхности уровня любой функции ),(xF т.е.
множества })({ xFRxL n
выступают гиперплоскостями.
Известно [1], что любой локальный минимум задачи дробно-линейного про-
граммирования в то же время глобальный, и если оптимальное решение конечно,
то существует крайняя точка многогранника G — области допустимых решений,
которая является оптимальной. Это утверждение выполняется, если числитель и
знаменатель дробно-линейной функции не превращаются одновременно в ноль
.Xx
Предположим, что .0, 0 Gxdxd Известно, что на любом прямоли-
нейном отрезке, который принадлежит многограннику G, дробно-линейная функ-
ция )(xF изменяется монотонно.
Теорема 1. Дробно-линейная функция )(xF достигает минимума (максиму-
ма) только в вершинах многогранника G. Если минимум (максимум) достигается
в нескольких крайних точках, то он достигается и на их выпуклой оболочке.
Определение 1. Непрерывная функция )(xF будет квазивыпуклой функцией
на выпуклом множестве G, если выполняется любое из следующих эквивалент-
ных условий:
(a) множество },)({ GxqxFRx m выпукло для всех q, ;nRG
(b) ),())1(()()(,, 1121221 xFxxFxFxFGxx .10
Определение 2. Функция )(xF будет строго квазивыпуклой на множестве G,
если в условии (b) фигурируют строгие неравенства.
Теорема 2. Любой локальный минимум строго квазивыпуклой функции яв-
ляется глобальным.
Поскольку множество },),/(),({ 00 GxqdxdcxcRx n выпукло
для всех значений q, то функция ),/(),()( 00 dxdcxcxF квазивыпукла на
множестве G. Нетрудно показать, что функция xdxc ,/, строго квазивыпукла
на G.
34 ISSN 0572-2691
Очевидно, что функция )(xF квазивогнута на выпуклом множестве S, если
функция ))(( xF квазивыпукла.
Если сделать замену: )(xFi на ),(xFi то условие (b) для квазивогнутых
функций можно записать в виде
)())1(()()( 12112 xFxxFxFxF iiii
или
)](),([min))1(( 2121 xFxFxxF iii ,
для любых Sxx 21, и .10 Для вогнутых и квазивогнутых функций с точ-
ностью до изменения знаков сохраняются свойства выпуклых и квазивыпуклых
функций.
Как известно [1, 2], для решения задач с дробно-линейной функцией цели
существует большое количество методов, которые условно распределяются на
методы линеаризации, параметрические методы, модификации симплекс-методов,
среди которых наиболее известны метод Чарнса и Купера, алгоритм Гилмори и
Гомори. Как отмечается в [1], все эти методы имеют близкую вычислительную
сложность, а приоритет отдается методу, позволяющему эффективнее решать
дробно-линейную задачу в конкретных практических условиях (имеется ввиду
размерность задачи, структура системы ограничений, наличие программного
обеспечения и т.п.). Предпочтение отдается методам сведения к решению серии
задач линейного программирования, для которых разработано эффективное про-
граммное обеспечение для различных типов ЭВМ. Но на данный момент пред-
ставляют интерес методы, в основе которых лежат структурные особенности об-
ласти допустимых решений, их свойства. В основе рассматриваемого подход как
раз и лежат некоторые структурные свойства перестановочного многогранника и
его графа, который выступает областью допустимых решений задачи.
3. Подход к решению задачи
Рассмотрим дробно-линейную функцию ),(xF где числитель )(xf и знаме-
натель )(xg — две линейные функции, в которых коэффициенты определяются
по правилу арифметической прогрессии:
),1(1 icci
).1(1 iddi (2)
Согласно этим обозначениям числитель и знаменатель дробно-линейной функ-
ции для данной перестановки p можно представить соответственно: )),(,()( pxcxf
где )( px — вектор переменных ),...,,,( )()2()1( nppp xxx а )),(,()( pxdxg
где
nPp — множество перестановок множества ),...,,,( 21 nxxx ,Nxi т.е. перестанов-
ке множества )...,,2,1( n ставится в соответствие вектор )....,,,()( )()2()1( nppp xxxpx
Рассмотрим значение дробно-линейной функции в двух разных пере-
становках ,, которые соответствуют номерам ,, 21 pp и сравним их:
.
))(,(
))(,(
))(,(
))(,(
xd
xc
xd
xc
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 35
Определим следующее соотношение в виде коэффициента ),,( который
характеризует некоторое различие между значениями функций в двух соседних
перестановках ,, отличающихся одной транспозицией:
).,)(,(),)(,(),( 122121 dpcpdpcppp
Тогда очевидно, что если ,0),( 21 pp то ).()( 21 pFpF Рассмотрим далее
следующие рассуждения:
)),((...)( 0
1
1)()2(2)1(1
xpxcxcxcxcxс
n
i
inn
),1...,,1,0(0 np .
1
Sx
n
i
i
Определим соотношения разности
,
))((
))((
))((
))((
01
01
01
01
xpSd
xpSc
xpSd
xpSc
проведем математические преобразования
))(())(((())(())(( 000101
2
11 xpxpxpSdxpScSdc
)).(())(((())(())(( 000101
2
11 xpxpxpSdxpScSdc
Сведем подобные слагаемые:
)),()(())()(( 011011 xpdcSxpdcS
))].()(()[())](()()[(( 0110011 xxpdcSxpxpdcS
Рассмотрим две перестановки:
...),,...,,...,,,( )()()2()1( kj xxxx ...),,...,,...,,,( )()()2()1( jk xxxx
].)[(])[1(])[1(),( )()()()()()( jkjkkj xxjkxxkxxjp
Далее приведем рассуждения для ,3n которое определяет количество эле-
ментов перестановки в множестве ,nP составленных из множества ),,,( 321 aaaA
поскольку их можно адаптировать на более общий случай.
В качестве примера рассмотрим две перестановки: ),3,2,1(1 p ),2,3,1(2 p
где ,, 21 nPpp подставив их в целевую функцию ),(xF и рассмотрим знак раз-
ности между ними:
.
233211
233211
332211
332211
xdxdxd
xcxcxc
xdxdxd
xcxcxc
(3)
Заметим, что знак разности определяется знаком числителя, а знаменатель не
влияет на знак, поэтому рассмотрим соотношения числителя (3). После элемен-
тарных математических преобразований над пропорциями получим следующее
выражение:
36 ISSN 0572-2691
)()()( 21121331213223
2
32332
2
2 dcdcdcdcxxdcdcxdcdcx
).( 3113122131 dcdcdcdcxx (4)
Введем такие обозначения:
;12
21
21
m
dd
cc
;13
31
31
m
dd
cc
.23
32
32
m
dd
cc
(5)
Подставляя обозначения (5) в (1), получаем следующее выражения:
);( 2
3
2
22323
2
323
2
2 xxmmxmx );()( 1213212112133121 mmxxdcdcdcdcxx
),()( 1312313113122131 mmxxdcdcdcdcxx
и после сведения подобных слагаемых имеем
),( 213112 xxxxm ),( 312113 xxxxm ).( 2
3
2
223 xxm
Введем коэффициент ),,( ji pp который определяет знак разности между
заданными перестановками ., ji pp
Определение 3. Множество миноров матрицы, образованной двумя строчка-
ми коэффициентов, заданных согласно формуле (2),
;
ji
ji
ij
dd
cc
m ,,, nNjiij
называется множеством миноров целевой функции ).(xF Тогда, учитывая (5)
и правило нахождения определителя, между перестановками 21, pp знак разно-
сти определяется следующим образом:
,5
231
321
),( 23131221 mmmpp
и зависит от миноров второго порядка .ijm
Определение 4. Назовем коэффициенты при минорах 231312 ,, mmm соответ-
ственно ,,, 231312 тогда ).,,(),( 231312 ji
Известно, что при 3n для линейной функции )(xf структурный граф пе-
рестановочного многогранника M имеет следующий вид (рис. 1).
123
213
132 231
312 321
1 3
2
5
4 6
Рис. 1
Определим соответствующие коэффициенты разности значений функции для
двух перестановок: ),5,1,1()3,1( ),3,3,3()2,1( ),1,5,1()4,2(
),4,4,8()4,3( ),3,3,3()5,3( ),3,3,3()6,4( ).1,1,5()6,5(
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 37
Учитывая (2), сделаем замену в выражениях (5), тогда будем иметь следую-
щие выражения:
.
2
2
;2)(2
2
2
;
12
1
1
1
1
11
11
23
1211
11
11
1311
11
11
12
m
d
c
d
c
dd
cc
m
mdc
dd
cc
mdc
dd
cc
m
(6)
Подставляя (6) в значения расстояний между точками-перестановками, по-
лучаем:
,6)3,1( 12m ,6)2,1( 12m ,12)4,2( 12m ,12)4,3( 12m
,12)5,3( 12m ,6)6,4( 12m .6)6,5( 12m
На основании расчетов коэффициентов можно построить гамильтонов путь
внутри каждой шестерки элементов перестановки и проследить изменения значе-
ний целевой функции в вершинах графа. Напомним, что граф перестановочного
многогранника для линейной целевой функции описан в [5] и имеет вид, пред-
ставленный на рис. 2.
22
2413 1423
2143 4123 4213
1234
2134
1324 2314
3124 3214
1243
1 3
2
5
4 6
7 9 11
10
12
3421 2431
3241 4231 4321
1342
3142
1432 3412
4132 4312
2341
13 15
14
17
16
18
19 21 23
20 24
A
B
C
D
Рис. 2
На основании изложенных рассуждений для перестановочного многогранни-
ка 3n изложим некоторые значимые факты для произвольного значения n.
Лемма. Для 3n и )( ji nNjiij ,, справедливо равенство
.12mijmij
38 ISSN 0572-2691
Доказательство леммы следует из преобразований
)1()1(
)1()1(
11
11
idid
icic
dd
cc
m
ji
ji
ij
.
)1(
)1(
12
1
1
1
1
mij
d
c
ji
id
ic
ij
Теорема 3. Разность между двумя перестановками ),,( st pp )( st для
произвольных n определяется по формуле
,),(
1
1
1
ij
n
ij
ij
n
i
st mpp
(7)
где ij равняется минорам матрицы ,2 n образованной двумя перестановками
., st pp
Доказательство проводим методом индукции:
1) для 1k это выражение имеет место;
2) для k оно выполняется на основании изложенных выше рассуждений;
3) для 1k докажем этот факт. Для этого рассмотрим ,, st pp которые обра-
зованы одной транспозицией, т.е. отличаются порядком следования только одной
координаты:
),,...,,,...,,,( 121 kkstt iiiiiip ).,...,,,...,,,( 121 kktss iiiiiip
Составим матрицу их коэффициентов, которая имеет следующий вид:
.
,...,,,,...,,
,...,,,...,,,
1
1
1
21
121
sk
kkst
t
kkst
iiiiii
iiiiii
(8)
Соответственно, чтобы найти разность между двумя перестановками
),,( st pp необходимо использовать формулу (3). Далее знак разности определя-
ется преобразованиями формул (5). Формула (7) следует из определений миноров
и коэффициентов при минорах.
Теорема 4. Граф перестановок )(
~
nPG для дробно-линейной функции ),(xF
коэффициенты которой определены согласно (2), совпадает с графом перестано-
вок для линейной функции )( nPG с точностью до ориентации.
Доказательство вытекает из леммы 1.
Следствие. Экстремальные значения функции ),(xF в которой коэффици-
енты целевой функции определяются по формулам (2), достигается в крайних
точках.
4. Вычислительные эксперименты
Рассмотрим численные примеры, учитывая, что для коэффициентов целевых
функций выполняются соотношения (2).
Пример 1. Найти отношения двух линейных функций — значение дробно-
линейной функции, когда коэффициенты изменятся в числители на 2, в знаменателе
на 1. В табл. 1 заданы значения коэффициентов целевой функции, точки-вершины
графа и значения коэффициентов линейных функций: ).3,2,1(),8,6,4( dc
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 39
Таблица 1
ip
1x
2x
3x ),(/),()( iiii xdxcxF
1 1 2 3 2,857143
2 2 1 3 2,923077
3 1 3 2 2,923077
4 3 1 2 3,090909
5 2 3 1 3,090909
6 3 2 1 3,2
На рис. 3 представлена динамика изменения значения целевой функции.
2,8
2,9
3
3,1
3,2
3,3
0 2 4 6 8
Рис. 3
Пример 2. Определить отношения двух линейных функций — значение
дробно-линейной функции, когда коэффициенты изменятся в числители на 2,
в знаменателе на 1. В табл. 2 заданы значения коэффициентов целевой функции,
точки-вершины графа (перестановки) и значения целевых функций: ),9,7,5(c
)54,3(d (см. рис. 4)
Таблица 2
ip
1x
2x
3x ),/(),()( iiii xdxcxF
1 1 2 3 1,769231
2 2 1 3 1,76
3 1 3 2 1,76
4 3 1 2 1,73913
5 2 3 1 1,73913
6 3 2 1 1,727273
1,72
1,73
1,74
1,75
1,76
1,77
1,78
0 2 4 6 8
Номер точки перестановки З
н
ач
ен
и
е
ф
у
н
к
ц
и
и
в
т
о
ч
к
е
Рис. 4
Пример 3. Найти отношения двух линейных функций — значение дробно-
линейной функции, когда коэффициенты изменятся в числители на 2, в знаме-
нателе на 1. В табл. 3 заданы значения коэффициентов целевой функции, точки-
вершины (перестановки) графа и значения целевых функций при :4n
),11,9,7,5(c ).7,5,4,3(d
40 ISSN 0572-2691
Таблица 3
№ пере-
становок 1x
2x
3x
4x ),/(),()( iiii xdxcxF
1 1 2 3 4 1,66666667
2 2 1 3 4 1,66037736
3 1 3 2 4 1,66037736
4 3 1 2 4 1,64705882
5 2 3 1 4 1,64705882
6 3 2 1 4 1,64
7 1 2 4 3 1,69230769
8 2 1 4 3 1,68627451
9 1 4 2 3 1,68
10 4 1 2 3 1,65957447
11 2 4 1 3 1,66666667
12 4 2 1 3 1,65217391
13 1 3 4 2 1,71428571
14 3 1 4 2 1,70212766
15 1 4 3 2 1,70833333
16 4 1 3 2 1,68888889
17 3 4 1 2 1,68181818
18 4 3 1 2 1,6744186
19 2 3 4 1 1,73333333
20 3 2 4 1 1,72727273
21 2 4 3 1 1,72727273
22 4 2 3 1 1,71428571
23 3 4 2 1 1,71428571
24 4 3 2 1 1,70731707
1,62
1,64
1,66
1,68
1,7
1,72
1,74
0 5 10 15 20 25 30
Номер точки перестановки
З
н
ач
ен
и
е
ф
у
н
к
ц
и
и
в
т
о
ч
к
е
1
2
Рис. 5
На рис. 5 представлена тенденция изменения значений целевой функции (ли-
ния 1) по отношению к функции, которая имеет полиномиальную зависимость:
6908,10277,00066,00006,0105,0100,7100,9 23425265 xxxxxxy
(линия 2). Если проанализировать все графики, то очевидно, что расположение
точек подтверждает сформулированные теоремы и их обоснования.
Продолжая и развивая результаты этой работы, целесообразно рассматривать
задачу, где не всегда существуют перестановки, в которых целевая функция при-
нимает заданное значение. Тогда сформулированная выше проблема предстанет
как задача:
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 2 41
определить множество пар перестановок ),,( xx для которых при заданном y
,
)(
)(
argmin)(argmin
)()( xg
xf
xFx
yxFyxF
.
)(
)(
argmax)(argmax
)()( xg
xf
xFx
yxFyxF
Заключение
Модель задачи с учетом комбинаторных свойств области допустимых реше-
ний и дробно-линейными функциями критериев может успешно применяться при
решении различных практических задач. Установлена взаимосвязь между задачей
на комбинаторном множестве перестановок и задачей на непрерывном допусти-
мом множестве, а также обосновано использование и применение теории графов
для построения метода решений сформулированной задачи. На основании дока-
занных теорем, продолжая исследования и развивая результаты предыдущих
работ авторов, предложен подход к решению векторной задачи с дробно-линей-
ными критериями на допустимом множестве комбинаторной конструкции пере-
становок, при котором поиск решения исходной задачи сводится к задаче постро-
ения гамильтонова пути на графе перестановочного многогранника.
Г.П. Донець, Л.М. Колєчкіна
ПРО ОДНУ ЗАДАЧУ ОПТИМІЗАЦІЇ
ДРОБОВО-ЛІНІЙНОЇ ФУНКЦІЇ
НА ПЕРЕСТАНОВКАХ
Досліджено задачу знаходження екстремуму функції на множині перестановок.
Функція цілі — це відношення двох лінійних форм, кожна з яких є прямою
в багатовимірному просторі. Запропоновано метод розв’язання задачі, що
ґрунтується на частковій упорядкованості значень функції.
G.A. Donets, L.N. Kolechkina
AN OPTIMIZATION PROBLEM
OF LINEAR-FRACTIONAL FUNCTION
ON A SET OF PERMUTATIONS
The problem under study is to find the extremum of a function on the set of permuta-
tions. The objective function is defined as a ratio of two linear forms each being
a straight line in multi-dimensional space. The method solution is offered based on
partial ordering of the function values.
1. Шор Н.З., Соломон Д.И. Декомпозиционные методы в дробно-линейном программирова-
нии. — Кишинев : Штиинца, 1989. — 204 с.
2. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільо-
вими функціями. — Київ : Наук. думка, 2005. — 118 с.
3. Донец Г.А., Шулинок И.Э. О сложности алгоритмов поиска в глубину на модульных графах //
Теорія оптимальних рішень. — 2002. — № 1. — С. 105–110.
4. Донец Г.А., Бинь Чжан Задачи о математическом сейфе на графах // Кибернетика и си-
стемный анализ. — 2006. — № 5. — С. 14–22.
5. Донец Г.А., Колечкина Л.Н. Метод упорядочения значений линейной функции на множе-
стве перестановок // Там же. — 2009. — № 2. — С. 50–61.
6. Донец Г.А., Колечкина Л.Н. Об одном подходе к решению комбинаторной задачи оптими-
зации на графах // Управляющие системы и машины. — 2009. — № 4. — С. 31–35.
7. Рыбников К.А. Введение в комбинаторный анализ. — М. : Изд-во Москов. ун-та, 1985. —
308 с.
Получено 09.11.2009
|
| id | nasplib_isofts_kiev_ua-123456789-210721 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-17T12:04:35Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Колечкина, Л.Н. 2025-12-15T19:01:39Z 2010 Об одной задаче оптимизации дробно-линейной функции на перестановках / Г.А. Донец, Л.Н. Колечкина // Проблемы управления и информатики. — 2010. — № 2. — С. 31-41. — Бібліогр.: 7 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210721 519.1 10.1615/JAutomatInfScien.v42.i4.10 Досліджено задачу знаходження екстремуму функції на множині перестановок. Функція цілі — це відношення двох лінійних форм, кожна з яких є прямою в багатовимірному просторі. Запропоновано метод розв’язання задачі, що ґрунтується на частковій упорядкованості значень функції. The problem under study is to find the extremum of a function on the set of permutations. The objective function is defined as a ratio of two linear forms each being a straight line in multi-dimensional space. The method solution is offered based on partial ordering of the function values. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Об одной задаче оптимизации дробно-линейной функции на перестановках Про одну задачу оптимізації дробово-лінійної функції на перестановках An optimization problem of linear-fractional function on a set of permutations Article published earlier |
| spellingShingle | Об одной задаче оптимизации дробно-линейной функции на перестановках Донец, Г.А. Колечкина, Л.Н. Оптимальное управление и методы оптимизации |
| title | Об одной задаче оптимизации дробно-линейной функции на перестановках |
| title_alt | Про одну задачу оптимізації дробово-лінійної функції на перестановках An optimization problem of linear-fractional function on a set of permutations |
| title_full | Об одной задаче оптимизации дробно-линейной функции на перестановках |
| title_fullStr | Об одной задаче оптимизации дробно-линейной функции на перестановках |
| title_full_unstemmed | Об одной задаче оптимизации дробно-линейной функции на перестановках |
| title_short | Об одной задаче оптимизации дробно-линейной функции на перестановках |
| title_sort | об одной задаче оптимизации дробно-линейной функции на перестановках |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210721 |
| work_keys_str_mv | AT donecga obodnoizadačeoptimizaciidrobnolineinoifunkciinaperestanovkah AT kolečkinaln obodnoizadačeoptimizaciidrobnolineinoifunkciinaperestanovkah AT donecga proodnuzadačuoptimízacíídrobovolíníinoífunkcíínaperestanovkah AT kolečkinaln proodnuzadačuoptimízacíídrobovolíníinoífunkcíínaperestanovkah AT donecga anoptimizationproblemoflinearfractionalfunctiononasetofpermutations AT kolečkinaln anoptimizationproblemoflinearfractionalfunctiononasetofpermutations |