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

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

Постановка задачи линейного программирования

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

Дана система m линейных уравнений с n неизвестными:

(3.1.1)

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

(3.1.2)

и линейная функция от тех же переменных

(3.1.3)

называемая целевой функцией.

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

Любое неотрицательное решение системы уравнений (3.1.1) называют допустимым решением, а то допустимое решение, при котором целевая функция (3.1.3) принимает наименьшее значение, называют оптимальным 80 решением задачи линейного программирования (3.1.1)—(3.1.3). Кратко задачу формулируют так: найти вектор , минимизирующий целевую функцию (3.1.3) при линейных ограничениях (3.1.1) и (3.1.2).

Стандартная задача ЛП

или, в матричной записи,

где — матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений.

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

Каноническая задача ЛП

или, в матричной записи,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП

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

Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .

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

При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор , удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи.

По Вентциль

Система – множество элементов с определенными способами взаимодей­ствия между ними, которые все вместе выполняют цель системы.

Процесс – все, что происходит в системе. Система работает, значит в ней происходит процесс.

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

При исследовании сложных организационных систем:

1. невозможен экспериментальный метод исследования;

2. невозможно описание поведения систем только на основе какой- либо естественнонаучной теории;

3. при описании таких систем количество факторов, которые необ­ходимо учитывать, велико.

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

Схема операционного проекта

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

Дадим краткую характеристику этапов операционного исследования.

1. В самом общем случае поводом для изучения и совершенствования системы служат зафиксированные симптомы, обнаруживающие проблемные вопросы в работе системы.

2. Установленные симптомы проблемы могут образовывать связанную цепочку фактов (тенденцию), которая помогает сформулировать проблему.

3. Важнейшим этапом исследования системы является четкая формули­ровка проблемы, которая присутствует на данном уровне жизнедеятельности системы.

4. Качественный системный анализ – это расщепление целостной систе­мы (операции) на отдельные элементы (сущности). Для этого нужно:

a. выделить изучаемую систему (операцию) из вышестоящей системы (операции);

b. сформулировать цель, выполняемую системой (операцией);

c. перечислить факторы, которые влияют на достижение цели;

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

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

a. устанавливается критерий – величина, количественно измеряющая степень достижения цели системы (операции);

b. вводятся количественные внутренние параметры системы, которые измеряют факторы, участвующие в описании системы (операции);

c. все множество этих параметров необходимо разбить на две части:

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

ii. управляемые параметры (переменные) – величины, которые мы можем менять .

6. Суть математического моделирования – установление количественных связей между введенными величинами , , и в виде так называемой операционной модели.

Классификация моделей систем (статические, динамические, концептуальные, топологические, формализованные (процедуры формализации моделей систем), информационные, логико-лингвистические, семантические, теоретико-множественные)

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

1. По отношению системы к окружающей среде:

a. открытые (есть обмен ресурсами с окружающей средой);

b. закрытые (нет обмена ресурсами с окружающей средой).

2. По происхождению системы (элементов, связей, подсистем):

a. искусственные (орудия, механизмы, машины, автоматы, роботы и т.д.);

b. естественные (живые, неживые, экологические, социальные и т.д.);

c. виртуальные (воображаемые и, хотя реально не существующие, но функционирующие так же, как и в случае, если бы они существовали);

d. смешанные (экономические, биотехнические, организационные и т.д.).

3. По описанию переменных системы:

a. с качественными переменными (имеющие лишь содержательное описание);

b. с количественными переменными (имеющие дискретно или непрерывно описываемые количественным образом переменные);

c. смешанного (количественно-качественное) описания.

4. По типу описания закона (законов) функционирования системы:

a. типа "Черный ящик" (неизвестен полностью закон функционирования системы; известны только входные и выходные сообщения);

b. не параметризованные (закон не описан; описываем с помощью хотя бы неизвестных параметров; известны лишь некоторые априорные свойства закона);

c. параметризованные (закон известен с точностью до параметров и его возможно отнести к некоторому классу зависимостей);

d. типа "Белый (прозрачный) ящик" (полностью известен закон).

5. По способу управления системой (в системе):

a. управляемые извне системы (без обратной связи, регулируемые, управляемые структурно, информационно или функционально);

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

c. с комбинированным управлением (автоматические, полуавтоматические, автоматизированные, организационные).

Пример. Рассмотрим экологическую систему "Озеро". Это открытая, естественного происхождения система, переменные которой можно описывать смешанным образом (количественно и качественно, в частности, температура водоема - количественно описываемая характеристика), структуру обитателей озера можно описать и качественно, и количественно, а красоту озера можно описать качественно. По типу описания закона функционирования системы, эту систему можно отнести к не параметризованным в целом, хотя возможно выделение подсистем различного типа, в частности, различного описания подсистемы "Водоросли", "Рыбы", "Впадающий ручей", "Вытекающий ручей", "Дно", "Берег" и др. Система "Компьютер" - открытая, искусственного происхождения, смешанного описания, параметризованная, управляемая извне (программно). Система "Логический диск" - открытая, виртуальная, количественного описания, типа "Белый ящик" (при этом содержимое диска мы в эту систему не включаем!), смешанного управления. Система "Фирма" - открытая, смешанного происхождения (организационная) и описания, управляемая изнутри (адаптируемая, в частности, система).

Из интернетов

Источник: http://www.studfiles.ru/preview/6023524/page:16/#36

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

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

Рассмотрим основные типы структур.

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

Кольцевая структура (рис. 5.1, б) отличается замкнутостью, любые два элемента обладают двумя направленными связями. Это повышает скорость обмена информацией, делает структуру более живучей.

Сотовая структура(рис. 5.1, в) характеризуется наличием резервных связей, что повышает надежность (живучесть) функционирования структуры, но приводит к повышению ее стоимости.

Многосвязная структура(рис. 5.1, г) имеет структуру полного графа. За счет наличия кратчайших путей надежность ее функционирования максимальная, эффективность функционирования высокая, однако стоимость тоже максимальная.

Звездная структура(рис. 5.1, д) имеет центральный узел, который выполняет роль центра, все остальные элементы системы являются подчиненными.

а - линейная	б - кольцевая
в - сотовая	г - многосвязная
д - звезда	е - графовая
Рис. 5.1. Типы структур

Графовая структура (рис. 5.1, е) используется обычно при описании производственно- технологических систем.

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

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

Сети бывают разные. Наиболее распространены и удобны для анализа однонаправленные сети. Но могут быть и сети с обратными связями, с циклами.

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

Рис.5.2

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

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

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

Рис. 5.3

Рис.5.4

Пример 1.

Иерархия каталогов в ОС может быть деревом или сетью.

Дерево(MS-DOS) - файлу разрешено входить только в один каталог (иерархическая структура с сильными связями, рис. 5.5 а);

Сеть (UNIX) - файл может входить сразу в несколько каталогов (рис.5.5 б).

Иерархия каталогов в MS DOS

Иерархия каталогов в UNIX

Рис. 5.5

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

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

Иерархическая структура с сильными связями может быть представлена матричной структурой (табл. 5.1). Такое представление иногда удобнее на практике, например, при оформлении планов работ, когда нужно указать исполнителей, формы отчетности и т.п.

Взаимоотношения между уровнями иерархии со «слабыми» связями могут быть представлены в виде двумерной матричной структурой (табл. 5.2) Важной особенностью такого представления является возможность отразить не только наличие связей, но и их силу: либо словами («сильная» - «слабая»), либо путем введения количественных характеристик силы связи.

Таблица 5.1

1. …	1.1. …	1.1.1. …
1.1.2 . …
1.1.3. …
1.2. …	1.2.1. …
1.2.2. …
2. …	2.1. …	2.1.1. …
2.1.2. …

Таблица 5.2

1.1 1.2 2.1	+ + -	+ - +

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

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

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

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

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

Основные страты изучения систем: макроскопический и микроскопический анализы.

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

Цель макроскопического анализа состоит в создании модели изучаемой системы в ее взаимодействии с окружением (модель «вход-выход» - модель типа «черный ящик»).

Микроскопический анализ детально описывает каждый из компонентов системы; центральным при этом является понятие элемента: изучаются связи и функции элементов, структура системы и др.

К задачам микроанализа можно отнести следующие:

• выделение элементов в системе;
• изучение каждого из элементов;
• установление структуры системы;
• выявление связей между элементами.

Примеры.

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

Рис. 5.6

2. Автоматизированный промышленный комплекс обычно моделируют на трех стратах (рис. 5.7)

Рис. 5.7

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

4. Ю.И.Черняк выделил уровни абстрагирования системы от философского или теоретико-познавательного описания ее замысла до материального воплощения, как это показано на см. рис. 5.8.

Рис.5.8

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

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

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

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

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

- технологическом - технологичекие карты, стандарты и другая технологическая документация (конструкторская и технологическая страты могут быть объединены);

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

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

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

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

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

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

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

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

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

Рис. 5.9

На рис. 5.10 представлена информационная система организации, состоящая из нескольких взаимодействующих слоев.

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

Рис. 5.10

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

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

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

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

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

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

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

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

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

Рис. 5.11

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

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

Для того, чтобы на это обратить внимание в [1] разделены понятия собственно «управления» и «координации». При этом координация может иметь разную силу воздействия (вмешательства) и осуществляется в разной форме. В связи с этим теорию многоуровневых систем М.Месаровича иногда называют теорией координации. В этой теории рекомендуется, чтобы в процессе принятия решений подсистемы не всегда стремились бы отстаивать свои интересы, доводя дело до конфликтных ситуаций, а вступали бы в коалиции.

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

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

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

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

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

Смешанный характер носит и организационная структура современного предприятия (объединения, акционерного общества и т. п.).

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

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

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

После формирования таких структур связи упорядочиваются и получают иерархические или сетевые структуры.

По википедии

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

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

Базы данных с иерархической моделью одни из самых старых, и стали первыми системами управления базами данных для мейнфреймов. Разрабатывались в 1950-х и 1960-х, например, Information Management System (IMS)[1]фирмы IBM.

По лекциям из интернетов

Иерархия (hiezosazche — священная власть, греч.) — это расположение частей целого в порядке от высшего к низшему. Термин «иерархия» (многоступенчатость) определяет упорядоченность компонентов системы по степени важности. Между уровнями иерархии структуры могут существовать взаимоотношения строгого подчинения компонент нижележащего уровня одному из компонент вышележащего уровня, т.е. отношения древовидного порядка. Такие иерархии называют сильными или иерархии типа «дерево».

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

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

Различают строго и нестрого иерархические структуры.

Система строгой иерархической структуры имеют следующие признаки:

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

Рис. 1 — Граф строго-иерархической структуры

Рис. 2 — Граф нестрогой иерархической структуры

На рис.1 приведен граф строго иерархической структуры, на рис.2 — граф нестрогой иерархической структуры. Обе структуры трехуровневые.

Так на рис.1 элемент 1-го уровня иерархии может представлять собой ректора университета, элементы 2-го уровня — проректоров, 3-го уровня — деканов, остальные элементы (4-го уровня, не отраженного на рисунке) будут представлять заведующих кафедрами. Понятно, что все элементы и связи представленной структуры не равноправны.

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