Задачi нелiнiйного програмування
У задачах лiнiйного програмування, якi розглядалися ранiше, всi невiдомi входили як до системи обмежень, так i до цiльової функцiї, у першому степенi. Тому цi задачi були досить простими у постановцi i за методами розв'язування.
продукцiї. Очевидно, що вона залежить вiд розмiру пiдприємства. Так, iз збiльшенням обсягу продукцiї собiвартiсть її зменшується. Проте таке зменшення не безмежне. Настає такий момент, коли внутрiшнi витрати пiдприємства починають зростати (збiльшуються витрати на перевезення, збереження продукцiї тощо), що у свою чергу призводить до збiльшення собiвартостi. Функцiя, яка i спадає, i зростає, вже не може бути лiнiйною. Крiм того, якщо врахувати в моделях лiнiйного програмування iншi можливi випадки, то цi моделi трансформуються також в нелiнiйнi. Наприклад, припустивши, що в задачi про використання ресурсiв обсяг реалiзацiї впливає на прибуток, маємо цiльову функцiю з нелiнiйнiстю.
Отже, лiнiйнi моделi ми можемо вважати першим наближенням реальної задачi. У тих випадках, коли iснує широкий вибiр допустимих планiв i наше уявлення про характер оптимального зв'язку не зовсiм повне, лiнiйнi моделi можуть бути неадекватними.
У бiльшостi випадкiв нелiнiйнiсть моделi обумовлюється, як правило, структурними спiввiдношеннями економiчного процесу або непропорцiйнiстю змiни витрат, випуску продукцiї, показникiв якостi.
У загальнiй постановцi задачу нелiнiйного програмування (НЛП) записують так:
(1)
(max)z(x1, x2, …, xn), (2)
де F1(x), …, Fn(x),z(x), x=(x1, x2, …,xn) – довiльнi функцiї. У конкретних задачах частина обмежень (або всi) можуть бути нерiвностями. Крiм того, на невiдомi можуть накладатися умови невiд'ємностi i т. п.
Однiєю з основних особливостей задач НЛТ є можливiсть рiзними способами задавати цiльову функцiю. Якщо в лiнiйному випадку вона була строго монотонною i досягала свого оптимального значення лише у вершинi многокутника розв'язку; то тут картина зовсiм iнша. Наприклад! навiть графiк функцiї, однiєї змiнної, свiдчить про те, що вона вже має багато локальних максимумiв.
Друга особливiсть задач НЛП випливає iз порушення властивостi опуклостi многокутника розв'язкiв задач ЛП. Легко навести приклади задач, де область розв'язкiв задачi НЛП буде багатозв'язною.
Геометрична iнтерпретацiя задач, нелiнiйного програмування
Приклад 1. Знайти найбiльше i найменше значення функцiї
за таких обмежень:
Система обмежень лiнiйна, тому область розв'язкiв складається з многокутника розв'язкiв.
Неважко помiтити, що цiльову функцiю можна записати таким чином:
. Отже z є квадратом радiуса кола. При фiксованому z маємо коло з центром у точцi, а найбiльше концентричне коло буде проходити через точку многокутника розв'язкiв. Тому
zmin= (6-l)2 + (0-2)2 = 29.
Аналогiчно zmax — (1 — І)2 + (2 — 2)2 = 0. В даному випадку найменше значення функцiї мiститься в областi розв'язкiв, а найбiльше — на її границi. Якщо в цьому ж прикладi розглянути функцiю z = (x1 — 4)2 + (х2 — 4)2.
zmin=
Приклад 2. Знайти найбiльше i найменше значення функцiї
Легко перевiрити, що маємо i два локальнi максимуму.
|