Устройство для решения геометрических и комбинаторных задач

(21) 40 (22) 30 (46) 07 (72) А. (53) 68 (56) П 1982,Авто117133 3 - 1, 4483073, кл тельство СССР 6 О 1/16, 1981. ское сви О, кл. 6(54) УС МЕТРИ ся к устройствам их и комбинаторипа. Данное устзадачи типа заизобретения ойство состоит изсо столом с по- которое устанаворотная штанга 4 ленной с втулкой ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ ОЙСТВО ДЛЯ РЕШЕНИЯ ГЕОСКИХ И КОМБИНАТОРНЫХ ЗАДАЧ(57) Изобретение относит для решения геометрическ ных задач маршрутного т ройство позволяет решать дачи коммивояжера. Цель повышение точности. Устр основания 1, соединенного мощью пантографа 2, на ливается вертикальная пов с втулкой 20, жестко скреп 21, являющейся направляющей для штанги 17. Со штангой 17 шарнирно соединена втулка 15, являющаяся направляющей для штанги 2. Со штангой 12 шарнирно соединен осветитель 7, снабженный объективом 8 и непрозрачной блендой 9, который служит для получения изображения эллипса (конического сечения светового потока) на карте местности, закрепленной на рабочем столе. Для задания направления, перемещая по которому штангу 12 вместе с осветителем 7 добиваются увеличения (уменьшения) размеров эллипса без изменения положения его центра на карте, в состав устройства входят нижний 11 и верхний 16 транспортиры и шкалы 22 и 23, а для задания направления большой оси эллипса на карте местности - транспортир Я 3. Устройство позволяет формировать на карте изображение эллипса любой заданной условиями задачи формы и размера и ориентированного своей большой осью в требуемом направлении. 5 ил.5 10 15 20 25 30 35 40 45 50 55 Изобретение относится к устройствам для решения геометрических и комбинаторных задач маршрутного типа и может быть использовано в организациях, связанных с необходимостью оперативного решения задач определения такой последовательности посещения городов или иных объектов транспортным средством, которая минимизирует суммарные потребные энергозатраты на обход при возможных заданных ограничениях,Цель изобретения - повышение точности решения задачи.Применение устройства при решении задач позволяет непрерывно изменять размеры и форму эллипсов, что существенно повышает оперативность и точность получаемого решения, так как в процессе решения не требуется проводить дополнительную аппроксимацию изолинии уровня при попадании очередной исследуемой точки в интервал между двумя соседними концентрическими эллипсами. Кроме того, исключается особенно трудоемкая операция аппроксимации целого семейства концентрических эллипсов определенной формы, задаваемой соотношением функций влияния.На фиг. 1 изображено коническое сечение, представляющее собой правильный эллипс, получаемый проекцией светового потока на карту местности (при фиксированном значении угла полураствора конуса светового потока р и фиксированном соотношении полуосей эллипса, равного отношению функций влияния, форма эллипса задается углом наклона а оси конуса светового потока и плоскости карты местности); на фиг. 2 - схема взаимного расположения конуса светового потока к плоскости рабочей карты; на фиг. 3 - предлагаемое устройство, общий вид; на фиг. 4 - устройство в ра. очем положении; на фиг. 5 - порядок выбора очередной точки маршрута по эвристическому правилу Иди в ближайшую точку,Устройство содержит следующие элементы (фиг. 3). Основание 1 соединено с помощью пантографа 2 со столом, на котором размещается карта местности с нанесенными на нее точками обхода. Пантограф 2 обеспечивает при перемещении основания 1 по карте местности постоянство выбранного направления, Для установки заданного условиями задачи направления ориентации эллипсов в состав устройства входят транспортер 3, жестко скрепленный с вертикальной поворотной штангой 4, риска 5, нанесенная на основание 1 и фиксирующий элемент 6, фиксирующий положение вертикальной поворотной штанги 4 в нужном направлении. Для задания требуемой формы эллипса устройство содержит осветитель 7, снабженный объективом 8 и непрозрачной блендой 9 для задания угла в полу- раствора светового потока (фиг. 2). Осветитель фиксируется фиксирующими элементами 1 О под требуемым углом а (фиг. 4), откладываемым с помощью прозрачного транспортера 11, жестко скрепленного с корпусом осветителя . Для отсчета угла а на подвижную штангу 12 нанесена риска 13. Зафиксированный осветитель 7 может перемещаться вместе со штангой 12 вдоль направляющей втулки 14, В случае необходимости штанга 12 может быть зафиксирована фиксирующим элементом 15. Транспортир слу. жит для задания направления движения штанги 2, перемещая по которому можно изменять размеры эллипса без изменения его формы, а также без изменения положения его центра на карте местности. Транспортир 16 жестко скреплен с горизонтальной штангой 7. Фиксирующий элемент 18 фиксирует положение направляющей втулки 14 в заданном направлении. Это направление задается углом а (фиг. 4). Для установки угла у на штангу нанесена риска 9. Для компенсации ухода центра эллипса из заданной точки при указанных изменениях положение осветителя 7 и штанги 12, приводящих устройство в рабочее положение, служат две взаимно перпендикулярные на. правляющие втулки 20 и 21, положение штанг определяется по шкалам 22 и 23, нанесенным соответственно на вертикальную 4 и горизонтальную 17 штанги, фиксирующие элементы 24 и 25 предназначены для фиксации этих штанг. Для приведения центра эллипса в исследуемую точку на объективе 8 осветителя 7 нанесено перекрытие, проекция которого на карте местности обозначена позицией 26. Для получения информации о размерах эллипса служит шкала 27, нанесенная на штангу 12.Все отсчеты на прямолинейных шкалах 22, 23 и 27 снимаются от нулевых отметок до пересечения с кромками соответствующих втулок 20, 21 и 14, Все отсчеты на транспортных шкалах 11 и 16 снимаются от нулевых отметок, за которые принимают направление отвесной линии в исходном положении, до рисок 13 и 19, нанесенных на штанге 12.Для приведения устройства в рабочее положение необходимо на транспортирной шкале 16 установить значение угла у, на транспортирной шкале 11 - значение угла а, горизонтальную штангу 17 совместитьвправо вдоль направляющей втулки 21 на величину ,1, а направляющую втулку 20 вниз на величину Л. Отсчеты в этом случае снимаются соответственно по шкалам 16, 11, 23 и 22. Формулы для определения величин у, сс, 1 и ЛЬиспользуются для градуировки соответствующих шкал б, бь бз в зависимости от заданного коэффициента К (величина отношения функций влияния ---- , задаваемая условиями задачи). а 1. (ахд/дхПосле градуировки шкал предлагаемого устройства установка соответствующих ко 336038эффициенту К значений угловых 7 и а линейных,1 и л Ь величин сводится фактически к установке на всех этих шкалах непосредственно значения задаваемого условиями задачи коэффициента К.Работу устройства продемонстрируем на примере решения геометрической задачи коммивояжера. В этом случае устройство работает следующим образом.Исходное положение устройства показано на фиг. 3. На всех шкалах выставляются нулевые отметки. При этом проекция светового потока представляет собой круг. Вертикальная штанга 4 поворачивается вокруг своей оси в заданном направлении, устанавливаемом с помощью транспортира 3 по риске 5 и фиксируется фиксируюгцим элементом 6. Затем,перемещая основание 1 с помощью пантографа 2, добиваются того, чтобы центр круга, определяемый проекцией 26 перекрестья на карту, совместился с первой исследуемой точкой Далее заданную величину отношения функций влияния (коэффициент К) устанавливают на соответствующих шкалах с целью приведения устройства в рабочее положение. Указанное приведение устройства в рабочее положение схематично изображено на фиг. 4 (всего требуется установить значение коэффициента К на четырех шкалах Сдь бь бз и 64 )Выбор ближайшей точки маршрута осуществляется с помощью увеличения (уменьшения) размеров эллипса заданной формы и ориентированного в заданном направлении (фиг. 6). Такое увеличение (уменьшение) размеров эллипса достигается перемещением штанги 12 с зафиксированным на ней осветителем 7 вдоль направляющей втулки 14. При этом, цем меньше размер эллипса, который накрывает точку, тем меньше затрат требуется для перехода из центра эллипса в эту точку и, следовательно, такая точка будет ближайшей. Ьлижайшей к центру будет точка б, а не точка а, так как точка б достигается при движении от центра быстрее, чем точка а (т.е. через точку б проходит изолиция меньших затрат, чем через точку а).После определения очередной точки устройство возвращается в исходное положение; перемещением основания 1 с помощью пацтографа 2 добиваются совмещения с ней центра окруж ности, изложенным способом определяют следующую точку, т, д. до получения последней точки.Если начальная точка маршрута це задана, то она может быть определена путем решения и раз (где и - число заданных точек маршрута) аналогичных задач изложенным способом, принимая последовательно в качестве начальной точки каждую из и точек. Суммируя при этом общие затраты на каждом из и маршрутов и сравнивая их между собой, можно выявить маршрут с наименьшими затратами и принять его в качестве решения. При условии определения маршрута, затраты на который не превосходят заданной величины, 5 процедура определения маршрута прекращается при выполнении этого условия и он принимается в качестве решения. Для операции оценки затрат на переход цз одной точки в другую необходимо снять отсчет со шкалы 27 и умножить это число на цену, т.е. на затраты, необходимые на переход из центра на эллипсе, соответствующий перемещению на одно деление шкалы 27. Общие затраты, потребленные для обеспечения всего маршрута, определяются путем 5 суммирования затрат на каждом шаге.формулы, необходимые для градуирования шкал С 2 ь С 22, (2 з, С 2 (фиг. 4) в зависимости от задаваемого условиями задачи коэффициента К (отношение функций влияния): 20д хдхд 1 г/дг3. = агсаи г сох рпг"г - Кг 2С 21(К) =у = агс(д 0,5(дф+.с) - (дф - 1);252(К) = - 2 с = а 7ВС=д+ гг ) - д - гг)С 2 з (К) = л 1= ВС+ 1 виу;ЗОб (К = Ь Ь= 1(1 - сов 2),где д 1 х/дхад 1 г/дг - задаваемые условиями задаци функции влияния;р - угол полураствора конуса световогопотока (задается формой бленды 9);35 11 - фиксированная величина, равнаярасстоянию от фокуса объектива 8 осветителя 7 в исходное положении до рабочейповерхности стола (т.е. до нижней поверхности основания 1),этому расстоянию соответствует нулевая отметка шкалы 22;11 - фиксированная величина, равнаядлине штанги 12 от нулевой отметки шкалы27 до фокуса объектива 8 (фцг. 4).Форлула изобретения45Устройство для решения геомстричсских и комбинаторных задач, содержащсе первую штангу с нанесенной на цес шкалой, первый транспортер, жестко сосдццсц ный с первой штангой, первый фиксирующий элемент, отличающееся тем, цто, с цслью повышения точности, в него введсцы прибор для формирования эллипсов, содержащий осветитель, снабженный объсктивом с блендой, корпус объектива жестко сосдицсц с вторым транспортером и шарнирно соединен с первой цтангой, помещенной внутри первой направляющей втулки, снабженной первым и вторым фиксирующими элемец 1336038тзми, первая направляющая втулка соединена с второй штангой, с которой жестко скреп,ен третий трзнспортер, вторая штанга расположена вну гри второй направляющей втулки, которая жестко соединена с третьей втулкой, являющейся направляющей для поворотной штанги, установленной на основании, выполненном с возможностью горизонтального и вертикального перемещения относительно плоскости стола, вторая и третья втулки и основание снабжены с третьего по пятый фиксирующими элементами соответственно, вторая и третья штанги снабжены нанесенными на них шкалами,Составитель 3. ШершневаРедактор С. Патрушева Техред И. Верес Корректор И.МускаЗа каз 3805/46 Тираж 672 ПодписноеВНИИПИ Государственного комитета СССР по делам изобретений и открытий13035, Москва, Ж - 35, Раушская наб., д, 4/5Производственно. полиграфическое предприятие, г. Ужгород, ул. Проектная, 4