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 ітерація

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

.

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

,

.

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


 

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

26821. Задача Коши для ОДУ первого порядка 111.5 KB
  При объектном подходе акцент переносится на конкретные характеристики системы являющейся предметом программного моделирования. Это позволило создавать программные системы максимально похожие на реальные и при этом добиваться наивысшего уровня абстракции. Концептуальная модель системы С чего начать Для одной и той же системы можно составить множество моделей. Они будут отличаться: степенью детализации учета тех или иных особенностей и режимов функционирования отражать определенную грань сущности системы ориентироваться на...
26823. Анатомический состав и морфофункциональная характеристика органов кровообращения. Особенности кровоснабжения отдельных органов 5.99 KB
  Анатомический состав и морфофункциональная характеристика органов кровообращения. особенности кровоснабжения отдельных органов. Система органов кровообращения состоит из центрального органа сердца; кроветворных органов селезенки костного мозга и лимфатических узлов; кровеносных сосудов артерий вен и капилляров. Таким образом сосуды несущие кровь от сердца к органам называются артериями а сосуды несущие кровь от органов к сердцу венами.
26824. Общие закономерности строения, хода и ветвления кровеносных сосудов 5.4 KB
  Строение кровеносных сосудов: Кровеносные сосуды по функции и строению разделяются на проводящие сосуды артерии и вены и питающие сосуды капилляры. Сосуды vasa vasorum и нервы nervi vasorum. Артерии arteria сосуды по которым кровь выносится из сердца. Соединяет сосуды с органами и мышцами По строению стенок различают артерии эластического переходного и мышечного типов.
26825. Основные данные фило- и онтогенеза сердечно -сосудистой системы 3.41 KB
  У амфибий на ряду с жаберным дыханием появляется легочное с образованием легочного круга кровообращения: из жаберной артерии появл. У рептилий 2 круга кровообращения: легочной и соматический. Следовательно 2 круга кровообращения. Одновременно с ними закладывается сердце которое на 7 неделе становится 4хкамерным устанавливается желточный круг кровообращения который заменяется на плацентарное кровообращещение связанное со стенкой матки.
26826. Круги кровообращения 2.55 KB
  круги кровообращения Большой или системный круг кровообращения начинается от левого желудочка сердца из которого кровь поступает в аорту. Путь крови от левого желудочка до правого предсердия составляет большой круг кровообращения. Из правого предсердия кровь поступает в правый желудочек который служит началом малого круга кровообращения. Малый или легочный круг кровообращения начинается из правого желудочка легочной Артерией которая в легких распадается на многочисленные капилляры что способствует освобождению крови от углекислого...
26827. Анатомическое строение сердца 4.15 KB
  анатомическое строение сердца Сердце cor гр. Предсердия располагаются в основании сердца и снаружи от желудочков отделены венечной бороздой sulcus coronarius. Желудочки образуют большую часть сердца.Обе борозды сходятся на краниальной поверхности сердца не достигая его верхушки.
26828. Деление общего плечеголовного ствола 4.3 KB
  Он делится на: Самая верхняя межреберная артерия a. intercostalis suprema отдающая 25 дорсальные межреберные артерии для питания грудной стенки холки и спинного мозга Дорсальная лопаточная артерия a. Глубокая шейная артерия a. Позвоночная артерия a.
26829. Общие закономерности строения внутренних органов (трубкообразного и паренхиматозного) 8.4 KB
  Паренхима рабочая часть органа тканевомягкая субстанция. Вторая часть органа строма каркас это соединительнотканная часть органа в ее состав входят все элементы которые обеспечивают нормальное функционирование паренхимы: соединительнотканные прослойки трабекулы которые делят орган на доли; кровеносные и лимфатические сосуды; нервные элементы. Характерные черты паренхиматозных органов: Наличие большого количества мягкой податливой субстанции паренхимы составляющей основу органа. Компактность и крупные размеры органа.