Линейное программирование (Графический метод. Симплексный метод) (стр. 5 )

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

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

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

Пример На плоскости выпуклыми множествами являются отрезок, прямая, круг, треугольник, полуплоскость и вся плоскость.

Множества, представленные на рис.1, являются выпуклыми.

В

А

 

Рисунок 1 – Выпуклые множества

Множества, изображенные на рис.2, выпуклыми не являются.

 

В

В

А

А

Рисунок 2 – Множества точек, которые не являются выпуклыми

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

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

Доказательство:

Рассмотрим систему ограничений задачи линейного программирования в канонической форме

Систему линейных уравнений представим в матричной форме. Обозначим матрицы следующим образом: , , . В новых обозначениях система линейных уравнений примет вид АХ=В.

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

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

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

Для этого в уравнение АХ=В, вместо матрицы , подставим матрицу и получим . Рассмотрим выполнение этого равенства

.

Действительно, матрица также является решением системы линейных уравнений. Компоненты решения являются линейной комбинацией неотрицательных компонент решений и с коэффициентами и (1-). По определению о выпуклой линейной комбинации точек, коэффициенты и (1-) также являются неотрицательными. Следовательно, решение есть допустимое решение задачи линейного программирования и множество допустимых решений задачи линейного программирования является выпуклым.

ч. т.д.

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

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

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

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

,