4.3. Теорема о достижении линейной функцией

экстремума в угловых точках

Теорема 4.3.1. Целевая функция задачи ЛП достигает экстремума в угловой точке множества допустимых решений , причём если целевая функция достигает экстремума в нескольких угловых точках множества допустимых решений, то она также достигает экстремума в любой выпуклой линейной комбинации этих точек.

Доказательство. Будем считать, что решается задача на максимум целевой функции, т.е. при системе ограничений (1.1.4). Доказательство проведём методом от противного. Предположим, чтодостигается во внутренней точкемногогранника, т.е.,. Тогда по теореме 4.2.1,и, гдеугловые точки многогранника. Найдём

.

Получено противоречие. Следовательно, является угловой точкой области допустимых решений.

Докажем второе утверждение теоремы. Пусть угловые точки ,, …,являются оптимальными решениями, т.е.и. Найдём значение целевой функции для некоторой выпуклой линейной комбинации этих угловых точек:,,,.

, т.е. решение также является оптимальным.