Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

.pdf
Скачиваний:
20
Добавлен:
20.10.2023
Размер:
8.54 Mб
Скачать

 

Например, рассматривается отображение для вершины

х{

про­

изведения графов

G(X,

Г). Отображениями

вершины Х\

в

графе

G\

являются

х2

и

х3 ,

т. е.

 

 

 

 

 

 

 

 

 

 

Г1JC1 =

{л:2, Хз}.

 

 

 

 

В этом случае

необходимо рассмотреть

отображения

вершин

х2

и х3 в графе

G2(X2,

Г2). Пусть

этими отображениями

в

графе

G2

являются

хх

и лс4

соответственно, т. е.

 

 

 

 

 

 

 

А * 2 = ф ' 1 }

и

Г2х3={хА}.

 

 

 

Следовательно, отображениями вершины хх в графе

G(X, Г)

будут вершины

хх

и

xit т. е.

 

 

 

 

 

 

 

 

 

 

Гхх = {хх,

х4}.

 

 

 

Матрицей смежности графа G(X, Г), содержащего п вершин, называется квадратная матрица А с п строками и п столбцами, в которой элементы а^, стоящие на пересечении i-й строки и /-го столбца, численно равны количеству дуг графа, идущих из г'-й вер­ шины в /-ю вершину. Так, для изображенного на рис. 1 графа мат­ рица смежности имеет следующий вид:

 

1

2

3

4

 

1

1

1

1

1

4

2

0

0

0

0

0

3

0

1

0

1

2

4

0

0

1

0

1

 

1

2

2

2

 

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

полустепень

исхода вершины ж,-

численно

равна сумме

элементов

i-й

строки

матрицы

 

 

 

 

 

P-(Xi)

= 2 а *

 

 

а

полустепень захода — сумме элементов

/-го столбца

при / = i

 

 

P+(Xi)

= 2 я* (* =

/ ) .

 

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

20

Две

матрицы

смежности A = (af)

и В = (Ь^),

соответствующие

графам

Gi(X,

U)

и G2(X,

V),

могут

быть

просуммированы,

если

они одного и того же размера, т. е. имеют

одинаковое

количество

строк

и

столбцов.

 

 

 

 

 

 

 

 

 

 

Сумма двух 'матриц смежности А + В определяется

следующи­

ми правилами:

 

 

 

 

 

 

 

 

 

 

 

 

1. Число элементов суммы матриц

равно

числу элементов

ис­

ходных матриц, т. е. ПА+В =

ПА =

ПВ.

 

 

 

 

 

 

2. Каждый элемент суммы матриц

получается

суммированием

соответствующих

элементов исходных

матриц, т. е.

 

 

 

 

 

 

 

 

 

Ci5 —cii5

+bi з

 

 

 

 

Так, для

двух

графов

G{(X,

 

U)

и

G2(X,

V),

представленных

матрицами

смежности

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

3

 

 

 

 

 

1

2

3

Л =

1

 

 

0

2

0

 

 

 

В=

1

0

0

0

 

 

2

 

 

0

0

0

 

 

 

 

2

1

0

1

 

 

3

 

 

1

1

0

 

 

 

 

3

0

0

1

сумма

этих

матриц

смежности

будет иметь вид:

 

 

 

 

 

 

 

 

 

 

 

1

 

2

3

 

 

 

 

 

 

 

 

А+В

=

1

 

0

 

2

0

 

 

 

 

 

 

 

 

 

 

2

 

I

 

0

1

 

 

 

 

 

 

 

 

 

 

3

 

1

 

1

1

 

 

 

Очевидно, что граф G(X, Г) представляет собой объединение графов Gi(X, if) и G2(X, V), т. е. правила его построения могут быть записаны в виде:

1)ХА+В = ХА — ХВ',

 

 

 

2)

Гх^ич

U

V*i •

 

Указанный

граф

G(X,

Г) может

быть

построен по отображени­

ям исходных

графов:

 

 

 

 

 

 

Г х , = [/х,

U Vxi = {xl,x2}

U { 0 } =

{*1Л};

Гх2=их2

у

Vx2={0}

U их3}

= {хих3} ;

Гх3=

Ux3

(J

Vx3=

их2}

у

3}

=

их2,Хг}.

2!

Следовательно, операция суммы матриц смежности соответст­ вует операции объединения графов, представленных этими матри­ цами:

 

 

C=A+B—*-.G

= Gi U G2

Две

матрицы

смежности А = (а^)

и В = (Ь^), соответствующие

графам

Gi(X, U)

и G2(X, V),

могут

быть перемножены в том слу­

чае, если число столбцов матрицы А равно числу строк матрицы В.

 

 

При этом матрица-произведение С=АхВ

имеет

то же

количе­

 

ство строк, что и Л, и то же количество столбцов, что и

