Приклад 1

Для виробництва двох виробів А і В підприємство використовує три типи технологічного обладнання. Кожний з виробів повинен пройти обробку на даному типі обладнання. Час обробки кожного з виробів, витрати, пов’язані з виробництвом одного виробу, наведено у таблиці. Обладнання 1-го та 3-го типів підприємство може використовувати не менше 48 і 6 годин відповідно, а обладнання 2-го типу не більше 50 годин.

Тип обладнання	Витрати часу на обробку одного виробу, год.
А	В
Витрати на виробництво одного виробу, тис. грн..

Визначити обсяг виробництва продукції за умови найменшої середньої собівартості одного виробу.

4. Графічне розв’язання задачі дробово-лінійного програмування.

У загальному випадку цільова функція задачі дробово-лінійного програмування має вигляд

(13)

З огляду на те, що , тобто , можна записати

(14)

З рівняння (13) виразимо змінну х₂ через х₁

(15)

або

(16)

Останнє рівняння можна розглядати як рівняння прямої з кутовим коефіцієнтом . З виду k можна зробити висновок, що при зміні значення цільвої функції z, змінюється k- кут нахилу лінії рівня. На відміну від задачі ЛП, щоб досягти оптимального значення z, лінію рівня потрібно повертати, а не переміщувати паралельно самій собі. Залишилося з’ясувати два питання:

· як повертати: за годинковою стрілкою або проти годинкової стрілки;

· навколо якої точки здійснювати поворот.

Звернемо увагу на те, що

. (17)

Кутовий коефіцієнт є функцією z. Щоб визначити, як повертати лінію рівня для досягнення z_max або z_min, необхідно дослідити функцію k(z) на монотонність.

Обчислемо похідну

(18)

· якщо то k зростає при збільшенні z;

· якщо то k спадає при збільшенні z..

Таким чином, якщо

(19)

то й при збільшенні z лінія рівня повертається проти годинникової стрілки.

Якщо

(20)

то й збільшенні z лінія рівня повертається за годинниковою стрілкою.

З рівняння (15) випливає, що при тобто при лінія рівня проходить через початок координат і, отже, поворот здійснюється навколо початку координат.

Якщо, й/або , то рівняння (15) визначає пучок прямих, які проходять через деяку точку Рівняння пучка прямих, які проходять через задану точку з урахуванням (15), запишеться у вигляді:

(21)

Так як з (15) маємо

(22)

То підставивши (21) в (20), одержимо

(23)

звідки

(24)

Останнє рівняння повинне виконуватися для всіх значень z. Це можливо, тільки якщо

(25)

Таким чином, у випадку якщо й/або , поворот лінії рівня здійснюється навколо точки з координатами , які є розв’язком системи (25).

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

Питання для самоконтролю.

· Сформулюйте задачу дробово-лінійного програмування.

· Дайте економічну інтерпретацію задачі дробово-лінійного програмування.

· Сформулюйте алгоритм розв’язання задачі дробово-лінійного програмування.

· У чому принципова відмінність геометричної інтерпретації задачі дробово-лінійного програмування?

· Навколо якої точки здійснюється поворот лінії рівня?

· Сформулюйте алгоритм розв’язання задачі дробово-лінійного програмування графічним методом.

Тема 7. Нелінійні оптимізаційні моделі економічних систем.

Лекція 15.

Тема лекції: Задачі нелінійного програмування

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

План лекції

1. Класичні методи розв’язування задач нелінійного програмування.

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

3. Задачі опуклого прогрмування.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1. Класичні методи розв’язання задач нелінійного програмування.

Загальна задача нелінійного програмування полягає у знаходженні максимального(мінімального) значення функції

Z=f(x₁, x₂,….. x_n) →max/ min (1)

за умов

g_i(x₁, x₂,….. x_n) { ≤=≥}b_i, i=1,2…..m (2)

де всі функції (або їх частина) нелінійні.

Функція f з (1) – цільова функція, а умови g_i з (2) - умовами обмеження.

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

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

Лише для небагатьох типів задач НП розроблені обчислювальні методи їх розв’язання.

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

Як згадувалось вище, найбільш вивченими є задачі з нелінійною цільовою функцією і лінійними обмеженнями, які можна класифікувати таким чином:

- Задачі дробово-лінійного програмування

Z=(∑c_ix_i)/(∑d_ix_i) →max/ min

за умов

∑a_ijx_j =b_i, (i=1,2…..m)

x_j ≥0 (j=1,2…..n)

- Сеперабельна задача НП

f(x₁, x₂,….. x_n) =∑f_i(x_i) →max/ min

