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

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

Теорию и методы решения задачи оптимизации изучает математическое программирование.

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

Классификация задач математического программирования

Класс	Особенности
Линейное программирование	Целевая функция j(x) и ограничения gi (x) и hi (х) линейны
Выпуклое программирование	Целевая функция и допустимое множество выпуклы
Нелинейное программирование	Ограничения или целевая функция содержат нелинейные функции, и X является подмножеством конечномерного векторного пространства
Целочисленное программирование	Если X является подмножеством множества целых чисел
Дискретное программирование (комбинаторная оптимизация)	Если X конечно или счетно, решение ищется лишь в дискретных, например целочисленных, точках множества X
Квадратичное программирование	Целевая функция квадратична и выпукла, допустимое множество определяется линейными равенствами и неравенствами
Параметрическое программирование	Раздел математического программирования, изучающий задачи, отличие которых от других задач состоит в следующем. Коэффициенты их целевой функции, или числовые характеристики ограничений, или и те, и другие предполагаются не постоянными величинами (как, например, в линейном программировании), а функциями, зависящими от некоторых параметров. Причем чаще всего эта зависимость носит линейный характер
Динамическое программирование	Способ решения сложных задач путем раз- биения их на более простые подзадачи
Стохастическое программирование	В отличие от детерминированных задач здесь входная информация носит элементы неопределенности

 

Основные виды иерархических структур. Модель функционирования иерархической системы

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

Источник: 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.