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

На правах рукописи

005006200

Токтошов Гулжигит Ысакович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ ОПТИМИЗАЦИИ СИСТЕМ СЕТЕВОЙ СТРУКТУРЫ В УСЛОВИЯХ ВЫСОКОГОРЬЯ

05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 5 ДЕК 2011

Новосибирск - 2011

005006200

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики" (ФГОБУ ВПО "СибГУТИ").

Научный руководитель: доктор физико-математических наук,

профессор

Попков Владимир Константинович

Официальные оппоненты: доктор физико-математических наук,

профессор

Малашенко Юрий Евгеньевич

Защита состоится 27.12.2011 г. в 16-30 часов на заседании диссертационного совета Д 003.061.02 при Учреждении Российской академии наук Института вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН) по адресу: 630090, г. Новосибирск, проспект академика М. А. Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан 23 ноября 2011г.

кандидат физико-математических наук, Мигов Денис Александрович

Ведущая организация:

ФГОБУ ВПО «Санкт-Петербургский государственный университет телекоммуникаций» имени проф. М. А. Бонч-Бруевича

Ученый секретарь

диссертационного совета Д 003.061.02 доктор физико-математических наук

С. Б.Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

- учет природных и сшуационных условий заданной территории;

- рассмотрение подсистем «линейные сооружения - область размещения» как единого объекта исследования;

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

- проведение оценки стоимости проектируемой сети до начала строительных

работ;

- применимость к проектированию сетей различного назначения.

Поставленная цель достигается в результате:

- создания концептуальной основы анализа и синтеза систем сетевой структуры

различного назначения;

- исследования существующих моделей и методов оптимизации сетей;

- исследования природных и ситуационных условий области размещения;

- разработки информационных и математических моделей местности;

- моделирования взаимодействия подсистем «линейные сооружения - область размещения»;

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

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

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

Методы исследования базируются на методе сеток, теории графов исследовании операций, дискретной оптимизации, методах имитационног моделирования, методах теории гиперсетей.

Основные положения, выносимые на защиту:

- концептуальная модель для анализа и синтеза инженерных сетей различног назначения;

- двумерная и трехмерная цифровые модели области размещения;

- гиперсетевая технология оптимизации инженерных сетей;

- двухэтапный алгоритм размещения линейных сооружений на заданно территории.

Научная новизна работы состоит в следующем:

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

- разработаны двумерная и трехмерная цифровые модели области размещения учитывающие зависимость трасс линейных сооружений от рельефа местности;

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

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

- разработана программа для проведения численных экспериментов.

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

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

Апробация работы

Основные научные результаты работы докладывались и обсуждались на следуют конференциях и семинарах:

- (3-я - 6-я) Международные Азиатские школы-семинары "Проблем оптимизации сложных систем" (Киргизия, Казахстан, Россия, 2007-2010 гг.);

- IX Всероссийская конференция молодых ученых "Математическое моделирование и информационные технология" (г. Кемерово, КемГУ, 28-30 oicr. 2008 г.);

- Всероссийская научная конференция молодых ученых "Наука. Технологии. Инновации" (г. Новосибирск, НГТУ, 4-7 декабря 2008 г.);

- Российских научно-технических конференциях "Информатика и проблемы телекоммуникаций" (г. Новосибирск, СибГУТИ, 2008-2011 гг.);

- Региональная научно-практическая конференция "Молодежь и научно-технический прогресс" (г. Владивосток, ДВГГУ, апрель-май 2009 г.);

- Международная научно-практическая конференция "Электроэнергетика в сельском хозяйстве" (Республика Алтай, с.Чемал, 26-30 июня 2009 г.);

- IV Всероссийская конференция "Проблемы оптимизации и экономические приложения" (г. Омск, 29 июня - 4 июля 2009 г.);

- Всероссийская конференция "Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях" (г.Иркутск, 15-17 июня 2011г.).

Основные результаты диссертационной работы опубликованы в 17 работах, список которых приведен в конце автореферата, среди них 2 работы опубликованы в периодических изданиях из списка ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем работы -200 страниц. Основной текст диссертации изложен на 180 страницах, включает библиографический список из 129 наименований работ и 30 рисунков. Рисунки, формулы и библиографические ссылки имеют сквозную нумерацию по всей работе.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, определены ее цели и задачи исследований, приведена структура и краткое изложение

работы по каждой главе.

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

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

Далее исследованы прикладные задачи, возникающие при управлении эксплуатацией инженерных сетей.

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

Определение 1. Гиперсеть 5 = (X,V,R\P,F,W) - это математическая модель : структуры инженерных сетей, включающая (рис. 1):

- X -(х^х2,...,х„) - множество вершин;

- V = (v,,v2.....v ) _ множество ветвей;

- R = (r,,r2,...,rm)~ множество ребер;

- Р: V -» 2х ~ отображение, сопоставляющее каждому элементу veC множество P(v) с X его вершин, тем самым, отображение Р определяет граф PS = (X,V;P);

- F:R-^2'PS - отображение, сопоставляющее каждому элементу гей множество ветвей F(r), образующих простой маршрут в графе PS = (X,V\P), причем семейство подмножеств ветвей 2'ps содержит такие подмножества, ветви которых составляют связную часть графа PS. Отображение F определяет гиперграф FS = (V,R;F);

- \/reR W \r2nHr)) - отображение, сопоставляющее каждому элементу! г s R подмножество его вершин W(r) с P(F(r)), где P(F(r)) - множество вершин в PS, инцидентных ветвям F(r) с К. Отображение Wопределяет граф WS = (X,R,W). Таким образом, гиперграф PS ~ первичная сеть, а гиперграф WS - вторичная сеть.

Из определения гиперсети следует, что математическая модель области размещения соответствует первичной сети PS = (X,V;P) (рис. 1,а) гиперсети S, а конфигурация инженерной сети - вторичной сети WS = (X,R;W) (рис. 1,6). Взаимодействие этих сетей определяется гиперсетью S (рис. \,в), т.е. ветвь veV инцидентна ребру г eR тогда и только тогда, когда соответствующее ребро г вторичной сети реализовано по ветви v соответствующей трассы F(r) .

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

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

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

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

Исследованы инженерно-экономическая и информационная модели местности, содержащие полную первичную и вторичную информацию о местности, что позволяет:

- установить рациональное положение трассы линейных сооружений и ее объектов относительно окружающей среды;

- получить оптимальные условия эксплуатации сетей;

- разработать рациональные параметры элементов сети;

- определить объемы строительных работ и стоимость строительства сети и т. д.

Представлена модель интегрированной информационной среды, которая служит

информационной основой построения вторичных моделей местности.

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

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

У2 УI

Л=с

X] х, X,

«О

Рис. 2. Построение двумерной расчетной сетки

Пусть О - сетка, наложенная на область размещения В. Всякая ветвь, соединяющая некоторые пары узлов хр и характеризуется длиной р и

стоимостью

Длина ветви (х]:, х^к[„) для двумерной расчетной сетки определяется следующим образом:

- р(х„, = \х]+к +1у,„ -у,| для прямоугольной сетки без диагоналей;

- . х^иг) = "*у)2 + 0^ - Л)2 Для прямоугольной сетки с диагоналями.

Нетрудно заметить, что величина удовлетворяет аксиоме

метрического пространства, т. е. для всех и к,г {] *к, г Фг)\

1) р(х^,хММг) >0=> р( = 0, если хм = хм,+г;

2) Р^щХ^г) =

Для линейных сооружений, продольный профиль которых зависит от высотных характеристик области размещения, для каждого узла сетки О, кроме метрических характеристик ветвей, аналитически или в виде таблицы задается минимальный перепад высот Ъ моделируемой поверхности. Далее сетка О переносится снизу вверх параллельно по оси Ог таким образом, чтобы она касалась всеми точками поля высот И = f{x,у), в результате чего получается трехмерная сетка (рис. 3,д-г).

Рис. 3. Построение трехмерной расчетной сетки

Далее приведены примеры вычисления длин ветвей (хл, соединяющих

некоторые пары узлов трехмерной расчетной сетки. Причем (рис. 3,г):

- р(А, В)-1, если вершины А и В соседних клеток располагаются на одном уровне;

- р(А,С) = ^/2 + , если вершины А и С соседних клеток располагаются на разных уровнях;

- /?(5,У) = ,/2/2+(й2+Лз)г, если вершины В и 3 соседних клеток располагаются на разных уровнях (диагональ с двумя ступенями);

- рф, = 1-Л , если вершины Си? соседних клеток располагаются на одном уровне (диагональ);

- р(А,в) = ^212 +к\ , если вершины Айв соседних клеток располагаются на

разных уровнях (диагональ с одной ступенью).

В работе для определения направления трассы для прокладки линейных сооружений введены величины а - угол между отрезком, соединяющим некоторые пары узлов (не фиктивных), и горизонтальной поверхностью; аир - предельно допустимый угол прокладывания линии вверх по склону; <ОЭ-

предельно допустимый угол прокладывания линии вниз по склону; а1Ш - предельно допустимый угол прокладывания линии перпендикулярно по склону.

Выделены возможные случаи:

1. Если а<а„р, то прокладка линии вверх по склону разрешена, в противном случае - нет;

2. Если а > £г4- , то прокладка линии вниз по склону разрешена, в противном случае - нет;

3. Если а <|а1(А|, то прокладка линии перпендикулярно склону разрешена, в противном случае - нет. Ясно, что {а^, аЛтт , }<90°.

Введены правила определения направления ветви:

- если для некоторой пары узлов трехмерной сетки П, расположенных на разных уровнях, выполняется условие 1 (условие 2), то ветвь ориентирована снизу вверх (сверху вниз);

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

Показана сводимость трехмерной расчетной сетки к некоторому ориентированному графу, взвешенному соответствующим образом (рис. 4).

Рис. 4. Построение ориентированного графа

Каждой ветви расчетных сеток П присвоим вес, равный

где ж ={жу.,>()(/ = 1,2.....»и;У = 1,2.....я) - координаты точек пересечения ветвей

(Хл,х^к1„)еП; а(хл,х^к1„) - стоимость строительных работ на единицу длины ветви.

Очевидно, что суммарная стоимость строительных работ во всей сеточной области принимает следующий вид:

б(£1) = £ в(*,, ) • р(х,, х^нг) (2)

П

Определение 2. Область D на плоскости хОу называется однородной

территорией, если Vxj„xmj„ еП: = const (г =1,2,..„от; у = 1,2.....и;

j противном случае область D называется неоднородной.

Ясно, что в горной местности удельные строительные затраты различны в различных точках области D, т.е. значение функции Qix^x^^) зависит от координат точек xJt,xMJ„ е D. В этом смысле область D можно считать неоднородной.

Для моделирования неоднородность заданной территории применена следующая технология: область D, в соответствии с выбранными критериями, разбивается на элементарных участков Д,...,Д. с примерно одинаковыми природными и ситуационными условиями, и внутри каждого элементарного участка D, (/ = 1,..,г количество элементарных участков) строится расчетные сетки П, (/ = 1,..,г).

т

Очевидно, что вся сеточная область Q = |Ji2;.

м

Суммарная стоимость строительных работ во всей сеточной области дня неоднородного случая имеет вид:

(

\

(3)

ы V п.

(г - количество элементарных участков, на которые разделена вся область,

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

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

. Показано, что взаимодействие структуры подсистем определяется иерархической 3-гиперсетью = (Рв,РО,Р5,РЮ;(рис.5), в которой = - граф, построенный на множестве узлов X сетки £1, а множество

ребер соответствует ее ветвям; РО = {Х1сХ,и-,Р1) - граф ситуационных трасс, в котором Х> с X - множество узловой основы заданной территории (места возможного размещения узловых элементов), а V - всевозможные трассы для линейных сооружений; РБ = (Х2 с - граф для линейных сооружений (ЛС), в

котором множество вершин Х2сХ1 соответствует местам непосредственного размещения узловых элементов сети, а ребра V - линейным сооружениям; Ш = (Хъ с Хг,Я\Ръ) - граф вторичных сетей, в котором Х1сХ1~ множество узлов, а Я - множество ребер вторичной сети. Приведена постановка задачи оптимизации

сетей, суть которой- построение иерархической 3-гиперсети S, минимальной стоимости.

Рис. 5. Гиперсетевойподход к проектированию сетей

Приведено описание методики оптимизации сетей на основе предложенной технологии и исследованы' задачи оптимизации сетей на примере сетей

электропередачи и электросвязи.

Для проведения численных экспериментов в диссертации решено использовать гиперсеть S = (PS,WS\F). Такой выбор основан на том, что гиперсета S = (PS,WS;F) в настоящее время наиболее изучены и при синтезе оптимальных структур сетей дают наиболее приемлемые результаты. Далее приведена обобщенная постановка задачи оптимизации сетей как задачи оптимального вложения вторичной сети WS гиперсета

S в первичную сеть PS.

Постановка задачи. Пусть известны графы PS = (X,V) и WS-(Y,R) и

параметры их элементов: p(v) - длина ветви veV графа PS; р(г) - длина ребра

reR графа WS, равная p(r)= £p(v); а(у) - удельная стоимость строительных

(земляных) работ на ветвях veV; br(v) - удельная стоимость аренды ресурсов для ветви veV; c(r) - стоимость приобретения и монтажа линий reí для прокладки ветви между парой заданных точек á.(r) - стоимость эксплуатационных работ.

Задача заключается в реализации ребра графа WS (прокладке линий или коммуникаций) по соответствующим маршрутам (трассам) в графе PS таким образом, чтобы функционал

«C ) reR J

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

Предложен двухуровневый алгоритм решения поставленной задачи, основная идея которого заключается в поиске начального решения и его улучшения. Начальное решение может быть найдено с помощью известного алгоритма Флойда или «жадного» алгоритма. Суть «жадного» алгоритма в данном случае состоит в следующем: найти все кратчайшие маршруты в графе PS с помощью алгоритма Флойда; реализовать самое дешевое (только один) ребро г е R графа WS в PS; обновить стоимости ветвей графа PS для ребра R\r (стоимость использованных ветвей равна нулю); повторить процесс до тех пор, пока не будут перебраны все ребра графа WS.

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

Для определения списка, по которому следует осуществлять перереализации ребер графа WS в PS, были использованы следующие понятия.

Определение 3. Если \/veV at(r) = const, то граф первичной сети PS, построенный на сетке (С1тЫ)) назовем однородным (неоднородным) и обозначим как PS^ (PSmod ).

Определение 4. Гиперсеть, построенную путем вложения графа вторичной сети WS в PS^ (PSMM), назовем однородной (неоднородной) и обозначим как S^ (5те0д ).

Для каждого ребра ^ ei? вычислим величину

Р(гиг/> ~ Xl^* п к* j которую в дальнейшем будем называть

j

метрикой 1, где Vk = F(rk) и Vj = F(rj) - множество ветвей графа PS„ttld , по которым проходят ребра гк и соответственно. Такая метрика позволяет определить, насколько расходятся ребра reR друг от друга при их реализации в графе PS„tod. Далее производится улучшение начального решения путем перереализаций в графе PSmM , начиная с самого удаленного ребра.

Для каждого ребра rkeR вычислим величину p(rk, rf-) = |(У, u V^) \ {Vk п V^ )|, которую в дальнейшем будем называть метрикой 2, где Vk - F(rk) - множество ветвей графа PSKl0d , Vf = F(rf) - множество ветвей графа PSoi, по которым проходят ребра гк и г^ соответственно. Такая метрика позволяет выяснить, насколько расходятся маршруты Vk =F(rk) и У„м - F(r^) в графах PSmod и PS^ для ребра гк и г? соответственно. Для достижения быстрой сходимости начального решения к оптимуму процесс перереализации должен начаться с того ребра, у которого самые расходящиеся маршруты.

Таким образом, для улучшения начального решения путем перереализации ребер reR графа fVS по новым трассам в обоих случаях необходимо упорядочить ребра в порядке убывания метрики, в результате чего получим список ребер {rt},i = \,...,m.

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

Случайная метрика. Произвольный порядок (список) можно построить, генерируя случайные числа от 1 до т.

Далее из списка {г(},г = 1,...,т выбирается ребро г,еЯ и удаляетея т гиперсети

Определение 5. Остаточную гиперсеть 5 \ г, по отношению к выбранному ребру назовем первичной сетью.

Для перереализации ребра г, е по новым трассам обновим параметры элементов первичной сети Б \ г; в соответствии с определенными правилами. Причем, если на некотором участке выбранного маршрута первичной сети 5 \ г; уже имеется трасса, которую можно использовать для реализации очередного ребра, то ее стоимость равна 0. С правилами обношхения (перерасчета) весов ветвей первичной сети 5 \ г, можно ознакомиться более подробно в диссертационной работе.

Найдем кратчайший маршрут с ломошью алгоритму Дейкстры на новых стоимостях в первичной сети 5 \ г,, и по нему перереализуем ребро г, е Д графа ,

После того как будут перебраны все ребра из списка {г(}, получим гиперсеть 51 с оценкой <9(5''), такую что @($11СОд )>{2($1). Перебор всех ребер из списка {г,} в порядке, определяемом метрикой, назовем итерацией. После второй итерации получим гиперсеть такую, что <2(5Исод )>()(5^)>(2($2) и т. д. Итерации повторяются до тех пор, пока есть возможность улучшить решения, т. е. <2($')>0(Б}~ ), где ] - номер итераций. Это объясняется тем, что через несколько итераций стоимость типерсети перестанет снижаться.

Далее в работе описана программная реализация предложенного алгоритма и приведены численные эксперименты.

Проведены расчеты стоимости прокладки вторичной сети по описанным выше алгоритмам. В качестве первичной сети использована граф-решетка (для наглядности на рис. 6 приведены результаты работы алгоритмов для решетки 5*5 вершин), стоимость единицы длины каждой ветви заданы случайными числами; дайна каждой ветви выбрана равной единице. Пары вершин для ребер вторичной сети, которую нужно сгенерировать, также выбраны случайным образом. Тесты проводились для различного количества ребер.

1

■ Флойд Я Ф-Метр1 □ Ф-Метр2 в Жадный

■ Ж-Метр1 О Ж-Метр2

и О

£ О

Й «

па а а

то аз

о

5 а_ о X

50 90 120 150 21

Число ребер Рис. 6. Численные эксперимен-

На рис. 6 по оси ординат отложена нормированная стоимость вторичной сети. Для нормирования выбиралось лучшее решение (имеющее минимальную стоимость), и веса всех решений делились на вес лучшего решения для заданного числа ребер. На оси абсцисс показано число ребер вторичной сети для которого проводился расчет. Для большей наглядности проведено 10 тестов для заданных параметров, а затем нормированная стоимость усреднена.

Численные результаты, полученные на различных решетках, показывают, что наилучший результат может быть получен с помощью разных алгоритмов в зависимости от числа ребер : при небольшом числе ребер лучшие результаты дает «жадный» алгоритм, а при большом (больше, чем ветвей Л?) - обычный алгоритм Флойда. Перелом происходит в тот момент, когда количество ребер вторичной сети примерено равно числу веггвей первичной сети (| № |=120 на рис. 6).

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

Однако, при использовании метрики 1 необходимо чуть меньшее количество итераций, чем для метрики 2. Например, для решетки 5><5 с использованием метрики 1 решение будет получено, в среднем, за 2,5 итерации, а с использованием метрики 2 - в среднем за 3 итерации.

Таким образом, метрика 1 показывает лучший результат, однако вычислительная сложность метрики 1 выше, чем метрики 2.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертационной работы состоят в следующем:

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

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

- предложена модель интегрированной информационной среды, являющаяся информационной основой для построения вторичных (математических, цифровых) моделей местности;

- разработаны двумерная и трехмерная (двумерная блочная и трехмерная блочная) расчетные сетки, являющиеся математической основой поиска оптимальных трасс для прокладки линий;

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

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

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

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

Список публикаций по теме диссертации Из списка ВАК:

1. Попков В. К., Токтошов Г. Ы. Гиперсетевая технология оптимизации инженерных сетей в горной или пересеченной местности Н Вестн. Бурят, гос. ун-та. - Сер. Математика и информатика. Улан-Уде: Изд-во Бурят, гос. ун-та. -Вып. 9 (июнь 2010). - С. 276 - 282.

2. Попков В. К., Токтошов Г. Ы. Методологические вопросы оптимизации инженерных сетей на неоднородной территории // Изв. Том. политехи, ун-та. - Сер. Управление, вычислительная техника и информатика. -Томск: Изд-во Том. политехи, ун-та. - 2010, № 5. Т. 317. - С. 40- 44.

Прочие публикации:

3. Токтошов Г. Ы. О задаче оптимального проектирования инженерных сетей в горных условиях // Материалы 2-й Азиат. Междунар. школы-семинара «Проблемы оптимизации сложных систем», Новосибирск, 7-12 авг. 2006 г. // Труды ИВМиМГ СО РАН, Сер. Информатика. - Вып. 6. - С. 210-221.

4. Токтошов IV Ы. Математическая модель топоосновы горной местности II Материалы 3-й Азиат. Междунар. школы-семинара «Проблемы оптимизации сложных систем», Бишкек (Кыргызская Респ.), 1-12 июля 2007 г. II Труды ИВМиМГ СО РАН. Сер. Информатика. - Вып. 7. - С. 123-126.

5. Токтошов Г. Ы. Об одной задаче анализа связности иерархических систем Н Тез. докл. 9-й Всерос. науч. конф. молодых ученых «Математическое моделирование и информационные технологи», Кемерово, 28-30 окт. 2008 г. -С. 27-28.

6. Токтошов Г. Ы. Особенности выбора направлений трасс линейных сооружений в условиях высокогорья И Материалы 4-й Азиат. Междунар. школы-семинара «Проблемы оптимизации сложных систем», с.Чемал (Респ.

- Алтай), 20-30 июня 2008 г. // Труды ИВМиМГ СО РАН. Сер. Информатика. -Вып. 8-С. 206-211.

7. Токтошов Г. Ы. Задача анализа живучесть иерархических сетей II Материалы Всерос. науч. конф. молодых ученых «Наука. Технологии. Инновации», Новосибирск, 4-7 дек. 2008 г. - Ч. 1. - С. 43-45.

8. Токтошов Г. Ы. Сеточная аппроксимация элементов рельефа местности //Материалы Всерос. науч.-технич. конф. «Информатика и проблемы телекоммуникаций», Новосибирск, 27-28 апр. 2009 г. - Т. 1.- С.23-24.

9. Токтошов Г. Ы. Сеточная аппроксимация в задаче поиска р-медианы гиперсети II Материалы 4-й Всерос. конф. «Проблемы оптимизации и экономические приложения», Омск, 29 июня - 4 июля 2009 г. - С. 167.

- 10. Токтошов Г. Ы., Касобов Л. С. Задачи выбора оптимальных схем системы электроснабжения /I Материалы регион, науч.-практ. конф. «Молодежь и научно-технический прогресс», Владивосток, апр.-май 2009 г. - Ч. 2. -С. 50-53.

11. Попков В. К., Токтошов Г. Ы. Задачи поиска оптимальных схем системы энергоснабжения методом сеточной аппроксимации // Материалы Междунар. науч.-практ. конф. «Электроэнергетика в сельском хозяйстве», с.Чемал (Респ/ Алтай,), 26-30 июня 2009 г. - Новосибирск: Изд-во Россельхозакадемия, Сиб. регион, отд., 2009. - С. 63-67.

12. Попков В. К., Токтошов Г. Ы. Об одной задаче оптимального размещения элементов электрических сетей // Инфосфера. 2009, № 42. - С. 38-40.

13. Токтошов Г. Ы. Метод сеток в задачах проектирования электрических сетей II Материалы 5-й Азиат. Междунар. школы-семинара «Проблемы оптимизации сложных систем», Бишкек (Кыргызская Респ.), 12 - 22 авг. 2009 г. II Труды ИВМиМГ СО РАН. Сер. Информатика. - Вып. 9 - С. 132-139.

14. Попков В. К., Токтошов Г. Ы. Об одной задаче синтеза сетей электросвязи в горных условиях И Пробл. инф. 2009, № 4. - С.15-32.

15. Токтошов Г. Ы. Вопросы оптимизации инженерных сетей на неоднородной территории // Материалы Всерос. науч.-технич. конф. «Информатика и проблемы телекоммуникаций», Новосибирск, 27-28 апр. 2010 г. - Т. 1,- С. 140.

16. Токтошов Г.Ы. Гиперсетевой подход к проектированию инженерных сетей/Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», г.Новосибирск, СибГУТИ, 2122 апреля 2011 г.//Том 1.-С.167-170.

17. Токтошов Г.Ы., Юргенсон А.Н. Гиперсетевой метод прокладки инженерных сетей!/Тезисы докладов Всероссийской конференции «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях», г.Иркутск, 15-17 июня 2011г.-С.114.

Токтошов Гулжигит Ысакович

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 18 ноября 2011 г. Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л.1,6, заказ № 60, тираж 100 экз., ФГОБУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

ВВЕДЕНИЕ.

Глава 1. ИССЛЕДОВАНИЕ СИСТЕМ СЕТЕВОЙ СТРУКТУРЫ (ССС) НА ПРИМЕРЕ ИНЖЕНЕРНЫХ СЕТЕЙ.

1.1. Инженерные сети (ИС) как объект исследования.

1.1.1. Основные свойства сетей.

1.1.2. Жизненный цикл ИС.

1.2. Линейные сооружения (ЛС).

1.2.1. Основное виды и назначения назначение.

1.2.2. Факторы, влияющие на выбор трассы для ЛС.

1.3. Задачи управления инженерными сетями.

1.3.1. Задачи инвентаризации, паспортизации, учета.

1.3.2. Задачи пространственного моделирования сетей.

1.3.3. Расчетные задачи анализа и управления.

1.3.4. Задачи моделирования жизненного цикла сетей.

1.4. Выводы.

Глава 2. МЕТОДОЛОГИЧЕСКИЕ ВОПРОСЫ ИССЛЕДОВАНИЯ И ПРОЕКТИРОВАНИЯ СЕТЕЙ.

2.1. Описание сетей и их теоретические модели.

2.1.1. Морфологическое описание сетей.

2.1.2. Концептуальное описание.

2.1.3. Формальное описание структур сетей.

2.2. Технологический подход к решению задач оптимизации сетей.

2.2.1. Предварительное описание ситуации и внешней среды.

2.2.2. Анализ критериев эффективности.

2.2.3. Формулировка цели и целевой функции.

2.3. Задачи оптимизации сетей и методы их решения.

2.3.1. Задачи анализа и синтеза.

2.3.2. Содержательная постановка.

2.3.3. Формальная постановка.

2.3.4. Выбор методов решения и их описание.

2.3.4.1.Сравнительный анализ.

2.3.4.2.Описание методов решения.

2.4. Выводы.:.

Глава 3. ИНФОРМАЦИОННОЕ И МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПРОЕКТИРОВАНИЯ СЕТЕЙ В ГОРАХ.

3.1. Особенности проектирования сетей в горах.

3.1.1. Описание горной местности.

3.1.2. Природные и ситуационные условия.

3.2. Информационное обеспечение проектирования сетей.

3.2.1. Инженерно-экономическая и информационная модели местности.

3.2.2. Построение интегрированной информационной среды.

3.2.3. Основные требования к исходной информации.

3.3. Метод сеток.в построении моделей местности.

3.3.1. Сущность и применение метода сеток.

3.3.2. Классификация и анализ типов сеток.

3.3.3. Обоснование и выбор сеток и сеточной области.

3.4. Математическое обеспечение проектирования сетей.

3.4.1. Двумерная расчетная сетка.

3.4.2. Трехмерная расчетная сетка.

3.5. Выводы.

Глава 4. ГИПЕРСЕТЕВОЙ ПОДХОД К ПРОЕКТИРОВАНИЮ

ИНЖЕНЕРНЫХ СЕТЕЙ.

4.1. Гиперсетевая технология.

4.1.1. Описание и разработка.

4.1.2. О методике применения гиперсетевой технологии.

4.1.3. Примеры оптимизации сетей.

4.2. Гиперсетевой подход к проектированию сетей.

4.2.1. Постановка задачи.

4.2.2. Двухэтапный метод прокладки JIC.

4.2.3. Алгоритмы и численные эксперименты.

4.2.3.1 .Двухэтапный алгоритм построение сетей.

4.2.3.2.Описание программной реализации и численные эксперименты.

4.3. Выводы.

Во введении обосновывается актуальность работы- диссертационной работы, определены ее цели и задачи исследования.

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

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

Глава 2 посвящена методологическим вопросам исследования и оптимизации сетей различного назначения. Предложены различные типы теоретических моделей инженерных сетей, с помощью которых прогнозируются характеристики и оцениваются возможности проектируемых сетей, проверяется их соответствие предъявляемым требованиям. Исследованы основные типы гиперсетей как универсальной модели, описывающей взаимодействие подсистем «линейные сооружения — область размещения» как единый объект исследования.

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

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

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

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

Исследован метод сеток для аппроксимации элементов топоосновы местности, описаны особенности выбора типов- сеток при построении вторичной (математической или цифровой) модели заданной территории.

10

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

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

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

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

В завершении приведено описание программной реализации предложенного алгоритма и приведены численные эксперименты.

Заключение содержит основные результаты, полученные в диссертационной работе.

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

- двумерная и трехмерная цифровые модели области размещения;

11

- гипер сетевая технология оптимизации инженерных сетей;

- двухэтапный алгоритм размещения линейных сооружений на заданной территории.

Научная новизна работысостоит в следующем:

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

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

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

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

- разработана программа для проведения численных экспериментов.

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

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

12 результатов, полученных в совместных исследованиях, согласовано с соавторами.

Апробация работы

Основные научные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

- (3-я - б-я) Международные Азиатские школы-семинары "Проблемы оптимизации сложных систем" (Киргизия, Казахстан, Россия, 2007-2010 гг.);

- IX Всероссийская конференция молодых ученых "Математическое моделирование и информационные технология" (г. Кемерово, КемГУ, 28-30 окт. 2008 г.);

- Всероссийская научная конференция молодых ученых "Наука. Технологии. Инновации" (г. Новосибирск, НГТУ, 4-7 декабря 2008 г.); Российских научно-технических конференциях "Информатика и проблемы телекоммуникаций" (г. Новосибирск, СибГУТИ, 2008—2011 гг.);

- Региональная научно-практическая конференция "Молодежь и научно-технический прогресс" (г. Владивосток, ДВГТУ, апрель-май 2009 г.);

- Международная научно-практическая конференция "Электроэнергетика в сельском хозяйстве" (Республика Алтай, с.Чемал, 26— 30 июня 2009 г.);

- IV Всероссийская конференция "Проблемы оптимизации и экономические приложения" (г. Омск , 29 июня — 4 июля 2009 г.);

- Всероссийская конференция "Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях" (г.Иркутск, 15-17 июня 2011г.).

Основные результаты опубликованы в периодических изданиях [75, 76] и материалах конференций [73,74, 77, 99-110].

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем работы - 200 страниц. Основной текст диссертации изложен на 180 страницах, включает библиографический список из 129 наименований работ и 30 рисунков. Автор выражает глубокую признательность В. К. Попкову за постановку некоторых задач и осуществление научного руководства.

4.3. Выводы

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

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

- в качестве примера применения гиперсетевого подхода исследованы задачи оптимизации сетей электропередач и электросвязи;

- представлена более общая формулировка задачи построения сетей как задачи поиска эффективного (по стоимости) размещения инженерной сети в заданную территорию;

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

В целом в ходе исследований, проведенных в настоящей работе, получены следующие результаты:

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

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

- предложена модель интегрированной информационной среды, являющаяся информационной основой для построения вторичных (математических, цифровых) моделей местности;

1. АБРАМОВ Н. Н. Водоснабжение. Учеб. для вузов. — Изд. 2-е перераб. и доп. -М.: Стройиздат, 1974. - 480 с.

2. Антонов М. Ф. К вопросу выбора экономически наилучших вариантов. — Томск, 1959. — 50с.

3. Басакер Р. Конечные графы и сети / Басакер Р., Саати Т. Перевод с англ. -М.: Наука, 1973. 368 стр.

4. Безкоровайный В. П. Разработка методов оптимизации трасс магистральных газопроводов и их разветвлений для сетей произвольной конфигурации: Автореф.дис. .канд. техн. наук —М.: 1978. 25 с.

5. Берж К. Теория графов и ее применения. М.: ИЛ, 1962. 320 с.

6. Бойков В. Н. Сплайны в трассировании автомобильных дорог / В.Н. Бойков, Б.М. Шумилов- Томск: ЦНТИ, 2001.- 164 с.

7. Бокарев д. И. Основы систем автоматизированного проектирование в сварке: Учеб. пособ. — Воронеж, 2006. — 264 с.

8. Болтов И. Ф. Геодезические измерения при строительстве инженерных сооружений. Куйбышев, 1982. — 80 с.

9. Бородавкин П. П. Выбор оптимальных трасс магистральных трубопроводов / П. П. Бородавкин, В. Л. Березин, С. Ю. Рудерман. М.: Недра, 1974.-240 с.

10. Бородавкин П.П. Сооружение магистральных трубопроводов / П.П. Бородавкин, В.Л. Березин М.: Недра, 1977. - 407 с.

11. Браун Ю. Г. Применение ЭВМ при проектировании газовых сетей / Ю.Г. Браун, В.А. Гайда // Нефть, газ и нефтехимия. 1985. - № 4 - С. 14 - 20.

12. БУЛЕНКО П. Г. Сложность задачи поиска Ь-медианы гиперсети и ее точное решение // Проблемы оптимизации: сложных систем:материалы 1-й Азиат, между нар. школы-семинара — Новосибирск, 2005. — С. 16-20.

13. БУХАРКИН Е. II. Инженерные сети: Оборудование зданий и сооружений: Учеб. / Под ред. Ю. П: Соси на / Е. Н. Бухаркин, В. М. Овсянников, К. С. Орлов. М : Высш. шк., 2001. — 415 с.

14. ВАРФОЛОМЕЕВ- Ю. М. Отопительные и тепловые сети: Учеб. * / 10. М. Варфоломеев, О. Я. Кокорин. М.: ИНФРА-М, 2008. - 480 стр.

15. Еалямов В. А. О задаче оптимизации построения первичной сети связи /А Проблемы оптимизации сложных систем: материалы 1-й: Азиат, междунар. школы-семинара. — Новосибирск, 2005. — С. 66 78.

16. Галямов В. А. Исследование и разработка- моделей и методов оптимизации структур телекоммуникационных систем: Дис. . канд. техн. наук Новосибирск, 2006. - 167 с.

17. Гельфанд И. М., Фомин^-С;.В: Вариационное вычисление. М.: Изд-во физмат литературы, 1961.-227 с.

18. Глотов Г. Ф- Изыскание, проектирование и строительства инженерных сооружений. М. - 1964.

19. Голятин В. К. Гидрологические изыскания трасс линий электропередач.-М;: Энергия, 1968;-120 с.

20. A. Я. Толчан М.: Связь, 1977. - 360 с.

21. Демидова П. Г. и др. Математические методы в геоинформационных технологиях. — М.: Наука, 2003. — 119 с.28 . Делоне Б. Н. О пустоте сферы // Изв. АН СССР. ОМЕН. 1934. № 4. С. 793-800.

22. Оптимизация систем обустройства нефтяных месторождений / Ш. С. Донгарян, Я. М. Каган, В. А. Горбатиков и др. — Свердловск: Средне-Уральское книжное издательство, 1976. 208 с.

23. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети /А;Ю. Дорогов,.В. Ю. Лесных,. И. В. Раков и др. // Искус, интеллект. 2008. - № 3. - С. 419-427.

24. Надежность и живучесть системы связи / Б. Я. Дудник,

25. B. Ф. Овчаренко, В. К. Орлов и др.- М.: Радио и связь, 1984. 216 с.

26. Журавлев В. Г. Построение трассы высоковольтной линии электропередач минимальной длины путём добавления новых точек / В: Г. Журавлев, В. И. Чиник, М. А. Чиник // Электроэнергетика и автоматика. — Кишинев. АН Молд.ССР, 1965.

27. Зыков A.A. Гиперграфы //Успехи мат.наук- Вып. 6, 1974.-С.89- 154.

28. ИДЕЛЬЧИК В. И. Электрические системы и сети. М. - 1989. - 592 с.

29. Ионин А. А. Газоснабжение: Учеб. для вузов. 4-е изд., перераб. и доп. - М.: Стройиздат, 1989. - 439 с.

30. Ковалев М. Мг Дискретная оптимизация (целочисленное программирование): Изд. 2-е М;: Едиториал УРСС, 2003. - 192 с.

31. Коровина А. Моделирование, телекоммуникационной системы Владимирской области с применением ГИС-технологий. — Владимир, 2001. — 109 с. ,

32. Алгоритмы: Построение и анализ, 2-е изд. / Т. X. Кормен, Ч. И. Лейзерсон, Р. Л; Ривест и др. М.: Изд. дом "Вильяме!1, 2005. — 1296 с.47. кристофиднес Н. Теория графов. Алг.подход.-М.: Мир, 1978.-432 с.

33. Методы анализа и оценивания рисков в. задачах менеджмента безопасности сложных технических систем / С. П. Крюков, С. Д. Бодрунов, Л. Н. Александровская и др. СПб.: Б. и., 2007. - 460 с.

34. Кузнецов Р. Н. Определение оптимального маршрут прокладки: Автореф. дис. . канд. техн. наук Воронеж: Б. и., 2009. - 16 с.

35. Медиоланская М. М. Проектирование водопроводных сетей: Учеб. пособ. / М. М. Медиоланская, Е. А. Мезенева, С. В. Колобова. Вологда: ВТУ, 1999.- 150 с.

36. Меньчуков А. Е. Предварительное изыскание трасс линий электропередач / А. Е. Меньчуков, В. В. Овсеенко, Н. П. Путник. М.: Госэнергоиздат, 1963. - 224 с.61. музалевская Г. Н. Инженерные сети городов и населенных пунктов. м.: б. и. - 2006. - 148 с.

37. Николаев Е. Ю. Водоотводящие сети: учебное пособие. -Новосибирск: НГАСУ, 2007. 104 с.

38. Николаевская И. А. Инженерные сети и оборудование территорий, зданий и стройплощадок / И. А. Николаевская, Л. А. Горлопанова, Н. Ю. Морозова М.: Издательство Академия ИЦ - 2008: - 224 с.

39. Выбор алгоритма- определения- экономичных трасс прокладки кабелей: Отчет «Гипросвязь — 4» по изысканию; и проектированию сооружений связи МСС! Новосибирск, сентябрь 1977. — 192;с.

40. Нападмитриу X. Комбинаторная оптимизация. Алгоритмы и сложность / Пер. с англ. В. Б. Алексеева. / Х. Пападмитриу, К. Стайглиц М.: Мир, 1985. -510 с. '

41. ПОПОВ Ю:И. Оптимальное трассирование газосборных сетей на месторождениях: Автореф.дис. .канд. техн-.наук- М;:МИНХиГЩ 1981 .-22'с.

42. ПОПКОВ В. К. Математические модели' живучести сетей- связи; -Новосибирск: Изд-во СО АН СССР, 1990. -235 с.

43. Попков В. К. Математические модели связности / Огв.ред. А. С. Алексеев.,- 2-е изд.- Новосибирск: ИВМиМГ СО РАН, 2006. 490 с.

44. Попков В. К. Гиперсети и их характеристики связности // Исследования; по прикладной теории; графов. — Новосибирск: Наука, 1986. -С.25-59. , ' ' '' ■ V" :■ Г." • -V-V. '

45. Попков В: К. Гиперсети и структурные модели сложных систем // Математические5 и имитационные модели сложных систем. — Системное моделирование-6: Сб. науч. тр. / Под редакцией М. И. Нечепуренко. -Новосибирск: ВЦСО АН СССР 1981.-С. 26-48.

46. Попков В. К. Задачи поиска оптимальных схем системы энергоснабжения-методом? сеточной аппроксимации / В. К. Попков, Г. Ы.

47. Попков В. К. Гиперсетевая технология оптимизации инженерных сетей в горной или пересеченной местности / В. К. Попков, Г. Ы. Токтошов // Вестн. Бурят, гос. ун-та. Сер. Матем. и информатика. - июнь 2010. — Вып. 9. - С. 276-282.

48. Попков В. К. Методологические вопросы оптимизации инженерных сетей на неоднородной территории / В. К. Попков, Г. Ы. Токтошов // Изв. Том. политехи, ун-та. — Сер. Управление, вычисл. техн. и информ. — 2010. — №5.-Т. 317.-С. 40-44.

49. Свами М. Графы, сети и алгоритмы.: Пер. с англ:/ М. Свами, К. Тхуласираман М.: Мир, 1984. - 455с.

50. Скворцов А. В. Триангуляция Делоне и ее применение Томск: Изд-во Том. гос. ун-та, 2002. 128 с.

51. Скворцов А. В. Разработка геоинформационных и инженерных систем на факультете информатики и в ООО «Индорсофт» // Вестник ТГУ, 2003.-№280-С. 346-349.

52. Татт У. Теория графов. М.: Мир, 1988. - 424 с.

53. ТИЩЕНКО А. С. Оптимальное технологическое проектирование нефтепроводов.-М.: Недра, 1982. -263 с. . ■.■■'■ •

54. Токтошов Г. Ы. О задаче оптимального проектирования линейных сооружений в горных условиях // Проблемы оптимизации сложных: систем: материалы 2-й Азиат, между нар. школы-семинара — Новосибирск, 7-12 авг. 2006. С. 210-221. .

55. Ток готов Г. Ы. Математическая модель топоосновы горной местности // Проблемы оптимизации сложных систем: материалы 3-й Азиат, междунар. школы-семинара — Бишкек (Кыргызская Респ), 1-12 июля 2007. С. 123-126. .

56. Токтошов Г. ЬГ. Об одной задаче анализа;связности иерархических систем // Тез. докл. 9-й Всерос. конф. молодых ученых по Математическому моделированию и, информационным: технологиям — Кемерово, 28-30 окт. 2008. :С. 27 -28. . ' ,

57. TOKTOlliOB;F.,bIi Особенности- выбора; направлений трасс-линейных сооружений в условиях высокогорья // Проблемы оптимизации сложных систем: материалы 4-й Азиат, междунар. школы-семинара с.Чемал (Республика Алтай), 20-30'июня 2008 -С. 206г2Т1. V

58. Токтошов Г. Ы. Задача анализа живучесть иерархических сетей // Наука. Технологии. Инновации: материалы всерос. науч. конф. молодых ученых Новосибирск, 4-7 декабря 2008. — Ч. 1. — С. 43-45.

59. ТОКТОШОВ F. Ы. Сеточная аппроксимация элементов рельефа местности // Информатика и проблемы телекоммуникаций: материалы Рос. науч.-техн. конф. Новосибирск, 27-28 апреля 2009. - Т. 1- G. 23-24.

60. ТОКТОШОВ Г. Ы. Сеточная аппроксимация ■ в задаче поиска р-медианы гиперсети // Проблемы оптимизации и экономические приложения: материалы IV-й всерос. конф. — Омск, 29 июня 4 июля 2009: - С. 167. :

61. Токтошов Г.Ы. Гиперсетевой подход к проектированию инженерных сетей// Информатика и проблемы телекоммуникаций: материалы: Российской научноттехнической конференции — Новосибирск, 21-22 апр. 2011.-Том 1,-С. 167-170.'

62. Трассировка и монтаж высоковольтных линий' передач в горных условиях.- Отчет —Тифилиси, 1986. 166 с.

63. Третьяков В. Ю; Геоинформационные системы (ГИС): Метод, пособие. СПб.: Изд-во С.-Петерб. ун-та; 2005. - 16 с.

64. Федотов Г. А. Инженерная геодезия. М.: Б. и., 2009. - 463 с.

65. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. Пер. с англ./ Д. Филлипс, А. Гарсиа-Диас М.: Мир, 1984. - 496 с.115 . Фрэнк Г. Сети, связи и потоки / Г. Фрэнк, И. Фриш. М.: Связь, 1978.-448 с.116. харари Ф. Теория графов. М.: Б. и., 2003. - 296 с.

66. Хомяк Я. В. Построение оптимальных сетей автомобильных дорог. -М.: Транспорт,, 1969. 144 с.118. хохлов В; X. Экономика передачи электрической энергии. М.: Б. и., 1961.-№1.-108 с.

67. Хохлов В. X. Экономика передачи электрической энергии. М.: Б. и., 1961.-№'2 - 111'с.

68. XY Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.-520 с.

69. Чепцов В. М. Системы распределения- информации. Синтез структуры и управления. — М.: Связь, 1980. , . V :

70. ЧерноруцкиЙ И. Г. Методы- оптимизации. и принятия решения: учебное пособие. Спб: Лань. — 2001. 384 с.

71. Чита ев И. В. Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной. стоимости: Автореф. дис. . канд. техн. наук Рязань, 2006. - 16 с.

72. Шубенко В. А. Технико-экономические расчеты при проектировании сетей электрических систем. — Красноярск,. 1973. — 36 с.

73. Канализация: Учеб. пособ; для вузов. Изд. 5-е, перераб. и дополн. / С. В. Яковлев, Я.А. Карелин, А.И. Жуков и др.-М.:Стройиздат, 1975.-632 с.

74. Ямлеева Э. У. Инженерные сети и оборудование: водоснабжение и водоотведение. Ульяновск: Б. и., 2006. — 122 с.1. АКТо внедрении результатов кандидатской диссертации Токтошова Г.Ы.

75. Данная работа проводилась по результатам научно-исследовательских работ, выполненных Токтошовым Г.Ы.аспирантом профессора Попкова В.К.

76. В рамках предложенной Токтошовым Г.Ы. методики были запроектированы линейные сооружения для международного аэропорта «Манас-2» в г. Бишкек, филиала международного аэропорта «Манас» в г.Ош, школы непрерывного образования в г. Нарын.

77. Разработанная Токтошовым Г.Ы. методика программно реализована в J среде Delphi. Проведено соответствующий численный эксперимент показывающий эффективность применяемого метода по сравнению с известными.

78. RadioButtonl: TRadioButton;

79. RadioButtonlO: TRadioButton;

80. RadioButton2: TRadioButton;

81. RadioButton3: TRadioButton;

82. RadioButton4: TRadioButton;

83. RadioButton5: TRadioButton;

84. RadioButton7: TRadioButton;

85. RadioButton8: TRadioButton;1. RadioGroup2: TRadioGroup;1. Savel: TMenuItem;1. Exitl: TMenuItem;1. Openl: TMenuItem;1. Close 1: TMenuItem;1. OpenDialogl: TOpenDialog;

86. Forml: TForml; implementation {TForml } var

87. G, Tree: TGraph; WSS, WSS2: TWS; GWS: TGraphW; V:arrayl.NMax2. of Vertex; wscol:BT;leng, total: real; { }procedure MyRepaint; begin

88. Forml .Image 1 .Canvas.Pen.Color:=clBtnFace; Forml.Imagel.Canvas.Brush.Color:=clBtnFace; Forml.Image l.Canvas.Rectangle(0,0,500,500); end;

89. Процедура рисует первичную сеть} procedure DrawGraph(var G: TGraph);vari j,count,sq,sql:BT; begin

90. Vi+ö-l)*sql.X~trunc((Forml.Imagel.Width-30)/(sql-l)*(i-l))+15;

91. Vi+(j-l)*sql.Y:=trunc((Forml.Imagel.Height-30)/(sq-l)*(j-l))+15;1. Vi+ö-l)*sql.M:=0;end;

92. Forml .Imagel .Canvas.Pen. Width:=2;

93. Forml.Imagel.Canvas.Pen.Color:=clGreen;for i:=l to G.sides dofor j:=G.KAO1. to G.KAOi+l.-l doif j>=0 thenbegin

94. Form 1 .Image 1 .Canvas.MoveTo(V1. .X, Vi. Y);

95. Forml .Imagel.Canvas.LineTo(VG.FO[j.].X,V[G.FO[j]].Y);end;1. Рисуются вершины}

96. Form 1.Imagel.Canvas.Pen.Width:=l;

97. Forml .Imagel .Canvas.Brush.Color:=clGreen;

98. Form 1 .Image 1 .Canvas.Pen.Color:=cIBlack;for count:=l to G.sides dobegin

99. Заполняются данные о вершинах и их местоположении} Forml .Imagel .Canvas.Pen. Width:=2; Forml.Imagel.Canvas.Pen.Color:=clRed; for i:=l to G.sides do for j:=G.KAO1. to G.KAOi+l.-l do if j>=0 then begin

100. Form 1 .Image 1 .Canvas.MoveTo(V1. .X, Vi. .Y); Forml.Imagel.Canvas.LineTo(V[G.FO[j]].X,V[G.FO[j]].Y); end;1. Рисуются вершины}

101. Form 1 .Image 1 .Canvas.Pen. Width:= 1;

102. Forml. Imagel. Canvas.Brush.Color:=clGreen;

103. Forml .Imagel .Canvas.Pen.Color:=clBlack;for count:=l to G.sides dobegin

104. Form 1 .Image 1 .Canvas.Pen. Width:=2;

105. Form 1.Image l.Canvas.Pen.Color:=clRed; Forml.Imagel.Canvas.MoveTo(Vil.X,V[il].Y); Form 1 .Image 1 .Canvas.LineTo(V[i2] .X, V[i2]. Y); end;procedure DrawEdgeS(i 1,i2:integer); begin

106. Forml.Imagel.Canvas.Pen.Width:=2; Forml.Imagel.Canvas.Pen.Color:=clBluc; Form 1 .Image 1 .Canvas.MoveTo(Vi 1 . .X, V[i 1]. Y); Form I .Image 1 ,Canvas.LineTo(V[i2].X,V[i2].Y); end;procedure DrawVertex6(n:BT); begin

107. Рисуется вершина} Forml .Imagel .Canvas.Pen.Width:=l; Forml.Imagel.Canvas.Brush.Color:=clYellow; Forml.Imagel.Canvas.Pen.Color:=clBlack;

108. Forml .Imagel.Canvas.Ellipse(Vn.X-radius 1, V[n]. Y-radius 1, V[n] .X+radius 1, V[n] .Y+radius 1);

109. Forml.Image l.Canvas.TextOut(Vn.X-(radius2+2),V[n].Y-radius2-3,IntToStr(n));end;procedure DrawVertex5(n:BT); begin

110. Рисуется вершина} Form 1 .Image 1 .Canvas .Pen. Width:= 1; Form 1 .Image 1 .Canvas.Brush.Color:=clBlue; Forml .Image 1 .Canvas.Pen.Color:=clBlack;

111. SpecVEj.:= StrToInt(sl); if SpecVE[j]>G.sides then begin

112. MessageDlg('0HH6Ka', Такого номера вершины нет!', mtrnformation,[mbOK.,"); exit; end; end; specol:=j;ss:=Forml .Editl .Text; sl:="; j:=0; for i:=l to length(ss)do if ss1.o',' then sl:=sl+ssi. else begin

113. SpecVSj.:= StrToInt(sl); sl:="; end;if slo" then begin j:=j+l;

114. SpecVSj.:= StrToInt(sl); if SpecVS[j]>G.sides then begin

115. MessageDlg('Oum6Ka', 'Такого номера вершины нет!', mtInformation,mbOK.,"); exit; end; end;if (specoloj) then begin

116. MessageDlg('OiiiH6Ka', 'Количество начальных и конечных вершин не совпадает!', mtInformation,mbOK.,"); exit; end;end;1. GWS.sides:=G.sides;end;else simbol l:=simboll+simbol; end; end;

117. G.FO1.:=StrToInt(simboll); if ioG.KAOG.sides+l.-l then begin

118. MessageDlg('OmH6Ka','Ошибка в открытом Вами файле!', mtInformation,mbOK.,"); Exit; end; readln(Fl); i:=l;

119. Simboll:-'; while not Eoln(Fl)do beginread(Fl,simbol);1. Case simbol oft f.

120. G.CostD1. :=StrToFloat(simbol 1); simboll:-'; i:=i+l; end;else simboll:=simboll+simbol; end; end;

121. G.CostD1.:=StrToFloat(simboll); if ioG.KAOG.sides+1 .-1 then begin

122. MessageDlg('OmH6Ka','OuiH6Ka в открытом Вами файле!', mtInformation,mbOK.,"); MyRepaint; Exit; end; readln(Fl); i:=l;

123. Simbol 1:="; while not Eoln(Fl)do beginread(Fl, simbol);1. Case simbol of11.

124. G.CostA1.:=StrToFloat(simbol 1); simboll:-1; i:=i+l; end;else simboll^simboll+simbol; end; end;

125. G.CostA1. :=StrToFloat(simbol 1); if ioG.KAOG.sides+l.-l then begin

126. MessageDlg('OuiH6Ka','Ошибка в открытом Вами файле!', mtInformation,mbOK.,"); MyRepaint; Exit; end;end; end;

127. DrawGraph(G); GenWSl(GWS); end;procedure TForm 1 .TabSheet2ContextPopup(Sender: TObject; MousePos: TPoint; var Handled: Boolean);begin end;procedure TForml.CloselClick(Sender: TObject); begin

128. Gl.FO1.:=Gl.FOi-l.; Gl .CostA[i] :=G 1 .CostA[i-1 ]; G1 .CostD[i] :=G 1 .CostD [i-1 ]; end;1. Gl.FOGl.KAO[vl + l.]:=v2;

129. Gl.CostAGl.KAO[vl+l.]:=costa;

130. Gl.CostDGl.KAO[vl+l.]:=costd;for i:=(GI.sides+1) downto vl+1 do Gl.KAO1.:=Gl.KAOi.+l;end;

131. Удалить ребро(к,т) в графе со стоимостями} procedure DeleteEdgeC(var Gl: TGraph; k,m:BT); var i,l:BT; beginfor i:=Gl.KAOk+l.-l downto Gl.KAO[k] do if Gl.FO1.=m then beginfor 1:= i to Gl.KAOGl.sides+l.-l do begin1. G1 .FO 1. :=G 1 .FOl+l .;

132. G1 .Cost Al. :=G 1 .CostA[l+1 ]; G1 .CostDfl] :=G 1 .CostD[l-H ]; //G1 .Prob[l] :=G 1 .Prob[l+1 ]; end;for 1:= Gl.KAOGl.sides+l.-l to Gl.KAO[Gl.sides+l] do begin

133. FloydPathl(i,Pij.,M,P,WSS,k); FloydPathl(P[ij] j,M,P,WSS,k); end else begin

134. FloydPathT(i,Pij.,M,P,WSS,k); FloydPathT(P[i,j]j,M,P,WSS,k); end else begin1. WSSk.col:=WSS[k].col+l;

135. WSSk.VertexfWSS[k].col]:=j;end;end;end;procedure FirstFloyd(var G: TGraph; var GWS: TGraphW; var WSS: TWS; var wscol: ВТ); vark,i,j:BT; M: TMatr; P: TMatrlnt; suml, sum2: real; begin k:=0;

136. FloydStartl(G, M, P); for i:=l to GWS.sides dofor j:=GWS.KAO1. to GWS.KAOi+l.-l do begin

137. Разворачиваем путь от вершины до вершины if minl<NMaxF then begin

138. Vec1.:=0; VecRi.:=i; for j:=l to wscol doif (ioj) then Vec1.:= Veci.+Dis[ij]; end;

139. Bubble(wscol, Vec, VecR); end;procedure DistanceT(var WSS: TWS; wscol: BT; var VecR: TVector); varij,k,kk, sum: BT; Dis: TMatrlnt; Vec: TVector; begin

140. VecR1.:=i; Bubble(wscol, Vec, VecR); end;procedure RandomSort(wscol: BT; var VecR: TVector); vari,kk,q: BT; beginfor i:=l to wscol do

141. Distance(WSS, wscol, VecR); if Form 1 .RadioButton3 .Checked=true then

142. DistanceT(WSS, wscol, VecR); if Form 1 .RadioButton4.Checked=true then RandomSort(wscol, VecR); for j:=wscol downto 1 do begin i:=VecRj.; Buff:= WSS1.; GBuff:=G;for k:=l to WSS1.col-l do

143. DelFlag(WSS1.Vertexfk., WSSi].Vertex[k+I],G); FloydStart2(G,M,P); WSS[i].col:=l;

144. WSS1.Vertexl.:=Buff.Vertex[l];

145. Timl : TClock; str, strl: string; begin leng:=l;if G.sides=0 then begin

146. MessageDlg('OmH6Ka', 'Вы еще не загрузили граф!', mtInformation,mbOK.,") ; exit; end;if (CheckBox2.Checked=true) then

147. Forml.Memol. Lines. Add('Floydl = '+FloatToStr(total)); str:=str+FloatToStr(total)+','; end;if((RadioButton2.Checked=true) or (Forml.RadioButton3.Checked=true) or (Forml.RadioButton4.Checked=true)) and (wscol>0) then begin i:=0; repeat suml:=total;

148. Forml .Memo 1 .Lines. Add(str 1 +FloatToStr(total)); str:=str+FloatToStr(total)+','; str 1 :=str 1 +FloatToStr(i-1)+','; end;if (RadioButton5.Checked=true) then beginfor i:=l to G.KAOG.sides+l.-l do G.Flag1.:=0;

149. Forml.Memo 1.Lines. Add('CreateMetr = '+FloatToStr(total)); str:=str+FloatToStr(total)+','; end; ifkk=12 then begin

150. Form 1 .Memo 1 .Lines. Add('---------------');end;if (CheckBox2.Checked=false) then

151. Edit2.Text:=FloatToStr(total); for i:= 1 to wscol do beginfor j:= 1 to WSS1.col-l do

152. DrawEdge(WSS1.VertexO.,WSSi].Vertex[j+l]);end;for i:= 1 to wscol do begin

153. AddArcEVAll(i*sq+j,(i+ii)*sq+j+jij, costd,costa, G); AddArcEVAll((i+ii)*sq+j+jj,i*sq+j, costd,costa, G); end;if(j-jj>0) and (jj>0) and (i+ii<=(sq-l)) and (ii>0)then begincostd:=random(5)+5; costa:=random(5)+1;

154. AddArcEVAll(i*sq+j,(i+ii)*sq+j-jj, costd,costa, G); AddArcEVAll((i+ii)*sq+j-jj, i*sq+j,costd,costa, G); end;end;end;for i:=l to G.sides do G.Cost1.:=l;//random(5)+l;it

155. MyRepaint; DrawGraph(G); GenWSl(GWS); end;procedure SaveMyFile(var G: TGraph; strfile:string); var

156. SaveDialogl.Filename:=SaveDialogl.Filename+'.txt'; str:=SaveDialog 1 .Filename; SaveMyFileG(G,str); end; end;initialization$1 unitws.lrs} G.sides:=0; Randomize; end.