Метод - ветвь
Cтраница 2
Метод ветвей и гра ниц используется для решения комбинаторных задач Дискретного программирования. Кратко поясним основную сущность метода ветвей и границ. [16]
Метод ветвей и границ относится к группе методов, которые учитывают комбинаторный характер задачи, дискретность отдельных переменных. Основан метод на упорядоченном переборе вариантов, рассмотрении лишь тех вариантов, которые оказываются по определенным признакам перспективными, и отбрасывании сразу целых множеств вариантов, являющихся бесперспективными. [17]
Метод ветвей и границ - точный метод решения комбинаторных задач и часто он предъявляет значительные требования к оперативной памяти ЭВМ. Существуют также приближенные методы, в которых, исходя из определенных эвристических предпосылок, по относительно простым правилам строятся допустимые решения, которые должны быть удовлетворительными с практической точки зрения, хотя они могут и не быть оптимальными. Оценку приближения при этом найти обычно не удается, достоинства методов определяются эвристическими соображениями, простотой реализации. [18]
Метод ветвей и границ используется для решения комбинаторных задач дискретного программирования. Кратко поясним основную сущность метода ветвей и границ. [19]
Метод ветвей и границ позволяет, определяя направление поиска оптимального варианта, осуществлять формирование и оценку только тех схемных решений, которые необходимы для отыскания оптимального, а не перебирать и точно оценивать все возможные решения. Необходимым условием использования этого метода является возможность определения на каждом этапе нижней оценки критерия оптимальности. [20]
Метод ветвей и границ наряду с методами отсечения обладает существенными достоинствами с вычислительной точки зрения. Алгоритмы, построенные на этих методах, сравнительно легко программируются на ЭВМ и реализуются на любой итерации без вмешательства человека, однако их эффективность резко снижается при увеличении размерности решаемой задачи. [21]
Метод ветвей и границ в отличие от метода прямого перебора позволяет с помощью верхних и нижних значений на каждом наборе значений функции отсекать от дальнейшего поиска некоторые варианты без их конкретного рассмотрения. [22]
Метод ветвей и границ можно аналогично применить и для нахождения определенного значения а, например, разности двух монотонных функций, для чего надо найти значение разности, большее а, и значание разности, меньшее а. Аналогично могут быть рассмотрены и сумма, и произведение, и произведение степеней двух монотонных функций. [23]
Метод ветвей и граних применим и для уровневых задач. Рассмотрим уровневую задачу: спонсор перечислил в пенсионный фонд ( массив пенсий р) сумму s с условием: поднять минимальный уровень пенсии на этот месяц. [24]
 |
Сеть комплекса работ. [25] |
Метод ветвей и границ можно применить и при прямом переборе всех 24 - х вариантов, когда каждый последующий вариант считается до тех пор, пока он меньше уже достигнутого минимума. Так как каждый вариант состоит из последовательного сложения чисел, такое отсечение возможно. Сложение проводится до тех пор, пока сумма меньше достигнутого минимума, в противном случае происходит переход к следующему варианту. [26]
Применяя метод ветвей и границ к приведенной выше в качестве примера матрице стоимостей, мы замечаем некоторую сложность. [27]
Впервые метод ветвей и границ был предложен в 1960 г. в работе Лэнд и Дойг [109] применительно к задаче целочисленного линейного программирования. [28]
Обычно метод ветвей и границ применяется для решения сложных задач. [29]
Применим метод ветвей и границ. [30]
Страницы: 1 2 3 4