SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Фундаментальная теорема о существовании оптимального решения ЗЛП (доказательство для ограниченной области).


Формулировка:

Если область допустимых решений не пустая и целевая функция ограничена сверху на максимум или снизу на минимум, то всегда существует оптимальное решение, и при этом оно обязательно совпадает с одним из опорных решений.

Проведем доказательство теоремы для ограниченной области.

Если область допустимых решений ограничена и целевая функция непрерывна, то она (функция) в этой области достигает максимума или минимума, то есть оптимальное решение существует.

При этом в ограниченной области имеется конечное число опорных решений.

Число опорных, или угловых точек вполне конкретно. Пусть их 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.