Учебное пособие по ТСиСА

	κ	)2		12	( 3 )
ρi	= ∑(1 − βl			, i = 1,...,n.
	l =1

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

Таблица П3.1

Характеристики альтернатив

	ξ1	ξ2	ξ3	ξ4
X1	100	0,99	24	1
	0,91	1,00	0,96	1
X2	110	0,98	24	1
	1,00	0,99	0,96	1
X3	100	0,99	25	1
	0,91	1,00	1,00	1

Примечание. В числителе приведены абсолютные значения, а в знаменателе – нормированные.

Исходный граф G(X) для данной задачи будет иметь вид:

X1	X2
G(X):	.

X3

По табл.П3.1, с использованием графа G(X) определяются:

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

R		0	0	1		R		0	1	0
	=						=				.
D1		1	0	1	.	D3		1	0	0
		1	0	0				1	1	0

R		0	1	1		R		0	1	1
	=				.		=
D2		0	0	0		D4		1	0	1	.
		1	1	0				1	1	0

Подставив данные матрицы в (2) рассчитываются показатели b, значения которых сведены в табл.П3.2.

Таблица П3.2

Значения показателей вершинной достижимости

	B1	B2	B3	B4
X1	0,25	1,00	0,25	1,00
X2	1,00	0,00	0,25	1,00
X3	0,25	1,00	1,00	1,00

Подставив данные табл.П3.2 в (3) имеем:

ρ1 = 1,06; ρ2 = 1,25; ρ3 = 0,75.

Следовательно, кортеж предпочтительности альтернатив будет иметь вид: x3 > x1 > x2.

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

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

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

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

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

какая планируется пропускная способность дорог и др.

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

Постановка задачи в этом случае будет иметь следующий

вид:

		u* : max {P };
			u U		u
					( 4)
		P =	Wu	,
		u	Su
где	u*	- оптимальный вариант сети дорог;
	Pu	- показатель экономической эффективности u-
		го варианта;
	Wu	- показатель топологического качества струк-
		туры сети дорог;
	Su	- суммарные затраты на реализацию u-го ва-
		рианта;

U- множество допустимых вариантов.

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

		Wu = f(δ, R, Qотн),	( 5)
где	δ	- степень централизации структуры;
	R	- структурная избыточность;

Qотн - относительная структурная компактность. При этом

Ra = 1; δ → max;

R → min;

Qотн → max.

Ra = 1 означает абсолютную связность структуры сети, т.е. принципиальную достижимость каждого пункта (элемента структуры) из каждого.

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

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

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

Wu = 0,384(1 – R) + 0,270Q отн + 0,346δ.

( 6)

Пусть имеется два варианта реализации сети дорог, структуры которх показаны на рис.П3.2.

2

3

2

3

1

1

4 5 4 5

А) Б)

Рис. П3.2. Варианты дорожной сети

Пусть также на реализацию варианта А необходимо SА = 15 ед., а на реализацию варианта Б - SА = 10 ед.

Результаты расчетов показателей топологических свойств структур вариантов сведены в табл.П3.3.

Таблица П3.3

Значения показателей топологических свойств

	Rа	R	Qотн	δ
Вариант А	1	0,000	0,667	0,667

Вариант Б	1	0,167	0,769	0,583

Рассчитав значения показателей топологических свойств структур вариантов А и Б имеем:

WA = 0,735;

WБ = 0,729.

Следовательно,

PA = 0,049;

PБ = 0,073.

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

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

При проектировании базы данных решаются две основных проблемы:

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

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

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

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

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

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

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

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

ДЕТАЛЬ (Код детали, Наименование детали, Код материала, Наименование материала, Код оборудования, Наименование оборудования, Дата изготовления, Отметка о выполнении, Табельный номер, Фамилия, Имя, Отчество, Должность, Дата рождения, Сдельщик).

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

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

ПЕРСОНАЛ		ДЕТАЛЬ

МАТЕРИАЛ ОБОРУДОВАНИЕ

Рис. П3.3. Инфологическая модель предметной области

Полная атрибутивная модель (ERD-диаграмма), соответствующая инфологической модели (рис.П3.3), показана на

рис.П3.4.

E/Материал

Кодматериала

Наименование метериала

Используется / Изготовлена из

E/Оборудование

Код оборудования

Наименование оборудования

Применяется / Изготовлена на

E/Персонал

E/Деталь

Код детали

Код материала (FK) Код оборудования (FK) Табельный номер (FK) Наименование детали Дата изготовления Отметка о выполнении

Табельный номер

Фамилия

Имя

Отчество

Изготавливает / Изготовлена Должность

Дата рождения Сдельщик

Рис.П3.4. Логическая структура базы данных

Показатели топологического качества логической структуры базы данных представлены на рис.П3.5.

Структура жестко централизована (степень централизации равна 1), все сущности (отношения) замыкаются на сущность ДЕТАЛЬ. Для таких структур не существует ни одного цикла (ацикличность равна 1), что положительно скажется при построении запросов к базе данных. Кроме того, жестко централизованные структуры достаточно компактны (относительная компактность и достижимость больше 0,5). Это обстоятельство максимально упрощает (и ускоряет) поиск элементов информации в связанных таблицах.