Двойственная задача. Пример решения

Методические пояснения: для проверки решения используйте сервис Двойственная задача ЛП

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 2x1+3x2+2x3 при следующих условиях-ограничений.
2x1+3x2-2x3≤2
-3x1-6x2+3x3≥5
4x1+3x2-x3=3

Решение.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 3x2-2x3 + 1x4 + 0x5 = 2
-3x1-6x2 + 3x3 + 0x4-1x5 = 5
4x1 + 3x2-1x3 + 0x4 + 0x5 = 3
Введем искусственные переменные x.
2x1 + 3x2-2x3 + 1x4 + 0x5 + 0x6 + 0x7 = 2
-3x1-6x2 + 3x3 + 0x4-1x5 + 1x6 + 0x7 = 5
4x1 + 3x2-1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 3
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1+3x2+2x3 - Mx6 - Mx7 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 5+3x1+6x2-3x3+x5
x7 = 3-4x1-3x2+x3
которые подставим в целевую функцию:
F(X) = 2x1 + 3x2 + 2x3 - M(5+3x1+6x2-3x3+x5) - M(3-4x1-3x2+x3) => max
или
F(X) = (2+1M)x1+(3-3M)x2+(2+2M)x3+(-1M)x5+(-8M) => max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:


 2

 3

 -2

 1

 0

 0

 0

 -3

 -6

 3

 0

 -1

 1

 0

 4

 3

 -1

 0

 0

 0

 1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x6, x7,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,2,0,5,3)

 План

 Базис

 В

 x1

 x2

 x3

 x4

 x5

 x6

 x7

 0

 x4

 2

 2

 3

 -2

 1

 0

 0

 0

 

 x6

 5

 -3

 -6

 3

 0

 -1

 1

 0

 

 x7

 3

 4

 3

 -1

 0

 0

 0

 1

 Индексная строка

 F(X0)

 -8M

 -2-1M

 -3+3M

 -2-2M

 0

 1M

 0

 0

Переходим к основному алгоритму симплекс-метода.

 План

 Базис

 В

 x1

 x2

 x3

 x4

 x5

 x6

 x7

 min

 1

 x4

 2

 2

 3

 -2

 1

 0

 0

 0

 0

 

 x6

 5

 -3

 -6

 3

 0

 -1

 1

 0

 1.67

 

 x7

 3

 4

 3

 -1

 0

 0

 0

 1

 0

 Индексная строка

 F(X1)

 -8M

 -2-1M

 -3+3M

 -2-2M

 0

 1M

 0

 0

 0

Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

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

Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 3 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x3
Строка, соответствующая переменной x3  в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3  и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.


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

 B

 x 1

 x 2

 x 3

 x 4

 x 5

 x 6

 x 7








 План

 Базис

 В

 x1

 x2

 x3

 x4

 x5

 x6

 x7

 min

 2

 x4

 5.33

 0

 -1

 0

 1

 -0.6667

 0.6667

 0

 0

 

 x3

 1.67

 -1

 -2

 1

 0

 -0.3333

 0.3333

 0

 0

 

 x7

 4.67

 3

 1

 0

 0

 -0.3333

 0.3333

 1

 1.56

 Индексная строка

 F(X2)

 3.33-4.67M

 -4-3M

 -7-1M

 0

 0

 -0.67+0.33M

 0.67+0.67M

 0

 0

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

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

Следовательно, 3-ая строка является ведущей
Разрешающий элемент равен 3 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x1
Строка, соответствующая переменной x1  в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1  и столбец x1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.


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

 B

 x 1

 x 2

 x 3

 x 4

 x 5

 x 6

 x 7

















 4.67 / 3 = 1.56

 3 / 3 = 1

 1 / 3 = 0.33

 0 / 3 = 0

 0 / 3 = 0

 -0.33 / 3 = -0.11

 0.33 / 3 = 0.11

 1 / 3 = 0.33











 План

 Базис

 В

 x1

 x2

 x3

 x4

 x5

 x6

 x7

 min

 3

 x4

 5.33

 0

 -1

 0

 1

 -0.6667

 0.6667

 0

 0

 

 x3

 3.22

 0

 -1.67

 1

 0

 -0.4444

 0.4444

 0.3333

 0

 

 x1

 1.56

 1

 0.3333

 0

 0

 -0.1111

 0.1111

 0.3333

 4.67

 Индексная строка

 F(X3)

 9.56

 0

 -5.67

 0

 0

 -1.11

 1.11+1M

 1.33+1M

 0

Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

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

