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

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

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

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

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

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

Предположим, что для изготовления двух видов продукции P1 и P2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице.

Расход ресурсов на производство продукции

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции	Запас ресурса
	P1	P2
S1
S2
S3
S4
Прибыль, получаемая от единицы продукции

 

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

(1)

и ряд ограничений (в данном случае диктуемых ограниченными запасами ресурсов):

х₁ + 3х₂ ≤ 18;

2 х₁+ х₂ ≤ 16; (2)

х₂ ≤ 5;.

3x₁ ≤21.

x₁≥0, x₂≥0,

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

a_i1x₁+…+ a_inx_n £ b_i, i= (1)

и представляет собой полупространство, лежащее по одну сторону от гиперплоскости

a_i1x₁+…+ a_inx_n = b_i, i= (2)

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

Линии уровня минимизируемой функции

z = с₁x₁+…+c_nx_n = const (3)

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

c = {c₁, c₂, …, c_n}^T

определяет направления возрастания нулевой функции z, а противоположный вектор –с определяет направление убывания функции z.

Рис1. Геометрическая интерпретация ЗЛП в стандартной форме

Выберем из семейства (3) любую плоскость, пересекающую многогранник допустимых решений X, и будем смещать ее в направлении с, если решается задача максимизации целевой функции z, и в направлении -с, если решается задача минимизации. Будем смещать эту плоскость до такого предельного положения, когда многогранник X окажется весь по одну сторону от неё и хотя бы одна их точек X все еще будет принадлежать нашей плоскости. Эти точки, или точка, лежащие на плоскости и будут решением задачи минимизации целевой функции z, и x^* решением, соответственно, задачи максимизации функции z (рис. 1).

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

Рис.2 Пример пустой области допустимых решений (X)

Во втором случае ЗЛП заведомо разрешима и имеет либо единственное решение (рис.1), совпадающее с одной из вершин допустимого многогранника X, либо бесконечное множество решений (рис.3) – ребро или грань многогранника, параллельные плоскостям семейства (3).

Рис.3 Пример ЗЛП, имеющий бесконечное множество решений (ребро АВ многогранника допустимых решений ABCDE)

Если допустимое множество решений ЗЛП неограниченно, ответ на вопрос о существовании ее решения для задачи максимизации зависит от того, ограничена сверху на этом множестве целевая функция z или нет. Если ограничена, задача разрешима, причем возможны те же ситуации, что и во втором из рассмотренных выше случаев. Если нет – решение отсутствует (рис.4). Для задачи минимизации, в случае неограниченного множества допустимых решений X, ответ на вопрос о существовании решения ЗЛП

Рис.4 - Пример ЗЛП, имеющей неограниченное множество допустимых решений.

зависит от того, ограничена снизу на множестве X целевая функция z или нет. Возникающие ситуации те же что и у задач максимизации.

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

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

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

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

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

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

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

(3.1)

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

где . (3.2)

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

Определить максимум линейной формы

F(x₁,…,x_n)=max(c₁x₁+…+c_nx_n) (3.3)

при условии, что точка (х₁, х₂,..., х_n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

(3.4)

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

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-транспонированная вектор-строка; х = (х₁, х₂,..., х_п) - п-мерный вектор переменных решений;

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

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

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

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

a₁₁х₁ +а₁₂х₂ +...+а_1пх_n=b₁

а₂₁х₁ +а₂₂х₂ +...+а_2пх_n=b_1…

…

а_m1х₁ +а_m2х₂ +...+а_mпх_n=b₁

x_t,x₂,...,x_n>0.

где с_[,с₂,...,с_п - коэффициенты целевой функции, a_tJ, i = \, 2,...,n,j = 1, 2,...,m -коэффициенты системы ограничений, а b₁,b_г,...,b_n - свободные члены, которые считаются неотрицательными.

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

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

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

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

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

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

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

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