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

ВВЕДЕНИЕ

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

1.1. Анализ архитектуры информационных систем масштаба предприятия на базе локальных вычислительных сетей ГО

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

1.3. Обобщенная постановка задачи оптимизации топологической структуры локальных вычислительных сетей информационных систем 41 ВЫВОДЫ

2. МОДЕЛИ ОПТИМИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ ОДНОРОДНЫХ ЛВС ИНФОРМАЦИОННЫХ СИСТЕМ '

2.1. Постановка задачи оптимизации топологической структуры однородных ЛВС информационных систем на базе концентраторов

2.2. Алгоритмы решения задачи оптимизации топологической структуры ЛВС информационных систем на базе концентраторов и их анализ

2.3 Постановка задачи оптимизации топологической структуры однородных ЛВС информационных систем на базе коммутаторов

2.4 Алгоритмы решения задачи оптимизации топологической структуры ЛВС корпоративных информационных систем на базе коммутаторов и их анализ

ВЫВОДЫ

3. МОДЕЛИ ОПТИМИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ НЕОДНОРОДНЫХ ЛВС ИНФОРМАЦИОННЫХ СИСТЕМ

3.1. Постановка задачи оптимизации топологической структуры неоднородных звездообразных ЛВС

3.2. Анализ существующих постановок задачи оптимизации неоднородных ЛВС и выбор метода решения

3.3. Генетический алгоритм оптимизации топологической структуры неоднородных звездообразных ЛВС

3.4. Экспериментальное исследование модифицированного генетического алгоритма синтеза топологической структуры ЛВСИС 124 ВЫВОДЫ

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

4.1. Реализация средств оптимизации топологической структуры ЛВС ИС в САПР "Модель"

4.2. Оптимизация топологической структуры ЛВС корпоративной информационной системы Шахтинских межрайонных электрических сетей

Интенсивное внедрение информационных систем (ИС) масштаба предприятия на базе локальных вычислительных сетей (ЛВС) сопровождается повышением требований к пропускной способности каналов передачи информации между клиентами сети и серверами. Такие изменения требований предопределяются увеличением числа пользователей в сети, повышением производительности рабочих станций, а также увеличением числа автоматизированных бизнес-процессов. Разработка подобных систем сопровождается существенными материальными затратами, которые в значительной степени зависят от выбранной топологической структуры ЛВС. Анализ отечественных и зарубежных публикаций показал, что существующие модели и методы конструирования структуры вычислительной сети масштаба предприятия ориентированы на использование моноканальной и кольцевой структур, таких как Ethernet или Token Ring, не удовлетворяющих требованиям современных ИС по производительности. В классе звездообразных вычислительных сетей известны математические модели для региональных и глобальных распределенных систем обработки информации, масштаб которых предопределяет существенные отличия в постановках задач и в методах решения. Для ЛВС звездообразной структуры задача синтеза топологии решена в частных постановках с использованием либо эвристических методик, либо без учета существенных для современных ИС параметров, таких как взаимное расположение рабочих станций, ограниченное число мест размещения активного оборудования (АО) - концентраторов и коммутаторов, а также требований к пропускной способности ЛВС. Таким образом, в условиях отсутствия адекватных современным требованиям моделей и методов проектирования топологической структуры звездообразных ЛВС ИС актуальными являются рассмотренные в диссертации вопросы.

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

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

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

Научную новизну представляют следующие результаты: классификационный граф структур звездообразных ЛВС, обеспечивающий описание альтернативных вариантов построения локальной вычислительной сети на базе концентраторов и коммутаторов; новые математические модели оптимизации структур однородных звездообразных ЛВС, позволяющие конструировать структуру сети с учетом взаимного расположения рабочих станций, наличия возможных мест размещения АО, а также требований ИС к пропускной способности; новые математические модели оптимизации структур неоднородных звездообразных ЛВС, позволяющие синтезировать структуру вычислительной сети с учетом возможности совместного использования коммутаторов и концентраторов рабочих групп, взаимного расположения рабочих станций, наличия возможных мест размещения АО, а также требований ИС к пропускной способности; оригинальные алгоритмы оптимизации топологической структуры однородных звездообразных ЛВС по критерию минимума затрат на создание сети, при обеспечении требуемой пропускной способности и структурных ограничений, на основе методов ветвей и границ и венгерского метода, позволяющие учитывать особенности поставленных задач; оригинальный генетический алгоритм синтеза топологической структуры неоднородных ЛВС по критерию минимума затрат. Основные положения, выносимые на защиту: классификационный граф структур звездообразных ЛВС на базе концентраторов и коммутаторов; формализованная постановка обобщенной задачи оптимизации структур ЛВС ИС; математические модели оптимизации топологической структуры однородных звездообразных ЛВС ИС; математические модели оптимизации топологической структуры неоднородных звездообразных ЛВС ИС; алгоритмы оптимизации топологической структуры однородных звездообразных ЛВС на базе концентраторов; алгоритмы оптимизации топологической структуры однородных звездообразных ЛВС на базе коммутаторов; алгоритм оптимизации топологической структуры неоднородных звездообразных ЛВС; комплекс программ оптимизации топологической структуры ЛВС ИС и результаты численных экспериментов.

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

Диссертационная работа выполнена в рамках научного направления "Проблемы автоматизации обработки информации в тренажно - обучающих, информационных и управляющих комплексах". Материалы диссертации вошли в отчеты о НИР "Принципы, методы и модели автоматизированного проектирования распределенных специализированных систем обработки информации в среде ЛВС" 37.94 ГР 01.99.0006730 ИН 02.99.0004513, "Методы и модели оптимизации архитектуры и организации функционирования корпоративных информационных систем для образовательных структур" 8.99 ГР 01.2.00010680 ИН 02.2.00005419.

Предложенные математические модели и алгоритмы оптимизации топологической структуры ЛВС ИС использованы в процессе синтеза структуры ЛВС корпоративной информационной системы Шахтинских межрайонных электрических сетей (ШМЭС), разработки вычислительной сети Шахтииского филиала гуманитарного института (ШФ ГИ) г. Москвы, а также в проектно-конструкторской деятельности Центра информационных технологий и дистанционного обучения. Полученные результаты внедрены в учебный процесс ЮРГТУ(НПИ).

Программная реализация алгоритмов оптимизации топологической структуры ЛВС ИС входит в состав САПР "Модель", разработанного в рамках межвузовской программы, в качестве обновленной версии комплекса "Топология".

Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийской научной конференции студентов и аспирантов "Новые информационные технологии. Информационное, программное и аппаратное обеспечение" (Таганрог, 1995г.); Межгосударственных научно-практических конференциях "Экономико -организационные проблемы анализа, проектирования и применения информационных систем" (Ростов-на-Дону, 1997, 1999гг.); Международной конференции "Современные технологии обучения"(Санкт-Петербург, 1998г.); на межвузовской конференции "Пути развития теории и техники связи"(Новочеркасск, 1999г.); на 2-й, 3-й и 4-й Международных конференциях "Новые технологии управления движением технических объектов" (Новочеркасск, 1999-2001гг.); на ежегодных научно-технических конференциях ЮРГТУ(НПИ) в период с 1995-2001гг.

Основные материалы диссертации отражены в 17 печатных работах.

выводы

Для неоднородных ЛВС ИС в соответствии с выделенными классами неоднородных ЛВС разработана оригинальная математическая постановка задачи оптимизации топологической структуры, которая учитывает особенности совместного использования на уровне рабочих групп концентраторов и коммутаторов, взаимное расположение рабочих станций, наличие множества возможных мест для размещения АО, а также характер информационного обмена.

Для решения задачи оптимизации топологической структуры ЛВС ИС предложен и обоснован подход с применением ГА, показаны принципы конструирования хромосом и преобразования ограничений задачи оптимизации для использования в ГА.

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

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

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

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

4.1 Реализация средств оптимизации топологической структуры ЛВС ИС в САПР "Модель"

Разработанные в диссертационной работе модели и алгоритмы оптимизации топологической структуры звездообразных ЛВС ИС составляют основу алгоритмического базиса программного комплекса оптимизации топологической структуры ЛВС (КОТС ЛВС). Комплекс является функционально самостоятельным продуктом и может быть использован в качестве составной части САПР "Модель" как обновленный вариант подсистемы "Топология".

Система автоматизированного проектирования "Модель" предназначена для проектирования, анализа и оптимизации информационных систем на базе ЛВС. В основе архитектуры системы лежит компонентная структура. САПР "Модель" включает следующие подсистемы: подсистема организации и ведения диалога; подсистема ведения баз данных; подсистема обработки правил; подсистема управления вводом-выводом; подсистема создания и поддержки файлов данных; комплекс "Моделирование"; комплекс "КОТС". Обобщенная структурная схема САПР "Модель" приведена на рис.4.1.

БД "обобщение структурные характеристики моделей"

БД "копжественные ха рактеристмки пользователей, вьнис пигелыъис ассоциаций, предметной области"

БД "хараетеристжи стаедартшх ЛВС"

БД "характеристики сетевых ОС"

БД "характеристиси рабочих станций"

БД "характеристики активного оборудования и каналов cB»tf

БД "характериспки раалюованшс ЛВС"

БД "характеристики текущей модели ЛВС

Функциональная структура САПР "МОДЕЛЬ"

Комплекс "Моделирование" организация и ведение диалога ведение БД у обработки правил управление вводом - выводом создание и поддержка файлов данных мдигационная модель ИС на базе ЛВС

Одноран говая

Файл Сервер сервер БД

ЗАКЛЮЧЕНИЕ

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

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

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

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

Задача построения топологической структуры однородных ЛВС на базе коммутаторов представлена в виде задачи о распределении множества работ по приборам при минимаксном критерии; решение данной задачи позволяет определить топологию ЛВС на базе коммутаторов при минимизации нагрузки с учетом внутрисегментной и межсегментной нагрузки.

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

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

Разработан программный комплекс проектирования топологической структуры звездообразных ЛВС в составе САПР "МОДЕЛЬ", реализующий полученные алгоритмы. Применение комплекса позволяет конструировать структуры звездообразных ЛВС, обеспечивая сокращение затрат на создание сети до 20 %.

При помощи разработанного программного комплекса получены варианты структур корпоративной информационной системы ШМЭС и ШФ ГИ на базе неоднородных ЛВС.

1. Алгоритм решения задачи о размещения концентраторов.-(Экспресс-информация / ГосИНТИ. Передача информации; N46).M., 1977, с40-48.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации -М. :Наука, 1987-248с.

3. Алиев Р.А., Абдулаев Р.В Гибридная экспертная система для проектирования технологической базы распределенной системы обработки данных «Экспетр-сеть» /.//УСиМ,-1991-N1. с.79-84

4. Бобер В.И., Янбых Г.Ф. «Комплексная оптимизация размещения вычислительных центров и межцентровой сети передачи данных». АВТ, 1981, №5. С.3-7.

5. Богуславский Л.Б., Дрожжинов В.И. Основы построения вычислительных сетей для автоматизированных систем.-М.: Энергоатомиздат, 1990.-256с.

