WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Задачі нелінійного програмування. Деякі основні методи їх розв'язування та аналізу - Реферат

Задачі нелінійного програмування. Деякі основні методи їх розв'язування та аналізу - Реферат


Реферат на тему:
Задачі нелінійного програмування. Деякі основні методи їх розв'язування та аналізу.
План.
1. Задачі квадратичного програмування (КП) та основні методи їх розв'язання.
2. Економічна постановка та математичні моделі окремих задач КП.
3. Література
Задачі квадратичного програмування та основні методи їх розв'язування.
Любий локальний максимум в задачі випуклого програмування являється глобальним максимумом.
Визначення 1: Функцією Лагранжа в задачі випуклого програмування (24)-(26) називається функція
де - множники Лагранжа.
Визначення 2: Точка
називається сідловою точкою функції Лагранжа, якщо
для всіх і
Теорема 2: (Теорема Куна-Таккера). Для задачі випуклого програмування (24)-(26), багато допустимих розв'язань які володіють регулярністю, являються оптимальним планом тоді і тільки тоді, коли існує такий вектор - сідлова точка функції Лагранжа
Якщо допустити, що цільова функція і функції неперервно диференціюють, то теорема Куна-Таккера може бути доповнена аналітичними вираженнями, визначеними необхідними достатніми умовами того, щоб точка була сідловою точкою функції Лагранжа, тобто була розв'язком задачі випуклого програмування. Ці вирази мають такий вид:
де та - значення відповідних частинних похідних функції Лагранжа, обчислених в сідловій точці. Усім вище вказаним вимогам, які дозволяють записати необхідні та достатні умови для сідлової точки функції Лагранжа у вигляді виразів
Визначення 1. Квадратичною формою відносно змінних називається числова функція від цих змінних, що має наступний вид
Визначення 2. Квадратична форма F називається позитивно (негативно) визначеною, якщо для всіх значень змінних , крім .
Визначення 3. Квадратична форма називається позитивно(негативно)-напіввизначеною, якщо для будь-якого набору значень змінних й, крім того, існує такий набір змінних , де не всі значення змінних одночасно дорівнюють нулю, що .
Теорема 1. Квадратична форма є опуклою функцією, якщо вона позитивно-напіввизначена, і увігнутою функцією, якщо вона негативно - напіввизначена.
Визначення 4. Задача, що складається у визначенні максимального (мінімального) значення функції
f(x) = (7)
при обмеженнях
(8)
хj , (9)
де - негативно(позитивно)-напіввизначена квадратична форма, називається задачею квадратичного програмування.
Для сформульованої задачі квадратичного програмування функція Лагранжа записується у вигляді:
Якщо функція має сідлову точку , то в цій точці виконуються співвідношення (1) - (6). Вводячи тепер доповнюючі змінні й , обертаючі нерівності (1) й (4) у рівності, перепишемо вираження (1) - (6), записані для задачі квадратичного програмування, у такому вигляді:
(14)
Таким чином, щоб знайти розв'язок задачі квадратичного програмування (7) (9), потрібновизначити невід'ємний розв'язок систем лінійних рівнянь (10) та (11), яке задовольняє умову (12) та (13). Цей розв'язок можна знайти за допомогою методу штучного базису, застосованого для знаходження максимального значення функції при умовах (10), (11), (14) з врахуванням (12) та (13). Тут - штучні змінні, введені в рівняння (10) та (11).
Використовуючи метод штучного базису і додатково з огляду на умови (12) та (13), після кінцевих етапів, одержимо оптимальний план вихідної задачі.
Отже, процес знаходження розв'язку задачі квадратичного програмування (7) - (9) включає наступні етапи:
1. Складають функцію Лагранжа.
2. Записують у вигляді виражень (10) - (14) необхідні і достатні умови існування сідлової точки для функції Лагранжа.
3. Використовують метод штучного базису, або установлюють відсутність сідлової точки для функції Лагранжа, або знаходять її координати.
4. Записують оптимальний розв'язок вихідної задачі і знаходять значення цільової функції.
1. Знайти максимальне значення функції
(15)
при умовах:
(16)
(17)
Розв'язок. Функція f є увігнутою, тому що представляє собою суму лінійної функції (яку можна розглядати як увігнутою) і квадратичної форми , що є негативно-визначенною отже, є також увігнутою. Система обмежень задачі включає тільки лише лінійні нерівності. Отже, можна скористатися теоремою Кун-Танккера. Складемо функцію Лагранжа
запишемо у вигляді виразів (10) - (14) необхідні і достатні умови існування сідлової точки побудованої функції:
(18)
(19)
(20)
Систему лінійних нерівностей (18) перепишемо в такий спосіб:
(21)
Вводячи додаткові ненегативні змінні , що перетворюють нерівності (18) у рівність:
(22)
(23)
З огляду на рівності (22), можна записати:
(24)
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.270-274.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с.
Loading...

 
 

Цікаве