74565

Квадратичне програмування

Лекция

Информатика, кибернетика и программирование

Метод розвязування задач квадратичного програмування. Система має ненульовий розвязок якщо. Метод розвязування задач квадратичного програмування Зазначимо що відомим з теорії аналізу функцій є таке твердження: відємно означена квадратична форма є угнутою а додатно означена опуклою...

Украинкский

2015-01-04

597.5 KB

12 чел.


  1.  Квадратичне програмування

Анотація

Квадратичне програмування. Квадратична форма та її властивості. Метод розв’язування задач квадратичного програмування.

10.1 Квадратичне програмування

Окремою частиною задач опуклого програмування є задачі квадратичного програмування. До них належать задачі, які мають лінійні обмеження, а функціонал являє собою суму лінійної і квадратичної функцій:

10.2 Квадратична форма та її властивості

Квадратична функція n змінних називається квадратичною формою і може бути подана у вигляді:

,

де , , ,

причому матриця С завжди симетрична, тобто  для всіх .

Квадратична форма Z(X) називається від’ємно означеною, якщо для всіх Х, крім Х=0, значення Z(X)<0 (якщо Z(X) ≤ 0, то маємо від’ємно напівозначену квадратичну форму), у протилежному разі Z(X) є додатно означеною (якщо Z(X) ≥ 0, то маємо додатно напівозначену квадратичну форму).

Квадратична форма Z(X) називається неозначеною, якщо вона додатна для одних значень Х і від’ємна для інших.

Вид квадратичної форми можна визначити, використовуючи

  вектор характеристичних коренів (власних значень) матриці С.

Вектор характеристичних коренів матриці С є вектором, кожна компонента якого задовольняє систему рівнянь виду . Система має ненульовий розв’язок, якщо . Таке рівняння називається характеристичним рівнянням матриці С і має  коренів, які утворюють вектор :

.

Теорема 10.1. Для того, щоб довільна квадратична форма була додатно (від’ємно) означеною, необхідно і достатньо, щоб усі компоненти вектора характеристичних коренів були додатними (від’ємними) значеннями.

Якщо хоча б один із характеристичних коренів дорівнює нулю, то квадратична форма є напівдодатною (напіввід’ємною). Якщо корені мають різні знаки, то квадратична форма є неозначеною.

Приклад 10.1. Визначити вид квадратичної форми:

Матриця С має вигляд:

.

Запишемо характеристичне рівняння .

Звідси маємо:

.

Коренями отриманого квадратного рівняння є: , тоді . Отже, квадратична форма  за теоремою 8.5 є напіввід’ємною.

10.3 Метод розв’язування задач квадратичного програмування

Зазначимо, що відомим з теорії аналізу функцій є таке твердження: від’ємно означена квадратична форма є угнутою, а додатно означена опуклою.

Розглянемо випадок від’ємно означеної квадратичної форми, що входить у цільову функцію задачі квадратичного програмування.

max , (10.1)

; (10.2)

. (10.3)

Оскільки цільова функція задачі є опуклою, а обмеження — лінійні, тобто визначають опуклу множину допустимих розв’язків, то ця задача належить до задач опуклого програмування, для яких справджується твердження, що будь-який локальний максимум є і глобальним. Отже, використовуючи умови теореми Куна-Таккера для задачі (10.1)-(10.3), отримаємо необхідні та достатні умови оптимальності плану у вигляді такої теореми.

Теорема 10.1. Вектор Х* є оптимальним розв’язком задачі квадратичного програмування тоді, і тільки тоді, коли існують такі m-вимірні вектори  і n-вимірний вектор , що виконуються умови:

(І) , ; (10.4)

(ІІ) , ; (10.5)

(ІІІ) , ; (10.6)

(ІV) , . (10.7)

Наведену теорему можна використати для побудови ефективного методу розв’язування задач квадратичного програмування на основі алгоритму симплексного методу.

Умови (10.4)-(10.7) утворюють стосовно змінних  систему (n+m) рівнянь з 2(n+m) невідомими.

Умови (10.4) та (10.5) означають, що змінні  не можуть одночасно мати додатні значення, тобто входити в базис разом. Якщо деякі k компонент вектора  додатні, то відповідні їм компоненти вектора V дорівнюють нулю і лише (nk) компонент відмінні від нуля (додатні). Отже, разом  будуть мати не більш ніж n додатних компонент. З аналогічних міркувань щодо рівності (10.7) випливає, що разом з  буде n+m відмінних від нуля компонент, тобто це може бути базисний розв’язок системи, що утворена умовами (10.4) та (10.6). Для знаходження такого розв’язку можна застосувати симплексний метод.

Якщо зазначена система рівнянь має допустимий план (він буде єдиним), то оптимальний план відповідної задачі квадратичного програмування також існує.

Розв’язуємо систему рівнянь (10.4) і (10.6) симплексним методом. Як відомо, спочатку необхідно привести систему обмежень до канонічного виду введенням потрібної кількості додаткових та штучних змінних. Для зведення системи до канонічної форми та визначення початкового опорного плану вводимо штучні змінні  у рівняння виду (10.4), які будуть базисними для першого опорного плану, а змінні   у групу рівнянь (10.6), які також дають базисні змінні для початкового плану. Потім для знаходження базисного розв’язку системи (10.4), (10.7) розв’язуємо симплексним методом таку задачу лінійного програмування:

