Составители:
Рубрика:
82
A
j
= [a
1j
,а
2j
. . .,а
тj
] — векторы условий;
B = [b
1
, b
2
, . . ., b
m
] — вектор ограничений.
Будем считать, что ранг системы уравнений (2.2.82) равен числу уравнений, т. е.
n
r
=т и что n>m. В таком случае совместная система (2.2.82) является неопределенной. Мы
знаем, что неопределенная система линейных уравнений имеет конечное число базисных
решений. Напомним, что всякое базисное решение связано с некоторым базисом векторов
условий A
j
.
В базисном решении ненулевые значения неизвестных соответствуют
некоторому линейно независимому набору векторов условий A
j
.
Всякое неотрицательное базисное решение системы ограничений (2.2.82)
канонической задачи линейного программирования называется опорным решением, или
опорным планом.
Докажем следующую очень важную для линейного программирования теорему.
Теорема 4
. (об опорных решениях). Если каноническая задача линейного
программирования имеет оптимальное решение, то существует по крайней мере одно
оптимальное опорное решение.
П о я с н е н и е. Если каноническая задача линейного программирования имеет
единственное решение, то это решение должно быть опорным решением. Если же задача
линейного программирования имеет бесчисленное множество решений, то среди этих
решений найдется хотя бы одно опорное решение.
Д о к а з а т е л ь с т в о. Всякое допустимое решение задачи (2.2.81) — (2.2.82) есть
неотрицательный вектор Х=[х
1
, х
2
, . . ., х
n
], удовлетворяющий векторному соотношению
(2.2.82). Пусть вектор Х'=[х
'
1
, х
2
', . . ., х
'
s
, 0, . . ., 0] — оптимальное решение, в котором
первые s координат х
'
1
, х
2
', . . ., х
'
s
положительны, а остальные равны нулю. Далее, если
вектор
[
]
00
2
0
1
0
,...,,
m
yyyY = какое-нибудь оптимальное решение двойственной задачи, то,
по теореме равновесия, имеем
A
j
Y
0
= c
j
, j=1, 2,..., s, (2.2.83)
где A
j
векторы условий задачи.
Если векторы условий А
1
, A
2
,..., A
s
, соответствующие положительным координатам
х
'
1
, х
2
', . . ., х
'
s
вектора X', независимы (s ≤ m), то вектор Х'=[х
'
1
, х
2
', . . ., х
'
s
, 0, . . ., 0] уже
будет определять опорное решение.
Предположим теперь, что векторы А
1
, A
2
,...,A
s
линейно зависимы. Тогда
существуют такие числа
λ
j
, не все равные нулю, что
.0...
2211
=+++
ss
AAA
λλλ
(2.2.84)
Мы можем при этом считать некоторые
λ
К
положительными (в противном случае
достаточно умножить равенство (2.2.84) на –1).
Пусть число Θ = макс.
'
/
kk
x
λ
. Изменяя, если это нужно, нумерацию, мы можем
считать Θ= .0/
'
>
ss
x
λ
Так как вектор Х'=[х
'
1
, х
2
', . . ., х
'
s
, 0, . . ., 0] является неотрицательным решением
уравнения (2.2.82), то имеем тождественно
....
'
2
'
21
'
1
BAxAxAx
ss
=+++ (2.2.85)
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
