Navigation bar
  Print document Start Previous page
 39 of 115 
Next page End  

39
      представленных в текущем базисе ? (a
r,j
(?)
? 0
, j
1:n) если br(?) < 0 l.*
* Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения
прямой задачи.
С другой стороны, если br(?)<0
и в строке
аr(?)
существуют отрицательные координаты, то
псевдоплан можно улучшить выводя из базиса столбец, находящийся на r-м месте, и вводя в него
некоторый вектор a
l
, имеющий отрицательную r-ую координату. При наличии в векторе b(?)
нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно определяется
строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.
Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы
очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы.
Для этого требуется, чтобы оценки всех небазисных векторов
а
0,j
(?) ( j
N(?)), вычисляемые по
формулам
а
0,j
(?) = -c
j +
c(?)а
j
(?)
(см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l
должен быть определен таким образом. Чтобы
После выбора выводимого и вводимого векторов производится обычный пересчет симплекс-таблицы
по формулам, аналогичным формулам (1.28)-(1.31), и процесс итеративно повторяется. В результате
через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты
множества допустимых планов.
1.7.2. Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в
предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения
КЗЛП.
0-этап. Нахождение исходного сопряженного (двойственно допустимого базиса). Результатом 0-
этапа являются сопряженный базис
?
(1)
и соответствующие ему псевдоплан x(?
(1)
), матрица A(?
(1)
) и
вектор b(?
(1)
), которые будут использованы на первой итерации. Полагаем номер текущей итерации q
равным 1 и переходим к I-этапу.
I-этап. Стандартная итерация алгоритма выполняется для очередного сопряженного базиса
?
(q)
.
1°. Проверка оптимальности текущего псевдоплана: осуществляется просмотр значений b
i
(?
(q)
),
i
1:m. Возможны два варианта:
1?. Для всех i
1:m, b
i
(?
(q)
)
? 0
. Тогда текущий псевдоплан x(?
(q)
) одновременно является допустимым
планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный процесс закончен. Элементы
оптимального плана х* определяются по формуле
а достигаемое на нем значение целевой функции равно
1". Существует по меньшей мере один номер строки r
1:m, для которого br(?
(q)
)<0 . Следовательно,
псевдоплан x(?
(q)
)  — неоптимален. Выбирается строка с номером r, такая, что
Она становится ведущей и определяет номер столбца Nr(?
(q)
), который должен быть выведен из
Сайт создан в системе uCoz