max  (10.8)

за умов:

  (10.9)

. (10.10)

Якщо в процесі розв’язування задачі (10.8)—(10.10) всі штучні змінні будуть виведені з базису  і разом з цим для знайдених значень змінних  виконуються умови (10.5), (10.7), то знайдений розв’язок є оптимальним планом задачі квадратичного програмування (10.1)-(10.3).

Приклад 10.2. Розв’язати задачу квадратичного програмування:

за умов:

Розв’язання. Оскільки цільова функція виражена сумою лінійної функції  та квадратичної форми , а система обмежень є лінійною, то маємо задачу квадратичного програмування.

Визначимо вид квадратичної форми , для чого відшукаємо корені характеристичного рівняння, що відповідає матриці, складеній з коефіцієнтів при змінних даної функції:

.

Характеристичним рівнянням для матриці С буде:

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

Запишемо функцію Лагранжа для цієї задачі:

.

Скористаємося теоремою 8.4. Необхідні умови існування екстремуму матимуть вигляд:

, причому ;

, причому ;

, причому,

де   координати сідлової точки.

Обмеження, що відповідають нерівностям, запишемо у вигляді:

Вводимо додаткові змінні для зведення нерівностей до
рівнянь:

Для зведення задачі до канонічної форми помножимо кожне рівняння на (–1):

Очевидно, що в даному разі штучні змінні необхідно вводити в перші два рівняння. У третьому рівнянні базисною змінною буде . Маємо таку задачу лінійного програмування:

,

.

Розв’язавши її симплексним методом, отримаємо:

Необхідно перевірити виконання умов:

;

;

.

Всі умови виконуються, отже,  є сідловою точкою функції Лагранжа для задачі квадратичного програмування, а   оптимальним планом задачі, для якого значення функціонала дорівнює:

.

10.9 Градієнтний метод

Градієнтні методи належать до наближених методів розв’язування задач нелінійного програмування і дають лише певне наближення до екстремуму, причому за збільшення обсягу обчислень можна досягти результату з наперед заданою точністю, але в цьому разі є можливість знаходити лише локальні екстремуми цільової функції. Зауважимо, що такі методи можуть бути застосовані лише до тих типів задач нелінійного програмування, де цільова функція і обмеження є диференційовними хоча б один раз. Зрозуміло, що градієнтні методи дають змогу знаходити точки глобального екстремуму тільки для задач опуклого програмування, де локальний і глобальний екстремуми збігаються.

В основі градієнтних методів лежить основна властивість градієнта диференційовної функції визначати напрям найшвидшого зростання цієї функції. Ідея методу полягає у переході від однієї точки до іншої в напрямку градієнта з деяким наперед заданим кроком.

Розглянемо метод Франка-Вульфа, процедура якого передбачає визначення оптимального плану задачі шляхом перебору розв’язків, які є допустимими планами задачі.

Нехай необхідно відшукати

за лінійних обмежень:

;

Допустимо, що Х0  початкова точка, що належить множині допустимих планів даної задачі. В деякому околі цієї точки нелінійну цільову функцію замінюють лінійною і потім розв’язують задачу лінійного програмування. Нехай розв’язок лінійної задачі дав значення цільової функції F0, тоді з точки Х0 в напрямку F0 необхідно рухатись доти, поки не припиниться зростання цільової функції. Тобто у зазначеному напрямку вибирають наступну точку Х1, цільова функція знову замінюється на лінійну, і знову розв’язується задача лінійного програмування.

Розглянемо детальніше перехід від k-ої ітерації методу до (k + 1)-ої ітерації.

Припустимо, що відома точка Xk, яка належить області допустимих розв’язків. У даній точці обчислюємо градієнт цільової функції:

.

Значення градієнта функції задає в даній точці напрям найшвидшого її зростання.

Замінюємо цільову функцію задачі лінійною функцією виду:

.

Потім розв’язуємо задачу лінійного програмування з обмеженнями початкової задачі і новою цільовою функцією:

за умов:

;

.

Нехай розв’язком такої задачі є точка .

З початкової точки  в напрямку  рухаємося з деяким довільним кроком , визначаючи координати нової точки  у такий спосіб:

Зауважимо, що значення параметра  доцільно вибирати таким, що дає найбільше значення цільової функції початкової задачі .

Для точки Хk+1 повторюємо розглянутий процес, для чого знову розраховуємо значення градієнта і т. д.

У такий спосіб знаходимо послідовність точок , які поступово наближаються до оптимального плану початкової задачі. Ітераційний процес повторюється до того моменту, поки значення градієнта цільової функції не стане рівним нулю або виконуватиметься умова , де   досить мале число, яке означає потрібну точність обчислень.

Приклад 10.3. Підприємство виробляє два види продукції (А і В) і використовує на виробництво три види ресурсів: І, ІІ, ІІІ. Витрати ресурсів на виробництво одиниці кожного виду продукції подано в табл. 10.1.

Таблиця 10.1

Ціна реалізації одиниці продукції виду А становить 20 ум.од., проте прибуток залежить від витрат на виробництво, які пропорційні квадрату кількості виготовленої продукції. Аналогічно визначається прибуток для продукції виду В, ціна реалізації якої дорівнює 18 ум.од.

Розв’язання. Позначимо через х1 кількість продукції виду А, х2 кількість продукції виду В, тоді загальний прибуток матиме вигляд: .

Математична модель задачі має вигляд:

,

.

Розв’яжемо задачу методом Франка Вульфа.

І ітерація

Вибираємо точку, що належить множині допустимих планів задачі. Розглянемо, наприклад, точку .

Визначимо градієнт цільової функції:

.

В точці  обчислюємо значення градієнта:

.

Використовуючи розраховане значення градієнта, записуємо і вводимо нову цільову функцію: . Маємо таку задачу лінійного програмування:

.

Розв’язуючи цю задачу симплексним методом, знаходимо її оптимальний план: .

Знайдемо новий допустимий план задачі, використовуючи формулу  для визначення координат наступної точки.

Визначаємо координати точки Х1:

, ,

Знайдемо крок  такий, за якого досягається максимальне значення цільової функції. Для цього підставимо розраховані значення для х1, х2, які виражені через , у цільову функцію :

Отримали функцію, що залежить від . Знайдемо значення , за якого функція досягає максимуму, тобто коли її похідна дорівнює нулю:

Оскільки , то беремо . Тоді наступна точка Х1 має координати:

.

Для знайденої точки  обчислюємо значення цільової функції: .

ІІ ітерація

Узявши точку , обчислюємо значення градієнта в ній:

Використовуючи розраховане значення градієнта, вводимо нову цільову функцію: . Отримуємо таку задачу лінійного програмування:

.

Розв’язавши її симплексним методом, отримуємо оптимальний план: .

За формулою  визначаємо координати наступної точки наближення.

Визначаємо координати точки Х2:

,

.

Знайдемо такий крок λ2, за якого досягається максимальне значення цільової функції:

Матимемо .

Обчислимо координати наступної точки Х2:

Для знайденої точки  значення цільової функції дорівнює: .

Продовжуючи процес у аналогічний спосіб, на ІІІ ітерації визначаємо точку  і переконуємося, що значення цільової функції знову зростає: .

На IV ітерації розраховуються координати точки , для якої .

V ітерація

Узявши точку , обчислюємо значення градієнта в ній:

.

Використовуючи значення цього вектора (градієнта), вводимо нову цільову функцію:  і маємо таку задачу лінійного програмування:

,

.

Розв’язавши цю задачу, отримаємо значення оптимального плану , тобто повертаємося до попереднього значення. Отже, точку з координатами  вважаємо оптимальним планом, оскільки маємо нульовий градієнт функції, тобто цей план поліпшити вже не можна.


 

А также другие работы, которые могут Вас заинтересовать

57477. Учебно-воспитательный процесс в дошкольных учреждениях 82.79 KB
  Можно предположить, что будут выявлены изменения в психомоторной функции после проведения занятий по танцевальной ритмике у детей с аутизмом старшего дошкольного возраста...
57478. У искусства есть два самых опасных врага: ремесленник не озаренный талантом и талант, не владеющий ремеслом 14.65 KB
  Что такое искусство? У этого слова несколько значений. Искусством называют воспроизведение действительности в художественных образах; умение, мастерство, знание дела - например, искусство вязания; само дело - например, военное искусство
57479. Современные цифровые системы коммутации AXE – 10 5.13 MB
  AXE – 10 обеспечивает постоянное и всестороннее наблюдение за порядком и результатом установления соединений, контроль поступающей нагрузки. Наличие значительного объема абонентских данных управления в памяти позволяет изменить конфигурацию системы
57482. Жеміс-жидекті айран өндіру технологиясы 79.3 KB
  Жұмыстың мақсаты, сүт қышқылды өнімдердің түрлері, соның ішінде айран өндірудің технологиялық үрдісін игеру, айран алудың термостатты және резервуарлы тәсілдері, айранның адам денсаулығына әсерін көрсету, жеміс-жидекті айран өнімін өндіргендегі технологиялық үрдістің барлық сатыларын бақылау.
57483. Виховна година, Моя Батьківщина - Україна 59 KB
  Мета: поглибити знання учнів про Україну; прищеплювати любов до рідного краю; розширити зміст поняття громадянин України; розвивати мовлення учнів; виховувати патріотичні почуття приналежності до українського народу.
57484. Сценарій літературного вечора «З Україною в серці» 1.31 MB
  Ведучі. Петриненко Ведучі. Україна Ти для мене диво І нехай пішов за роками рік буду завжди я горда і вродлива з тебе дивуватися навік На екрані карта України Ведучі. Ведучі.
57485. Welcome to Ukraine 55 KB
  The aims: Practical aims: to teach the new vocabulary, by the end of the lesson pupils will have revised the information they have learned about Ukraine, will have recollected some facts about our country by doing different tasks...