Розділ 4. Загальні відомості про задачі нелінійного програмування. Особливості їх розв’язку

У попередніх розділах було розглянуто методи розв'язування задач лінійного програмування та деякі типи задач, що певними нескладними перетвореннями зводяться до лінійних. Ці методи найкраще розроблені, легко реалізуються на ПЕОМ, а тому набу­ли широкого застосування в багатьох галузях науки, техніки та економіки. Проте лінійні моделі відображають лише певну й ве­льми обмежену сукупність властивостей навколишнього світу. Адже, скажімо, соціально-економічні процеси переважно не є лі­нійними. Галузі, об'єднання та окремі підприємства народного господарства функціонують і розвиваються за умов невизначено­сті, а тому адекватно їх можна описати нелінійними, стохастичними, динамічними моделями. Отже, для ефективного управлін­ня народним господарством в цілому, його галузями і окремими об'єктами господарювання потрібне застосування нелінійних економіко-математичних моделей та методів.

Зауважимо, що сучасний рівень розвитку комп'ютерної техні­ки і методів математичного моделювання створює передумови для застосування нелінійних методів, а це може суттєво підвищи­ти якість розроблюваних планів, надійність та ефективність рі­шень, які приймаються.

Досить детально розглянута в розділах, присвячених лінійно­му програмуванню, задача пошуку оптимальних обсягів вироб­ництва ґрунтується на допущеннях про лінійність зв'язку між ви­тратами ресурсів і обсягами виготовленої продукції; між ціною, рекламою та попитом тощо. Але такі зв'язки насправді є нелінійними, тому точніші математичні моделі доцільно формулювати в термінах нелінійного програмування.

Нехай для деякої виробничої системи необхідно визначити план випуску продукції за умови найкращого способу викорис­тання її ресурсів. Відомі загальні запаси кожного ресурсу, нор­ми витрат кожного ресурсу на одиницю продукції та ціни реалі­зації одиниці виготовленої продукції. Критерії оптимальності можуть бути різними, наприклад, максимізація виручки від реа­лізації продукції. Така умова подається лінійною залежністю загальної виручки від обсягів проданого товару та цін на оди­ницю продукції.

Однак, загальновідомим є факт, що за умов ринкової конкурен­ції питання реалізації продукції є досить складним. Обсяг збуту продукції визначається передусім її ціною, отже, як цільову функ­цію доцільно брати максимізацію не всієї виготовленої, а лише реалізованої продукції. Необхідно визначати також і оптималь­ний рівень ціни на одиницю продукції, за якої обсяг збуту був би максимальним. Для цього її потрібно ввести в задачу як невідому величину, а обмеження задачі мають враховувати зв'язки між ці­ною, рекламою та обсягами збуту продукції. Цільова функція в такому разі буде виражена добутком двох невідомих величин: оптимальної ціни одиниці продукції на оптимальний обсяг відпо­відного виду продукції, тобто буде нелінійною. Отже, маємо за­дачу нелінійного програмування.

Також добре відома транспортна задача стає нелінійною, як­що вартість перевезення одиниці товару залежить від загального обсягу перевезеного за маршрутом товару. Тобто коефіцієнти при невідомих у цільовій функції, що в лінійній моделі були ста­лими величинами, залежатимуть від значень невідомих (отже, самі стають невідомими), що знову приводить до нелінійності у функціоналі.

І нарешті, будь-яка задача стає нелінійною, якщо в математич­ній моделі необхідно враховувати умови невизначеності та ризик. Як показник ризику часто використовують дисперсію, тому для врахування обмеженості ризику потрібно вводити нелінійну фун­кцію в систему обмежень, а мінімізація ризику певного процесу досягається дослідженням математичної моделі з нелінійною ці­льовою функцією.

Нелінійні задачі математичного програмування не зводяться до певної стандартної форми. Тип задачі визначається типом функцій, які входять до цільової функції і обмежень. Не існує загального уні­версального методу розв'язування нелінійних задач, подібного до того, яким є симплексний метод для задач лінійного програмування. Ця обставина, а також специфіка окремих типів нелінійних задач зу­мовили значну різноманітність методів їх розв'язування.

Далі подано деякі загальні властивості нелінійних задач різних типів і основні ідейні засади, на яких ґрунтуються алго­ритми їх розв'язування.

При побудові методів розв'язування задач нелінійного програму­вання, особливо задач з лінійними обмеженнями, широко використо­вується ідея зведення їх до вигляду, що так чи інакше допускає засто­сування симплексного або подібного до нього методу. Проте коли для лінійних задач симплексний метод дає точний розв'язок, то за допомо­гою згаданих методів можна дістати лише наближений розв'язок нелінійних задач. Як правило, нелінійна задача замінюється при цьо­му лінійною, розв'язок якої близький до розв'язку нелінійної за­дачі.

Для такого зведення треба, щоб задача нелінійного програмування мала певні властивості. При побудові наближених лінійних задач виникає ряд труднощів, які можуть призвести до того, що розв'язок наближеної задачі буде надто грубим і непридатним для викори­стання.

Слід зауважити, що навіть питання про існування розв'язку задачі нелінійного програмування не вирішується так просто, як для лінійних задач, а часто потребує окремого дослідження.

Поряд з цим розроблено деякі методи, що дають змогу діставати точні розв'язки нелінійних задач певних типів; проте і в цьому разі для реальних задач виникають часто труднощі обчислювального ха­рактеру.