Булево линейное программирование 35, [c.460]
Широко известным приближенным методом решения задач отображения является метод балансировки загрузки (см., например, [66, 67]). При этом программы назначают процессорам таким образом, чтобы вычислительная загрузка последних была максимально одинаковой. Предлагается формализация задачи оптимального отображения структуры ИСУ на архитектуру МВС в виде задачи глобальной балансировки загрузки [68]. Подход, основанный на математическом программировании, позволяет свести задачу балансировки к задаче булева линейного программирования. [c.131]
Основной целью работы является исследование эффективности метода решения задачи оптимального отображения структуры ИСУ на архитектуру МВС, в котором указанная задача булева линейного программирования решается приближенно методом релаксации [69]. Идея заключается [c.131]
Справедливость теоремы следует из того факта, что задача булева линейного программирования (1.152) является NP-сложной [70]. [c.134]
Булево линейное программирование — класс задач дискретного программирования, в которых все или несколько искомых переменных являются булевыми величинами, а критерий и ограничения — линейные. [c.211]
Среди разработанных в монографии экономико-математических моделей, являющихся задачами дискретного программирования, часть представляет собой одноэтапные экономико-математические модели-задачи целочисленного линейного программирования, часть — многоэтапные, целочисленного нелинейного программирования. iB качестве переменных взяты булевы переменные. [c.187]
Точных методов решения целочисленных нелинейных задач в настоящее время нет. Однако нелинейные целочисленные задачи можно свести, к линейным целочисленным [122]. Сведем, например, задачу (4.24) — (4.31) к задаче целочисленного линейного программирования. Для этого любое произведение булевых переменных, входящее в условия задачи, необходимо заменить одной новой булевой переменной, а к системе ограничений экономико-математической модели добавить два линейных неравенства соответственно для каждой вновь вводимой булевой переменной. >В нашем случае [c.193]
Условие (3) означает, что каждый претендент назначается на одну работу, а условие (4) — что на каждую работу назначается один претендент. Условия (1) выводят задачу из класса задач линейного программирования, так как они нелинейные, т. е. формально задачу о назначениях можно отнести к классу задач линейного программирования с булевыми переменными. Однако практически задачу о назначениях можно рассматривать как частный случай транспортной (и, следовательно, просто линейной) задачи, в которой т = п, а все д,< = bj = 1, если условия (1) заменить условиями неотрицательности переменных [c.202]
Для записи постановки задачи в терминах целочисленного линейного программирования определим булевы переменные следующим образом // = 1, если коммивояжер переезжает из i -го [c.521]
Рассмотрим два стохастических аналога задачи линейного программирования со статистическими и вероятностными ограничениями и булевыми переменными. [c.149]
Формирование оптимальной инвестиционной программы с учетом риска и бюджетного ограничения сводится к задаче линейного целочисленного программирования с булевыми переменными. [c.182]
БУЛЕВЫ ВЕЛИЧИНЫ [Boolean variables] — переменные величины, которые могут принимать лишь одно из двух значений (0 или I). См. также Булево линейное программирование, Данные, Параметр целочисленных значений. [c.35]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Примем параметр е = 0. Тогда вся задача ( перераспределения сводится к задаче смешанного булевого линейного программирования. [c.174]
В настоящее время разработаны две группы таких методов [60]. Первую группу составляют методы отсечения (метод целочисленных форм и др.). (Вторую — комбинаторные методы (метод ветвей и границ, аддитивный алгоритм и др.). Наибольшее распространение при решении задач с булевыми переменными получил аддитивный алгоритм Балаша. Для реализации этого метода на ЭВМ разработаны программы. Одна из таких программ, получившая широкое распространение, разработана 3. В. Коробковой [62]. Для того, чтобы воспользоваться этой программой, необходимо задачу целочисленного линейного программирования привести к виду [c.188]