Экономический смысл угловой точки

Теорема об оптимальном решении ЗЛП.

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

А I-ресурс

В

О

Е

II-ресурс

В точке А оба ресурса расходуются полностью.

В угловых точках полностью расходуется некое количество ресурса (на плоскости 2), либо расходуется ресурс полностью и не выпускается продукт (точка В – полностью 1 ресурс, не выпускается 2-ой продукт).

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

Легко доказать, что угловых точек – конечное число.

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

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

Определение: точка в любом пространстве для выпуклового множества линейного многогранника называется угловой, если она не может быть внутренней точкой любого отрезка этого множества.

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