Cтраница 4
Определение начального радиуса К и межцентрового расстояния АС при заданной длине коромысла ВС, максимальных углах давления и некоторых других ограничениях представляет собой задачу нелинейного программирования с двумя неизвестными. В разработанном алгоритме задача решается оригинальным численным методом, названным целенаправленным поиском. Этот метод позволяет решать рассмотренную задачу в несколько раз быстрее, чем любым из градиентных методов. Метод основан на логическом анализе знаков ограничивающих функций. В отличие от градиентных методов за первое приближение берется значение переменных, при которых не выполняются все или почти все ограничения и решение идет в направлении ухудшения критерия оптимальности. Этот же участок алгоритма выполняет и вторую функцию, а именно, изменение величины ВС или АС, если заданные углы давления могут быть получены без изменения К. В последнем алгоритме этот участок упрощен, так как исключены расчеты так называемого исходного или единичного механизма. [46]
В данной главе приводятся алгоритмы решения двух ( двумерных по аргументу) задач дискретного программирования ( назначения и коммивояжера) с помощью метода, изложенного в гл. Выбор этих задач не случаен. Как правило, вновь создаваемые общие схемы в дискретном программировании тестируются на рассматриваемых в главе задачах. Рассматривается задача назначения с подробным изложением математической постановки задачи, с построением реализации элементарной операции, конкретизацией последней для задачи, приводящей к точному алгоритму решением модельного примера. Предлагаемый алгоритм решения задачи назначения наиболее близок к алгоритмам венгерской группы, отличаясь от него нетривиальными особенностями. По такой же схеме рассматривается и используется задача коммивояжера с получением точного алгоритма решения этой задачи. Как показывает сравнение с существующими точными алгоритмами решения этой задачи, рассматриваемый алгоритм наиболее близок к алгоритму Балаша - Кристофидеса - наиболее эффективному на сегодняшний день алгоритму решения задачи коммивояжера с асимметричной матрицей расстояний. Так, в частности, с помощью последнего алгоритма к настоящему времени решены задачи размерностей до 325 городов. [47]