 |
 |
 |
 |
|
 |
 |
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
}, называют