за умов

∑a_ijx_j{ ≤=≥}b_i, (i=1,2…..m)

x_j ≥0 (j=1,2…..n)

- Квадратична задача НП

f(x₁, x₂,….. x_n) =∑c_jx_j +∑∑d_jix_ix_j →max/ min

за умов

∑a_ijx_j{ ≤=≥}b_i, (i=1,2…..m)

x_j ≥0 (j=1,2…..n)

- Задача опуклого програмування

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

Розглянемо задачу (5), якщо на змінні не накладаються умови обмежень.

Така задача вирішується класичними методами дифереціального числення.

Нехай Z=f(x₁, x₂,….. x_n) неприривно – диференційована функція в своїй області визначення. Необхідною умовою екстремуму в точці Х₀ функції Z=f(x₁, x₂,….. x_n) є рівність нулю градієнта функції Z(X₀)=0.Для функції Z=f(x₁, x₂,….. x_n) запишемо матрицю Гессе:

Н=

яка складається з частинних похідних другого порядку.

Головні мінори матриці Гессе позначимо:

M₁= , M₂= , ………….,M_n=H,

де f_ij= – значення частинної похідної другого порядку функції Z в точці X₀.

Якщо всі головні мінори M₁, M₂, M₃, …… M_n>0, то Х₀ – точка локального мінімуму. Якщо головні мінори почергово міняють знак, починаючи з мінуса, то точка Х₀ – точка локального максимуму. Проаналізувавши всю область допустимих розв’язків, можна виділити серед локальних екстремумів найбільший і найменший, які і будуть глобальними.

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

Розглянемо задачу НП з обмеженнями – рівностями:

Z=f(x₁, x₂,….. x_n) →max/ min (3)

за умов

g_i(x₁, x₂,….. x_n)=b_i, i=1,2…..m (4)

в якій f і g_i двічі неперервно диференційовані функції.

Для визначення оптимальних точок цієї задачі, введемо набір змінних λ_i (i=1,2,….m), які називаються множниками Лагранжа, і побудуємо функцію Лагранжа

L(x₁, x₂,….. x_n, λ₁,, λ₂,...., λ_m)= f(x₁, x₂,….. x_n) + ∑ λ_i(b_i - g_i(x₁, x₂,….. x_n)) (5)

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

3. Задачі опуклого програмування.

Означення 1. Функція f(x₁, x₂,….. x_n), що задана на опуклій множені Х, називається опуклою, якщо для будь – яких двох крапок Х₁,Х₂ є Х і довільного µє[0;1] виконується співвідношення:

f(µX₁+(1-µ) X₂) ≤ µ f(X₁) +(1-µ) f(X₂)

Означення 2. Функція f(x₁, x₂,….. x_n), що задана на опуклій множині Х, називається вгнутою, якщо для будь яких двох крапок Х₁,Х₂ є Х і довільного µє[0;1] виконується співвідношення

f(µX₁+(1-µ) X₂) ≥ µ f(X₁) +(1-µ) f(X₂).

Якщо f(x₁, x₂,….. x_n) – опукла, то - f(x₁, x₂,….. x_n) – вгнута.

Загальна постановка задачі опуклого програмування:

Z=f(x₁, x₂,….. x_n) →max (6)

за умов

g_i(x₁, x₂,….. x_n) ≤b_i, i=1,2…..m (7)

x_j ≥0 j=1,2,…..n (8)

де f – вгнута і g_i - опуклі функції

Надалі припустимо, що ОДР задачі (6) – (8) не порожня й обмежена.

Теорема 3. Довільний локальний максимум (мінімум) задачі опуклого програмування є глобальним максимумом (мінімумом).

Означення 3. Говорять, що множина ОДР задовольняє умову регулярності, якщо існує хоча б одна крапка

Означення 4. Говорять, що множина допустимих планів (6) – (8) задовольняє умові регулярності, якщо існує хоча б одна крапка х _i з області допустимих розв’язків така, що g_i(x_i)<b_i (i=1,2,….m).

Означення 5. Крапка (Х^*,Λ^*) називається сідловою крапкою функції Лагранжа, якщо L(Х,Λ^*) ≤L(Х^*,Λ^*)≤L(Х^*,Λ) для всіх x_j ≥0 (j=1,2,…n) і λ_i≥0 (i=1,2,….m).

Теорема 4. (Куна-Такера). Нехай для ОДР задачі опуклого програмування (6) – (8) виконується умова регулярності. План Х^*буде оптимальним планом цієї задачі тоді і тільки тоді, коли існує такий вектор Λ^*, λ_i≥0 (i=1,2,….m), що пара (Х^*,Λ^*) – сідлова крапка функції Лагранжа.

