Лінійна оптимізація

Цей розділ призначений як вступ до складної теми лінійної оптимізації (LOP). У цьому контексті виникають деякі питання, які ми хочемо з’ясувати поступово.

Що розуміється під терміном "лінійна оптимізація"?
Як можна математично сформулювати задачу?
Відомі випадки використання лінійної оптимізації?
Які існують методи вирішення?
Які рішення можливі?

Пояснення в цій главі обмежуються лінійною оптимізацією з двома змінними.

Що таке лінійна оптимізація?

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

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

лінійна оптимізація має справу з максимізацією або мінімізацією лінійної функції з обмеженнями.

Математичне формулювання

Так звана "лінійна програма" (ЛП) складається з наступних компонентів

Цільова функція

Лінійна функція, яку слід максимізувати (мінімізувати), називається цільовою функцією, а змінні (\ (x \), \ (y \)), що виникають у цільовій функції, називаються змінними рішення.

Обмеження (обмеження)

\ (\ begina_1x + b_1y & \ leq c_1 \\ a_2x + b_2y & \ leq c_2 \\\ qquad \ vdots \ qquad \ vdots \\ a_nx + b_ny & \ leq c_n \ end \)

(Умова невід’ємності)

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

Екскурс: Що графічно означає умова невід’ємності?

\ (x \ geq 0 \) графічно означає, що для розгляду релевантною є лише область праворуч від осі y.

\ (y \ geq 0 \) графічно означає, що для розгляду релевантною є лише область над віссю х.

Якщо спостерігати як \ (x \ geq 0 \), так і \ (y \ geq 0 \), виявляється, що для розгляду має значення лише 1-й квадрант системи координат.

Таким чином, область, виділена кольором, є областю, яка відповідає умові невід'ємності.

Програми

На практиці існує велика кількість додатків для лінійної оптимізації. Деякі з них будуть пояснені більш докладно на прикладах.

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

На цьому етапі настійно рекомендуємо ще раз переглянути розділ "Лінійні системи нерівностей з двома змінними".

а) виробнича проблема

Два різні типи кабелів виробляються на заводі і продаються за 150 євро (тип А) та 100 євро (тип В) за 100 метрів. Для кабелів типу А потрібно 16 кг пластику та 4 кг міді. Для кабелів типу B потрібно 6 кг пластику та 12 кг міді. Кількість виробленого В не повинно перевищувати подвійного вмісту А. Крім того, в даний час запас матеріалу складає лише 252 кг пластику та 168 кг міді.

Які кількості двох типів кабелів максимізують оборот компанії, дотримуючись обмежень?

1.) Чітка компіляція завдання

2.) Математична постановка задачі

Цільова функція	\ (z (x, y) = 150x + 100y \ quad \ rightarrow \ quad \ text \)
Обмеження	\ (\ початок 16x + 6y & \ leq 252 \\ 4x + 12y & \ leq 168 \ кінець \)
. а через \ (y \ leq 2x \) маємо:	\ (2x - y \ geq 0 \)
Умова невід’ємності	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Графічний розгляд

Чи хотіли б ви першу вторинну умову
\ (16x + 6y \ leq 252 \)
малюючи в системі координат, потрібно вирішити нерівність для \ (у \) \ (6y \ leq - 16x + 252 \)
\ (y \ leq - \ fracx + 42 \)
а потім інтерпретувати нерівність як прямолінійне рівняння
\ (y = - \ fracx + 42 \)

Кольорова зона вказує на область, яка відповідає 1-й вторинній умові.

Чи хотіли б ви другу вторинну умову
\ (4х + 12 років \ leq 168 \)
малюючи в системі координат, потрібно вирішити нерівність для \ (у \) \ (12y \ leq - 4x + 168 \)
\ (y \ leq - \ fracx + 14 \)
а потім інтерпретувати нерівність як прямолінійне рівняння
\ (y = - \ fracx + 14 \)

Кольорова зона вказує на область, яка відповідає 2-й вторинній умові.

Третя вторинна умова:
"Кількість виробленого В не повинно перевищувати подвійного обсягу А."
. або сформульовано математично: \ (y \ leq 2x \)

Кольорова область вказує область, яка відповідає 3-й вторинній умові.

Набір рішень системи лінійної нерівності.
\ (16x + 6y \ leq 252 \)
\ (4х + 12 років \ leq 168 \)
\ (y \ leq 2x \)
.виділено кольором на сусідній графіці.

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

4.1) Визначити оптимальне рішення (математичне)

Оскільки оптимум відповідає кутовій точці області розчину, спочатку ми зчитуємо його: \ (P_1 (0,0) \); \ (P_2 (6.12) \); \ (P_3 (12,10) \); \ (P_4 (15,75; 0) \);

Тепер ми ставимо точки в цільову функцію і визначаємо максимум.

\ (z (0,0) = 150 \ раз 0 + 100 \ раз 0 = 0 € \)

\ (z (6.12) = 150 \ разів 6 + 100 \ разів 12 = 2100 € \)

\ (z (12.10) = 150 \ cdot 12 + 100 \ cdot 10 = 2800 € \ qquad \ rightarrow \ quad \ text \)

\ (z (15,75; 0) = 150 \ разів 15,75 + 100 \ разів 0 = 2362,50 € \)

відповідь:
Фабрика максимізує свої продажі, дотримуючись обмежень, коли виробляє кабель типу 12 х 100 м типу А та кабель типу В 10 х 100 м типу В.

4.2) Визначити оптимальне рішення (графічно)

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

Спочатку вирішуємо цільову функцію для \ (у \).
\ (z (x, y) = 150x + 100y = 0 \)
\ (100y = -150x \)
\ (y = -1,5x \)
.намалювати їх у системі координат. Потім рухаємося прямою паралельно, поки не дійдемо до останнього кута області розчину.

Оптимум (тут: максимум) відображається на графіку червоною крапкою.

б) Транспортна проблема

Авіакомпанія хоче встановити авіасполучення між двома містами. Мета - перевезти 1600 людей та 96 тонн вантажу протягом певного періоду часу. В даний час доступні два типи літаків: 11 літаків типу А та 8 літаків типу В. Тип А коштує 4000 євро за рейс і може перевезти 200 осіб та 6 тонн вантажу. Тип B коштує 1000 євро за рейс і може перевезти 100 людей та 15 тонн вантажу.

Як і багато літальних апаратів кожного типу, авіакомпанія діятиме з обмеженнями, щоб мінімізувати свої витрати?

1.) Чітка компіляція завдання

\ почати
& \ text & \ text & \ text \\ \ hline
\ text & 200 & 100 & 1600 \\ \ hline
\ text & 6 & 15 & 96 \\ \ hline
\ text & 4000 & 1000 &
\ кінець

2.) Математична постановка задачі

Цільова функція	\ (z (x, y) = 4000x + 1000y \ quad \ rightarrow \ quad \ text \)
Обмеження	\ (\ початок 200x + 100y & \ geq 1600 \\ 6x + 15y & \ geq 96 \ кінець \)
. також застосовується:	\ (x \ leq 11 \) \ (y \ leq 8 \)
Умова невід’ємності	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Графічний розгляд

Чи хотіли б ви першу вторинну умову
\ (200x + 100y \ geq 1600 \)
малюючи в системі координат, потрібно вирішити нерівність для \ (у \) \ (100y \ geq -200x + 1600 \)
\ (y \ geq -2x + 16 \)
а потім інтерпретувати нерівність як прямолінійне рівняння
\ (y = -2x + 16 \)

Кольорова зона вказує на область, яка відповідає 1-й вторинній умові.

Чи хотіли б ви другу вторинну умову
\ (6x + 15y \ geq 96 \)
малюючи в системі координат, потрібно вирішити нерівність для \ (y \) \ (15y \ geq - 6x + 96 \)
\ (y \ geq - 0,4x + 6,4 \)
а потім інтерпретувати нерівність як прямолінійне рівняння
\ (y = - 0,4x + 6,4 \)

Кольорова зона вказує на область, яка відповідає 2-й вторинній умові.

Третя вторинна умова
\ (x \ leq 11 \)
є паралеллю осі y з перетином осі \ (x = 11 \).

Кольорова область вказує область, яка відповідає 3-й вторинній умові.

4-а вторинна умова
\ (y \ leq 8 \)
є паралеллю осі x із перетином осі \ (y = 8 \).

Кольорова область вказує область, яка відповідає 4-й вторинній умові.

Набір рішень системи лінійної нерівності.
\ (200x + 100y \ geq 1600 \)
\ (6x + 15y \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.виділено кольором на сусідній графіці.

4.1) Визначити оптимальне рішення (математичне)

Оскільки оптимум відповідає кутовій точці області розчину, спочатку ми зчитуємо його: \ (P_1 (6,4) \); \ (P_2 (4.8) \); \ (P_3 (11.8) \); \ (P_4 (11.2) \);

Тепер ми ставимо точки в цільову функцію і визначаємо мінімум.

\ (z (6.4) = 4000 \ раз 6 + 1000 \ раз 4 = € 28000 \)

\ (z (4.8) = 4000 \ разів 4 + 1000 \ разів 8 = 24000 € \ qquad \ rightarrow \ quad \ text \)

\ (z (11,8) = 4000 \ разів 11 + 1000 \ разів 8 = 52000 € \)

\ (z (11.2) = 4000 \ разів 11 + 1000 \ разів 2 = 46000 € \)

відповідь:
Авіакомпанія мінімізує свої витрати відповідно до обмежень, якщо експлуатує 4 літаки типу А та 8 літаків типу В.

4.2) Визначити оптимальне рішення (графічно)

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

Спочатку вирішуємо цільову функцію для \ (у \).
\ (z (x, y) = 4000x + 1000y = 0 \)
\ (1000y = -4000x \)
\ (y = -4x \)
.намалювати їх у системі координат. Потім рухаємо пряму паралельно, поки не дійдемо до першого кута області розчину.

Оптимум (тут: мінімум) відображається на графіці червоною крапкою.

Можливі рішення

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

Далі ви знайдете графічний приклад кожного рішення. Завдання - завжди знайти мінімум.

Чітке оптимальне рішення

. Вище ми вже детально розглянули два приклади.

Нескінченна кількість оптимальних рішень

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

Не оптимальне рішення

Бувають випадки, коли немає оптимального рішення.

Висновок

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

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

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

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

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

Мене звуть Андреас Шнайдер, і я з 2013 року працюю на платформі навчання математики www.mathebibel.de, яка отримала багато нагород. Щомісяця мої заяви переглядають до 1 мільйона учнів, батьків та вчителів. Я публікую новий вміст майже щодня. Підпишіться на мій бюлетень зараз і отримайте 3 з 46 електронних книг безкоштовно!

PS: Я вже бачив поточний серіал моєї серії #MathAmMontag?