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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

оставались неотрицательными. Тогда найденное базисное решение будет допустимым, т.е. опорным.
Получим правило выбора разрешающих элементов для преобразований Жордана, при котором пра-
вые части системы уравнений остаются неотрицательными.
Пусть разрешающим элементом для преобразования Жордана является коэффициент
lk
a при неиз-
вестной
k
x в уравнении с номером l. В результате преобразования Жордана правые части уравнений,
как известно, пересчитываются по следующим формулам:
,
1
1
1
k
a
b
b =
′
,
1
1
ik
k
ii
a
a
b
bb −=
′
i = 1, 2,…, m, i ≠ l.
1 Для того чтобы правая часть
′
l
b уравнения с разрешающим элементом
lk
a оставалась неотрица-
тельной, должно выполняться неравенство:
так как 0≥
l
b , то первое условие для разрешающего элемента
lk
a состоит в том, что он должен быть по-
ложительным, т.е.
lk
a ≥ 0.
2 Неотрицательными также должны быть правые части остальных уравнений, т.е.
,0
1
1
≥−=
′
ik
k
ii
a
a
b
bb i = 1,2, …, m, i ≠ l.
Для получения требований, налагаемых на разрешаемый элемент
lk
a , рассмотрим два случая:
а) если 0≤
lk
a , то в силу того, что ,0 ib
i
∀
≥ ,0≥
i
b
lk
a ≥ 0, без дополнительных условий ;0≥
′
l
b
б) если же
ik
a > 0 , то неравенство
ok
Q
0
1
1
≥−=
′
ik
k
ii
a
a
b
bb
поделим на
,ik
a получим
lk
l
ik
i
a
b
a
b
≥
.
Данное неравенство должно выполняться для любого уравнения с номером i, в котором
ik
a 0f . Для
удобства вычислений вводят вспомогательный параметр
ok
Q .
lk
l
ik
i
ok
a
b
a
b
Q =
= min
при
ik
a > 0, (2.4)
где k – номер вектора условия
k
A , вводимого в базис (выбираемого столбца матрицы системы ограни-
чений), а l – номер вектора
k
A , выводимого из базиса (номер строки матрицы, в которой следует выби-
рать разрешающий элемент для преобразований Жордана ).
С помощью данного условия можно выбрать разрешающий элемент в любом столбце k матрицы систе-
мы ограничений, в котором имеется хотя бы один положительный элемент. Если нарушить это условие при
выборе разрешающего элемента, в правой части системы появятся отрицательные величины.
Используя данное условие, можно найти начальное опорное решение.
Аналогичное условие может быть использовано при переходе от одного опорного решения к дру-
гому.
Пусть система уравнений-ограничений путем выбора разрешающих элементов приведена к равно-
сильной разрешенной так, что правые части системы сохранились неотрицательными, и имеет вид:
.,1,0
,......
.....................................................................
,......
,......
01)1(
20221)1(22
1011)1(11
njx
xxxxxxxx
xxxxxxxx
xxxxxxxx
j
mnmnkmkmmmm
nnkkmm
nnklkmm
∈∀≥
=+++++
=+++++
=+++++
++
++
++
Тогда базисное решение )0...,,0,...,,,(
020101 m
xxxX = является допустимым и опорным решением с ба-
зисом из единичных векторов
)....,,,(
211 m
AAAB =
Для перехода от этого опорного решения к новому необходимо использовать соотношение
lk
l
ik
i
k
x
x
x
x
Q
00
0
min =
=
при ,0f
ik
x (2.5)
где k – номер вектора, вводимого в базис; l – номер вектора, выводимого из базиса;
0i
x – координаты
опорного решения;
ik
x – коэффициенты разложения вектора
k
A по базису опорного решения.
,0
1
1
1
≥=
′
k
a
b
b

Страницы