На головну

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

  1. C) загальна і особлива частини
  2. Стандартний алгоритм симплекс-методу
  3. DFD - методологія в проектуванні ІС
  4. I. Загальна характеристика
  5. I.3.3. Методи виносу в натуру проектних точок.
  6. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  7. III. Опис експериментальної установки та методу вимірювання

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

Метод застосовують до завдань:

, (1)

для яких виконуються два припущення:

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

2. для безлічі  і для будь-якого його підмножини  може бути обчислена ефективна нижня межа значень цільової функцій на ньому, тобто для  можна побудувати число (5)



Завдання обслуговування заявок на одному приладі | Загальна схема

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

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