Урок 57                                                                      Інформатика ІКТ

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

Мета:

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

Виховна: виховувати старанність, активність при вивченні нового матеріалу, уміння працювати в групі; сприяти самостійній роботі за комп’ютером;

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

Тип уроку: урок вивчення нового матеріалу.

Обладнання: комп’ютери.

Терміни і поняття: табличний процесор Місrоsoft Excel 2003, електронна таблиця, зведена таблиця, консолідація.

Матеріали для роботи з учнями:

Методичні рекомендації з лінійного програмування

План уроку:

I. Організаційний момент

II. Перевірка домашнього завдання

III. Актуалізація опорних знань

IV. Вивчення нового матеріалу

V. Підведення підсумків уроку

VІ. Домашнє завдання

Пам’ятка для учня!

1.  Пригадайте правила техніки безпеки при роботі з ПК.

2.  Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку:

1. Організаційна частина

2. Перевірка домашнього завдання.

1. Наявність.
2. Питання.

3. Актуалізація опорних знань

1. Що таке чисельні методі?
2. У чому полягає метод виділення коренів?
3. У чому полягає метод ітерації?

4. Вивчення нового матеріалу.

Математична модель оптимізаційної задачі

У багатьох задачах вимагається не просто знайти який-небудь розв’язок, а підібрати серед усіх розв’язків найкращий (оптималь­ний). Йдеться про такі задачі, як підбір збалансованого раціо­ну харчування, оптимізація асортименту продукції, оптимізація транспортних перевезень та багато інших — їх ще називають оптимізаційними.

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

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

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

f(x) = х + sinx min;

0   х  10.

Тут змінною є х, цільовою функцією — f(x), критерієм — вимога мінімізації (—> min), а обмеженнями — 0   х  10.

Добре дослідженим та важливим для планування виробничих про­цесів різновидом оптимізаційних задач є задачі лінійного про­грамування (ЗЛП), тобто задачі, в яких цільова функція та об­меження є лінійними. У загальному випадку математична модель ЗЛП має такий вигляд:

Тут х1, … xn — змінні; аij, bi  та сi — деякі числа; (1) — цільова функція разом із критерієм; (2) і (3) — обмеження. Зазначимо, що обмеження (3) називаються прямими, а обмеження (2) — не­прямими. У непрямих обмеженнях замість знаків «» можуть стояти знаки «» або «=». Крім того, можуть накладатися додат­кові обмеження, наприклад, може вимагатися, щоб змінні були цілочисельними.

Aлгоритм розв’язання оптимізаційної задачі

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

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

Графічний метод розв’язування ЗЛП

Графічний метод на площині застосовується насамперед для ЗЛП, заданих в стандартній формі відносно двох змінних х1 і х2 .

Нехай треба знайти максимум або мінімум лінійної функції

за умов

Для графічного розв’язування цієї задачі використовують наступний алгоритм:

1. Зобразимо на площині х1Ох2 множину точок, які задовольняють нерівності (2.2) і (2.3). Для цього побудуємо прямі: аі1х1 + аі 2 х2 = bі. Кожна пряма аі1х1 + аі2х2 = bi (і = 1,..., т) поділяє площину на дві півплощини. Точки однієї з цих півплощин задовольняють вказану нерівність, іншої - ні. Щоб визначити півплощину, точки якої задовольняють нерівність, треба в цю нерівність підставити координати будь-якої точки координатної площини (якщо b0, то краще взяти початок координат). Якщо координати цієї точки задовольняють нерівність, то нерівність будуть задовольняти всі точки півплощини, яка її містить. Якщо координати цієї точки не задовольняють нерівність, то нерівність будуть задовольняти всі точки іншої півплощини.

Припустимо, що вже побудовані всі прямі і визначені півплощини, точки яких задовольняють відповідні нерівності. Перетином (спільною частиною) півплощин буде деяка область К, множина точок якої є множиною розв’язків системи (2.2). Множина точок, які задовольняють умову (2.3), утворює першу координатну чверть. Тому множиною точок, які задовольняють умови (2.2), (2.3), є та частина області К, яка лежить у першій координатній чверті. Позначимо цю множину (множину допустимих розв’язків ЗЛП) через М. Зауважимо, що М може бути порожньою множиною, опуклим многокутником або необмеженою опуклою многокутною областю. В першому випадку ЗЛП не має розв’язку, тому що її умови суперечливі. В другому випадку завжди існують точки, в яких функція набуває мінімального і максимального значень. В третьому випадку для лінійної форми може не існувати максимуму або мінімуму, або максимуму та мінімуму одночасно.

