teor_ver_2008

Решение

В данной задаче первые четыре этапа решения задачи линейного программиро- вания рассмотренным графическим методом уже выполнены, то есть область допусти- мых решений определена и известны координаты ее вершин: A (0,2), B (6,2), C (3,5), D(0,5). В задании обозначений вершин буквами нет. Они введены для удобства реше- ния.

5-й этап. Вычисление значений целевой функции во всех вершинах области до- пустимых решений:

z A = z (0,2) = x1A + 2 x 2A = 0 + 2 × 2 = 0 + 4 = 4 , z B = z (6,2) = x1B + 2 x 2B = 6 + 2 × 2 = 6 + 4 =10,

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

z ma x = m a x {z A , z B , z C , z D } = m a x {4,10,13,10} =13 .

Следовательно, максимальное значение целевой функции в данной задаче ли- нейного программирования равно 13. Оно достигается в точке C (3,5).

Номер варианта ответа: 1.

2.3.2. Задание № 26 по теме “Линейное программирование: аналитическое задание области допустимых решений”

Максимальное значение целевой функции z = x1 + 2 x 2 при ограничениях

Решение

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

42

Графики граничных прямых показаны на рис 5.

x 2 x1 = 0

x1 = 4

6

x 2 = - x1 + 6

x 2 = 0

Рис. 5. Граничные прямые в задании № 26

2-й этап. Нахождение полуплоскостей, определяемых каждым из ограничений. Очевидно, что:

1)полуплоскость, определяемая неравенством x1 ³ 0, расположена справа от оси ординат;

2)полуплоскость, определяемая неравенством x1 £ 4 , расположена слева от

прямой x1 = 4 ;

3) полуплоскость, определяемая неравенством x 2 ³ 0 , расположена выше оси

абсцисс.

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

неравенство 0 ≤ 6 . Следовательно, искомая полуплоскость та, в которой расположена точка О (0,0). Данная полуплоскость расположена ниже граничной прямой x1 + x 2 = 6 .

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

43

3-й этап. Определение области допустимых решений. Анализ рис. 6 показывает, что область допустимых решений представляет собой четырехугольник OABC, пока- занный на рис. 7.

Рис. 7. Область допустимых решений в задании № 26

4-й этап. Вычисление координат всех вершин области допустимых решений. Координаты точек O (0,0), A (4,0) и C (0,6) известны в результате построения

граничных прямых.

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

ì x 2 = - x1 + 6, íî x1 = 4.

44

Подставляя значение x1 из второго уравнения системы в первое, получим

x 2 = - 4 + 6 = 2.

Тогда решение системы уравнений будет иметь вид

ì x1 = 4, íî x 2 = 2.

Следовательно, точка B имеет координаты (4,2).

5-й этап. Вычисление значений целевой функции во всех вершинах области до- пустимых решений:

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

z ma x = m a x {z O , z A , z B , z C } = m a x {0, 4, 8,12} =12 .

Следовательно, максимальное значение целевой функции в данной задаче ли- нейного программирования равно 12. Оно достигается в точке С (0,6).

Номер варианта ответа: 3.

2.3.3. Задание № 27 по теме “Нелинейное программирование”

Требуется выбрать один вариант ответа.

Краткие теоретические сведения по теме

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

Локальным максимумом (минимумом) функции нескольких переменных f ( x1 , x 2 , ... , xn ) , определенной на множестве M n -мерного пространства, называется

45

В общем виде задача нелинейного программирования формулируется сле-

дующим образом: найти такие значения x1 , x 2 , ... , x n неизвестных переменных x1 , x 2 , ... , x n , доставляющие экстремум целевой функции вида

z= f ( x1 , x 2 , ... , xn ) ® e xt r

иудовлетворяющие системе ограничений

Система ограничений может включать также условия неотрицательности пере- менных, если такие условия имеются.

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

Условный экстремум функции – экстремум функции, аргументы которой удовлетворяют дополнительным условиям, называемым ограничениями или уравне-

ниями связи.