6. Буч Г. Объектно-ориентированное проектирование с примерами применения: Пер. с англ.-М.:Конкорд, 1992.-512с.

7. Верма, Преймоуд К. Сети связи ЭВМ. Оценка эффективности функционирования: Структурный анализ. М.:Радио и связь, 1992.-112с.

8. Вишневский В.М., Ляхов А.И. Оценка пропускной способности локальной беспроводной сети при высоких нагрузках и помехах // Автоматика и телемеханика. 2001. №8.

9. Воробьев С.П. Модели оптимизации топологии распределенных систем обработка информации на базе ЛВС. //Автореферат диссертации на соискание ученой степени канд. техн. наук. Новочеркасск 1994.

10. Ю.Гальперович Д.Я., Яшнев Ю.В. Высокоскоростные кабельные системы для компьютерных сетей.-M.:SPSL "Русская панорама", 1999.-128с.

11. П.Гольц Г. Рабочие станции и информационные сети.-М. Машиностроение, 1990.-240с.

12. Гроппен В.О., Мирошников А.С. Управление системой оптимальной параллельной обработки информации в ЛВС: модели, алгоритмы, интерфейс // Автоматика и телемеханика. 2001. №6.

13. Гузик В.Ф, Решетняк В.Н. "Система NET PRO как инструментальное средство проектирования топологии распределенных вычислительных сетей", "УсиМ" №1/2 1995г, 44-49

14. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. Мир. 1982. (ЗОП)

15. Захаров Г.П., Лохмотко В.В. «Модель оптимизации структуры больших информационно-вычислительных сетей». АВТ, 1985, №3. С.19

16. Ирбенек B.C., Келенин К.В. Алгоритмы решения задачи о назначениях и их применение. Программные продукты и системы. 1999, №1.

17. Исаев С.А. Разработка и исследование генетических алгоритмов для принятия решений на основе многокритериальных нелинейных моделей.//Автореферат диссертации на соискание ученой степени канд. техн. наук. Н.Новгород 2000.

18. Калмычков А.И. «Сравнительный анализ алгоритмов топологического проектирования иерархических сетей связи». АВТ, 1989, №5. С.51-57.

19. Коллинз Г, Блэй Дж. Структурные методы разработки систем от стратегического планирования до тестирования, архитектура / Пер. с англ.;-М.:Финансы и статистика. 1986 248с.

20. Кристофидес Н. Теория графов. Алгоритмический подход.-М.:Мир, 1978, с.432.

21. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска // Автоматика и телемеханика, 2001г., N10.

22. Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы // Изв. РАН. Теория и системы управления, 1999, N1.

23. Мартин Дж. Вычислительные сети и распределенная обработка данных: программное обеспечение, методы и архитектура / Пер. с англ.;-М.-.Финансы и статистика. 1985 256с.

24. Мартин Дж. Планирование развития автоматизированных систем / Пер. с англ.;-М.:Финансы и статистика. 1984 264с.

25. Мизин И.А., Богатырев В.А., Кулешов А.П. «Сети коммутации пакетов». М.: Радио и связь, 1986.- 407 с.

26. Минкин Ю. И., Петров А.И. Самоорганизующийся генетический алгоритм // Изв. РАН. Теория и системы управления, 2001, N3.

27. Монтлевич В.М. Задача размещения предприятий с типовыми мощностями и неделимыми потребителями // ЖВМиМФ, 2000,Т40, №10. С1491-1507.

28. Назаров С.В., Ашихин Н.В., Луговец А.В. Локальные вычислительные сети: Справочник. В 3-х ч. Кн.З: Организация функционирования, эффективность, оптимизация,—М.:Фин и статистика, 1995.-248с.

29. Нанс Б. Компьютерные сети. М.:Бином, 1996.-400с.

30. Норенков И.П. Трудношин В.А. Телекоммуникационные технологии и сети.М:МГУ, 1998.-232с.

31. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: пер. с англ.- М.: Мир, 1985.- 512 с.

32. Позин Л.Л., Шербо В.К. Телеобработка данных в автоматизированных системах.- М.,Статистика, 1976.-180с.

33. Принципы, методы и модели автоматизированного проектирования распределенных специализированных систем обработки информации в среде ЛВС. Отчет о научно исследовательской работе. N гос. Per. -01990006730. Шифр темы 37.94.-Новочеркасск, 1998.

34. Ракитянская А.Б., Ротштейн А.П. Генетический алгоритм диагностики на основе нечетких отношений // Изв. РАН. Теория и системы управления, 2001, N5.

35. Растригин Л. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3-16.

36. Рубинштейн М.И. Алгоритм решения минимаксной задачи о назначении со слабо заполненной прямоугольной исходной матрицей // АиТ.1986.№1.с.81-89.

37. Рубинштейн М.И. Оптимальная группировка взаимосвязанных объектов. М.:Наука, 1989, с. 168.

38. Семенюта А.Н. Планирование развития первичных сетей связи на основе генетического алгоритма// АиТ, №1 2002г. с.67-75.

39. Сергеев С.И. Квадратичная задача назначения. Новые нижние границы в схеме парного назначения.//АиТ, 1999, №8, с127-143.

40. Сергеев С.И. Квадратичная задача назначения. Улучшенный алгоритм Гилмора-Лоулера//АиТ, 1999, №8, с127-143.

41. Скибенко И.Т, Кулик Ю.А. "Система автоматизированного проектирования структуры распределенных сетей передачи данных", "УсиМ" №4/5 1994г, с.73-78.

42. Тищенко Н.М. Введение в проектирование систем управления.-М.: Финансы и статистика, 1986 248с.

43. Халсалл Ф. Передача данных, сети компьютеров и взаимосвязь открытых систем: М.: Радио и связь, 1995.-407с.49.Холл. Комбинаторика

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

45. Хубаев Г.Н., Щербаков С.М., Латыпов P.P. Система имитационного моделирования временных параметров информационной системы//Материалы научных чтений Ростов н/Д.:1999.

46. Черноморов Г.А., Скоба А.Н. Модель оптимального размещения распределенной базы данных в локальных вычислительных сетях при внедрении интегрированных информационных систем на предприятиях. //Изв. Вузов. Электромеханика, 1991, N 7.С.52-60.

47. Черноморов Г.А., Шестаков С.А. Применение задачи о покрытии для оптимизации топологии локальной вычислительной сети. Экономика.Бизнес.Право: Межвуз. сб. науч. тр./Институт открытого образования.-Новочеркасск, ЮРГТУ, 2001. С.9-13.

48. Шаймарданов Р.Б. Моделирование и автоматизация проектирования структур баз данных /М. Радио и связь, 1984.-120с.

49. Шаффер Дж. Д., Эшельман Л.Дж. Комбинаторная оптимизация с использованием генетического алгоритма/Юбозрение прикладной и промышленной математики. 1996, Т.З, № 5.

50. Шестаков С.А. Анализ существующих методов и алгоритмов оптимизации топологии распределенных систем обработки данных на базе вычислительных сетей /Новочерк. гос.техн.ун-т.- Новочеркасск, 1998.-26с. Деп. в ВИНИТИ 17.08.98, №2592-В98.

51. Шестаков С.А. Сегментация коммутируемых локальных вычислительных сетей информационных систем. Новые технологии управления движением технических объектов: Материалы 3-й Междунар. науч.-техн. конф. /Ростов-на-Дону. изд. СКНЦ ВШ 2000.-Т4.-С.32-35.

52. Шестаков С.А., Воробьев С.П. Вопросы проектирования топологической структуры современных распределенных обучающих систем // Современные технологии обучения: Материалы междунар. конф. 16 апр. 1998г. Санкт-Петербург:СПбГЭУ,.-С.188-189.

53. Щербаков С.М. Исследование информационной системы деканата Вуза.// Организационно-экономические проблемы проектирования и применения информационных систем: // Материалы III Межгосударственной научно-практической конференции -Ростов н/Д: РГЭА, 1998.

54. Эттингер Б.Я.,.Янбых Г.Ф «Оптимизация структуры сети телеобработки данных с явными ограничениями на время реакции». АВТ. 1979, 4. С.63-69.

55. Янбых Г.Ф. «Применение метода ветвей и границ топологической оптимизации сети телеобработки данных при ограничении на время реакции». АВТ, 1980, №5. С.3-7.

56. Янбых Г.Ф. «Выбор комплектации вычислительных комплексов и пропускных способностей линий связи в информационно-вычислительных сетях с распределенной базой данных».АВТ, 1989, №2, С.3-9.

57. Янбых Г.Ф. «Оптимизация размещения вычислительных комплексов, программ и файлов в сети ЭВМ». АВТ, 1984, №5. С. 14-20.

58. Янбых Г.Ф. «Оптимизация размещения телеконцентраторов информации в централизованной сети передачи данных с учетом надежности каналов связи». АВТ, 1986, №4. С. 10-19.

59. Янбых Г.Ф., Столяров Б.А. «Оптимизация многоярусной централизованной сети передачи информации». АВТ, 1974, №6. С.49-54.

60. Bahl L.,Tang D. Optimization of concentrator locations in teleprocessing networks.- In Proc.: Symposium on Computer-Communication Networks and Teletraffic. Polytechnic Institute of Brooklyn. New York, 1972.

61. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

62. Coad P., Yourdon E. Object-Oriented Analysis, 2nd Ed. Englewood Cliffs, NJ : Prentice Hall, 1991.

63. DeMarco, T. Strustured Analysis and System Specification. Englewood Cliffs, NJ: Prentice-Hall., 1979.

64. Dysart H. G., Jeorganas N.D. NewClust An Algorhytm for the Topological Design of Two-Level Multidrop Teleprocessing Networks.-IEEE Trans. On Communications, 1978, vol. Com-26, Nol 1

65. Gane, C., Sarson, T. Structured System Analysis. Englewood Cliffs, NJ: Prentice-Hall., 1979.185

66. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

67. Muhlenbien H. How genetic algorithms really work: I mutation and Hillclimbing // Parallel Problem Solving from Nature N2. R.Manner Manderick, eds North Holland.

68. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der Biologischen Information, Freiburg: Fromman, 1973.

69. S. Haykin, Neural Networks: A Comprehensive Foundation, MacMillan College Publishing Co., New York, 1994.

70. Schwefel H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.

71. Shlaer, S., Mellor, S. Object-Oriented Systems Analysis: Modeling the World in Data. Englewood Cliffs, NJ: Prentice-Hall., 1988

72. Smith, M., Tockey, S. An Integrated Approach to Software Requirements Definition Using Objects. Seattle, WA: Boeing Commercial Airplane Support Division, pi33,1988.

73. Ward, P., Mellor, S. Structured Development for Real-time Systems. Englewood Cliffs, NJ: Prentice-Hall., 1985

74. Yordon, E. Modern Structured Analysis. Englewood Cliffs, NJ: Prentice-Hall., 1989.1. ГУП РО «ДОНЭНЕРГО»

