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

Двойственный симплекс метод − теория, примеры и решения

1. Обоснование алгоритма двойственного симплекс метода

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

Рассмотрим следующую задачу линейного программирования:

Предполагая, что первые m векторы столбцы уравнений (1b) единичные линейно независимые векторы столбцы, запишем задачу ЛП:

Запишем задачу ЛП (2a)-(2c) в матричной форме:

где , , , , ,

Пусть среди координат вектора B имеются отрицательные числа. Очевидно, что является решением системы линейных уравнений (2b), но не является планом задачи ЛП (2a)−(2b), так как среди его компонент имеются отрицательные числа.

Для целевой функции (2a), учитывая (2b), сделаем следующие преобразования

где

Δ_F − вектор-строка длины n-m.

Сделаем следующее обозначение:

или

где 0_m− нулевой вектор-строка длины m, Δ − вектор-строка длины n.

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

Определение 1. Решение системы линейных уравнений (2b) называется псевдопланом задачи (2a)-(2c), если Δ ≥ 0.

Заметим, что при Δ ≥ 0, C_B является допустимым планом двойственной к (3) задачи ЛП:

Действительно. C_B удовлетворяет системе линейных неравенств (9) и первые m неравенства в (9) удовлетворяются как равенства (поскольку первые m координат вектор-строки Δ нулевые). Другими словами C_B является вершиной выпуклого многогранного множества (9). Целевая функция в этой точке равна:

Из вершины \(\small C_B \) нужно передвигатся по одной из m ребер так, чтобы новая точка осталось в допустимой области (9) и целевая функция (8) уменьшалась. Параметрическое равнение прямой, по которой нужно передвигаться имеет следующий вид:

где t − параметр, \( \small e_p \)− направляющий вектор прямой, \( \small e_p \)− один из единичных векторов-строк единичной матрицы:

где E − матрица порядка m×m

Подставим (10) в (8):

Посмотрев правую часть равенства (12) видим, что для того, чтобы целевая функция \( \small YB \) уменьшилась нужно, чтобы \( \small B_p \lt 0,\;t \gt 0.\) То есть выбираем строку p, в котором свободный член отрицательное число.

Подставим (10) в (9):

где \( \small A_p \)− p-я строка матрицы A.

Решим (13) относительно t:

где \( \small a_{pj} \) −\( \small j \)-ый элемент вектора строки \( \small A_p \).

Из (14) и (15) находим нижнюю и верхнюю границы параметра :

Нас интересует верхняя граница параметра t так как нам нужно максимально уменьшить целевую функцию (8). При этом новый план остается в допустимой области задачи (8)- (9), т.е. удовлетворяется условие (7). Обозначим через q индекс j, при котором достигается минимум в (17). Строка с номером q входит в базис задачи (8)-(9) или, что то же самое столбец q входит в базис в задаче (2a)-(2c). Для столбца q делается шаг Жордана-Гаусса, учитывая, что ведущим элементом является \( \small a_{pq} \).

Подставляя найденный \( \small t_{верх} \) в (10) находим новый план двойственной задачи (8)-(9). Отметим, что если при всех , то параметр t не имеет ограничение сверху и может быть увеличен бесконечно. Тогда целевая функция задачи (8)-(9) будет неограничен снизу и задача не будет иметь решение. Соответственно, в этом случае, допустимая область исходной задачи пуста.

Мы доказали следующие две теоремы:

Теорема 1. Если в псевдоплане есть хотя бы одно отрицательное число \(\small b_i \lt 0 \) такое, что все \(\small a_{ij}\ge 0 \;\;(j=\overline{1,n})\), то задача (2a)-(2c) вообще не имеет решения.

Теорема 2. Если в псевдоплане имеются отрицательные числа \(\small b_i \lt 0 \) такие, что для любого из них существуют числа \(\small a_{ij}\lt 0 \;\;(j=\overline{1,n})\), то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (8)-(9) не увеличится.

Вышеизложенные соображения и теоремы дают основание для построения алгоритма двойственного симплекс метода.

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

Пусть псевдоплан задачи ЛП (2a)-(2c). На основе исходных данных составляют симплекс-таблицу:

Пусть в этой таблице некоторые элементы вектора-столбца B отрицательные числа. Если таких чисел нет, то в симплекс таблице, в столбце "Базис" записаны индексы оптимального плана, а в столбце B − соответственные координаты плана (отметим, что целевая (последняя) строка таблицы неотрицательна, т.е. должна выполняться условие (7)). Если в столбце B есть отрицательные числа, то переходим от одной симплекс таблицы к другой пока все отрицательные числа вектора B не станут неотрицательными. При этом преобразования с таблицей должны выпоняться так, чтобы все элементы последней строки таблицы оставались неотрицательными т.е. выполнялось условие (7).

После составления симплекс таблицы проверяют, имеются ли отрицательные числа в столбце B. Если таких нет, то найден оптимальный план, а если такие есть, выбирается самый большой по модулю отрицательный элемент (например элемент с индексом p). Тогда из базиса выходит переменная \(\small x_{p} \). Чтобы определить, какой вектор следует ввести в базис, вычисляем

Пусть минимальное значение принимается при j=q. Тогда в базис входит переменная \(\small x_{q} \). Далее производится шаг Жордана-Гаусса для столбца q, учитывая, что ведущим элементом является \(\small a_{pq} \). Итерационный процесс заканчивается тогда, когда в столбце B больше нет отрицательных чисел. В этом случае получен оптимальный план. Если на каком-то этапе итерационного процесса в столбце B стоит отрицательное число, а среди остальных элементов этой строки нет отрицательных чисел, то задача не имеет решения.

Таким образом алгоритм решения задачи ЛП двойственным симплекс методом содержит следующие шаги:

1. Находят псевдоплан задачи.

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

3. Находят наибольшую по абсолютной величине отрицательный элемент столбца B. Фиксируют индекс этой строки p. Находят наименьшую по абсолютной величине отношения элементов целевой (последней) строки к элементам разрешающей строки p. Пусть минимальное значение принимается при j=q.

4. Делают шаг Жордана-Гаусса для столбца q, учитывая, что разрешающим (ведущим) элементом является \( a_{pq} \). Находят новый псевдоплан и переходят к шагу 2.

Для просмотра примеров решения, введите данные на онлайн калькулятор выше и нажмите на кнопку "Вычислить". Калькулятор представит решение задачи ЛП двойственным симплекс методом подробно, по шагам. Для решения задачи линейного программирования обычным симплекс методом используйте калькулятор Симплекс метод онлайн.