Ефективність державної інвестиційної та інноваційної політики на сучасному етапі розвитку економіки

 
















Метод Біла для розвязку задач квадратичного програмування


1.Теорема Куна-Такера


Центральне місце в теорії нелінійного програмування займає теорема Куна-Такера.

Нехай має місце задача нелінійного програмування: знайти максимальне значення функції при обмеженнях (1).


(1)


Побудуємо функцію Лагранжа для даної задачі


(2)


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

Теорема 1. Вектор тоді і тільки тоді є оптимальним розвязком задачі (1), коли існує такий вектор , що при і для всіх і має місце нерівність (3)


(3)


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

Доведення. Нехай і- сідловка точка функції. Якщо в (3) підставити (2), то одержимо


При , .

Права нерівність справедлива при будь-якому , тому


.


Тоді із лівої нерівності отримаємо


при .


Так як при цьому , то .

Таким чином, точка задовольняє обмеженням (1) і в усіх інших точках функції приймає значення менше, чим у . Це твердження призводить до знаходження сідловин точок функції Лагранжа .

Доведення необхідності умови (3) через його складність не розглядається.

Якщо і - диференційовані функції, то (3) еквівалентні наступним локальним умовам Куна-Такера:


(4)

(5)


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


(4)

(5)


В подальшому при розгляданні задачі квадратичного програмування використовуватимуться умови (4) і (5).


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


Частковим випадком задачі нелінійного програмування являється задача квадратичного програмування, в якій обмеження


є лінійними функціями, а функція є сумою лінійної і квадратичної функції:

такер програмування лагранж функція


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



При цьому передбачається, що - симетрична матриця (матриця називається симетричною, якщо ).

Запишемо задачу квадратичного програмування в матричній формі:



при


(6)


Як і в загальному випадку рішення завдань нелінійного програмування, для визначення глобального екстремуму завдання квадратичного програмування не існує ефективного обчислювального методу, якщо не відомо, що будь-який локальний екстремум одночасно і глобальний. Оскільки в завданні (6) безліч допустимих рішень опукла, то, якщо цільова функція увігнута, будь-який локальний максимум глобальний. Якщо ж цільова функція опукла, то будь-який локальний мінімум так само і глобальний.

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

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

Квадратична форма називається відємно визначеною, якщо для усіх , окрім .

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

Квадратична форма називається додатньо визначеною (додатньо напіввизначеною), якщо квадратична форма - відємно визначена (відємно напіввизначена).

Квадратична форма називається невизначеною, якщо вона позитивна для одних значень і негативна для інших.

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

Приклад. Задана квадратична форма


.


Привести цю форму до канонічного виду.

Розвязок. Запишемо матрицю, що відповідає цій квадратичній формі:


.


Перепишемо форму , виділяючи члени, що містять :


.


Доповнюючи вираження, що стоїть в дужках, до повного квадрата, отримуємо



Припустимо, що


(7)

запишемо квадратичну форму в наступному виді:



де



Із співвідношень (7) маємо


(8)


Перетворимо :



Нехай


(9)


звідки


(10)

Тоді

Остаточно маємо

Для безпосереднього виразу через можна скористатись добутком перетворень (8) і (10), визначивши відповідну матрицю перетворень. Перетворенню (8) відповідає матриця



Перетворенню (10) - матриця



Знайдемо матрицю :



Знайдемо матрицю :



Матриця відповідає квадратичній формі . Остаточно отримуємо


.


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

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

Теорема 2. Якщо для квадратичної форми



якщо визначники відмінні від нуля, то цю форму можна трикутним перетворенням привести до виду

(11)


Доведення. Оскільки , то, виділяючи перший квадрат, отримуємо



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



Оскільки , то можна виділити ще один квадрат.

Таким чином, процес послідовного виділення квадратів за допомогою трикутних перетворень можна продовжувати до тих пір, поки форма не буде приведена до канонічного виду. Виходячи з того, що визначники (11) інваріантні відносно трикутних перетворень, отримуємо співвідношення . Матриця наводиться до діагонального виду, при цьому :

….………………………….


або. Оскільки відмінні від нуля, то. Теорема доведена. Таким чином, знаки коефіцієнтів визначаються знаками визначників .

