Економічна і геометрична інтерпретації задачі нелінійного програмування

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

f (x₁, x₂,..., x_п) (1)

за умови, що її змінні задовольняють співвідношенням

де f і g_i – деякі відомі функції п змінних, а b_i – задані числа.

Тут мається на увазі, що в результаті Розв’язок задачі буде визначена точка Х*= (х₁*; х₂ *;...; х_п*),координати якої задовольняють співвідношенням (2) і така, що для всякої іншої точки Х= (х₁; х₂;...; х_п),щозадовольняє умовам (2), виконується нерівність f (х₁*; х₂ *;...; х_п*) ≥ f (х₁; х₂;...; х_п)[ f (х₁*; х₂ *;...; х_п*) ≥ f (х₁; х₂;...; х_п)].

Якщо f і g_i – лінійні функції, то задача (1), (2) є задачею лінійного програмування.

Співвідношення (2) утворять систему обмежень і містять у собі умови невід’ємності змінних, якщо такі умови є. Умови невід’ємності змінних можуть бути задані і безпосередньо.

В евклідовому просторі Е_п система обмежень (2) визначає область припустимих рішень задачі. На відміну від задачі лінійного програмування вона не завжди є випуклою.

Якщо визначена область припустимих рішень, то знаходження Розв’язок задачі (1), (2) зводиться до визначення такої точки цієї області, через яку проходить гіперповерхня найвищого (найнижчого) рівня: f (х₁; х₂;...; х_п) =h. Зазначена точка може перебувати як на границі області припустимих рішень, так і всередині її.

Процес знаходження Розв’язок задачі нелінійного програмування (1), (2) з використанням її геометричної інтерпретації включає наступні етапи:

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

2. Будують гіперповерхню f (х₁; х₂;...; х_п) =h.

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

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

3.1. Знайти максимальне значення функції

F=x₂ – x₁ ²+6 x₁ (3)

при умовах

х₁, х₂ ≥ 0 (5)

Розв’язок. Так як цільова функція (3) нелінійна, то задача (3)-(5) є задачею нелінійного програмування. Областю припустимих рішень даної задачі є багатокутник ОАВС (рис. 3.1).

Рис. 3.1

Отже, для знаходження її Розв’язок потрібно визначити таку точку багатокутника ОАВС,у якій функція (3) приймає максимальне значення. Побудуємо лінію рівня F=x₂ – x₁ ²+6 x₁ = h, де h – деяка постійна, і досліджуємо її поведінку при різних значеннях h. При кожному значенні h одержуємо параболу, що тим вище віддалена від осі Ox₁, чим більше значення h (рис. 3.1). Виходить, функція F приймає максимальне значення в точці дотику однієї з парабол із границею багатокутника ОАВС. У даному випадку це точка D (рис. 3.1), у якій лінія рівня F=x₂ – x₁ ²+6 x₁ =13 торкається сторони АВ багатокутника ОАВС. Координати точки D можна знайти із системи рівнянь

(6)

Вирішуючи цю систему, одержимо х₁ *=3; х₂ *=4. Отже, F_max= 13при Х*= (3;4).

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

3.2. Знайти максимальне і мінімальне значення функції

F =(х₁ –3) ² +(х₂ –4) ² (7)

при умовах

х₁, х₂ ≥ 0 (9)

Розв’язок. Областю припустимих рішень задачі (7)-(9) є трикутник АВС (рис. 3.2). Приймаючи значення цільової функції (7) рівним деякому числу h,одержуємо лінії рівня, а саме окружності (х₁ –3) ² +(х₂ –4) ² = h із центром Е (3; 4) і радіусом . Зі збільшенням (зменшенням) числа h значення функції F відповідно збільшуються (зменшуються).

