Устройство для решения геометрических и комбинаторных задач Советский патент 1987 года по МПК G06G1/16 

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

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

На фиг. 1 изображено коническое сечение, представляющее собой правильный эллипс, получаемый проекцией светового потока на карту местности (при фи.ксирован- ном значении угла полураствора конуса светового потока р и фиксированном соотношении полуосей эллипса, равного отношению функций влияния, форма эллипса задается углом наклона а оси конуса светового потока и плоскости карты местности); на фиг. 2 - схема взаимного расположения конуса светового потока к плоскости рабочей карты; на фиг. 3 - предлагаемое устройство, общий вид; на фиг. 4 - устройство в ра: ючем положении; на фиг. 5 - порядок выбора очередной точки маршрута по эвристическому правилу «Иди в ближайшую точку.

Устройство содержит следующие элементы (фиг. 3). Основание 1 соединено с помощью пантографа 2 со столом, на котором размещается карта местности с нане- сен-ными на нее точками обхода. Пантограф 2 обеспечивает при перемещении основания 1 по карте местности постоянство выбранного направления. Для установки заданного условиями задачи направления ориентации эллипсов в состав устройства входят транспортер 3, жестко скрепленный с вертикальной поворотной штангой 4, риска 5, нанесенная на основание 1 и фиксирующий элемент 6, фиксирующий положение вертикальной поворотной штанги 4 в нужном направлении. Для задания требуемой формы эллипса устройство содержит осветитель 7, снабженный объективом 8 и непрозрачной блендой 9 для задания угла s полураствора светового потока (фиг. 2). Осветитель фиксируется фиксируюшими элемента0

ми 10 под требуемым углом а (фиг. 4), откладываемым с помощью прозрачного транспортера 11, жестко скрепленного с корпусом осветителя 7. Для отсчета угла а на подвижную штангу 12 нанесена риска 13. Зафиксированный осветитель 7 может перемещаться вместе со штангой 12 вдоль направляющей втулки 14. В случае необходимости щтанга 12 может быть зафиксирована фиксирующим элементом 15. Транспортир служит для задания направления движения штанги 12, перемещая по которому можно изменять размеры эллипса без изменения его формы, а также без изменения положения его центра на карте местности. Тран5 спортир 16 жестко скреплен с горизонтальной щтангой 17. Фиксирующий элемент 18 фиксирует положение направляющей втулки 14 в заданном направлении. Это направление задается углом а (фиг. 4). Для установки угла Y на штангу нанесена риска 19.

0 Для компенсации ухода центра эллипса из заданной точки при указанных изменениях положение осветителя 7 и штанги 12, приводящих устройство в рабочее положение, служат две взаимно перпендикулярные нас правляющие втулки 20 и 21, положение штанг определяется по шкалам 22 и 23, нанесенным соответственно на вертикальную 4 и горизонтальную 17 штанги, фиксирующие элементы 24 и 25 предназначены для фиксации этих штанг. Для приведения центра

0 эллипса в исследуемую точку на объективе 8 осветителя 7 нанесено перекрытие, проекция которого на карте местности обозначена позицией 26. Для получения информации о размерах эллипса служит шкала 27, нанесенная на штангу 12.

5 Все отсчеты на прямолинейных шкалах 22, 23 и 27 снимаются от нулевых отметок до пересечения с кромками соответствующих втулок 20, 21 и 14. Все отсчеты на транспортных щкалах 11 и 16 снимаются от нулевых отметок, за которые принимают

направление отвесной линии в исходном положении, до рисок 13 и 19, нанесенных на щтанге 12.

Для приведения устройства в рабочее положение необходимо на транспортирной

с шкале 16 установить значение угла v- на транспортирной шкале 11 - значение угла а, горизонтальную штангу 17 совместить вправо вдоль направляющей втулки 21 на величину А1, а направляющую втулку 20 вниз на величину дК. Отсчеты в этом случае сни0 маются соответственно по шкалам 16, 11, 23 и 22. Формулы для определения величин Y а. Al и ДКиспользуются для градуировки соответствующих шкал Gi, G2, Оз в зависимости от заданного коэффициента К (величина отношения функций влияния

задаваемая условиями задачи).

После градуировки шкал предлагаемого устройства установка соответствующих коэффициенту К значений угловых и а линей- ныХ Д| и h величин сводится фактически к установке на всех этих шкалах непосредственно значения задаваемого условиями задачи коэффициента К.

Работу устройства продемонстрируем на примере решения геометрической задачи коммивояжера. В этом случае устройство работает следуюшим образом.

