ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1090
Скачиваний: 2
56
номер
j
такой
,
что
k
j
≠
0, j = 1, 2, …
.
Тогда
найдется
положительное
число
δ
такое
,
что
:
α
j
δ
k
j
≥
0
для
всех
j = 1, 2, …
l,
а
одно
из
чисел
{
α
j
δ
k
j
}
обязательно
равно
нулю
.
Доказательство
предлагается
студентам
провести
самостоятельно
.
Теорема
(
о
существовании
опорного
решения
).
Если
каноническая
задача
линейного
программирования
имеет
хотя
бы
одно
допустимое
решение
,
то
эта
задача
имеет
и
опорное
решение
.
▲
Рассмотрим
КЗЛП
(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
, …,
α
, 0, …, 0),
где
координаты
α
1
> 0, …,
α
> 0 (
координаты
всегда
можно
перенумеровать
так
,
что
первыми
из
них
станут
ненулевые
)
и
докажем
,
что
выбранный
вектор
является
опорным
решением
задачи
(1) – (3).
Предположим
противное
,
а
именно
,
что
вектор
α
не
является
опорным
решением
.
Тогда
по
определению
опорного
решения
,
векторы
A
1
, A
2
, … A
,
соответствующие
ненулевым
координатам
выбранного
вектора
α
,
образуют
линейно
зависимую
систему
.
Из
определения
линейно
зависимой
системы
векторов
следует
,
что
найдется
ненулевой
набор
чисел
k
1
, k
2
, …k
такой
,
что
будет
выполняться
соотношение
(4)
A
1
k
1
+ A
2
k
2
+ … + A
k
=
Ө
.
Так
как
вектор
α
является
допустимым
решением
рассматриваемой
задачи
,
то
по
определению
,
этот
вектор
является
решением
системы
линейных
уравнений
(2).
Тогда
по
определению
решения
системы
уравнений
должно
выполняться
соотношение
(5)
A
1
α
1
+ A
2
α
2
+ … + A
α
=
В
.
Прибавив
к
соотношению
(5)
соотношение
(4),
умноженное
на
δ
,
получим
А
1
(
α
1
δ
k
1
) +
А
2
(
α
2
δ
k
2
) + … +
А
(
α
δ
k
) = B.
Из
последнего
соотношения
по
определению
решения
системы
уравнений
следует
,
что
векторы
α
’
= (
α
1
+
δ
k
1
,
α
2
+
δ
k
2
, …
α
+
δ
k
, 0, …, 0)
и
α
”
=
(
α
1
–
δ
k
1
,
α
2
–
δ
k
2
, …
α
–
δ
k
, 0. …. 0 )
являются
решениями
системы
линейных
уравнений
(2).
Если
же
число
δ
выбрать
так
,
что
оно
удовлетворяет
арифметической
лемме
,
то
координаты
векторов
α
’
и
α
”
будут
удовлетворять
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
57
условию
(3),
а
сами
векторы
будут
являться
допустимыми
решениями
задачи
(1)–(3)
и
при
этом
,
хотя
бы
у
одного
из
этих
векторов
число
ненулевых
координат
будет
меньше
,
чем
.
Это
противоречит
выбору
допустимого
вектора
α
.
Следовательно
,
вектор
α
является
опорным
решением
задачи
(1)–
(3).
■
Ответьте
на
вопросы
1.
Выпишите
в
координатной
форме
j-
й
вектор
условий
канонической
задачи
линейного
программирования
.
2.
Дайте
определение
линейно
зависимой
системе
векторов
.
3.
Дайте
определение
опорного
решения
канонической
задачи
линейного
программирования
.
4.
Как
выяснить
,
является
ли
вектор
опорным
решением
данной
канонической
задачи
линейного
программирования
?
5.
Выпишите
формулировку
арифметической
леммы
.
6.
Сформулируйте
теорему
о
существовании
опорного
решения
для
данной
канонической
задачи
линейного
программирования
.
7.
На
каком
противоречии
построено
доказательство
теоремы
о
существовании
опорного
решения
для
данной
канонической
задачи
линейного
программирования
?
Решите
самостоятельно
Дана
система
условий
канонической
задачи
линейного
программирования
и
векторы
α
(k)
.
Выяснить
,
являются
ли
эти
векторы
опорными
решениями
данной
задачи
:
1.
x
j
≥
0, j–1, 2, 3, 4,
α
(1)
= (1, 0, 1, 1),
α
(2)
=(3, –1, –1, 0).
2.
x
j
≥
0, j–1, 2, 3, 4,
α
(1)
= (1, 1, 1, 0),
α
(2)
=(2, 2, 0, 0),
α
(3)
=(0, 2, 1, 0).
3
х
1
+
х
2
–
х
3
+ 3
х
4
= 3,
2
х
1
–
х
2
+ 3
х
3
–
х
4
= 4,
х
1
+ 2
х
2
–
х
3
+ 2
х
4
= 2,
х
1
+
х
2
+ 2
х
3
–
х
4
= 4,
2
х
1
–
х
2
+
х
3
– 2
х
4
= 2,
–
х
1
+ 2
х
2
+
х
3
+ 3
х
4
= 2,
х
1
–
х
2
+
х
3
+ 3x
4
– 3x
5
= 1,
х
1
+
х
2
–
х
3
+
x
4
+
х
5
= 1,
х
1
+
х
2
+
х
3
+ 5x
4
–
х
5
= 3,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
58
x
j
≥
0, j–1, 2, 3, 4,
α
= (1, 1, 1, 0, 0),
4.
x
j
≥
0, j–1, 2, 3, 4,5,
α
= (1, 2, 2, 1, 0),.
5.
x
j
≥
0, j–1, 2, 3, 4,
α
= (0, 1, 1, 1),.
6.
x
j
≥
0, j–1, 2, 3, 4,
α
= (1, 0, 1, 1).
х
2
+
х
3
+ x
4
– 2x
5
= 5,
х
1
+
х
3
+
x
4
+
х
5
= 4,
х
1
+
х
2
+
x
4
–
х
5
= 4,
х
1
+
х
2
+
х
3
–
2
х
5
= 5,
х
1
–
х
2
+ 2
х
3
+ 3
х
4
= 4,
2
х
1
+
3
х
2
–
х
3
+
х
4
= 3,
х
1
–
х
2
+ 2
х
3
– 3
х
4
= –2,
х
1
+ 2
х
2
–
х
3
–
х
4
= –1,
2
х
1
–
х
2
+ 3
х
3
+ 8
х
4
=13,
х
1
–
х
2
+
х
3
+ 3
х
4
= 5,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
59
2. 5.
Базис
опорного
решения
Среди
базисов
системы
векторов
А
1
, …,
А
j
, …,
А
n
условий
канонической
задачи
линейного
программирования
(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.
имеются
базисы
,
соответствующие
опорным
решениям
данной
задачи
.
Определение
.
Базис
A
i1
, A
i2
, …, A
ir
системы
векторов
А
1
, …,
А
j
, …,
А
n
условий
задачи
(1) – (3)
называется
базисом
опорного
решения
α
= (
α
1
, …,
α
j
, …,
α
n
),
если
α
i
= 0
для
любых
i
≠
i
1
, i
2, …,
i
r
.
Таким
образом
,
базис
A
i1
, A
i2
, …, A
ir
системы
векторов
А
1
, …,
А
j
, …,
А
n
условий
задачи
(1) – (3)
называется
базисом
опорного
решения
α
= (
α
1
, …,
α
j
, …,
α
n
),
если
небазисным
векторам
из
системы
векторов
условий
задачи
(1) –
(3)
соответствуют
нулевые
координаты
опорного
решения
.
Замечание
.
Так
как
векторы
условий
,
соответствующие
ненулевым
координатам
опорного
решения
α
=(
α
1
,…,
α
j
,…,
α
n
),
входят
в
каждый
его
базис
,
то
это
опорное
решения
может
иметь
не
один
базис
.
Пример
.
Дана
КЗЛП
f(X) = 3x
1
– x
2
+ x
4
( min ),
2x
1
– x
2
+ x
3
– x
4
=3,
3x
1
+ 2x
2
– x
3
+ 3x
4
=2,
x
j
≥
0, j = 1, 2, 3, 4.
и
ее
опорное
решение
α
= ( 1, 0, 1, 0).
Ненулевым
координатам
опорного
решения
соответствуют
векторы
А
1
,
А
3
системы
векторов
условий
данной
задачи
.
Разрешив
методом
Гаусса
систему
векторов
условий
рассматриваемой
задачи
относительно
векторов
А
1
,
А
3
А
1
А
2
А
3
А
4
А
1
А
2
А
3
А
4
А
1
А
2
А
3
А
4
2 –1
1
–1
2 –1
1 –1
0 –7/5 1 –7/5
3 2 –1 3
5
1 0 2 1 1/5 0 2/5
видим
,
что
эти
векторы
А
1
,
А
3
образуют
базис
системы
векторов
условий
данной
задачи
и
по
определению
являются
базисом
данного
опорного
решения
.
Свойства
базисов
опорного
решения
Свойство
1
.
Любому
опорному
решению
канонической
задачи
линейного
программирования
соответствует
,
по
крайне
мере
,
один
базис
системы
векторов
условий
этой
задачи
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
60
▲
Пусть
вектор
α
= ( 0, …,0,
α
i1
, 0,…, 0,
α
i2
, 0, …, 0,
α
il
, 0, …, 0 )
является
опорным
решением
канонической
задачи
линейного
программирования
(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.
где
α
i1
>0 ,
α
i2
>0, …,
α
i
> 0.
Тогда
по
определению
в
системе
векторов
условий
задачи
(1) – (3)
векторы
A
i1
, A
i2
, …, A
i
,
соответствующие
ненулевым
координатам
данного
опорного
решения
,
образуют
линейно
независимую
систему
векторов
,
которую
можно
дополнить
до
базиса
всей
системы
векторов
условий
данной
задачи
.
Пусть
этим
базисом
будет
система
из
векторов
A
i1
, A
i2
,
… A
i
A
i
+1
, , …, A
ir
.
Тогда
небазисным
векторам
из
системы
векторов
условий
задачи
(1) – (3)
соответствуют
нулевые
координаты
опорного
решения
и
по
определению
векторы
A
i1
, A
i2
, …, A
ir
образуют
базис
опорного
решения
α
.
■
Следствие
.
Число
ненулевых
координат
у
любого
опорного
решения
α
канонической
задачи
линейного
программирования
не
превышает
r = rang{ A
1
,
…, A
n
} –
ранга
системы
векторов
условий
этой
задачи
.
▲
Выше
было
доказано
,
что
любому
опорному
решению
КЗЛП
соответствует
хотя
бы
один
базис
системы
векторов
условий
КЗЛП
.
Число
векторов
в
любом
базисе
системы
векторов
условий
КЗЛП
совпадает
с
рангом
этой
системы
.
По
определению
базиса
опорного
решения
,
все
координаты
опорного
решения
α
,
соответствующие
не
базисным
векторам
системы
векторов
условий
КЗЛП
,
равны
нулю
.
Следовательно
,
ненулевых
координат
у
опорного
решения
α
не
более
,
чем
r
.
■
Определение
.
Опорное
решение
канонической
задачи
линейного
программирования
(1) – (3)
называется
невырожденным
,
если
число
его
ненулевых
координат
равно
рангу
системы
векторов
условий
рассматриваемой
задачи
.
Если
же
число
ненулевых
координат
опорного
решения
меньше
ранга
системы
векторов
условий
рассматриваемой
канонической
задачи
линейного
программирования
,
то
это
опорное
решение
называется
вырожденным
.
Свойство
2
.
Невырожденному
опорному
решению
канонической
задачи
линейного
программирования
(1) – (3)
может
соответствовать
только
один
базис
системы
векторов
условий
данной
задачи
.
▲
Пусть
вектор
α
= ( 0, …, 0,
α
i1
, 0,…, 0,
α
i2
, 0, …, 0,
α
ir
, 0, …, 0 ) –
невырожденное
опорное
решение
КЗЛП
,
у
которого
по
определению
α
i1
>0,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.