Cтраница 3
Задача (15.25) - (15.27) и (15.29) - рассмотренная выше задача назначения. Ее допустимыми решениями могут быть не только циклы, но и подциклы, не являющиеся допустимыми решениями задачи коммивояжера. Ограничения (15.28) введены для устранения всех возникающих в процессе решения задачи коммивояжера подциклов. [31]
Рассмотрим, например, функцию (12.59), являющуюся критерием задачи назначения по вероятности обслуживания всех заявок. [32]
Рассмотрим соотношение между значениями целевых функций для оптимальных решений задач назначения и коммивояжера для одной и той же матрицы С. [33]
Z)) 0, т.е. разрушается это решение задачи назначения. [34]
Основная сложность этого вопроса - доказательство то / с-дественности задачи назначения весомости и тестовой. [35]
Еще один специализированный метод описан в [81], где решается задача назначения на архитектуру ВС типа гиперкуб. [36]
На всех иерархических уровнях нисходящего проектирования, кроме самого верхнего, задача назначения ТТ может быть формализована и представлена как задача оптимального преобразования ТТ к выходным параметрам объекта на & - м уровне в ТТ к выходным параметрам частей объекта на ( & 1) - м уровне. [37]
В шаге 3 при переходах к шагу 2, вызванных получением нового решения задачи назначения, помимо ветвей, образованных в результате разрыва одного из подциклов этого решения, следует учитывать непросмотренные ( висячие) ветви, образованные в результате разрыва предыдущего решения задачи назначения. [38]
Для анализа эффективности венгерского метода статистически проанализировали алгоритм Мака на выборках из 100 задач назначения различных размерностей. В табл. 3.1 для анализируемых выборок приведено среднее, минимальное и максимальное время счета. [39]
Среди важнейших классов задач И.о. можно назвать задачи управления запасами, распределения ресурсов и задачи назначения ( распределительные задачи), задачи массового обслуживания, задачи замены оборудования, упорядочения и согласования ( в том числе теории расписаний), состязательные ( напр. Среди применяемых методов - математическое программирование ( линейное, нелинейное и т.п.), дифференциальные и разностные уравнения, методы теории графов, марковские процессы, теория игр, теория ( статистических) решений, теория распознавания образов и ряд других. [40]
Такое усиление будет проведено ниже для частных классов задачи (13.26) - (13.28) - для задачи назначения, а также для задачи коммивояжера, тесно связанной с задачей назначения. [41]
Таким образом, получился ряд условий допустимости планов выбора Y, для проверки которых необходимо решать задачи назначения, обладающие различной степенью алгоритмической сложности. [42]
В ряде случаев задачи уравновешивания в силу жестких огра и - чений могут быть сведены к задачам назначения на фиксирований16 места. Рассмотрим следующую задачу, возникающую при уравно е - шивании масс вращающихся частей в турбостроении, авиамоторостр е - нии и других отраслях промышленности. [43]
На рис. 16.5, а - б приведены соответственно примеры 6-вер-шинных графов оптимальных решений задачи коммивояжера, задачи назначения и кратчайшего остова. Если окажется, что для задачи назначения выполняется свойство 1, то полученное решение для этой задачи является и решением задачи коммивояжера с той же матрицей расстояний. [44]
Предложенный алгоритм имеет некоторые общие фрагменты с известными алгоритмами решения задачи коммивояжера: решение начинается с решения задачи назначения для той же матрицы расстояний и формирования условий (14.35), где в качестве подмножеств А и А выбираются подциклы решения задачи назначения. Однако затем в предложенном алгоритме не преследуется цель обязательного выполнения этих условий для фиксированной пары множеств А к А, как это имеет место в известных алгоритмах либо за счет решения задачи линейного программирования (14.31) - (14.33) и (14.35), либо за счет соответствующего списка новых задач назначений. При этом выполнение условий (14.35) не обязательно. [45]