Известны различные методы решения целочисленных задач линейного программирования методы отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий целочисленной задачи линейного программирования. [c.219]
Для решения задачи (I) автор предлагает использовать метод ветвей и границ, а для нахождения решения семейства задач (II) -использовать методы линейного программирования (например. симплекс -метод). [c.120]
В данной статье предложена адекватная математическая модель распределения временно свободных денежных средств предприятия, найдена декомпозиция исходной задачи, сводящая ее решение к решению двух подзадач. Первую предложено решать на основе метода ветвей и границ (это позволит рассмотреть все допустимые множества исходов, удовлетворяющие ожиданиям инвестора), а вторую подзадачу (получение оптимального портфеля инвестиций в активы на заданном множестве исходов) - методом линейного программирования. [c.120]
Надо отметить, что принятие решения на основе отбрасывания неразумных вариантов действий является естественным для человека. При этом чем шире множество вариантов, претендующих на то, чтобы быть выбранными в качестве решения, тем грубев могут быть оценки, применяемые для отсеивания нерациональных вариантов. При сужении множества рассматриваемых вариантов оценки должны становиться все более точными. Идеи последовательного анализа и отбрасывания вариантов нашли широкое применение при решении задач оптимизации в виде различных реализаций общего подхода, получившего название метода ветвей и границ . В этом подходе, описываемом во многих учебниках по оптимизации, даются грубые оценки целым группам вариантов, после чего большое число вариантов с плохими оценками отбрасывается. [c.332]
Методы исследования операций Системный анализ, имитационное моделирование, управление запасами, теория расписаний, сетевое планирование и управление, методы теории массового обслуживания, математическое (линейное, нелинейное, динамическое, дискретное, стохастическое) программирование, метод ветвей и границ и др. [c.430]
При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи — конечно. Например, в задаче с переменными х, Xz 0 < xi < 4 0 < х, < 5 число возможных решений — 20. Следовательно, возможен полный перебор возможных сочетаний целочисленных х, х2 и выбор наилучшего в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ. [c.127]
МЕТОД ВЕТВЕЙ И ГРАНИЦ [c.127]
Из примера видно, что метод ветвей и границ достаточно трудоемкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений. [c.128]
Специфика рассматриваемой задачи позволяет успешно применить для ее решения метод ветвей и границ. Подробное изложение метода решения и данные о практическом использовании рекомендуемой методики см. в [71]. [c.333]
Вычислительная схема метода ветвей и границ в этом случае также упростится, а сам метод будет более эффективным. [c.334]
Для разработки наилучших стандартпланов работы поточных линий и предметных участков используются различные современные математические методы линейное и выпуклое программирование, метод ветвей и границ и "различные приближенные методы. [c.4]
Рассмотрим метод ветвей и границ для решения задачи управления [c.45]
Согласно методу ветвей и границ, из двух подмножеств выбирается [c.28]
Разработка метода ветвей и границ на основе нижних или верхних оце- [c.3]
Метод ветвей и границ [c.48]
Метод ветвей и границ это метод ветвлений, в котором в качестве [c.48]
Эффективность метода ветвей и границ в существенной степени зави- [c.48]
Рассмотрим на примере применение метода ветвей и границ для ре- [c.63]
Применим метод ветвей и границ. Разобьем множество всех решений [c.64]
Используя (1.7), опишем метод ветвей и границ. Разобьем множество [c.77]
Для общего случая рассмотрен метод ветвей и границ, в котором [c.97]
Второй вариант состоит в применении метода ветвей и границ. [c.64]
Далее можно применить метод ветвей и границ на основе получен- [c.74]
Для решения задач дискретного программирования широко применяются комбинаторные методы, основная идея которых заключается в замене полного перебора всех решений их частичным перебором. Одним из таких методов является метод ветвей и границ, основе которого лежат следующие построения, позволяющие существенно уменьшить объем перебора решений [c.212]
Для реализации метода ветвей и границ применительно к задаче о коммивояжере необходимо конкретизировать правила ветвления, вычисления оценок и нахождения решений. [c.212]
Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем. [c.212]
Чтобы проиллюстрировать алгоритм метода ветвей и границ для решения задачи о коммивояжере приведем численный пример. [c.215]
В настоящее время разработаны две группы таких методов [60]. Первую группу составляют методы отсечения (метод целочисленных форм и др.). (Вторую — комбинаторные методы (метод ветвей и границ, аддитивный алгоритм и др.). Наибольшее распространение при решении задач с булевыми переменными получил аддитивный алгоритм Балаша. Для реализации этого метода на ЭВМ разработаны программы. Одна из таких программ, получившая широкое распространение, разработана 3. В. Коробковой [62]. Для того, чтобы воспользоваться этой программой, необходимо задачу целочисленного линейного программирования привести к виду [c.188]
МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ [bran h and bound te hnique] — один из общих подходов к решению дискретных задач оптимального программирования, для которых еще не выработаны специфические способы алгоритмы) решения. Они характеризуются частичным целенаправленным перебором возможных вариантов. При этом решаемая задача последовательно ветвится, заменяясь более простыми, и путем анализа с помощью графа "дерево задач " отбрасываются заведомо непригодные варианты, чем облегчается дальнейший перебор. [c.196]