Бескоалиционные игры в нормальной форме. Часть 1. Григорьева К.В. - 31 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

Составители: 

Рубрика: 

60 61
2
x
1
x
1
s
2
s
3
s
4
s
1
s
1*
–1
1 0 0 0 1
2
s
1 0 0 1 0 0 2
3
s
2 1 0 0 1 0 6
4
s
1 2 0 0 0 1 8
F
2 3 0 0 0 0 0
Если все элементы последнего столбца меньше нуля (кроме
последнего элемента последней строки
F
), то решение неограниченноее
и оптимального решения не существует.
Условия оптимальности: если все элементы последней строки
0
£
F
, то полученное решение оптимально.
Выбор генерального столбца (кроме последнего): в последней
строке выбираем положительный элемент.
Выбор генеральной строки: за генеральную строку берется та
строка (кроме последней), в которой отношение свободного члена
к положительному элементу генерального столбца было бы минимальным.
2
x
1
x
1
s
2
s
3
s
4
s
2
x
1 –1
1 0 0 0 1
2
s
0 1*
–1
1 0 0 1
3
s
0 3 –2
0 1 0 4
4
s
0 3 –1
0 0 1 7
F
0 5 –2
0 0 0 –2
Повторяем итерации.
2
x
1
x
1
s
2
s
3
s
4
s
2
x
1 0 0 1 0 0 2
1
x
0 1 –1
1 0 0 1
3
s
0 0 1*
–3
1 0 1
4
s
0 0 2 –3
0 1 4
F
0 0 3 –5
0 0 –7
2
x
1
x
1
s
2
s
3
s
4
s
2
x
1 0 0
1 0 0 2
1
x
0 1 0
–2
1 0 2
1
s
0 0 1
–3
1 0 1
4
s
0 0 0
3*
–2
1 2
F
0 0 0
4 –3
0 –10
2
x
1
x
1
s
2
s
3
s
4
s
2
x
1 0 0
0 2/3 –1/3
4/3
1
x
0 1 0
0 –1/3
2/3 10/3
1
s
0 0 1
0 –1 1 3
2
s
0 0 0
1 –2/3
1/3 2/3
F
0 0 0
0 –1/3
–4/3
338-
.34;310;32123212
21maxmin
=
=
=
Þ
-
=
xxzF
Пример 2. Метод искусственного базиса для основной задачи.
ï
î
ï
í
ì
=³
=-+-
-=--
®
+
-
=
3,1,0
1123
222
max432
321
321
321
jx
xxx
xxx
xxxz
j
ï
î
ï
í
ì
=³
=+-+-
=+++-
3,1,0
1123
222
2321
1321
jx
wxxx
wxxx
j
Умножив обе части первого
уравнения на (–1) и прибавив к
левым частям обоих уравнений
искусственные неизвестные
w
1
и w
2
, получим
расширенную систему
()
min
21
®+=j wwx
Составим на множестве планов
расширенной системы
вспомогательную функцию
(
)
()
.1353
;5313
321
32121
=-+-j
+
-
+
=
+
=
j
xxxx
xxxwwx

Страницы