Фундаментальная теорема о существовании оптимального решения ЗЛП (доказательство для ограниченной области).
Формулировка:
Если область допустимых решений не пустая и целевая функция ограничена сверху на максимум или снизу на минимум, то всегда существует оптимальное решение, и при этом оно обязательно совпадает с одним из опорных решений.
Проведем доказательство теоремы для ограниченной области.
Если область допустимых решений ограничена и целевая функция непрерывна, то она (функция) в этой области достигает максимума или минимума, то есть оптимальное решение существует.
При этом в ограниченной области имеется конечное число опорных решений.
Число опорных, или угловых точек вполне конкретно. Пусть их S.
Перечислим их: , , …, .
Допустим, целевая функция решается на максимум. (Z = (max)).
существует, следовательно, можно записать: Z = (max).
— угловая точка. В этом случае — теорема доказана.
Пусть не совпадает с угловой точкой.
Следовательно, = t1 + t2 + … + ts , где ti 0,
t = 1, 2, …, s и ti = 1.
Zmax = = (t1 + t2 + … + ts ) =
СitiXi = tiZi
где i =1, 2, …, s и где Z — значение целевой функции в одном из опорных решений.
Так как опорных решений конечное число, среди них можно выбрать большее.
Возьмем Zk Zi,
TiZi Ti Zk = Zk Ti = Zk
Zmax Zk, что возможно только если Zmax = Zk.