3. Основные свойства и теоремы злп
3.1. Применение классического аппарата математического анализа для решения злп
[С.А. Ашманов Линейное программирование, стр.35]
Первым шагом в исследовании ЗЛП, естественно, является попытка применить для отыскания решения классический аппврат математического анализа и высшей алгебры.
3.1.1
Пусть X- замкнутое
и ограниченное множество в
,
f - непрерывная функция на X. Тогда
глобальное решение задачи f(x)max,
xX
существует.
Непрерывная функция на f(x) достигает на замкнутом ограниченном множестве своего максимума во внутренней или граничной точке.
f f
X
X
f - непрерывная функция на X f – не является непрерывной функцией на X
f
(в точке
имеем разрыв)
X
f – не является непрерывной функцией на X (в точке имеем разрыв)
Теорема Вейерштрасса применима т. к первому случаю.
3.1.2.
Рассмотрим простейшую задачу нахождения максимума дифференцируемой функции одной переменной на отрезке:
Алгоритм, который дает для решения этой задачи математический анализ, таков:
найти производную
;решить уравнение
;
пусть
те решения этого уравнения, которые
принадлежат отрезку
вычислить значения
и выбрать из них наибольшее.
Сразу видно, что в этом простом случае могут возникнуть осложнения. Еще сложнее дело обстоит для функций нескольких переменных.
3.1.3.
Пусть
–
замкнутое и
ограниченное множество,
,
–функция n
переменных, дифференцируемая на множестве
.
Найти максимум функции на множестве :
Что рекомендует в этом случае классический анализ?
Вспомним сначала основные положения математического анализа для этого случая.
значение функции
в окрестности
точки
растет быстрее всего, если в качестве
вектора направления выбрать градиент
функции
в точке
.
Вектор
называется градиентом
функции
в точке
и обозначается
(i-ая
компонента вектора равна значению
частной производной
по
в точке
).
Если в достигается локальный максимум функции , то в этой точке нет направления, вдоль которого функция возрастает. Поэтому необходимым условием максимума функции во внутренней точке множества
является равенство градиента
нулевому вектору.
(Именно для
внутренней точки.
Т.к. это утверждение справедливо лишь
в том случае когда из точки
можно хоть немного сдвинуться по любому
направлению, не выходя за пределы
).
Таким образом, для нахождения максимума функции на множестве надо:
найти все внутренние точки множества , в которых градиент равен нулевому вектору, т.е. найти все решения
,
системы уравнений
,
вычислить значения
и значения
во всех
точках
границы
множества
,
а затем выбрать из них максимальное.
Применим эту схему к ЗЛП
.
Градиент ЦФ равен
, он является величиной постоянной, не
зависящей от точки вычисления. Ранее
этот вектор мы назвали нормалью!!!
Следовательно,
если не все
равны нулю одновременно (в противном
случае нет оптимизационной задачи), то
у функции
нет локальных
максимумов.
Значит, ее
максимальное значение достигается на
границе множества
.
Т.о., основные
вычислительные проблемы решения задач
ЛП состоят в определении границы
множества
и организации вычислений значений
функции
в точках этой границы с тем, чтобы найти
среди них наилучшее.
Т.о., наше внимание должно быть сосредоточено на границах многогранного множества , (а граничных точек - бесконечное число)
3.2. Следующая теорема значительно сужает множество возможных точек максимума функции .
Имеем ЗЛП:
,
.
Теорема:
Пусть
допустимое множество
задачи ЛП является многогранником.
Тогда ЦФ
достигает своего максимума в вершине
.
Если функция
принимает максимальное значение более
чем в одной точке, то она достигает того
же значения в любой точке, являющейся
их выпуклой линейной комбинацией.
[Ермольев и др. Мат. Методы ИСО].
Доказательство:
Докажем сначала 1-ю часть теоремы (максимум – в вершине).
Пусть
-
вершины многогранника
,
-
оптимальное решение задачи (согласно
теореме Вейерштрассе оно существует),
т.е.
для
.
Если - вершина, то первая часть теоремы доказана.
Если же точка не является вершиной многогранника Х, то она может быть представлена в виде выпуклой линейной комбинации его вершин:
.
Домножим на
: 
.
Пусть 
- максимальное значение ЦФ, достигаемое
в вершинах.
Если
и
,
то
-
средневзвешенное
меньше максимального значения.
5 ¼ 5 + ¾ 10 10
5 7 ВЛК 10
В силу линейности
функции
и того, что
имеем
.
Но, по предположению,
х*- оптимальное решение, следовательно,
,
то есть существует вершина
,
в которой линейная функция
принимает максимальное значение.
Докажем теперь вторую часть теоремы.
Если принимает максимальное значение более чем в одной точке, то она принимает то же значение в каждой их выпуклой линейной комбинации.
Пусть
принимает максимальные значения в
точках
,
то есть
Возьмем некоторую выпуклую линейную комбинацию этих точек
.
.
Следовательно,
ЦФ
достигает максимального значения
в
произвольной точке х, являющейся выпуклой
линейной комбинацией точек
.
Ч.т.д.
Из этой теоремы вытекает, что множество оптимальных точек не может быть конечным, если оптимальная точка не единственна.