Некоторые важные теоремы

Теорема 1. Множество всех допустимых решений задачи ЛП выпукло.

€ Надо показать, что если , – допустимые решения задачи ЛП, то и ,тоже допустимое решение.

Имеем: ■

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

€ Пусть ОДР задачи ЛП ограничена и имеет угловые точки.

Пусть - оптимальное решение.

Имеем: (1) для любой точки из ОДР.

Пусть - не угловая точка (она м.б. представлена в виде выпуклой линейной комбинации).

Тогда имеем:

и

Среди найдем максимальное:

Тогда: (2)

Из (1), (2) имеем: и - угловая точка.

Следовательно, существует угловая точка , в которой целевая функция достигает максимального значения.

Если среди величин имеются равные, т.е. , то для точек образуем выпуклую линейную комбинацию .

На основании предыдущей теоремы следует, что .

Определим , т.е. ■

Дата добавления: 2014-01-13