Основы теории систем и системного анализа. Матвеев Ю.Н. - 87 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

87
miy
i
,1,0 =≥ . Внешним признаком отсутствия допустимого решения
является отсутствие отрицательных коэффициентов в какой-то строке y
r
таблицы, где 0<
r
b . Тогда
),....(
2211 nrnrrrr
xxxby
α
α
α
+
+
+
−=
где
0<
r
b и
njx
jrnrr
,1,0,0....,,0,0
21
=≥≥≥≥
ααα
. В этом случае y
r
не
может стать неотрицательной величиной.
Пример 9
Пусть )322(10
3214
xxxy
+
+−
−
= . При 100
4321
−=→
=
=
=
yxxx .
Допустим, x
1
= 1, x
2
= 2, x
3
= 3. Тогда 25)942(10
4
−
=++
−
−
=
y ,
следовательно, опорного решения нет.
В случае, когда опорного решения нет, необходимо производить
замены
ij
yx ↔ так, чтобы после каждого «переразрешения» происходило
приближение к границе ОДР, т.е. с каждым шагом число отрицательных
базисных переменных должно убывать или, по крайней мере, убывали бы
по абсолютной величине отрицательные свободные члены. Для замены
ij
yx ↔ необходимо выбрать разрешающий элемент. Существует ряд
способов выбора разрешающего элемента для наиболее быстрого
движения к опорному решению. Суть одного из них заключается в
следующем.
Пусть в одном из уравнений системы (2.51) свободный член 0
<
r
b .
Рассматриваем в этой строке коэффициенты
rj
α
при свободных
переменных
njx
j
,1, = . Напомним, что если все nj
rj
,1,0 =>
α
, то задача
ЛП не имеет решения.
Пусть 0<
rp
α
. Выбираем столбец х
р
в качестве разрешающего, где
рассматриваем все коэффициенты
mi
ip
,1, =
α
, которые имеют одинаковые
знаки (плюс или минус) с соответствующими свободными членами
mib
i
,1, = . В качестве разрешающего выбирается тот коэффициент, для
которого отношение к нему соответствующего свободного члена
минимально:
mi
b
i
ip
rp
,1,min =→
α
α
.
Выбор разрешающего элемента однозначно определяет
разрешающую строку. Далее применяется процедура «переразрешения»,
т.е. замена
pr
xy ↔ .
Пример 10
Определить (если оно существует) опорное решение ОЗЛП.
Линейная функция W для простоты не приводится.

Страницы