Решение двойственной задачи линейного программирования

С помощью данного онлайн-калькулятора можно получить:

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

При этом ограничения типа xi ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных xi неопределена, то можно использовать этот калькулятор.

Основная идея теории двойственности: для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с прямой. При этом:

  • матрица ограничений двойственной задачи (ДЗ) есть транспонированная матрица прямой задачи;
  • вектор "цен" для прямой задачи есть вектор правых частей ограничений задачи ДЗ и наоборот.

Задание: Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.
F(X) = 3x1 + x2 → min
- 2x1 + x2≥4
2x1 + x2≤8
3x1 + 2x2≥6
Решение.
I этап. Приводим систему к каноническому виду.
II этап. Решаем simplex-методом.
Примечание: Если задача решается данным калькулятором, то предыдущие два этапа пропускаем, поскольку они автоматически включены в решение.
На втором этапе окончательный вариант симплекс-таблицы имеет вид:

Базис B x1 x2 x3 x4 x5 x6 x7
x5 2 -7 0 -2 0 1 2 -1
x4 4 4 0 1 1 0 -1 0
x2 4 -2 1 -1 0 0 1 0
F(X3) 4 -5 0 -1 0 0 1-M -M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Записываем оптимальный план:
x1 = 0
x2 = 4
F(X) = 1•4 = 4

Составим двойственную задачу к прямой задаче.
- 2y1 + 2y2 + 3y3≤3
y1 + y2 + 2y3≤1
4y1 + 8y2 + 6y3 → max
y1 ≥ 0
y2 ≤ 0
y3 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A5, A4, A2) =
001
011
-102

Определяем обратную матрицу D = А-1 через алгебраические дополнения:
D = A-1 =
20-1
-110
100

Обратите внимание, обратная матрица A-1 расположена в столбцах дополнительных переменных окончательного варианта симплекс-таблицы. Тогда Y = C*A-1 =
(0, 0, 1) x
20-1
-110
100
= (1;0;0)

Примечание: см. как умножать матрицы.
Оптимальный план двойственной задачи равен (двойственные оценки):
y1 = 1
y2 = 0
y3 = 0
Z(Y) = 4*1+8*0+6*0 = 4

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

Проверим критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального. В данном примере двойственная оценка (теневая или альтернативная) y1 больше всех, что означает ценность ресурса №1.

Далее решается вопрос об экономической интерпретации двойственных оценок.

Пример №1. Для выполнения задания необходимо, чтобы одновременно взлетели 50 АК I-го вида, 30 АК 2-го вида и 45 АК 3-го вида. АК расположены на аэродромах I и II. В таблице представлено среднее время взлета (в секундах) с соответствующего аэродрома одного АК данного типа.

Номер аэродрома Тип АК
1 2 3
I 4 10 10
II 6 8 20
Как следует разместить АК по аэродромам, чтобы время последовательного взлета всего наряда АК было минимальным? До какой степени можно изменить время взлета каждого АК, чтобы при этом оптимальное решение осталось прежним.

Решение. Обозначим через:
x11 – АК 1-го типа на первом аэродроме,
x12 – АК 1-го типа на втором аэродроме,
x21 – АК 2-го типа на первом аэродроме,
x22 – АК 2-го типа на втором аэродроме,
x31 – АК 3-го типа на первом аэродроме,
x32 – АК 3-го типа на втором аэродроме,

Ограничения
4x11+ 6x12 = 50
10x21+ 8x22 =  30
10x31+ 20x32 = 45
x11, x12, x21, x22, x31,x32 ≥ 0
x11, x12, x21, x22, x31,x32 –целые числа

Целевая функция
4x11+ 6x12 + 10x21+ 8x22 +10x31+ 20x32 → min

После найденного решения, ответом на первый вопрос будут значения переменных x11, x12, x21, x22, x31,x32. Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.

Открыть диалог Discus Помощь в решении контрольных