Название: Математические методы исследования операций в экономике

Жанр: Экономика

Рейтинг:

Просмотров: 1030

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 ~  {а1, а2} и т. д.).

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

План двойственной задачи и, соответствующий сопряженному базису β={aj1, aj2,...,ajm}, называют опорным планом. Его «опорность» заключается в том, что в системе ограничений uаj ≥ cj  (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), и процесс итеративно повторяется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множества допустимых планов.

1.7.2. Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.

0-этап. Нахождение исходного сопряженного (двойственно допустимого базиса). Результатом 0-этапа являются сопряженный базис β(1) и соответствующие ему псевдоплан x(β(1)), матрица A(β(1)) и вектор b(β(1)), которые будут использованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполняется для очередного сопряженного базиса β(q).

1°. Проверка оптимальности текущего псевдоплана: осуществляется просмотр значений bi(β(q)), iÎ1:m. Возможны два варианта:

1΄. Для всех iÎ1:m, bi(β(q)) ≥ 0. Тогда текущий псевдоплан x(β(q)) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный процесс закончен. Элементы оптимального плана х* определяются по формуле

а достигаемое на нем значение целевой функции равно

1". Существует по меньшей мере один номер строки rÎ1:m, для которого br(β(q))<0 . Следовательно, псевдоплан x(β(q))  — неоптимален. Выбирается строка с номером r, такая, что

Она становится ведущей и определяет номер столбца Nr(β(q)), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.                              

2°. Определение столбца, вводимого в базис. Рассматривается ведущая строка аr(β(q)). Возможны два варианта:       

2'. Для всех jÎ1: n аr,j(β(q)) ≥ 0. Делается вывод об отсутствии допустимых планов у решаемой задачи (D = Ø) и завершается вычислительный процесс*.

* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку аi(β(q)), соответствующую bi(β(q)) < 0.

2". В строке аr(β(q)) существует по крайней мере один элемент аr,j(β(q))<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пункту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относительно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и вектора ограничений b относительно нового базиса β(q+1), который получается в результате вывода из базиса β(q) столбца аr и ввода в него столбца аl. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту алгоритма.

По аналогии со стандартным симплекс-методом вычислительную процедуру двойственного симплекс-метода удобно оформлять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иногда считается целесообразным добавить к двойственной симплекс-таблице строку, содержащую строку со значениями λj, которые вычисляются на этапе определения столбца, вводимого в базис.

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

Рассмотрим задачу минимизации:

при ограничениях

где

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные хn+1, хn+2, ... , хn+m:

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи

и исходный сопряженный базис, образуемый векторами аn+1, аn+2, …., аn+m. При этом начальный псевдоплан равен

Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.

Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких изменений являются:

 изменение компонент вектора ограничений b, что, допустим, может быть интерпретировано как  корректировка объемов доступных ресурсов в процессе управления экономическим объектом;

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

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

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

1.7.4. Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном, примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых

Содержание исходной симплекс-таблицы T(1) (за исключением столбца b(β(1))) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b(β(1)) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации в п. 1.5.2:

В результате имеем:

Как видно из таблицы Т(1), в столбце b(β(1)) содержатся отрицательные элементы b1(β(1)) = - 1/3<0), то есть базис β(1) ={5, 1, 3} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β(1)) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r = 1 и N1(β(1))=5. Далее рассматриваем строку a1(β(1)) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ2 =42:(-(-1/6))=252, λ4 =38:(-(-1/6))=228. λ2> λ4, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T(2).

Поскольку b(β(2)) >0, то достигнутый базис N(β(2)) = {4,1,3} является оптимальным. Из Т(2) можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции f(x*)= 444.