 |
 |
 |
 |
|
 |
 |
15
комбинации угловых точек х¹, х²,..., x
m
Так как х* — точка максимума, то для любого х ? D сх*
?
сх. Функция f(x) — линейная, поэтому
cледовательно,
где x® — угловая точка, удовлетворяющая условию
Из (1.10) видно, что сх*
?
сх®.
В то же время справедливо обратное неравенство: сх* ? сх®. Откуда
следует, что сх* = сх®, т. е. существует по крайней мере одна угловая точка
х®, в которой целевая
функция принимает максимальное значение.
Теорема 1.2. Если целевая функция f принимает максимальное значение в нескольких точках
множества D, то она принимает это же значение в любой точке, являющейся их выпуклой
комбинацией.
Доказательство.
Пусть максимальное значение функции f достигается в точках ??¹, ??²,...,[?
s
, т. е. сх
~i
=f*,
i?
l:s.
Рассмотрим произвольную выпуклую комбинацию этих точек
Найдем значение целевой функции в точке х*
Итак, для произвольной выпуклой комбинации х* точек ??¹, ??²,...,x
~s
справедливо равенство
1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП
1.3.1. Векторная форма записи КЗЛП и ее применение. Рассмотрим каноническую задачу
линейного программирования
Обозначим через а
j
столбцы матрицы А и будем рассматривать их как векторы пространства
R
m
.
Тогда каждому допустимому плану КЗЛП —
n-мерному вектору х
— соответствует неотрицательная