Общая Постановка задачи линейного программирования

Общая задача линейного программирования (ОЗЛП) может быть сформулирована следующим образом: найти значения переменных Х₁, Х₂,…,Хn, максимизирующие линейную форму

(x₁,x₂,…,x_n)= c₁x₁+…+c_nx_n (3.1)

при условиях

, i= 1,…,m₁ (m₁£m) (3.2)

, i=m₁+1,…,m (3.3)

x_j ³0, j=1,…,p (p£n)

Соотношения (3.2) и (3.3) будем называть соответственно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП).

Значения переменных Хj (j=1,2,…,n) можно рассматривать как компоненты некоторого вектора =(Х₁,Х₂,…,Хn) пространства Еn.

Определение. Планом или допустимым решением задачи линейного программирования будем называть вектор пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.

Множество всех планов задачи линейного программирования (3.1) – (3.3) будем обозначать Р.

Теорема 1.1 Множество планов Р задачи линейного программирования (ЗЛП) есть замкнутое выпуклое множество.

Множество Р может быть как ограниченным, так и неограниченным, кроме того оно может оказаться пустым.

Напомним, что множество точек Р пространства E_n есть выпуклое множество, если вместе с любыми двумя его точками и ему принадлежит и любая выпуклая линейная комбинация этих точек, то есть если , , то и любая точка

, 0 ≤ λ ≤ 1

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

Множество точек =(Х₁,Х₂,…,Хn) пространства E_n, компоненты которых удовлетворяют условию

C₁X₁+ C₂X₂+…+ C_nX_n = b,

называется гиперплоскостью пространства E_n.

Множество точек =(Х₁,Х₂,…,Хn) пространства E_n, компоненты которых удовлетворяют условию

C₁X₁+ C₂X₂+…+ C_nX_n ≤ b (≥b),

называется полупространством пространства E_n.

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

Напомним, что точка выпуклого множества К является крайней, если в К не существует таких точек и , ≠ , что

, при некотором .

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

Определение. План =(Х₁^*,…Х_n^*) будем называть решением задачи линейного программирования или ее оптимальным планом, если

Определение. Будем говорить, что задача линейного программирования разрешима, если она имеет хотя бы один оптимальный план.