ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1088
Скачиваний: 2
71
2.7.
Симплекс
таблицы
и
их
свойства
Рассмотрим
каноническую
задачу
линейного
программирования
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
(2)
n
j
1
А
j
x
j
=B,
(3) x
j
≥
0, j=1,2,…,n.
Задачу
(1) – (3)
можно
записать
в
виде
таблицы
(4),
а
именно
,
A
1
A
2
…
A
j
…
A
n
B
a
11
a
12
… a
1j
… a
1n
b
1
(4)
a
21
a
22
… a
2j
… a
2n
b
2
…
…
…
…
…
…
…
a
m1
a
m2
… a
mj
… a
mn
b
m
–
γ
1
–
γ
2
… –
γ
j
… –
γ
n
γ
0
Пусть
вектор
α
есть
некоторое
опорное
решение
задачи
(1) – (3).
Выберем
один
из
базисов
этого
опорного
решения
,
например
,
А
i1
.
А
i2
, … ,
А
ir
.
Тогда
это
опорное
решение
будет
иметь
следующие
структуру
α
= ( 0, 0, …, 0,
α
i1
, 0, 0, …, 0,
α
i2
, 0, 0, … , 0,
α
ir
, 0, 0, .., 0)
Преобразовав
систему
векторов
условий
рассматриваемой
задачи
методом
Гаусса
к
базису
А
i1
.
А
i2
, … ,
А
ir
выбранного
опорного
решения
α
,
получим
таблицу
(5):
A
1
’
…
A
i1
’
…
A
i2
’
…
A
ir
…
A
n
’
B
’
γ
i1
‘
a
11
… 1 … 0 … 0 …
‘
a
1n
α
1
’
γ
i2
‘
a
21
…
0 … 1 … 0 …
‘
a
2n
α
2
’
(5) … … … … … … … … … … …
γ
ir
‘
a
r1
… 0 … 0 … 1 …
‘
a
rn
α
r
’
–
γ
1
… –
γ
i1
… –
γ
i2
…
γ
ir
… –
γ
n
γ
0
δ
1
…
δ
ir
…
δ
i2
…
δ
ir
…
δ
n
δ
0
Последняя
строка
таблицы
(5)
получена
в
результате
последовательного
сложения
противоположенных
значений
коэффициентов
целевой
функции
сначала
с
первой
строкой
системы
векторов
условий
,
умноженной
на
γ
i1
,
затем
со
второй
строкой
системы
векторов
условий
,
умноженной
на
γ
i2
,
и
так
далее
включая
последнюю
строку
векторов
условий
,
умноженную
на
γ
ir
.
Таблицу
(5)
будем
называть
симплекс
таблицей
системы
векторов
условий
задачи
(1) – (3)
,
приведенных
к
базису
опорного
решения
,
в
данном
случае
к
базису
А
i1
.
А
i2
, … ,
А
ir
,
а
числа
δ
1
,
δ
2
, …,
δ
n
–
оценками
векторов
условий
задачи
(1) – (3),
приведенных
к
базису
А
i1
.
А
i2
, … ,
А
ir
опорного
решения
α
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
72
Свойства
симплекс
таблицы
1
0
.
Если
симплекс
таблица
приведенна
к
базису
А
i1
.
А
i2
, … ,
А
ir
опорного
решения
α
,
то
в
столбце
В
’
находятся
координаты
опорного
решения
α
,
соответствующие
векторам
базиса
А
i1
.
А
i2
, … ,
А
ir
,
то
есть
α
1
’
=
α
i1
,
α
2
’
=
α
i2
,
…,
α
r
’
=
α
ir
,
▲
Так
как
вектор
α
= ( 0, 0, …, 0,
α
i1
, 0, 0, …, 0,
α
i2
, 0, 0, …, 0,
α
ir
, 0, 0, .., 0)
является
опорным
решением
задачи
(1) – (3),
то
он
является
и
допустимым
решением
этой
задачи
,
а
следовательно
,
является
решением
системы
линейных
уравнений
(2),
то
есть
выполняется
соотношение
:
(6)
А
i1
α
i1
+ A
i2
α
i2
+…+ A
ir
α
ir
= B.
Решением
системы
(5)
является
вектор
α
’
= ( 0, 0, …, 0,
α
1
’
, 0, 0, …, 0,
α
2
’
,
0, 0, … , 0,
α
r
’
, 0, 0, .., 0).
Системы
(5)
и
(4)
равносильны
,
так
как
получены
одна
из
другой
методом
Гаусса
.
Поэтому
вектор
α
’
является
решением
системы
(4),
и
,
следовательно
,
выполняться
соотношение
:
(7)
А
i1
α
1
’
+ A
i2
α
2
’
+…+ A
ir
α
r
’
= B.
Вычитая
из
соотношения
(6)
соотношение
(7),
получаем
соотношение
:
(8)
А
i1
(
α
i1
–
α
1
’
)+ A
i2
(
α
i2
–
α
2
’
)+…+ A
ir
(
α
ir
–
α
r
’
)
=
Ө
.
Так
как
векторы
А
i1
.
А
i2
, … ,
А
ir
являются
базисом
системы
векторов
условий
задачи
(1) – (3),
то
они
линейно
независимы
.
Следовательно
,
соотношение
(8)
возможно
,
при
α
i1
–
α
1
’
= 0,
α
i2
–
α
2
’
= 0, …,
α
ir
–
α
1
’
= 0.
Откуда
α
i1
=
α
1
’
,
α
i2
=
α
2
’
, …,
α
ir
=
α
1
’
■
2
0
.
Оценки
базисных
векторов
опорного
решения
всегда
равны
нулю
,
то
есть
,
если
векторы
А
i1
.
А
i2
, … ,
А
ir
являются
базисом
некоторого
опорного
решения
задачи
(1) – (3),
то
δ
i1
=
δ
i2
=…,=
δ
ir
.
▲
Доказательство
следует
из
построения
строки
оценок
системы
векторов
условий
,
приведенных
к
базису
опорного
решения
.
■
3
0
.
Если
симплекс
таблица
приведена
к
базису
опорного
решения
α
,
то
δ
0
= f(
α
).
▲
Из
построения
строки
оценок
для
системы
векторов
условий
задачи
(1) – (3),
приведенной
к
базису
А
i1
.
А
i2
, … ,
А
ir
,
и
с
учетом
того
,
что
α
1
’
=
α
i1
,
α
2
’
=
α
i2
, …,
α
1
’
=
α
ir
(
см
.
1
0
)
следует
:
δ
0
=
γ
0
+
γ
i1
α
i1
+
γ
i2
α
i2
+…+
γ
ir
α
ir
= f(
α
).
■
Пример
.
Пусть
вектор
α
=(1, 0, 1)
является
опорным
решением
КЗЛП
на
минимум
вида
:
f(X) = 3x
1
+ 4x
2
– x
3
(min),
2x
1
– x
2
+
х
3
=3,
x
1
+ x
2
+ x
3
=2,
x
j
≥
0, j = 1, 2, 3.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
73
Покажем
,
что
δ
0
= f(
α
).
▲
Приведем
систему
векторов
условий
данной
задачи
к
базису
А
1
,
А
3
опорного
решения
α
=(1, 0, 1)
A
1
A
2
A
3
B A
1
A
2
A
3
B A
1
A
2
A
3
B
2 –1
1
3
2 –1
1 3
0 3 1 1 *(–1)
1 1 1 2
–1
2 0 –1
1 –2 0 1 *(3)
–
γ
–3
–4 1 0 *(1)
δ
δ
0 –13 0
2
В
полученной
симплекс
таблице
имеем
строку
оценок
õ=(0, –13, 0)
системы
векторов
условий
,
приведенных
к
базису
А
1
,
А
3
опорного
решения
α
=(1, 0, 1),
а
δ
0
= 2
соответствует
значению
целевой
функции
на
этом
опорном
решении
f(
α
) = 3 *1 + 4* 0 – 1* 1 = 2,
следовательно
,
δ
0
= f(
α
).
■
Лемма
(
о
целевой
функции
).
Пусть
δ
1
, …,
δ
j
, …,
δ
n
оценки
векторов
условий
задачи
(1) – (3),
приведенных
к
базису
опорного
решения
α
.
Если
вектор
β
=(
1
, …,
j
, …,
n
)
является
допустимым
решением
данной
задачи
,
то
f(
β
)=f(
α
) –
n
j
1
δ
j
j
.
▲
Пусть
векторы
А
1
,
А
2
, …,
А
r
являются
базисом
опорного
решения
α
=(
α
1
,
α
2
, …,
α
r
, 0, 0, …, 0).
Тогда
симплекс
таблица
системы
векторов
условий
задачи
(1) – (3),
приведенных
к
данному
базису
будет
иметь
вид
:
A
’
1
A
’
2
… A
’
r
A
’
r+1
… A
’
n
B
’
1 0
…
0
a
/
1,r+1
a
'
1n
α
1
0 1
…
0
a
'
2,r+1
a
'
2n
α
2
(9) … … … …
… … … …
0 0
…
1
a
'
r,r+1
a
'
rn
α
r
–
γ
1
–
γ
2
–
γ
r
–
γ
r+1
–
γ
n
γ
0
δ
1
δ
2
δ
r
δ
r+1
δ
n
δ
0
где
по
правилу
построения
строки
(
δ
1
, …,
δ
j
, …,
δ
n),
оценки
примут
следующие
значения
:
δ
1
=
δ
2
= …=
δ
r
=0
и
δ
r+1
= –
γ
r+1
+
a
'
1,r+1
γ
1
+ … a
'
r,r+1
γ
r
,
δ
r+2
= –
γ
r+2
+
a
'
1,r+2
γ
1
+ …
a
'
r,r+2
γ
r
,
(10) …
…
…
…
…
δ
n
= –
γ
n
+
a
'
1n
γ
1
+ … a
'
rn
γ
r
.
По
условию
вектор
β
=(
1
, …,
j
, …,
l
n
)
является
допустимым
решением
задачи
(1) – (3),
следовательно
,
он
является
решением
СЛУ
(2) ,
то
есть
должно
выполнятся
равенство
:
А
’
1
1
+
А
’
2
2
+ … +
А
’
r
r
+
А
’
r+1
r+1
+ … +
А
’
n
n
=
В
’
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
74
С
учетом
этого
соотношения
и
таблицы
(9)
получаем
:
1
+
a
'
1,r+1
r+1
+ … + a
’
1n
n
=
α
1
,
2
+
a'
2,r+1
r+1
+ … + a
’
2n
n
=
α
2
,
… …
…
… …
(11)
r
+
a
'
r,r+1
r+1
+ … + a
’
rn
n
=
α
r
.
Значение
целевой
функции
на
векторе
β
=(
1
, …,
j
, …,
n
)
с
учетом
соотношений
(10)
и
(11)
будет
равно
:
f(
β
) =
γ
1
1
+
γ
2
2
+ … +
γ
r
r
+
γ
r+1
r+1
+
γ
r+2
r+2
+…+
γ
n
n
+
γ
0
=
=
γ
1
1
+
γ
2
2
+ … +
γ
r
r
+ ( –
δ
r+1
+ a
1,r+1
γ
1
+…+ a
’
r,r+1
γ
r
)
r+1
+ ( –
δ
r+21
+ a
1,r+2
γ
1
+ … + a
’
r,r+2
γ
r
)
r+2
+…+ ( –
δ
n
+ a
1,n
γ
1
+…+ a
’
n
γ
r
)
n
+
γ
0
=
=
γ
0
–
δ
r+1
r+1
–
δ
r+2
r+2
–…–
δ
n
n
+
γ
1
(
1
+ …+ a
’
1,r+1
r+1
+ a
’
1,r+2
r+2
+…+ a
’
1n
n
) +…+
γ
r
(
r
+…+ a
’
r,r+1
r+1
+ a
’
r,r+2
r+2
+…+ a
’
rn
n
) =
=
γ
0
+
γ
1
α
1
+ … +
γ
r
α
r
–
δ
r+1
r+1
–
δ
r+2
r+2
–…–
δ
n
n
.
Так
как
для
базисных
векторов
А
1
,
А
2
, …,
А
r
оценки
равны
нулю
,
т
.
е
.
δ
1
=
δ
2
= …= =
δ
r
=0,
то
значение
целевой
функции
на
векторе
β
можно
записать
в
виде
f(
β
) =
γ
0
+
γ
1
α
1
+ … +
γ
r
α
r
–
δ
1
1
–
δ
2
2
…–
δ
r
r
–
δ
r+1
r+1
–
δ
r+2
r+2
–…–
δ
n
n
== f(
α
) –
n
j
1
δ
j
j
.
■
Теорема
(
достаточное
условие
оптимальности
опорного
решения
)
Если
для
опорного
решения
α
0
канонической
задачи
линейного
программирования
на
минимум
(1) – (3)
найдется
базис
,
для
которого
все
оценки
неположительные
,
то
есть
δ
j
≤
0
для
всех
j = 1, 2, …, n,
то
вектор
α
0
является
оптимальным
решением
данной
задачи
.
▲
Пусть
δ
1
,
δ
2
, …,
δ
n
–
оценки
системы
векторов
условий
,
приведенных
к
некоторому
базису
опорного
решения
α
0
.
Если
вектор
β
=(
1
, …,
j
, …,
n
)
является
произвольным
допустимым
решением
канонической
задачи
линейного
программирования
(1) – (3),
то
по
доказанной
лемме
имеем
: f(
β
)=f(
α
) –
n
j
1
δ
j
j
.
Так
как
,
для
любых
j=1, 2, …, n
по
условию
δ
j
≤
0 ,
а
вектор
β
=(
1
, …,
j
,
…,
n
)
произвольное
допустимое
решение
данной
задачи
,
т
.
е
.
j
≥
0
для
всех
j=1, 2, …, n ,
то
f(
β
)
≥
f(
α
0
).
Следовательно
,
по
определению
вектор
α
0
является
оптимальным
решением
задачи
(1) – (3)
на
минимум
.
■
Пример
.
Пусть
вектор
α
=(1, 0, 0, 0)
является
опорным
решением
КЗЛП
на
минимум
вида
:
f(X) = -10x
1
+ 4x
2
– 9x
3
+6
х
4
(min),
x
1
+ x
2
+ 3
х
3
=1,
x
1
– x
2
– x
3
+2
х
4
, =1,
x
j
≥
0, j = 1, 2, 3, 4
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
75
Выясним
,
является
ли
вектор
α
оптимальным
решением
данной
задачи
.
▲
Приведем
систему
векторов
условий
задачи
и
строку
с
противоположенными
значениями
коэффициентов
целевой
функции
к
симплекс
таблице
,
соответствующей
базису
А
1
,
А
2
данного
опорного
решения
.
А
1
А
2
А
3
А
4
В
А
1
А
2
А
3
А
4
В
А
1
А
2
А
3
А
3
В
1
1 3 0 1
1 1 3 0 1
1 0 1 1 1
1 –1
–1 2
1 0
–2
–4 2 0 0 1
2
–1 0
–
γ
10 –1 9 –6 0 0 –11 –21 –6 –10
δ
= 0 0 1
–17 –10
В
строке
оценок
первой
симплекс
таблице
имеется
положительная
оценка
δ
3
=1.
Поэтому
нельзя
утверждать
,
что
вектор
α
=(1,
0,
0,
0)
является
оптимальным
решением
данной
задачи
.
Однако
,
если
в
качестве
базиса
данного
опорного
решения
взять
векторы
А
1
,
А
3
,
то
в
новой
симплекс
таблице
все
векторы
условий
данной
задачи
имеют
неположительные
оценки
и
,
следовательно
,
по
доказанной
теореме
вектор
α
=(1, 0, 0, 0)
является
оптимальным
решением
данной
КЗЛП
.
■
Теорема
(
о
неограниченности
целевой
функции
).
Пусть
симплекс
таблица
приведена
к
некоторому
базису
опорного
решения
α
канонической
задачи
линейного
программирования
(1) – (3)
на
минимум
.
Если
при
этом
существует
столбец
А
s
с
положительной
оценкой
,
т
.
е
.
δ
s
> 0,
где
s=1, 2, …, n ,
а
все
остальные
элементы
этого
столбца
неположительные
,
т
.
е
,
α
is
≤
0, i=1, 2, …, r ,
то
целевая
функция
данной
задачи
неограниченна
на
множестве
допустимых
решений
,
и
,
следовательно
,
задача
не
имеет
оптимального
решения
.
▲
Пусть
симплекс
таблица
приведена
к
базису
А
1
,
А
2
, …,
А
r
опорного
решения
α
=(
α
1
,
α
2
, …,
α
r
, 0, 0, …, 0)
и
имеет
вид
:
A
’
1
A
’
2
… A
’
r
A
’
r+1
…
A
’
s
… A
’
n
B
’
1 0 … 0 a
/
1,r+1
…
a
'
1s
… a
'
1n
α
1
0 1 … 0 a
'
2,r+1
…
a
'
2s
… a
'
2n
α
2
… … … … … …
… …
0 0 … 1 a
'
r,r+1
…
a
'
rs
… a
'
rn
α
r
0
0 0
δ
r+1
…
δ
s
…
δ
n
δ
0
Следовательно
,
вектор
ограничений
В
’
,
а
также
вектор
условий
А
’
s
можно
представить
в
виде
линейной
комбинации
базисных
векторов
,
а
именно
,
(12)
А
’
1
α
1
+
А
’
2
α
2
+ …+
А
’
r
α
r
=
В
’
и
А
’
1
a
’
1s
+
А
’
2
a’
2s
+ … +
А
’
r
a’
rs
= A
’
s
А
1
А
2
А
3
А
4
В
1 –1/2 0 3/2 1
0 1/2 1 –1/2 0
δ
=
0 –1/2 0 –33/2 –10
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.