ВУЗ:
Составители:
89
. ; ... ; ;
;0...
21
1
21
в
у
в
у
в
у
ххх
m
m
n
===
====
(5.20)
Если все свободные члены (в
1
, в
2
, ..., в
m
) в уравнениях (5.19) неотрица-
тельны
, то это значит, что опорное решение уже получено. Рассмотрим
случай, когда среди свободных членов в
1
, в
2
, ..., в
m
ecть отрицательные.
Это значит, что решение (5.20) не является опорным – оно вообще не
допустимо, и опорное решение еще предстоит найти. Для этого мы бу-
дем шаг за шагом обменивать местами базисные и свободные перемен-
ные в уравнениях (5.19) до тех пор, пока не придем к опорному реше-
нию или не убедимся, что
его не существует, т. е. когда система уравне-
ний (5.19) несовместима с неравенствами
х
1
≥ 0, х
2
≥ 0, …, х
n
≥ 0, у
1
≥ 0, у
m
≥ 0, (5.21)
т. е. у нее нет неотрицательных решений.
Очевидно, нужно так обменивать местами базисные и свободные
переменные, чтобы эта процедура
приближала нас к границе ОДР, а
не удаляла от нее, т. е. чтобы число отрицательных свободных членов с
каждым шагом убывало или если число отрицательных свободных чле-
нов остается прежним, то, по крайней мере, убывали бы их абсолютные
величины
.
5.5.4. Способ выбора разрешающего элемента для приближения
к опорному решению
Пусть имеется одно из уравнений (5.19) с отрицательным свобод-
ным членом.
1. Ищем в этой строке отрицательный элемент α
ij
. Если такого
элемента нет (все элементы α
ij
≥ 0), это признак того, что система урав-
нений (5.19) несовместима с неравенствами (5.21).
2. Предположим, что отрицательный элемент есть. Тогда выбира-
ем столбец, в котором он находится в
качестве разрешающего.
3. Теперь надо выбрать в этом столбце сам разрешающий элемент.
Рассмотрим все элементы данного столбца, имеющие одинаковый знак
со свободным членом. Из них выбираем в качестве разрешающего тот,
для которого отношение к нему свободного члена минимально.
П р и м е р. Найти опорное решение задачи линейного програм-
мирования с ограничениями-равенствами
Страницы
- « первая
- ‹ предыдущая
- …
- 87
- 88
- 89
- 90
- 91
- …
- следующая ›
- последняя »