Випадок 1. Якщо усі визначники позитивні, то і усі коефіцієнти позитивні, отже, квадратична форма позитивно визначена.

Випадок 2. Якщо у ряді знаки чергуються, то усі коефіцієнти негативні, в цьому випадку форма є негативно визначеною.

Випадок 3. Якщо ранг матриці рівний , то вона буде позитивно напіввизначеною, якщо перші визначників її позитивні, а інші дорівнюють нулю.

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

Випадок 4. Якщо ранг матриці рівний , у ряді знаки чергуються і , то квадратична форма негативно напіввизначена.

Випадок 5. Якщо у ряді чисел немає чергування знаків, причому є негативні , то відповідна квадратична форма є невизначеною.

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



Розвязок. Маємо:



Ряд - знакозмінний, отже, квадратична форма - негативно визначена.

Повернемося до завдання (6), в якому вважаємо, що - увігнута функція. Обмеження в завданні лінійні, тому можна використати умови Куна-Такера (4) і (5) для отримання необхідних і достатніх умов оптимальності рішення. Складемо функцію Лагранжа для завдання (6):


(12)


Оскільки


то



Аналогічно маємо



Сформулюємо умову (4) для завдання (6). Якщо - оптимальний план завдання квадратичного програмування, то повинен існувати такий вектор , що задовольняє умові . Введемо допоміжний вектор



Тоді умову (4) можна записати так:


(13)


Умова (5) в даному випадку має вигляд . Оскільки обмеження в завданні представлені у вигляді рівнянь, то на вектор не накладається умова позитивності, умову виконується при будь-якому допустимому рішенні і його можна виключити. Отже, якщо існують і , ті, що задовольняють умовам

(14)


то вектор - оптимальне рішення задачі квадратичного програмування (6). Розглянемо методи рішення завдань квадратичного програмування.


3.Метод Біла


Метод Біла являє собою узагальнення симплексного метода лінійного програмування. При розвязку задач цим методом вихідним є яке-небудь базово-допустиме рішення системи обмежень.

Нехай задана задача квадратичного програмування:



де квадратична форма відмінно визначена, тобто функція увігнутості.

Припустимо, що систему рівнянь вдалося розвязати відносноперших змінних:


(15)


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


(15)


дедля усіх і .

Вираз, який стоїть у скобках при, не що інше, як. Зокрема, у вихідній точці (припускаючи, що вільні змінні дорівнюють нулю) маємо. Значення функціїв цій точці рівно. При такому представленні функціїумова Куна-Такера має дуже простий вигляд. Якщо всі похідні, то вихідна точка є оптимальним розвязком, так як збільшення будь-якої незалежної змінної призводить до зменшення значення, окрім того, в силу увігнутості функції одночасно збільшується декілька вільних змінних також призводить до збільшення значення функції. Якщо ж деякі з, тобто, то можна збільшити значення, збільшуючи одну з цих змінних, наприклад , залишаючи інші незалежна змінні рівними нулю. Зміна веде до змінення базових змінних. При деякому значенніодна із залежних змінних перетворюється на нуль і подальше збільшення змінної неможливо. Це має місце для лінійної функції, так як її частинні похідні - постійні величини. Для квадратичної функції похіднаможе перетворитись на нуль раніше, ніж одна з залежних змінних. Тоді подальше збільшення не має сенсу, так як значення функціїзнову починає зменшуватись.

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


(16)


Використовуючи вираз (16), виключимо з інших рівнянь (6) змінну . В результаті одержимо разом з (16) нову систему (17)


(17)


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



Таким чином, відмінність отриманого розвязку від початкового полягає у тому, що зміннііпомінялися місцями.

Розглянемо тепер випадок, коли похідна перетворюється в нуль всередині допустимої області. Введемо нову, не обмежену по знаку змінну, яка звязана з вільними змінними співвідношенням (18)


(18).


В якості другої точки в даній ситуації беремо точку, в якій , а також старі незалежні змінні, окрім, дорівнюють нулю. На основі співвідношень (18) можна представити у наступному вигляді:


(19)


За допомогою формули (19) перетворимо вирази для та інших залежних змінних. В результаті число базових змінних збільшилось на одиницю.

