Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

Основные идеи двойственного симплекс-метода. Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 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 ~ {а1, а2} и т. д.).

F В дальнейшем систему β={aj1, aj2,...,ajm} из т линейно-независимых столбцов матрицы условий прямой задачи А будем называть сопряженным базисом, или двойственно допустимым базисом, если всякий вектор и Rm, удовлетворяющий условиям, удовлетворяет также условиям иаj≥cj(j 1:n), т. е. является допустимым планом двойственной задачи (1.49).

План двойственной задачи и, соответствующий сопряженному базису β={aj1, aj2,...,ajm}, называют опорным планом. Его «опорность» заключается в том, что в системе ограничений jcj (j 1:n), задающих область определения двойственной задачи D*, т неравенств с номерами j N(β) обращаются в равенства.

Следует обратить внимание на то, что не всем сопряженным базисам соответствуют допустимые базисные планы прямой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам {а1, а2}, {а3 , а4 } или {а4, а5}. В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псевдопланом. В то же время базис {а2, а3} является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец b, с конусом К), а с другой — минимум двойственной (низшую точку пересечения этой прямой с лежащей над К опорной гиперплоскостью):

Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.

Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи*. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким.

* В данном пункте используется та же система обозначений, что и в п. 1.4.1.

F Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том,

что х одновременно должен являться допустимым планом прямой задачи, т. е. все его

компоненты должны быть неотрицательны (хj ≥ 0).

Обратно, если хотя бы одна из компонент псевдоплана является отрицательной, то процесс улучшения значения целевой функции может быть продолжен. Геометрическая иллюстрация данной ситуации приведена на рис. 1.13. Здесь на плоскости (для m = 2) изображена система столбцов ограничений КЗЛП, из которых {а1, а2} образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную координату по направлению, задаваемому вектором а1. В то же время очевидны и те базисы (например, {а2, а3}), в которых b будет иметь все положительные координаты. Однако это не всегда так. Пример на рис. 1.14 иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b имеет отрицательную компоненту в текущем базисе {а1, а2} по направлению а2, а для всех остальных небазисных столбцов (а3, а4) данная координата является положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полуплоскостях, образуемых прямой, проходящей через вектор а1,

и при любых базисах, отличных от текущего, соответствующая координата вектора b все равно останется отрицательной.

F Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у

решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах аj,

представленных в текущем базисе β (ar,j(β) ≥ 0, j 1:n) если br(β) < 0 l.*

* Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения прямой задачи.

С другой стороны, если br(β)<0 и в строке аr(β) существуют отрицательные координаты, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r-м месте, и вводя в него некоторый вектор al, имеющий отрицательную r-ую координату. При наличии в векторе b(β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно определяется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.

Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы. Для этого требуется, чтобы оценки всех небазисных векторов а0,j(β) ( j N(β)), вычисляемые по формулам

а0,j(β) = -cj + c(β)аj(β)

(см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l должен быть определен таким образом. Чтобы

После выбора выводимого и вводимого векторов производится обычный пересчет симплекс-таблицы по формулам, аналогичным формулам (1.28)-(1.31), и процесс итеративно повторяется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множества допустимых планов.