|
|
Загальна постановка задачі нелінійного програмування. Класифікація задачДосить детально розглянута в розділах, присвячених лінійному програмуванню, задача пошуку оптимальних обсягів виробництва ґрунтується на допущеннях про лінійність зв’язку між витратами ресурсів і обсягами виготовленої продукції; між ціною, рекламою та попитом тощо. Але такі зв’язки насправді є нелінійними, тому точніші математичні моделі доцільно формулювати в термінах нелінійного програмування. Нехай для деякої виробничої системи необхідно визначити план випуску продукції за умови найкращого способу використання її ресурсів. Відомі загальні запаси кожного ресурсу, норми витрат кожного ресурсу на одиницю продукції та ціни реалізації одиниці виготовленої продукції. Критерії оптимальності можуть бути різними, наприклад, максимізація виручки від реалізації продукції. Така умова подається лінійною залежністю загальної виручки від обсягів проданого товару та цін на одиницю продукції. Однак, загальновідомим є факт, що за умов ринкової конкуренції питання реалізації продукції є досить складним. Обсяг збуту продукції визначається передусім її ціною, отже, як цільову функцію доцільно брати максимізацію не всієї виготовленої, а лише реалізованої продукції. Необхідно визначати також і оптимальний рівень ціни на одиницю продукції, за якої обсяг збуту був би максимальним. Для цього її потрібно ввести в задачу як невідому величину, а обмеження задачі мають враховувати зв’язки між ціною, рекламою та обсягами збуту продукції. Цільова функція в такому разі буде виражена добутком двох невідомих величин: оптимальної ціни одиниці продукції на оптимальний обсяг відповідного виду продукції, тобто буде нелінійною. Отже, маємо задачу нелінійного програмування. Також добре відома транспортна задача стає нелінійною, якщо вартість перевезення одиниці товару залежить від загального обсягу перевезеного за маршрутом товару. Тобто коефіцієнти при невідомих у цільовій функції, що в лінійній моделі були сталими величинами, залежатимуть від значень невідомих (отже, самі стають невідомими), що знову приводить до нелінійності у функціоналі. І нарешті, будь-яка задача стає нелінійною, якщо в математичній моделі необхідно враховувати умови невизначеності та ризик. Як показник ризику часто використовують дисперсію, тому для врахування обмеженості ризику потрібно вводити нелінійну функцію в систему обмежень, а мінімізація ризику певного процесу досягається дослідженням математичної моделі з нелінійною цільовою функцією. Загальна задача математичного програмування формулюється так: знайти такі значення змінних xj
за умов:
Якщо всі функції
35. Геометрична інтерпретація задачі
Якщо цільова функція неперервна, а допустима множина розв’язків замкнена, непуста і обмежена, то глобальний максимум (мінімум) задачі існує. Найпростішими для розв’язування є задачі нелінійного програмування, що містять систему лінійних обмежень та нелінійну цільову функцію. В цьому разі область допустимих розв’язків є опуклою, непустою, замкненою, тобто обмеженою. Розглянемо приклад геометричного способу розв’язування задачі нелінійного програмування. З
за умов:
Рис. 8.1
Розв’язання. Область допустимих розв’язків утворює чотирикутник АВСD (рис. 8.1). Геометрично цільова функція являє собою коло з центром у точці М (2; 2), квадрат радіуса якого
Оскільки Очевидно, що найменший радіус
Зазначимо, що в даному разі точка, яка відповідає оптимальному плану задачі (мінімальному значенню функціонала), знаходиться всередині багатокутника допустимих розв’язків, що в задачах лінійного програмування неможливо. З
за умов:
Розв’язування. У даному прикладі множина допустимих розв’язків складається з двох окремих частин, необмежених зверху (рис. 8.2). Цільова функція аналогічно попередньому випадку є колом з центром у точці М (4; 4). Функція Z має два локальних мінімуми: в точці А ( З Рис. 8.2. начення функціонала в цих точках однакове і дорівнює:
Даний приклад ілюструє ще одну особливість задач нелінійного програмування: на відміну від задач лінійного програмування багатогранник допустимих розв’язків задачі нелінійного програмування не обов’язково буде опуклою множиною.
Метод множників Лагранжа Ідея методу множників Лагранжа полягає в заміні початкової задачі простішою. Для цього цільову функцію замінюють іншою, з більшою кількістю змінних, тобто такою, яка включає в себе умови, що подані як обмеження. Після такого перетворення дальше розв’язування задачі полягає в знаходженні екстремуму нової функції, на змінні якої не накладено ніяких обмежень. Тобто від початкової задачі пошуку умовного екстремуму переходимо до задачі відшукання безумовного екстремального значення іншої функції. Отже, завдяки такому перетворенню можливе застосування методів класичного знаходження екстремуму функції кількох змінних. У попередньому параграфі наведена необхідна умова існування локального екстремуму неперервної та диференційовної функції двох змінних. Узагальнення необхідної умови існування локального екстремуму функції n змінних має аналогічний вигляд. Отже, для розв’язування задачі необхідно знайти вирази частинних похідних нової цільової функції за кожною змінною і прирівняти їх до нуля. В результаті отримаємо систему рівнянь. Її розв’язок визначає так звані стаціонарні точки, серед яких є і шукані екстремальні значення функції. Розглянемо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд:
за умов:
де функції Задача (8.6), (8.7) полягає в знаходженні екстремуму функції Переходимо до задачі пошуку безумовного екстремуму. В літературі [13, 28] теоретично доведено, що постановки та розв’язання таких задач еквівалентні. Замінюємо цільову функцію (8.6) на складнішу. Ця функція називається функцією Лагранжа і має такий вигляд:
де Знайдемо частинні похідні і прирівняємо їх до нуля:
Друга група рівнянь системи (8.9) забезпечує виконання умов (8.7) початкової задачі нелінійного програмування. Система (8.9), як правило, нелінійна. Розв’язками її є Для діагностування стаціонарних точок і визначення типу екстремуму необхідно перевірити виконання достатніх умов екстремуму, тобто дослідити в околі стаціонарних точок диференціали другого порядку (якщо для функцій Узагальнення достатньої умови існування локального екстремуму для функції n змінних приводить до такого правила: за функцією Лагранжа виду (8.8) будується матриця Гессе, що має блочну структуру розмірністю
де О — матриця розмірністю Р — матриця розмірністю
Q — матриця розмірністю
Розглянемо ознаки виду екстремуму розв’язку системи (8.9). Нехай стаціонарна точка має координати 1. Точка 2. Точка
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
, щоб цільова функція набувала екстремального (максимального чи мінімального) значення:
(8.1)
(
); (8.2)
та 
, 
найти мінімальне і максимальне значення функції:
.
. Це означає, що її значення буде збільшуватися (зменшуватися) зі збільшенням (зменшенням) радіуса кола. Проведемо з точки М кола різних радіусів. Функція Z має два локальних максимуми: точки В (0; 6) і С (8; 0). Обчислимо значення функціонала в цих точках:
,
.
, то точка С (8; 0) є точкою глобального максимуму.
, тоді:
. Тобто точка М є точкою мінімуму, оскільки їй відповідає найменше можливе значення цільової функції.
найти мінімальне значення функції:
), і в точці В (
).
.
(8.6)
, (8.7)
і 
мають бути диференційовними.
за умов виконання обмежень 
.
(8.8)
— деякі невідомі величини, що називаються множниками Лагранжа.
(8.9)
і 
— стаціонарні точки. Оскільки, ці розв’язки отримані з необхідної умови екстремуму, то вони визначають максимум, мінімум задачі (8.6), (8.7) або можуть бути точками перегину (сідловими точками).
існують другі частинні похідні і вони неперервні).
:
, що складається з нульових елементів,
, елементи якої визначаються так:
,
— транспонована матриця до Р розмірністю 
,
виду:
, де 
.
є точкою максимуму, якщо, починаючи з головного мінору порядку (m + 1), наступні (n – m) головних мінорів матриці Н утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником 
.
.