В.

 

 

 

Полезно напомнить, что элемент С,-* матрицы-произведения

по­

лучается

суммированием

произведений

всех

элементов

i

(строки

 

матрицы Л) на

соответствующие

элементы

к (столбцы

 

матри­

 

цы

В), т.

е.

 

 

 

 

 

 

 

 

 

 

 

, j

r

\

 

 

 

 

Ct

=

2

а,'Ь}

 

 

 

 

 

Г

""Si

 

 

 

 

 

 

j = l

 

 

 

 

 

 

 

 

Рассмотрим произведение матриц на следующем примере. Да­

 

ны

графы

G\(X,

U),

G2(X,

V)

и

соответствующие

им

 

матрицы

 

смежности А и В:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

3

 

4

 

 

 

1

2

 

3

4

 

 

1

0

1

1

 

0

 

 

1 "

0

0

 

0

0

Л--

2

0

0

0

 

0

 

В=

2

0

0

 

1

1

 

 

3

0

0

0

 

1

 

 

3

1

1

 

0

1

 

 

4

0

1

0

 

0

 

 

4

0

1

 

0

0

 

 

Произведение

данных

матриц

смежности

имеет

вид:

 

 

 

 

 

 

 

 

 

 

1

 

2

3

4

 

 

 

 

 

 

 

 

 

1

 

1

 

1

1

2

 

 

 

 

 

 

 

 

 

2

 

0

 

0

0

0

 

 

 

 

 

 

 

 

 

3

 

0

 

1

0

0

 

 

 

 

 

 

 

 

 

4

 

0

 

0

1

1

 

 

 

 

22

Легко показать, что отображения для любой вершины этого графа G(X, Г) удовлетворяют условию:

 

 

 

 

 

Гх{=У{ин),

 

 

 

 

 

 

 

где

U4 — отображение для рассматриваемой

вершины в

графе

 

GX(X,

U);

 

 

 

 

 

 

 

 

 

 

 

 

V(UH)—отображение

 

 

графа

G2(X,

V)

для

вершины,

являю­

 

щейся

отображением

рассматриваемой

в

графе

 

GX(X, U).

G(X,

Г)

имеем:

 

 

 

 

 

 

Для вершин

графа

 

 

 

 

 

 

 

Гхх = V (Ux{) = V (а-2 , Х3)

= 3,

х4,

хи

х2,

ХА}

;

 

 

 

 

rx2=V(Ux2)

 

= V(0)

=

0;

 

 

 

 

 

 

 

rx3=V(U,3)

 

= V(xi)

=

{x2};

 

 

 

 

 

/ х 4 = У ( ^ * 4 ) = П * 2 ) = { и з о ­

 

 

 

 

графически

отображения

графа G(X,

Г) для каждой его вер­

шины означают, что существует путь,

составленный из

двух дуг,

одна из которых принадлежит графу

GX(X,

U),

а другая —графу

G2(X,

V). Например,

дуга

3х2) графа

G

соответствует

пути, со­

ставленному из дуги (x3Xi)

 

графа

Gi и дуги

4х2)

графа

G2.

Важными понятиями

теории графов

являются

понятия

дерева

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

Ориентированный граф

G(X,

U) называется

прадеревом

с кор­

нем х\^Х,

если:

 

ХхфХ\

 

 

 

1)

в каждую

вершину

заходит ровно

одна дуга;

 

2)

в

Х\ не заходит

ни

одна

дуга;

 

 

3)

граф G(X, U) не содержит контуров.

 

 

Относительно деревьев можно доказать следующие простые ут­

верждения:

 

 

 

 

 

 

1. Всякая пара вершин в дереве соединена

цепью и

притом

только

одной.

 

 

 

 

 

 

Действительно, так как дерево — связный граф, то хотя бы одна

цепь существует. Но если бы их

было две, то они образовали бы

цикл,

а

дерево

не имеет

циклов.

 

 

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

3.Дерево Gen вершинами имеет (п1) ребро.

Вершина X графа G называется висячей, если в G существует единственное ребро, инцидентное X.

§ 1. 5. ПОНЯТИЕ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ

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

23

ритмов и системы автоматизации программирования и отладки алгоритмов и программ.

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

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

1.Модульность.

2.Адаптируемость.

3.Модифицируемость.

4.Расширяемость.

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

модульности

заключается

в том,

что любая

программа на

языке

исполнительной системы

может

быть собрана из модулей.

При

этом система

средств программирования не

предусматривает

ино­

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

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

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

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

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

Принцип модифицируемости заключается в том, что любой мо­

дуль можно

изменять, исправлять,

оставляя неизменным

лишь

принцип организации модулей, принятый для данной системы.

Принцип

расширяемости — это

возможность

расширения

мо­

дуля.

 

 

 

 

 

 

 

