4.3. Теорема о достижении линейной функцией
экстремума в угловых точках
Теорема 4.3.1. Целевая функция задачи ЛП достигает экстремума в угловой точке множества допустимых решений , причём если целевая функция достигает экстремума в нескольких угловых точках множества допустимых решений, то она также достигает экстремума в любой выпуклой линейной комбинации этих точек.
Доказательство.
Будем считать, что решается задача
на максимум целевой функции, т.е.
при системе ограничений (1.1.4). Доказательство
проведём методом от противного.
Предположим, что
достигается
во внутренней точке
многогранника
,
т.е.
,
.
Тогда по теореме 4.2.1
,
и
,
где
угловые
точки многогранника
.
Найдём
.
Получено противоречие. Следовательно, является угловой точкой области допустимых решений.
Докажем
второе утверждение теоремы. Пусть
угловые точки
,
,
…,
являются оптимальными решениями, т.е.
и
.
Найдём значение целевой функции для
некоторой выпуклой линейной комбинации
этих угловых точек:
,
,
,
.
,
т.е. решение
также является оптимальным.
4.4. Опорное решение задачи линейного программирования,
его взаимосвязь с угловыми точками.
Рассмотрим каноническую задачу ЛП в векторной записи (см.(2.1.2)):
,
,
(4.4.1)
.
Определение
4.4.1. Опорным решением задачи ЛП
называется такое допустимое решение
,
для которого соответствующие положительным
координатам
векторы
,
,…,
в (4.4.1) линейно независимы.
Число
отличных от нуля координат опорного
решения не может быть больше ранга
системы векторов условия (т.е. числа
линейно независимых уравнений системы
ограничений). В дальнейшем будем считать,
что система ограничений состоит из
линейно независимых уравнений, т.е.
.
Если число отличных от нуля координат
опорного решения равно
,
то оно (решение) называется невырожденным,
в противном случае (меньше
вырожденным.
Определение 4.4.2. Базисом опорного решения называется базис системы векторов условия задачи (4.4.1), в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.
Приведём без доказательства две теоремы о взаимосвязи опорных решений и угловых точек множества допустимых решений.
Теорема 4.4.1. Любое опорное решение является угловой точкой области допустимых решений.
Теорема 4.4.2. Любая угловая точка области допустимых решений является опорным решением.
Доказательства теорем 4.4.1 и 4.4.2 проводятся методом от противного (см. [3], с.537-539).
5. Симплексный метод решения задач
линейного программирования
Симплексный метод – это метод целенаправленного перебора опорных решений задачи ЛП. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что его не существует. Основное содержание метода состоит в следующем:
1. Указать способ нахождения начального опорного плана.
2. Указать способ перехода от одного опорного плана к другому, на котором значение целевой функции ближе к оптимальному.
3. Задать критерии, которые позволяют своевременно прекратить проверку решений на оптимальность или сделать заключение об отсутствии оптимального решения.