Балашовский филиал

4. Геометрическая интерпретация ЗЛП

Рассмотрим задачу линейного программирования по нахождению максимума (минимума) целевой функции L(X) = c₁x₁ +...+ c_nx_n + c на допустимом множестве , заданном с помощью системы линейных ограничений (нестрогих неравенств или уравнений).
Напомним некоторые определения.
Выпуклой линейной комбинацией элементов X₁,…, X_k из пространства Rⁿ называют элемент X этого же пространства вида
X =₁X₁+…+_kX_k, где все _i  0 и ₁+…+_k = 1.
М
ножество M  Rⁿ называется выпуклым, если M =  или вместе
с любыми двумя элементами X₁ и X₂ содержит и их произвольную выпуклую линейную комбинацию. Геометрически выпуклость множества M  Rⁿ означает, что вместе с любыми двумя своими точками оно содержит
и весь отрезок, их соединяющий (Error: Reference source not found).
Замечание 5. Такая геометрическая интерпретация выпуклости объясняется тем, что любая точка отрезка является выпуклой линейной комбинацией его концов. Действительно, если точки X, X₁, X₂ определяются в Rⁿ соответственно координатами (x₁,…, x_n), (x₁₁,…, x_1n), (x₂₁,…, x_2n) и X — произвольная точка отрезка X₁X₂, то x₁ = x₁₁+(1)x₂₁,…, x_n = x_1n +
+ (1)x_2n, 0    1. В сокращенном виде это запишется так:
X = X₁+ (1)X₂, 0    1.
Примерами выпуклых множеств в R³ служат куб, шар, точка. Примером выпуклого множества в Rⁿ может служить плоскость. Еще два примера выпуклых множеств в Rⁿ описывает