SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки Фундаментальная теорема о существовании оптимального решения ЗЛП (доказательство для ограниченной области). Формулировка: Если область допустимых решений не пустая и целевая функция ограничена сверху на максимум или снизу на минимум, то всегда существует оптимальное решение, и при этом оно обязательно совпадает с одним из опорных решений. Проведем доказательство теоремы для ограниченной области. Если область допустимых решений ограничена и целевая функция непрерывна, то она (функция) в этой области достигает максимума или минимума, то есть оптимальное решение существует. При этом в ограниченной области имеется конечное число опорных решений. Число опорных, или угловых точек вполне конкретно. Пусть их 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. |