МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Метод гілок і границьНехай потрібно максимізувати функцію за умови, що належить деякій скінченній множині G. Перш за все шукаємо верхню границю функції на множині всіх планів G. Далі множину G певним чином розбиваємо на декілька неперетинаючих підмножин . Потім на одержаних підмножинах шукаємо верхні границі функції . Нехай – підмножина, для якої , де Якщо тепер на цій підмножині знайдеться таке , що , то задача розв’язана: план є оптимальним. Якщо такий план не знайдено, то процес розбиття продовжуємо, починаючи з множини , для якої – найбільше. Оскільки множина всіх планів скінченна, то оптимальний план після скінченного числа розбиттів буде знайдений. Приклад 1.12. Методом гілок і границь знайти найбільше значення функції при обмеженнях: ; ; , – цілі числа. Розв’язок. Будуємо область допустимих планів. Рис. 1.12 Якщо розглядати дану задачу без умови цілочисельності, то найбільше значення досягається в точці і дорівнює . . Оскільки, , то розіб’ємо G на дві частини: одна з них містить ті допустимі плани, в яких , а в другу увійдуть допустимі плани з . При цьому не буде втрачено жодного допустимого цілочислового розв’язку. Знайдемо для функції верхні межі в областях і : і . Для цього розв’яжемо дві ЗЛП: знайти найбільше значення функції при обмеженнях а) б)
де , – цілі числа. де , – цілі числа.
Рис.1.13 Розв’язуючи дані задачі без умови цілочисельності, встановлюємо, що найбільше значення функції f задачі а) досягається в точці і дорівнює , в задачі б) – в точці і дорівнює . Оскільки > , то розбиваємо на дві неперетинаючі підмножини і , а за додаткові обмеження візьмемо спочатку , а потім . Таким чином, приходимо до задачі: знайти найбільше значення функції при обмеженнях в) г)
, – цілі числа. , – цілі числа. Рис.1.14 З рисунка видно, що задачу в) можна не розглядати, оскільки вона не має жодного допустимого плану; що стосується задачі г) то в області точка задає її нецілочисловий оптимальний план з = = > . Розбивши на дві неперетинаючі підмножини і , і взявши за додаткові обмеження спочатку , а потім , прийдемо до наступної пари ЗЛП: знайти найбільше значення функції при обмеженнях д) е)
, – цілі числа. , – цілі числа. Оптимальні плани задач д) і е) без умови цілочисельності визначаються точками і і = = 4. Оскільки , то ми можемо стверджувати, що в точках E і F функція дійсно досягає найбільшого значення.. Рис.1.15 Зауваження 1.10. При розв’язуванні конкретних задач методом гілок і границь оптимум нерідко вдається відшукати доволі швидко. Проте цю процедуру часто доводиться виконувати багато разів, оскільки в ході обчислень виникає необхідність в неодноразовому поверненні назад в пошуках нових гілок “дерева” можливих варіантів. У прикладі, який ми розглядали, нам не доводилось цього робити тільки тому, що > , а потім = > .
Читайте також:
|
||||||||
|