75. Филиал государственного ШАХТИНСКИЕ МЕЖРАЙОННЫЕ ЭЛЕКТРИЧЕСКИЕ СЕТИунитарного предприятия Ростовской области1. УТВЕРЖДАЮ1«

76. Битюцкий Б.И., начальник отдела ИТО ШМЭС

77. Технических предложений по реализации топологической структуры ЛВС рабочих групп ШМЭС на базе концентраторов и коммутаторов.

78. Методик расчета и оптимизации топологической структуры коммутируемых ЛВС по критерию минимума нагрузки для корпоративной информационной системы ШМЭС.

79. Моделей и алгоритмов оптимизации топологической структуры ЛВС применительно к корпоративной информационной системе ШМЭС на базе однородных и неоднородных ЛВС по критерию минимума затрат.

80. Рекомендаций по выбору активного оборудования для реализации топологической структуры ЛВС.

81. JHOy Гуманитарный Институт Зхтинский филиал)1. А.Н.Коротенко " 2001г.1. Акто внедрении результатов диссертационной работы Шестакова С.А. при разработке и проектировании локальной вычислительной сети ННОУ ГИ г.Москва (Шахтинский филиал)

82. Красовский М.Ю., директор ЦИТиДО,

83. Технических предложений по реализации топологической структуры ЛВС рабочих групп на базе концентраторов и коммутаторов.

84. Методик расчета и оптимизации топологической структуры коммутируемых ЛВС. по критерию минимума нагрузки.

85. Моделей и алгоритмов оптимизации топологической структуры ЛВС на базе неоднородных ЛВС по критерию минимума затрат.

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

87. Рекомендаций по выбору коммутаторов и концентраторов в качестве активного оборудования для реализации топологической структуры ЛВС.

88. Использование указанных результатов позволяет: повысить качество проектирования топологической структуры ЛВС; сократить затраты на создание вычислительной сети и проведение проекгно-конструкгорских работ.

89. Полученные результаты положены в основу организации корпоративной вычислительной сети ЮРГТУ(НПИ).

90. Директор ЦИТиДО Зам. директора ЦИТиДО1. Нач. отдела ЦИТиДО

91. Красовский М.Ю. Купаев В.М.1. Геймал Л А.

92. ЮЖНО-РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (НОВОЧЕРКАССКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ)1. УТВЕРЖДАЮ

93. Проректор по информатизации и1. АКТо внедрении результатов диссертационной работы Шестакова Сергея Александровича в учебный процесс.

94. Спецификация Проект создания ЛВС ИСГИ

95. Артикул Наименование товара Ед. изм Кол-во Цена, $ Сумма, $

96. Активное сетевое оборудование j 2 888,38

97. ЗС16464А SuperStack II Baseline 10/100 Switch 12 port шт 1 461,13 461,13

98. ЗС16441 SuperStack II Baseline Hub 24 шт 1 228,63 228,63

99. ЗС16440 SuperStack II Baseline Hub 12 шт 1 151,13 151,133C905B-TX-NM Fast EthcrLink XL PCI 10/100 TX NM шт 39 52,50 2 047,50

100. Источники бесперебойного питания 1 674,55

101. SU700RMI2U Smart-UPS 700 2U rack mount, 2U| in height , improved voltageprr regulation J 1 411,95 411,95

102. SU3000INET Smart-UPS 3000 |шт 1 1 262,60 1 262,60

103. Серверы и рабочие станции 35 065,44

104. QEW- 1G6670261091NINN Aquarius Server PP201 133 шт 4 1 637,28 6 549,12

105. CPU Intel Pentium III 667Mhz/256K/133MHz cache шт -4 94,50 -378,00

106. CPU Intel Pentium III 800Mhz/256K cache шт 4 192,78 771,12

107. CPU Intel Pentium П1 800Mhz/256K/133MHz cache шт 4 129,60 518,40

108. DIMM 256 Mb SDRAM ECC 100 MHz шт 12 97,20 1 166,40

109. HDD 36.4 Gb U160 SCSI 10 krpm SCA шт 16 425,52 6 808,32

110. Monitor 15 Monitor 15 LITE-ON TC095 шт 39 162,00 6 318,00

111. RAID card Mylex AcceleRAID 170 32Mb шт 4 965,52 3 862,08

112. QSI-C600064100-FNNS2 Aquarius Std MC600 (С600/64/VINT/H10/KM-SB) шт 35 270,00 9 450,00

113. Программное обеспечение 22 888,45

114. CI 1-00207 Windows Svr 2000 Russian Disk Kit CD w/Boot Disks шт 1 33,52 33,52

115. CI 1-00206 Windows Svr 2000 Russian DocKit шт 1 16,05 16,05

116. CI 1-00505 Windows Svr 2000 Russian OLP В шт 4 644,81 2 579,24

117. C78-00351 Windows CAL 2000 Russian OLP В шт 35 26,57 929,95

118. Пассивное сетевое оборудование 3 051,0027.1B.481.B100G 19" Patch Panel, 48xRJ45, KATT/HD, 568B, UTP. PowerCat, 1U, Graphite шт 1 305,75 305,75

119. A013G 19" Ring Run (Jumper) Panel, 2U, Graphite шт 1 32,20 32,20

120. A017G 19" Ring Run (Jumper) Panel, 1U, Graphite шт 3 23,49 70,47

121. NCT1050 Trunking 100x50 м 33 9,88 326,04

122. YT4 Mini trunking 40x25 м 230 2,09 480,70

123. RAA-00076 19"MODBOX II Wall Mount Cabinet 14U, 500 mm Deep шт 1 404Д 4 404,141. ИТОГО 65 567,81^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^jg ^ ^ ^ ^ ^jg ^ ^ ^ ^ ^jg ^ ^ ^ ^ ^jg ^ ^ ^ ^ ^ ^ .mj^f ^

124. Основные модули КОТС (Delphi 5.0)sjs э|с sfc sjc sjs sjs sjs sjs sjc #|c #|c #|c «|c sjs s$c sjs )|c $ sjs $ $ * sjs $ $ $ s|j * sjs )|c He ^ ^jj ^ s^ ^ ^unit Unit 1;interfaceuses

125. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

126. DBCtrls, Db, DBTables, StdCtrls, ExtCtrls, Menus, Buttons; type

127. Private declarations } public

128. Public declarations } end; coord=record X:integer; Y:integer; end;var

129. Forml: TForml; TypeOflmage: integer; CoordX,CoordY: Integer;

130. CurrentImage:TImage; // My def for Image 2 be created1. BmAO:TBitmap; // My21. Flag:boolean;

131. Settings for project++-H--H-++++++++! KodP:byte; // Kode of LAN project

132. ScaleP:integer; // Scaling FNPlan:string; NP: string;

133. NumberWS: integer; //Count of added stantions CountPlace:integer; // .of Places MatrL: array of array of real; //Матрица расстояний PathName: string;

134. OpenDialogl.Filter := 'Bitmap files (*.bmp)|*.bmp'; If NOT OpenDialog 1 .Execute Then FNPlan:-PlanBlank.bmp';;

135. FNPlan:=OpenDialogl .FileName;1. Form2.show;1. Form2.SetFocus;

136. Form2. TblPlan. Active :=True;1. Form2.TblPlan.insert;

137. NumberWS :=NumberWS+1; if NumberWS > 1 Then TblWS.insert; Currentlmage := Image4; TblWS.Active:=True;

138. Add To DB Stantions (CountWS,CoordX,CoordY) TblWS.Edit;

139. TblWs.FieldByName('KodP').Value:=NP; TblWs.FieldByNameCNWsivalue-Numbe^WS; TblWs.FieldByName('X,).Value:=CoordX; TblWs.FieldByName('Y).Value:=CoordY; ТЫ WS.Post; End; 2: Begin

140. Currentlmage := Image2; CountPlace:=CountPlace+1; if CountPlace > 1 Then TblPlaces.insert; TblPlaces.Active:=True; TblPlaces.Edit;

141. TblPlaces.FieldByName('KodP').Value:=NP;

142. TblPlaces.FieldByNameC'NPlace^.Value.-Coun^Place;

143. TblPlaces.FieldByName('X').Value:=CoordX;

144. TblPlaces.FieldByNameCY^.Value^CoordY; TblPlaces.FieldByName('InUse').Value:=False; TblPlaces.Post; End; 3: Begin

145. Currentlmage := Image 1; //Forml .Cursor:=crDefault; End; 4: Begin

146. Currentlmage := Image3; //Forml. Cursor ~crDefault; End; end;if TypeOflmage > 0 Then Canvas.Draw(CoordX,CoordY+ImagePlan.Top, Currentlmage.Picture.BitMap); end;procedure TForml .FormCreate(Sender: TObject); begin

147. Forml .Panel 1 .Visible:=False;1. TypeOflmage := 0;end;procedure TForml.ImagePlanMouseUp(Sender: TObject; Button: TMouseButton;

148. Shift: TShiftState; X, Y: Integer); begin

149. CoordX:=X; CoordY:=Y; end;procedure TForml.Image2Click(Sender: TObject); begin

150. TypeOflmage := 2; Image4.Visible:=True; Image 1 .Visible:=True; Image2.Visible:=False; Image3. Visible:=True; Forml .Cursor:=crDrag; end;procedure TForml.ImagelClick(Sender: TObject); begin

151. TypeOflmage := 3; Image4.Visible:=True; Image 1 .Visible :=False; Image2.Visible:=True; Image3. Visible:=True;

152. Forml .Cursor:=crDrag; end;procedure TForml.Image3Click(Sender: TObject); begin

153. TypeOflmage := 4; Image4.Visible:=True; Image 1 .Visible:=True; Image2.Visible:=True; Image3Visible.-False; Forml. Cursor:=crDrag; end;procedure TForml.BitBtnlClick(Sender: TObject); begin

154. OpenDialog 1 .Execute; //FNPlan:=OpenDialog 1 .FileName; end;procedure TForml .N7Click(Sender: TObject); // Open project begin1. Form2.show;1. Form2.SetFocus;

155. Form2 .TblPlan .Active :=True;end;1. Procedure ShowPlan; begin

156. Forml .Panel 1 .visible.-True;

157. Forml.ImagePlan.Picture.Bitmap.LoadFromFile(FNPlan);

158. Forml .ImagePlan.Visible:=True;

159. Forml .Image4.Visible:=True;

160. Forml .Image 1. Visible:=True;

161. Forml .Image2.Visible::=True;

162. Forml .Image3.Visible:=True;1. NumberJWS :=0;1. CountPlace:=0;1. Flag:=False;

163. Forml .Button 1 .Visible:=False; Forml .Button 1 .Enabled:=False; Forml .Button2.Visible:=False; Forml .Button2.Enabled:=False; // Draw Stantions button Forml .TblWS .Active :=TRUE; Forml.ТЫ WS.First; While Not Forml .TblWS.EOF do begin

164. Forml .TblWS.FieldByName('KodP').AsString=NP Then

165. Flag:=True; // В базе есть станции Forml .TblWS .Next; end;1. Flag then begin

