Математические методы в коммерческой деятельности. Буравлева О.Ю. - 14 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

njx
mibxa
xcXZ
j
n
j
ijij
n
j
jj
1,j ,0
,,...,2,1,
max(min),)(
1
1
∈∀≥
==
→=
∑
∑
=
=
(3.2)
0≥
i
b
,i
∀
mi ,1∈
Для исходной задачи составляется расширенная задача. При этом используется искусственные пе-
ременные.
Искусственными переменными называются неотрицательные переменные, которые вводятся в
ограничения-равенства для получения начального опорного решения с базисом из единичных векторов.
Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с
коэффициентом +1 и в целевую функцию в задаче на максимум с коэффициентом –M, а в задаче на мини-
мум с коэффициентом +M. Число M сколь угодно большое по сравнению с единицей (M >> ).1
В общем случае расширенная задача на максимум имеет вид:
=++++
=++++
=++++
→−−−−+++=
+
+
+
+++
,...
.............................................
,...
,...
max,......)(
2211
222222121
111212111
212211
mnmnmnmm
nnn
nnn
mnnnnn
bxxaxaxa
bxxaxaxa
bxxaxaxa
MxMxMxxcxcxcXZ
....,,2,10,...,,2,10 mibmnjx
ij
=
≥
+
=
≥ (3.3)
или в компактной записи
.0
,0
,,...,2,1,
max,)(
1
11
ib
jx
mibxxa
MxxcXZ
i
j
n
j
iinjij
m
i
in
n
j
jj
∀≥
∀≥
==+
→−=
∑
∑∑
=
+
=
+
=
(3.4)
Данная задача имеет начальное опорное решение
)...,,,,0...,,0,0(
21
1
m
bbbX =
с базисом
)....,,,(
21
1
mnnn
AААБ
+++
=
Здесь и в дальнейшем для расширенной задачи отмечаются чертой сверху следующие величины:
целевая функция )(XZ , допустимое решение
X
, опорные решения
i
X , базисы опорных решений
i
Б , об-
ласть допустимых решений .G
Для обоснования метода используются две леммы и три теоремы.
Лемма 3.1 Любому допустимому решению )...,,,(
21 n
kkkX
=
исходной задачи программирования со-
ответствует допустимое решение расширенной задачи )0...,,0,...,,,(
21 n
kkkX = и, наоборот, любому до-
пустимому решению расширенной задачи
)0...,,0,...,,,(
21 n
kkkX =
соответствует допустимое решение ис-
ходной задачи )...,,,(
21 n
kkkX = . При этом значение целевых функций задач на соответствующих реше-
ниях совпадают, т.е. )()( XZXZ = .
Лемма 3.2 Значение целевой функции расширенной задачи на максимум (минимум) на любом
допустимом решении =
k
X )0...,,0,...,,,(
21 n
kkk= , у которого все искусственные переменные равны нулю,
больше (меньше) значения целевой функции на любом допустимом решении )...,,,...,,,(
121 mnnnl
lllllX
++
= ,
у которого хотя бы одна искусственная переменная отлична нуля.
Теорема 3.2 (признак оптимальности решения). Если расширенная задача линейного программи-
рования имеет оптимальное решение )0...,,0,...,,,(
21
*
n
xxxX = , у которого все искусственные переменные

Страницы