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

37
ляют предмет специального раздела исследования операций, получившего название параметрического
программирования. Заинтересованный читатель может получить дополнительную информацию по
данному предмету в [1, 6].
1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
1.7.1. Основные идеи двойственного симплекс-метода.
Непосредственное приложение теории
двойственности к вычислительным алгоритмам линейного программирования позволило разработать
еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода по-
следовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г.
В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз
воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На
рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий а
j
для случая m = 2, n = 6, а на рис. 1.12
— (для большей наглядности) — поперечное сечение данного
конуса некоторой плоскостью L, проходящей параллельно оси аппликат.
С каждым планом и задачи, двойственной по отношению к (1.48), можно взаимно однозначно связать
гиперплоскость, проходящую через начало координат и перпендикулярную вектору (-1,и). Допустимые
планы двойственной задачи (1.49) должны удовлетворять условиям иА ? с, которые можно переписать в
виде (1,
и)А
? 0 .
Последнее означает, что всякий рас
ширенный вектор условий а
j
лежит «ниже»
плоскости, определяемой вектором (-1, и). Таким образом, любому допустимому плану двойственной
задачи в рассматриваемом примере соответствует некоторая плоскость, расположенная выше всех рас-
ширенных векторов, а стало быть, и конуса К. На рис. 1.12, где изображено поперечное сечение, конусу
К отвечает многогранник, а «гиперплоскостям двойственных планов» пунктирные линии,
являющиеся их следами.
По аналогии с интерпретацией решения прямой задачи процесс решения двойственной задачи может
быть представлен как поиск такой гиперплоскости, которая лежит выше конуса К и пересекает
прямую, проведенную через конец вектора b параллельно оси аппликат, в самой нижней точке.
Из геометрической иллюстрации видно, что плоскости, не соприкасающиеся с конусом К, заведомо
не представляют интереса, так как для любой из них легко указать плоскость, у которой искомая точка
пересечения лежит ниже. Таким образом, процесс поиска экстремума сводится к последовательному пе-
ребору плоскостей, касающихся «верхних» граней конуса, или, как еще говорят, опорных по
отношению к конусу. Для случая, изображенного на рис. 1.12, таковыми являются гиперплоскости
?
1,2
,
?
2,3
, ?
3,4
и
?
4,5
. Как можно заметить, каждая из рассматриваемых гиперплоскостей натянута на некоторый
базисный набор расширенных векторов а
j
, что, собственно, и использовано для их обозначения (
?
1,2
{а¹, а²} и т. д.).
В дальнейшем систему
?={a
j1
, a
j2
,...,a
jm
} из т линейно-независимых столбцов матрицы условий
прямой задачи А будем называть сопряженным базисом, или двойственно допустимым базисом,
если всякий вектор и
R
m
, удовлетворяющий условиям, удовлетворяет также условиям
иа
j
?c
j
(j
1:n), т. е. является допустимым планом двойственной задачи (1.49).
План двойственной задачи и, соответствующий сопряженному базису ?={a
j1
, a
j2
,...,a
jm
}, называют
Сайт создан в системе uCoz