Проводячи із точки Е окружності різних радіусів, бачимо, що мінімальне значення цільова функція приймає в точці D,у якій окружність торкається області рішень. Для визначення координат цієї точки скористаємося рівністю кутових коефіцієнтів прямої 10 х₁–х₂ =8 і дотичної до окружності у точці D. З рівняння прямої х₂ =10 х₁ –8 бачимо, що її кутовий коефіцієнт у точці D дорівнює 10. Кутовий же коефіцієнт дотичної до окружності в точці D визначимо як значення похідної функції x₂ від змінної x₁ у цій точці. Розглядаючи x₂ як неявну функцію змінної x₁ і диференціюючи рівняння окружності, одержимо

2(x₁ –3)+2(x₂ –4) x ′ ₂ =0

звідки

x ′ ₂ =–(x₁ –2)/(x₂ –4).

Прирівнюючи знайдене вираження числу 10, одержуємо одне з рівнянь для визначення координат точки Е. Приєднуючи до нього рівняння прямої, на якій лежить точка Е, маємо систему

звідки х₁ *=123/101; х₂ *=422/101. Таким чином, F_тin= (123/101–3) ² +(422/101– –4) ² =324/101.

Як видно з рис. 3.2, цільова функція приймає максимальне значення в точці C (2; 12). Її координати визначені шляхом Розв’язок системи рівнянь прямих, на перетині яких перебуває точка С. Таким чином, максимальне значення функції F_max =65.

 

Рис. 3.2

 

3.3. Знайти максимальне і мінімальне значення функції

F =(х₁ –4) ² +(х₂ –3) ² (10)

при умовах

х₁, х₂ ≥ 0 (12)

Розв’язок. Областю припустимих рішень вихідної задачі є багатокутник АВСDЕ (рис. 3.3), а лініями рівня – окружності (x₁ –4)²+(х₂–3)²= h із центром Е (4; 3) і радіусом R= .

Рис. 3.3

З рис. 3.3 видно, що цільова функція приймає мінімальне значення в точці F (4; 3), а максимальне – у точці C (13; 10,5). Отже, F_min =0 і F_max =137,25.

3.4. Знайти максимальне значення функції

F =3 х₁ +4 х₂ (13)

при умовах

х₁, х₂ ≥ 0 (15)

Розв’язок. Область рішень задачі (13)-(15) зображена на рис. 3.4. На цьому малюнку побудовані дві лінії рівня, що представляють собою прямі. З рис. 3.4 видно, що максимальне значення цільова функція задачі приймає в точці Е, у якій пряма торкається окружності х₁² + х₂² =25. Для визначення координат точки Е скористаємося рівністю кутових коефіцієнтів прямої 3 x₁ +4 х₂ = h (де h – деяка постійна) і дотичної до окружності в точці Е. Розглядаючи х₂ як неявну функцію змінної x₂,почленно диференціюємо рівняння окружності х₁² + х₂² =25 і одержимо

2 х₁ +2 х₂x ′ ₂ =0, або x ′ ₂=–х₁ / х₂.

Рис. 3.4

Прирівнюючи знайдене вираження числу k =–3/4, одержуємо одне з рівнянь для визначення координат точки Е. Як друге рівняння візьмемо рівняння окружності. Таким чином, для визначення координат точки Е маємо систему

звідки х₁ *=4; х₂ *=3. Виходить, F_тах =3²+4²=25.

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться:

Читайте также:

I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
Аудиторська палата України: функції, задачі.
Взаємно двоїсті задачі
Визначте предмет і задачі психології юридичної праці.
Визначте сутність інтерпретації результатів експериментального дослідження психіки і охарактеризуйте складові інтерпретації.
ВИРОБНИЧІ ФУНКЦІЇ, ТИПОВІ ЗАДАЧІ ДІЯЛЬНОСТІ ТА УМІННЯ ЩОДО ВИРІШЕННЯ ТИПОВИХ ЗАДАЧ ДІЯЛЬНОСТІ
Військовий тил, його роль, задачі і призначення в сучасному бою.
Власність як економічна категорія.
ВЛАСТИВОСТІ ОСНОВНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ГЕОМЕТРИЧНЕ ТЛУМАЧЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині

Воспользуйтесь поиском по сайту: