Самостійна робота 2

Тема: Метод Хілдрета та д’Езопо

 

Мета самостійної роботи – вивчити основні положення та особливості методу Хілдрета та д’Езопо, та набути практичних навичок з використання цього методу.

 

1. Основні теоретичні положення

Метод Хілдрета та д’Езопо спрямований на мінімізацію квадратичної цільової функції:

                 (1.1)

при виконані обмежень:

                                               (1.2)

до складу яких можуть бути легко включені обмеження за невід’ємністю змінних

З метою подальшої формалізації подамо задачу (1.1), (1.2) в матричному вигляді, тобто, цільову функцію запишемо, як:

                       (1.3)

а обмеження, як:

                                (1.4)

де А - матриця m×n.

При цьому для обмежень (1.2) може бути представлена інша форма запису:

де - j-та стрічка матриці А.

Симетрична n-мірна матриця, яка входить у цільову функцію (1.3) є додатною, тобто:

для будь-якого вектора

Функція Лагранжа для задачі (1.3), (1.4) може бути записана таким чином:

Позначимо

Тоді:

                       (1.5)

 

                            (1.6)

Складемо умови Куна-Таккера:

                        (1.7)

 

Оскільки матриця D додатньо визначена, то існує обернена матриця . Другу умову з системи рівнянь (1.7) можна розв’язати відносно  таким чином:

                   (1.8)

Після підстановки (1.8) в перше рівняння (1.7), умови Куна-Таккера набудуть такого вигляду:

                          (1.9)

де для зручності введені наступні позначення:

                         (1.10)

                          (1.11)

Умови (1.9) є умовами Куна-Таккера для мінімізації функції:

                       (1.12)

при дотримані обмеження

                                 (1.13)

Умови Куна-Таккера (1.7) та (1.9), які складені для задач (1.3), (1.4) та (1.12), (1.13), практично співпадають, тому можна сформувати теорему [1], згідно якої є розв’язком задачі (1.3), (1.4), тоді і тільки тоді, якщо  (згідно умови (1.8)), причому   представляє собою розв’язок задачі (1.12), (1.13).

Задача (1.12), (1.13) називається двоїстою по відношенню до (1.3), (1.4).

Згідно з вказаною теоремою, двоїста задача має розв’язок, якщо має розв’язок пряма задача (1.3), (1.4). При цьому для отримання розв’язку прямої задачі достатньо знайти розв’язок  двоїстої задачі та скористатися відношенням (1.8) для переходу до .

Доцільність переходу від задачі (1.3), (1.4) до задачі (1.12), (1.13) пов’язана з тим, що її розв’язок надзвичайно простий. Фактично він зводиться до добре відомого в енергетичних розрахунках ітераційного розв’язку систем лінійних рівнянь на основі методу Гауса-Зейделя.

Розв’язок задачі (1.12), (1.13) починається з допустимої точки . При цьому зручно прийняти , оскільки в кінцевому розв’язку деякі із компонент  мають нульові значення. Для ітераціїтакі наближення  можуть бути знайдені за формулами:

                      (1.14)

де

                (1.15)

У виразі (1.15) елементи та  відповідно діагональні та поза діагональні елементи матриці G (1.11). Використання для обчислення-го наближення -ої змінної  при  і складає суть методу Гауса-Зейделя.

Вирази (1.14) і (1.15) записані, виходячи з наступних міркувань.

Якщо вираз (1.12) про диференціювати за будь-якою , то отримаємо :

Прирівнявши останній вираз до нуля та розв’язавши відносно , можна було б безпосередньо отримати для  вираз (1.15). Однак необхідність дотримання (1.13) потребує обчислювати чергове наближення  за виразом (1.14).

Як показано в [1], послідовність  наближається до мінімуму (1.12), а послідовність  до . Таким чином, ітераційний процес продовжується до тих пір, доки  або , або  не будуть змінюватися в межах допустимої точності.