1 of 26

Розв’язування оптимізаційних задач

За навчальною програмою 2018 року

Урок 14

10

2 of 26

Запитання

Розділ 2 § 2.5

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

Як ви вибираєте, який саме вид молока (або іншого продукту) купити, якщо є кілька його видів?

Як ви розумієте терміни «оптимальний», «оптимізація»? Наведіть приклади.

10

3 of 26

Задачі оптимізації

Розділ 2 § 2.5

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

Ці задачі люди розв'язують:

у побуті

на вироб-ництві

в економіці

на транспорті

у військовій справі тощо

10

4 of 26

Задачі оптимізації

Розділ 2 § 2.5

Наприклад, якщо вам потрібно поїхати на виставу в театр, то ви шукаєте з усіх можливих:

або

І приймаєте кожного разу конкретне рішення, яким маршрутом ви поїдете саме того дня.

найшвидший маршрут

найдешевший маршрут

10

5 of 26

Задачі оптимізації

Розділ 2 § 2.5

Якщо потрібно створити новий літак, то велика група людей приймає рішення:

які матеріали

скільки людей

скільки енерго-ресурсів

скільки коштів та іншого

Потрібно використати (і все це в межах допустимих можливостей), щоб у майбутньому продаж нового літака приніс найбільший можливий прибуток.

10

6 of 26

Задачі оптимізації

Розділ 2 § 2.5

Якщо планують військову операцію, то приймають рішення:

як її провести

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

10

7 of 26

Задачі оптимізації

Розділ 2 § 2.5

Для розв'язування таких задач у побуті люди часто користуються:

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

інтуїцією

життєвим досвідом

10

8 of 26

Задачі оптимізації

Розділ 2 § 2.5

Розв'язування таких задач в інших галузях діяльності людини вимагає застосування спеціальних наукових методів для планування діяльності й прийняття рішень, які розробляються із середини XX ст. Ці методи полягають у такому:

Записують сукупність допустимих можливостей, умов, ресурсів тощо як систему рівнянь і/або нерівностей — систему обмежень.

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

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

10

9 of 26

Задачі оптимізації

Розділ 2 § 2.5

Розглянемо приклад такої задачі й алгоритм її розв'язування з використанням табличного процесора Excel.

Задача 1. Підприємство випускає столи двох моделей: А і В. Для випуску одного столу моделі А потрібно 3 одиниці сировини та 2 одиниці машинного часу. Для випуску одного столу моделі В — 4 одиниці сировини та 5 одиниць машинного часу. Прибуток від реалізації одного столу моделі А складає 2 грошові одиниці, столу моделі В — 4 грошові одиниці. На підприємстві на тиждень наявні 1700 одиниць сировини та 1600 одиниць машинного часу. Визначити, яким повинен бути план виробництва на тиждень, щоб підприємство отримало максимальний прибуток.

10

10 of 26

Задачі оптимізації

Розділ 2 § 2.5

Побудуємо математичну модель для цієї задачі.

Нехай х₁ — кількість столів моделі А, випущених за тиждень, а х₂ — кількість столів моделі В. Щотижневий прибуток від реалізації такої кількості продукції виражатиметься значеннями функції:

Z = 2 * х₁ + 4 * х₂

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

10

11 of 26

Задачі оптимізації

Розділ 2 § 2.5

Запишемо систему обмежень на ресурси для даного плану виробництва. Обмеження на сировину виражаються нерівністю:

3 * х₁ + 4 * х₂ ≤ 1700

Обмеження на машинний час:

2 * х₁ + 5 * х₂ ≤ 1600

10

12 of 26

Задачі оптимізації

Розділ 2 § 2.5

Крім того, очевидно, що х₁ і х₂ можуть набувати тільки невід'ємних значень. Маємо таку систему обмежень:

10

13 of 26

Задачі оптимізації

Розділ 2 § 2.5

Потрібно знайти такі значення змінних х₁ та х₂, за яких будуть виконуватися нерівності у системі обмежень, а цільова функція Z набуде максимального значення.

У процесі використання Excel для розв'язування задач оптимізації на Стрічці на вкладці Дані має бути група елементів керування Аналіз з кнопкою Розв'язувач.

10

14 of 26

Задачі оптимізації

Розділ 2 § 2.5

Якщо ця група не відображається на вкладці Дані, потрібно виконати Файл ⇒ Параметри і далі у вікні Параметри Excel виконати Надбудови ⇒ Пошук розв'язання ⇒ Перейти.

1

2

3

10

15 of 26

Задачі оптимізації

Розділ 2 § 2.5

Після цього у вікні Надбудови встановити позначку прапорця Пошук розв'язання і вибрати ОК.

1

2

10

16 of 26

Задачі�оптимізації

Розділ 2 § 2.5

Для розв'язування наведеної задачі потрібно:

Увести початкові значення змінних, наприклад увести в клітинки С2 і СЗ значення 0 для змінних х₁, та х₂.

10

17 of 26

Задачі оптимізації

Розділ 2 § 2.5

(Продовження…)

Увести формули, що відповідають нерівностям системи обмежень, наприклад увести:

в клітинку С5 формулу

в клітинку С6 формулу

=3*С2+4*СЗ

=2*С2+5*СЗ

що відповідає лівій частині першої нерівності системи

що відповідає лівій частині другої нерівності системи

10

18 of 26

Задачі оптимізації

Розділ 2 § 2.5

(Продовження…)

Увести формулу, що відповідає цільовій функції, наприклад увести в клітинку С8 формулу =2*С2+4*СЗ.

Виконати Дані ⇒ Аналіз ⇒ Розв'язувач.

10

19 of 26

Задачі�оптимізації

Розділ 2 § 2.5

5. Заповнити поля та встановити позначки елементів керування вікна Параметри розв'язувана відповідно до умови задачі, наприклад за зразком

6. Вибрати кнопку Розв'язати.

10

20 of 26

Задачі оптимізації

Розділ 2 § 2.5

Після цього в клітинках із значеннями змінних

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

10

21 of 26

Задачі оптимізації

Розділ 2 § 2.5

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

х₁ = 300

х₂ = 200

та

При цьому ліві частини нерівностей системи обмежень (клітинки С5 і С6) матимуть граничні значення: 1700 та 1600.

Отже, за оптимального плану потрібно щотижнево виготовляти 300 столів моделі А та 200 столів моделі В. При цьому буде повністю використано наявні виробничі ресурси, а підприємство отримає максимальний прибуток — 1400 грошових одиниць.

10

22 of 26

Розгадайте ребус

Оптимізація

Розділ 2 § 2.5

10

23 of 26

Дайте відповіді на запитання

Розділ 2 § 2.5

Які задачі називаються задачами оптимізації?

З яких етапів складається розв'язування задач оптимізації?

Які задачі оптимізації ви розв'язували під час вивчення різних предметів?

Які задачі оптимізації ви розв'язували у повсякденному житті?

Який алгоритм розв'язування задачі оптимізації з використанням табличного процесора?

10

24 of 26

Домашнє завдання

Проаналізувати

§ 2.5, ст. 64-68

Розділ 2 § 2.5

10

25 of 26

Працюємо за комп’ютером

Розділ 2 § 2.5

Сторінка

66-67

10

26 of 26

Дякую за увагу!

За навчальною програмою 2018 року

Урок 14

10