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

40
базиса. Переходим к пункту 2° алгоритма.                               
2°. Определение столбца, вводимого в базис. Рассматривается ведущая строка аr(?
(q)
). Возможны два
варианта:        
2'. Для всех j
1:
n
а
r,j
(?
(q)
)
? 0
. Делается вывод об отсутствии допустимых планов у решаемой
задачи (D = O) и завершается вычислительный процесс*.
* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную
строку а
i
(?
(q)
), соответствующую b
i
(?
(q)
) < 0.
2". В строке аr(?
(q)
) существует по крайней мере один элемент а
r,j
(?
(q)
)<0. Согласно правилу (1.62)
определяются l — номер столбца, вводимого в очередной базис. Переходим к пункту 3° алгоритма.
3°. Пересчет элементов матрицы А и столбца b относительно нового базиса. В соответствии с
формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и вектора ограничений b
относительно нового базиса
?
(q+1)
, который получается в результате вывода из базиса
?
(q)
столбца а® и
ввода в него столбца а
l
. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту
алгоритма.
По аналогии со стандартным симплекс-методом вычислительную процедуру двойственного
симплекс-метода удобно оформлять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с
формальной стороны их структура остается неизменной. Иногда считается целесообразным добавить к
двойственной симплекс-таблице строку, содержащую строку со значениями
?
j
, которые вычисляются на
этапе определения столбца, вводимого в базис.
1.7.3. Особенности применения двойственного симплекс-метода. Алгоритм двойственного
симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исходного сопряженного
базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей,
сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев
исходный псевдоплан может быть определен достаточно легко.
Рассмотрим задачу минимизации:
при ограничениях
где
Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные х
n+1
, х
n+2
,
... , х
n+m
:
Задача, двойственная к (1.70)—(1.72), будет иметь вид:
Сайт создан в системе uCoz