Труднощі розв’язування задач нелінійного програмування

Постановка задачі

Приклади задач нелінійного програмування

Метод множників Лагранжа

Труднощі розв’язування задач нелінійного програмування

Постановка задачі

План

ЛЕКЦІЯ 13-15. Постановка задачі нелінійного програмування

Розв’язуючи задачі оптимального управління (планування), дово­диться враховувати нелінійний характер взаємозв’язків між економічними показниками. У загальному вигляді нелінійна економіко-математична модель має вигляд:

за умов

,

де і — нелінійні функції.

Задачу нелінійного програмування намагаються звести до лінійного вигляду. Проте в такому разі можливі значні похибки. Нехай, наприклад, собівартість продукції y визначено як функцію , де х — обсяги виробництва. Ввівши заміну , дістанемо лінійну залежність . За такої заміни похибки немає. А коли , то заміна цієї залежності деякою лінійною функцією призводить до значних похибок, що ілюструє рис. 1.

Рис. 1.

У точках х ₁ і х ₃ значення собівартості для обох розглядуваних функцій однакові, але в усіх інших точках ці значення відрізняються, причому в точці х ₂ значною мірою:

.

Отже, лінеаризація нелінійних процесів є досить складною математичною задачею.

Для лінійних задач можна завжди знайти оптимальний розв’я­зок універсальним методом — симплексним. При цьому немає проблеми з доведенням існування такого розв’язку. Адже в результаті розв’язування задачі симплексним методом завжди дістаємо один із варіантів відповіді: 1) знайдено розв’язок; 2) задача суперечлива, тобто її розв’язку не існує; 3) цільова функція необмежена, отже, розв’язку також немає.

Для задач нелінійного програмування не існує універсального методу розв’язування, тому щоразу слід доводити існування розв’язку задачі, а також його єдиність. Це досить складна математична задача.

Відомі точні методи розв’язування нелінійних задач, але при цьому постають труднощі обчислювального характеру. Навіть для сучасних ПЕОМ відповідні алгоритми є доволі трудомісткими.

Для розв’язування нелінійних задач застосовують наближені методи, стикаючись із проблемою локальних і глобальних оптимумів. Наприклад, на рис. 2. маємо на відрізку локальні оптимуми в точках х ₀, х ₁, х ₂, х ₃, х ₄, х ₅, х ₆, х ₇, х ₈, х ₉, а глобальний — у точці х ₄ і х ₆.

Рис. 2

Більшість наближених методів дають змогу знаходити локальний оптимум. Визначивши всі локальні оптимуми, методом порівняння можна знайти глобальний. Проте для практичних розрахунків такий метод не є ефективним. Часто наближені методи не «вловлюють» глобального оптимуму, зокрема тоді, коли глобальний оптимум лежить досить близько до локального. Якщо відрізок [ x ₀, x ₁₀] розіб’ємо на десять підвідрізків і глобальний оптимум потрапить у відрізок [ x_i, x_{i +1}] (див. рис. 6.4), а ліворуч від x_i та праворуч від x_{i +1} крива y = f (x) підніматиметься, то глобальний оптимум буде пропущеним. Звернемо увагу ще на один дуже важливий момент. У задачах лінійного програмування точка оптимуму завжди була граничною. Для нелінійних задач точка, яка є оптимальним планом, може бути граничною або такою, що міститься всередині допустимої області розв’язків (планів).

Дата добавления: 2014-10-31