Повна версія

Головна arrow Економіка arrow Дослідження операцій в економіці

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

РОЗДІЛ II. МОДЕЛІ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ

Глава 9. Класичні методи оптимізації

Глава 10. Моделі лінійного програмування

Глава 11. Моделі динамічного програмування

КЛАСИЧНІ МЕТОДИ ОПТИМІЗАЦІЇ

Класичні методи визначення екстремумів

У багатьох економічних моделях дослідження операцій залежності між постійними і змінними факторами лише в першому наближенні можна вважати лінійними, більш детальний розгляд дозволяє виявити їх нелінійність. Як правило, такі показники, як прибуток, собівартість, капітальні витрати на виробництво та ін., В дійсності залежать від обсягу виробництва, витрати ресурсів і т.п. нелінійно. В цьому випадку виникає задача нелінійного програмування, математична модель якої (0.1), (0.2) наведена у вступі.

Можна виділити клас нелінійних задач, які відносяться до класичних методів оптимізації. Припустимо, що серед обмежень (0.1) немає нерівностей, не обов'язкові умови невід'ємності, змінні нс є дискретними, т <п, а функції φ, (Χ) і f (X) неперервні і мають приватні похідні по крайней мере другого порядку. У цьому випадку завдання оптимізації можна сформулювати так: знайти змінні х { , х 2, ..., х П , що задовольняють системі рівнянь

(9.1)

і звертають в максимум (мінімум) цільову функцію

(9.2)

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

Прикладом типової і простий нелінійної задачі є наступна: дане підприємство для виробництва якогось продукту витрачає два засоби в кількості x ↑ і х 2 відповідно. Це фактори виробництва, наприклад машини і праця, два різних види сировини і т.п., а величини ж, і х 2 - витрати факторів виробництва. Фактори виробництва надалі будемо вважати взаємозамінними. Якщо це "праця" і "машини", то можна застосовувати такі методи виробництва, при яких величина витрат машин в порівнянні з величиною витрат праці виявляється більше або менше (виробництво більш-менш трудомістке). У сільському господарстві взаємозамінними факторами можуть бути посівні площі або мінеральні добрива (екстенсивний чи інтенсивний метод виробництва).

Обсяг виробництва (виражений в натуральних або вартісних одиницях) є функцією витрат виробництва г = f (x v x 2 ). Ця залежність називається виробничою функцією. Витрати залежать від витрати обох факторів (ж, і х 2 ) і від цін цих факторів (с, і з,). Сукупні витрати виражаються формулою Потрібно при даних сукупних витратах визначити таку кількість факторів виробництва, яке максимізує обсяг продукції z.

Математична модель цієї задачі має вигляд: визначити такі змінні хх Т задовольняють умовам

(9.3)

при яких функція

(9.4)

досягає максимуму.

Як правило, функція (9.4) може мати довільний нелінійний вигляд.

Використовуючи класичні методи оптимізації, слід чітко уявляти собі відмінність між локальним екстремумів функції, глобальним екстремумів і умовним екстремумів. При цьому корисно повторити визначення локального і глобального екстремумів для функції однієї змінної. Поняття умовного екстремуму вводиться для випадку, коли число змінних п не менш 2 ( "> 2).

Будемо вважати, що функція двічі диференційована в точці , J і в деякій її околиці. Якщо для всіх точок X цієї околиці або , то кажуть, що функція має екстремум в X ' (відповідно максимум або мінімум).

Точка , в якій всі приватні похідні функції дорівнюють нулю, називається стаціонарною точкою.

Необхідна умова екстремуму. Якщо в точці функція z = f (x) має екстремум, то приватні похідні функції в цій точці дорівнюють нулю:

Отже, точки екстремуму функції z = f (X) задовольняють системі рівнянь:

(9.5)

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

Достатні умови екстремуму:

а) в стаціонарній точці Х ° функція z = f (X) має

максимум, якщо , і мінімум, якщо ,

при будь-яких Δ.Γ і AXj Xв цих випадках Х ° = X '), що не оораща- ющихся в нуль одночасно;

  • б) якщо i / 2 / [X ° j може приймати в залежності від Ах. і Ах, і позитивні, і негативні значення, то в точці екстремуму немає;
  • в) якщо (1 2 / (А '° I може звертатися в нуль не тільки при нульових збільшеннях Ax j і Ах, то питання про екстремуму залишається відкритим.

Для функції двох змінних z = / (х х , ХЛ достатні умови ще не дуже складні. Існують чотири приватні похідні другого порядку;

. З них дві змішані похідні і "2 якщо безперервні, то рівні.

Знайдемо значення приватних похідних другого порядку в стаціонарній точці :

(можна переконатися, що α νι = а21). Позначимо через Δ визначник, складений з ї .. для i, j = 1,2:

Тоді достатні умови екстремуму функції двох змінних мають вигляд:

  • а) якщо А > 0 і "" <0 ( а. п < 0), то в точці Х ° функція має максимум: якщо Δ> 0 і а і> 0 ( а 22> 0), то в точці Х ° - мінімум (в цих випадках Х ° = Х ');
  • б) якщо А <0, то екстремуму немає;
  • в) якщо А = 0, то питання про екстремуму залишається відкритим.

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

9.1. Дослідити на екстремум функцію

Рішення. Знаходимо приватні похідні:

(9.6)

Прирівнюємо приватні похідні нулю:

(9.7)

Вирішуємо систему рівнянь (9.7). Віднімаючи з першого рівняння друге, одержимо , тому = х 2, і з першого рівняння знайдемо >, звідки х. = О або

_Імеем три стаціонарні точки X1 = (О; 0); X 2 = (l; l);

Знайдемо другі приватні похідні, використовуючи (9.6):

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

У точці

Питання про екстремуму залишається відкритим (така точка називається седловой).

У точці а також і в точці :

Функція в цих точках має мінімум, так як Δ > 0 і а> 0 • Z min = -21. ►

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

Кажуть, що функція z = / (X) має в точці Х ° заданої області D глобальний максимум (найбільше значення) або глобальний мінімум (найменше значення), якщо нерівність I або відповідно виконується для люоой точки леї.

Якщо область D замкнута і обмежена, то диференційована функція 2 = f (x) досягає в цій області своїх найбільшого і найменшого значень або в стаціонарній точці, або в граничної точці області ( теорема Вейєрштрасса) 2.

Отже, щоб знайти найбільше (найменше) значення функції 2 = f (x) в області D, потрібно:

  • 1) знайти всі стаціонарні точки всередині області D і обчислити значення функції в них;
  • 2) дослідити функцію на екстремум на кордоні області D;
  • 3) порівняти значення функції, отримані в π. 1 і 2: найбільше (найменше) з цих чисел і буде найбільшим (найменшим) значенням функції у всій області.

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