166. Forml.Buttonl.Enabled :=True; Forml.Button 1.Visible :=True; end; Flag:=False; // Draw Places Button Forml .TblPlaces.Active:=TRUE; Forml .TblPlaces.First; While Not Forml .TblPlaces.EOF do begin

167. Forml .TblPlaces.FieldByName(,KodP').AsString=NP Then

168. Flag:=True; If Flag then begin

169. Forml .Button2.Enabled :=True; Forml.Button2.Visible := True; end;

170. Val(NP,i,j); If i<l then begin

171. MessageDlg('OTKpoirre проект', mtlnformation, mbOK., 0);exit;end;1. CountPlace <1 then begin

172. MessageDlg('3aflafiTe места активного оборудования', mtlnformation, mbOK., 0); exit; end;

173. SetLength(MatrL,NumberWS,CountPlace); Tbl WS. Active:=True; ТЫ Ws. First; TblPlaces.Active:=True; TblPlaces.First; i:=0; J~0;

174. While Not TblWS.Eof do beginif TblWS.FieldByName('KodP').AsString = NP Then begin

175. XI :=TblWs.FieldByName('X').AsInteger; Yl:=TblWs.FieldByName('Y').AsInteger; While Not TblPlaces.Eof do beginif TblPlaces.FieldByName('KodP').AsString = NP Then begin

176. X2:=TblPlaces.FieldByName('X').AsInteger; Y2:=TblPlaces.FieldByName('Y').AsInteger; MatrL i j . abs(X2-X 1 )+abs( Y2-Y1); j:=j+l; end;

177. TblPlaces.Next; //j:=0; end; //while Tblplaces j:=0;i:=i+l; end;

178. ТЫ WS .Next; TblPlaces.First; end;

179. MessageDlg('MaTpima расстояний сформирована',mtlnformation, mbOK., 0); If MessageDlg('CoxpaHHTb в файл?mtConfirmation, mbOK, mbNo., 0) = mrOk Then begin

180. SaveDialogl .Execute; AssignFile(Fl, SaveDialogl.Filename); Rewrite(Fl);

181. Writeln(Fl,' ТОПОЛОГИЯ ');

182. Writeln(F 1 /Матрица расстояний Forml .Lobject.caption);1. For i:=0 to NumberWS-l dobegin

183. For j:=0 to CountPlace-l do write(Fl, matrLi,j.:8:2); writeln(Fl); end;1. CloseFile(Fl); end; end;procedure TForml.N18Click(Sender: TObject);var ij:integer;begin

184. Input Traffic here: Val(NP,i,j); Ifi<l then begin

185. MessageDlg('OTKpofiTe проект', mtlnformation, mbOK., 0);exit;end;1. Form3.Show;1. Form3.SetFocus;end;procedure TForml.ButtonlClick(Sender: TObject); begin

186. Show Stantions Forml .ТЫWS. Active:=TRUE; Forml.TblWS.First; Forml .ImagePlan.Canvas.Font.Size:=2; Form 1 .ImagePlan. Canvas.Brush. Style :=bsClear; Forml .ImagePlan.Canvas.Font.Color:=clRed; // Forml .ImagePlan.Canvas.Font.Style:=fsBold.;

187. While Not Forml .TblWS.EOF do begin

188. Forml .TblWS.FieldByName('KodP,).AsString=NP Then With Forml.TblWs do begin

189. CoordX.—FieldByNameCX^.AsInteger; CoordY—FieldByNameCY^.AsInteger; NumberWS:=FieldByName('NWS').AsInteger; Form 1 .ImagePlan.Canvas.Draw(CoordX,CoordY,

190. Forml .Image4.Picture.BitMap); Form 1 .ImagePlan.Canvas.TextOut(CoordX,CoordY+2(), intToStr(NumberWS));end;

191. Forml.TblWS.Next; end; end;procedure TForml.Button2Click(Sender: TObject); begin

192. Draw Places from DB Forml .TblPlaces.Active:=TRUE; Forml .TblPlaces.First;

193. Forml.ImagePlan.Canvas.Font.Color:=clBlue; While Not Forml .TblPlaces.EOF do begin

194. With Forml .TblPlaces do If FieldByName('KodP').AsString=NP Then begin

195. CoordX-FieldByNameCXO-AsInteger; CoordY:=FieldByName('Y').AsInteger; CountPlace:=FieldByName('NPlace').AsInteger; Forml.ImagePlan.Canvas.Draw(CoordX,CoordY,

196. Forml .Image2.Picture.BitMap); Forml.ImagePlan.Canvas.TextOut(CoordX+2,CoordY+2, intToStr(CountPlace));end;

197. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

198. Grids, DBGrids, Db, DBTables, StdCtrls, Buttons, ExtCtrls, Mask, DBCtrls; type

199. Private declarations } public

200. Public declarations } end; var

201. Foim2: TForm2; implementation uses Unit 1; {$R *.DFM}procedure TForm2.BitBtnlClick(Sender: TObject); begin1. TblPlan. Active:=True;1. TblPlan.Insert;1. TblCurPlan.Active:=True;

202. TblCurPlan.RecordCount > 0 Then TblCurPlan.Delete; TblCurPlan.Insert;

203. TblCurPlan.FieldByNameCKodP').AsString :=

204. TblPlan.FieldByNameOKodP').AsString;

205. TblCurPlan.FieldByName('NamePlan*).AsString :=

206. TblPlan.FieldByName(WamePlari).AsString;

207. TblCurPlan.FieldByName('FNPlan').AsString :=

208. Forml.LObject.Caption:=TblCurPlan.FieldByName('NamePlan').Asstring;1. TblCurPlan.Post;1. Self.Close;1. ShowPlan;end;end.unitUnit5;interfaceuses

209. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

210. StdCtrls, Grids, DBGrids, Db, DBTables; type

211. TForm5 = class(TForm) DataSourcel: TDataSource; Table 1: TTable; DBGridl: TDBGrid; Label 1: TLabel; Button 1: TButton; DBGrid2: TDBGrid; Label2: TLabel;procedure ButtonlClick(Sender: TObject); private

212. Private declarations } public

213. Public declarations} end; var

214. Form5: TForm5; implementation {$R *.DFM}procedure TForm5.ButtonlClick(Sender: TObject);beginself.close;end; end.unit UnitGA;interfaceuses

215. Windows, Messages, Syslltils, Classes, Graphics, Controls, Forms, Dialogs,

216. Unitl, Unit5, StdCtrls, ExtCtrls, Buttons, Gauges ; type

217. Private declarations } public

218. Public declarations } end;

219. Hromosom = record Gamma : array of array of boolean; //гены гамма Beta : array of boolean; //ген вета

220. Delta : array of boolean; //ген дельта

221. CF : longint; //целевая функция

222. D : longint; //нарушение ограниченийend; var1. FormGA: TForm4;1. HnHromosom; //Хромосома

223. Popul: array of Hromosom; //Популяция Nhromosom:integer; //Размер нач популяцииff:textfile;

224. Начальная популяция Klstr 1: array of Hromosom; // Кластер 1 Klstr2: array of Hromosom; // Кластер 1 Klstr3 :array of Hromosom; // Кластер 1

225. BestKl,BestK2,BestK3:integer; // Номера лучших особей вкластерах

226. NHromPopul:integer = 20; // Размер популяции(ТЧ хромосом) N Oper Kros :integer =5000; // Количество операций1. Кроссинговерав кластере на 1 этапе P mutrreal = 0.6; // вероятность точечной мутации

227. Ngenom:=Random(CountPlace+2); // номер гена if Ngenom < CountPlace then begin

228. Npos:=Random(NumberWS); // номер позициии no m (Gamma) Hr.GammaNgenom,Npos.:= not Hr.Gamma[Ngenom,Npos]; endelsebegin

229. Npos:=Random(CountPlace); // номер позициии по n if Npos = CountPlace then

230. Hr.BetaNpos.:= not Hr.Beta[Npos]; if Npos = CountPlace+l then

231. CI входит if Cl.D<bad.D then

232. MovHromosom(Cl ,bad); if (Cl.D=bad.D) and (C1.D=0) then if Cl.CF < bad.CF then MovHromosom(C 1 ,bad);end else1. C2 входит beginif C2.D<bad.D then

233. MovHromosom(C2,bad); if (C2.D=bad.D) and (C2.D=0) then if C2.CF < bad.CF then MovHromosom(C2,bad);end elseif Cl.D < C2.D then //CI входит beginif Cl.D<bad.D then

234. MovHromosom(C 1 ,bad); if (Cl.D=bad.D) and (C1.D=0) then if С1 .CF < bad.CF then MovHromosom(C 1 ,bad);end else begin

235. C2 входит if C2.D<bad.D then

236. MovHromosom(C2,bad); if (C2.D=bad.D) and (C2.D=0) then if C2.CF < bad.CF then MovHromosom(C2,bad);end;end;

237. Cut:array of integer; begin

238. Setlength(Cut,NumberWS+2);for i:=0 to CountPlace-l do // Определим точки

239. Cut1.:=Random(NumberWS); // разрыва генов CutCountPlace.:=Random(CountPlace); //в хромосомах

240. CutCountPlace+l.:=Random(CountPlace); //для кроссинговера for j :=0 to CountJPlace-1 do // перебор генов Гаммаbeginfor i:=0 to Cutj-1. do begin

241. Childl.Gammaj,i.:=Parl.Gamma[j,i]; // наследование до Child2.Gamma[j,i]:=Par2.Ganmia[j,i]; // точки разрыва end;for i:=Cutj. to CountJPlace-1 do begin

242. Childl.Gammaj,i.:=Par2.Gamma[j,i]; // обмен после Child2.Gamma[j,i]:=Parl.Gamma[j,i]; // точки разрыва end;if j <= Cutj-1. then // параллельноbegin // перебор генов

243. Childl .Betaj.:=Parl .Beta[j]; // Бета и Дельта -Child2.Beta[j]:=Par2.Beta[j]; // наследование Childl .Delta[j]:=Parl .Delta[j]; // .до точки Child2.Delta[j]:=Par2.Delta[j] end else begin.и обмен после // точки разрыва

244. Childl.Betaj.:=Par2.Beta[j] Child2.BetaD']:=Parl.Beta[j] Childl .Delta[j]:=Par2.Delta[j]; Child2.Delta[j]:=Parl .Delta[j] end end; end;procedure CalcDCF(var HI :Hromosom); var i,j,k,s:integer;

245. Ch,Cs,Cms,Cmh,Cp,Cl,Phub,Psw,Pnih,Pms:integer;dl,d2,d3,d4,d5,d6,d7:integer;1. F,D: Longint;ff:textfile;beginassign (ff,'tl.txt'); rewrite(ff); writeln(ff,* D:'); F:=0;D:=0;

246. Ch:=Form5 .Table 1 .FieldByName('Chub*).AsInteger; Cs:=Form5 .Table 1 .FieldByName('Csw').AsInteger; Cms:=Form5 .Table 1 .FieldByName('Cms').AsInteger; Cmh :=Form5 .Table 1 .FieldByNameCCmh'). Aslnteger; Cp:=Form5 .Table 1 .FieldByName('Cp'). Aslnteger;

247. D:=sqr(NumberWS-d 1); // D = dlA2 writeln(ff,'dl= ',D);d2 ===========d2:=0;dl:=0;for i:= 0 to NumberWS-l do begin dl:=0;for j:=0 to CountPlace-l dodl :=dl+b2i(Hl.Betaj.)*b2i(Hl .Gamma[j,i]);dl :=dl+b2i(Hl .Gammaj,i.);d2:=d2+abs(l-dl);end;

248. Этап1 Создание хромосомы Кластер 1-3 =procedure Klaster(var H:Hromosom;Kl:integer); var i j,k:integer; HrM,HrN:integer; begin1.itHrom(H);1. Init Hromosome

249. For i:= 0 to CountPlace-l dobegin1. H.Beta1.:=False;1. H.Delta1.:=False;

250. For j:= 0 to NumberWS-l do

251. H.Gammai j.:=False; // init Gamma with 0end;1. Gamma

252. H.DeltaRandom(CountPlace). :=True;end; end; end;

253. Этап1 Создание хромосомы Кластер 1-3 =end1. Создание хромосомы =procedure CreateHromosom(var HI :Hromosom);var i,j,k:integer; HrM,HrN:integer; begin1. Init Hromosome

254. For v.= 0 to CountPlace-l dobegin1. Hl.Beta1.-False;1. HI .Delta1.:=False;

255. For j := 0 to NumberWS-l do

256. HI .Gammai,j.:=False; 11 init Gamma with 0end;1. Gamma

257. For i:= 0 to CountPlace-l do begin1. HrM:=Random(NumberWS);1. For k:=0 to HrM dobeginj :=Random(NumberWS);1. HI .Gammai j.:=True;end;end;1. Beta

258. HrN:=Random(CountPlace); For i:=0 to HrN do

259. H1 .BetaRandom(CountPlace). :=True; //Delta

260. HrN:=Random(CountPlace); For i:=0 to HrN do

261. H1 .DeltaRandom(CountPlace).:=True;

262. Procedure WriteHromosom(var Hl:Hromosom; NH:integer);var i,j:integer;begin

263. FormGA.Canvas.TextOut(20,0;Hromosome'+inttostr(NH));

264. For i:= 0 to CountPlace-l dobegin

265. FormGA. Canvas .TextOut(20+NumberWS * 9,15,'Beta'); if Hl.Beta1. then

266. FormGA.Canvas.TextOut(20+NumberWS*9+i*8,30,'r)else FormGA.Canvas.TextOut(20+NumberWS*9+i*8,30;0'); FormGA. Canvas. TextOut(20+NumberWS+NumberWS * 8,55 ,'Delta'); if Hl.Delta1. Then

267. FormGA.Canvas.TextOut(20+NumberWS*9+i*8,70,T)end;1.--II-

268. Создание хромосомы =end = просмотр хромосомы =

269. Else FormGA.Canvas.TextOut(20+NumberWS*9+i*8,70,'0'); For j:= 0 to NumberWS-l do begin

270. FormGA. Canvas. Text0ut(20,l 5/Gamma');ifHl.Gammai,j. Then FormGA.Canvas.TextOut(j+j *8+20,i+i* 10+30/1') Else FormGA.Canvas.TextOut(j+j*8+20,i+i* 10+30/0');end; end;

271. FormG A. Canvas. TextOut(20+NumberWS+NumberWS * 8,85 ,'D:'); FormGA.Canvas.TextOut(40+NumberWS+NumberWS*8,85,inttostr(Hl. D)+' ');

272. Gauge 1 .Visible:=True; Gaugel .Progress:=l ^1. RefreshLambda;===============этап 1 ==1. SaveDialogl .Execute;

273. AssignFile(F 1, SaveDialogl .Filename);1. Rewrite(Fl);setlength(Klstr 1 ,NHromPopul);setlength(Klstr2,NHromPopul);setlength(Klstr3 ,NHromPopul);1.itHrom(Cl);1.itHrom(C2);for i:= 0 to NHromPopul-l do //Генерация кластеров 1 этапа begin

274. Klaster(Klstrl1.,l); //Кл11. CalcDCF(Klstrl 1.);1.estl.Caption:=IntToStr(BestKl);

275. Hrom2File(Klstrl 1.,Fl); // Кл1 в файл1. Klaster(Klstr21.,2);1. CalcDCF(Klstr2 1.);1.est2.Caption:=IntToStr(BestK2);1. Hrom2File(Kistr2 1.,F 1);1. Klaster(Klstr31.,3);1. CalcDCF(Klstr3 1.);1.est3.Caption:=IntToStr(BestK3);1. Hrom2File(Klstr21.,Fl);

276. Gauge 1 .Progress:=Trunc((20/NHromPopul)*i);showmessage('');end;1. Берём кластер 1

277. For i:= 0 to NOperKros-l dobegin11 :=Random(NHromPopul); //Это индексы родителей1.:=Random(NHromPopul);13 :=Random(NHromPopul);

278. FindIParents(Klstr 1,11,12,13 Др 1 ,Ip2,Ibad);

279. Индексы родителей Ip 1 ,Ip2, Уходит Ibad

280. Kros2(KlstrlIpl.,Klstrl[Ip2],Cl,C2);1. CalcDCF(Cl);1. CalcDCF(C2);

281. Select2(Cl,C2,Klstrl Ibad.); // Выбор лучшей из CI и C2 и замена на

282. Ibad, если Ibad хуже. LNKros.Caption:=intToStr(i); Gauge 1 .Progress :=Trunc(20+(20/NOperKros)*i); end;

283. FindBest(Klstr 1 ,BestK 1); // Берём кластер 2

284. Select2(C 1 ,C2,Klstr2Ibad.); // Выбор лучшей из С1 и C2 и замена на

285. Ibad, если Ibad хуже. LNKjros.Caption:=intToStr(i); Gauge 1 .Progress:=Trunc(40+(20/NOperKros)*i); end;

286. Select2(Cl,C2,Klstr3Ibad.); // Выбор лучшей из CI и C2 и замена на

287. Ibad, если Ibad хуже. LNKros.Caption:=intToStr(i); Gauge 1 .Progress:=Trunc(60+(20/NOperKros)*i); end;

288. FindBest(Klstr3 ,BestK3); //++++ Формируем ЭТАП2

289. BestKl.,.BestK2, BestK3 переходят на второй этапif Popul = nil thenbeginsetlength(Popul,NHromPopul); for i;= 0 to NHromPopul-l do begin1.itHrom(Popul 1.); CalcDCF(Populi.) end; RefreshLambda; end;

290. MovHromosom(KlstrlBestKl.,Popul[0]); MovHromosom(Klstr2 [BestK2],Popul[ 1 ]); MovHromosom(Klstr3[BestK3],Popul[2]); for i:=3 to NHromPopul-l do begin

291. Pmutcur:real; PIntrRecmbcur:real; PKrosscur: real; i,nm,nIRec,nKross: integer;

292. Cl,C2:Hromosom; // Хромосомы для кроссинговера и селекции1. 1 Др2,Ibad,11,12,13: integer; // Индексы хромосом для кроссинговераbegin

293. Gaugel .Visible:=True; Gaugel.Progress:=l; InitHrom(Cl); InitHrom(C2); // Берём популяцию nm:=0; nIRec:=0; nKross:=0; For i:~ 0 to NOperKros-l do begin11 :=Random(NHromPopul); //Это индексы родителей1.:=Random(NHromPopul);13 :=Random(NHromPopul);

294. FindIParents(Popul,11,12,13 Др 1 ,Ip2,Ibad);

295. Индексы родителей Ipl,Ip2, Уходит Ibad1. PKrosscur:=random;if PKrosscur < PKross thenbegin

296. Kros2(PopulIp 1 .,Popul[Ip2],C 1 ,C2); CalcDCF(Cl);

297. CalcDCF(C2); nKross:=nKross+1; LNKros.Caption:=intToStr(nKross); end;

298. Pmutcur:=random; 11 мутация if Pmutcur < Pmut then // ? begin //мутируем nm:=nm+l;

299. MutateDot (CI); //Точечная мутация CalcDCF(Cl); LNMut.Caption:=intToStr(nm); end;

300. Select2(Cl,C2,PopulIbad.); //Выбор лучшей из CI и C2 и замена на

301. Ibad, если Ibad хуже. PIntrRecmbcur:=random; // Разыгрываем интерполирующуюрекомбинациюif PIntrRecmbcur < PIntrRecmb then begin // nlrec:=nlrec+l;1.terRecombinate(PopulIpl.,Popul[Ip2],Cl); CalcDCF(Cl);

302. IRec.Caption:=intToStr(nIrec); end;

303. SelectInterRec(PopulIp 1 .,Popul[Ip2],C 1); // Выбор лучшей из CI и C2 и замена на

304. SetLength(Popul,NHromPopul);

305. SetLength(Coord WS ,NumberWS);

306. SetLength(CoordP,CountPlace);for i:=0 to NHromPopul-l do1.itHrom(Popul1.);

307. Randomize; RefreshLambda; //AssignFile(Ff, 'tl.txt'); //rewrite(Ff);for i:=0 to NHromPopul-l do begin

308. Просмотр Популяции end= procedure TForm4.Button5Click(Sender: TObject); vari:integer; Fl:TextFile; begin

309. Сохр популяции в файл SaveDialogl .Execute; AssignFile(F 1, SaveDialogl .Filename); for i:= 0 to NHromPopul-l do Hrom2File(Popul1.,Fl); end;procedure TForm4.Button3Click(Sender: TObject); begin

310. Form6.position:=poScreenCenter; Form6.show; end; end.unit UnitGAShow;nterface uses

311. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

312. Db, DBTables, StdCtrls, UnitGA; type

313. Private declarations } public

314. Public declarations } end; var

315. Form6: TForm6; implementation uses Unit 1; {$R *.DFM}procedure GADrawHrom(var HR1 :Hromosom);var i j :integer;begin1. Clear ALL

316. Form6.Canvas.Brush.Color:=clBtnFace; Form6.Canvas.FillRect(Rect(0,0,500,500));

317. Show Stantions Form6.TWS.Active:=TRUE; Form6.TWS.First; Form6.Canvas.Font.Color:=clRed; While Not Form6.TWS.EOF do begin

318. Form6.TWS.FieldByName('KodP').AsString=NP Then With Form6.TWS do begin

319. CoordX^FieldByNameCXO.AsInteger; CoordY:=FieldByName('Y').AsInteger; NumberWS:=FieldByName('NWS').AsInteger; Form6.Canvas.Draw(CoordX,CoordY,

320. Forml .Image4.Picture.BitMap); Form6.Canvas.Textout(CoordX,CoordY+20,intToStr(NumberWS)); CoordWS NumberWS-1 . .X:=CoordX; CoordWS[NumberWS-l].Y:=CoordY; end;1. Form6.TWS.Next; end;1. Draw Places from DB1. Form6.TPL.Active:=TRUE;1. Form6.TPL.First;

321. Form6. Can vas .Font. Color :=clwhite;

322. While Not Form6.TPL.EOF do begin1. With Form6.TPL do

323. FieldByNameCKodP').AsString=NP Then begin

324. Form 1 ,Image3 .Picture.BitMap) //switchelse

325. Form6 .Canvas.Draw(CoordX,CoordY, Forml .Image 1 .Picture.BitMap); //hub if HR1 .betaCountJPlace-1 .then

326. Form6.Canvas.Font.Color:=clGreen // есть AOelse

327. Form6.Canvas.Moveto(CoordWS1.X,CoordWSi.Y);

328. Form6.Canvas.Lineto(CoordPj.X,CoordP[j].Y);end;

329. Form6.LCF.Caption:=IntToStr(Hrl.CF); Form6.LD.Caption :=IntToStr(Hrl .D); end;procedure TForm6.FormActivate(Sender: TObject); begin

330. GADrawHrom(Popul 0.); end;procedure TForm6.ButtonlClick(Sender: TObject); beginform6.Close; end;procedure TForm6.Button2Click(Sender: TObject); begin

331. GADrawHrom(PopulFormGA.Button4.tag.); end;procedure TForm6.Button3Click(Sender: TObject); begin

332. Form6 .Canvas .Draw(0,0 ,Forml .ImagePlan.Picture .BitMap);

333. GADrawHrom(PopulFormGA.Button4.tag.);end;end.unit UnitTraf;interfaceuses

334. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

335. StdCtrls, ExtCtrls, DBCtrls, Grids, DBGrids, Db, DBTables, Buttons; type

336. Private declarations } publicprocedure RefreshLambda; {Public declarations } end;procedure RefreshLambda; // will use from other units var1. Form3: TForm3;

337. TblTraf: TTable; //Source Table 2 createfor trafic data for plan FNTrafDb: string; // FileName (Traf Table) implementation uses Unitl; {$R *.DFM}procedure RefreshLambda;var i,j:integer;begin

338. SetLength(Lambda,NumberWS,NumberWS);1. TblTraf. Active ."True;1. TblTraf.First;

339. FNTrafDb"PathName+NP+'.db'; FNTrafDB:=NP+'.db'; TblTraf:=Ttable.Create(Form3); TblTraf.DatabaseName := 'LanOpt'; TblTraf.TableName := FNTrafDB; TblTraf.TableType:=ttParadox; TblTraf.FieldDefs.Clear; If Not TblTraf.Exists Then begin

340. TblTraf.FieldDefs.Add('NWS', ftlnteger, 0, false); for i:=l to NumberWS do

341. TblTraf.FieldDefs.Add(intToStr(i), ftlnteger, 0, false); TblTraf.Indexdefs.Clear; TblTraf.Createtable; // Fill with zero ALL WS++++++++++++++++++++++++ TblTraf.Active:=True; For k:=NumberWS downto 1 do begin1. TblTraf.Insert;

342. TblTraf.Fields.FieldByNumber(l).AsInteger:=k;1. TblTraf.Insert;1. For j :=1 to NumberWS do

343. SetLength(Lambda,NumberWS,NumberWS);1. TblTraf.Active:=True;1. TblTraf.First;

344. For i:=0 to NumberWS-l do begin1. For j to NumberWS-1 do1.mbdai,j . TblTraf.Fields.FieldByNumber(j+2). Aslnteger; TblTraf.Next; end;

345. For i:=0 to NumberWS-l do For j:=i to NumberWS-l do Lambdai,j.:=Lambda[j,i];

346. TblTraf.First; TblTraf.Edit;

347. For i:=0 to NumberWS-l do begin1. For j:=0 to NumberWS-l do

348. TblTraf.Fields.FieldByNumber(j+2).AsInteger:=Lambdaij.; TblTraf.Next; TblTraf.Edit; end;

349. MessageDlg('Vfhh', mtlnformation, mbOK., 0); end;procedure TForm3.SpeedButton2Click(Sender: TObject); var

350. Fl:TextFile; i,j:integer; s: string; begin

