ИсследОпераций

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

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

§ 2. Задача безусловной минимизации

Рассмотрим задачу безусловной минимизации

min f x .

x En

Теорема 2.1. Если непрерывно дифференцируемая функция f x имеет в

точке x безусловный локальный экстремум, то все ее частные производные обращаются в точке x в нуль:

З а м е ч а н и е . 1. Точки x , являющиеся решениями системы уравнений (2.1), называются стационарными точками функции f x .

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

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

необходимо (достаточно), чтобы главные миноры ее гессиана в точке x были неотрицательны (положительны).

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

необходимо (достаточно), чтобы у ее гессиана в точке x главные миноры четного порядка были неотрицательны (положительны), а нечетного – неположительны (отрицательны).

Пример. Найти локальные экстремумы функции

fx1, x2, x3 2x1x2 x12 3x22 x33 8x2 3x3 .

Ре ш е н и е. 1) Вычислим частные производные данной функции и приравняем их к нулю

43

§ 3. Задача условной минимизации с ограничениями типа равенств.

Метод множителей Лагранжа

где допустимое множество D определяется системой m ограничений – равенств

нято называть множителями Лагранжа.

Теорема 3.1. (Необходимые условия локального экстремума). Пусть даны задача (3.1), (3.2) и точка x , в некоторой окрестности которой функции f x ,

k x непрерывно дифференцируемы, а градиенты k x линейно независи-

мы. Если x – точка локального экстремума данной задачи, то существуют такие значения множителей Лагранжа k* k 1, m , не равные нулю одновременно,

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

Для нахождения стационарных точек, являющихся «претендентами» на оптимальное решение в задаче (3.1), (3.2), применяется метод множителей Лагранжа, состоящий из следующих этапов:

1) составляется функция Лагранжа;

45

Пример. Найти наименьшее значение функции f x, y 3x 4y

при ограничении x2 y2 25 .

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

Функция Лагранжа для данной задачи имеет вид

L x, y, 3x 4 y x2 y2 25 .

Метод множителей Лагранжа приводит к уравнениям

L 3 2 x 0,x

L 4 2 y 0,y

L x2 y2 25 0.

Эта система имеет два решения

1)1 2 , x1 3, y1 4 ;

2)2 2 , x2 3, y2 4 .

46

§ 4. Задача условной минимизации с ограничениями типа неравенств.

Условия Куна-Таккера

допустимое множество которой определяется системой m ограничений – неравенств

gk x непрерывно дифференцируемы, а градиенты g xk* линейно независимы.

Если x – точка локального минимума данной задачи, то существуют такие неотрицательные и не равные нулю одновременно значения множителей Лагранжа k* k 1, m , что

З а м е ч а н и е. Условия (4.3) известны как условия Куна-Таккера. Если же рассматривается локальный максимум, то знак k в условиях (4.3) меняется на

противоположный.

Пример. Найти наименьшее значение функции f x, y xy 4x

при ограничении x2 y2 6 .

Р е ш е н и е. По теореме Вейерштрасса существует оптимальное решение данной задачи. Это оптимальное решение (точка глобального минимума) является и локальным минимумом, а следовательно, по теореме 4.1, удовлетворяет

47

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

Функция Лагранжа для данной задачи имеет вид

L x, y, xy 4x x2 y2 6 .

Запишем условия Куна-Таккера

L y 4 2 x 0,x

L x 2 y 0,y

L x2 y2 6 0, (4.4)

x2 y2 6,

0.

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

Итак, решаем систему:

y 4 2 x 0,

x 2 y 0, (4.5)

x2 y2 6 0.

Рассмотрим последнее уравнение системы. Возможны два случая:

а) 0 x 0, y 4 ; б) 0 .

Исключая неизвестное , получаем систему

48

Исключая неизвестное x , получаем уравнение

2 y2 4 y 6 0 .

Откуда находим y 1 либо y 3. Если y 3, то x2 3, что невозможно. При y 1 находим еще два решения системы (4.5). Таким образом, система (4.4) имеет три решения:

1)0; x 0; y 4 ;

2)25 ; x 5; y 1;

3)25 ; x 5; y 1,

из которых только второе удовлетворяет всем условиям (4.4).

fmin f 5; 1 55 .

§ 5. Заключение

Рассмотренные примеры достаточно ясно указывают на трудности, возникающие при применении классической теории экстремума к решению ЗМП. Вопервых, применение классических методов требует решения нелинейной системы уравнений, что является сложной задачей, особенно при большом числе переменных. Во-вторых, найденные решения системы являются лишь «претендентами» на искомые точки экстремума, и их характер часто должен исследоваться при помощи громоздких достаточных условий. И наконец, классические методы позволяют найти лишь точки локального экстремума, зачастую оставляя открытым вопрос о существовании и нахождении глобальных максимумов и минимумов. Поэтому практическое значение классических методов невелико, и они могут быть использованы лишь при решении простых ЗМП с небольшим количеством переменных.

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

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

49

ГЛАВА 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

В общем виде математически поставленная ЗЛП формулируется следующим образом:

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

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

где "?" – один из знаков =, ≤ или ≥. Найти такую точку x , которая удовлетворяет системе (1.2) и доставляет целевой функции (1.1) наименьшее или наибольшее значение.

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

Например,

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

Пусть предприятие выпускает продукцию n различных наименований, ис-

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

Если обозначить через x j количество единиц j -го вида продукции, кото-

рое необходимо произвести, то математическая модель поставленной задачи примет вид

§ 2. Различные формы ЗЛП. Основные приемы преобразования ЗЛП

из одной формы в другую

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

Так рассмотренную в предыдущем параграфе задачу (1.1), (1.2) будем называть общей ЗЛП.

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

1)она является задачей минимизации;

2)все ее ограничения имеют вид равенств;

3)на все переменные наложено требование неотрицательности. Таким образом, каноническая ЗЛП имеет следующий вид:

min z c1x1 ... cn xn ,

xk 0, k 1, n .

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

min z c , x , x En ,

Ax B, B Em , x 0.

51

Здесь A – матрица системы ограничений (размера m n ), B – столбец свободных членов, а c – вектор коэффициентов целевой функции.

Определение. Стандартными или симметричными будем называть ЗЛП следующих двух типов:

а): 1) задача минимизации;

2)все ограничения являются неравенствами со знаком ≥;

3)на все переменные наложено требование неотрицательности; б): 1) задача максимизации;

2)все ограничения являются неравенствами со знаком ≤;

3)на все переменные наложено требование неотрицательности. Запишем в матричном виде оба типа стандартных ЗЛП:

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

1) Переход от задачи минимизации к задаче максимизации осуществляется сменой знака у целевой функции

2) Переход к эквивалентной системе неравенств. Меняя знак у обеих ча-

стей ограничения–неравенства, можно поменять знак этого неравенства на противоположный:

a, x b a, x b .

3) Представление ограничения–равенства парой неравенств

4) Переход от ограничения–неравенства к равенству. Для приведения не-

равенства

к равенству необходимо к левой его части прибавить некоторую неотрицательную величину xn 1 0 . В результате неравенство (2.1) эквивалентно двум огра-

ничениям

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

52