Реферат на тему:
Задачі нелінійного програмування. Деякі основні методи їх розв’язування та аналізу.
План.
1. Метод Франка-Вулфа.
2. Приклади розв’язування задач.
3. Література
Деякі з основних методів розв’язування задач НЛП.
Метод Франка –Вулфа . Нехай потрібно найти максимальне значення вогнутой функції
(57)
при умовах : (58)
(59)
Характерною особливістю цієї задачі являється то , що її система обмеження вміщує тільки лінійні нерівності . Ця особливість являє основний для заміни в межах досліджуваної точки нелінійної цільової функції лінійною , завдяки чому розв’язок даної задачі зводиться до послідовного розв’язку задач лінійного програмування.
Процес найдення розв’язку задачі начинають з оприділення точки , принадлежавшої області допустимих розв’язків задачі.
Нехай ця точка , тоді в цій точці вираховують градієнт функції (57)
і будують лінійну функцію
(60)
Потім знаходять максимальне значення цієї функції при обмеженнях (58) і (59). Нехай рішення даної задачі визначається точкою . Тоді за новий допустимий розв’язок даної задачі приймають координати точки
(61)
де -- деяке число , називають кроком вирахуваним і закінченням між нулем і одиницею . Це число беруть довільно чи визначають таким способом , щоб значення функції в точці
залежавши від , було максимальним . Для цього необхідно найти рішення рівності і вибрати його найменший корінь . Якщо його значення більше одиниці , то слідує покласти . Після визначення числа находять координати точки вираховують значення цільової функції в ній і виясняють необхідність переходу до нової точки . Якщо така необхідність має , то вираховують в точці градієнт цільової функції , переходять до даної задачі лінійного програмування і находять її розв’язок . Визначають координати точки і досліджують необхідність проведення подальших обчислень . Після кінцевого числа отримують з необхідною точністю розв’язок даної задачі .
Отже, процес находження розв’язків задачі (57) – (59) методом Франка – Вулфа включає наступні етапи :
Визначають даний допустимий розв’язок задачі .
Находять градієнт функції (57) в точці допустимого розв’язку .
Будують функцію (60) і находять її максимальне значення при умовах (58) і (59) .
Визначають крок обчислень .
По формулам (61) находять компоненти нового допустимого розв’язку .
Провіряють необхідність переходу до наступного допустимого розв’язку . У випадку необхідності переходять до етапу 2 , в поганому випадку найдене прийняте розв’язок даної задачі .
3.27. Методом Франка – Вулфа найти розв’язок задачі 3.22. , забезпеченої в певному максимальному значенні функції
(62)
при умовах
(63) (64)
Розв’язок . Найдем градієнт функції
і в якості даного допустимого розв’язку задачі візьмемо точку а в якості критерія оцінки якості одержимо розв’язок – нерівності де .
1. Ітерація . В точці градієнт .Знаходимо максимальне значення функції
(65)
при умовах (63) і (64)
(66)
(67)
Задача (65)—(67) має оптимальний план .
Найдемо новий допустимий розв’язок даної задачі по формулі (61):
, де . (68)
Підставимо замість і їх значення , отримаємо
(69)
Знайдемо тепер число . Підкладемо в рівність (62) замість і
із значення у відповідності з відношенням (69)
,
знайдемо подібну цій функції по і прирівняємо її нулю :
.Розв’язуючи цю рівність , отримаємо .
Оскільки найдене значення заключне між 0 і 1 , приймаючи його за величину кроку .Таким образом ,
.
Ітерація . Градієнт цільової функції даної задачі в точці є . Находимо максимальне значення функції при умовах (63) і (64) . Рішення являється .
Оприділяєм тепер .Останню рівність перепишемо наступним образом :
Підкладемо тепер в функцію (62) замість і їх значення у відношенні з відношенням (70) , отримаємо
звідки . Прирівняємо нулю і розв’язуючи отримаємо рівність , знаходимо . Таким образом ,
т.е. .
3. Ітерація . Градієнт функції f в точці є . Находимо максимальне значення функції при умовах (63) і (64). Розв’язком буде .
Знайдемо . Маємо
Розв’язуючи рівність , находимо . Слідуючи , ,, .
Таким образом , являється задовільним розв’язком даної задачі . Дана точка находиться достатньо близько до точки максимального значення цільової функції , найденої при розв’язку цієї задачі в п. 3.3. Задав меншу величину , можна було , зробивши доповнюючи приближення , ще ближче підійти до точки максимального значення цільової функції.
Література.
Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2003.- 452 с.
Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут післядипломної освіти) “Інтелект - Захід”, 2004. – 448 с.
Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. – Вища школа, 1985-319с.,ст.270-274.
Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.
Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута”, 1998.-168 с.
Другие работы по теме:
Налагоджування та програмування промислового робота МП-9С
Основні системи у складі промислового робота: виконавча (рушійна), керуюча (інтелектна), інформаційно-вимірювальна (сенсорна) та система зв'язку. Налагоджування та програмування робота, основні режими роботи. Розробка програми для виконання операцій.
Цілочислове програмування
Постановка задачі Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва.
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Функціональне відображення поведінки споживача
1. Геометричне подання зміни попиту при зміні доходу й цін Припустимо змінюється доход ( ). Його збільшення або зменшення еквівалентно паралельному зсуву бюджетної прямої. Зі зміною доходу змінюється й попит на товари. На кожній бюджетній прямій можна знайти точку рівноваги, в якій забезпечується максимум функції корисності
Автоматизований аналіз злочинності по областям
Розробка програми "Злочин", що призначена для збереження та перегляду, а також автоматичного аналізу всієї інформації про злочинність. Порядок і основні принципи формування структури даних, постановка задачі. Написання та лістинг розробленої програми.
Системи автоматизованого проектування
Організаційні основи розробки систем автоматизованого проектування на виробництві, їх впровадження і експлуатація. Загальні відомості про мікропроцесорні пристрої і системи. Основні поняття, визначення, постановка й розв’язок простих оптимізаційних задач.
Контроль доступу до вибраних файлів з веденням протоколу
Ведення протоколу роботи комп’ютера. Розробка програми для створення списку розширень файлів і занесення часу і дати доступу до них на мові програмування Асемблер. Виклик переривання 21h код-функції та занесення до регістрів. Алгоритм та лістинг програми.
Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
Аналіз успішності групи
Розробка програми мовою Turbo Pascal для автоматизації процесу перевірки оцінок та аналізу успішності групи, для збереження і перегляду всієї інформації стосовно навчання. Формальна постановка задачі, створення алгоритму та вихідного коду програми.
Створення програми "Залізничний вузол"
Використання мови програмування Turbo Pascal, алгоритмів та графічних примітивів модуля Graph. Розробка та реалізація програми для сортування вагонів з довільного порядку в порядок через один. Присвоєння початкових значень та сортувальний алгоритм.
Довідкова система по кримінальному праву
Створення довідкової системи по зменшенню витрат часу на здобуття інформації по кримінальному праву. Розробка алгоритму основної програми на мові програмування Turbo Pascal з підключенням модуля СRT, якій відповідає за графіку і DOS та працює з файлами.
Дослідження чисельних методів вирішення нелінійних рівнянь
В роботі розглянуто наближені методи розв'язку нелінійних рівнянь для методів Ньютона та хорд, складено блок-схеми та написано програму, за допомогою якої розв'язується задане рівняння. Аналіз рівняння, методів його розв'язання і результатів обрахунку.
Автоматизований аналіз злочинності
Створення програми "Аналізатор злочинності в регіоні". Структура зберігаючих даних. Неформальна постановка задачі. Алгоритм основної програми. Введення і збереження інформації. Можливість перегляду всіх існуючих документів. Вихідний код програми.
Автоматизоване нарахування заробітної плати
Методика та особливості створення програми "Автоматизоване нарахування платні" для збереження, перегляду та аналізу введеної інформації, її алгоритм та вихідний код. Аналіз факторів, які впливають на формування заробітної платні робітника підприємства.
База даних по приватним підприємствам регіону
Програма "Приватка" для збереження та перегляду всієї інформації, що стосується пошуку підприємства. Розробка алгоритму та програмування на мові Turbo Pascal. Формальна та неформальна постановка задачі. Структура зберігаючих даних. Вихідний код програми.
Наближені методи розв’язку нелінійних рівнянь
В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.
Лінійне програмування
Транспортна задача Розв'язок задач лінійного програмування. Транспортна задача. Мета роботи: Набути навичок складання математичної моделі транспортної задачі та її реалізації з використанням табличного процесору Excel
Середовище програмування DELPHI 2 0
СЕРЕДОВИЩЕ ПРОГРАМУВАННЯ DELPHI 2.0 Зміст Основні елементи середовища 1. Головне вікно 2. Вікно форми 3. Вікно коду 4. Інспектор об’єктів Управління файлами проекту Delphi
Середовище програмування DELPHI 20
СЕРЕДОВИЩЕ ПРОГРАМУВАННЯ DELPHI 2.0 Зміст 5.Основні елементи середовища 2 a.1. Головне вікно 2 a.2. Вікно форми 2 a.3. Вікно коду 3 a.4. Інспектор об’єктів 3
Задачі нелінійного програмування
У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування.
Бухгалтерський облік 5
Київська Державна Академія Водного Транспорту КОНТРОЛЬНА РОБОТА з дисципліни ОХОРОНА ПРАЦІ Студентки МО - 4 Питання контрольної роботи Підприємницький пил
1998-09-29 - Методи дослiдження Основнi напрямки
База лекций и рефератов института КИМО www.kimo.non Методи педагогічних досліджень поділяються на 3 великі групи: 1) соціографічні методи (у нас вони називаються статистичні або соціологічні методи)
Роль цікавих задач при вивченні курсу алгебри та початків аналізу
Реферат на тему: Роль цікавих задач при вивченні курсу алгебри та початків аналізу. Шкільний курс математики відіграє важливу роль в системі загальноосвітньої підготовки учнів, формування в них діалектико-матеріалістичного світогляду, готовності до активної участі в сфері матеріального виробництва.
Мовне забезпечення САПР
: Мовне (лінгвістичне) забезпечення САПР. Призначення, структура та вимоги до мовного забезпечення. Мовне проектування. Мови програмування. 1. Мови забезпечення САПР включають в себе мови проектування та мови програмування і охоплює терміни, визначення, правила формалізації звичайної мов, методи стиснення та розширення.
Математичне забезпечення САПР
Тема : . Загальні поняття та вимоги до МЗ. Способи отримання математичних моделей. Постановка задач оптимізації. Класифікація і характеристика методів оптимізації.