Зазначимо, що умови Куна-Такера мало придатні для знаходження оптимального розв’язку, вони лише характеризують розв’язок, тобто дають можливість перевірити деякий розв’язок на оптимальність.

i. Задачі опуклого програмування.

Розглянемо задачу квадратичного програмування, яка є окремим випадком задач опуклого програмування.

Означення 6. Квадратичною формою відносно змінних x₁, x₂,….. x_n називається функція Z, яка має вигляд Z=∑∑с_jix_ix_j.

Означення 7. Квадратична форма Z називається додатньо (від’ємно) – визначеною, якщо Z(Х)>0 (Z(Х)<0) для всіх значень змінних Х, окрім крапки Х=(0,0,……0).

Означення 8. Квадратична форма Z називається додатньо (від’ємно) – напіввизначеною, якщо Z(Х) ≥0 (Z(Х) ≤0) для будь якого набору значень змінних Х =(x₁, x₂,….. x_n) і, крім того, існує такий набір змінних Х^*, де не всі змінні одночасно рівні нулю, що Z(Х) =0.

Теорема 5. Квадратична форма є опуклою функцією, якщо вона додатньо-напіввизначена.

Постановка задачі квадратичного програмування має вигляд:

Z=∑∑с_jix_ix_j.+ ∑d_jx_j→max/ min (9)

за умов

∑a_ijx_j ≤b_i, (i=1,2…..m),

x_j ≥0 (j=1,2…..n),

де ∑∑с_jix_ix_j - від’ємно (додатньо) – напіввизначена квадратична форма.

Алгоритм знаходження розв’язку задачі квадратичного програмування.

1. Складаємо функцію Лагранжа.

2. Записуємо необхідні і достатні умови існування сідловок точки для функції Лагранжа.

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

4. Записуємо оптимальний план початкової задачі й обчислюємо значення цільової функції.

Питання для самоконтролю.

· Сформулюйте загальну задачу НП.

· Сформулюйте задачу сепарабельного програмування.

· Сформулюйте задачу квадратичного програмування.

· Сформулюйте задачу опуклого програмування.

· Поясніть метод множників Лагранжа.

· Сформулюйте означення сідловок точки функції Лагранжа.

· Сформулюйте теорему Куна-Такера.

· Сформулюйте означення додатньо-визначеної квадратичної форми.

· Сформулюйте означення додатньо-напіввизначеної квадратичної форми.

Тема 7. Нелінійні оптимізаційні моделі економічних систем.

Лекція 16.

Тема лекції: Основні поняття теорії варіаційного числення

Мета: ознайомити студентів з методами розв’язання задач варіаціонного числення.

План лекції

1. Поняття про функціонал.

2. Екстремум функціонала.

3. Класичні задачі варіаційного числення.

4. Варіація функції та приріст функціоналу.

5. Перша та друга варіація функціоналу.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

5. Высшая математика. Специальные главы: пособие для студентов вузов/ П.И. Чинаев, Н.А. Минаев, А.Ю. Перевозчиков, А.А. Черенков. Под ред. П.И. Чинаева. – 2-е изд. – Киев: Вища школа, 1981. – 368 с.

1. Поняття про функціонал.

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

Нехай задано деякий клас D функцій . Якщо кожній функції із класу D за деяким законом ставиться у відповідність певне числове значення змінної I, то ця змінна І називається функціоналом від однієї функціональної змінної і позначається .

Клас D функцій , на яких визначений функціонал, називається областю визначення функціоналу. При цьому функція служить незалежною змінною (аргументом) функціоналу. Функції із області визначення D даного функціоналу І називаються функціями порівняння або допустимими функціями.

Кожну функцію , яка належить області визначення D функціоналу І[у], можна розглядати як точку (елемент) деякої множини (простору) функцій. Простори, елементами яких служать функції, називаються функціональними просторами. Можна сказати, що функціонал — це функція, в якої значеннями незалежної змінної є точки (елементи) функціонального простору, а значеннями залежної змінної І — числа.

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

Приклад 1. Обчислити заданий функціонал при заданих значеннях аргументу:

а)

б)

Розв'язання.

а)

б)

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

2. Екстремум функціоналу.

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

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

Приклад 2. Знайти відстань першого порядку між кривими і на відрізку .

Розв'язання.

Розглянемо функції і . Знайдемо їх найбільші та найменші значення на відрізку :

Тоді

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

Функціонал має в класі D ₁ локальний або відносний мінімум (максимум), який реалізується функцією , якщо для довільної функції , яка близька до функції , виконується рівність

