Название: Задачі нелінійного програмування
Вид работы: реферат
Рубрика: Информатика
Размер файла: 20.88 Kb
Скачать файл: referat.me-133355.docx
Краткое описание работы: У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування.
Задачі нелінійного програмування
У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування.
Зрозуміло, що ряд економічних задач допускають такі математичні моделі, до яких невідомі або деяка їх частина входять нелінійно. Наприклад, нехай критерієм оптимальності є собівартість одиниці виробленої продукції. Очевидно, що вона залежить від розміру підприємства. Так, із збільшенням обсягу продукції собівартість її зменшується. Проте таке зменшення не безмежне. Настає такий момент, коли внутрішні витрати підприємства починають зростати (збільшуються витрати на перевезення, збереження продукції тощо), що у свою чергу призводить до збільшення собівартості. Функція, яка і спадає, і зростає, вже не може бути лінійною. Крім того, якщо врахувати в моделях лінійного програмування інші можливі випадки, то ці моделі трансформуються також в нелінійні. Наприклад, припустивши, що в задачі про використання ресурсів обсяг реалізації впливає на прибуток, маємо цільову функцію з нелінійністю.
Отже, лінійні моделі ми можемо вважати першим наближенням реальної задачі. У тих випадках, коли існує широкий вибір допустимих планів і наше уявлення про характер оптимального зв'язку не зовсім повне, лінійні моделі можуть бути неадекватними.
У більшості випадків нелінійність моделі обумовлюється, як правило, структурними співвідношеннями економічного процесу або непропорційністю зміни витрат, випуску продукції, показників якості.
У загальній постановці задачу нелінійного програмування (НЛП) записують так:
(1)
(max)z(x1, x2, …, xn), (2)
де F1(x), …, Fn(x),z(x), x=(x1, x2, …,xn) – довільні функції. У конкретних задачах частина обмежень (або всі) можуть бути нерівностями. Крім того, на невідомі можуть накладатися умови невід'ємності і т.п.
Однією з основних особливостей задач НЛТ є можливість різними способами задавати цільову функцію. Якщо в лінійному випадку вона була строго монотонною і досягала свого оптимального значення лише у вершині многокутника розв'язку; то тут картина зовсім інша. Наприклад! навіть графік функції, однієї змінної, свідчить про те, що вона вже має багато локальних максимумів.
Друга особливість задач НЛП випливає із порушення властивості опуклості многокутника розв'язків задач ЛП. Легко навести приклади задач, де область розв'язків задачі НЛП буде багатозв'язною.
Геометрична інтерпретація задач, нелінійного програмування
Для більшої наочності проілюструємо ці випадки графічно. Розглянемо випадок двох змінних з обмеженнями-нерівностями.
Приклад 1. Знайти найбільше і найменше значення функції
за таких обмежень:
Система обмежень лінійна, тому область розв'язків складається з многокутника розв'язків.
Неважко помітити, що цільову функцію можна записати таким чином:
. Отже z є квадратом радіуса кола. При фіксованому z маємо коло з центром у точці, а найбільше концентричне коло буде проходити через точку многокутника розв'язків. Тому
zmin= (6-l)2 + (0-2)2 = 29.
Аналогічно zmax — (1 — І)2 + (2 — 2)2 = 0. В даному випадку найменше значення функції міститься в області розв'язків, а найбільше — на її границі. Якщо в цьому ж прикладі розглянути функцію z = (x1 — 4)2 + (х2 — 4)2.
zmax=(4-0)2+(4-0)2=32,
zmin=
Приклад 2. Знайти найбільше і найменше значення функції
за таких обмежень:
Oбласть розв'язків є незв'язною — складається з двох окремих частин. Маємо два однакових локальних мінімуми. Координати цих точок можна знайти як розв'язок системи рівнянь:
Легко перевірити, що маємо і два локальні максимуму.
Похожие работы
-
Різницевий метод розв язування звичайних диференціальних рівнянь Апроксимація Метод прогонки
Різницевий метод розв'язування звичайних диференціальних рівнянь. Апроксимація. Метод прогонки Розглянемо задачу: [0, 1] розіб'ємо на n частин, Розглянемо розклади
-
Задачі нелінійного програмування. Деякі основні методи їх розвязування та аналізу
Реферат на тему: Задачі нелінійного програмування. Деякі основні методи їх розв’язування та аналізу. План. 1. Метод Франка-Вулфа. 2. Приклади розв’язування задач.
-
Лінійні однорідні диференціальні рівняння другого порядку з постійними коефіцієнтами
Характеристичне рівняння Загальний розв’язок лінійного однорідного диференціального рівняння з постійними коефіцієнтами 1. Лінійні диференціальні рівняння з сталими коефіцієнтами
-
База даних по приватних підприємствах регіону
Міністерство внутрішніх справ України Харківський національний університет внутрішніх справ Навчально-науковий інститут менеджменту, соціальних та інформаційних технологій Кафедра інформаційних систем і технологій в діяльності ОВС
-
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Пошукова робота на тему: Основні поняття математичного програмування. Побудова моделі задачі лінійного програмування 1. Мета і предмет математичного програмування.
-
Розвязання задачі Коші для звичайного диференціального рівняння першого порядку методом Ейлера
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Кафедра інформатики КУРСОВА РОБОТА З програмування На тему: “Розв’язання задачі Коші для звичайного диференціального рівняння першого порядку методом Ейлера”
-
Розробка алгоритмів та складання програм на мові програмування MS VisualBasic for Application
Полтавський університет споживчої кооперації України Факультет економіки та менеджменту Кафедра економічної кібернетики Звіт про виконання індивідуальних завдань
-
Допоміжні алгоритми
та тему: ДОПОМІЖНІ АЛГОРИТМИ Тема: Допоміжні алгоритми. Мета уроку: навчити учнів складати допоміжні алгоритми; виховати старанність, дисциплінованість;
-
Лінійне програмування
Транспортна задача Розв'язок задач лінійного програмування. Транспортна задача. Мета роботи: Набути навичок складання математичної моделі транспортної задачі та її реалізації з використанням табличного процесору Excel
-
Загальна задача лінійного програмування і деякі з методів її розвязування
Реферат на тему: Загальна задача лінійного програмування і деякі з методів її розв’язування. План. Модифікований симплекс-метод розв’язування задач лінійного програмування.