2.4 Теоретические основы методов линейного программирования. Выпуклые множества точек.
2.4 Теоретические основы методов линейного программирования. Выпуклые множества точек.
В основе линейного программирования лежит теория выпуклых множеств. В школьном курсе математики вы рассматривали выпуклые многоугольники. Только напомним.
Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий их.
Среди точек выпуклого множества можно выделить внутренние, граничные и угловые.
Точка множества называется внутренней, если в некоторой ее окрестности содержаться точки только данного множества.
Точка множества называется граничной, если в любой ее окрестности содержаться как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.
Особый интерес в задачах линейного программирования представляют угловые точки.
Точка множества называется угловой (крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
На рис. приведены примеры различных точек:
М – внутренняя;
N – граничная;
А – угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например отрезка АР, она не является внутренней; точка А – внутренняя для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.
Для выпуклого многоугольника угловые точки всегда совпадают с вершинами многоугольника.
Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество, в противном случае множество называется неограниченным.
Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многоугольником, если оно ограничено, и выпуклой многоугольной областью, если оно не ограничено.
Сформулируем без доказательства 2 теоремы, которые имеют отношение к поиску решения задачи линейного программирования и опираются на теорию.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым, т.е. представляет собой выпуклый многогранник или выпуклую многогранную область, которые мы в дальнейшем будем называть – многоугольником решений.
Теорема 2. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает экстремальное значение в одной из угловых точек многоугольника решений.
Согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них оптимального, необходимо исследовать конечное число угловых точек многоугольника решений.