Від другої точки переходимо до третьої і так далі. При цьому останній випадок суттєво змінюється. Для необмежених по знаку змінних умова Куна-Такера має вигляд. Так як значеннянеобмежене по знаку, томожна збільшити, змінюючи(якщо , то збільшуємо значення , якщо , - то зменшуємо). Якщо необмежена по знаку змінна при цьому відмінна від нуля, то її необхідно виключити із виразу для й із рівності для базових змінних і в подальшому не приймати до уваги. При переході до наступної точки в першу чергу розглянемо можливість зміни необмежених по знаку змінних. Якщо ж всі, то у базис включають незалежну обмежене по знаку змінну. В результаті перетворень знаходять оптимальний розвязок задачі.

Приклад. Знайти при обмеженнях



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



Розвяжемо відносно базових змінних ісистему обмежень



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

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



Друга точка розвязку задачі: .

Так як , то додаємо в базис змінну і визначаємо можливі її зміни. Зі зростаннямзначення може тільки збільшуватись; перетворюється на нуль при , змінна перетворюється на нуль при, при. Тому виключимо з базису і введемо змінну.

Для третьої точки маємо:



Третя точка розвязку задачі:



Тепер збільшимо значення функції , збільшуючи . Зміннаперетворюється в нуль при , при при збільшенні збільшується;перетворюється на нуль при . Звідси слідує, що замість вводимо нову змінну. Визначимо координати четвертої точки:



Четверта точка розвязку:


Похідна, а , тому четверта точка дає оптимальний розвязок задачі.

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

Для спрощення обчислення значень і для кожної ітераційної точки можна представити у вигляді таблиці. У верхній частині таблиці записати коефіцієнти системи (15). До них додаються рядки, які відповідають обмеженням по знаку змінних, які не входять до базису. Для цей рядок матиме одиницю на перетині зм стовпчиком і нулі на перетині з іншими стовпчиками. В нижній частині таблиці записуються коефіцієнти функції , представлені у вигляді (15). Ця таблиця зображена нижче (табл. 1).


Таблиця 1

1001…0000…11

Сформулюємо правила переходу від однієї таблиці до іншої.

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

.Ділять елемент , вибраний у відповідності до правила 1, на модуль відповідного діагонального елементу нижньої частини таблиці . Порівнюють одержане число з частками від ділення нам модуль, знак яких співпадає зі знаком . Рядок, який дає мінімум цих співвідношень, є направляючим. Елемент, який знаходиться на перетині направляючого рядка та направляючого стовпчика, називається розвязуючим. Якщо направляючий рядок знаходиться у верхній половині таблиці, то у проміжній таблиці на місці змінної, яка відповідає направляючому стовпчику, записують змінну, яка відповідає направляючому рядку. Якщо остання змінна знаходиться в нижній частині, то замінюється на нову змінну.

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

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

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


(20)


Елементи іобчислюють по аналогічним формулам.

6.Верхню частину завершальної таблиці переписують без змін з проміжної.

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

Щоб одержати -й рядок нижньої частини кінцевої таблиці, від елементів цього рядка в проміжній таблиці обчислюють елемент другого направляючого рядка, множення на елемент вихідної таблиці, знаходиться на перетині першого направляючого рядка і -го стовпчика. В табл. 2-8 приведено розвязок задачі.


Перелік посилань


1.Кузнецов Ю.Н., Кузубов В.Н. «Математическое программирование» - Москва: Высшая школа, 1980. - 300 с.

2.Абрамов Л.М., Капустин В.Ф. «Математическое программирование.» Ленинград, Изд-во Ленинград. ун-та, 1976. - 184 с.

.Степанюк В.В. Методи математичного програмування Київ: Вища школа, 1997. - 272 с.

.Романюк Т.П., Терещенко Т.О., Присенко Г.В., Городкова І.М. Математичне програмування: Навч. посіб. - Київ: ІЗМН, 1996. - 312 с.

.«Велика Радянська Енциклопедія» / Третє видання - Москва: Велика Радянська Енциклопедія, 1971.



Метод Біла для розвязку задач квадратичного програмування 1.Теорема Куна-Такера Центра

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