Двойственная задача ЛП
Общие правила составления двойственной задачи (более подробно):| Прямая | Двойственная |
| Целевая функция (max) | Правая часть ограничений |
| Правая часть ограничений | Целевая функция (min) |
| A - матрица ограничений | AT – матрица ограничений |
| i-ое ограничение: ≤ 0, (≥ 0) | Переменная yi ≥ 0, (≤ 0) |
| i-ое ограничение: = 0 | Переменная yi≠ 0 |
| Переменная xj ≥ 0 (≤ 0) | j-ое ограничение: ≤ 0 (≥ 0) |
| Переменная xj ≠ 0 | j-ое ограничение: = 0 |
Пример. Решим прямую задачу симплексным методом, используя калькулятор.
Определим максимальное значение целевой функции F(X) = 3x1 +5x2 +4x3 при следующих условиях-ограничений.
0.1x1 + 0.2x2 + 0.4x3≤1100
0.05x1 + 0.02x2 + 0.02x3≤120
3x1 + x2 + 2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6= 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6= 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6= 8000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4 , x5 , x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,1100,120,8000)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Индексная строка | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x2
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=0.2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются поправилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 |
| 1100 / 0.2 = 5500 | 0.1 / 0.2 = 0.5 | 0.2 / 0.2 = 1 | 0.4 / 0.2 = 2 | 1 / 0.2 = 5 | 0 / 0.2 = 0 | 0 / 0.2 = 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Индексная строка | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x1
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=0.04
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.04), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 |
|
|
|
|
|
|
|
| 10 / 0.04 = 250 | 0.04 / 0.04 = 1 | 0 / 0.04 = 0 | -0.02 / 0.04 = -0.5 | -0.1 / 0.04 = -2.5 | 1 / 0.04 = 25 | 0 / 0.04 = 0 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
Конец итераций: найден оптимальный план
Окончательный вариант симплекс-таблицы:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Индексная строка | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Оптимальный план можно записать так:
x2 = 5375
x1 = 250
x6 = 1875
F(X) = 3*250 + 5*5375 = 27625
Составим двойственную задачу к прямой задаче.
0.1y1+0.05y2+3y3≤3
0.2y1+0.02y2+y3≤5
0.4y1+0.02y2+2y3≤4
1100y4+120y4+8000y4 => min
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных x4 , x5 , x6 .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 23.75
y2 = 12.5
y3 = 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-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 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-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75и станет равной:
F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:
-3.8 ≤ с1 ≤ 1
Таким образом, 1-параметр может быть уменьшен на 3.8 или увеличен на 1
Интервал изменения равен:
[3-3.8; 3+1] = [-0.8;4]
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.
2-ый параметр целевой функции может изменяться в пределах:
-0.5 ≤ с2 ≤ 9.5
Таким образом, 2-параметр может быть уменьшен на 0.5 или увеличен на 9.5
Интервал изменения равен:
[5-0.5; 5+9.5] = [4.5;14.5]
Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.
Проведем анализ устойчивости двойственных оценок.
1-ый запас может изменяться в пределах:
-860 ≤ b1 ≤ 100
Таким образом, 1-ый запас может быть уменьшен на 860 или увеличен на 100
Интервал изменения равен:
[1100-860; 1100+100] = [240;1200]
2-ый запас может изменяться в пределах:
-10 ≤ b2 ≤ 30
Таким образом, 2-ый запас может быть уменьшен на 10 или увеличен на 30
Интервал изменения равен:
[120-10; 120+30] = [110;150]
Составим субоптимальные варианты плана с учетом изменений исходных данных модели (таблицы).
Пусть 2-ый ресурс увеличили на 50
| Базисные переменные | Значение базисных переменных | Коэффициент структурных сдвигов kc | Произведение kc на (50) | Расчет варианта плана |
| x2 | 5375 | 6.25 | 312.5 | 5687.5 |
| x1 | 250 | -2.5 | -125 | 125 |
| x6 | 1875 | 1.25 | 62.5 | 1937.5 |
| F(X) | 27625 | 23.75 | 1187.5 | 28812.5 |
Пусть 1-ый ресурс уменьшили на -5
| Базисные переменные | Значение базисных переменных | Коэффициент структурных сдвигов kc | Произведение kc на (-5) | Расчет варианта плана |
| x2 | 5375 | -12.5 | 62.5 | 5437.5 |
| x1 | 250 | 25 | -125 | 125 |
| x6 | 1875 | -62.5 | 312.5 | 2187.5 |
| F(X) | 27625 | 12.5 | -62.5 | 27562.5 |