351. MessageDlg('CoxpaHHTb в файл? mtConfirmation, mbOK, mbNo., 0) = mrOk Then begin1. SaveDialogl .Execute;

352. AssignFile(F 1, SaveDialog 1 .Filename);1. Rewrite(Fl);

353. Writeln(Fl,' ТОПОЛОГИЯ ');

354. Writeln(F 1 /Матрица тяготений ',Forml .Lobject.caption);1. TblTraf. Active :=True;1. TblTraf.First;

355. For i:=0 to NumberWS-1 do begin

356. For j:=0 to NumberWS-1 do begins := IntToStr(TblTraf.Fields.FieldByNumber(j+2).AsInteger); write (Fl,s:4); end;

357. TblTraf.Next; writeln(Fl); end;

358. CloseFile(Fl); end; end; end.

359. Распределение рабочих станций (DOS)

360. Mset = Set of 0.250; PNode ANode; Node = record Z : integer;

361. N : Array 1.MH. of Mset; T : Array [1.MH] of real; Tz : Real; F : Real; Aktive : byte;

362. Next: Array 1.MH. of PNode;1. Back: Pnode; End;var

363. Hub,WS : integer; Function INITNODE : Pnode ; Forward; Function OcenkaI(Z:integer;P:Pnode):real; Forward; Function IfInSet(i:Word;N:Mset): Boolean; Forward; Function SetActive(p:Pnode):Pnode; Forward; Procedure OPT; Forward;

364. Procedure PrintNode(p:Pnode); Var i,j: integer;k,c: String; Begin With рл do Begin1. Writeln('Level = ',Z);1. Write('N=');1. For j:= 1 to Maxhub Do1. Begin1. K:=";1. For i:=l to maxStan do

365. IfInSet(i,Nj.) then Begin Str(i,c); K:=K+' '+c; End; WriteC[',k:7,T); End; Writeln;1. Write ('Т=');1. For i:=l to maxhub Do1. Write(T1.:7:l);1. Writeln;

366. Writeln ('OCEN = *,Tz:5:2); Writeln (' F = ',F:5:2); End; End;

367. Procedure FPrintNode(var F:text;p:Pnode): Var i,j:integer;k,c: String; Begin With рл do Begin

368. Writeln(Fstat,'Level ',Z);1. Write(Fstat,'N=');1. For j:= 1 to Maxhub Do1. Begin1. K:=";

369. For i:=l to max Stan do If IfInSet(i,Nj.) then Begin Str(i,c); K:=K+' '+c; End;

370. Write(Fstat,'',k:7,'.'); End;

371. Writeln(Fstat,"); Write (Fstat,'T='); For i:=l to maxhub Do Write(Fstat,T1.:7:1); Writeln(Fstat,");

372. Writeln('Graphics error:', GraphErrorMsg(ErrCode)); Halt(l); End;end;

373. Procedure ShowLines(P:Pnode); Var i,j: integer;

374. XH,XS,YH,YS:Word; Begin Reset(Fh); Reset(Fc); With Рл Do Begin For i:=l to MaxHub Do Begin1. ReadLn(Fh,XH,YH);1. Reset(Fc);1. SetColor(i);

375. For j:=l to MaxStanDo Begin

376. Readln(Fc,XS,YS); If IfInSetG',N1.) then1.ne(XH, YH,XS, YS); End; End; End; End;

377. Procedure MakeLij; Var i,j: integer;

378. HX,HY,SX,SY:real; Begin Reset(fc); Reset(fh); rewrite(fmatr); For i:=l to Maxstan do Begin

379. Read (fc,sX); Readln(fc,sY); Reset(fh);

380. For j :-l to Maxhub do Begin

381. Read (fh,hX); Readln(fh,hY);1.,j.:=SQRT(SQR(HX-SX)+SQR(HY-SY));write(fmatr,Li,j.: 10:2); End;1. Writeln(fmatr,"); End;close(fmatr); End;

382. Procedure CreateLevel(Var P:Pnode; Var Levekinteger);1. Var i,j:integer;1. BeginwRITELN(LEVEL);} For i:=l to maxhub do Begin

383. PA.Next1.:=InitNode; With PA.Nexti.A do Begin Z:=Level; Baclc:=P;

384. For j:=l to maxhub do begin1. Nj.:=PA.N[j];1. j=i then Nj.:=N[j]+[Level]; T£j]:=PA.T[j]; end;

385. Tz:=OcenkaI(Level,PA.Next1.); If Tz >= OptimA.F Then Tz:=l 00000; NLevels:=NLevels+l; { PrintNode(PA.Nexti.);1. Readln; } End End End;

386. Procedure MakeLfile; Var i:integer; Xl,X2,Yl,Y2:word; a:array 1. .ms. of recordxl,yl:integer; End;1. DX,DY:Real; Begin1. Rewrite(Fr); Reset(fc);

387. Writeln(Fr,MaxStan); For i:=l to MaxStan do Read(fc,a1.Xl,ai.Yl);

388. For i:=l to Maxstan do Begin

389. For J:=1 to MaxStan Do Begin

390. DX:=abs(a1.Xl -aj.X 1); DY:=abs(a[i].Yl-a[j].Yl); Write( fr,sqrt(DX*DX+DY*DY): 10:2); End; Writeln(fr,"); Readln(fc); End; End;

391. Procedure MakeCoordFile(Mx,My:Word);1. Var i: integer;1. Begin1. Rewrite(Fc);1. Randomize;1. Randseed:=SdS;1. For i:=l to MaxStan dobegin

392. Write (Fc,Random(Mx)/'); writeln(Fc,Random(My)); end; End;

393. Procedure MakeCoordHubs(Mx,My:Word)1. Var i:integer;1. Begin1. Rewrite(Fh);1. Randomize;1. Randseed:=SdH;1. For i:=l to MaxHub dobegin

394. Write (Fh,Random(Mx),' *); writeln(Fh,Random(My)); end; End;

395. Procedure ShowPole; Var X,Y,i,j :Word; MaxX,MaxY:Word; Begin

396. For i:=l to Maxstan do Begin1. Read (Fc,X,Y);

397. Putpixel(X,Y,White); Putpixel(X+1, Y+1, White); Putpixel(X+1, Y,'White); Putpixel(X,Y+1, White); End;1. Reset(Fh); readln;

398. For i:=l to Maxhub do Begin1. Read (Fh,X,Y);1. Putpixel(X,Y,Red);1. Putpixel(X+1,Y+1 ,Red);1. Putpixel(X+l,Y,Red);1. Putpixel(X, Y+1 ,Red);1. End;1. End;

399. Procedure CalcTau; Var i,j :integer; Begin For i:= 1 to maxstan do Begin

400. Tau1.:.=1000; For j := 1 to maxhub do If Taui.>L[ij] then Tau[i]:=L[ij]1. End; End;

401. Procedure SortTE; Var Mx:REAL; Begin

402. For i:=l to 5 do Forj:=ito5do If Te(j.<Te1. Then Begin Mx:=Te£j]; Te|j]:=Tei]; Te[i]:=Mx End;1. End;

403. Procedure PrintLevel(p:pnode)1. Var i: integer;begin

404. For i:=l to maxhub do PrintNode(PA.Next1.);end;

405. Procedure Process(var V:integer; var P:PNode); Var i,j-.integer;1. Begin1. Writeln('Process',v);1. Readln;}v:=v+l;

406. For i:=v to maxstan do Begin

407. CreateLevel(P,i); P:=SetActive(P); If PA.Tz = 100000 Then break; End; V:=i; End;

408. Procedure DEL(Var V:integer;Var P:Pnode);1. Var i: integer;1. Begin1. Writeln('Der,V); Readln;

409. NDels:=NDels+l; If V=PA.Z Then Begin1. P:=PA.Back;1. For i:=l to maxhub do1. Begin

410. Dispose(PA.Next1.); PA.Nexti.:=nil; PA.Tz:=100000; { Writeln('Del from ',PA.z;=100000');} End; End Else Begin

411. Writeln ('Error Level del: V=',V5' Z=',PA.Z); Halt(l); End; End;1. Procedure Opt; Begin

412. GetTime(h,m,s,hund); {Grafika;

413. WriteLn('Choice is :'); PrintNode(Optim); ShowPOLE; ShowLines(Optim);} Sek:=s+Hund/100+m*60+h*60*60; Append (Fstat);

414. Write(Fstat,Maxstan:3,Maxhub:3,OptimA.F: 10:2,Nlevels: 10,Ndels: 10);

415. Writeln(Fstat; ',Sek:10:2);1. Close(Fstat);1. Writeln ('OK');1. Readln;}1. Halt(l);1. End;

416. Function InitNode:Pnode; Var i .'integer;1. P:Pnode; begin1. New(P); with Рл do begin

417. For i:=l to MaxHub do Begin

418. Next1. := nil; Ti.:=0; N[i]:=Q;1. Tz:=0; End;1. Aktive := 0; Z:=0; End;1.itNode:=p End;

419. Function OcenkaO:real; Var i:integer;1. Sl,S2:real; Begin

420. S1:=0; S2:=0; For i.-l to maxstan do

421. Sl:=Sl+Tau1.; OcenkaO:=Sl; End;

422. Function IflnSet(i: Word;N:Mset): Boolean; Begin1. i in N Then IflnSet:=TRUE1. Else IflnSet.-False;1. End;

423. Function OcenkaI(Z:integer;P:Pnode):real: Var i: integer;

424. S1 ,S2,S3,MaxTau,Tzj :real; R:byte; Begin S1:=0; S2:=0; S3:=0;

425. For i:=Z+l to maxstan do S3:=S3+Tau1.;1. With рл do1. For i:=l to MaxHub Do1. Begin1. T1.:=0;

426. For j:=l to maxstan do If IfInSet(j,N1.) Then Ti. := T[i] + L[j,i];1. End;

427. For i:=l to MaxHub Do S2:=S2+pA.T1.;1. OcenkaI:=S2+S3;1. With Рл do1. Begin1. F:=T1.;

428. For i:=2 to maxhub do F:=F+T1.; End; End;

429. Function SetActive(p:Pnode);Pnode; Var i,j:integer;1. Mx:real; Begin

430. PA.Z=Maxstan-1 then Begin With Рл Do Begin Aktive:=l; Mx:=Nextl.A.F; For i:=2 to MaxHub do If Mx > Next1.A.F Then

431. Begin Aktive :=i; Mx:=Next1.A.F End; End;

432. Writeln ('From V=\PA.Z,' Aktive = \PA.Aktive); } SetActive:=PA.NextPA. Aktive.;

433. End Else Begin With PA Do Begin Aktive:=l; Mx:=Nextl.A.Tz; For i:=2 to MaxHub do If Mx > Next1.A.Tz Then Begin Aktive:=i; Mx:=Next[i]A.Tz End; End;

434. Writeln ('From V=',PA.Z,' Aktive = ",PA. Aktive);

435. SetActive :=PA.NextPA. Aktive.;1. End1. End;1. Begin

436. Assign(fr,PathFr); Assign(fc,PathFc); Assign(fh,PathFh); Assi gn(fmatr,PathFmatr); Assign(fstat,Pathstat); Val(ParamStr(l), MaxHub, Code); if code <> 0 then Begin

437. Writeln('Error at positon:', Code);1. Halt(l);1. End;

438. Val(ParamStr(2),MaxStan, Code); if code <> 0 then Begin

439. WriteLn(XA.Tz: 10:2);} SetTime(0,0,0,0); Process(V,X);

440. While ((X <> nil) And (V>=0 )) do Begin1. If V=1 then Begin1. Writeln('VX=l!!!');1. Readln;1. End;1. (V < 0) Or (X=nil) then begin Opt;end;1. (XA.F < OptimA.F) and (v=maxstan) Then Begin { Writeln (XA.F:10:2);} For i:=l to MaxHub do Begin

441. OptimA.N1.:=XA.Ni.; OptimA.T[i]:=XA.T[i]; End;

442. OptimA.Tz:=XA.Tz; OptimA.F:=XA.F; OptimA.Z:=XA.Z; If OptimA.F=RootA.Tz Then begin Opt;1. End;

443. Writeln('Del X',V);} Del(V,X); V:=V-1;1. (V <= 0) Or (X=nil) Then begin Opt; end;1. X:=XA. Back;1. X:=SetActive(X);

444. While (V>0) and (X<>nil) Do1. Begin1. If V=1 then Begin1. Writeln('VA=l!!!');1. Readln;1. End;1.XA.Tz= 100000 Then1. Begin

445. Writeln('Del Active was 100000',V);} DEL(V,X); V:=V-1;1. V<=0 Then begin Opt; end;1. End Else Begin J.-0;

446. For i:=l to maxstan do If ifmset(i,xA.NxA.BackA.aktive.) then

447. J:=J+1; If J<=Nmax Then Begin1. J:=l;

448. While j <= maxstan do Begin1. Flag:=TRUE;1. For i:=l to maxhub do

449. Lj,i. < (Abs(OptimA.F-XA.Tz)) Then

450. Flag "False; If Flag Then Break; J-J+l; End;1. Flag Then } Begin

451. Process(V,X); Break; End; End; End; XA.Tz:=l 00000; X:=XA.back; X:=SetActive(X);1. End; End; Opt; End.

452. Распределение нагрузки минимаксный критерий (DOS)

453. Program BMinMax; Uses graph,strings,windos; Const MaxHub =2; MaxStan = 10; Nmax = 8; BGIPath = 'c:\bp\bgi'; PathFr = 'c'.\bp\work\stan.txt'; PathFc = 'c:\bp\work\coord.txt'; PathFh = 'c:\bp\work\hubs.txt'; PathFmatr='c :\bp\work\matr.txt'; Type

454. Mset = Set of 0. 100; PNode = ANode; Node = record Z : integer;

455. N : Array 1 .MaxHub. of Mset; T : Array [1 .MaxHub] of real; Tz : Real; F : Real; Aktive : byte;

456. Next: Array 1.MaxHub. of PNode; Back: Pnode; End;var1. Fr,Fc,Fh,Fmatr: text;1.: Array 1.MaxStan, 1.MaxHub. of real; Tau : Array [l.maxstan] of real; Те : Array [ 1. .MaxHub] of Real; N0 : Mset;

457. ТО : real; Optim,Check,Root,х : Pnode; ij,z,v,Nstan,Nhub:integer; kbyte; ch : char; Flag:Boolean;

458. Function INITNODE : Pnode ; Forward; Function OcenkaI(Z:integer;P:Pnode):real; Forward; Function IfInSet(i:Word;N:Mset): Boolean; Forward; Function SetActive(p:Pnode):Pnode; Forward; Procedure OPT; Forward;

459. Procedure PrintNode(p:Pnode); Var ij:integer;k,c:String; Begin With pA do Begin1. Writeln('Level = *,Z);1. Write('N=');1. For j:= 1 to Maxhub Do1. Begin1. K:=";

460. For i:=l to maxStan do If IflnSet(i,Nj.) then Begin Str(i,c); K:=K+' '+c; End; Write('[',k:7,']'); End; Writeln; Write (*T='); For i.-l to maxhub Do Write(T1.:7:l); Writeln;

461. Writeln('Graphics error:', GraphErrorMsg(ErrCode));1. Halt(l); End;end;

462. Procedure ShowLines(P:Pnode); Var i,j'.integer;

463. XH,XS,YH,YS:Word; Begin Reset(Fh); Reset(Fc); With Рл Do Begin1. For i:=l to MaxHub Do1. Begin1. ReadLn(Fh,XH,YH);1. Reset(Fc);1. SetColor(i);1. For j :=1 to MaxStan Do1. Begin

464. Readln(Fc,XS,YS); If IfInSet(j,N1.) then1.e(XH,YH,XS,YS); End; End; End; End;

465. Procedure MakeLij; Var ij-.integer;

466. HX,HY,SX,SY:real; Begin Reset(fc); Reset(fh); rewrite(fmatr); For i:=l to Maxstan do Begin

467. Read (fc,sX); Readln(fc,sY); Reset(fh);

468. For j :=1 to Maxhub do Begin

469. Read (fh,hX); Readln(fh,hY);1.,j.:=SQRT(SQR(HX-SX)+SQR(HY-SY));write(fmatr,Lij.: 10:2);1. End;1. Writeln(fmatr,''); End;close(fmatr); End;

470. Procedure CreateLevel(Var P:Pnode; Var Level:integer);1. Var i,j:integer; BeginwRITE LN(LEVEL); } For i:=l to maxhub do Begin

471. PA.Next1.:=InitNode; With PA.Nexti.A do1. Begin Z:=Level; Back:=P;1. For j :=1 to maxhub dobegin1. Nj.:=PA.N[j];1. j=i then Nj.:=N[j]+[Level];1. Tj.:=PMB];end;

472. Tz:=OcenkaI(Level,PA.Next1.); PrmtNode(PA.Nexti.); Readln; End End End;

473. Procedure MakeLfile; Var i:integer; Xl,X2,Yl,Y2:word; a: array l.maxstan. of record xl,yl:integer; End;1. DX,DY:Real;1. Begin1. Rewrite(Fr); Reset(fc);

474. Writeln(Fr,MaxStan); For i:=l to MaxStan do Read(fc,a1.Xl,ai.Yl);

475. For i:=1 to Maxstan do Begin

476. For J:=l to MaxStan Do Begin

477. DX:=abs(a1.Xl-a£j.Xl); DY:=abs(ai].Yl-a[j].Yl); Write( fr,sqrt(DX*DX+DY*DY): 10:2);

478. End; Writeln(fr,"); Readln(fc); End; End;

479. Procedure MakeCoordFile(Mx,My:Word);1. Var ianteger; Begin1. Rewrite(Fc);1. Randomize;1. Randseed:=5;1. For i:=l to MaxStan dobegin

480. Write (Fc,Random(Mx)/'); writeln(Fc,Random(My)); end; End;

481. Procedure MakeCoordHubs(Mx,My:Word)1. Var i: integer; Begin1. Rewrite(Fh);1. Randomize;1. Randseed:=3;1. For i:=l to MaxHub dobegin

482. Write (Fh,Random(Mx),''); writeln(Fh,Random(My)); end; End;1. Procedure ShowPole; Var

483. X,Y,i,j :Word; MaxX,MaxY:Word; Begin

484. For i:=l to Maxstan do Begin

485. Read (Fc,X,Y); Putpixel(X,Y,White); Putpixel(X+1 ,Y+1,White) Putpixel(X+1, Y,White); Putpixel(X,Y+l, White); End;1. Reset(Fh); readln;

486. For i:=l to Maxhub do Begin1. Read (Fh,X,Y);1. Putpixel(X,Y,Red);1. Putpixel(X+1, Y+l ,Red);1. Putpixel(X+1, Y,Red);1. Putpixel(X, Y+1 ,Red);1. End;1. End;

487. Procedure CalcTau; Var i,j:integer; Begin For i:= 1 to maxstan do1. Begin

488. Tau1.:=1000; For j ^ 1 to maxhub do If Taui.>L[i,j] then Tau[i]:=L[i,j]1. End; End;

489. Procedure SortTE; Var Mx:REAL; Begin For i:=l to 5 do For j:=i to 5 do If Tej.<Te1. Then Begin

490. Mx:=Te£j.; Tej]:=Te1.; Te[i]:=Mx End;1. End;

491. Procedure PrintLevel(p:pnode);1. Var i: integer; begin

492. For i:=l to maxhub do PrintNode(PA.Next1.);end;

493. Procedure Process(var V:integer; var PrPNode);1. Var i,j: integer;1. Begin1. Writeln('Process',v);1. Readln;v:=v+l;

494. For i:=v to maxstan do Begin

495. CreateLevel(P,i); P:=SetActive(P); End; V:=Maxstan; End;

496. Procedure DEL(Var V:integer;Var P:Pnode);1. Var irinteger; Begin1. Writeln('Der,V);1. Readln; }1. V=PA.Z Then Begin

497. P:=PA.Back; For i:=l to maxhub do Begin Dispose(PA.Next1.); PA.Nexti.:=nil; PA.Tz:=100000; { Writeln('Del from ',PA.z,'= 100000'); } End;1. End Else Begin

498. Writeln ('Error Level del: V=',V,' Z=',PA.Z);1. Halt(l); End; End;1. Procedure Opt;1. Begin1. Grafika;1. WriteLn('Choice is :');1. PrintNode(Optim);1. ShowPOLE;1. ShowLines(Optim);1. Readln;1. Halt(l);1. End;

499. Function InitNode:Pnode; Var i: integer;1. P:Pnode; begin1. New(P); with Рл do begin

500. For i:=l to MaxHub do Begin1. Next1. := nil; Ti.:=0;1. N1.:=.;1. Tz:=0;1. End;1. Aktive := 0; Z:=0; End;1.itNode:=p End;1. Function OcenkaO:real;1. Var i: integer;1. Sl,S2:real; Begin

501. S1:=0; S2:=0; For i:=l to maxstan do1. Begin

502. Sl:=Sl+Tau1.; If S2<Taui. Then S2:=Tau[i]; End; SI :=S1 /Maxhub; If S1>S2 Then OcenkaO:=SI Else OcenkaO:=S2;1. End;

503. Function IfInSet(i:Word;N:Mset): Boolean; Begin1. i m N Then IfInSet:=TRUE Else IfInSet:=False;1. End;

504. Function OcenkaI(Z:integer;P:Pnode):real;1. Var i: integer;

505. S1, S2,S3 ,MaxTau,Tzj :real; R:byte; Begin

506. Z <= MaxStan Maxhub Then R:=MaxHub1. Else1. R:=Maxstan Z;1. S1:=0; S2:=0; S3:=0;

507. Maxtau:=TauZ+1 .; For i:=Z+l to maxstan do1. Begin

508. MaxTau < Tau 1. then MaxTau:=Taui.1. S3:=S3+Tau1.; End;

509. With pA do For i:=l to MaxHub Do Begin T1.:=0;

510. For j:=l to maxstan do If IfInSet(j,N1.) Then Ti. T[i] + L[j,i]; Te[i]:=T[i]; End;1. SortTe; If R>0 Then1. Begin

511. Fori:=ltoRdo Sl:=Sl+Te1.; S1:=(S1+S3)/R; End

512. Else S1:=0; S2:=TeMaxhub.; If S1<S2 Then Tzj:=S2

513. Else Tzj:=Sl; If Tzj<MaxTau Then Tzj:=MaxTau;1. Ocenlcal:=Tzj;1. With Рл do1. Begin1. F:=T1.;

514. For i:=2 to maxhub do If F<T1. Then F:=Ti. End; End;

515. Function SetActive(p:Pnode):Pnode; Var i,j -.integer;1. Mx:real; Begin

516. PA .Z=Maxstan-1 then Begin With Рл Do Begin Aktive:=l; Mx:=Nextl.A.F; For i:=2 to MaxHub do If Mx > Next1.A.F Then Begin Aktive:=i; Mx:=Next[i]A.F End; End;

517. Writeln ('From V=',PA.Z,' Aktive = l,PA.Aktive); } SetActive:=PA.NextPA.Aktive.;1. End Else

518. Begin With PA Do Begin Aktive:=l; Mx:=Nextl.A.Tz; For i:=2 to MaxHub do If Mx > Next1.A.Tz Then Begin Aktive:=i; Mx:=Next[i]A.Tz End; End;

519. Writeln ('From V=',PA.Z,' Aktive = ',PA.Aktive);

520. SetActive:=PA.NextPA.Aktive.;1. End1. End;1. Begin

521. Assign(fr,PathFr); Assign(fc,PathFc); Assign(fh,PathFh); Assign(fmatr,PathFmatr); Writeln('Mem: ',Memavail); WriteLn('l Create files'); WriteLn('2 - Open files'); Readln (ch); Case ch of '1'.-Begin

522. MakecoordFile(640,480); MakecoordHubs(640,480); Close(fc); MakeLij; Reset(fc); End; '2': Begin Reset(fr); Reset(fh); MakeLij; Reset(fc); Reset(fmatr);1. End; End;1. CalcTau; Optim:=InitNode;

523. OptimA.Tz:=900000; OptimA.F : =900000; OptimA.Back:=nil;1. Root:=InitNode;1. RootA.Back:=nil;1. RootA.Tz:=OcenkaO;1. RootA.F:=900000;1. X:=Root;1. V:=0;

524. WriteLn(XA.Tz: 10:2); Process(V,X);

525. While ((X <> nil) And (V>=0 )) do Begin If V=1 then Begin1. Writeln('VX=l!!!');1. Readln;1. End;1. (V < 0) Or (X=nil) Then Opt; If XA.F < OptimA.F Then Begin

526. Writeln (XA.F:10:2); For i:=l to MaxHub do Begin1. OptimA.N1.:=XA.Ni.; End;

527. OptimA. Tz:=XA Tz; OptimA.F:=XA.F; OptimA.Z~XA.Z; If OptimA.F=RootA.Tz Then Opt;1. End;1. Writeln('Del X',V);1. Del(V,X);1. V:=V-1;1. (V <= 0) Or (X=nil) Then Opt;1. X:=XA.Back;1. X-SetActive(X);

528. While (V>0) and (X<>nil) Do1. Begin

529. V=l then Begin Writeln(,VA=l !!!*); Readln; End;1.XA.Tz= 100000 Then Begin

530. Writeln('Del Active was 100000',V); DEL(V,X); V:=V-1;

531. V<=0 Then Opt; End Else Begin {J"0;

532. For i:=l to maxstan do If ifmset(i,xA.NxA.BackA.aktive.) then

533. J:=J+1; If J<=Nmax Then} Begin J:=l;

534. While j <= maxstan do Begin

535. Flag:=TRUE; For i:=l to maxhub do If Lj,i. < (Abs(OptimA.F-XA.Tz)) Then

536. Flag :=False; If Flag Then Break; J:=J+1; End;

537. Flag Then} Begin Process(V,X); Break; End; End; End;1. XA.Tz:=l 00000;1. X:=XA.back;1. X:=SetActive(X);1. End; End; Opt; End.

538. Реализация переборных алгоритмов (DOS)$A+,B-,D-,E-,F-,G+,I-,L-,N+,0-,P-,Q-,R-,S-,T-,V-,X-} {$M 16384,0,655360}(с) TITANIC 4 Shs *) Program Optimum; Const

539. NStantions =10; NHubs =2; Koeff = 10;

540. FileNameStantions = 'c:\bp\work\coord.txt'; FileNameHubs = 'c:\bp\work\hubs.txt'; Type

541. PointType = Record X, Y: Single; End;

542. DistanceMatr = Array 1.NHubs, 1.NStantions. of Word; ConnectsSet = Array [1.NStantions] of Word; ConnectsMatr = Array [1.2] of ConnectsSet; { 1 Work array

543. Result array } Procedure HubLinks(var С : ConnectsSet); Var

544. E : Arrayl.NHubs. of Word; i: Integer; Begin For i:=l to NHubs do E1.:=0;

545. For i:=l to NStantions do inc(EC1.);

546. WriteLn('Links with Hubs:'); WriteC Hubs:'); For i:=l to NHubs do Write(i:5); WriteLn; Write('Links:'); For i:=l to NHubs do Write(E1.:5); Writeln; End;

547. Procedure PrintConnections(var С : ConnectsSet); Var i: Integer; Begin

548. Writeln('Optimal connection:');1. Write('Stantions:');1. For i:=l to NStantions do1. Write(i:5); WriteLn;

549. WriteC Hubs:'); For i:=l to NStantions do Write(C1.:5); WriteLn; End;

550. Function Open(var f: Text; FileName : String): Boolean; Begin {$1-}

551. Assign(f, FileName); Reset(f); {$1+}1. Open:=IOResult = 0; End;

552. Function Len(pl, p2 : PointType): Word; Begin1.n:=Round(Sqrt(Sqr(p2.x-p 1 .x)+Sqr(p2.y-p 1 .y))*Koeff); End;

553. Function How(PDist, PRes : Pointer;

554. Distance : DistanceMatr; Connects: ConnectsMatr; HubsCoords : Array l,.NHubs. of PointType; StantionsCoords : Array [L.NStantions] of PointType; f: Text; i,j : Integer; SummaryLen : Longlnt; BEGIN WriteLn;

555. Not Open(f, FileNameHubs) Then Begin

556. WriteLn('Error opening file:FileNameHubs,""); Halt(l); End;

557. For i:=l to NHubs do If Not EOF(f) Then

558. ReadLn(f, HubsCoords1.X, HubsCoordsi.Y); Close(f);

559. Not Open(f, FileNameStantions) Then Begin

560. WriteLn('Error opening file:FileNameStantions,""); Halt(l); End;

561. For i:=l to NStantions do If Not EOF(f) Then

562. ReadLn(f, StantionsCoords1.X, StantionsCoordsi.Y); Close(f);1. For i:=l to NHubs do