Математическое обеспечение подразделяется

на

общее и

спе­

циальное

математическое

обеспечение.

 

 

 

Общее

математическое

обеспечение представляет

собой

сово­

купность

программных средств, предназначенных

для автоматиза-

24

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

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

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

обслуживающую

систему для отладки,

контроля и

диагностики

неисправностей

в ходе работы

ЭВМ.

 

 

 

 

Специальное математическое обеспечение состоит из комплек­

тов

прикладных

программ, называемых

пакетами.

 

 

В

настоящее

время принята

следующая

классификация

паке­

тов:

 

 

 

 

 

 

 

группа I — пакеты программ, расширяющие возможности

основ­

ных

операционных систем;

 

 

 

 

 

группа I I — пакеты прикладных программ

общего

назначения,

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

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

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

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

Системная организация программ пакета зависит от выбранной структуры: простой или сложной.

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

Пакет сложной структуры включает в себя ведущую програм­ му и может содержать:

ведущую программу; процессор с входного языка;

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

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

25

системе (ОС)

для вызова той или иной фазы -пакета и

передачи

ей управления.

 

Процессор

предназначен для обработки программы,

написан­

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

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

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

агностики

ошибок.

 

 

 

 

 

 

При разработке пакета могут быть выделены следующие уров­

ни языков:

 

 

 

 

 

 

языки,

используемые

для

написания

программ

пакетов. Ими

являются

исходные языки основных операционных систем: КОБОЛ,

АЛГОЛ, ФОРТРАН, PL/I, ассемблер и др. Разные

модули пакета

могут быть написаны на различных языках;

 

язык, управляющий заданиями для ввода программы пользова­

теля в систему и ее инициирования;

 

 

 

 

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

пользователем

параметров и управляющей информации

для

настройки пакета на

решение

конкретной задачи.

 

 

 

 

 

Пакеты функционируют под управлением основных операцион­

ных систем и должны удовлетворять стандартным

соглашениям,

предъявленным этими

системами к

программам

пользователя.

К ним относятся соглашения

о функциональном

распределении

регистров, о передаче информации от одной

программы к другой,

о правилах образования

задач и их

приоритетах,

соглашения об

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

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

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

Операционная система проектируется для работы в различных

26

режимах. Поэтому на вход системы может одновременно

поступить

большое количество работ, выполнить которые

сразу

невозможно

из-за недостаточного количества ресурсов.

К

ресурсам

системы

относятся центральный процессор,

место

в

основной

и

вспомога­

тельной памяти, отдельные программы,

устройства

управления

вводом-выводом, каналы, таймер, консоль оператора.

 

 

 

Вся работа, поступающая на вход системы, делится на незави­

симые задания, являющиеся единицей работы

для операционной

системы. Задания записываются

с помощью

управляющих

карт.

В пакетном режиме они группируются

для

ввода

в систему во

входном потоке заданий. Поток заданий — совокупность

несколь­

ких заданий, включающая управляющие

операторы,

тексты

про­

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

Составная часть задания, выполняемая самостоятельно, назы­ вается шагом задания. Шаги одного задания могут быть взаимо­ зависимы. В единицу времени всегда выполняется один шаг одно­ го задания.

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

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

заданий, преследующих основную цель — обеспечение

эффектив­

ной загрузки оборудования: пакетная обработка,

пакетная обра­

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

Режим пакетной обработки предусматривает

такую

организа­

цию прохождения заданий, при которой на входе

системы имеется

пакет заданий, последовательно пропускаемый через машину. Су­

щественной чертой пакетной обработки является

то,

что

каждая

задача,

формируемая из

одного задания, имеет

в своем

распоря­

жении

более или менее

все ресурсы системы,

за

исключением

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

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

27

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

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

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

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

Глава II И С С Л Е Д О В А Н И Е ПОТОКОВ

И Н Ф О Р М А Ц И И

§ 2. 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ

Применение электронно-вычислительных машин в эко­ номике имеет важное народнохозяйственное значение. В послед­ ние годы среди широкого круга проблем внедрения электронно-вы­ числительных машин в сферу управления производством ведущее место занимает проектирование автоматизированных систем уп­ равления (АСУ).

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

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

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

ботке и внедрению проекта автоматизированной

системы управле­

ния предшествует

тщательное

изучение

объекта

автоматизации.

В

процессе изучения должны быть определены:

а)

логика

процессов, подлежащих

автоматизации;

б)

схема

информационных потоков;

 

в)

объемы

перерабатываемой информации;

 

г)

алгоритмы

обработки

информации;

 

д)

возможность применения тех или иных

экономико-матема­

тических методов.

 

 

 

 

Полученные в

результате

изучения

материалы являются осно­

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

29

Соседние файлы в папке книги из ГПНТБ