ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1089
Скачиваний: 2
61
α
i2
>0, …,
α
ir
> 0,
где
r = rang{ A
1
, …, A
n
},
и
в
соответствующий
ему
базис
системы
условий
КЗЛП
должны
входить
векторы
условий
КЗЛП
– A
i1
, A
i2
,
…, A
ir
.
Так
как
ранг
системы
векторов
условий
КЗЛП
совпадает
с
количеством
ненулевых
координат
данного
опорного
решения
,
то
векторы
A
i1
, A
i2
, …, A
ir
могут
образовывать
только
единственный
базис
,
соответствующий
рассматриваемому
опорному
решению
.
■
Утверждение
о
том
,
что
вырожденному
опорному
решению
КЗЛП
может
соответствовать
несколько
базисов
системы
векторов
условий
КЗЛП
,
подтверждается
следующим
примером
.
Пример
.
Дана
КЗЛП
:
f(X) = x
1
+ x
2
( min
),
x
1
+ x
2
– 2x
3
+ x
4
=1,
x
1
– x
2
+ 3x
3
– x
4
=1,
x
j
≥
0, j = 1, 2, 3, 4.
и
дано
вырожденное
опорное
решение
α
=( 1, 0, 0. 0)
этой
задачи
.
Очевидно
,
что
вектор
А
1
,
соответствующий
ненулевой
координате
данного
опорного
решения
,
образует
линейно
независимую
систему
векторов
и
,
следовательно
,
может
быть
дополнен
до
любого
из
базисов
системы
векторов
условий
,
соответствующего
данному
опорному
решению
,
например
,
либо
до
базиса
А
1
,
А
2
,
либо
до
базиса
А
1
,
А
3
,
либо
до
базиса
А
1
,
А
4
.
Свойство
3
.
Один
и
тот
же
базис
системы
векторов
условий
канонической
задачи
линейного
программирования
(1) – (3)
не
может
являться
базисом
двух
различных
опорных
решений
этой
задачи
.
▲
Предположим
,
что
базис
A
1
, …, A
r
системы
векторов
условий
КЗЛП
(1) – (3)
является
базисом
опорного
решения
:
α
’
=(
α
’
1
,…,
α
’
r
,
α
’
r+1
,…,
α
’
n
)
и
опорного
решения
α
”
=(
α
”
1
,…,
α
”
r
,
α
”
r+1
,…,
α
”
n
) ,
у
которых
α
’
r+1
= 0,…,
α
’
n
= 0
и
α
”
r+1
= 0,…,
α
”
n
= 0.
Следовательно
,
α
’
=(
α
’
1
,…,
α
’
r
, 0,…, 0 )
и
α
”
=(
α
”
1
,…,
α
”
r
, 0,…, 0 ).
По
определению
опорного
решения
векторы
α
’
=(
α
’
1
, …,
α
’
r
,0, …,
0 )
и
α
”
=(
α
”
1
, …,
α
”
r
, 0,…, 0 )
являются
допустимыми
решениями
КЗЛП
(1) –
(3)
и
,
следовательно
,
являются
решением
системы
линейных
уравнений
(2).
Поэтому
,
подставляя
указанные
векторы
в
систему
линейных
уравнений
(2) ,
получаем
:
А
1
α
’
1
+
А
2
α
’
2
+…+
А
r
α
’
r
= B
и
А
1
α
”
1
+
А
2
α
”
2
+…+
А
r
α
”
r
= B.
После
вычитания
второго
соотношения
из
первого
,
получим
:
А
1
(
α
’
1
–
α
”
1
) +
А
2
(
α
’
2
–
α
”
2
)+…+
А
r
(
α
’
r
–
α
“
r
) =
Ө
.
Из
этого
соотношения
с
учетом
линейной
независимости
базисных
векторов
A
1
, …, A
r
,
имеем
:
α
’
1
–
α
”
1
= 0,
α
’
2
–
α
”
2
= 0, …,
α
’
r
–
α
r
= 0.
то
есть
α
’
1
=
α
”
1
,
α
’
2
=
α
”
2
, …,
α
’
r
=
α
r
.
Следовательно
,
один
и
тот
же
базис
системы
условий
КЗЛП
(1) – (3)
является
базисом
только
одного
опорного
решения
,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
62
т
.
к
.
α
’ =
α
”.
■
Следствие
.
Каноническая
задача
линейного
программирования
(1) – (3)
имеет
конечное
число
различных
опорных
решений
.
▲
Любому
опорному
решению
задачи
(1) – (3)
соответствует
не
менее
одного
базиса
системы
векторов
условий
задачи
.
Один
и
тот
же
базис
системы
векторов
условий
рассматриваемой
задачи
не
может
быть
базисом
двух
различных
опорных
решений
этой
задачи
.
Следовательно
,
число
опорных
решений
не
превосходит
числа
базисов
системы
векторов
условий
задачи
(1) –
(3).
В
то
же
время
,
число
базисов
любой
системы
из
n m-
мерных
векторов
конечно
и
не
превосходит
числа
сочетаний
из
n
по
m ,
то
есть
,
!
)!
(
!
m
m
n
n
c
m
n
.
Следовательно
,
число
опорных
решений
канонической
задачи
линейного
программирования
то
же
конечно
.
■
Свойство
4
.
Базис
системы
векторов
условий
канонической
задачи
линейного
программирования
(1) – (3)
является
базисом
некоторого
опорного
решения
этой
задачи
тогда
и
только
тогда
,
когда
вектор
ограничений
В
системы
линейных
уравнений
(2)
линейно
выражается
через
базисные
векторы
с
неотрицательными
коэффициентами
.
▲
Необходимость
.
Пусть
A
i1
, A
i2
, …, A
ir
базис
системы
векторов
условий
задачи
(1) – (3)
является
базисом
опорного
решения
α
= (
α
1
, …,
α
j
, …,
α
n
)
этой
задачи
.
Из
определения
базиса
опорного
решения
следует
,
что
α
i
= 0
для
любых
i
≠
i
1
, i
2, …,
i
r
, .
По
определению
,
опорное
решение
является
допустимым
решением
задачи
(1) – (3),
то
есть
оно
удовлетворяет
ограничениям
(3)
α
i1
≥
0 ,
α
i2
≥
0 , …,
α
ir
≥
0
и
является
решением
системы
линейных
уравнений
(2),
то
есть
обращает
ее
в
точное
числовое
равенство
вида
А
i1
α
i1
+
А
i2
α
i2
+…+
А
ir
α
ir
= B.
Следовательно
,
вектор
ограничений
В
линейно
выражается
через
базисные
векторы
A
i1
, A
i2
, …, A
ir
с
неотрицательными
коэффициентами
.
Достаточность
.
Пусть
A
i1
, A
i2
, …, A
ir
базис
системы
векторов
условий
задачи
(1) – (3)
и
вектор
ограничений
В
представим
в
виде
А
i1
α
i1
+
А
i2
α
i2
+…+
А
ir
α
ir
= B ,
где
α
i1
≥
0 ,
α
i2
≥
0 , …,
α
ir
≥
0.
Рассмотрим
вектор
α
=( 0, …, 0,
α
i1
, 0, …,
0,
α
i2
, 0, …, 0,
α
ir
, 0, …, 0 ).
Очевидно
,
что
этот
вектор
удовлетворяет
условию
(3)
и
является
решением
системы
уравнений
(2).
Следовательно
,
вектор
α
является
допустимым
решением
задачи
(1) – (3),
при
чем
его
ненулевым
координатам
соответствуют
векторы
из
набора
базисных
векторов
A
i1
, A
i2
, …,
A
ir
.
Может
случиться
,
что
среди
координат
α
i1
,
α
i2
, …,
α
ir
окажутся
такие
,
которые
равны
нулю
(
например
,
если
вектор
α
является
вырожденным
).
В
этом
случае
остальным
ненулевым
координатам
вектора
будут
соответствовать
некоторая
,
часть
базисных
векторов
,
которая
будет
,
очевидно
,
линейно
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
63
независимой
.
Таким
образом
,
вектор
α
по
определению
является
опорным
решением
задачи
(1) – (3).
Кроме
того
,
векторы
условий
данной
задачи
,
не
попавшие
в
набор
базисных
векторов
A
i1
, A
i2
, …, A
ir
,
будут
соответствовать
нулевым
координатам
рассматриваемого
вектора
α
.
Следовательно
,
по
определению
,
набор
базисных
векторов
A
i1
, A
i2
, …, A
ir
системы
векторов
условий
задачи
(1) – (3)
является
базисом
опорного
решения
α
.
■
Замечание
.
На
основании
свойства
4
можно
найти
все
опорные
решения
канонической
задачи
линейного
программирования
,
выполнив
следующие
действия
:
найти
все
базисы
системы
векторов
условий
данной
задачи
;
по
каждому
из
найденных
базисов
разложить
вектор
ограничений
В
и
выбрать
среди
них
разложение
с
неотрицательными
коэффициентами
;
для
каждого
выбранного
разложения
вектора
В
с
неотрицательными
коэффициентами
выписать
опорное
решение
исходной
задачи
.
Пример
.
Найти
все
опорные
решения
КЗЛП
:
f(X) = x
1
+ 2x
2
–
х
3
( min ),
x
1
+ x
2
– x
3
=3,
,
2x
1
+ x
2
+ x
3
=3
x
j
≥
0, j=1, 2, 3, 4.
Найдем
все
базисы
системы
векторов
условий
данной
задачи
,
разрешив
ее
относительно
различных
пар
векторов
,
входящих
в
эту
систему
,
а
именно
:
А
1
А
2
А
3
В
А
1
’
А
2
’
А
3
’
В
’
А
1
’’
А
2
’’
А
3
’’
В
’’
1
2 –1 3
1 2 –1 3
1 0 1 1
2 1 1 3
0
–3
3 –3
0 1
–1
1
А
1
’
’’
А
2
’’’
А
3
’’’
В
’’’
А
1
’’’’
А
2
’’’’
А
3
’’’’
В
’
’
’’
1
1
0
2
1 1 0 2
0 –1 1 –1
1 0 1 1
Получили
три
базиса
системы
векторов
условий
данной
задачи
:
А
1
’’
,
А
2
’’
;
А
1
”’
,
А
3
”’
и
А
2
’’’’
,
А
3
’’’’
и
соответствующие
им
векторы
решений
системы
уравнений
:
α
’’
=(1,1,0),
α
’’’
=(2,0,1),
α
’’’’
=(0,2,1),
из
которых
опорными
решениями
данной
задачи
будут
векторы
α
’’
=(1,1,0),
α
’’’
=(2,0,1).
■
Ответьте
на
вопросы
1.
Какое
количество
базисов
может
иметь
система
векторов
условий
канонической
задачи
линейного
программирования
?
2.
Дайте
определение
базиса
опорного
решения
канонической
задачи
линейного
программирования
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
64
3.
Сколько
базисов
системы
векторов
условий
канонической
задачи
линейного
программирования
может
соответствовать
опорному
решению
этой
задачи
?
4.
Сколько
ненулевых
координат
может
иметь
опорное
решение
канонической
задачи
линейного
программирования
?
5.
Сколько
нулевых
координат
может
иметь
опорное
решение
канонической
задачи
линейного
программирования
?
6.
Дайте
определение
ранга
системы
векторов
.
7.
Дайте
определение
невырожденного
и
вырожденного
опорного
решения
.
8.
Какое
максимальное
количество
базисов
системы
векторов
условий
канонической
задачи
линейного
программирования
может
соответствовать
вырожденному
опорному
решению
?
9.
Какое
максимальное
количество
базисов
системы
векторов
условий
канонической
задачи
линейного
программирования
может
соответствовать
невырожденному
опорному
решению
?
Решите
самостоятельно
Задача
1.
Образуют
ли
векторы
A
1
, …, A
r
базис
опорного
решения
α
для
системы
условий
канонической
задачи
линейного
программирования
:
1.1.
x
j
≥
0, j= 1, 2, 3, 4.
α
= (1,0,0, 1);
А
1
,
А
4
;
А
2
,
А
4
.
1.2.
x
j
≥
0, j= 1, 2, 3, 4.
α
= (1,0,0, 0);
А
1
,
А
2
;
А
1
,
А
3
;
А
1
,
А
4
;
А
2
,
А
3
.
1.3.
x
j
≥
0, j= 1, 2, 3, 4.
α
= (0,1,0, 0);
А
1
,
А
2
,
А
3
;
А
2
,
А
3
,
А
4
;
А
1
,
А
3
,
А
4
.
Задача
2.
Найти
все
базисы
данного
опорного
решения
:
2.1.
x
1
+ x
2
+ x
3
+ x
4
=1,
x
1
– x
2
+ x
3
– x
4
=1,
x
j
≥
0, j=1, 2, 3, 4.
α
= (1,0,0, 0);
2.2.
x
1
+ 2x
2
– x
3
+ x
4
=2,
2x
1
– x
2
+ 3x
3
– x
4
=1,
x
1
+ 2x
2
– x
3
+ x
4
=1,
x
1
– x
2
+ 2x
3
+ x
4
=1,
x
1
+ 2x
2
– x
3
+ x
4
=2,
x
1
– 3x
2
+ x
3
+ x
4
=– 3,
2x
1
+ x
2
– x
3
+ 2x
4
=1,
x
1
+ x
2
+ x
3
=1
x
1
–
2x
3
=0
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
65
x
j
≥
0, j= 1, 2, 3.
α
= (1/2,0,1/2); .
2.3.
x
j
≥
0, j=1, 2, 3, 4.
α
= (1,0,1, 0);
2.4.
x
j
≥
0, j=1, 2, 3, 4.
α
= (0,1,1, 0).
Задача
3.
Является
ли
базис
системы
векторов
условий
данной
канонической
задачи
линейного
программирования
базисом
некоторого
опорного
решения
этой
задачи
?
3.1.
x
j
≥
0, j=1, 2, 3.
А
2
,
А
3.
3.2.
x
j
≥
0, j= 1, 2, 3.
А
1
,
А
3
.
3.3.
x
j
≥
0, j=1, 2, 3, 4.
А
2
,
А
3.
3.4.
x
j
≥
0, j=1, 2, 3, 4.
А
1
,
А
4.
3.5.
x
1
– x
2
+ x
3
+ x
4
=2,
2x
1
+ x
2
– x
3
– x
4
=1,
x
1
+ x
2
+ 2x
3
– x
4
=3,
x
1
+ 2x
2
– x
3
+ x
4
=1
2x
1
– x
2
+ x
3
– x
4
=0,
x
1
+ 3x
2
– x
3
+ x
4
=2,
x
1
+ x
2
+ x
3
=2,
–x
1
–
х
2
+ x
3
=2,
x
1
+ x
2
+ x
3
=1,
2x
1
–
х
2
– 3x
3
=2,
x
1
+ x
2
+ 3x
3
+ 2x
4
=2,
x
1
+ x
2
+ x
3
– x
4
=1,
x
1
+ x
2
+ 3x
3
+ 2x
4
=2,
x
1
+ x
2
+ x
3
– x
4
=1,
x
1
– x
2
+ x
4
+
х
5
+ 4
х
6
=1,
x
2
– x
3
+ 7
х
5
+ 2
х
6
=1,
x
1
+ x
2
–
х
6
=1,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.