Задачи нелинейного программирования возникают на практике, например, 1) когда затраты изменяются не пропорционально количеству закупленных или произве- денных товаров, 2) когда расход определенных видов сырья и ресурсов происходит не линейно, а скачкообразно (в зависимости от объема производства).

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

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

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

тоду).

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

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

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

2) выпуклое программирование – раздел нелинейного программирования, изучающий задачи минимизации выпуклых функций (максимизации вогнутых функ- ций) на выпуклых замкнутых множествах (выпуклым множеством точек называется множество точек, которое вместе с любыми своими двумя точками содержит и соеди- няющий их отрезок; замкнутым множеством – называется множество точек, содер- жащее все свои граничные точки);

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

46

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

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

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

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

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

ì z = f ( x , y ) ® e xt r , íî g ( x, y ) = b.

Точкой условного максимума (минимума) функции z = f ( x, y ) называется точка ( x0 , y 0 ) , если существует такая ее окрестность, что для всех точек ( x, y ) из этой окрестности, удовлетворяющих условию g ( x, y ) = b , выполняется неравенство

f ( x0 , y 0 ) ³ f ( x, y ) [ f ( x0 , y 0 ) £ f ( x, y ) ].

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

Метод подстановки используется, если из ограничения g ( x, y ) = b можно в явном виде выразить функцию y = h( x ) . Тогда, подстановка функции y = h( x ) в це- левую функцию z = f ( x, y ) вместо переменой y приводит к получению целевой функции вида z = f [ x, h( x)] , которая зависит только от одной переменной x . В

этом случае задача на условный экстремум функции двух переменных сводится к за- даче на безусловный экстремум функции одной переменной.

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

Точка x 0 называется точкой максимума функции f ( x ) , если в некоторой ок- рестности точки x 0 выполняется неравенство f ( x ) £ f ( x0 ) .

Точка x 0 называется точкой минимума функции f ( x ) , если в некоторой ок- рестности точки x 0 выполняется неравенство f ( x ) ³ f ( x0 ) .

Точки экстремума – общее название точек максимума и минимума функции. Максимум функции – значение функции в точке ее максимума.

Минимум функции – значение функции в точке ее минимума. Экстремум функции – общее название максимума и минимума функции.

47

Необходимое условие экстремума функции одной переменной – равенство нулю ее первой производной ( f ' ( x ) = 0 ).

Критическая точка – точка, в которой выполнено необходимое условие экс- тремума функции.

Достаточное условие экстремума функции одной переменной: если первая производная f ' ( x ) дважды дифференцируемой функции y = f ( x ) равна нулю в неко- торой точке x 0 , а вторая производная в этой точке f '' ( x0 ) положительна, то точка x 0

чии экстремума в точке x 0 остается открытым.

Алгоритм решения задачи на безусловный экстремум функции одной пере-

менной включает следующие этапы.

1.Нахождение производной f ' ( x ) функции y = f ( x ) .

2.Нахождение критических точек функции y = f ( x ) путем приравнивания ее

производной к нулю ( f ' ( x ) = 0 ) в соответствии с необходимым условием экстремума функции.

3. Нахождение второй производной f '' ( x ) функции y = f ( x ) и проверка дос- таточного условия экстремума функции в каждой критической точке.

4.Вычисление локальных экстремумов функции.

5.Нахождение глобальных максимума и минимума функции (при наличии не- скольких максимумов или минимумов). Глобальный максимум функции определяется как наибольший локальный максимум. Глобальный минимум функции определяется как наименьший локальный минимум.

Алгоритм решения задачи на безусловный экстремум функции двух пере-

менных z = f ( x, y ) включает следующие этапы.

1.Нахождение частных производных функции z = f ( x, y ) и приравнивание их к нулю

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

лучится система из двух уравнений вида

Частной производной первого порядка (первой частной производной или просто частной производной) функции двух переменных z = f ( x, y ) по переменной

x называется производная данной функции, вычисленная при фиксированном значе- нии переменной y как обыкновенная производная функции одной переменной x . Она

обозначается как ¶¶ xz , ¶¶ xf , z 'x , f 'x .

Частной производной первого порядка функции двух переменных z = f ( x, y ) по переменной y называется производная данной функции, вычисленная

при фиксированном значении переменной x как обыкновенная производная функции одной переменной y . Она обозначается как ¶¶ zy , ¶¶ yf , z 'y , f 'y .

48

Функция, имеющая частные производные первого порядка, называется диффе-

ренцируемой.

Теорема (необходимое условие экстремума функции двух переменных): если в точке максимума или минимума все частные производные существуют и непрерыв- ны, то они равны нулю в этой точке.

2. Нахождение критических точек, в которых целевая функция задачи z = f ( x, y ) мо-

жет иметь экстремум путем решения полученной системы уравнений.

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

3. Нахождение частных производных второго порядка функции z = f ( x, y ) , вычисле-

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

Частной производной второго порядка (второй частной производной) функ-

ции z = f ( x, y ) называется частная производная первого порядка от частной произ- водной первого порядка данной функции. Функция двух переменных вида z = f ( x, y ) имеет четыре частных производных второго порядка:

Частные производные второго порядка, в которых дифференцирование произво- дится по разным переменным, называются смешанными производными.

Частные производные более высоких порядков определяются аналогичным об-

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

Теорема (достаточное условие экстремума функции двух переменных). Если функция z = f ( x, y ) : а) определена в некоторой окрестности критической точки

( x0 , y 0 ) , в которой обе частные производные равны нулю ( f 'x ( x0 , y 0 ) = 0, f 'y ( x0 , y 0 ) = 0 ); б) имеет в этой точке непрерывные частные производные второго по-