Следовательно, 3-ая строка является ведущей
Разрешающий элемент равен 0.33 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 3 войдет переменная x2
Строка, соответствующая переменной x2  в плане 3, получена в результате деления всех элементов строки x1 плана 2 на разрешающий элемент РЭ=0.33
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x2 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x2  и столбец x2 .
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.


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

 B

 x 1

 x 2

 x 3

 x 4

 x 5

 x 6

 x 7

















 1.56 / 0.33 = 4.67

 1 / 0.33 = 3

 0.33 / 0.33 = 1

 0 / 0.33 = 0

 0 / 0.33 = 0

 -0.11 / 0.33 = -0.33

 План

 Базис

 В

 x1

 x2

 x3

 x4

 x5

 x6

 x7

 4

 x4

 10

 3

 0

 0

 1

 -1

 1

 1

 

 x3

 11

 5

 0

 1

 0

 -1

 1

 2

 

 x2

 4.67

 3

 1

 0

 0

 -0.3333

 0.3333

 1

 Индексная строка

 F(X4)

 36

 17

 0

 0

 0

 -3

 3+1M

 7+1M

x4 = 10
x3 = 11
x2 = 4.67
F(X) = 3*4.67 + 2*11 = 36

Составим двойственную задачу к прямой задаче.
2y1-3y2+4y3≥2
3y1-6y2+3y3≥3
-2y1+3y2-y3≥2
2y1+5y2+3y3 => min
y1 ≥ 0
y2 ≤ 0

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

Определив обратную матрицу А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =

Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 3
y3 = 7
Z(Y) = 2*0+5*3+3*7 = 36
Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
2*0 + 3*4.67 + -2*11  = -8 < 2
-3*0 + -6*4.67 + 3*11  = 5 = 5
4*0 + 3*4.67 + -1*11  = 3 = 3
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0.
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3>0).
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
Обоснование эффективности оптимального плана.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
2*0 + (-3)*3 + 4*7  = 19 > 2
3*0 + (-6)*3 + 3*7  = 3 = 3
-2*0 + 3*3 + (-1)*7  = 2 = 2
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x1 = 0.
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 2-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 3и станет равной:
F(x) = 36 + 3 = 39
Анализ устойчивости оптимального плана.
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
2-ый параметр целевой функции может изменяться в пределах:

-3 ≤ с2 ≤ 0
Таким образом, 2-параметр может быть уменьшен на 3 или увеличен на 0
Интервал изменения равен:
[3-3; 3+0] = [0;3]
Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.
3-ый параметр целевой функции может изменяться в пределах:

-7 ≤ с3 ≤ 0
Таким образом, 3-параметр может быть уменьшен на 7 или увеличен на 0
Интервал изменения равен:
[2-7; 2+0] = [-5;2]
Если значение c3 будет лежать в данном интервале, то оптимальный план не изменится.
Проведем анализ устойчивости двойственных оценок.
2-ый запас может изменяться в пределах:

3 ≤ b2 ≤ 0
Таким образом, 2-ый запас может быть уменьшен на 3 или увеличен на 0
Интервал изменения равен:
[5+3; 5+0] = [8;5]
3-ый запас может изменяться в пределах:

1.5 ≤ b3 ≤ 0
Таким образом, 3-ый запас может быть уменьшен на 1.5 или увеличен на 0
Интервал изменения равен:
[3+1.5; 3+0] = [4.5;3]

загрузка...