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

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

• решение двойственной задачи линейного программирования через решений прямой задачи (симплексным методом, по теореме двойственности);
• оптимальный план двойственной задачи; оценки ресурсов (двойственные оценки);
• определение дефицитных и недефицитных (избыточных) ресурсов;
• изменение целевой функции при изменении параметров; обоснование эффективности оптимального плана;
• анализ устойчивости двойственных оценок (предельное изменение b_i, c_i); анализ субоптимальных вариантов плана.
• решение задачи о расшивке узких мест производства.

• Шаг №1
• Шаг №2
• Инструкция
• Оформление Word

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

Количество переменных 2345678910 Количество строк (количество ограничений) 12345678910

Далее

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

Видеоинструкция №1
Видеоинструкция №2

Скачать пример отчета

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

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

Пример. Определим максимальное значение целевой функции F(X) = 3x₁ +5x₂ +4x₃ при следующих условиях-ограничений.
0.1x₁ + 0.2x₂ + 0.4x₃≤1100
0.05x₁ + 0.02x₂ + 0.02x₃≤120
3x₁ + x₂ + 2x₃≤8000

Решим прямую задачу симплексным методом.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
0.1x₁ + 0.2x₂ + 0.4x₃ + 1x₄ + 0x₅ + 0x₆= 1100
0.05x₁ + 0.02x₂ + 0.02x₃ + 0x₄ + 1x₅ + 0x₆= 120
3x₁ + 1x₂ + 2x₃ + 0x₄ + 0x₅ + 1x₆= 8000
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₄ , x₅ , x₆ 
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,1100,120,8000)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.

Посмотреть таблицу

Посмотреть таблицу
Конец итераций: найден оптимальный план. Окончательный вариант симплекс-таблицы:

Составим двойственную задачу к прямой задаче.
0.1y₁+0.05y₂+3y₃≤3
0.2y₁+0.02y₂+y₃≤5
0.4y₁+0.02y₂+2y₃≤4
1100y₄+120y₄+8000y₄ => min
y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А^-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных  x₄ , x₅ , x₆ .
Тогда Y = C*A^-1 =
Оптимальный план двойственной задачи равен: y₁ = 23.75, y₂ = 12.5, y₃ = 0
Z(Y) = 1100*23.75+120*12.5+8000*0 = 27625
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
0.1*250 + 0.2*5375 + 0.4*0  = 1100 = 1100
0.05*250 + 0.02*5375 + 0.02*0  = 120 = 120
3*250 + 1*5375 + 2*0  = 6125 < 8000

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₃ = 0.
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
При постановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
0.1*23.75 + 0.05*12.5 + 3*0  = 3 = 3
0.2*23.75 + 0.02*12.5 + 1*0  = 5 = 5
0.4*23.75 + 0.02*12.5 + 2*0  = 9.75 > 4
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75 и станет равной: F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:

-3.8 ≤ с₁ ≤ 1
Таким образом, 1-параметр может быть уменьшен на 3.8 или увеличен на 1
Интервал изменения равен: [3-3.8; 3+1] = [-0.8;4]
Если значение c₁ будет лежать в данном интервале, то оптимальный план не изменится.

2-ый параметр целевой функции может изменяться в пределах:

-0.5 ≤ с₂ ≤ 9.5
Таким образом, 2-параметр может быть уменьшен на 0.5 или увеличен на 9.5
Интервал изменения равен: [5-0.5; 5+9.5] = [4.5;14.5]
Если значение c₂ будет лежать в данном интервале, то оптимальный план не изменится.

Проведем анализ устойчивости двойственных оценок.
1-ый запас может изменяться в пределах:

-860 ≤ b₁ ≤ 100
Таким образом, 1-ый запас может быть уменьшен на 860 или увеличен на 100
Интервал изменения равен: [1100-860; 1100+100] = [240;1200]
2-ый запас может изменяться в пределах:

-10 ≤ b₂ ≤ 30
Таким образом, 2-ый запас может быть уменьшен на 10 или увеличен на 30
Интервал изменения равен: [120-10; 120+30] = [110;150]
Составим субоптимальные варианты плана с учетом изменений исходных данных модели (таблицы).
Пусть 2-ый ресурс увеличили на 50

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

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

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

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

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

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

Решение. Обозначим через:
x₁₁ – АК 1-го типа на первом аэродроме,
x₁₂ – АК 1-го типа на втором аэродроме,
x₂₁ – АК 2-го типа на первом аэродроме,
x₂₂ – АК 2-го типа на втором аэродроме,
x₃₁ – АК 3-го типа на первом аэродроме,
x₃₂ – АК 3-го типа на втором аэродроме,

Ограничения
4x₁₁+ 6x₁₂ = 50
10x₂₁+ 8x₂₂ = 30
10x₃₁+ 20x₃₂ = 45
x₁₁, x₁₂, x₂₁, x₂₂, x₃₁,x₃₂ ≥ 0
x₁₁, x₁₂, x₂₁, x₂₂, x₃₁,x₃₂ –целые числа

Целевая функция
4x₁₁+ 6x₁₂ + 10x₂₁+ 8x₂₂ +10x₃₁+ 20x₃₂ → min

После найденного решения, ответом на первый вопрос будут значения переменных x₁₁, x₁₂, x₂₁, x₂₂, x₃₁,x₃₂. Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.