Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа
Побудовано та досліджено математичні моделі задач оптимізації на розміщеннях і перестановках ігрового типу, в яких обидва гравці мають комбінаторні обмеження на використання своїх стратегій. Для задач вимірності 2 × n та m × 2 запропоновано модифікований графічний метод. Mathematical model...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2006 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/206809 |
| 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: | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2006. № - 3. — С. 37-47 . — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859790842599833600 |
|---|---|
| author | Емец, О.А. Устьян, Н.Ю. |
| author_facet | Емец, О.А. Устьян, Н.Ю. |
| citation_txt | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2006. № - 3. — С. 37-47 . — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Побудовано та досліджено математичні моделі задач оптимізації на розміщеннях і перестановках ігрового типу, в яких обидва гравці мають комбінаторні обмеження на використання своїх стратегій. Для задач вимірності 2 × n та m × 2 запропоновано модифікований графічний метод.
Mathematical models of optimization problems on arrangements and permutations of game type in which both players have combinatorial restrictions for using their strategies are built and studied. The modified graphic method for solving such problems of dimension 2 × n and m × 2 is offered.
|
| first_indexed | 2025-12-02T11:44:39Z |
| format | Article |
| fulltext |
© О.А. ЕМЕЦ, Н.Ю. УСТЬЯН, 2006
Проблемы управления и информатики, 2006, № 3 37
УДК 519.85
О.А. Емец, Н.Ю. Устьян
РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ
КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ
НА РАЗМЕЩЕНИЯХ И ПЕРЕСТАНОВКАХ
ИГРОВОГО ТИПА
Введение. Многие процессы и ситуации уже описаны и исследованы различ-
ными математическими дисциплинами. Определив, к какому классу относится
данная задача, при помощи нужных методов легко найти оптимальный в опреде-
ленном смысле вариант действий.
Например конфликтные ситуации, часто встречающиеся в нашей жизни, изу-
чает теория игр [1, 2], которая позволяет получить рекомендации о том, как нуж-
но вести себя в конкретном случае. Часто для выбора оптимального варианта дей-
ствий необходимо решить задачу оптимизации. Для этого можно использовать
методы линейного и нелинейного программирования [3], дискретной [4, 5] и ком-
бинаторной оптимизации [6–13] и др.
Однако возникают новые проблемы и задачи, появляются новые ситуации,
которые представляют собой специфические матричные игры. Для их решения
уже нельзя использовать методы классической теории игр без модификации. Спе-
цифика задач может быть в существовании комбинаторных ограничений на ис-
пользование игроками своих стратегий (не только чистых стратегий, но и сме-
шанных). Поэтому нужно строить и исследовать математические модели таких
задач и, в зависимости от ограничений на стратегии, разрабатывать соответству-
ющие методы для их решения. Авторам статьи неизвестны такие исследования.
В данной статье формулируются и изучаются задачи комбинаторной оптими-
зации на перестановках и размещениях игрового типа (модели 1–3), в которых оба
игрока имеют комбинаторные ограничения на использование своих стратегий.
Рассмотрим три экономические задачи, которые могут быть представлены
указанными математическими моделями.
1. Постановка задач
Задача 1. В городе работают два конкурирующие предприятия, выпекающие
хлеб. Перед этими предприятиями стоит задача покупки автомобилей, которые
каждое утро должны развозить продукцию в их фирменные магазины (считается,
что вся вчерашняя продукция непригодна к употреблению). Первому предприя-
тию нужно выбрать m автомобилей из M предложенных для развоза продукции
в m фирменных магазинов. Аналогично второму предприятию нужно выбрать
n автомобилей из N предложенных. Прибыли обоих предприятий зависят от того,
сколько хлеба в каждый фирменный магазин будет завезено. Нужно разработать
оптимальный план развоза хлеба в магазины города.
Будем рассматривать эту задачу как антагонистическую игру двух игроков —
предприятий (антагонистической, как известно (см., например, [2, с. 11]), называ-
ют игру двух игроков с нулевой суммой).
Пусть x
iP — отношение количества продукции, которое можно отвезти i-м
из предложенных автомобилей, ко всему количеству продукции. Cоставим вектор
),...,,,( 21
x
M
xxx PPPP = для которого справедливо
38 ISSN 0572-2691
,0 M
x
i JiP ∈∀≥ (1)
MJ здесь и далее обозначает множество первых M натуральных чисел
}.,,2,1{ M
Пусть ),,,( 21 mxxxX = — вектор, характеризующий объемы развоза про-
дукции первым предприятием. Его компонента под номером i — часть продук-
ции, завезенная в фирменный магазин первого предприятия с номером i. По-
скольку в каждый магазин привозит продукцию один автомобиль, а автомобили
выбираются из M предложенных, то обозначив ),,,,( 121 −= mxxxX получаем
),(),,,( 1
121
xm
Mm PExxxX −
− ∈= (2)
где )( xk
M PE — множество k размещений из M элементов вектора .xP Кроме то-
го, в магазины должна развозиться вся продукция, поэтому компоненты вектора
),,,( 21 mxxxX = должны удовлетворять условию
,1
1
=∑
=
m
i
ix (3)
т.е. все автомобили, кроме последнего, развозят часть продукции ,ix ,1−∈ mJi
а последний автомобиль — часть продукции .1
1
1
∑
−
=
−
m
i
ix
Введем аналогичные векторы и для второго предприятия: вектор =yP
),,,,( 21
y
N
yy PPP = для которого
,0 N
y
j JjP ∈∀≥ (4)
и вектор ),,,,( 21 nyyyY = характеризующий развоз продукции вторым пред-
приятием. Тогда
);(),,,( 1
121
yn
Nn PEyyyY −
− ∈= .1
1
=∑
=
n
j
jy (5)
Сумма прибылей обоих предприятий равна максимально возможной прибы-
ли за продукцию. Оба производителя стремятся получить по возможности
наибольшую прибыль, т.е. максимально увеличить разность между своей прибы-
лью и прибылью конкурента. Составим матрицу
,
21
22221
11211
=
mnmm
n
n
aaa
aaa
aaa
A
(6)
где ija — разность прибылей первого и второго производителей в том случае, ес-
ли бы вся продукция первого завозилась в его магазин под номером i, а вся про-
дукция второго — в его магазин под номером j.
Проблемы управления и информатики, 2006, № 3 39
Пусть ),,( YXF функция прибылей, — это разность прибылей первого и вто-
рого производителей, если ),,,( 21 mxxxX = и ).,,,( 21 nyyyY = Если бы
первый производитель завез всю продукцию в свой фирменный магазин под но-
мером i, а работа второго характеризовалась бы вектором ),,,,( 21 nyyyY = то
.),(
1
∑
=
=
n
j
jij yaYXF Но первый производитель тоже работает, и вектор =X
),,,( 21 mxxx = характеризует объемы развоза его продукции, поэтому
.),(
11
∑∑
==
=
n
j
jij
m
i
i yaxYXF (7)
Оптимальные стратегии игроков определяем так же, как в классической тео-
рии игр (см., например, [2, с. 21]): цель первого игрока — за счет изменения ком-
понент вектора ),,,( 21 mxxxX = максимально увеличить свою минимальную
прибыль ),,( YXF т.е. нужно найти такие X и Y, при которых достигается нижняя
цена игры );,(minmax YXF
nm JjJi ∈∈
=α второй игрок за счет своих смешанных страте-
гий стремится сделать свой максимальный проигрыш минимальным, т.е. нужно
найти верхнюю цену игры ).,(maxmin YXF
nm JiJj ∈∈
=β
В классической теории игр справедлива такая теорема (см., например, [2, с. 30]):
для матричной игры с любой матрицей A величины ),(minmax YXF
ji
=α и =β
),(maxmin YXF
ij
= существуют и равны величине υ, если
,1;0),,,(
1
21
=≥=∈= ∑
=
m
i
iimm xxXSxxxX
.1;0),,,(
1
21
=≥=∈= ∑
=
n
j
jjnn yyYSyyyY
Величину υ называют ценой игры.
Из этой теоремы следует, что если бы компоненты вектора X выбирались из
mS произвольно, то задача 1 имела бы цену игры
),(maxmin),(minmax YXFYXF
mnnm SXSYSYSX ∈∈∈∈
==υ
для пары векторов ),,,( **
2
*
1
*
mxxxX = и ).,,,( **
2
*
1
*
nyyyY = Но в общем случае
)(),,,(:),,,( 1*
1
*
2
*
1
***
2
*
1
* xm
Mmm PExxxXxxxX −
− ∉== и (или) ,,( *
2
*
1
* yyY =
,)(),,,(:), 1*
1
*
2
*
1
** yn
Nnn PEyyyYy −
− ∉= поэтому в нашей задаче, как прави-
ло, нижняя цена игры не равна верхней, а значение υ определяется следующим
образом:
),,(
21 ji YXF=υ (8)
где
1iX — оптимальная стратегия первого игрока,
),,(minmax),(
11
YXFYXF
ji
ji =α= (9)
40 ISSN 0572-2691
2jY — оптимальная стратегия второго игрока,
).,(maxmin),(
22
YXFYXF
ij
ji =β= (10)
Можно доказать, что цена игры υ находится в интервале между нижней и
верхней ценами игры и в частном случае (когда )β=α равна им.
Математическая модель задачи 1 имеет следующий вид.
Модель 1. Найти цену игры (8) и оптимальные стратегии игроков
1iX — из
выражения (9) и
2jY — из выражения (10) при условиях (1)–(7).
Задачи, которые имеют описанную выше математическую модель, назовем
матричными задачами теории игр с комбинаторными ограничениями І типа,
определяемыми размещениями, на стратегиях обоих игроков.
Задача 2. В городе работают два конкурирующие предприятия, выпекающие
хлеб. Как и в задаче 1, хлеб считается скоропортящейся продукцией, поэтому
каждое утро перед предприятиями возникает проблема развоза продукции по ма-
газинам. Первое предприятие имеет m разных автомобилей, которыми хлеб разво-
зится в m фирменных магазинов. Грузоподъемность автомобилей разная, поэтому
в каждый магазин попадает разное количество хлеба. Перед вторым предприяти-
ем стоит задача покупки n автомобилей из N предложенных для развоза своей
продукции в n фирменных магазинов. Прибыли обоих предприятий зависят от то-
го, сколько хлеба в каждый фирменный магазин будет завезено. Нужно разрабо-
тать оптимальный план развоза хлеба.
Построим математическую модель этой задачи.
Пусть x
iP — отношение грузоподъемности i-го автомобиля первого пред-
приятия к сумме грузоподъемностей всех автомобилей этого производителя. Со-
ставим вектор ),,,,( 21
x
m
xxx PPPP = для которого
.0;1
1
m
x
i
m
i
x
i JiPP ∈∀≥=∑
=
(11)
Пусть ),,,( 21 mxxxX = — вектор, характеризующий объемы развоза про-
дукции первым предприятием. Его компонента под номером i — это часть про-
дукции, завезенная в фирменный магазин первого предприятия под номером i.
Поскольку каждый автомобиль привозит продукцию в один, свой магазин, то
компоненты вектора X получаем в результате перестановок компонент векто-
ра ,xP т.е.
),(),,,( 21
x
mm PExxxX ∈= (12)
где )( x
m PE — множество перестановок из m элементов вектора .xP
Векторы ),,,,( 21
y
N
yyy PPPP = ),,,,( 21 nyyyY = матрица A, функция
прибылей, цена игры и оптимальные стратегии игроков такие же, как и в задаче 1.
Таким образом, математическая модель задачи 2 имеет следующий вид.
Модель 2. Найти цену игры (8) и оптимальные стратегии игроков
1iX — из
выражения (9) и
2jY — из выражения (10) при условиях (4)–(12).
Задачи, которые имеют описанную выше математическую модель, назовем
матричными задачами теории игр с перестановочными ограничениями на страте-
гии первого игрока и комбинаторными ограничениями І типа, определяемыми
размещениями, на стратегии второго игрока.
Проблемы управления и информатики, 2006, № 3 41
Задача 3. В городе работают два конкурирующие предприятия по выпечке
хлеба. Как и в задаче 1, хлеб считается скоропортящейся продукцией, поэтому
каждое утро перед предприятиями возникает проблема развоза продукции по ма-
газинам. Перед первым предприятием стоит задача покупки m автомобилей из
M предложенных для развоза своей продукции в m фирменных магазинов. Второе
предприятие имеет n разных автомобилей, которыми хлеб развозится в n фирмен-
ных магазинов. Грузоподъемность автомобилей разная, поэтому в каждый мага-
зин попадает разное количество хлеба. Прибыли обоих предприятий зависят от
того, сколько хлеба в каждый фирменный магазин завезено. Нужно разработать
оптимальный план развоза хлеба в магазины города.
Построим математическую модель этой задачи.
Векторы ),,,( 21
x
M
xxx PPPP = и ),,,( 21 mxxxX = остаются такие же, как
и в задаче 1.
Пусть y
jP — отношение грузоподъемности j-го автомобиля второго пред-
приятия к сумме грузоподъемностей всех автомобилей этого производителя. Со-
ставим вектор ),,,,( 21
y
n
yyy PPPP = для которого
.0;1
1
n
y
j
n
j
y
j JjPP ∈∀≥=∑
=
(13)
Пусть ),,,( 21 nyyyY = — вектор, характеризующий объемы развоза про-
дукции вторым предприятием. Его компонента под номером j — часть продук-
ции, завезенная в его фирменный магазин под номером j. Поскольку каждый ав-
томобиль привозит продукцию в один, свой магазин, то компоненты вектора Y
получаем в результате перестановок компонент вектора ,yP т.е.
),(),,,( 21
y
nn PEyyyY ∈= (14)
где )( y
m PE — множество перестановок из n элементов вектора .yP
Матрица A, функция прибылей, цена игры и оптимальные стратегии игроков
такие же, как в задаче 1.
Математическая модель задачи 3 имеет следующий вид.
Модель 3. Найти цену игры (8) и оптимальные стратегии игроков
1iX — из
выражения (9) и
2jY — из выражения (10) при условиях (1)–(3), (6)–(10), (13), (14).
Задачи, которые имеют описанную выше математическую модель, назовем
матричными задачами теории игр с комбинаторными ограничениями І типа,
определяемыми размещениями, на стратегии первого игрока и перестановочными
ограничениями на стратегии второго игрока.
2. Графический метод для решения задач комбинаторной оптимизации
на размещениях игрового типа размерности n×2 и 2×m
В классической теории игр задачи размерности n×2 и 2×m решают графи-
ческим методом (см., например, [2, с. 49–55]). Задачи оптимизации на размещени-
ях игрового типа такой же размерности тоже будем решать графическим методом,
который предварительно модифицируем.
1. Рассмотрим графический метод для решения задач размерности .2 n×
1.А. Для моделей 1 и 3
;1),()( 21
1
1 =+∈= xxPExX x
M .0 M
x
i JiP ∈∀≥
42 ISSN 0572-2691
Пусть первый игрок смешивает свои стратегии с вероятностями 1x и .1 1x−
Тогда
.)(),(
1
22
1
11
2
11
∑∑∑∑
====
+
−==
n
j
jjj
n
j
jj
i
iij
n
j
j yaaayxxayYXF (15)
Первый игрок ищет величину ,1x которая максимизирует минимум ожидае-
мых выигрышей:
.)(minmax
1
22
1
11
1
+
− ∑∑
==
n
j
jjj
n
j
jj
jx
yaaayx
Для каждой стратегии второго игрока построим график ),( YXF как функ-
ции от 1x (рис. 1).
0 P1 MP …
F (X, Y)
υ
x1
1 1 − P1 … MP−1
— минимальный выигрыш
первого игрока для
каждой его стратегии
и максимальный проигрыш
второго для каждой его
стратегии;
— точки, в которых
достигается нижняя
и верхняя цена игры;
— точка, в которой
достигается цена игры
).,(
21 ji YXF=υ
),(
22 ji YXF
),(
11 ji YXF
Рис. 1
Пусть
;1);()(},min{ 21
1
121 =+∈=∀= xxPExXxxP x
Mj .)(1 x
M PEM =
Все числа jP упорядочим по возрастанию. Обозначим на оси 1Ox точки jP и
.1 Mj JjP ∈∀− Для того чтобы найти ,
1iX построим нижнюю огибающую пря-
мых, которая показывает минимальный выигрыш первого игрока независимо от
того, что делает второй. Отметим на этой огибающей значение функции ),,( YXF
когда jPx =1 и .11 Mj JjPx ∈∀−= То из отмеченных значений ,1x при котором
величина функции больше, и будет оптимальным. Находим ).1,( 111
xxX i −=
Графики функции ),( YXF построены при всех возможных стратегиях вто-
рого игрока, поэтому ),(maxmin),(
22
YXFYXF
ij
ji = нужно искать на одной из
этих прямых. Для этого на каждой прямой необходимо найти максимальное зна-
чение функции ),,( YXF а потом из этих максимальных значений — минималь-
ное. Стратегия второго игрока, отвечающая этому значению функции, и
Проблемы управления и информатики, 2006, № 3 43
будет .
2jY Максимум функции ),( YXF достигается при 11 =x (если ),( YXF
монотонно возрастает), при 01 =x (если монотонно убывает) или при любом зна-
чении 1x (если ).),(
1
2∑
=
=
n
j
jj yaYXF Цена игры ),(
21 ji YXF=υ находится на
прямой, соответствующей стратегии
1iX первого игрока, в точке, в которой стра-
тегия второго игрока ).1,( 112
yyY j −=
1.Б. Для модели 2
),(),( 221
xPExxX ∈= .0;1 221 JiPPP x
i
xx ∈∀≥=+
Пусть первый игрок смешивает свои стратегии с вероятностями 1x и .1 1x−
Тогда функция выигрышей ),( YXF имеет вид (15). Первый игрок ищет
величину ,1x которая максимизирует минимум ожидаемых выигрышей:
.)(minmax
1
22
1
11
1
+
− ∑∑
==
n
j
jjj
n
j
jj
jx
yaaayx
Для каждой стратегии второго игрока построим график функции ),( YXF
как функции от 1x (рис. 2).
0
F (X, Y)
υ
x1
1 1 − P P
— минимальный выигрыш
первого игрока для
каждой его стратегии
и максимальный проигрыш
второго для каждой его
стратегии;
— точки, в которых
достигается нижняя
и верхняя цена игры;
— точка, в которой
достигается цена игры
).,(
21 ji YXF=υ
),(
22 ji YXF
),(
11 ji YXF
Рис. 2
Пусть }.,min{ 21
xx PPP = Обозначим на оси 1Ox точки P и .1 P− Для того
чтобы найти ,
1iX построим нижнюю огибающую прямых, которая показывает
минимальный выигрыш первого игрока независимо от того, что делает второй.
Отметим на этой огибающей значение функции ),,( jYXF когда Px =1 и
.11 Px −= То значение 1x из этих двух, при котором значение функции больше, и
будет оптимальным. Получаем ).1,( 111
xxX i −= Оптимальную стратегию второ-
го игрока
2jY и цену игры находим так же, как в случае 1.А для моделей 1 и 3.
2. Рассмотрим графический метод для решения задач размерности .2×m
44 ISSN 0572-2691
2.А. Для моделей 1 и 2
;1),()( 21
1
1 =+∈= yyPEyY y
N .0 N
y
j JjP ∈∀≥
Пусть второй игрок смешивает свои стратегии с вероятностями 1y и .1 1y−
Тогда
.)(),(
1
22
1
11
2
11
∑∑∑∑
====
+
−==
m
i
iii
m
i
ii
j
jij
m
i
i xaaaxyyaxYXF (16)
Второй игрок ищет величину ,1y которая минимизирует максимум функции
проигрыша:
.)(maxmin
1
22
1
11
1
+
− ∑∑
==
m
i
iii
m
i
ii
iy
xaaaxy
Для каждой стратегии первого игрока построим график функции ),( YXF
как функции от 1y (рис. 3).
0 P1 MP …
F (X, Y)
υ
y1
1 1 − P1 … MP−1
— минимальный выигрыш
первого игрока для
каждой его стратегии
и максимальный проигрыш
второго для каждой его
стратегии;
— точки, в которых
достигается нижняя
и верхняя цена игры;
— точка, в которой
достигается цена игры
).,(
21 ji YXF=υ
),(
11 ji YXF
),(
22 ji YXF
Рис. 3
Пусть
,1);()(},{min 21
1
121 =+∈=∀= yyPEyYyyP y
Nj .)(1 y
N PEN =
Все числа jP упорядочим по возрастанию. Обозначим на оси 1Ox точки jP и
.1 Nj JjP ∈∀− Для того чтобы найти ,
2jY построим верхнюю огибающую пря-
мых, которая показывает максимальный проигрыш второго игрока независимо от
того, что делает первый. Отметим на этой огибающей значение функции
),,( YXF когда jPy =1 и .11 Nj JjPy ∈∀−= То из отмеченных значений 1y ,
при котором значение функции меньше, и будет оптимальным. Получаем =
2jY
).1,( 11 yy −=
Графики функции ),( YXF построены при всех возможных стратегиях пер-
вого игрока, поэтому ),(minmax),(
11
YXFYXF
ji
ji = нужно искать на одной из
Проблемы управления и информатики, 2006, № 3 45
этих прямых. Для этого на каждой прямой необходимо найти минимальное зна-
чение функции ),,( YXF а потом из этих значений — максимальное. Стратегия
первого игрока, которая соответствует этому значению функции, и будет .
1iX
Минимальное значение функции ),( YXF достигается при 01 =y (если ),( YXF
монотонно возрастает), при 11 =y (если монотонно убывает) или при любом зна-
чении 1y (если ]).1,0[),( 1
1
2 ∈∀= ∑
=
yxaYXF
m
i
ii Цена игры )(
21, ji YXF=υ нахо-
дится на прямой, соответствующей стратегии
1iX первого игрока, в точке, в ко-
торой стратегия второго игрока ).1,( 112
yyY j −=
2.Б. Для модели 3
),(),( 221
yPEyyY ∈= .0;1 221 JjPPP y
j
yy ∈∀≥=+
Пусть первый игрок смешивает свои стратегии с вероятностями 1x и .1 1x−
Тогда функция выигрышей ),( YXF имеет вид (16). Первый игрок ищет величи-
ну ,1x которая максимизирует минимум ожидаемых выигрышей:
.)(maxmin
1
22
1
11
1
+
− ∑∑
==
m
i
iii
m
i
ii
iy
xaaaxy
Для каждой стратегии первого игрока построим график функции ),( YXF
как функции от 1y (рис. 4).
0
F (X, Y)
υ
y1
1
— минимальный выигрыш
первого игрока для
каждой его стратегии
и максимальный проигрыш
второго для каждой его
стратегии;
— точки, в которых
достигается нижняя
и верхняя цена игры;
— точка, в которой
достигается цена игры
).,(
21 ji YXF=υ
),(
11 ji YXF
),(
22 ji YXF
P 1 − P
Рис. 4
Пусть }.,min{ 21
xx PPP = Обозначим на оси 1Oy точки P и .1 P− Для того
чтобы найти ,
2jY построим верхнюю огибающую прямых, которая показывает
максимальный проигрыш второго игрока независимо от того, что делает первый.
Отметим на этой огибающей значение функции ),,( YXF когда Py =1 и
.11 Py −= То значение 1y из этих двух, при котором значение функции меньше,
46 ISSN 0572-2691
и будет оптимальным. Находим ).1,( 112
yyY j −= Оптимальную стратегию пер-
вого игрока
1iX и цену игры ),(
21 ji YXF=υ ищем так же, как и в пункте 2.А для
моделей 1 и 2.
3. Поиск решений задач оптимизации на размещениях
игрового типа произвольной размерности
Далее рассмотрим задачи, в которых 2≠m и .2≠n Решать такие задачи
можно двумя способами.
1-й способ: свести задачи отыскания
1iX и
2jY к комбинаторным задачам
оптимизации на размещениях и решить их методом отсечения (см. [12, 13]).
2-й способ: составить новую матрицу выигрышей ).( ijaA ′=′ В этой матрице
элемент ija′ — это значение функции прибыли ),( YXF в том случае, когда пер-
вый игрок применит свою i-ю стратегию, а второй — свою j-ю стратегию. Теперь,
как и в обычных матричных играх, ищем минимумы в каждой строке, а потом из
них — максимум. Этот максимум и есть нижняя цена игры, а строка, которая ему
соответствует, — оптимальная стратегия первого игрока .
1iX Для поиска верхней
цены игры ищем максимум минимумов всех столбцов. Тот столбец, который со-
ответствует этому максимуму, — оптимальная стратегия второго игрока .
2jY Це-
на игры υ находится на пересечении строки, которая соответствует оптимальной
стратегии первого игрока ,
1iX и столбца, который соответствует оптимальной
стратегии второго игрока .
2jY Этот способ можно применять для матриц с не-
большим количеством строк и столбцов.
Выводы. Таким образом, впервые сформулированы и исследованы задачи
комбинаторной оптимизации на размещениях и перестановках игрового типа (за-
дачи комбинаторной оптимизации на перестановках игрового типа уже рассмат-
ривались в [14]). Предложены методы для решения задачи оптимизации на раз-
мещениях и перестановках игрового типа, развит графический метод классиче-
ской теории игр для решения задач размерности n×2 и .2×m
Предложенные методы для решения задач комбинаторной оптимизации на
размещениях и перестановках игрового типа можно использовать, как правило,
лишь для задач небольшой размерности, поэтому нужно разрабатывать методы,
которые позволят решать задачи большой размерности.
О.О. Ємець, Н.Ю. Устьян
РОЗВ’ЯЗОК ДЕЯКИХ ЗАДАЧ КОМБІНАТОРНОЇ
ОПТИМІЗАЦІЇ НА РОЗМІЩЕННЯХ
І ПЕРЕСТАНОВКАХ ІГРОВОГО ТИПУ
Побудовано та досліджено математичні моделі задач оптимізації на розміщен-
нях і перестановках ігрового типу, в яких обидва гравці мають комбінаторні
обмеження на використання своїх стратегій. Для задач вимірності 2 × n та m × 2
запропоновано модифікований графічний метод.
Проблемы управления и информатики, 2006, № 3 47
O.A. Yemets, N.Yu. Ustian
SOLVING OF SOME OPTIMIZATION
PROBLEMS ON ARRANGEMENTS
AND PERMUTATIONS OF GAME TYPE
Mathematical models of optimization problems on arrangements and permutations of
game type in which both players have combinatorial restrictions for using their strat-
egies are built and studied. The modified graphic method for solving such problems
of dimension 2 × n and m × 2 is offered.
1. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. — М. : Наука,
1970. — 780 с.
2. Крушевский А.В. Теория игр. — Киев : Вища шк., 1977. — 215 с.
3. Ляшенко И.Н., Карагодова Е.А., Чернышова Н.В., Шор Н.З. Линейное и нелинейное про-
граммирование / Под ред. И.Н. Ляшенко. — Киев : Вища шк., 1975. — 372 с.
4. Сергиенко И.В. Математические модели и методы решения задач дискретной оптими-
зации. — Киев: Наук. думка, 1988. — 472 с.
5. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации : Проблемы, методы, решения,
исследования. — Киев: Наук. думка, 2003. — 263 с.
6. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Киев :
ІСДО, 1993. — 188 с.
7. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та мето-
ди. — Полтава : РВЦ ПУСКУ, 2005. — 103 с.
8. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в матема-
тическом программировании : Учеб. пособие. — Киев : УМК ВО, 1992. — 92 с.
9. Емец О.А., Евсеева Л.Г., Романова Н.Г. Интервальная математическая модель комбинатор-
ной задачи цветной упаковки прямоугольников // Кибернетика и системный анализ. —
2001. — № 3. — С. 131–138.
10. Ємець О.О., Ємець Є.М. Відсікання в лінійних частково комбінаторних задачах евклідової
комбінаторної оптимізації // Доп. НАН України. — 2000. — № 9. — С. 105–109.
11. Емец О.А., Колечкина Л.Н. Решение задач оптимизации с дробно-линейными целевыми
функциями и дополнительными линейными ограничениями на перестановках // Киберне-
тика и системный анализ. — 2004. — № 3. — С. 30–43.
12. Емец О.А., Барболина Т.Н. Решение линейных задач оптимизации на размещениях методом
отсечений // Там же. — 2003. — № 6. — С.131–141.
13. Барболина Т.Н., Емец О.А. Полностью целочисленный метод отсечения для решения ли-
нейных условных задач оптимизации на размещениях // Журн. вычисл. математики и мат.
физики. — 2005. — 45, № 2. — С. 254–261.
14. Ємець О.О., Устьян Н.Ю. Ігрова комбінаторна модель однієї задачі сільськогосподар-
ського виробництва // Матеріали VII Міжнар. наук.-практ. конф. «Наука і освіта 2004».
Т. 70. — Дніпропетровськ : Наука і освіта, 2004. — С. 46–49.
Получено 14.12.2005
1. Постановка задач
2. Графический метод для решения задач комбинаторной оптимизации на размещениях игрового типа размерности и
3. Поиск решений задач оптимизации на размещениях игрового типа произвольной размерности
|
| id | nasplib_isofts_kiev_ua-123456789-206809 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2026-03-16T04:19:20Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Устьян, Н.Ю. 2025-09-22T15:44:55Z 2006 Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа / О.А. Емец, Н.Ю. Устьян // Проблемы управления и информатики. — 2006. № - 3. — С. 37-47 . — Бібліогр.: 14 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206809 519.85 Побудовано та досліджено математичні моделі задач оптимізації на розміщеннях і перестановках ігрового типу, в яких обидва гравці мають комбінаторні обмеження на використання своїх стратегій. Для задач вимірності 2 × n та m × 2 запропоновано модифікований графічний метод. Mathematical models of optimization problems on arrangements and permutations of game type in which both players have combinatorial restrictions for using their strategies are built and studied. The modified graphic method for solving such problems of dimension 2 × n and m × 2 is offered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа Розв’язок деяких задач комбінаторної оптимізації на розміщеннях і перестановках ігрового типу Solving Selected Optimization Problems on Arrangements and Permutations of a Game Type Article published earlier |
| spellingShingle | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа Емец, О.А. Устьян, Н.Ю. Оптимальное управление и методы оптимизации |
| title | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| title_alt | Розв’язок деяких задач комбінаторної оптимізації на розміщеннях і перестановках ігрового типу Solving Selected Optimization Problems on Arrangements and Permutations of a Game Type |
| title_full | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| title_fullStr | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| title_full_unstemmed | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| title_short | Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| title_sort | решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/206809 |
| work_keys_str_mv | AT emecoa rešenienekotoryhzadačkombinatornoioptimizaciinarazmeŝeniâhiperestanovkahigrovogotipa AT ustʹânnû rešenienekotoryhzadačkombinatornoioptimizaciinarazmeŝeniâhiperestanovkahigrovogotipa AT emecoa rozvâzokdeâkihzadačkombínatornoíoptimízacíínarozmíŝennâhíperestanovkahígrovogotipu AT ustʹânnû rozvâzokdeâkihzadačkombínatornoíoptimízacíínarozmíŝennâhíperestanovkahígrovogotipu AT emecoa solvingselectedoptimizationproblemsonarrangementsandpermutationsofagametype AT ustʹânnû solvingselectedoptimizationproblemsonarrangementsandpermutationsofagametype |