Глава 2.

Линейное программирование. Теоретические основы и алгоритмы решения.

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

Как показывают приведенные в Главе I примеры, левая и правая части ограничений линейной модели могут быть связаны знаками  ; = ; . Также и переменные, фигурирующие в линейных моделей, могут быть неотрицательными, отрицательными или не иметь ограничений в знаке, поэтому задачи линейного программирования имеют несколько вариантов постановок.

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

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

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

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

при условиях

, i= 1,…,m₁ (m₁m) (2.2)

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

x_j 0, j=1,…,p (pn) (2.4)

Соотношения (2.2) - (2.3) и (2.4) будем называть соответственно функциональными и прямыми ограничениями, выражение (2.1) - целевой функцией задачи линейного программирования (ЗЛП).

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

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

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

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

или или

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

Основная задача линейного программирования (ОснЗлп)

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

Такую ЗЛП можно поставить следующим образом: найти значения переменных x₁,x₂,…,x_n, максимизирующие линейную форму

= (2.5)

при условиях

, i= 1,…,m (2.6)

x_j 0, j=1,…,n (2.7)

или в векторно-матричной форме

(2.8)

A  (2.9)

 , (2.10)

или

, (2.11)

где = (с₁,с₂,…,с_n); =(b₁,b₂,…,b_m); А=(a_ij) – матрицы коэффициентов ограничений (2.6). Задача (2.5)- (2.7) или (2.8) – (2.10) называется основной ЗЛП. Основная ЗЛП является частным случаем общей ЗЛП при m₁=m, p=n.

В линейном программировании широко используется аппарат линейной алгебры.