Задача нелінійного програмування. Математична модель задачі нелінійного програмування

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

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

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

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

В загальному вигляді математична модель задачі нелінійного програмування формулюється наступним чином: знайти вектор , при якому б цільова функція набувала свого екстремального (максимального чи мінімального) значення (можливо лише в тому випадку коли цільова функція неперервна, а допустима множина розв’язків замкнена, непуста і обмежена):

при наступних обмеженнях:

де  – змінні, та  – задані функції від  змінних, – фіксовані значення.

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

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

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

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

Зауваження: відшукувати екстремальні точки для розглядуваного прикладу не будемо, дану процедура реалізуємо при розгляді графічного методу розв’язку задачі нелінійного програмування.

Задача нелінійного програмування – приклад:

Знайти максимальне та мінімальне значення функції мети при наступних обмеженнях:

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

Область допустимих розв'язків задачі
Область допустимих розв’язків задачі

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

Залишити коментар

Your email address will not be published. Required fields are marked *

*