Умовний екстремум. Нехай необхідно знайти екстремум функції 2 = / (х ,, х2, ..., х п) за умови, що змінні X ,, х2, ..., х п задовольняють рівнянням

(9.8)

Передбачається, що функції / і φ; мають безперервні приватні похідні по всім змінним. Рівняння (9.8) називають рівняннями зв'язку.

Кажуть, що в точці , що задовольняє рівнянням зв'язку (9.8), функція має вус

ловного максимум (мінімум), якщо нерівність

має місце для всіх точок X, координати яких задовольняють рівнянням зв'язку.

Легко помітити, що завдання визначення умовного екстремуму збігається із завданням нелінійного програмування (9.1), (9.2).

Один із способів визначення умовного екстремуму застосовується в тому випадку, якщо з рівнянь зв'язку (9.8) т змінних, наприклад можна виразити через що залишилися п-т змінних:

(9.9)

Підставивши отримані вирази для x i в функцію z, отримаємо

або

(9.10)

Задача зведена до знаходження локального (глобального) екстремуму для функції (9.10) від п-т змінних. Якщо в точці функція (9.10) має екстремум, то в точці функція має умовний екстремум (сформульований на с. 188).

9.2. Вирішити задачу (9.3), (9.4), припустивши, що виробнича функція

Рішення. Необхідно знайти змінні х х і х. г, що задовольняють рівняння

(9.11)

(Рівняння зв'язку), умові незаперечності х,> 0 і .р,> 0 і звертають в максимум функцію

(9.12)

Мал. 9.1

Обмеження (9.11) разом з умовами невід'ємності визначають на площині Οχ χ χ 2 відрізок АВ, який утворює замкнуту обмежену область (рис. 9.1).

Згідно з теоремою Вейєрштрасса максимум функції може досягатися або всередині цього відрізка, або в граничних точках: А (4; 0) або В (0; 2).

Отже, необхідно знайти умовний екстремум функції (9.12), якщо рівняння зв'язку має вигляд (9.11).

З рівняння зв'язку знайдемо, наприклад, х, і підставимо в (9.12):

Спростивши цей вислів, отримаємо

(9.13)

При цьому . Знайдемо глобальний екстремум

функції (9.13) на відрізку [0; 2]. Похідна цієї функції дорівнює

Стаціонарні точки: I. Одна з них,

, Лежить всередині відрізка, дві інші збігаються з кінцями. Знайдемо значення функції (9.13) в стаціонарній точці і на кінцях відрізка:

Отже, zmax = 4 і досягається при х 2 = 1 р.р., = = 4-2х 2 = 2, тобто в точці (2; 1).

Максимальний обсяг виробництва, рівний zmax = 4 од., Досягається за умови, що витрати виробничих факторів х 1 і х 2 рівні відповідно 2 од. та 1 од. ►

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

Нехай вирішується завдання визначення умовного екстремуму функції г = / (Х) при обмеженнях (9.8).

складемо функцію

(9.14)

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

2-го ресурсу, відповідні цим планом, то - ціна (оцінка) г-го ресурсу, що характеризує зміну екстремального значення цільової функції в залежності від зміни розміру 2-го ресурсу (маргінальна опенкаV L (X) - функція 22 + 222 змінних.

Визначення стаціонарних точок цієї функції призводить до вирішення системи рівнянь:

(9.15)

Легко помітити, що = <р; (х), тобто в (9.15) входять рівняння зв'язку. Таким чином, завдання знаходження умовного

  • [1] Ж. Л. Лагранж (1736-1813) - французький математик і механік.
 
<<   ЗМІСТ   >>