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

Под линейным программированием понимается раздел теории экстремальных задач, в котором изучаются задач и минимизации (или максимизации) линейных функций на множествах, задаваемых системами линейных равенств и неравенств. В общем случае задача линейного программирования формулируется следующим образом. Найти вектор х* (x*₁, ..., х*_n), определяющий максимум (минимум) линейной форме

f(x) с₁x₁ + с₂x₂+...+с_nx_n (7.17)

при ограничениях (7.18) :

a₁₁x₁ + … a_1nx_n b₁;

. . . . . . . . . . . . . . . . . . .

a_m1x₁ + … a_mnx_n b_m;

a_m+1x₁+… a_m+1,nx_n b_m+1;

. . . . . . . . . . . . . . . . . . . (7.18)

a_kx₁ + … a_knx_n b_m;

a_k+1 x₁ + … a_k+1nx_n b_m;

a_m+1x₁ + … a_m+1,nx_n b_m+1;

. . . . . . . . . . . . . . . . . .

a_lx₁ + … a_lnx_n b_l;

x_i 0; i 1, …, n.

Каждое из условий-неравенств определяет полупространство, ограниченное гиперплоскостью. Пересечение полупространств образует выпуклый п-мерный многогранник Q. Условия равенства выделяют из n-мерного пространства (п-l) -мерную плоскость, пересечение которой с областью Q дает выпуклый (n-l) -мерный многогранник G. Экстремальное значение линейной формы (если оно существует) достигается в некоторой вершине многогранника. При вырождении оно может достигаться во всех точках ребра или грани многогранника. В силу изложенного для решения задачу линейного программирования теоретически достаточно вычислить значения функции в вершинах многогранника и найти среди этих значений наибольшее или наименьшее. Однако в практических задачах количество вершин области G настолько велико, что просмотр их даже с использованием ЭВМ невозможен. Поэтому разработаны специальные численные методы решения задач линейного программирования, которые ориентируются в основном на две формы записи задач. Каноническая форма задачи линейного программирования:

f(x) с₁х₁ + ...+ с_nx_n > ?max(min);(7.19)

a₁₁x₁ +… a_1nx_n b₁;

. . . . . . . . . . . . . . . . . .(7.20)

a_mx₁ +… a_mnx_n b_m;

x_i 0; i 1, …, n.

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

(с, х) ? > max(min);(7.21)

Ax b,

х 0.

Здесь А (а_ij) - (mхn) - матрица условий. Ее столбцы (a_1j, ..., а_mj)^T , j 1, ..., п, называются векторами условий. Вектор b (b₁, ..., b_m)^T носит название вектора правых частей, а с (с₁, …, с_n) - вектора коэффициентов линейной формы.

Задача линейного программирования с однотипными условиями

f(x) с₁х₁ + ...+ с_nx_n ? > max(min);(7.22)

a₁₁x₁ +… a_1nx_n b₁;

. . . . . . . . . . . . . . . . . .

a_mx₁ +…a_mnx_n b_m;

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

(с, х) ? > max(min);(7.23)

Ax b,

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

Переход к эквивалентной системе неравенств.

Знак неравенства можно поменять на обратный, меняя знаки свободного члена и коэффициентов. Например, ограничение

a₁₁x₁ +…a_1nx_n b₁;

можно заменить условием

‑a₁₁x₁ +…‑a_1nx_n -b₁.

Переход от ограничения - неравенства к равенству

Для этого необходимо ввести дополнительную неотрицательную переменную. Так, условие

a₁x₁ +…a_nx_n b.

эквивалентно двум ограничениям:

‑a₁₁x₁+…‑a_1nx_n+x_n+1 b; x_n+1 b₁.

Представление ограничения-равенства парой неравенств.

Ограничение

a_lx₁ +… a_nx_n b;

можно представить парой условий:

a₁₁x₁ +… a_1nx_n b₁.

a₁₁x₁ +…-a_1nx_n -b₁.

Переход к неотрицательным переменным

Если на знак переменной х_i не наложено ограничений, можно заменить ее разностью двух неотрицательных переменных:

x_i x_n+2 - x_n+1, x_n+1 0; x_n+2 0.

Переход от переменных, ограниченных снизу, к неотрицательным переменным

Если переменная ограничена снизу х_i b_i то, заменив ее по формуле х_i у_i + b_i переходим к задаче с неотрицательной переменной у_i 0.

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

Идея этого метода состоит в следующем. Отыскиваются некоторая вершина многогранника G и все ребра, выходящие из этой вершины. Далее перемещаются вдоль того из ребер, по которому функция убывает (при поиске минимума), и попадают в следующую вершину. Находят выходящие из нее ребра и повторяют процесс. Когда приходят в такую вершину, в которой вдоль всех выходящих из нее ребер функция возрастает, то минимум найден. Отметим, что, выбирая одно ребро, исключают из рассмотрения вершины, лежащие на остальных траекториях. В результате количество рассматриваемых вершин резко сокращается и оказывается посильным для ЭВМ. Симплекс-метод весьма эффективен и широко применяется для решения задач линейного программирования.