ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1140
Скачиваний: 2
91
2.10.
Взаимно
двойственные
задачи
линейного
программирования
Определение
.
Взаимно
двойственными
задачами
линейного
программирования
(
ЛП
)
называется
пара
задач
вида
:
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
(max),
(2)
n
j
1
a
ij
x
j
≤
b
i
, i
I
M={1,2,…,m},
(3)
n
j
1
a
ij
x
j
= b
i
, i
M \ I,
(4)
x
j
≥
0, j
J
N=(1, 2, …, n}
и
(1’)
φ
(Y) =
m
i
1
b
i
y
i
+
γ
0
(min),
(2’)
m
i
1
a
ij
y
i
≥
γ
j
, j
J
N={1,2,…,n},
(3’)
m
i
1
a
ij
y
i
=
γ
j
, j
N \ J,
(4’) y
i
≥
0, i
I
M=(1, 2, …, m}.
Если
дана
задача
ЛП
,
то
для
нее
всегда
можно
построить
взаимно
двойственную
задачу
ЛП
,
используя
следующие
правила
.
1
0
.
Одна
из
пары
взаимно
двойственных
задач
ЛП
должна
быть
задачей
на
максимум
и
левая
часть
ее
системы
условий
не
больше
правой
,
то
есть
между
левой
и
правой
частями
системы
условий
неравенство
вида
:
≤
.
Тогда
другая
из
пары
взаимно
двойственных
задач
ЛП
должна
быть
задачей
на
минимум
и
левая
часть
ее
системы
условий
не
меньше
правой
,
то
есть
между
левой
и
правой
частями
системы
условий
неравенство
вида
:
≥
.
2
0
.
Для
каждой
из
пары
взаимно
двойственных
задач
ЛП
можно
выписать
таблицу
,
в
которой
координаты
вектора
ограничений
,
входящие
в
неравенства
системы
условий
,
и
коэффициенты
целевой
функции
при
неотрицательных
переменных
отмечаются
звездочкой
.
При
этом
таблица
для
одной
из
взаимно
двойственных
задач
ЛП
после
транспонирования
становится
таблицей
для
другой
из
взаимно
двойственных
задач
ЛП
.
Пример
.
Для
задачи
ЛП
на
максимум
построить
взаимно
двойственную
задачу
ЛП
на
минимум
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
92
f(x) = x
1
+ 2x
2
– x
3
(max)
x
1
+ x
2
– 2x
3
≤
3,
1 1 –2 3 *
1
2 –1 1 *
2x
1
– x
2
+
x
3
= 4,
2 –1 1 4
1 –1 1 2
–x
1
+ x
2
+ 4x
3
≤
5,
–1 1 4 5 *
–2 1 4 –1
x
1
≥
0. 1 2 –1 0
3 4 5 0
*
*
*
φ
(y) = 3y
1
+ 4y
2
+ 5y
3
(min),
y
1
+ 2y
2
– y
3
≥
1,
y
1
– y
2
+ y
3
=
2,
–2y
1
+ y
2
+ 4y
3
=
–1,
y
1
≥
0, y
3
≥
0.
Отметим
,
что
:
число
переменных
одной
из
взаимно
двойственных
задач
ЛП
равно
числу
ограничений
в
системе
условий
другой
из
взаимно
двойственных
задач
ЛП
;
неотрицательным
переменным
одной
из
взаимно
двойственных
задач
ЛП
соответствуют
неравенства
в
системе
ограничений
другой
из
взаимно
двойственных
задач
ЛП
;
координаты
вектора
ограничений
одной
из
взаимно
двойственных
задач
ЛП
являются
коэффициентами
при
переменных
в
целевой
функции
другой
из
взаимно
двойственных
задач
ЛП
.
Важнейшие
частные
случаи
взаимно
двойственных
задач
линейного
программирования
:
1.
Симметричная
пара
взаимно
двойственных
задач
ЛП
( I = M, J = N):
f(X) =
n
j
1
γ
j
x
j
+
γ
0
(max),
φ
(Y) =
m
i
1
b
i
y
i
+
γ
0
(min),
n
j
1
a
ij
x
j
≤
b
i
, i =1,2,…,m,
m
i
1
a
ij
y
i
≥
γ
j
, j =1,2,…,n,
x
j
≥
0, j=1, 2, …, n. y
i
≥
0, i=1, 2, …, m.
2.
Несимметричная
пара
взаимно
двойственных
задач
ЛП
( I = Ø, J = N):
f(X) =
n
j
1
γ
j
x
j
+
γ
0
(max),
φ
(Y) =
m
i
1
b
i
y
i
+
γ
0
(min),
n
j
1
a
ij
x
j
= b
i
, i =1,2,…,m,
m
i
1
a
ij
y
i
≥
γ
j
, j =1,2,…,n,
x
j
≥
0, j=1, 2, …, n.
y
i
, i=1, 2, …, m.
Лемма
.
Если
векторы
α
=(k
1
, …, k
n
)
и
β
=(
1
, …,
m
)
являются
допустимыми
решениями
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) –
(4’)
соответственно
,
то
выполняются
неравенства
:
(L
1
)
(
n
j
1
a
ij
k
j
)
i
≤
b
i
i
, i=1, 2, …, m
,
(L
2
)
(
m
i
1
a
ij
I
)k
j
≥
γ
j
k
j
, j=1, 2, …, n
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
93
▲
Если
i
I,
то
n
j
1
a
ij
k
j
≤
b
i
и
i
≥
0
(
n
j
1
a
ij
k
j
)
i
≤
b
i
i
.
Если
же
,
i
M \ I,
то
n
j
1
a
ij
k
j
= b
i
и
для
i
,
справедливо
(
n
j
1
a
ij
k
j
)
i
= b
i
i
.
Следовательно
,
для
любых
i = 1, 2, …, m
выполняется
неравенство
(L
1
) .
Справедливость
неравенства
(L
2
)
доказывается
аналогично
.
■
Основные
свойства
взаимно
двойственных
задач
ЛП
1
0
.
Если
векторы
α
=(k
1
, …, k
n
)
и
β
=(
1
, …,
m
)
являются
допустимыми
решениями
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) – (4’)
соответственно
,
то
f(
α
)
≤
φ
(
β
).
▲
Значение
целевой
функции
ЗЛП
(1) – (4)
на
допустимом
векторе
α
=(k
1
, …, k
n
)
с
учетом
доказанной
леммы
можно
записать
в
виде
f(
α
) =
γ
1
k
1
+…+
γ
т
k
n
+
γ
0
≤
(
m
i
1
a
i1
i
) k
1
+…+ (
m
i
1
a
in
i
) k
n
+
γ
0
=
=(a
11
1
+…+a
m1
m
)k
1
+…+(a
1n
1
+…+a
mn
m
)k
n
+
γ
0
= =(a
11
k
1
+…+a
1n
k
n
)
1
+…+(a
m1
k
1
+…+a
mn
k
n
)
m
+
γ
0
=
=(
n
j
1
a
1j
k
j
)
1
+…+ (
n
j
1
a
mj
k
j
)
m
+
γ
0
=b
1
1
+…+ b
m
m
+
γ
0
≤
φ
(
β
).
Следовательно
, f(
α
)
≤
φ
(
β
).
■
2
0
.
Если
векторы
α
0
и
β
0
являются
допустимыми
решениями
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) – (4’)
соответственно
,
и
f(
α
0
) =
φ
(
β
0
),
то
векторы
α
0
и
β
0
–
оптимальные
решения
этих
задач
соответственно
.
▲
Для
произвольного
допустимого
решения
α
задачи
ЛП
(1) – (4)
по
свойству
1
0
выполнятся
неравенство
f(
α
)
≤
φ
(
β
0
).
Так
как
по
условию
f(
α
0
) =
φ
(
β
0
),
то
f(
α
)
≤
f(
α
0
)
и
по
определению
вектор
α
0
является
оптимальным
решением
ЗЛП
(1) – (4).
Оптимальность
вектора
β
0
доказывается
аналогично
.
■
3
0
.
Если
целевая
функция
одной
из
взаимно
двойственных
задач
ЛП
неограниченна
на
множестве
допустимых
решений
этой
задачи
,
то
другая
взаимно
двойственная
задача
ЛП
не
имеет
ни
одного
допустимого
решения
,
т
.
е
.
система
условий
этой
задачи
является
несовместной
.
▲
Доказательство
проведем
от
противного
.
Пусть
целевая
функция
–
φ
(
β
)
задачи
ЛП
(1’) – (4’)
неограниченна
снизу
на
множестве
допустимых
решений
,
а
задача
ЛП
(1) – (4)
имеет
допустимое
решение
–
α
.
Тогда
по
свойству
1
0
для
любого
допустимого
решения
–
β
задачи
ЛП
(1’) – (4’)
должно
выполняется
неравенство
: f(
α
)
≤
φ
(
β
).
Это
неравенство
противоречит
неограниченности
снизу
целевой
функции
φ
(
β
)
на
множестве
допустимых
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
94
решений
этой
задачи
.
Следовательно
,
задача
ЛП
(1) – (4)
не
имеет
ни
одного
допустимого
решения
,
т
.
е
.
система
условий
этой
задачи
несовместна
.
■
Теоремы
двойственности
Теорема
1
.
Если
одна
из
взаимно
двойственных
задач
ЛП
имеет
оптимальное
решение
,
то
и
другая
взаимно
двойственная
задача
ЛП
имеет
оптимальное
решение
,
при
этом
значения
целевых
функций
на
оптимальных
решениях
этих
задач
совпадают
.
Если
же
целевая
функция
одной
из
взаимно
двойственных
задач
ЛП
неограниченна
на
множестве
допустимых
решений
,
то
вторая
из
взаимно
двойственных
задач
ЛП
не
имеет
ни
одного
допустимого
решения
,
т
.
е
.,
система
условий
второй
задачи
несовместна
.
▲
Доказательство
теоремы
следует
из
сформулированных
выше
свойств
.
■
Теорема
2
.
Пусть
векторы
α
0
=(x
1
0
, …, x
n
0
)
и
β
0
=(y
1
0
, …, y
m
0
)
являются
допустимыми
решениями
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) –
(4’)
соответственно
.
Для
того
,
чтобы
векторы
α
0
и
β
0
были
оптимальными
решениями
этих
задач
необходимо
и
достаточно
выполнение
следующих
равенств
:
x
j
0
(
m
i
1
a
ij
y
i
0
–
γ
j
) = 0, j=1, 2, …, n;
y
i
0
(
n
j
1
a
ij
x
j
0
– b
i
) = 0, i=1, 2, …, m.
▲
Необходимост
ь
.
Пусть
векторы
α
0
и
β
0
оптимальные
решения
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) – (4’)
соответственно
.
Тогда
по
свойству
2
0
выполняется
равенство
f(
α
0
) =
φ
(
β
0
),
которое
можно
записать
в
виде
:
γ
1
x
1
0
+ … +
γ
n
x
n
0
+
γ
0
= b
1
y
1
0
+ … + b
m
y
m
0
+
γ
0
.
Это
равенство
с
учетом
соотношения
(L
2
) ,
т
.
е
. (
m
i
1
a
ij
y
i
0
)x
j
0
≥
γ
j
x
j
0
, j=1, 2, …, n,
равносильно
неравенству
:
(
m
i
1
a
i1
y
i
0
) x
1
0
+ … +(
m
i
1
a
i
т
y
i
0
) x
т
0
≥
b
1
y
1
0
+ … + b
m
y
m
0
(a
11
y
1
0
+…+a
m1
y
m
0
)x
1
0
+…+(a
1n
y
1
0
+…+a
mn
y
m
0
)x
n
0
+
γ
0
≥
b
1
y
1
0
+ … + b
m
y
m
0
(a
11
x
1
0
+…+a
1n
x
n
0
– b
1
)y
1
0
+…+(a
m1
x
1
0
+…+a
mn
x
n
0
– b
m
)y
m
≥
0
(
n
j
1
a
1j
x
j
0
– b
1
) y
1
0
+…+ (
n
j
1
a
mj
x
j
0
– b
m
) y
m
0
≥
0.
В
то
же
время
,
из
условий
задач
(1) – (4)
и
(1
’
) – (4
’
)
следует
,
что
каждое
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
95
слагаемое
в
последнем
неравенстве
неположительное
.
Поэтому
и
все
выражение
в
левой
части
этого
неравенства
неположительно
.
Следовательно
,
в
последнем
соотношении
должно
быть
равенство
,
т
.
е
.
(
n
j
1
a
1j
x
j
0
– b
1
) y
1
0
+…+ (
n
j
1
a
mj
x
j
0
– b
m
) y
m
0
= 0
Однако
сумма
неположительных
слагаемых
может
равняться
нулю
только
тогда
,
когда
каждое
из
слагаемых
равно
нулю
,
т
.
е
.
y
i
0
(
n
j
1
a
ij
x
j
0
– b
i
) = 0, i=1, 2, …, m.
Таким
образом
,
необходимость
для
выполнения
второго
соотношения
в
утверждении
теоремы
доказана
.
Необходимость
для
выполнения
первого
соотношения
в
утверждении
теоремы
доказывается
аналогично
.
Достаточность
.
Пусть
выполняются
равенства
:
x
j
0
(
m
i
1
a
ij
y
i
0
–
γ
j
) = 0, j=1, 2, …, n;
y
i
0
(
n
j
1
a
ij
x
j
0
– b
i
) = 0, i=1, 2, …, m.
Тогда
f(
α
0
) =
γ
1
x
1
0
+ … +
γ
n
x
n
0
+
γ
0
= x
j
0
(
m
i
1
a
ij
y
i
0
) + … + x
j
0
(
m
i
1
a
ij
y
i
0
) +
γ
0
=
= (a
11
y
1
0
+…+a
m1
y
m
0
)x
1
0
+…+(a
1n
y
1
0
+…+a
mn
y
m
0
)x
n
0
+
γ
0
=
= (a
11
x
1
0
+…+a
1n
x
n
0
)y
1
0
+…+(a
m1
x
1
0
+…+a
mn
x
n
0
)y
m
+
γ
0
=
= b
1
y
1
0
+ … + b
m
y
m
0
+
γ
0
.=
φ
(
β
0
)
т
.
е
. f(
α
0
) =
φ
(
β
0
).
Откуда
с
учетом
свойства
2
0
следует
,
что
векторы
α
0
и
β
0
оптимальные
решения
взаимно
двойственных
задач
ЛП
(1) – (4)
и
(1’) – (4’)
соответственно
.
■
Пример
.
Дано
α
0
= (1. 0 , –4) –
оптимальное
решение
задачи
ЛП
на
минимум
.
f(X) = 2 x
1
– 4
x
3
(min)
x
1
– x
2
≤
1,
x
1
– 3
x
2
– 2
x
3
≥
9,
x
1
+ x
2
– 2
x
3
≥
7,
x
1
≥
0 x
2
≥
0
Найти
оптимальное
решение
взаимно
двойственной
задачи
ЛП
на
максимум
,
используя
2-
ю
теорему
двойственности
.
▲
Перепишем
данную
задачу
ЛП
в
стандартной
форме
и
,
используя
выше
сформулированные
правила
,
найдем
взаимно
двойственную
к
ней
задачу
ЛП
f(X) = 2 x
1
– 4
x
3
(min)
–
x
1
+ x
2
≥
–1,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.