2. Побудуємо вектор нормалі n лінії рівня лінійної форми f, тобто вектор n = {с1; с2 }.
3. Побудувавши в середині області М лінію рівня, тобто перпендикулярну до n пряму, зміщуємо її паралельно самій собі в напрямку нормалі n, якщо необхідно знайти максимум лінійної форми f і в протилежному до n напрямку, якщо треба знайти мінімальне значення функції f. Зміщення продовжуємо до тих пір, поки ця пряма буде мати хоча б одну спільну точку з областю М, тоді в своєму крайньому положенні вказана пряма пройде через точку області М, в якій цільова функція прийме оптимальне значення. Якщо М - опуклий многокутник, то оптимальне значення лінійної функції завжди досягається в її вершині. Якщо оптимальне значення досягається в двох вершинах, то f набуває його в будь-якій точці, що лежить на відрізку, який їх з’єднує.
4. Координати потрібної вершини знаходимо, розв’язуючи систему рівнянь прямих, на перетині яких вона знаходиться.

Якщо оптимальним розв’язком є точки відрізку, то знаходимо координати кінцевих точок цього відрізку X1опт і Х2опт, а загальний розв’язок записуємо за формулою

У випадку необмеженої області М оптимальна межа може бути необмеженою. В цьому випадку, знайшовши один з оптимальних розв’язків X1опт, за Х2опт візьмемо довільну точку оптимальної межі. Тоді всі оптимальні розв’язки визначатимуться за формулою

Приклад.

Розв’язати графічним методом ЗЛП на максимум і мінімум:

Розв’ язання.

В площині xOy будуємо множину допустимих розв’язків ЗЛП - область М.

Для знаходження півплощини, яка визначається першою нерівністю, підставимо в цю нерівність координати т. О (О; О). Оскільки одержуємо вірну нерівність (О < 2), то шуканою півплощиною є та, яка містить т. О. Аналогічно, знаходимо півплощини, які визначаються другою та третьою нерівностями. Враховуючи вимогу x  0 і y  0, одержимо область М - п’ятикутник OAВСD.

1.   Будуємо вектор n = {2; - 2} і лінію рівня ln .

Для знаходження точки максимуму зміщуємо лінію рівня l в напрямку n. В своєму крайньому положенні вона буде проходити через точку С області М. Її координати знаходимо, розв’язуючи систему

Для знаходження точок мінімуму функції f зміщуємо пряму І в напрямку протилежному вектору n. В своєму крайньому положенні пряма І буде містити відрізок АВ області М, тобто всі точки цього відрізку є оптимальними для мінімізації функції f. Такий розв’язок ЗЛП називається альтернативним.

Знаходимо координати кінцевих точок відрізку як точок перетину відповідних прямих: т. A (0;2) і т. B(1,25;3,25). Тоді

Xmin = t • (0;2) + (1 -t) • (1,25; 3,25) = (1,25 - 1,25t; 3,25 - 1,25t), 0  t 1.

Підставивши координати т. А в лінійну форму f, знаходимо мінімальне значення функції f: fmin = -4.

Відповідь: Xmax = {3;1},  fmax = 4,

Xmin = (1,25 - 1,25t; 3,25 - 1,25t), 0  t 1,

fmin=-4.

Зауваження. Графічний метод розв’язування ЗЛП використовується також для задач канонічної або загальної форми, якщо після перетворення їх у стандартну форму залишається лише дві змінні.

Розв’язати транспортну задачу (рекомендації щодо розв’язування)

У пунктах постачання А1, А2, А3 є однорідний вантаж в обсязі а1, а2, а3 одиниць відповідно; цей вантаж треба транспортувати у пункти В1, В2, В3 в обсязі відповідно b1, b2, b3 одиниць. Потреби замовника (в умовних одиницях), запаси вантажу на кожному пункті постачання (у тих же одиницях) і тарифи (вартість перевезення одиниці вантажу з даного пункту постачання даному замовнику) вказані в таблиці. Потрібно спланувати перевезення так, щоб загальна сума вартості перевезень була найменшою.

5. Підсумки уроку.

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

1. Вивчити конспект.
2. Виконати завдання:

1. Графічним методом розв’язати задачу:

2. У пунктах постачання А1, А2, А3 є однорідний вантаж в обсязі а1, а2, а3 одиниць відповідно; цей вантаж треба транспортувати у пункти В1, В2, В3, В4, В5 в обсязі відповідно b1, b2, b3, b4, b5 одиниць. Потреби замовника (в умовних одиницях), запаси вантажу на кожному пункті постачання (у тих же одиницях) і тарифи (вартість перевезення одиниці вантажу з даного пункту постачання даному замовнику) вказані в таблиці. Потрібно спланувати перевезення так, щоб загальна сума вартості перевезень була найменшою.

Задачі для самостійного розв’язування