Устройство для графического решения задач Советский патент 1985 года по МПК G06G1/16 

Изобретение относится к устройствам для графического решения задач и может быть использовано, в частности, для решения комбинаторных задач маршрутного типа, относящихся к классу задач коммивояжера. Целью изобретения является расширение класса решаемых задач, а именно, помимо возможности решения геометрических задач обеспечить возможность графического решения ряда технических задач маршрутного типа, сводящихся к обобщенной задаче коммивояжера. На фиг. 1 изображено устройство, общий вид; на фиг. 2 - схема, поясняющая принцип работы устройства. Устройство (фиг. 1) содержит линейку 1, на которой расположен первый ползунок 2, выполненный из прозрачного материала. На ползунке 2 нанесена визирная риска 3. На пересечении одной из сторон линейки и визирной риски 3 расположена ось 4, на которой размещается поворотная планка 5, закрепленная с помощью фиксирующего элемента 6. Угол поворота задается с помощью градусной шкалы 7, нанесенной на секторный выступ ползуна 2. В планке 5 имеется сквозной паз 8 для снятия отсчета с градусной шкалы. На поворотной планке расположен второй ползунок 9, к которому прикрепляется сменный прозрачный планшет 10 (система концентрических эллипсов, одна из осей которых параллельна поворотной планке 5). В основу решения обоба1енной задачи коммивояжера положено эвристическое правило «иди в ближайшую точку. Обобщение задачи коммивояжера заключается в неравноценности затрат по осям эллипса при переходе из одной точки в другую. Если обозначить направление, задаваемое поворотной планкой, через х (направление, параллельное продольной оси эллипсов), а направление, перпендикулярное планке, через 2 и совместить центр эллипса с одной из заданных точек Nj, то координаты любой другой точки NJ в введенной системе координат будут Axjj , AZjj . Пусть затраты при движении коммивояжера в x(z) - направлении прямо пропорциональны пройденному расстоянию, т. е. , (), (1) где д Jx;л 3 -затраты при переходе из одной точки в другую, расположенные относительно .. друг друга в направлении; - (-g-)-с)ункции влияния, характеризующие приращение затрат при переходе из одной точки в другую, находящуюся на единичном расстоянии в направлении. Тогда, полные затраты при переходе из точки Nj в точку NJ равны AtJij УАУх1 + -/(IFfSi W - Уравнение (2) есть уравнение эллипса с .соотнош нием полуосей, равным а 33z/9z Т Эах/Эх где полуось а. ориентирована в х-направлении, а полуось и в z-напраелении. График эллипса представляет собой изолинию уровня затрат при переходе из центра на любую точку эллипса. В частном случае при одинаковых затратах в х и Z - направлениях ( -V эллипс вырождается в окружность (1). Планшет изготавливается из прозрачного материала, на который наносятся концентрические эллипсы с соотнощением полуосей пропорциональным функциям влияния в X и z-направлениях. Частота нанесения эллипсов и масщтаб, а следовательно, и размеры планщета выбираются исходя из конкретного класса решаемых задач. При решении однотипных задач с различными значениями отношений функций влияния необходимо иметь набор планшетов. Кроме того, для случая равных значений функций влияния в х и zнаправлениях необходим планшет с концентрическими окружностями. Нанесение на планшет эллипсов (окружностей) нецелесообразно производить с равными приращениями функций влияния по соответствующим осям. Такой способ подготовки планщетов позволит не только графически определять наивыгоднейший марщрут, но и производить оценку затрат для выбранного маршрута. Для оценки затрат на переход из одной точки в другую необходимо сосчитать число линий уровня, которыми накрывается дан-. ная точка и умножить это число на «цену, т. е. на затраты, необходимые на переход из центра на ближайший эллипс. Общие затраты, потребные для обеспечения всего маршрута, определяются путем суммирования затрат на каждом шаге. Устройство работает следующим образом. Линейка 1 накладывается на прямоугольную кромку графика точек, а поворотная планка 5 выставляется в заданном направлении с помощью транспортира и фиксируется фиксирующим элементом 6. Перемещением ползунков 2 и 9 добиваются совмещения центра концентрических эллипсов с точкой, выбираемой за начальную

Выбор ближайшей точки осуществляется с помощью концентрических эллипсов (фиг. 2). Ближайшей к центру будет точка 5, а не точка о, поскольку точка 5 накрывается меньшим числом концентрических эллипсов (т. е. через точку «б проходит изолиния меньших затрат, чем через точку а).

После определения очередной точки перемещением ползунков 2 и 9 добиваются совмещения с ней центра концентрических эллипсов и определяют следующую точку описанным способом.

Если начальная точка маршрута не задана, то она может быть определена путем решения п раз (п-крличество заданных точек марщрута) аналогичных задач описанным способом, принимая последовательно в качестве начальной точки каждую из п точек. Суммируя при этом общие затраты на каждом из п маршрутов и сравнивая их между собой, можно выявить маршрут с наименьшими затратами и принять его в качестве решения. При условии определения маршрута, затраты на который не превосходят заданной величины, процедура определения маршрута прекращается при выполнении этого условия, и он принимается в качестве решения

Таким образом, технико-экономический эффект от практического использования предлагаемого устройства заключается в расширении диапазона решаемых задач.

С помощью этого устройства имеются возможности:

делить отрезок на любое число равных частей;

делить ряд лучей, выходящих из одной точки, отрезками, перпендикулярными этим лучам, пропорционально ряду чисел;

определять расстояние до делимого луча;

определять угол наклона прямых;

оперативно находить решение задач маршрутного типа, сводящихся к задачам коммивояжера , по эвристическому правилу «иди в ближайщую точку ;

определять потребные для всего марщрута затраты;

определять маршрут и затраты при незаданной начальной точке.

УСТРОЙСТВО ДЛЯ ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧ, содержащее сриг. i линейку, на которую нанесена шкала, на линейке расположен первый ползунок, на оси которого закреплена поворотная планка, отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит второй ползунок, размещенный на поворотной планке, к которому прикреплен сменный прозрачный планшет, на который нанесена система концентрических эллипсов, первый ползунок снабжен секторным выступом с градусной шкалой, а поворотная планка снабжена фиксирующим элементом.