Название: Задачі нелінійного програмування. Деякі основні методи їх розвязування та аналізу
Вид работы: реферат
Рубрика: Информатика
Размер файла: 103.56 Kb
Скачать файл: referat.me-131706.docx
Краткое описание работы: Реферат на тему: Задачі нелінійного програмування. Деякі основні методи їх розв’язування та аналізу. План. 1. Метод Франка-Вулфа. 2. Приклади розв’язування задач.
Задачі нелінійного програмування. Деякі основні методи їх розвязування та аналізу
Реферат на тему:
Задачі нелінійного програмування. Деякі основні методи їх розв’язування та аналізу.
План.
1. Метод Франка-Вулфа.
2. Приклади розв’язування задач.
3. Література
Деякі з основних методів розв’язування задач НЛП.
1. Метод Франка –Вулфа . Нехай потрібно найти максимальне значення вогнутой функції
(57)
при умовах : (58)
(59)
Характерною особливістю цієї задачі являється то , що її система обмеження вміщує тільки лінійні нерівності . Ця особливість являє основний для заміни в межах досліджуваної точки нелінійної цільової функції лінійною , завдяки чому розв’язок даної задачі зводиться до послідовного розв’язку задач лінійного програмування.
Процес найдення розв’язку задачі начинають з оприділення точки , принадлежавшої області допустимих розв’язків задачі.
Нехай ця точка , тоді в цій точці вираховують градієнт функції (57)
і будують лінійну функцію
(60)
Потім знаходять максимальне значення цієї функції при обмеженнях (58) і (59). Нехай рішення даної задачі визначається точкою . Тоді за новий допустимий розв’язок даної задачі приймають координати точки
(61)
де -- деяке число , називають кроком вирахуваним і закінченням між нулем і одиницею
. Це число
беруть довільно чи визначають таким способом , щоб значення функції в точці
залежавши від , було максимальним . Для цього необхідно найти рішення рівності
і вибрати його найменший корінь . Якщо його значення більше одиниці , то слідує покласти
. Після визначення числа
находять координати точки
вираховують значення цільової функції в ній і виясняють необхідність переходу до нової точки
. Якщо така необхідність має , то вираховують в точці
градієнт цільової функції , переходять до даної задачі лінійного програмування і находять її розв’язок . Визначають координати точки
і досліджують необхідність проведення подальших обчислень . Після кінцевого числа отримують з необхідною точністю розв’язок даної задачі .
Отже, процес находження розв’язків задачі (57) – (59) методом Франка – Вулфа включає наступні етапи :
1. Визначають даний допустимий розв’язок задачі .
2. Находять градієнт функції (57) в точці допустимого розв’язку .
3. Будують функцію (60) і находять її максимальне значення при умовах (58) і (59) .
4. Визначають крок обчислень .
5. По формулам (61) находять компоненти нового допустимого розв’язку .
6. Провіряють необхідність переходу до наступного допустимого розв’язку . У випадку необхідності переходять до етапу 2 , в поганому випадку найдене прийняте розв’язок даної задачі .
3.27. Методом Франка – Вулфа найти розв’язок задачі 3.22. , забезпеченої в певному максимальному значенні функції
(62)
при умовах
(63) (64)
Розв’язок . Найдем градієнт функції
і в якості даного допустимого розв’язку задачі візьмемо точку а в якості критерія оцінки якості одержимо розв’язок – нерівності
де
.
1. Ітерація . В точці градієнт
.Знаходимо максимальне значення функції
(65)
при умовах (63) і (64)
(66)
(67)
Задача (65)—(67) має оптимальний план .
Найдемо новий допустимий розв’язок даної задачі по формулі (61):
, де
. (68)
Підставимо замість і
їх значення , отримаємо
(69)
Знайдемо тепер число . Підкладемо в рівність (62) замість
і
із значення у відповідності з відношенням (69)
,
знайдемо подібну цій функції по і прирівняємо її нулю :
.Розв’язуючи цю рівність , отримаємо
.
Оскільки найдене значення заключне між 0 і 1 , приймаючи його за величину кроку .Таким образом ,
.
2. Ітерація . Градієнт цільової функції даної задачі в точці є
. Находимо максимальне значення функції
при умовах (63) і (64) . Рішення являється
.
Оприділяєм тепер .Останню рівність перепишемо наступним образом :
Підкладемо тепер в функцію (62) замість і
їх значення у відношенні з відношенням (70) , отримаємо
звідки . Прирівняємо
нулю і розв’язуючи отримаємо рівність , знаходимо
. Таким образом ,
т.е.
.
3. Ітерація . Градієнт функції f в точці є
. Находимо максимальне значення функції
при умовах (63) і (64). Розв’язком буде
.
Знайдемо . Маємо
Розв’язуючи рівність , находимо
. Слідуючи ,
,
,
.
Таким образом , являється задовільним розв’язком даної задачі . Дана точка
находиться достатньо близько до точки максимального значення цільової функції
, найденої при розв’язку цієї задачі в п. 3.3. Задав меншу величину
, можна було , зробивши доповнюючи приближення , ще ближче підійти до точки максимального значення цільової функції.
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут післядипломної освіти) “Інтелект - Захід”, 2004. – 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. – Вища школа, 1985-319с.,ст.270-274.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута”, 1998.-168 с.
Похожие работы
-
Різницевий метод розв язування звичайних диференціальних рівнянь Апроксимація Метод прогонки
Різницевий метод розв'язування звичайних диференціальних рівнянь. Апроксимація. Метод прогонки Розглянемо задачу: [0, 1] розіб'ємо на n частин, Розглянемо розклади
-
Задачі нелінійного програмування
У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування.
-
Метод Стрілянини
Вступ На даний момент велика роль в розвитку сучасного світу відводиться підвищенню технічного рівня обчислювальної техніки, пристроїв і засобів автоматизації. Це передбачає розвиток виробництва і широке використання промислових роботів, систем автоматичного управління з використанням мікропроцессорів і мікро-ЕОМ, створення гнучких автоматизованих виробництв.
-
Наближене розв язування рівнянь графічне відокремлення коренів методи проб хорд і дотичних Д
Пошукова робота на тему: Наближене розв’язування рівнянь: графічне відокремлення коренів, методи проб, хорд і дотичних. Дотична і нормаль до кривої.
-
Обернені тригонометричні функції Тригонометричні рівняння і нерівності
Реферат Н а Т Е М У: “Обернені тригонометричні функції. Тригонометричні рівняння і нерівності” ОБЕРНЕНІ ТРИГОНОМЕТРИЧНІ ФУНКЦІЇ. РОЗВЯЗУВАННЯ НАЙПРОСТІШИХ ТРИГОНОМЕТРИЧНИХ РІВНЯНЬ І НЕРІВНОСТЕЙ
-
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Пошукова робота на тему: Основні поняття математичного програмування. Побудова моделі задачі лінійного програмування 1. Мета і предмет математичного програмування.
-
Розвязання задачі Коші для звичайного диференціального рівняння першого порядку методом Ейлера
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Кафедра інформатики КУРСОВА РОБОТА З програмування На тему: “Розв’язання задачі Коші для звичайного диференціального рівняння першого порядку методом Ейлера”
-
Розробка алгоритмів та складання програм на мові програмування MS VisualBasic for Application
Полтавський університет споживчої кооперації України Факультет економіки та менеджменту Кафедра економічної кібернетики Звіт про виконання індивідуальних завдань
-
Лінійне програмування
Транспортна задача Розв'язок задач лінійного програмування. Транспортна задача. Мета роботи: Набути навичок складання математичної моделі транспортної задачі та її реалізації з використанням табличного процесору Excel
-
Загальна задача лінійного програмування і деякі з методів її розвязування
Реферат на тему: Загальна задача лінійного програмування і деякі з методів її розв’язування. План. Модифікований симплекс-метод розв’язування задач лінійного програмування.