74565

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

Лекция

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

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

Украинкский

2015-01-04

597.5 KB

15 чел.


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

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

.

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

,

.

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


 

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

29807. ОСНОВНЫЕ КОМПОНЕНТЫ ЗВУКОВОГО РЕШЕНИЯ 19.65 KB
  ОСНОВНЫЕ КОМПОНЕНТЫ ЗВУКОВОГО РЕШЕНИЯ Условно звуковое решение можно представить в виде трех блоков: блок выбора параметров и характеристик звука физические энергетические психофизические блок выбора художественных приемов блок выбора конкретного звукового материала. Выбор параметров и характеристик звука: 1. Громкость звука. Выбор громкости звука любого материала в мероприятии должен быть во всех случаях мотивирован.
29808. Фонограммы и их сценарно-режиссерские функции в КДД 15.96 KB
  Все театральные шумы музыкальный материал и литературно-музыкальные разработки общего характера. В качестве средства художественной выразительности наиболее часто используются музыкальные и шумовые фонограммы в самых разнообразных комбинациях как между собой так и с другими звуковыми и зрелищными элементами. Музыкальные фонограммы Музыкальные фонограммы используются как отдельные музыкальные выступления завершающие части целых музыкальных программ музыкальные заставки музыка сопровождающая действие. Для создателей театрализованных...
29809. ЗВУКИ И ШУМЫ 15.02 KB
  ЗВУКИ И ШУМЫ Все звуки делятся на тоны звуки и шумы. Музыкальный звук беспредметен тогда как все остальные шумы и звуки связаны либо с явлениями природы либо с действиями человека или какихто предметов то есть они конкретны. В зрелищных программах все шумы и звуки в зависимости от метода включения в действие делятся на три группы: 1. В связи с тем что подобные шумы в настоящее время воспроизводятся преимущественно с помощью фонограммы следует особенно внимательно следить за расположением динамиков на игровой площадке.
29810. ЗВУКОВЫЕ ЭФФЕКТЫ И ИХ ВЫРАЗИТЕЛЬНЫЕ ВОЗМОЖНОСТИ В КДД 15.38 KB
  ЗВУКОВЫЕ ЭФФЕКТЫ И ИХ ВЫРАЗИТЕЛЬНЫЕ ВОЗМОЖНОСТИ В КДД Звуковые эффекты весьма разнообразны: здесь и перемещение звуковых образов в пространстве движение поездов самолетов демонстраций и т. Эффект панорамирования звука. Суть эффекта заключается в создании иллюзии перемещения звука или звуковой картины в пространстве. Технология получения эффекта панорамирования звука: акустические колонки устанавливают в задействованном пространстве в определенном порядке по планам сцены и зала фойе или другого помещения и вместе с соответствующими...
29811. Методика разработки звуковой партитуры досуговых мероприятий 16.84 KB
  Указывается также дата проведения мероприятия. Здесь же указывается схема коммутации источников звуковой программы магнитофоны микрофоны и пр. При использовании на спектакле ревербератора и панорамного микшера указывается режим их работы и схема подсоединения к каналам звукоусиления. Вначале указывается порядковый номер включения.
29812. Общие понятия о светотехническом обеспечении 15.57 KB
  Техническое обеспечение состоит из пяти условно выделенных групп: световые приборы светорегулирующая аппаратура силовое установочное электрооборудование цветомузыкальные установки приспособления. Световые приборы предназначены для освещения и получения световой проекции или световых эффектов в постановочном освещении КДУ. Здесь же отметим что в группе прожекторов можно выделить подгруппы: прожекторные приборы проекторные приборы и приборы для световых эффектов. На щите установлены аппараты защиты и управления линиями нерегулируемого...
29814. Световое решение мероприятия, световая среда и понятие о технологии их получения 17.47 KB
  Световое решение мероприятия световая среда и понятие о технологии их получения. Задачу создания постановочного света решает светотехническое обеспечение СТО которое представляет собой совокупность технических средств методов и способов их эксплуатации и использование в клубном мероприятии. Разработанное в результате поисков и проб световое решение в клубном мероприятии составляет его световую среду. Световая среда характеризуется интенсивностью контрастностью цветностью динамикой.
29815. Принцип теневого театра: технология получения и использования в КДД 34.51 KB
  Источник тени т. При использовании двух прожекторов получают две тени от одного объекта при трех три и т. А если во все три используемые прожектора поставить разного цвета светосфильтры то получим от одного объекта три тени разного цвета. Более того если два прожектора с разными цветами света установить на легкие тележки и начать их развозить друг от друга то на экране тень от одного объекта начнет раздваиваться на две разного цвета тени.