Метод множителей Лагранжа, метод нахождения условного экстремума функции f(X), где , относительно m ограничений , I меняется от единицы до m. Описание метода

• Составим функцию Лагранжа в виде линейной комбинации функции f и функций , взятыми с коэффициентами, называемыми множителями Лагранжа — λ_i:

где .

• Составим систему из n + m уравнений, приравняв к нулю частные производные функции Лагранжа по x_j и λ_i.

• Если полученная система имеет решение относительно параметров x'_j и λ'_i, тогда точка x' может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

Обоснование

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

Двумерный случай

Линии уровня и кривая .

Пусть требуется найти экстремум некоторой функции двух переменных при условии, задаваемом уравнением . Мы будем считать, что все функции непрерывно дифференцируемы, и данное уравнение задает гладкую кривую S на плоскости . Тогда задача сводится к нахождению экстремума функции f на кривой S. Будем также считать, что S не проходит через точки, в которых градиент f обращается в 0.

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

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

где λ — некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа , зависящую от и λ:

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

Мы получили систему, первые два уравнения которой эквивалентны необходимому условию локального экстремума (1), а третье — уравнению . Из нее можно найти . При этом , поскольку в противном случае градиент функции f обращается в нуль в точке , что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки могут и не являться искомыми точками условного экстремума — рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции L и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия.

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию Z = С ₁ х ₁ +С ₂ х ₂ +… +С _N x _N

при линейных ограничениях

a ₁₁ x ₁ + a ₂₂ x ₂ + … + a _1N Х _N = b ₁

a ₂₁ x ₁ + a ₂₂ x ₂ + … + a _2N Х _N = b ₂

. . . . . . . . . . .

a _М1 x ₁ + a _М2 x ₂ + … + a _МN Х _N = b _М

Так как Z – линейная функция, то = С _j (j = 1, 2, …, n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами

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

1. Общая задача линейного программирования

   1. Формулировка задачи.

Даны линейная функция

(1.1)    Z = С ₁ х ₁ +С ₂ х ₂ +… +С _N x _N

и система линейных ограничений

a ₁₁ x ₁ + a ₂₂ x ₂ + … + a _1N Х _N = b ₁

a ₂₁ x ₁ + a ₂₂ x ₂ + … + a _2N Х _N = b ₂

. . . . . . . . . . .

a _i1 x ₁ + a _i2 x ₂ + … + a _iN Х _N = b _i (1.2)

                                   . . . . . . . . . . .

a _M1 x ₁ + a _M2 x ₂ + … + a _MN Х _N = b _M

(1.3)                x _j 0 (j = 1, 2, … ,n)

где а _ij , Ь _j и С _j - заданные постоянные величины

Найти такие неотрицательные значения х ₁ , х ₂ , …, х _n , которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное значение

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

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

Найти минимальное значение линейной функции

(1.5)    Z = С ₁ х ₁ +С ₂ х ₂ +… +С _N x _N

при ограничениях

a ₁₁ x ₁ + a ₂₂ x ₂ + … + a _1N Х _N b ₁

                                   a ₂₁ x ₁ + a ₂₂ x ₂ + … + a _2N Х _N b ₂

(1.6)                . . . . . . . . . . .

                                   a _M1 x ₁ + a _M2 x ₂ + … + a _MN Х _N b _M

(1.7)                x _j 0 (j = 1, 2, … ,n)

Совокупность чисел х ₁ , х ₂ , …, х _N , удовлетворяющих ограничениям (1.6) и (1.7), называется решением. Если система неравенств (1.6) при условии (1.7) имеет хотя бы одно решение, она называется совместной, в противном случае – несовместной

Рассмотрим на плоскости х ₁ Ох ₂ совместную систему линейных неравенств

a ₁₁ x ₁ + a ₂₂ x ₂ b ₁

a ₂₁ x ₁ + a ₂₂ x ₂ b ₂

. . . .a _M1 x ₁ + a _M2 x ₂ b _M

x ₁ 0, x ₂ 0

Это все равно, что в системе (1.6) – (1.7) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

a _i1 x ₁ + a _i2 x ₂ = b _i ,(i = 1, 2, …, m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рис. 1.1)

Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом, много-угольником, неограничен-ной многоугольной облас-тью

Если в системе ограничений (1.6) – (1.7) n = 3, то каждое нера-венство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a _i1 x ₁ + a _i2 x ₂ + a _i3 x ₃ = b _i ,(i = 1, 2, …, n), а условия неотрицательности – полупрост-ранства с граничными плоскостями соответственно х _j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений . Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.6) – (1.7) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a _i1 x ₁ + a _i2 x ₂ + a _iN x _N = b _i (i = 1, 2, …, m), а условия неотрицательности – полупространства с граничными гиперплоскостями х _j 0 (j = 1, 2, …, n)

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

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

79. Графический метод решения задачи линейного программирования для двух переменных.

Наиболее простым и наглядным методом линейного про­граммирования является графический метод. Он применяется для решения задач ЛП с двумя переменными, заданными в не­канонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных.

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

Для нахождения экстремального значения целевой функ­ции при графическом решении задач ЛП используют вектор L() на плоскости Х₁ОХ₂, который обозначим . Этот вектор показывает направление наискорейшего изменения це­левой функции, он равен

где е₁ и е₂ — единичные векторы по осям OX₁ и ОX₂ соответ­ственно; таким образом, = (∂L/∂х₁, ∂L/∂х₂). Координатами вектора являются коэффициенты целевой функции L().