2 Задача линейного программирования

Задачи линейного программирования относятся к категории оптимизационных. Они находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку: найти значения переменных x₁, …, x_n, доставляющие оптимум заданной линейной формы z=c₁x₁ + c₂x₂+… + c_nx_n при выполнении системы ограничений, представляющих собой также линейные формы.

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

Слово «программирование» объясняется тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно определяют программу (план) действий некоторого объекта, например, промышленного предприятия. Слово «линейное» отражает линейную зависимость между переменными.

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

Графическое решение задачи приведено на рисунке 1.

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

Существует два крайних положения линии уровня, когда она «касается» допустимого множества. Этим двум положениям в данном случае соответствуют две точки «касания» -начало координат (0, 0) и точка (9, 13). Первая из этих точек - точка минимума, а вторая - максимума данной функции F вида (1) на допустимом множестве (2).

Рисунок 1 - Графическое решение ЗЛП

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

Постановка данной задачи выглядит следующим образом.

Имеется множество переменных X = (x₁, х₂,..., х_n). Целевая функция линейно зависит от управляемых параметров:

Имеются ограничения, которые представляют собой линейные формы

где .

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

Определить максимум линейной формы F(x₁,…,x_n )=max(c₁x₁+…+c_nx_n) при условии, что точка (х₁, х₂,..., х_n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

Любое множество значений (х₁*, х₂*,..., х_n*), которое удовлетворяет системе неравенств задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство

c₁х₁^o+ c₂ х₂^o+..+ c_n х_n^o ≥ c₁х₁+ c₂ х₂+..+ c_n х_n

для всего множества значений x₁, х₂,..., х_n, то значение х₁^o..х_n^o является оптимальным решением задачи линейного программирования.

Задачу линейного программирования удобно представлять в векторной форме, тогда она будет выглядеть следующим образом: найти max F(x) = max (c^Tx) при условии АХ ≤ Р_о; Х≥0, где с = (с₁,с₂,..., с_n) представляет собой n-мерный вектор, составленный из коэффициентов целевой функции, причем с^T-транспонированная вектор-строка; х = (х₁, х₂,..., х_n) - n-мерный вектор переменных решений;

P₀- m-мерный вектор свободных членов ограничений;

Матрица А размером (m×n) - матрица, составленная из коэффициентов всех линейных ограничений:

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

Каноническая задача линейного программирования заключается в минимизации (максимизации) линейной целевой функции

F(x) = c_lx₁+c₂x₂+... + c_nx_n при ограничениях

a₁₁х₁ +а₁₂х₂ +...+а_1nх_n=b₁

а₂₁х₁ +а₂₂х₂ +...+а_2nх_n=b₁…

…

а_m1х₁ +а_m2х₂ +...+а_mnх_n=b₁

x₁,x₂,...,x_n>0,

где с₁,с₂,...,с_n - коэффициенты целевой функции, а b₁,b₂,...,b_n - свободные члены, которые считаются неотрицательными.

Вектор X = (x₁, х₂,..., x_n), удовлетворяющий ограничениям задачи ЛП, называется допустимым решением или планом. Допустимый план X*, при котором целевая функция задачи ЛП принимает максимальное (минимальное) значение, называется оптимальным планом.

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

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

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

Наиболее простым и распространенным методом решения канонической задачи линейного программирования до сих пор является симплекс-метод, предложенный в 40-е годы прошлого века Дж. Данцигом. Геометрически идею симплекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче линейного программирования является некоторое многогранное множество n-мерного векторного пространства (в частном случае n = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начинается с некоторой начальной вершины (начального опорного плана) многогранного множества. Специальным образом выясняется, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина находится, то она и принимается за следующее приближение. После этого вновь исследуются соседние вершины для полученного приближения и т. д. до тех пор, пока не будет получена вершина, среди соседних вершин которой не существует вершины с лучшим значением целевой функции. Такая вершина является оптимальной. Она соответствует оптимальной точке (оптимальному решению) задачи линейного программирования.

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

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

В настоящее время линейное программирование представляет собой область математики, посвященную разработке теории и численных методов решения экстремальных задач с линейными целевыми функциями и линейными ограничениями в виде систем равенств и/или неравенств. С применением линейного программирования решается широкий круг задач экономического характера: задачи о комплексном использовании сырья, рационального раскроя материалов, задачи загрузки оборудования, размещения заказов по однородным предприятиям, задачи о смесях, задачи текущего производственного планирования (статическая модель), задачи перспективного оптимального планирования, транспортная задача.