3. Критерий угловой точки множества.
Рассмотрим
задачу в канонической форме:
(1),
(2).
Опр.
Угловой точкой мн-ва
называется точкой
которая не может быть представлена как
точка отрезка
для любых
.
Т.(Критерий
угловой точки): Обозначим
через
столбцы матрицы А, тогда основные
ограничения в системе (2) можно записать
в виде:
.
Предположим, что матрица А в системе
(2) имеет
,т.е.
матрица А ненулевая. Для того, чтобы
точка
была угловой точкой – G
необходимо и достаточно, чтобы существовали
,
что справедливо равенство: (3)
,
если
и
– ЛНЗ.
Док-во:
Необ.: Пусть
– угловая точка этого мн-ва. а)
.
Т.к. м-ца А в соотнош. (2) невырождена, то
существует r
ЛНЗ векторов
,
то выполнено
.
т.е. (3) справедливо; б)
тогда основные ограничения в (2) превратятся
в равенство:
(4).
Рассм. р-во
(5).
Построим точки
и
след. образом:
т.к.
,
то
к
равенству (4) прибавим и отнимем р-во (5)
умноженное на
получим что выполняются равенства:
,
т.е
.
Легко видеть
, но х – угловая точка след-но
след-но
в (5), т.е. вектора
– ЛНЗ след-но
Если
,
то (3) – доказано, если
,
то к векторам
можно добавить вектора
так, чтобы
– ЛНЗ, тогда (3) примет вид:
.
Достат.:
пусть для точки
справедливо (3):
– ЛНЗ, где
.
Предположим, что
,
что
(6).
Покажем, что (6) возможно только при
.
Рассм. нулевую координату точки х:
,т.е
.
Докажем (6) для тех координат, которые
больше 0. Положительными координатами
точки х могут быть только те, у которых
индекс
.
Пусть
Случай когда
или
не исключается, тогда система основных
ограничений из (2) преобразуется к виду:
.
Докажем, что
,
если
.
Точки
было доказано, что
,
когда
след-но
и
.
Вектора
– ЛНЗ, а разложение произвольного
вектора пространства по ЛНЗ-векторам
является единственным, след-но
для строго положительных координат.
4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
Опр.
Система векторов
входящие в равенство
,
если
называется базисом угловой точки х,
координаты
называются базисными, остальные
координаты – небазисными.
Опр. Если все базисные координаты точки х строго больше 0, тогда точка х называется невырожденной.
Следствие. Если точка х – невырожденная угловая точка, то для нее существует единственный базис. Вырожденная угловая точка может обладать несколькими базисами.
Пример:
– невырожденная
угловая точка, проверим это.
,
,
где
,
.
– вырожденная
угловая точка, так как при рассмотрении
равенства
,
где
точка
– не является угловой точкой, так как
.
5. Связь между переменными злп.
Пусть
,
.
Из системы осн. ограничений можно удалить
ЛЗ ур-я, тогда
.
Если
,
то система
им. единств. решение. Если это реш-е не
удовл. прямым огр-ям, то
,
иначе
.
Рассм
.
Найдена угл. т-ка
,
- базисные компоненты,
- тоже, иначе м. перенумеровать.
- ЛНЗ. Обозначения:
Умножим
на
:
Т.к.
у – угловая, то
,
т.е.
.
Рав-во
м. привести в виду
.
Из определения В
(*)
примет вид:
.
Из (3) выражаем
-
(4), обозначаем
(3)
перепишем в виде:
(5)
(3), (4), (5) – зависимость между базисными и небазисными переменными.
6 . Ф-ла приращения целев ф-ии для ЗЛП.
Рассм
знач целев ф-ии в некот точке
,
т.е.
,
где
Получим
формулу (1)
-
ф-ла приращ целев ф-ии,
В-р
в-р оценок целевой ф-ии
Замеч:
Величина
имеет смысл и для
;
действительно,
- единичный в-р
Замеч:
Вел-на
полностью опр-ся коэф-ми м-цы
,
в-ра
и базисом угловой точки
,
при этом не зав-т от в-ра ресурсов
Замеч:
Из (1) виден
физический смысл оценок
.
Величины
представляют собой взятую с обратным
знаком скорость зменения целев ф-ии при
изменении i-ой
небазисной переменной.