Этап 0. Возьмем
q
0
= (0
,
0
,
5
,
0
,
5
,
0)
.
Этап 1. Вычисления дают ситуацию
(
p
0
, q
0
)
:
p
0
= (0
,
0
,
33
,
0
,
0
,
67)
,
q
0
= (0
,
0
,
67
,
0
,
33
,
0)
, в которой
F
=
−
0
,
33
. Двойственные перемен-
ные
λ
0
= (0
,
0
,
67
,
0
,
0
,
33)
,
μ
0
= (0
,
0
,
0
,
1)
.
Этап 2. Заменим стратегию
q
0
на
λ
0
(при этом изменилось значение
целевой функции на
F
=
−
0
,
45
) и выполним вычисления этапа 1.
В результате найдем искомое равновесие
p
= (0
,
33
,
0
,
0
,
0
,
67)
, q
= (0
,
0
,
33
,
0
,
0
,
67)
, v
= 2
,
33
, u
= 2
.
Всего потребовалось решить четыре задачи ЛП.
Заключение.
Задачи ЛП имеют полиномиальную сложность ре-
шения [6]. Это дает основание предположить, что предложенный в
работе алгоритм имеет такую же вычислительную сложность.
СПИСОК ЛИТЕРАТУРЫ
1. П е т р о с я н Л. А., З е н к е в и ч Н. А., С е м и н а Е. А. Теория игр. – М.:
Высш. шк., 1998.
2. В о л к о в И. К., З а г о р у й к о Е. А. Исследование операций. – М.: Изд-во
МГТУ им. Н.Э. Баумана, 2004.
3. А ш м а н о в С. А. Линейное программирование. – М.: Наука, 1981.
4. В а с и л ь е в Ф. П. Численные методы решения экстремальных задач. – М.:
Наука, 1980.
5. И о ф ф е А. Д., Т и х о м и р о в В. М. Теория экстремальных задач. – М.:
Наука, 1974.
6. Х а ч и я н Л. Г. Полиномиальный алгоритм в линейном программировании //
ДАН СССР. – 1979. – T. 244. – C. 1093–1096.
Статья поступила в редакцию 24.12.2007
Николай Семенович Васильев окончил МГУ им. М.В. Ломоносова в 1974 г. Д-р физ.-
мат. наук, профессор кафедры “Высшая математика” МГТУ им. Н.Э. Баумана. Автор
более 50 научных работ в области теории оптимального управления и моделирования
распределенных телекоммуникационных систем.
N.S. Vasiliev graduated from the Lomonosov Moscow State University in 1974. D. Sc.
(Phys.-Math.), professor of “Higher Mathematics” department of the Bauman Moscow
State Technical University. Author of more than 50 publications in the field of theory of
optimal control and simulation of distributed telecommunication systems.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 3
59