Максимуми і мінімуми називаються екстремумами.

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

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

На рис. 1 зображені лінії, близькі в смислі відстані нульового порядку (координати їх близькі, а напрямки дотичних можуть суттєво відрізнятись), а на рис. 2 наведені криві, близькі в смислі відстані першого порядку (близькі не тільки їх координати, а і напрямки дотичних).

Рис.1 Рис.2

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

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

Надалі будемо розглядати слабкий відносний екстремум і слова "слабкий", "відносний" будемо опускати.

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

3. Класичні задачі варіаційного числення.

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

Аналітичне формулювання цієї задачі: серед неперервно диференційовних функцій знайти таку, яка доставляє мінімум функціоналу

при крайових умовах

a b

Рис. 3.

· Задача про геодезичні лінії.

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

Аналітичне формулювання цієї задачі: серед неперервно диференційовних функцій параметра t знайти такі, які задовольняють рівняння зв'язку і доставляють мінімум функціоналу

при крайових умовах

· Ізопериметрична задача (задача Дідо).

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

Аналітичне формулювання цієї задачі: серед неперервно диференційовних функцій вибрати таку, яка задовольняє рівняння зв'язку і доставляє максимум функціоналу при крайових умовах

Рис. 4.

4. Варіація функції та приріст функціоналу.

Нехай функціонал визначений на класі функцій D, і — довільні функції даного класу D. Функція, яка дорівнює різниці функцій і , називається приростом або варіацією аргументу функціоналу і позначається : .

Тоді .

Різниця називається приростом функціоналу , який відповідає варіації аргументу.

Зазначимо, що похідна варіації функції дорівнює варіації похідної: Дійсно,

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

Функціонал називається лінійним, якщо виконуються умови:

1. Функціонал від алгебраїчної суми функцій дорівнює відповідній алгебраїчній сумі функціоналів:

2. Сталий множник можна виносити за знак функціоналу:

5. Перша та друга варіації функціоналу.

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

При дослідженні функціоналів варіація функціоналу відіграє роль, аналогічну тій, яку виконує при дослідженні функцій диференціал. В таблиці 1 наведено відповідність понять диференціального та варіаційного числень.

Таблиця 1

№ п/п	Диференціальне числення	Варіаційне числення
1.	Аргумент — числова змінна х	Аргумент — числова функція
2.	Залежна змінна — числова y	Залежна змінна — числова I
3.	Приріст аргументу	Варіація аргументу
4.	Приріст функції	Приріст функціоналу
5.	Диференціал функції	Варіація функціоналу
6.	Другий диференціал функції	Друга варіація функціоналу
7.	Необхідна умова екстремуму	Необхідна умова екстремуму
8.	Стаціонарна точка функції	Стаціонарна функція (допустима екстремаль) функціоналу
9.	Достатня умова екстремуму:	Достатня умова екстремуму:

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

Візьмемо довільну допустиму функцію і довільну її варіацію таку, що функція є допустимою функцією. Зафіксуємо та і розглянемо однопараметричну сім'ю функцій , де — деяке число. Функціонал на вказаній сім'ї функцій є функцією параметра :

.

Розкладемо цю функцію за формулою Тейлора до квадратичного члена включно в околі точки :

де залишковий член є нескінченно малою вищого порядку порівняно з : .

Тоді варіаціям першого та другого порядку можна дати такі означення.

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

(Друге означення варіації функціоналу).

Можна показати, що це означення першої варіації рівносильне наведеному раніше. На практиці зручніше користуватись останнім означенням.

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

Приклад 3. Знайти варіацію функціоналу а) б) в) користуючись першим означенням як головної лінійної відносно частини приросту .

Розв'язання. а) Знайдемо приріст функціоналу :

За першим означенням

б) Знайдемо приріст функціоналу :

За першим означенням .

в) Знайдемо приріст функціоналу :

За першим означенням .

Приклад 4. Знайти варіацію функціоналу а) б) в) користуючись другим означенням варіації функціоналу як похідної по параметру.

Розв'язання. У відповідності з другим означенням варіації функціоналу маємо:

а)

б)

в)

Питання для самоконтролю.

· Сформулюйте класичні задачі варіаційного числення.

· Як знайти відстань нульового порядку?

· Як знайти відстань другого порядку?

· Який екстремум зветься сильним?

· Який екстремум зветься слабим?

· Сформулюйте основну задачу варіаційного числення.

· Які умови повинні виконуватися щоб функціонал був лінійним?

· Дайте означення першої варіації функціоналу.

· Дайте означення другої варіації функціоналу.