П. 2. Свойства выпуклых множеств

Рассмотрим некоторые свойства выпуклых множеств.

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

Свойства выпуклых множеств.

1) Пересечение любой совокупности выпуклых множеств есть выпуклое множество.

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

Точка множества называется внутренней, если существует такая ее окрестность, в которой содержатся только точки данного множества.

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

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

2) Через каждую точку границы выпуклого множества на плоскости проходит по крайней мере одна опорная прямая, имеющая общую точку с границей, но не рассекающая это множество (на рис. 2.1 a, b, c – опорные прямые).

c b a   B G A

Рис. 2.1.

3) Замкнутое выпуклое множество есть пересечение конечного числа замкнутых полупространств.

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

Угловой точкой назовем точку множества, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству. Точки А и В являются угловыми точками множества G.

 

П. 3. Свойства решений задачи линейного программирования

Перед тем, как изложить основные свойства задачи ЛП, изложим основные формы записи общей задачи ЛП.

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

Рассмотрим следующую задачу ЛП.

П р и м е р 2.2. Z = 3 x₁ + 2 x₂ + 3 x₃ ® max.

(*)

Поставим задачу – привести систему неравенств (*) к системе уравнений.

Для этого введем две дополнительные неотрицательные переменные х₄ и х₅. В первом неравенстве для превращения его в равенство переменную добавим, во втором – вычтем. Получим

Будем считать, что новые переменные в целевой функции имеют коэффициенты С₄ = С₅ = 0 и не влияют на нее.

Любую систему ограничений, заданную неравенствами, можно перевести в систему уравнений, если в неравенствах со знаком «£ » прибавить новую переменную, а в неравенствах со знаком «³ » новую переменную отнять.

Задачу ЛП в этом случае можно сформулировать следующим образом:

,

В матричном виде задачу ЛП можно записать следующим образом:

Z = C X ® max (min)

где С = (С₁, С₂, …, С_n) – матрица строка, – матрица столбец переменных, – матрица столбец свободных членов, – матрица системы.

Задачу ЛП можно записать в векторной форме следующим образом

Z = C X ® max (min)

где С Х – скалярное произведение векторов С = (С₁, …, C_n) и Х = (х₁, …, х_n), (j = 1, …, n).

Сформулируем свойства задачи ЛП.

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

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

3) Каждому опорному значению задачи ЛП соответствует угловая точка многогранника и наоборот, каждой угловой точке многогранника соответствует опорное решение задачи ЛП.

Из свойств 1) – 3) следует, что оптимальное решение задачи ЛП, т.е. набор значений (х₁, х₂, …, х_n), следует искать только среди конечного числа опорных решений системы уравнений ограничений.

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

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: