Способ моделирования задач оптимального размещения центра сети

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТ8У

Союз Соеетснмк

Социапнстнчеснни

Рес убпнн 1 879627 (61) Дополнительное к авт. свнд-ву— (22)Заявлено04.01.80 (21) 2865767/28-12 с присоединением заявки №(23) Приоритет—

Опубликовано07.11.81. Бюллетень №41

Дата опубликования опнсання10.11.81 (51) М. Кл.

G 09 В 23/02 (осудерственный коянтет

СССР оо делаи имбретеннй н аткрнтнй (53) УДК 515.

07 08(088 8) И. Н. Евтушенко и В. И. Колосов (72) Авторы изобретения

Запорожский машиностроительный институт им. В. Я. Чубаря (7!) Заявитель (54) СПОСОБ МОДЕЛИРОВАНИЯ ЗАДА"1 ОПТИМАЛЬНОГО

РАЗМЕЩЕНИЯ IIEHTPA СЕТИ

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

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

10 коэффициенты Р„. от и заданных точек.

Этот способ состоит в том, что в местах расположения заданных точек устанавливают опорные элементы и производят

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

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

Целью изобретения является расширение функциональных воэможностей.

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

879627

50 указателя судят о величине целевой функции.

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

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

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

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

40 вспомогательная неинфсрмационная связь.

В общем случае, суммарная длина гибкого элемента от точки закрепления его начала до последнего по очередности огибания опорного элемента или указателя с учетом вспомогательных неинформационных связей выражается формулой где 4с — количество вспомогатедьных неинформационных связей; — длина l -ой вспомогательной линии связи между вершинами радиальной сети (опорными элементами); суммарная длина всех вспомогательных неинформационных свяТак как суммарная длина P всех вспомогательных неинформационных связей для данных координат вершин радиальной сети есть величина постоянная Р =Oortef ), то истинное значение целевой функции для некоторых координат размещения центра определеляется выражением:

C=L — Р.

Длина гибкого элемента может быть определена по нанесенной на него в единицах стоимости связей шкале, нулевая отметка которой совмещена с: точкой закрепления начала гибкого элемента. При этом отметка шкалы против последнего no oseредности огибания опорного элемента или указателя соответствует с5ммарной длине 4 .

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

Истинное значение целевой функции в заданной точке размещения указателя вычисляют по формуле (1), используя полученные значения 1 и Р

Таким образом, размещая указатель B различных точках и считывая по шкале значения величин (, и Р, можно исспедовать форму целевой функции, т.е, зависимость суммарной стоимости произвольных . по трассам радиальных связей от координат размещения центра сети и изучать различные методы поиска экстремума.

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

Кроме этого, возмо»<ен поиск оптимального решения при наличии различных ограничений на трассе связей и обасти возмох<ного размещения центра.

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

879627

Составитель LL Гриценко

Редактор Л. Гольдина Техред А. Савка Корректор В. Бутяга

Заказ 9726/21 Тираж 487 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушска" наб., д. 4/5

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

Определение координат точек, лежащих на поверхности равного уровня проводят налогичным образом.

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

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

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

% 308148, кл. С 09 В 23/02, 1965.