У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування.
Зрозуміло, що ряд економічних задач допускають такі математичні моделі, до яких невідомі або деяка їх частина входять нелінійно. Наприклад, нехай критерієм оптимальності є собівартість одиниці виробленої продукції. Очевидно, що вона залежить від розміру підприємства. Так, із збільшенням обсягу продукції собівартість її зменшується. Проте таке зменшення не безмежне. Настає такий момент, коли внутрішні витрати підприємства починають зростати (збільшуються витрати на перевезення, збереження продукції тощо), що у свою чергу призводить до збільшення собівартості. Функція, яка і спадає, і зростає, вже не може бути лінійною. Крім того, якщо врахувати в моделях лінійного програмування інші можливі випадки, то ці моделі трансформуються також в нелінійні. Наприклад, припустивши, що в задачі про використання ресурсів обсяг реалізації впливає на прибуток, маємо цільову функцію з нелінійністю.
Отже, лінійні моделі ми можемо вважати першим наближенням реальної задачі. У тих випадках, коли існує широкий вибір допустимих планів і наше уявлення про характер оптимального зв'язку не зовсім повне, лінійні моделі можуть бути неадекватними.
У більшості випадків нелінійність моделі обумовлюється, як правило, структурними співвідношеннями економічного процесу або непропорційністю зміни витрат, випуску продукції, показників якості.
У загальній постановці задачу нелінійного програмування (НЛП) записують так:
(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бласть розв'язків є незв'язною — складається з двох окремих частин. Маємо два однакових локальних мінімуми. Координати цих точок можна знайти як розв'язок системи рівнянь:
Легко перевірити, що маємо і два локальні максимуму.
Другие работы по теме:
Наведення усіх перестановок елементів множини
Перестановка як перевпорядкованість наборів елементів, об’єктів або функція, що задає таку перевпорядкованість. Всі можливі варіанти перестановок елементів множини за умови наявності трьох елементів за умови, що жоден елемент не залишається на місці.
Цілочислове програмування
Постановка задачі Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва.
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Побудова математичної моделі задачі лінійного програмування
Складання плану виробництва при максимальному прибутку. Введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. Розв’язування задачі лінійного програмування графічним методом та економічна інтерпретація отриманого розв’язку.
Автоматизований облік власників автомобілей
Розробка програми "Авто" для введення та збереження інформації про власників та їхні автомобілі. Побудова математичної моделі. Критерії вибору та пошуку даних. Структура введених та збережених у файлах програми даних. Алгоритм основної програми та її код.
Автоматизований аналіз злочинності по областям
Розробка програми "Злочин", що призначена для збереження та перегляду, а також автоматичного аналізу всієї інформації про злочинність. Порядок і основні принципи формування структури даних, постановка задачі. Написання та лістинг розробленої програми.
Математичне моделювання економічних систем
Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
Контроль доступу до вибраних файлів з веденням протоколу
Ведення протоколу роботи комп’ютера. Розробка програми для створення списку розширень файлів і занесення часу і дати доступу до них на мові програмування Асемблер. Виклик переривання 21h код-функції та занесення до регістрів. Алгоритм та лістинг програми.
Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
Аналіз успішності групи
Розробка програми мовою Turbo Pascal для автоматизації процесу перевірки оцінок та аналізу успішності групи, для збереження і перегляду всієї інформації стосовно навчання. Формальна постановка задачі, створення алгоритму та вихідного коду програми.
Створення програми "Залізничний вузол"
Використання мови програмування Turbo Pascal, алгоритмів та графічних примітивів модуля Graph. Розробка та реалізація програми для сортування вагонів з довільного порядку в порядок через один. Присвоєння початкових значень та сортувальний алгоритм.
Довідкова система по кримінальному праву
Створення довідкової системи по зменшенню витрат часу на здобуття інформації по кримінальному праву. Розробка алгоритму основної програми на мові програмування Turbo Pascal з підключенням модуля СRT, якій відповідає за графіку і DOS та працює з файлами.
Дослідження чисельних методів вирішення нелінійних рівнянь
В роботі розглянуто наближені методи розв'язку нелінійних рівнянь для методів Ньютона та хорд, складено блок-схеми та написано програму, за допомогою якої розв'язується задане рівняння. Аналіз рівняння, методів його розв'язання і результатів обрахунку.
Розробка гри "Життя"
Розробка програми для вирішення графічної задачі. При вирішенні задачі необхідно cтворювати програму у середовищі програмування Turbo Pascal. Розробка алгоритму функціонування програми і надання блок-схеми алгоритму. Демонстрація роботи програми.
Автоматизований аналіз злочинності
Створення програми "Аналізатор злочинності в регіоні". Структура зберігаючих даних. Неформальна постановка задачі. Алгоритм основної програми. Введення і збереження інформації. Можливість перегляду всіх існуючих документів. Вихідний код програми.
Автоматизоване нарахування заробітної плати
Методика та особливості створення програми "Автоматизоване нарахування платні" для збереження, перегляду та аналізу введеної інформації, її алгоритм та вихідний код. Аналіз факторів, які впливають на формування заробітної платні робітника підприємства.
Автоматизована реєстрація і облік автомобілей
Розробка програми реєстрації автомобілів для збереження та перегляду інформації про модель машини, рік її випуску, об'єм двигуна і витрати палива. Складання алгоритмів розв'язання поставленої задачі та написання тексту програми в середовищі Turbo Pascal.
Створення програми гри "Шибениця"
Алгоритмічна мова програмування універсального призначення Turbo Pascal. Розробка і створення програми для гри "Шибениця". Алгоритм функціонування программи, блок-схема алгоритму. Використання додаткових модулів Graph та Crt у процессі створення програми.
База даних по приватним підприємствам регіону
Програма "Приватка" для збереження та перегляду всієї інформації, що стосується пошуку підприємства. Розробка алгоритму та програмування на мові Turbo Pascal. Формальна та неформальна постановка задачі. Структура зберігаючих даних. Вихідний код програми.
Наближені методи розв’язку нелінійних рівнянь
В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.
Лінійне програмування
Транспортна задача Розв'язок задач лінійного програмування. Транспортна задача. Мета роботи: Набути навичок складання математичної моделі транспортної задачі та її реалізації з використанням табличного процесору Excel
Розробка гри Життя
Міністерство освіти і науки України Полтавський національний технічний університет імені Юрія Кондратюка Факультет інформаційних та телекомунікаційних технологій і систем
База даних по приватних підприємствах регіону
Міністерство внутрішніх справ України Харківський національний університет внутрішніх справ Навчально-науковий інститут менеджменту, соціальних та інформаційних технологій Кафедра інформаційних систем і технологій в діяльності ОВС
Мовне забезпечення САПР
: Мовне (лінгвістичне) забезпечення САПР. Призначення, структура та вимоги до мовного забезпечення. Мовне проектування. Мови програмування. 1. Мови забезпечення САПР включають в себе мови проектування та мови програмування і охоплює терміни, визначення, правила формалізації звичайної мов, методи стиснення та розширення.