Двойственный симплекс метод в математике

Двойственный  симплексный метод

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

 Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются С_j а оценками плана двойственной задачи – b_i. Решим "двойственную задачу по симплексной таблице, в которой записана исходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит название двойственного симплексного метода,

 Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A₀, Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA₀ при YA £ С. Допустим, что выбран такой базис D = (A₁, А₂, ..., А_i, ..., А_m), при котором хотя бы одна из компонент вектора Х = D^-1 A₀ = (x₁, x₂, ..., x_i, ..., x_m) отрицательная (например, x_i < 0), но для всех векторов A_j выполняется соотношение Z_j – C_j £ 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = С_баз D^-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.

 Таким образом, вектор А_i, соответствующий компоненте x_i < 0, следует исключить из базиса исходной задачи, а вектор, соответствующий отрицательной оценке,— включить в базис двойственной задачи.

  Для выбора вектора, включаемого в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся x_ij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые x_ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q_0j= min (x_i/x_ij) ³ 0 и определяем вектор, соответствующий max q_0j(Z_j — C_j) при решении исходной задачи на минимум и min q_0j(Z_j — C_j) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой.

 Если q_0j= min (x_i/x_ij) = 0, т. е. x_i = 0, то x_ij берется за разрешающий элемент только в том случае, если x_ij > 0. Такой выбор разрешающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X. Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

 В процессе вычислений по алгоритму двойственного  симплексного метода условие Z_j – C_j £ 0 можно не учитывать до исключения всех х_i < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все х_i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q_0j определить не по минимуму, а по максимуму отношений, т. е. q_0j= max (x_i/x_ij) > 0.

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

Алгоритм  двойственного симплекс-метода

   1.      Выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов.

   2.      Выбирают разрешающий столбец по наибольшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки.

   3.      Пересчитывают симплексную таблицу по правилам обычного симплекс-метода.

   4.      Решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.

Замечания: 1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.

             2. Если ограничения  задачи заданы неравенствами  типа «³», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.

Пример.                        L = х₁+4х₂+х₃ (min)

Составляем исходную симплексную таблицу

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

Аналогично рассуждая, получим еще одну таблицу

Отсутствие в  столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение Lmin = , `Хmin( ;0; ;0;0; ;11).

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

Пример.                        L = 5х₁-х₂-х₃ (max)

Составляем исходную симплексную таблицу