рядка, равные

f ''x x ( x 0 , y 0 ) = A , f ''x y ( x 0 , y 0 ) = f ''y x ( x0 , y 0 ) = B , f ''y y ( x 0 , y 0 ) = C ,

то характер этой точки определяется значением величины D = AC - B 2 .

49

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

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

Теорема (достаточное условие экстремума функции n переменных). Если точка ( x1 , x 2 , ... , x n ) является критической точкой функции n переменных

z = f ( x1 , x 2 , ... , x n ) , и в окрестности этой точки существуют и непрерывны частные

Определитель матрицы Гессе называется гессианом.

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

Квадратичной формой L ( x1 , x 2 , ... , xn ) от n переменных называется сумма,

каждый член которой является либо квадратом одной из переменных, либо произведе- нием двух разных переменных, взятых с некоторым коэффициентом:

где ai j (i, j = 1, ... , n ) – коэффициенты квадратичной формы, являющиеся действи- тельными числами, причем ai j = a ji .

Матрицей квадратичной формы называется симметрическая матрица, состав- ленная из коэффициентов квадратичной формы, то есть

Симметрическая (симметричная) матрица – квадратная матрица, в которой элементы, расположенные симметрично относительно главной диагонали равны, то

50

Квадратичная форма L ( x1 , x 2 , ... , xn ) называется положительно (отрицатель-

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

L ( x1 , x 2 , ... , xn ) > 0 ( L ( x1 , x 2 , ... , xn ) < 0 ).

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

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

Теорема (критерий Сильвестра). Для того чтобы квадратичная форма была положительно определенной, необходимо и достаточно, чтобы все главные миноры

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

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

еематрицы отличны от нуля.

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

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

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

1. Введение вспомогательной переменной λ , называемой множителем Лагранжа, и составление функции Лагранжа, которая представляет собой сумму це- левой функции и ограничения, умноженного на множитель Лагранжа, вида

L ( x, y, λ ) = f ( x , y ) + λ ×[ g ( x, y ) - b ] .

Метод множителей Лагранжа основан на том, что точка условного экстремума ( x0 , y 0 ) функции z = f ( x, y ) при условии g ( x, y ) = b совпадает с точкой безус-

ловного экстремума ( x0 , y 0 , λ 0 ) функции Лагранжа.

51