Экономический смысл угловой точки.
Теорема об оптимальном решении ЗЛП.
Если задача линейного программирования имеет оптимальное решение (для ограниченного многогранника всегда), то это решение, либо единственное – угловая точка, либо этих решений бесконечное множество на грани многогранника, среди, которых есть угловые точки. Т.о. всегда среди оптимальных точек, есть угловая.
А I-ресурс
В
О
Е
II-ресурс
В точке А оба ресурса расходуются полностью.
В угловых точках полностью расходуется некое количество ресурса (на плоскости 2), либо расходуется ресурс полностью и не выпускается продукт (точка В – полностью 1 ресурс, не выпускается 2-ой продукт).
Для поиска оптимального решения необходимо проверить угловые точки, они подозрительны на оптимальность.
Легко доказать, что угловых точек – конечное число.
Поиск оптимальной точки из перебора бесконечного множества допустимых точек сводится к перебору конечного числа угловых точек.
Для построения угловых точек задач с двумя переменными – нет никаких проблем, это легко делается на плоскости. Если же задача имеет больше, чем 2 переменные, возникает проблема поиска угловой точки.
Определение: точка в любом пространстве для выпуклового множества линейного многогранника называется угловой, если она не может быть внутренней точкой любого отрезка этого множества.