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

Розглянемо частинний випадок нелінійної задачі:

(1.107)

, (1.108)

де (1.107) - нелінійна функція мети від n змінних величин;

(1.108) - нелінійні обмеження;

b_i - сталі величини.

На змінні величини x_j не покладається умова невід’ємності, що дає змогу розглядати задачу (1.107) - (1.108) як класичну задачу умовної оптимізації.

Допустимо, що функції f(x), g_i(x) є неперервними разом із своїми частинними похідними.

Перейдемо від задачі умовної до задачі безумовної оптимізації шляхом побудови функції Лагранжа:

(1.109)

Необхідною умовою існування екстремуму функції Лагранжа буде:

(1.110)

Кожен розв’язок системи рівнянь (1.110) визначає можливу точку екстремуму Х⁰=(х₁⁰,...,х_n⁰).

Для лінійної задачі

, (1.111)

, (1.112)

функція Лагранжа прийме такий вигляд:

(1.113)

Необхідною умовою існування екстремуму функції Лагранжа буде:

(1.114)

(1.115)

Якщо задачу (1.107) - (1.108) доповнити умовою x_j0, що є типовим обмеженням в економічних задачах, то необхідна умова існування екстремуму функції Лагранжа для задачі:

(1.116)

(1.117)

(1.118)

описується теоремою Куна-Такера.

За теоремою Куна-Такера точка Х⁰=(х₁⁰,...,х_n⁰) буде розв’язком задачі (1.116) - (1.118) лише тоді, коли знайдеться такий вектор ⁰=(₁⁰,...,_m⁰) при якому для функції Лагранжа

в точці (Х⁰; ⁰) будуть виконуватися такі умови:

(1.119)

(1.120)

(1.121)

(1.122)

(1.123)

Для загальної задачі лінійного програмування

функція Лагранжа набере вигляду

(1.124)

а необхідна умова існування екстремуму функції опишеться системою обмежень:

(1.125)

(1.126)

(1.127)

(1.128)

(1.129)

(1.130)

1.5.3. Множники Лагранжа і двоїсті оцінки задачі лінійного програмування

Розглянемо задачу лінійного програмування

(1.131)

(1.132)

(1.133)

яку перетворимо до вигляду

(1.134)

(1.136)

(1.137)

Позначимо множники Лагранжа для задачі (1.134) - (1.137) через х_j і побудуємо функцію Лагранжа:

(1.138)

Умови Куна-Такера для функції Лагранжа (1.138) можна записати в такому вигляді:

(1.139)

(1.140)

(1.141)

(1.142)

(1.143)

(1.144)

Очевидно, що умови (1.139), (1.141), (1.144) для задачі (1.131) - (1.133) співпадають з обмеженнями (1.126), (1.128), (1.129) для загальної задачі лінійного програмування, а обмеження (1.140), (1.142), (1.143) - з обмеженнями (1.125), (1.127), (1.130). Подібна пара задач називається двоїстою. Множники Лагранжа _і - суть не що інше як двоїсті змінні (двоїсті оцінки), які характеризують чутливість функції мети щодо зміни значень b_i.

Приклад 7. Графічне розв’язування нелінійних задач

Знайти оптимальний розв’язок таких задач:

а)

б)

в)

У випадку а) максимальне значення функції мети досягається в точці В(1; 0), тобто f_max =f(B)=1.

Мінімальне значення f(х) досягається в точці А(0;1) і дорівнює f_min =f(А)=-1.

У випадку б) максимальне значення ФМ досягається в точці С(0; 4), тобто f_max =f(С)=(0-4)²+(4-1)²=25.

Мінімальне значення f(х) досягається у внутрішній точці Е(4;1) і дорівнює f_min =f(Е)=0.

У випадку в) максимальне значення ФМ досягається в точці М(7; 4/7), тобто f_max =f(М)=49+16/49=2417/49.

Мінімальне значення функції мети досягається в точках А(1;4) та L(4;1) і дорівнює f_min =f(L)=17.

Приклад 8. Знаходження оптимального розв’язку нелінійної задачі за методом множників Лагранжа

Для задачі

Знайти оптимальний розв’язок.

Будуємо функцію Лагранжа

За необхідною умовою існування екстремуму функції Лагранжа отримаємо:

Звідки слідує:

Приклад 9. Знаходження оптимального розв’язку лінійної задачі за методом множників Лагранжа

Для задачі

побудуємо функцію Лагранжа

і запишемо необхідні умови Куна-Такера існування екстремуму функції:

Пересвідчуємося, що ці умови виконуються для Х⁰=(6/7; 4/7) при ⁰=(3/7; 1/7), а значить точка Х⁰=(6/7; 4/7) є точкою максимуму функції мети в заданій області допустимих розв’язків.

Оскільки ₁⁰=3/7, ₂⁰=1/7, то це означає, що збільшення b₁ в умові задачі на одиницю (b₁^ =3) призведе до зростання функції мети на 3/7, а збільшення b₂=4 на одиницю (b₂^ =5), призведе до зростання функції мети на 1/7.

ЧАСТИНА 2. МОДЕЛЮВАННЯ ЗАДАЧ ОПТИМАЛЬНОГО ВИКОРИСТАННЯ РЕСУРСІВ

ТЕМА 2.1. МОДЕЛЮВАННЯ ОСНОВНИХ ТИПІВ ОБМЕЖЕНЬ ТА ОБГРУНТУВАННЯ ВИБОРУ ФУНКЦІЇ МЕТИ ДЛЯ ЗАДАЧІ ОПТИМАЛЬНОГО ПЛАНУВАННЯ ВИРОБНИЦТВА ПРОДУКЦІЇ НА КАЛЕНДАРНИЙ ПРОМІЖОК ЧАСУ

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

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

• на ресурсне забезпечення;

• на виробництво продукції;

• на структуру асортименту продукції;

• на основні економічні показники.

Календарний проміжок часу може охоплювати рік, квартал, місяць.

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