Единое окно доступа к образовательным ресурсам

Руководство по решению задач по курсу "Вариационное исчисление и методы оптимизации": Методическое пособие

Голосов: 5

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
              МИНИСТЕРСТВО ОБРАЗОВАНИЯ
           РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 Кафедра теории вероятностей и оптимального управления




                     В.Г. Шарапов

 РУКОВОДСТВО ПО РЕШЕНИЮ ЗАДАЧ ПО КУРСУ
      «ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ
        И МЕТОДЫ ОПТИМИЗАЦИИ»

                 Методическое пособие




                    Волгоград 2004


                            Рецензент:
   канд. физ.-мат. наук, доц., и.о. зав. каф. МАиТФ А.А. Клячин


     Печатается по решению учебно-методической комиссии
           математического факультета университета
                 (протокол № 3 от 04.06 2004 г.)




             Печатается с готового оригинал-макета
                     в авторской редакции



Шарапов В.Г.
        Руководство по решению задач по курсу «Вариационное ис-
числение и методы оптимизации»: Методическое пособие. — Вол-
гоград: Издательство Волгоградского государственного универси-
тета, 2004. — 52 с.

      .




                         © В.Г. Шарапов, 2004
                         © Издательство Волгоградского

                                2


                               государственного университета, 2004

                              Введение
       Методическое пособие предназначено для обучения студентов ре-
шению задач по курсу "Вариационное исчисление и методы оптимизации"
(ВИМО).
       Решение задач по ВИМО не простое дело, требующее не только
знаний предмета, но и определённой интуиции и смекалки. Чтобы вырабо-
тать в себе эти качества необходимо наработать опыт решения таких задач,
т.е., попросту, решать их. Решение этих задач обычно требует больших
затрат времени, но с каждой решённой задачей приходит удовлетворение и
уверенность в себе.
       Задачи усложняются постепенно, самые сложные − это задачи оп-
тимального управления, они помещены в конце методического пособия.
       Рекомендуется сначала изучить правила решения, а затем пытаться
решать самостоятельно, при необходимости заглядывая в пособие.
       Каждая задача (P) по ВИМО начинается с формализации типа:
                                  f(x) → extr (P),
и определения области D(P) допустимых решений x ∈D(P) задачи (P).
После этого обычно используются необходимые условия экстремума, по
                                ˆ
ним определяются экстремали x , среди которых только и могут быть ре-
шения задачи. Затем по определению экстремумов (обычно даны опреде-
ления локального минимума, остальные определяются по аналогии) уста-
                                                ˆ
навливаются, какими экстремумами являются x или не являются вовсе.
Достаточные условия привлекаются только в простейших случаях.
В большинстве же случаев их привлечение очень сложно. Часто использу-
ется следствие из теоремы Вейерштрасса о достижении экстремума на
компактном множестве:
                                  n
Если функция f непрерывна на R и lim f ( x ) = ∞ ( lim f ( x ) = −∞ ),
                                       |x|→∞          |x|→∞

то f достигает абсолютный минимум (максимум) на любом замкнутом
               n
подмножестве R .
     Автор выражает благодарность А.Клячину за ценные замечания.
       При подготовке пособия использовалась литература:
1.   Алексеев В.М., Галеев Э.М., Тихомиров В.М., Сборник задач по
     оптимизации, Учебное пособие, М., Наука, 1979
2.   Галеев Э.М., Тихомиров В.М., Краткий курс теории экстре-
     мальных задач, Издательство МГУ, 1989
3.   Галеев Э.М., Тихомиров В.М., Оптимизация: теория, примеры,

                                   3


задачи, М., Эдиториал УРСС, 2000




                              4


      1. Конечномерные гладкие задачи без ограничений
                                                n
      Постановка задачи. Пусть f: R → R − функция n действитель-
ных переменных, обладающая некоторой гладкостью (дифференцируемо-
стью). f ∈ D (x ) означает, что функция f k раз дифференцируема в
                  k
              ˆ
      ˆ
точке x .
      Гладкой конечномерной задачей называется задача f ( x ) → extr .
      Точка x ∈ R называется точкой локального минимума (максиму-
                      n
               ˆ
ма) функции f, если
      | x − x | < ε ⇒ f ( x ) ≥ f ( x ) ( f ( x ) ≤ f ( x )) .
            ˆ                       ˆ                   ˆ
      Здесь |⋅| − обозначение нормы в конечномерном пространстве. При
этом пишем x ∈ loc min f ( x ∈ loc max f ) .
              ˆ                  ˆ
      Необходимые условия экстремума первого порядка.
      Если x = ( x1 , K , x n ) ∈ loc extr f и f ∈ D(x ) , то
             ˆ                                             ˆ
                          ∂f ( x )
                               ˆ       ∂f ( x )
                                            ˆ
       f ′( x ) = 0 ⇔
            ˆ                      =K=          = 0.
                           ∂x1          ∂x n
      Необходимые условия экстремума второго порядка.
      Если f ∈ D ( x ) ,
                   ˆ  2
                                  x ∈ loc min(max) f , то f ′( x ) = 0 ,
                                  ˆ                            ˆ
 f ′′( x )h, h ≥ 0
       ˆ              (   f ′′( x )h, h ≤ 0) ∀h ∈ R .
                                ˆ                   n


      Достаточные условия экстремума второго порядка.
       f ′( x ) = 0 . f ′′( x )h, h > 0
            ˆ               ˆ              (   f ′′( x )h, h < 0 ) ∀h ∈ R n , h ≠ 0.
                                                     ˆ
      Последовательными главными минорами матрицы A = ( a ij ) i , j =1
                                                                             n


называются определители
                       ⎛ a11 K a1k ⎞
                       ⎜            ⎟
      A1,...,k   = det ⎜ K K K ⎟ .
                       ⎜a           ⎟
                       ⎝ k 1 K a kk ⎠
      Главными минорами Ai1Kin матрицы A называются определители

                       ⎛ ai1i1 K ai1ik ⎞
                       ⎜                ⎟
      Ai1Kik     = det ⎜ K K K ⎟, i1 < i2 < … < ik .
                       ⎜a               ⎟
                       ⎝ ik i1 K aik ik ⎠

                                          5


     Второй производной функции нескольких переменных является
симметричная матрица вторых частных производных
                                                        n
                               ⎛ ∂ 2 f ( x) ⎞
                                         ˆ
               A = f ′′( x ) = ⎜
                         ˆ                  ⎟   = ( aij ) in, j =1 .
                               ⎜ ∂x ∂x ⎟
                               ⎝ i j ⎠ i , j =1
      Матрица A называется неотрицательно определенной (A ≥ 0), если
                                           n
           Ah, h ≥ 0 ∀h ∈ R n ⇔          ∑a h h
                                         i , j =1
                                                     ij i   j   ≥ 0 ∀h = ( h1 , K , hn ) ∈ R n

       .
      Матрица A называется положительно определенной (A > 0), если
       Ah, h > 0 ∀h ∈ R n , h ≠ 0 .
      Аналогично определяются отрицательно определенная матрица и
неположительно определенная матрица, для которых соответственно
A < 0, A ≤ 0.
      Критерий Сильвестра.
      Теорема. Пусть A − симметричная матрица. Тогда
      1. A > 0 ⇔ A1Kk > 0, k = 1, K , n.
      2. A < 0 ⇔ ( −1) ⋅ A1Kk > 0, k = 1, K , n
                           k


      3.   A ≥ 0 ⇔ Ai1Kik ≥ 0, 1 ≤ i1 ≤ K ≤ ik ≤ n, k = 1, K , n
      4. A ≤ 0 ⇔ ( −1) Ai1Kik ≥ 0,                  1 ≤ i1 ≤ K ≤ ik ≤ n, k = 1, K , n.
                           k



      Правило решения.
      1. Выписать необходимые условия экстремума первого порядка
                                    ∂f ( x )     ∂f ( x )
                  f ′( x ) = 0 ⇔             =K=          =0
                                     ∂x1          ∂xn
Решения этой системы называются стационарными точками и обознача-
      ˆ
ются x .
       2. Проверить выполнение условий экстремума второго порядка. Для
этого найти матрицу вторых производных
                                                        n
                                  ⎛ ∂ 2 f ( x) ⎞
                                            ˆ
                  A = f ′′( x ) = ⎜
                            ˆ                  ⎟   = ( aij ) in, j =1 .
                                  ⎜ ∂x ∂x ⎟
                                  ⎝ i j ⎠ i , j =1


                                            6


         Найти Ai…k. Если все Ai…k > 0, то   x ∈ loc min f ; если все
                                             ˆ
    k
(−1) Ai…k > 0, то x ∈ loc max f .
                  ˆ
         Если предыдущие условия не выполняются, то надо проверить, бу-
дет ли    Ai1Kik ≥ 0 ; 1 ≤ i1 ≤ K ≤ ik ≤ n, k = 1, K , n (тогда A ≥ 0 ) и
(−1)k Ai1Kik ≥ 0 , 1 ≤ i1 ≤ K ≤ ik ≤ n, k = 1, K , n (тогда A ≤ 0 ). Если
не выполняются оба условия A ≤ 0 и A ≥ 0 , то экстремума нет. Если вы-
полняется одно из условий A ≤ 0 или A ≥ 0 , то проверка на экстремум
производится по определению экстремума.
         Пример 1.
                                   50 20
         f ( x1 , x2 ) = x1 x2 +     +   → extr .
                                   x1 x2
         Необходимые условия экстремума первого порядка:
         ⎧             50
         ⎪ f x1 = x2 − x 2 = 0
         ⎪                      ⎧ x12 x 2 = 50   50 20       5
         ⎨
                        1
                               ⇔⎨ 2            ⇒   =   ⇒ x1 = x 2 .
                       20       ⎩ x1 x 2 = 20    x1 x2       2
         ⎪ f x2 = x1 − 2 = 0
         ⎪
         ⎩             x2

         ⎧        5
         ⎪ x1 = x 2
         ⎨        2    ⇒ x1 =5, x2 = 2.
         ⎪ x1 x 2 = 20
         ⎩
                2


         Стационарная точка x = (5, 2) .
                             ˆ
                                               100
         Вторые частные производные f x1x1 =        , f x1x2 = f x2 x1 = 1,
                                                x13
                        40
           f x 2 x2 =    3
                           .
                        x2
                                                                  ⎛ 4 / 5 1⎞
         Матрица вторых частных производных в точке x A = ⎜
                                                    ˆ     ⎜                ⎟.
                                                                           ⎟
                                                                  ⎝ 1 5⎠
         Последовательные главные миноры:
                             4    1
         A1 = 4 > 0, A1 2 = 5       = 3 > 0 ⇒ x ∈ loc min f .
                                               ˆ
               5              1 5
         Минимальное и максимальное значения функции f(x1, x2):

                                         7


                Smin = −∞, Smax = +∞.
      ( Для последовательностей {(− 1 n , − 1 n )} и {(1 4 , 1 n )} соответ-
ственно).
      Пример 2.
        f ( x1 , x2 , x3 ) = x12 + x 2 + 2 x3 + x1 x 2 + 2 x1 x3 + 3x 2 x3 − x1 → extr
                                     2      2



      Необходимые условия экстремума первого порядка:
       ⎧ f x1 = 2 x1 + x 2 + 2 x3 − 1 = 0
       ⎪
       ⎨ f x2 = 2 x 2 + x1 + 3x3 = 0 .
       ⎪ f = 4 x + 2 x + 3x = 0
       ⎩ x3         3      1      2

      Решив эту систему, находим стационарную точку
x = (1 2 , − 1, 1 2) .
ˆ
      Вторые частные производные f x1x1 = 2, f x1 x2 = f x2 x1 = 1,
       f x1x3 = f x3 x1 = 2, f x2 x2 = 2, f x2 x3 = f x3 x2 = 3, f x3 x3 = 4.
      Матрица вторых частных производных в точке x              ˆ
    ⎛2 1 2⎞
    ⎜            ⎟
A = ⎜ 1 2 3⎟ .
    ⎜2 3 4⎟
    ⎝            ⎠
      Последовательные главные миноры: A1 = 2, A12 = 3, A123 = −2.
Так как условия A ≥ 0 и A ≤ 0 не выполняются, то x ∉ loc extr f .
                                                 ˆ
      Минимальное и максимальное значения функции f(x1, x2, x3):
       Smin = −∞, Smax = +∞. (Соответствующие последовательности
легко построить).

     2. Конечномерные гладкие задачи с ограничениями
типа равенств
                                   n
     Постановка задачи. Пусть fi: R → R, i = 0, m − функции, об-
ладающие определенной гладкостью.
      Гладкой конечномерной задачей с ограничениями типа равенств на-
зывается задача:
        f 0 ( x ) → extr , f i ( x ) = 0 , i = 1, m .     (P)


                                           8


       Необходимые условия экстремума первого порядка.
       Пусть x ∈ loc extr P , функции f i , i = 0, m , непрерывно диффе-
             ˆ
                                         ˆ
ренцируемы в некоторой окрестности точки x .
       Тогда ∃λ = ( λ0 , λ1 , K , λm ) ∈ R                      , λ ≠ 0 , такие что для функции
                                                         m +1

                         m
Лагранжа Λ ( x ) =   ∑ λ f ( x ) выполняется условие стационарности:
                      i =0
                             i   i


                             ∂Λ ( x )
                                  ˆ
        Λ x ( x) = 0 ⇔
              ˆ                       = 0, j = 1, n .
                              ∂x j
      Точки, удовлетворяющие условию стационарности, называются
стационарными.
       Необходимые условия экстремума второго порядка.
       Пусть    x ∈ loc min P , f i ∈ D 2 ( x ), i = 0, m , размерность оболоч-
                 ˆ                           ˆ
ки { f1′( x ), K , f m ( x )} равна m. Тогда
          ˆ          ′ ˆ
∃λ = (1, λ1 , K , λm ) ∈ R m +1 ( λ0 = 1) , такие что для функции Лагранжа
                     m
Λ ( x ) = f 0 ( x ) + ∑ λi f i ( x ) выполняется условие стационарности
                    i =1

Λ x ( x ) = 0 и условие неотрицательной определённости матрицы вторых
      ˆ
производных: Λ ′′( x )h, h ≥ 0 ∀h : f i ′( x ), h = 0, i = 1, m .
                   ˆ                       ˆ
       Достаточные условия экстремума второго порядка.
       Пусть f i ∈ D ( x ), i = 0, m, dim lim{ f 1′( x ), K , f m ( x )} = m,
                                                                ′ ˆ
                         2
                       ˆ                             ˆ
∃λ = (1, λ1 , K , λm ) ∈ R m +1 такие, что для функции Лагранжа
                     m
Λ ( x ) = f 0 ( x ) + ∑ λi f i ( x ) задачи (P) выполняется условие стационар-
                   k =1
                                      m
ности: Λ ′ ( x ) = 0 ⇔ f 1′( x ) +
             ˆ               ˆ       ∑ λ f ′( x ) = 0 и условие положительной
                                      i =1
                                             iˆ      i


определённости матрицы вторых производных: Λ ′′( x )h, h > 0 ∀h ≠ 0
                                                 ˆ
такого, что    f i′( x ), h = 0, i = 1, m . Тогда x ∈ loc min P .
                     ˆ                            ˆ



                                                 9


       Условие максимума аналогично, если
                         m
Λ ( x ) = − f 0 ( x ) + ∑ λi f i ( x ) .
                        k =1
       Правило решения. Для решения задачи (P) нужно:
                                                           m
       1. Составить функцию Лагранжа Λ ( x ) =             ∑ λ f ( x) .
                                                           i =0
                                                                  i   i


      2. Написать необходимое условие экстремума первого порядка −
условие стационарности:
                                           m
                     Λ ′x ( x ) = 0 ⇔ ∑ λi f i′( x ) = 0
                            ˆ                    ˆ                        (1)
                                           i =0

      3. Решение системы (1) даёт стационарные точки. При этом сначала
рассматривается случай λ0 = 0, а затем λ0 = 1 или любое другое положи-
тельное число. Обычно этого достаточно, чтобы установить, являются ли
стационарные точки точками локального или абсолютного максимума или
минимума по их определению. Можно воспользоваться достаточными ус-
ловиями экстремума второго порядка. При этом для максимума удобно
брать λ0 = −1 или любое другое отрицательное число.

       Пример 1. f ( x, y , z ) = xyz → extr ; x 2 + y 2 + z 2 = 1 ,
        x + y + z = 0.
       Функция Лагранжа
         Λ ( x ) = λ0 xyz + λ1 ( x 2 + y 2 + z 2 − 1) + λ2 ( x + y + z ) .
       Условия стационарности:
                     Λ x = 0 ⇔ λ0 yz + 2λ1 x + λ2 = 0 ,
                     Λ y = 0 ⇔ λ0 xz + 2λ1 y + λ2 = 0 ,
                     Λ z = 0 ⇔ λ0 xy + 2λ1 z + λ2 = 0 .
       Пусть λ0 = 0. Тогда 2λ1 x + λ2 = 0 , 2λ1 y + λ2 = 0 ,
2λ1 z + λ2 = 0 .
       Если эти три равенства сложить и принять во внимание, что
x + y + z = 0 , получаем λ2 = 0, а значит, и λ1 = 0. Отсюда λ0 ≠ 0.
      Принимаем λ0 = 1. Получаем:
                yz + 2λ1x + λ2 = 0
                xz +2λ1y + λ2 = 0
                xy +2λ1z + λ2 = 0
                                                  10



    
Яндекс цитирования Яндекс.Метрика