На головну

Загальна схема

  1. C) загальна і особлива частини
  2. I. Загальна характеристика
  3. а) схема змішаної неврівноваженості; б) розрахункова схема
  4. Абстрактне мистецтво. Загальна характеристика і його представники.
  5. Автогрейдери. Основні параметри, робочі органи, продуктивність, область застосування.
  6. Акцизи: загальна характеристика, історична ретроспектива
  7. Альдегіди, загальна формула. Хімічні властивості. Отримання, застосування мурашиного і оцтового альдегідів.

У методі на кожній ітерації будується список  з перспективних підмножин, одне з яких, принаймні містить оптимальний план. На нульовій ітерації  . Обчислюємо оцінку ітерації  , Рекорд ітерації .

обчислюємо різницю  . Можливі випадки:

1.  . В цьому випадку рекордний план буде оптимальним планом задачі, так як на ньому досягалася нижня межа.

2.  , де  - Мале позитивне число, задана точність обчислення. В цьому випадку рекордний план можна взяти в якості  - Оптимального, тобто наближеного рішення задачі (1).

3.  . Тоді задана точність не досягнута. Переходимо до першої ітерації. Для цього у відповідність з першим припущенням  Гілки на більш дрібні. Для кожного обчислюємо кордон по другим припущенням, і безперспективні підмножини відкидаємо, а перспективні включаємо в список для першої ітерації.

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

нехай  - Список перспективних підмножин  -ої ітерації. Обчислюємо оцінку ітерації  . Обчислюємо рекорд ітерації .

обчислюємо різницю .

Здійснюємо аналіз:

1. якщо  , То побудований оптимальний план. Записуємо відповідь.

2. якщо  , То побудований  оптимальний план. Записуємо відповідь.

3. якщо  , То переходимо до  ой ітерації. Для цього вибираємо з  найперспективніший підмножина (з найменшою нижньою межею) і дробу його за першим припущенням. В  включаємо перспективні підмножини з знову отриманих дробленням і інших підмножин безлічі .

І так далі.

Ясно, що на ітераціях  зменшуються, а  збільшуються (чим дрібніше підмножина, тим точніше можна для неї побудувати кордон). Отже, числа  зменшуватимуться і, врешті-решт, метод гілок і меж дозволить, вирішити задачу (1).

Зауваження 2. Слово «ефективна» у другому припущенні означає, що нижня межа  не сильно відрізняється від точної нижньої. Чим точніше будується оцінка, тим швидше сходиться метод гілок і меж.



Метод гілок і меж. Загальна схема Завдання про рюкзаку | Завдання про рюкзаку

МЕТОДИ ПОШУКУ | Завдання обслуговування заявок на одному приладі | Метод гілок і меж. Загальна схема Завдання цілочисельного лінійного програмування | Завдання цілочисельного лінійного програмування | Метод сплайнів 1-го порядку (знаходження точки глобального мінімуму) | Методи мінімізації унімодальних функцій. Метод рівномірного пошуку | Метод рівномірного пошуку | Методи двухточечного пошуку | метод Фібоначчі | Метод золотого перерізу |

© um.co.ua - учбові матеріали та реферати