1 of 26

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

2-ге видання, оновлене

Урок 14

Інформатика

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.

Рівень стандарту 10(11)

2 of 26

Запитання

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

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

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

Розділ 2

§ 2.5

3 of 26

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

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

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

у побуті

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

в економіці

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

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

Розділ 2

§ 2.5

4 of 26

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

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

або

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

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

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

Розділ 2

§ 2.5

5 of 26

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

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

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

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

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

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

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

Розділ 2

§ 2.5

6 of 26

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

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

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

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

Розділ 2

§ 2.5

7 of 26

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

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

інтуїцією

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

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

Розділ 2

§ 2.5

8 of 26

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

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

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

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

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

Розділ 2

§ 2.5

9 of 26

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

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

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

Розділ 2

§ 2.5

10 of 26

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

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

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

Z = 2 * х₁ + 4 * х₂

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

Розділ 2

§ 2.5

11 of 26

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

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

3 * х₁ + 4 * х₂ ≤ 1700

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

2 * х₁ + 5 * х₂ ≤ 1600

Розділ 2

§ 2.5

12 of 26

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

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

Розділ 2

§ 2.5

13 of 26

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

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

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

Розділ 2

§ 2.5

14 of 26

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

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

1

2

3

Розділ 2

§ 2.5

15 of 26

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

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

1

2

Розділ 2

§ 2.5

16 of 26

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

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

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

Розділ 2

§ 2.5

17 of 26

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

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

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

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

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

=3*С2+4*СЗ

=2*С2+5*СЗ

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

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

Розділ 2

§ 2.5

18 of 26

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

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

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

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

Розділ 2

§ 2.5

19 of 26

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

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

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

Розділ 2

§ 2.5

20 of 26

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

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

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

Розділ 2

§ 2.5

21 of 26

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

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

х₁ = 300

х₂ = 200

та

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

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

Розділ 2

§ 2.5

22 of 26

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

Оптимізація

Розділ 2

§ 2.5

23 of 26

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

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

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

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

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

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

Розділ 2

§ 2.5

24 of 26

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

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

§ 2.5, с. 64-68

Розділ 2

§ 2.5

25 of 26

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

Сторінка

66-67

Розділ 2

§ 2.5

26 of 26

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

2-ге видання, оновлене

Урок 14

Інформатика

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.

Рівень стандарту 10(11)