Составители:
Рубрика:
64
перейти от одного опорного решения не к произвольному базисному решению, а снова к
опорному решению (хотя бы даже не к «лучшему»). Для этого достаточно дополнить
правила замещения следующим правилом выбора ключевого элемента.
В качестве ключевого столбца (k-го) может быть выбран любой столбец матрицы
системы, в котором имеется хотя бы один положительный элемент a
ik
. Выбрав таким
образом ключевой столбец (k-й), составляем отношения
ik
i
i
a
b
=
β
свободных членов
системы к положительным элементам ключевого столбца. Для отрицательных и нулевых
элементов ключевого столбца эти отношения не вычисляются (в дополнительном столбце
чисел
β
i
>0 делаются прочерки). Все числа
β
i
положительны, так как мы рассматриваем
невырожденную задачу.
Та (s-я) строка матрицы, для которой число
β
i
оказывается наименьшим,
выбирается в качестве ключевой строки.
Докажем, что при таком выборе ключевого элемента (a
sk
) мы получим снова
опорное решение. В формулах (2.1.29) и (2.1.30) для преобразования строк, для столбца
свободных членов следует положить a
ij
=b
i
; a
sj
=b
s
и b
ij
=b
'
i
, b
sj
=
'
s
b , где b
'
i
(i=l,2,..., m) —
новые свободные члены. Таким образом, имеем формулы, по которым преобразуются
свободные члены:
.и
при,
'
'
sk
s
i
s
sk
ik
ii
a
b
b
sib
a
a
bb
=
≠−=
Но по правилу выбора ключевого элемента
,min
===
ik
i
i
sk
s
a
b
a
b
ββ
следовательно, имеем:
.и
при,
'
'
β
β
=
≠−=
s
ikii
b
siabb
Число
β
>0, так как все числа
β
i
положительны. Если элемент a
ik
в ключевом
столбце меньше нуля или равен ему, то соответствующее число ,0
'
>≥
ii
bb т. е.
положительно. Если a
ik
положительно, то число 0
'
>
−=
β
ik
i
iki
a
b
ab
также положительно, так как
ik
i
a
b
<
β
поскольку
β
минимальное из отношений
ik
i
a
b
при
положительных a
ik.
Таким образом, в новом невырожденном базисном решении все базисные
неизвестные будут иметь положительные значения
'
i
b (i=l, 2, ..., т), т. е. мы придем к
опорному решению.
Пример
. Найти какие-либо два оперных решения системы:
=++
=++−
=−+
.42
,62
,232
53
432
321
xx
xxx
xxx
Здесь мы имеем очевидное опорное решение: x
1
=2, x
2
=0, x
3
= 0, x
4
= 6, x
5
=4
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
