Cтраница 1
Целочисленные алгоритмы, описанные в гл. В этом приложении мы обсудим другой подход, который может быть назван методом дерева поиска. Сюда относятся алгоритм ветвей и границ ( Лэнд и Дойг [139], Литтл и др. [144]), аддитивный алгоритм ( Балаш [4], Бил и Смол [14]), алгоритм прямого поиска ( Лемке и Шпильберг [143]) и многие другие. [1]
В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка, первоначально предназначенный для использования в графопостроителях. [2]
Если мы хотим применить эти методы для получения неравенств или отсекающих плоскостей в циклическом целочисленном алгоритме, то необходимо проделать следующие шаги. [3]
На таге 2 и 3 мы должны знать группу G, в то время как в циклическом целочисленном алгоритме [79] отсекающие плоскости получаются непосредственно после шага 1 без проверки групповой структуры. [4]
Таким образом, в отличие от задач линейного программирования, время решения которых относительно невелико, реализация целочисленных алгоритмов в ряде случаев весьма затруднительна. Далее изложим идею одного из современных методов целочисленного программирования. [5]
Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения ( гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) к. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. [6]
Так мы находим образ каждого небазисного вектор-столбца. Так как первая часть асимптотического целочисленного алгоритма предполагает решение задачи целочисленного программирования как задачи линейного программирования, то В-1 А [ I, B - 1N ] при окончании симплексных вычислений. [7]
Система позволяет анализировать стратегические решения, осуществлять текущую диспетчеризацию, а также в интерактивном режиме оценивать различные изменения и предлагать альтернативные сценарии размещения. Система ежечасно прогнозирует потребность в патрульных офицерах, автоматически осуществляя их диспетчеризацию с целью максимизировать контролируемую площадь и позволяет осуществлять настройку оптимального расписания. Пря-модвойственный целочисленный алгоритм генерировал решения, которые позволили высвобождать до 25 % экипажей в случае необходимости, это эквивалентно дополнительному штату из 200 офицеров или экономии в 11 млн. долларов в год. Время реакции в среднем уменьшилось на 29 %, принося дополнительно около 3 млн долл. [8]