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

Розв’язування оптимізаційних задач.10 клас

ЗАДАЧІ ОПТИМІЗАЦІЇЗадачі, які визначають найкращий у певному сенсі (найдешевший, найшвидший, з найменшими втратами, з найбільшими прибутками тощо) план дій, називаються задачами оптимізації (лат. optimus — найкращий, досконалий). Для розв’язування таких задач у побуті люди часто користуються інтуїцією, життєвим досвідом. Розв’язування таких задач в інших галузях діяльності людини вимагає застосування спеціальних наукових методів для планування діяльності й прийняття рішень, які розробляються із середини ХХ ст. Ці методи полягають у такому:1 . Записують сукупність допустимих можливостей, умов, ресурсів тощо як систему рівнянь і/або нерівностей — систему обмежень.2 . Задають для визначення оптимального варіанта цільову функцію, яка повинна набути максимального або мінімального значення (залежно від поставленої задачі) для тих значень аргументів, які задовольняють систему обмежень.3 . Шукають мінімум або максимум цільової функції та відповідні йому значенняаргументів з урахуванням системи обмежень, що й вважається розв’язком задачі оптимізації.

Модель оптимізаційної задачі складається з елементів: Змінні – невідомі величини, значення яких потрібно знайти в результаті розв’язання задачі;цільова функція – величина, яка залежить від змінних і значення якої потрібно максимізувати чи мінімізувати;критерій – вимоги мінімізації та максимізації цільової функції;обмеження – умови, яким мають задовольняти змінні. f(x)= x+sinx → min;0 ≤ x ≤ 10 Тут змінною величиною є - Х; цільова функція - f(x)критерієм - вимога мінімізації (→ min) ; обмеження - 0≤ х ≤ 10 Найпростішою оптимізаційною задачею вважається задача пошуку максимального або мінімального значення функції однієї змінної.

Загалом алгоритм розв’язання оптимізаційної задачі:1. Введення позначень. Потрібно визначити, яка змінна яку величину позначатиме.2. Створення цільової функції та критерію. Записати формулу цільової функції. Нею може бути вартість продукції, обсяг прибутку, обсяг витрат на виробництво та перевезення. Слід визначити, яка величина максимізуватиметься чи мінімізуватиметься.3. Складання системи обмежень. Обмеження – це нерівності або рівності, яким мають задовольняти значення змінних.4. Розв’язання задачі. Деякі оптимізаційні задачі можна розв’язати аналітично, але такий спосіб трудомісткий простіше засобами табличного процесора. Це будуть задачі на пошук екстремуму функції однієї змінної так і задачі лінійного програмування.

Задача 1. Підприємство випускає столи двох моделей: A і B. Для випуску одного столу моделі A потрібно 3 одиниці сировини та 2 одиниці машинного часу. Для випуску одного столу моделі B — 4 одиниці сировини та 5 одиниць машинного часу. Прибуток від реалізації одного столу моделі A складає 2 грошові одиниці, столу моделі B — 4 грошові одиниці. На підприємстві на тиждень наявні 1700 одиниць сировини та 1600 одиниць машинного часу. Визначити, яким повинен бути план виробництва на тиждень, щоб підприємство отримало максимальний прибуток. МАТЕМАТИЧНА МОДЕЛЬ ЗАДАЧІНехай x1 — кількість столів моделі А, .випущених .за .тиждень, x2 — кількість столів моделі B. Щотижневий прибуток від реалізації такої кількості продукції виражатиметься значеннями функції: Z = 2 ⋅ x1 + 4 ⋅ x2. Функція Z — це цільова функція. Для того щоб підприємство мало максимальний прибуток, потрібно, щоб функція Z набула максимального значення.

Запишемо систему обмежень на ресурси для даного плану виробництва. Обмеження на сировину виражаються нерівністю:3 ⋅ x1 + 4 ⋅ x2 ≤1700. Обмеження на машинний час:2 ⋅ x1 + 5 ⋅ x2 ≤1600. Крім того, очевидно, що x1 і x2 можуть набувати тільки невід’ємних значень. Маємо таку систему обмежень: 3∙𝑥1+4∙𝑥2≤1700,2∙𝑥1+5∙𝑥2≤1600,𝑥1≥0, 𝑥2≥0. Потрібно знайти такі значення змінних x1 та x2, за яких будуть виконуватися нерівності у системі обмежень, а цільова функція Z набуде максимального значення.  

У процесі використання Excel для розв’язування задач оптимізації на Стрічці на вкладці Дані має бути група елементів керування Аналіз з кнопкою Розв’язувач. Якщо ця група не відображається на вкладці Дані, потрібно виконати Файл ⇒ Параметри і далі у вікні Параметри Excel виконати Надбудови ⇒ Пошук розв’язання ⇒ Перейти. Після цього у вікні Надбудови встановити позначку прапорця Пошук розв’язання і вибрати ОК. !

РОЗВ’ЯЗУВАННЯ ЗАДАЧІ1. Увести початкові значення змінних, наприклад увести в комірки С2 і С3 значення 0 для змінних x1 та х2 2. Увести формули, що відповідають нерівностям системи обмежень, наприклад увести в комірку С5 формулу =3*C2+4*C3, що відповідає лівій частині першої нерівності системи, а в клітинку С6 — формулу =2*C2+5*C3, що відповідає лівій частині другої нерівності системи.3. Увести формулу, що відповідає цільовій функції, наприклад увести в комірку С8 формулу =2*C2+4*C34. Виконати Дані ⇒ Аналіз ⇒ Розв’язóвач5. Заповнити поля та встановити позначки елементів керування вікна Параметри розв’язувача відповідно до умови задачі.6. Вибрати кнопку Розв’язати

Після цього в комірках із значеннями змінних (це комірки С2 і С3) за спеціальним алгоритмом будуть змінюватися значення так, щоб значення в клітинці із значенням цільової функції (це комірка С8) стало оптимальним відповідно до умови задачі. Для розглянутої задачі цільова функція набуде максимального значення 1400 при значеннях змінних х1 = 300 та х2 = 200. При цьому ліві частини нерівностей системи обмежень (комірки С5 і С6) матимуть граничні значення: 1700 та 1600. Отже, за оптимального плану потрібно щотижнево виготовляти 300 столів моделі А та 200 столів моделі В. При цьому буде повністю використано наявні виробничі ресурси, а підприємство отримає максимальний прибуток — 1400 грошових одиниць.

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