Исходное положение устройства показано на фиг. 3. На всех шкалах выставляются нулевые отметки. При этом проекция светового потока представляет собой круг. Вертикальная штанга 4 поворачивается вокруг своей оси в заданном направлении, устанавливаемом с помощью транспортира 3 по риске 5 и фиксируется фиксирующим элементом 6. Затем,перемещая основание 1 с помощью пантографа 2 добиваются того, чтобы центр круга, определяемый проекцией 26 перекрестья на карту, совместился с первой исследуемой точкой Далее заданную величину отношения функций влияния (коэффициент К) устанавливают на соответствующих шкалах с целью приведения устройства в рабочее положение. Указанное приведение устройства в рабочее положение схематично изображено на фиг. 4 (всего требуется установить значение коэффициента К на четырех шкалах GI, G2, Сз и G4.).

Выбор ближайщей точки маршрута осуществляется с помощью увеличения (уменьшения) размеров эллипса заданной формы и ориентированного в заданном направлении (фиг. 6). Такое увеличение (yMeHbuje- ние) размеров э.члипса достигается перемещением штанги 12 с зафиксированным на ней осветителем 7 вдоль направляющей втулки 14. При этом, чем меньше размер эллипса, который накрывает точку, тем меньше затрат требуется для перехода из центра эллипса в эту точку и, следовательно, такая точка будет ближайшей. Ближайшей к центру будет точка б, а не точка а, так как точка б достигается при движении от центра быстрее, чем точка а (т.е. через точку б проходит изолиния меньших затрат, чем через точку а).

После определения очередной точки устройство возвращается в исходное положение; перемен1,ением основания 1 с помощью пантографа 2 добиваются совмещения с ней центра окружности, изложенным способом определяют следующую точку, т. д. до получения последней точки.

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

маршрут с наименьщими затратами и принять его в качестве решения. При условии определения маршрута, затраты на который не превосходят заданной величины,

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

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

суммирования затрат на каждом шаге.

Формулы, необходимые для градуирования щкал G|. 02, Оз, G4 (фиг. 4) в зависимости от задаваемого условиями задачи коэффициента К (отношение функций влияния):

20

К

dlz/dz

L arcsin(cos pV Gt(K)y arctg 0,(+jL )-tg(-J:)

G2(K) oc аЦ,;

|tg(P+a )-tg(p-a )l; G3(K) BC+ lisinv;

0

G,K Ah l,(l-cosY), где д 1дка:д 7.1д2 - задаваемые условиями задачи функции влияния;

Р - угол полураствора конуса светового потока (задается формой бленды 9); 5 hi - фиксированная величина, равная расстоянию от фокуса объектива 8 осветителя 7 в исходное положении до рабочей поверхности стола (т.е. до нижней поверхности основания 1),

этому расстоянию соответствует нулевая отметка шкалы 22;

h - фиксированная величина, равная длине штанги 12 от нулевой отметки 1пкалы 27 до фокуса объектива 8 (фиг. 4).

5Формула изобретения

Устройство для решения геометрических и комбинаторных задач, содержащее первую штангу с нанесенной на нее шкалой, первый транспортер, жестко соединеи0 ный с первой 1нтангой, первый фиксирующий элемент, отличающееся тем, что. с целью повышения точности, в него введены прибор для формирования эллипсов, содержащий осветитель, снабженный объективом с блендой, корпус объектива жестко соединен

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

Изобретение относится к устройствам для решения геометрических и комбинаторных задач маршрутного типа. Данное устройство позволяет решать задачи типа задачи коммивояжера. Цель изобретения - повышение точности. Устройство состоит из основания 1, соединенного со столом с помощью пантографа 2, на которое устанавливается вертикальная поворотная штанга 4 с втулкой 20, жестко скрепленной с втулкой 21, являющейся направляющей для штанги 17. Со штангой 17 шарнирно соединена втулка 15, являющаяся направляющей для штанги 12. Со штангой 12 шарнирно соединен осветитель 7, снабженный объективом 8 и непрозрачной блендой 9, который служит для получения изображения эллипса (конического сечения светового потока) на карте местности, закрепленной на рабочем столе. Для задания направления, перемещая по которому штангу 12 вместе с осветителем 7 добиваются увеличения (уменьшения) размеров эллипса без изменения положения его центра на карте, в состав устройства входят нижний 11 и верхний 16 транспортиры и шкалы 22 и 23, а для задания направления большой оси эллипса на карте местности - транспортир 3. Устройство позволяет формировать на карте изображение эллипса любой заданной условиями задачи формы и размера и ориентированного своей большой осью в требуемом направлении. 5 ил. о .19 гСО со Ci О СО ОО

Фиг. 2

пл.П