Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
КЛАСИЧНІ МЕТОДИ ОПТИМІЗАЦІЇ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 5
“КЛАСИЧНІ МЕТОДИ ОПТИМІЗАЦІЇ ”
з дисциплін “Математичні методи дослідження операцій”
і “Методи оптимізації та дослідження операцій”
для студентів базових напрямків
“Комп’ютерні науки” та “Легка промисловість”
стаціонарної і заочної форм навчання
Затверджено
на засіданні кафедри
автоматизованих систем управління
Протокол № 6 від 13 листопада 2003 року
Львів – 2008
Методичні вказівки до лабораторної роботи № 5 “Класичні методи оптимізації” з дисциплін “Математичні методи дослідження операцій” та “Методи оптимізації та дослідження операцій” для студентів базових напрямків “Комп’ютерні науки” і “Легка промисловість” стаціонарної і заочної форм навчання / Укл. Я.П. Романчук, А.М. Ковальчук. – Львів: Видавництво національного університету “Львівська політехніка”, 2003. – 10 с.
Укладачі: Романчук Я.П., кад. фіз.-мат. наук, доц.
Ковальчук А.М., асистент.
Відповідальна за випуск Дронюк І.М., канд. фіз.-мат. наук, доц.
Рецензенти: Вальковський В.О., д-р техн. наук, проф.
Різник В.В., д-р техн. наук, проф.
ЛАБОРАТОРНА РОБОТА № 5
Тема: “Класичні методи оптимізації”.
Мета роботи: Закріпити навики дослідження функцій з використанням класичних методів оптимізації.
Завдання: Для вказаного індивідуального варіанту знайти точки екстремуму й намалювати графік функції.
ВСТУП
Лабораторна робота базується на лекційному матеріалі з курсів “Математичні методи дослідження операцій” (ММДО) і “Методи оптимізації та дослідження операцій” (МОДО), “Математичного аналізу”, задачах, методах і алгоритмах, наведених у відповідних збірниках і довідниках.
Приклад 1. Дослідити на екстремум функцію y = x3 – 3x + 5.
Розв’язування. Похідна даної функції має вигляд: y′ = 3х2 – 3 = 3 (х +1) (х –1).
Оскільки похідна існує при всіх значеннях аргументу, то точками екстремуму можуть бути лише корені рівняння (х + 1) (х –1) = 0; корені цього рівняння: –1 і 1. Похідна y′ > 0 для всіх х < –1 і для всіх х >1, а для всіх х, які задовольняють –1< х <1, похідна y′ < 0. Тому робимо висновок: точки х = – 1 і х = 1 є точками відповідно максимуму та мінімуму функції y = x3 – 3x + 5.
Приклад 2. Дослідити на екстремум функцію y = EMBED Equation.3 EMBED Equation.3
Розв’язувння. Якщо х ≠ 0, то маємо:
EMBED Equation.3
Отже, EMBED Equation.3 EMBED Equation.3
EMBED Equation.3 Тому в усіх точках х ≠ 0 похідна функції y = EMBED Equation.3 має вигляд: EMBED Equation.3
У точці х = 0 дана функція не має похідної. Справді, маємо:
EMBED Equation.3 EMBED Equation.3
і, отже, не існує границі EMBED Equation.3 , коли EMBED Equation.3 .
Функція y = EMBED Equation.3 може мати екстремум лише в точці х = 0.
З виразу для похідної бачимо, що вона від’ємна в усіх точках x < 0 і додатна в усіх точках x > 0, тому точка х = 0 – точка мінімуму функції y = EMBED Equation.3 Отже, екстремум (мінімум) розглядуваної функції дорівнює нулю.
Приклад 3. Знайти найменше та найбільше значення функції у = 2х3 – 3х2 – 12х + 6, х EMBED Equation.3 [– 3; 1].
Розв’язувння. Досліджувана функція є неперервною на відрізку [–3; 1] і диференційовною в інтервалі (– 3; 1) (як многочлен). Її похідною буде y′ = 6х2 – 6х – 12.
Рівняння 6х2 – 6х – 12 = 0 має корені х = – 1 і х = 2. Знаходимо у ( – 1) = 13. Точка х = 2 не належить відрізку [–3; 1], тому значення функції y в цій точці нас не цікавить.
Обчислюємо у ( –3) = – 39 і у (1) = – 7.
Залишилося вибрати найменше і найбільше серед чисел у ( – 3) = – 39, у ( – 1) = 13 і у (1) = – 7. Бачимо, що найменшого значення досліджувана функція у набуває в точці – 3 і воно дорівнює – 39, а найбільшого – в точці – 1 і воно дорівнює 13. Коротко це прийнято записувати так:
EMBED Equation.3
Приклад 4. Знайти найменше і найбільше значення функції y = EMBED Equation.3 , х EMBED Equation.3 [–1; 2].
Розв’язування. Скориставшись розв’язком прикладу 2, маємо:
EMBED Equation.3
Приклад 5. Дослідити на найменше значення функцію у = х3 – 10х2 – 2, х EMBED Equation.3 (0; 10).
Розв’язування. Ця функція не належить до класу функцій, для якого ми маємо алгоритм знаходження найменшого значення. Тому спочатку знайдемо найменше значення функції у = х3 – 10х2 – 2, х EMBED Equation.3 [0; 10]. Вона неперервна на відрізку [0; 10] і диференційовна в інтервалі (0; 10) (як многочлен). Її похідна y′ = 3х2 – 20х.
Єдиним розв’язком рівняння 3х2 – 20х = 0, який належить інтервалу (0; 10), є х = EMBED Equation.3 . Знаходимо EMBED Equation.3 = EMBED Equation.3 . Обчислюємо у(0) = – 2 і у (10) = – 2.
Отже, функція у = х3 – 10х2 – 2, х EMBED Equation.3 [0; 10] має EMBED Equation.3 .
Очевидно, що знайдене найменше значення буде і найменшим значенням функції у = х3 – 10х2 – 2, х EMBED Equation.3 (0; 10), оскільки точка х = EMBED Equation.3 — внутрішня точка відрізку [0; 10].
Приклад 6. Знайти найменше і найбільше значення функції y = 2| х | + х, х EMBED Equation.3 [–2; 1].
Розв’язувння. За означенням модуля
– х, якщо х < 0;
2| х | + х = 3х, якщо х ≥ 0.
Тому досліджувану функцію у можна записати у вигляді:
– х, якщо – 2 ≤ х < 0;
у = 3х, якщо 0 ≤ х ≤ 1.
Звідси легко показати, що функція у неперервна на відрізку [–2; 1] і її похідна
– 1, якщо – 2 ≤ х < 0; (покажіть це самі).
y′ =
3, якщо 0 < х < 1.
У точці х = 0 дана функція не має похідної. Справді, для функції у у точці х = 0 маємо:
– 1, якщо ∆х < 0;
3, якщо ∆х > 0.
Але тоді не існує границі EMBED Equation.3 , коли ∆х → 0, тобто функція у у точці х = 0 не має похідної. Справді, якщо припустити, що зазначена границя існує і дорівнює числу А, то за означенням границі в деякому околі точки ∆х = 0 EMBED Equation.3 = | –1 – А | < 1 і отже, для будь–якого від’ємного ∆х з цього околу |– 1 – А| < 1, тобто –1 < –1 — А < 1 або
–2 < А < 0, (1)
а для будь–якого додатного ∆х з вказаного околу |3 — А| < 1, тобто –1 < 3 — А < 1 або
2 < А < 4. (2)
Нерівності (1) і (2) суперечливі, тому припущення про існування границі EMBED Equation.3 , коли ∆х → 0, неправильне.
Отже, для розглядуваної функції у рівняння у′ = 0 коренів не має і в точці х = 0 похідна функції у не існує.
Знаходимо у(0) = 0, у(–2) = 2 і у(1) = 3. Звідси бачимо, що
EMBED Equation.3
Приклад 7. На прямому березі річки треба відгородити прямокутну ділянку з трьох боків. Є матеріал для огорожі завдовжки 400 м. Як відгородити ділянку найбільшої площі?
Розв’язувння. Нехай х – ширина, а у – довжина прямокутної ділянки. Тоді площа S ділянки дорівнює ху і, оскільки 2х + у = 400 (звідки у = 400 – 2х), то маємо цільову функцію:
S = х (400 – 2х) = 2 (– х2 + 200х), х EMBED Equation.3 (0; 200).
(Таку область визначення функції S взято з тих міркувань, що ширина і довжина ділянки повинні бути додатними).
Дослідимо на найбільше значення функцію:
z = – х2 + 200х, х EMBED Equation.3 [0; 200].
Ця функція неперервна на відрізку [0; 200] і диференційовна в інтервалі (0; 200) (як многочлен). Для її похідної маємо z′ = –2х + 200. Рівняння z′ = 0 має єдиний корінь х =100, що належить інтервалу (0; 200). Тому найбільше значення функції z слід шукати серед її значень: z (100) і z (0) = z (200) = 0. Функція z набуває найбільшого значення в точці х = 100. Оскільки точка х = 100 лежить всередині відрізку [0; 200], то вона буде точкою, в якій функція z = – х2 + 200х, х EMBED Equation.3 (0; 200), а отже, і цільова функція S набуває найбільшого значення.
Отже, шукана прямокутна ділянка повинна мати ширину 100 м і довжину 200 м.
Приклад 8. Довжина меншої основи і кожної з бічних сторін трапеції дорівнює α. Якою має бути довжина більшої основи трапеції, щоб її площа була найбільшою?
Розв’язувння. Розглядувана трапеція рівнобічна, тому, скориставшись твердженням про те, що в рівнобічній трапеції кути при основі рівні, введемо змінну: φ — гострий кут при основі трапеції. Тоді довжина більшої основи трапеції дорівнює α (1 + 2 cos φ), а висота трапеції дорівнює α sin φ (покажіть це самі); а тому площа S трапеції (цільова функція) має вигляд:
EMBED Equation.3 ,
що те саме
S = α2 sin φ (1 + cos φ), φ EMBED Equation.3 .
Дослідимо на найбільше значення функцію
у = sin φ (1 + cos φ), φ EMBED Equation.3 .
Ця функція залежить від класу функцій, для якого ми маємо алгоритм знаходження найбільшого значення. Її похідна y′ = cos φ (1 + cos φ) – sin φ · sin φ, що те саме y′ = cos 2φ + cos φ = 0 єдиний розв’язок φ = EMBED Equation.3 належить інтервалу EMBED Equation.3 . Найбільшим значенням функції у= sin φ (1 + cos φ), φ EMBED Equation.3 буде найбільше серед чисел EMBED Equation.3 . Звідси бачимо, що ця функція набуває найбільшого значення в точці EMBED Equation.3 . Оскільки точка EMBED Equation.3 – внутрішня точка відрізка EMBED Equation.3 , то вона буде точкою, в якій функція у = sin φ (1 + cos φ), φ EMBED Equation.3 EMBED Equation.3 , а отже, і цільова функція S , набуває найбільшого значення.
Шукана довжина більшої основи дорівнює α EMBED Equation.3 , тобто вона дорівнює 2α.
Приклад 9. З круглої колоди, діаметр якої дорівнює d, витесують брус з прямокутним поперечним перерізом, довжина основи якого дорівнює l, а висота – h. Якими повинні бути розміри поперечного перерізу бруса, щоб його міцність була найбільшою (міцність бруса пропорційна lh2)?
Розв’язувння. Зрозуміло, що l2 + h2 = d2 , тому міцність Р бруса визначається рівністю
Р = kl ( d2 – l2 ), l EMBED Equation.3 .(0; d ),
де к — коефіцієнт пропорційності.
Дослідимо на найбільше значення функцію:
y = l ( d2 – l2 ) = d2l – l3, l EMBED Equation.3 [0; d]
Ця функція неперервна на відрізку [0; d] і диференційовна в інтервалі ( 0; d) (як многочлен ). Її похідна у′ = d2 – 3 l2. В інтервалі ( 0; d) єдиним розв’язком рівняння
d2 – 3 l2 = 0 є число EMBED Equation.3 . Тому найбільше значення функції у слід шукати серед її значень: EMBED Equation.3 .
Бачимо, що функція у набуває найбільшого значення в точці EMBED Equation.3 . Оскільки точка EMBED Equation.3 лежить всередині відрізка [0; d], то вона буде точкою, в якій функція y = l (d2 – l2),
l EMBED Equation.3 ( 0; d), а отже, і цільова функція Р набуває найбільшого значення.
Отже, шуканий поперечний переріз бруса повинен мати (як прямокутник) основу EMBED Equation.3 і висоту EMBED Equation.3 .
Приклад 10. Два велосипедисти одночасно почали рухатись по двох прямолінійних взаємно перпендикулярних напрямах до перехрестя, перебуваючи на відстані 2 і 3 км від нього. Швидкість велосипедистів відповідно 10 і 12 км за годину. Через який час відстань між ними буде найменшою, якщо рух триватиме одну годину?
Розв’язувння. В будь–який момент часу t (0 ≤ t ≤ 1) перший велосипедист перебуватиме від перехрестя на відстані | 10t – 2 | км, а другий | 12t – 3 | км. Зрозуміло, що відстань l між велосипедистами в момент часу t є довжиною гіпотенузи прямокутного трикутника з вказаними катетами. При двох значеннях t (t = 0,2; t = 0,25) цей трикутник вироджується у відрізок прямої; проте формула відстані залишається правильною для цих значень t. За теоремою Піфагора
EMBED Equation.3 .
За цільову функцію візьмемо функцію
EMBED Equation.3 .
Ця функція є неперервною на відрізку [0; 1] і диференційовною в інтервалі (0; 1) як многочлен. Її похідна y′ = 488 t – 112 набуває нульового значення в єдиній точці EMBED Equation.3 . Порівнявши між собою значення функції у в точках EMBED Equation.3 , t = 0 і t = 1, приходимо до висновку, що точка EMBED Equation.3 є точкою, в якій ця функція набуває найменшого значення.
Відстань між велосипедистами буде найменшою через EMBED Equation.3 години від початку руху. Розглянутий алгоритм розв’язування одновимірних задач оптимізації можна застосувати до будь–якої задачі вказаного типу. Проте в окремих випадках, що визначаються властивостями цільової функції, досліджувати її на найменше (найбільше) значення можна інакше.
Приклад 11. Витрати за годину плавання деякого судна з довільною постійною швидкістю складається з двох частин: сталої, що дорівнює α грн., і змінної, яка пропорційна до кубу швидкості плавання (коефіцієнт пропорційності дорівнює k, k > 0). З якою швидкістю v плавання судна буде найекономнішим?
Розв’язувння . Нехай судно пройшло з деякою сталою швидкістю v вузлів/год. шлях S миль. Тоді воно перебувало в русі EMBED Equation.3 годин, а тому згідно з умовою витрати (в грн.) становлять:
EMBED Equation.3 .
За цільову функцію візьмемо функцію
EMBED Equation.3
яка неперервна і диференційовна в своїй області визначення. Її похідна
EMBED Equation.3
набуває нульового значення в єдиній точці EMBED Equation.3 , причому при переході через цю точку в напрямі зростання змінює знак з мінуса на плюс. Тому точка EMBED Equation.3 є точкою мінімуму функції у. Тоді шукана швидкість плавання судна EMBED Equation.3 .
Приклад 12. Яким повинен бути кут при вершині рівнобедреного трикутника площі S, щоб радіус вписаного в нього кола був найбільшим?
Розв’язувння. Нехай АВС – рівнобедрений трикутник, (АВ = ВС) даної площі S, ВD – його висота, О – центр вписаного кола (точка О належить відрізку ВD), r – радіус цього кола
(r = ОD). Позначимо кут ВАD = φ. Тоді АD = r· ctg EMBED Equation.3 , AB = EMBED Equation.3 (покажіть це самі).
Оскільки EMBED Equation.3 , то EMBED Equation.3 , звідки EMBED Equation.3 , а тому маємо:
EMBED Equation.3 .
За цільову функцію візьмемо функцію:
EMBED Equation.3 .
Ця функція є неперервною та диференційовною в області визначення як многочлен від EMBED Equation.3 (має вигляд EMBED Equation.3 ). Її похідна
EMBED Equation.3 EMBED Equation.3 .
EMBED Equation.3 В інтервалі EMBED Equation.3 рівняння EMBED Equation.3 0 має єдиний корінь EMBED Equation.3 в напрямі зростання φ похідна EMBED Equation.3 змінює знак з плюса на мінус, тому ця точка є точкою максимуму функції у. Звідси робимо висновок: EMBED Equation.3 – точка, в якій функція у набуває найбільшого значення.
Отже, радіус кола, вписаного в рівнобедрений трикутник площі S, буде найбільшим тоді, коли кут при вершині цього трикутника дорівнює EMBED Equation.3 , тобто у випадку правильного трикутника.
Приклад 13. У рівнобедрений трикутник з кутом при основі EMBED Equation.3 вписано рівнобічну трапецію. Менша основа трапеції лежить на основі трикутника, а кінці більшої основи – на рівних його сторонах. Довжина більшої основи трапеції дорівнює 2α, а меншої основи і бічних сторін – α. При якому значенні кута EMBED Equation.3 площа трикутника найменша?
Розв’язувння. Нескладно показати, що площа S трикутника АВС визначається рівністю
EMBED Equation.3 .
За цільову функцію візьмемо функцію:
EMBED Equation.3
Вона неперервна і диференційовна в своїй області визначення (як частка від ділення многочлена від tg EMBED Equation.3 на tg EMBED Equation.3 , EMBED Equation.3 ).
Знаходимо її похідну:
EMBED Equation.3
Рівняння EMBED Equation.3 0 в інтервалі EMBED Equation.3 має єдиний корінь EMBED Equation.3 , причому при переході через точку EMBED Equation.3 в напрямі зростання EMBED Equation.3 похідна EMBED Equation.3 змінює знак з мінуса на плюс, тому ця точка є точкою мінімуму функції у.
Отже, шуканий кут EMBED Equation.3 .
Приклад 14. Поперечний переріз відкритого каналу, що підводить воду до турбіни, має форму рівнобічної трапеції (нижня основа менша від верхньої). При якому нахилі EMBED Equation.3 боків « мокрий периметр » перерізу буде найменшим, якщо площа « живого перерізу » води в каналі дорівнює S, а рівень води дорівнює h?
Розв’язувння. Нехай ABCD – переріз розглядуваного каналу, MNCD – « живий переріз » води в каналі, CF – висота трапеції MNCD, кут ECN у трапеції MNCD дорівнює S.
« Мокрий периметр » Р = NC + CD + DM визначається за формулою EMBED Equation.3 .
Встановлення справедливості двох попередніх формул залишаємо читачеві; воно базується на тому, що трапеція MNCD, як і трапеція ABCD, рівнобічна. За цільову функцію візьмемо функцію:
EMBED Equation.3 .
Розгляд її похідної EMBED Equation.3 , як бачимо шуканий нахил EMBED Equation.3 боків дорівнює EMBED Equation.3 .
Завдання
Серед усіх прямокутників з діагоналлю d знайти той, площа якого найбільша.
Серед усіх трикутників із спільною стороною α і периметром 2р знайти той, що має найбільшу площу.
Серед усіх прямокутних трикутників периметра 2р знайти той, що має найбільшу площу. Розв’язати цю задачу двома способами, вибираючи як аргумент цільової функції: а) величину гострого кута; б) довжину гіпотенузи.
Серед усіх прямокутних трикутників площі S знайти той, для якого площа описаного круга буде найбільшою.
У півкруг радіуса R вписано рівнобічну трапецію так, що одна її основа збігається з діаметром. Яке значення кута EMBED Equation.3 при основі трапеції, що має найбільший периметр?
Поперечний переріз каналу, що підводить воду до турбіни, має форму рівнобічної трапеції з нижньою основою α (нижня основа менша від верхньої). При якому нахилі EMBED Equation.3 боків « мокрий периметр » перерізу буде найменшим, якщо рівень води в каналі дорівнює h?
Витрата води, яка щосекунди витікає через круглий отвір у вертикальній стінці посудини, де підтримується сталий рівень води, визначається формулою EMBED Equation.3 , де d – діаметр отвору, h – глибина його нижньої точки, с – деяка стала. При якому діаметрі d отвору витрати води будуть найбільшими?
Вантаж маси m, що лежить на горизонтальній площині, треба зсунути з місця, приклавши до нього силу F. Під яким кутом α до горизонтальної площини потрібно прикласти цю силу, щоб величина її була найменшою (коефіцієнт тертя дорівнює μ, 0< μ <1)?
Серед усіх ромбів з діагоналлю d знайти той, периметр якого найбільший.
Серед усіх правильних чотрикутних призм з діагоналлю d знайти ту, бічна поверхня якої найбільша.
У круг радіуса R вписано рівнобічну трапецію так, що її середня лінія збігається з діаметром. Яке значення кута EMBED Equation.3 при основі трапеції, що має найбільший периметр?
Серед усіх трикутників із спільною стороною α і периметром 2р знайти той, що має найбільшу площу.
Серед усіх тупокутних трикутників периметра 2р знайти той, що має найбільшу площу.
Поперечний переріз каналу, що підводить воду до турбіни, має форму трикутника з основою α.При якому нахилі EMBED Equation.3 боків « мокрий периметр » перерізу буде найменшим, якщо рівень води в каналі дорівнює h?
У круг радіуса R вписано правильний шестикутник так, що найбільша її діагональ збігається з діаметром. Яке значення кута EMBED Equation.3 шестикутника, що має найбільший периметр?
Знайтити точки екстремуму функцій:
а) у = 2х3 – 9 х2 + 12х + 5;
б) у = 3| х | + 2х.
17.
Дослідити на екстремум функції:
а) EMBED Equation.3
б) EMBED Equation.3
18.
Знайтити точки екстремуму функцій:
а) у = 2х3 – 12х2 + 12х + 7;
б) у = 7| х3 | + 6х.
19. Знайти найменше і найбільше значення функції:
а) у = 2х3 – 21х2 + 72х + 12, х EMBED Equation.3 [0; 5];
б) у = EMBED Equation.3 , х EMBED Equation.3 [–5; 10];
в) у = 2х4 – 18х2 + 7, х EMBED Equation.3 [–4; 6];
г) у = 3|х | + 2х, х EMBED Equation.3 (–1; 1].
20. Знайти найменше і найбільше значення функції:
а) у = 2х4 – 21х2 + 3х + 12, х EMBED Equation.3 [0; 7];
б) у = EMBED Equation.3 , х EMBED Equation.3 [–5; 5];
в) у = 2х3 – 18х2 + 7х, х EMBED Equation.3 [–4; 4];
г) у = 3 | х | + 2х, х EMBED Equation.3 (–1; 1].
21. Серед усіх прямокутних трикутників периметра 5р знайти той, що має наймену площу. Розв’язати цю задачу двома способами, вибираючи як аргумент цільової функції:
а) величину гострого кута; б) довжину гіпотенузи.
22. Вантаж маси m, що лежить на горизонтальній площині, треба зсунути з місця, приклавши до нього силу F. Під яким кутом α до горизонтальної площини потрібно прикласти цю силу, щоб величина її була найбільшою (коефіцієнт тертя дорівнює μ, 0< μ <1)?
23. Витрата води, яка щосекунди витікає через круглий отвір у вертикальній стінці посудини, де підтримується сталий рівень води, визначається формулою EMBED Equation.3 , де d – діаметр отвору, h – глибина його нижньої точки, с – деяка стала. При якій висоті h його нижньої точки витрати води будуть найбільшими?
СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
Зайченко Ю.П. Дослідження операцій. Підручник. – К.: ЗАТ “ВІПОЛ”. – 2000. – 688 с.
Вивальнюк Л.М., Соколенко О.І., Костарчук Ю.В. і ін. Задачі оптимізації. Посібник. – К.: Рад. шк., 1991. – 175 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора