Двойственная задача ЛП

Общие правила составления двойственной задачи (более подробно):
Прямая Двойственная
Целевая функция (min) Правая часть ограничений
Правая часть ограничений Целевая функция (max)
A – матрица ограничений AT – матрица ограничений
i–ое ограничение: ≥ 0, (≤ 0) Переменная yi ≥ 0, (≤ 0)
i–ое ограничение: = 0 Переменная yi ≠ 0
Переменная x ≥ 0 j–ое ограничение: ≤ 0
Переменная x ≠ 0 j–ое ограничение: = 0

Пример. Решим прямую задачу симплексным методом, используя калькулятор.
Определим максимальное значение целевой функции F(X) = 3 x1  +5 x2  +4 x3   при следующих условиях-ограничений.
0.1x1 + 0.2 x2  + 0.4 x3<=1100
0.05x1 + 0.02x2 + 0.02 x3<=120
3x1 + x2 + 2 x3<=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, так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 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, так как наибольший коэффициент по модулю.
Вычислим значения D i по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 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

Скачать в формате Word

загрузка...