Сглаживание потребности в ресурсах. Граф Ганта. Транспортные сети. Оптимизация потоков в транспортных сетях

Приведем несколько определений, относящихся к структуре множе­ства М, упорядоченного некоторым отношением порядка А. Мажорантой (верхней границей) подмножества QÎМ называют такой элемент тÎМ, что для всех qÎQ справедливо соотношение qAm. Минорантой (нижней границей) подмножестваQÎМ называют такой элемент пÎ М, что для всех qÎQ справедливо соотношение nAq.

Если мажоранта т (миноранта а) принадлежит Q, то т называют максимумом (п называют минимумом) множества Q и обозначают maxQ (minQ). Максимум, как и минимум, если он существует, единственен; поэтому, когда говорят о минимуме или максимуме множества Q, имеют в виду вполне определенный элемент.

Множество QÎМ может иметь много мажорант и минорант. Если множество мажорант (минорант) имеет минимум (максимум), то этот элемент единственен. Его называют верхней (нижней) гранью или супремумом (инфинумом) множества Q и обозначают supQ (in/Q). Отношению порядка соответствует матрица, у которой главная диагональ заполнена единицами (рефлексивность). Кроме того, ни один единичный элемент не имеет симметричного относительно главной диагонали (антисимметричность). Например, матрица отношения «быть делителем» на множестве {1,2,3,4,6,7, 12, 14,21,28,42,84} представлена в таблице 3.

Таблица 3 Матрица отношений

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

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

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

На рис. 3 показан упрощенный граф отношения «быть делителем» из приведенного ранее примера. На графе наглядно прослеживается структура упорядоченного множества. Так, для подмножества Q - {4, 6, (14, 28, 42} мажорантой является элемент 84, а минорантами — элементы 1 и 2, Максимума и минимума Q не имеет, но supQ=84, a infQ~2. Для всего множества единственная мажоранта 84 является одновременно макси­мальным, элементом, а миноранта 1 - минимальным элементом.