Двойственные задачи. Двойственность в линейном программировании. Виды двойственных задач. Алгоритм составления двойственных задач.
Двойственные задачи. Симметричные двойственные задачи. Модель симметричных двойственных задач.
Несимметричные двойственные задачи. Модель несимметричных-двойственных задач.
Двойственные задачи.
Производную задач линейного программирования можно сопоставить с другой задачей, которая называется двойственной. В этом случае первоначальная задача называется исходной. Эти задачи сходны между собой и они образуют двойственную пару. Есть двойственные задачи:
Симметричные
Несимметричные
Смешенные
1. Симметричные двойственные задачи
Исходная задача (ИЗ)
L(x) =c1x1 + c2x2 + … + cn xn → max
a
11
x1
+ a12
x2
+ … + a1n
xn
=< b1 y1
a21 x1 + a22 x2 + … + a2n xn =< b2 y2
…
am1 x1 + am2 x2 + … + amn xn =< bm ym
X = (x1, x2, … , xn) xi >=0, i=1,n
Алгоритм составления мат. модели двойственной задачи.
Каждому неравенству системы ограничений приводим в соответствии переменную yi
Составляем целевую функцию, коэффициентами которой являются свободные значения системы ограничений ИЗ.
Составляем систему ограничений, Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений ИЗ. Знаки неравенств меняются на противоположные.
Свободными значениями системы ограничений являются коэффициенты целевой функции ИЗ. Все переменные двойственной задачи также не отрицательны.
Двойственная задача (ДЗ)
S(y) = b1y1 + b2y2 + … + bm ym → min
a
11
y1
+ a21
y2
+ … + am1
ym
>= c1
a12 y1 + a22 y2 + … + am2 ym >= c2
…
a1n y1 + a2n y2 + … + amn ym >= cn
Y = (y1, y2, … , ym) yj>=0; j=1,m
2. Несимметричные двойственные задачи.
Исходная задача (ИЗ)
L(x) =c1x1 + c2x2 + … + cn xn → max
a
11
x1
+ a12
x2
+ … + a1n
xn
= b1
a21 x1 + a22 x2 + … + a2n xn = b2
…
am1 x1 + am2 x2 + … + amn xn = bm
xi >=0, i=1,n
Мат. модель двойственной задачи идентична предыдущему примеру.
Особенности двойственной несимметричной задачи:
Только неравенства ( если max, то =<; если min, то >=)
Переменные yj могут быть произвольными по знаку.
3. Смешенные двойственные пары.
Представляют систему, где идет смешение знаков (=, <, >)
Общая постановка симплексного метода. Алгоритм симплексного метода. Понятие опорного решения.
Аналитический способ решения задач симплексным методом.
Для реализации симплексного метода необходимо последовательно выполнить 3 последующих элементов:
Определение какого-либо первоначального допустимого базисного решения.
Определение правила перехода к лучшему (не худшему) решению
Определение критерия оптимальности найденного решения.
Пример симплекс метода:
F=2x1+3x2→max
x
1+3x2=<18
2x1+x2=<16
x2=<5
x1=<21
x1>=0; x2>=0
Для реализации симплексного метода система ограничений должна быть приведена к каноническому виду (в виде равенства)
x 1+3x2+x3=18
2x1+x2+x4=16
x2+x5=5
x1+x6=21
x3, 4, 5, 6>=0
X= (x1 x2 x3 x4 x5 x6)
F= 2x1+3x2+0*x3+0*x4+0*x5+0*x6→max
Все переменные нужно разделить на 2 группы: основные (базисные) и не основные. Основными будут называться переменные, кот. входят только один раз в систему ограничений.
Основные (базовые) – x3, x4, x5, x6
Неосновные – x1, x2
x
3=18
- x1
- 3x2
x4=16 - 2x1 - x2
x5=5 - x2
x6=21 - x1
Для нахождения первоначального решения нужно найти способ получения неотрицательного вектора.
Этап 1: X= (x1 x2 x3 x4 x5 x6)
x1 = 0 x2=0, тогда
Х1 = (0, 0, 18, 16, 5, 21)
F1=0
Выбираем только одну переменную
За основу выбора переменной, смотрим, какой коэффициент больше.
Этап 2: выбираем большую переменную из целевой функции на увеличение
x1=0, чтобы x2↑
x
3=18
- 3x2
x4=16 - x2
x5=5 - x2
x6=21
1
8
- 3x2>=0
16 - x2>=0
5 - x2>=0
21
x2=<6
x2=<16
x2=<5
x2 =5
X2= (0; 5; 3; 11; 0; 21)
F2 = 2*0 + 3*5 = 15
Этап 3:
Основные (базовые) – x3, x4, x2, x6
Неосновные – x1, x5
x
3=18
- x1
- 3x2
x4=16 - 2x1 - x2
x6=21 - 3x1
x2=5 – x5
подставляем x2 в уравнения.
x
3=18
- x1
– 3(5 – x5)
=3- x1+3x5
x4=16 - 2x1 - (5 – x5) =11 - 2x1 + x5
x6=21 - 3x1
x2=5 – x5
F=2x1+3x2=2x1+3(5 – x5) = 15+2x1–3 x5= 15
x5= 0
x
3=3
- x1
x4=11 - 2x1
x6=21 - 3x1
x2=5
3
- x1>=0
11 - 2x1 >=0
21 - 3x1>=0
5
x1=<3
x1=<5,6
x1=<7
x1 = 3
X3= (3; 5; 0; 5; 0; 12)
F3=21
Основные (базовые) – x1, x2, x4, x6
Неосновные – x3, x5
F=21-2x3+3x5
X4= (6; 4; 0; 0; 1; 3)
F4=24
Ответ: F=24-4/5x3-3/5x4