 |
 |
 |
 |
|
 |
 |
38
опорным планом. Его «опорность» заключается в том, что в системе ограничений uа
j
?
c
j
(j
1:n),
задающих область определения двойственной задачи D*, т неравенств с номерами j
N(?) обращаются
в равенства.
Следует обратить внимание на то, что не всем сопряженным базисам соответствуют допустимые
базисные планы прямой задачи. В частности, вектор b не может быть разложен с неотрицательными
коэффициентами по базисам {а¹, а²}, {а³ , а
4
} или {а
4
, а
5
}. В связи с этим систему коэффициентов
разложения вектора b по сопряженному базису называют псевдопланом. В то же время базис {а², а³}
является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны,
определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец
b, с конусом К), а с другой — минимум двойственной (низшую точку пересечения этой прямой с
лежащей над К опорной гиперплоскостью):
Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.
Описанные выше свойства пары двойственных задач линейного программирования являются
идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс
целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих
псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в
котором последовательно рассматриваются допустимые базисные планы прямой задачи*. Нетрудно
догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом,
может оказаться более коротким.
* В данном пункте используется та же система обозначений, что и в п. 1.4.1.
Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том,
что х одновременно должен являться допустимым планом прямой задачи, т. е. все его
компоненты должны быть неотрицательны (х
j
? 0).
Обратно, если хотя бы одна из компонент псевдоплана является отрицательной, то процесс
улучшения значения целевой функции может быть продолжен. Геометрическая иллюстрация данной
ситуации приведена на рис. 1.13. Здесь на плоскости (для m = 2) изображена система столбцов
ограничений КЗЛП, из которых {а¹, а²} образуют текущий базис. Как видно из рисунка, вектор
ограничений имеет отрицательную координату по направлению, задаваемому вектором а¹. В то же
время очевидны и те базисы (например, {а², а³}), в которых b будет иметь все положительные
координаты. Однако это не всегда так. Пример на рис. 1.14 иллюстрирует случай отсутствия
допустимых планов у прямой задачи: вектор b имеет отрицательную компоненту в текущем базисе {а¹,
а²} по направлению а², а для всех остальных небазисных столбцов (а³, а
4
) данная координата является
положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных
полуплоскостях, образуемых прямой, проходящей через вектор а¹,
и при любых базисах, отличных от текущего, соответствующая координата вектора b все равно
останется отрицательной.
Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у
решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах а
j
,