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

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых bi могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

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

Инструкция для решения задач двойственным симплекс-методом. Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения двойственным симплекс-методом).
Количество переменных
Количество строк (количество ограничений)
При этом ограничения типа xi ≥ 0 не учитывайте.

Вместе с этим калькулятором также используют следующие:

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных xi имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

  1. Составление псевдоплана. Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
  2. Проверка плана на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом.
  3. Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
  4. Расчет нового опорного плана. Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса. Далее переход к этапу 2.
Более подробный алгоритм двойственного симплекс-метода.

Пример. Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание: Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x1 + 2x2 + x3 при следующих условиях-ограничений.
- x1 - x2≤-10
2x1 + x2 - x3≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x4. Во втором неравенстве смысла (≤) вводим базисную переменную x5.
-1x1-1x2 + 0x3 + 1x4 + 0x5 = -10
2x1 + 1x2-1x3 + 0x4 + 1x5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
-1-1010
21-101

Решим систему уравнений относительно базисных переменных:
x4, x5,
Полагая, что свободные переменные равны нулю, получим первый опорный план:
X1 = (0,0,0,-10,8)
Базис B x1 x2 x3 x4 x5
x4 -10 -1 -1 0 1 0
x5 8 2 1 -1 0 1
F(X0) 0 -4 -2 -1 0 0

Итерация №1
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет первая строка, а переменную x4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис B x1 x2 x3 x4 x5
x4 -10 -1-1 0 1 0
x5 8 2 1 -1 0 1
F(X0) 0 -4-2 -1 0 0
θ 0 -4 : (-1) = 4 -2 : (-1) = 2 - - -

4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5
x2 10 1 1 0 -1 0
x5 -2 1 0 -1 1 1
F(X0) 20 -2 0 -1 -2 0

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5
-10 : -1 -1 : -1 -1 : -1 0 : -1 1 : -1 0 : -1
8-(-10 • 1):-1 2-(-1 • 1):-1 1-(-1 • 1):-1 -1-(0 • 1):-1 0-(1 • 1):-1 1-(0 • 1):-1
0-(-10 • -2):-1 -4-(-1 • -2):-1 -2-(-1 • -2):-1 -1-(0 • -2):-1 0-(1 • -2):-1 0-(0 • -2):-1

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис B x1 x2 x3 x4 x5
x2 10 1 1 0 -1 0
x5 -2 1 0-1 1 1
F(X0) 20 -2 0-1 -2 0
θ 0 - - -1 : (-1) = 1 - -

4. Пересчет симплекс-таблицы. Выполняем преобразования.

Базис B x1 x2 x3 x4 x5
x2 10 1 1 0 -1 0
x3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1

Или более подробно:

B x 1 x 2 x 3 x 4 x 5
10-(-2 • 0):-1 1-(1 • 0):-1 1-(0 • 0):-1 0-(-1 • 0):-1 -1-(1 • 0):-1 0-(1 • 0):-1
-2 : -1 1 : -1 0 : -1 -1 : -1 1 : -1 1 : -1
20-(-2 • -1):-1 -2-(1 • -1):-1 0-(0 • -1):-1 -1-(-1 • -1):-1 -2-(1 • -1):-1 0-(1 • -1):-1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Базис B x1 x2 x3 x4 x5
x2 10 1 1 0 -1 0
x3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1

Оптимальный план можно записать так:
x1 = 0
x2 = 10
x3 = 2
F(X) = 2•10 + 1•2 = 22
загрузка...