Меньков А.В., Острейковский В.А. Теоретические основы автоматизированного управления

Подождите немного. Документ загружается.

180

Оператор преобразования F (t). На основе ал оритма обработ-

и информации и принципиальной схемы доментооборота

расрываем все операторы F(t). На аждом тате t

(j = 1–5) вы-

полняется один оператор F

(t).

, F

– передача оператор УПС. Вводим элементарню о-

манд f

– передача домента. F

= f

(D1/*).

, F

– ввод в память ЭВМ ло ина, сроа и сммы. Вводим

элементарню оманд f

– ввод домента в целом или полей

домента. F

= f

(D1/2, 02/3, 02/4).

, F

– перенос поля ло ин домента D1 в соответствющее

поле домента D2. Вводим элементарню оманд f

– перенос.

= f

(D1/2 → D2/2). t

, F

– ввод в че полей: фамилия адми-

нистратора, оплаченный сро, смма, дата. F

= f

(D2/1, D2/3,

D2/4, D2/5).

, F

– передача лиент D1/* и D2/*. F

= f

(D1/*, D2/*).

Резльтаты сводим в табл. 4.24 – оператор преобразования

системы.

Таблица 4.24

Примечание. В операции «Перенос», очевидно, необходимо азы-

вать два адреса: отда брать и да направлять. В табл. 4.24 это поазано

с помощью стрели.

Моделирющий алоритм. Разработаем неоторый автомат A,

состояниями оторо о были бы таты доментооборота t

, де

j = 1, 2, 3, 4, 5, а выходным алфавитом это о автомата – элемен-

тарные оманды f

, i = 1, 2, 3. Ка отмечалось выше, на аждом

тате t

выполняется одна или несольо оманд f

, имеющих не-

нлевой списо ар ментов. Эта информация определяется на

основе оператора преобразования F(t) (табл. 4.24). На тате t

ни-

аие элементарные оманды не выполняются. Данный автомат

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

D1/* D1/*

D2/*

D1/2

02/3

02/4

D2/1

D2/3

D2/4

D2/5

D2/2D1/2

лоин

181

о в зависимости от словий ϕ

. Причем если «да», то ϕ

, если

«нет», то . Поведение автомата описывается табл. 4.25, оторая

составляется на основе ал оритма обработи информации. В от-

личие от оманд f

, j

таже переводит систем из одно о состоя-

ния в др ое, но она не изменяет содержимо о ни одно о из до-

ментов.

Таблица 4.25

Таим образом, модель фнционирования ор анизационной

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

F(t), оператором сопряжения R и моделирющим ал оритмом

(автоматом).

Для ее реализации необходимо заодировать элементарные

оманды f

в виде подпро рамм, а сам автомат — в виде лавно о

модля. При работе автомата необходимо пользоваться операто-

ром F(t), чтобы определять элементарню оманд, выполняемю

в тещем тате, и оператором R, чтобы станавливать источнии

информации, подаваемой на входы доментов, обрабатываемых

с помощью f

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Перечислите цели и задачи стртрно(о анализа АСУ.

2. Рассмотрите пти совершенствования ор(анизационной, фнцио-

нальной, ал(оритмичесой стртр.

3. Назовите ровни описания стртры АСУ.

4. Сформлирйте формализованные способы описания стртры АСУ.

Номер

перехода

Тещее состояние Условие Следющее состояние

1 t

2—

3 t

4—

5 t

— t

6 t

— t

7 t

— t

8 t

— t

182

5. Каю цель преследет введение порядовой фнции?

6. Рассмотрите ал(оритм введения порядовой фнции.

7. Что представляет собой числовая фнция на (рафе?

8. Рассмотрите тополо(ичесю деомпозицию стртр АСУ.

9. Ка определяется порядо элементов?

10. Что является формальным признаом для выделения входных и вы-

ходных элементов потоа?

11. Приведите пример анализа потоов информации в АСУ.

12. Дайте харатеристи основных стртрно-тополо(ичесих хара-

теристи систем.

13. Приведите основные виды тополо(ичесих стртр.

14. Ка определяется связность стртры?

15. Каим образом определяется избыточность стртры?

16. Зачем вводят параметр ε

17. Что представляет собой омпатность стртры?

18. Ка определяется степень централизации стртры?

19. Проведите сравнительный анализ тополо(ичесих стртр.

20. Определите одноровневю схем сопряжения.

21. Что представляет собой мно(оровневая схема сопряжения?

22. Каим образом разрабатывается оператор преобразования?

23. Приведите ал(оритм разработи модели фнционирования ор(ани-

зационной системы.

24. Что представляет собой ал(оритм, моделирющий процесс фнци-

онирования ор(анизационной системы?

25. Рассмотрите пример модели фнционирования ор(анизационной

системы.

Глава 5

МОДЕЛИ СИНТЕЗА СТРУКТУРЫ АСУ

В лаве рассмотрены неоторые вопросы синтеза моделей

стртры АСУ. Сначала производится формализация общей

задачи синтеза в самом общем слчае. Затем разрабатываются

математичесие выражения для частных ритериев оптимиза-

ции и о раничений в частных задачах оптимизации. Основны-

ми параметрами в рассматриваемых моделях являются затраты

на реализацию фнциональных задач АСУ и время решения

этих задач. Различные омбинации этих параметров и состав-

ляют сть той или иной частной задачи синтеза оптимальной

стртры АСУ.

183

В резльтате изчения данной лавы стденты должны знать

подходы  постанове и решению задач подобно о ласса, меть

анализировать полченные резльтаты.

Авторы сознательно о раничили рами изла аемо о матери-

ала, посвященно о синтез моделей стртры АСУ. Это вызва-

но, во-первых, о раниченностью объема чебниа, во-вторых,

требованиями соответствюще о Госдарственно о образова-

тельно о стандарта высше о профессионально о образования и,

в-третьих, наличием специально о рса «Проетирование

АСОИУ».

5.1. Формализация общей задачи

синтеза стртры АСУ

Стртра системы — это способ ор анизации системы из от-

дельных элементов с их взаимосвязями, оторые зависят от рас-

пределения фнций и целей, выполняемых системой. Таим об-

разом, стртра (одно из определений) — это способ ор аниза-

ции цело о из составных частей.

В зависимости от задачи исследования в понятие стртры

системы может владываться различный смысл. Та, при разра-

боте стртры АСУ в это понятие входит, например, опреде-

ление множества элементов системы и связей межд ними, рас-

пределение задач, возла аемых на техничесие средства АСУ, по

ровням и элементам системы и выбор омплеса техничесих

средств, обеспечивающе о их своевременное решение.

Основными проблемами, возниающими при разработе

стртры АСУ, являются:

1) определение необходимо о числа ровней иерархии;

2) становление межд ровнями правильных взаимоотноше-

ний, что связано с задачами со ласования целей элементов раз-

личных ровней и оптимальным стимлированием их работы;

3) распределение ответственности;

4) выбор онретных схем правления и создание онтров

принятия решения;

5) ор анизация информационных потоов;

6) выбор соответствющих техничесих средств.

Все эти вопросы взаимосвязаны и образют сложню про-

блем.

Рассмотрим задач синтеза стртры АС в самом общем ви-

де. Для ее формализации введем следющие обозначения:

182

5. Каю цель преследет введение порядовой фнции?

6. Рассмотрите ал(оритм введения порядовой фнции.

7. Что представляет собой числовая фнция на (рафе?

8. Рассмотрите тополо(ичесю деомпозицию стртр АСУ.

9. Ка определяется порядо элементов?

10. Что является формальным признаом для выделения входных и вы-

ходных элементов потоа?

11. Приведите пример анализа потоов информации в АСУ.

12. Дайте харатеристи основных стртрно-тополо(ичесих хара-

теристи систем.

13. Приведите основные виды тополо(ичесих стртр.

14. Ка определяется связность стртры?

15. Каим образом определяется избыточность стртры?

16. Зачем вводят параметр ε

17. Что представляет собой омпатность стртры?

18. Ка определяется степень централизации стртры?

19. Проведите сравнительный анализ тополо(ичесих стртр.

20. Определите одноровневю схем сопряжения.

21. Что представляет собой мно(оровневая схема сопряжения?

22. Каим образом разрабатывается оператор преобразования?

23. Приведите ал(оритм разработи модели фнционирования ор(ани-

зационной системы.

24. Что представляет собой ал(оритм, моделирющий процесс фнци-

онирования ор(анизационной системы?

25. Рассмотрите пример модели фнционирования ор(анизационной

системы.

Глава 5

МОДЕЛИ СИНТЕЗА СТРУКТУРЫ АСУ

В лаве рассмотрены неоторые вопросы синтеза моделей

стртры АСУ. Сначала производится формализация общей

задачи синтеза в самом общем слчае. Затем разрабатываются

математичесие выражения для частных ритериев оптимиза-

ции и о раничений в частных задачах оптимизации. Основны-

ми параметрами в рассматриваемых моделях являются затраты

на реализацию фнциональных задач АСУ и время решения

этих задач. Различные омбинации этих параметров и состав-

ляют сть той или иной частной задачи синтеза оптимальной

стртры АСУ.

183

В резльтате изчения данной лавы стденты должны знать

подходы  постанове и решению задач подобно о ласса, меть

анализировать полченные резльтаты.

Авторы сознательно о раничили рами изла аемо о матери-

ала, посвященно о синтез моделей стртры АСУ. Это вызва-

но, во-первых, о раниченностью объема чебниа, во-вторых,

требованиями соответствюще о Госдарственно о образова-

тельно о стандарта высше о профессионально о образования и,

в-третьих, наличием специально о рса «Проетирование

АСОИУ».

5.1. Формализация общей задачи

синтеза стртры АСУ

Стртра системы — это способ ор анизации системы из от-

дельных элементов с их взаимосвязями, оторые зависят от рас-

пределения фнций и целей, выполняемых системой. Таим об-

разом, стртра (одно из определений) — это способ ор аниза-

ции цело о из составных частей.

В зависимости от задачи исследования в понятие стртры

системы может владываться различный смысл. Та, при разра-

боте стртры АСУ в это понятие входит, например, опреде-

ление множества элементов системы и связей межд ними, рас-

пределение задач, возла аемых на техничесие средства АСУ, по

ровням и элементам системы и выбор омплеса техничесих

средств, обеспечивающе о их своевременное решение.

Основными проблемами, возниающими при разработе

стртры АСУ, являются:

1) определение необходимо о числа ровней иерархии;

2) становление межд ровнями правильных взаимоотноше-

ний, что связано с задачами со ласования целей элементов раз-

личных ровней и оптимальным стимлированием их работы;

3) распределение ответственности;

4) выбор онретных схем правления и создание онтров

принятия решения;

5) ор анизация информационных потоов;

6) выбор соответствющих техничесих средств.

Все эти вопросы взаимосвязаны и образют сложню про-

блем.

Рассмотрим задач синтеза стртры АС в самом общем ви-

де. Для ее формализации введем следющие обозначения:

184

P — множество возможных принципов построения системы

или ее элементов. Возможные принципы бывают обычно заданы

и выбираются при синтезе системы;

π — выбранные принципы построения системы или ее

элементов. Очевидно, π ° P;

F — множество взаимосвязанных фнций (операций), вы-

полняемых системой. Каждом набор принципов π построения

системы соответствет неоторое множество фнций F(π), из

оторо о при проетировании системы необходимо выбрать под-

множество f ° F (π), достаточное для реализации выбранных при-

нципов π;

А — множество возможных взаимосвязанных элементов сис-

темы. Подобными элементами, например, мо т быть злы сис-

темы, техничесие средства, пнты обслживания, отдельные

исполнители, оллетивы и т. п.;

а — выбранные взаимосвязанные элементы системы. Введем

таже операцию отображения W элементов множества F на эле-

менты множества А. Оптимальное отображение должно обеспе-

чивать эстремм неоторой (или неоторых) целевой фнции

при выполнении заданных о раничений.

В общем слчае задача синтеза оптимальной стртры состо-

ит в определении:

π ° P ;(5.1)

f ° F (π); (5.2)

a ° A;(5.3)

[ f ° F (π)]W [a ° A]. (5.4)

Если заданы принципы построения системы, то синтез опти-

мальной стртры состоит в определении (5.2), (5.3) и (5.4). Ес-

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

фнции — то в определении (5.4) и (5.3). Если заданы принципы

построения системы, выполняемые ею фнции и элементы сис-

темы — то в определении (5.4), т. е. в нахождении оптимально о

отображения множества выполняемых фнций на множестве

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

Задача анализа состоит в определении харатеристи системы

при заданных словиях (5.1) — (5.4). Если для неоторых элементов

возниает проблема большой на рзи, то словия с (5.1) по (5.4)

должны читывать правила фнционирования элементов. В ряде

слчаев эти правила определяются при синтезе, посоль от них

может зависеть распределение фнций и взаимосвязей в системе.

185

5.2. Частные задачи синтеза

оптимальной стртры АСУ

Сложность синтеза оптимальной стртры АСУ приводит 

том, что на пратие ставят и решают более частные задачи син-

теза, таие, например, а оптимальное распределение возла ае-

мых на АСУ фнций по заданным ровням и  лам системы, оп-

ределение оптимальной реализации фнций в АСУ, выбор ом-

плеса техничесих средств, обеспечивающе о ачественню

реализацию фнций, и т. д.

Рассмотрим неоторые частные постанови задач формали-

зованно о распределения множества решаемых задач межд зла-

ми АСУ при различных ритериях и о раничениях.

5.2.1. Частные ритерии оптимизации

а) Минимизация затрат на реализацию задач в АСУ.

min , (5.5)

де i = — множество фнциональных задач, реализемых в

АСУ, j = — множество обслживающих злов системы прав-

ления, W

— затраты на реализацию i-той задачи в j-том злe.

Кроме то о, псть x

= ; x

= 1, если i-тая задача выполняется

в j-том зле и x

= 0 — в противном слчае.

б) Минимизация обще о времени решения всех задач АСУ

min , (5.6)

де t

— время решения i-той задачи в j -том зле.

в) Минимизация масимально о времени решения задач в АСУ

min max . (5.7)

Возможна оптимизация по более сложным ритериям, влю-

чающим (5.5) — (5.7), а таже использование ритериев более об-

ще о типа, таих, а полчение масимальной прибыли, обес-

печение требемо о времени отовности системы и т. д.

j 1=

∑

i 1=

∑

1 I,

1 J,

j 1=

∑

i 1=

∑

⎝

⎛

j 1=

∑

i 1=

∑

⎠

⎞

184

P — множество возможных принципов построения системы

или ее элементов. Возможные принципы бывают обычно заданы

и выбираются при синтезе системы;

π — выбранные принципы построения системы или ее

элементов. Очевидно, π ° P;

F — множество взаимосвязанных фнций (операций), вы-

полняемых системой. Каждом набор принципов π построения

системы соответствет неоторое множество фнций F(π), из

оторо о при проетировании системы необходимо выбрать под-

множество f ° F (π), достаточное для реализации выбранных при-

нципов π;

А — множество возможных взаимосвязанных элементов сис-

темы. Подобными элементами, например, мо т быть злы сис-

темы, техничесие средства, пнты обслживания, отдельные

исполнители, оллетивы и т. п.;

а — выбранные взаимосвязанные элементы системы. Введем

таже операцию отображения W элементов множества F на эле-

менты множества А. Оптимальное отображение должно обеспе-

чивать эстремм неоторой (или неоторых) целевой фнции

при выполнении заданных о раничений.

В общем слчае задача синтеза оптимальной стртры состо-

ит в определении:

π ° P ;(5.1)

f ° F (π); (5.2)

a ° A;(5.3)

[ f ° F (π)]W [a ° A]. (5.4)

Если заданы принципы построения системы, то синтез опти-

мальной стртры состоит в определении (5.2), (5.3) и (5.4). Ес-

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

фнции — то в определении (5.4) и (5.3). Если заданы принципы

построения системы, выполняемые ею фнции и элементы сис-

темы — то в определении (5.4), т. е. в нахождении оптимально о

отображения множества выполняемых фнций на множестве

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

Задача анализа состоит в определении харатеристи системы

при заданных словиях (5.1) — (5.4). Если для неоторых элементов

возниает проблема большой на рзи, то словия с (5.1) по (5.4)

должны читывать правила фнционирования элементов. В ряде

слчаев эти правила определяются при синтезе, посоль от них

может зависеть распределение фнций и взаимосвязей в системе.

185

5.2. Частные задачи синтеза

оптимальной стртры АСУ

Сложность синтеза оптимальной стртры АСУ приводит 

том, что на пратие ставят и решают более частные задачи син-

теза, таие, например, а оптимальное распределение возла ае-

мых на АСУ фнций по заданным ровням и  лам системы, оп-

ределение оптимальной реализации фнций в АСУ, выбор ом-

плеса техничесих средств, обеспечивающе о ачественню

реализацию фнций, и т. д.

Рассмотрим неоторые частные постанови задач формали-

зованно о распределения множества решаемых задач межд зла-

ми АСУ при различных ритериях и о раничениях.

5.2.1. Частные ритерии оптимизации

а) Минимизация затрат на реализацию задач в АСУ.

min , (5.5)

де i = — множество фнциональных задач, реализемых в

АСУ, j = — множество обслживающих злов системы прав-

ления, W

— затраты на реализацию i-той задачи в j-том злe.

Кроме то о, псть x

= ; x

= 1, если i-тая задача выполняется

в j-том зле и x

= 0 — в противном слчае.

б) Минимизация обще о времени решения всех задач АСУ

min , (5.6)

де t

— время решения i-той задачи в j -том зле.

в) Минимизация масимально о времени решения задач в АСУ

min max . (5.7)

Возможна оптимизация по более сложным ритериям, влю-

чающим (5.5) — (5.7), а таже использование ритериев более об-

ще о типа, таих, а полчение масимальной прибыли, обес-

печение требемо о времени отовности системы и т. д.

j 1=

∑

i 1=

∑

1 I,

1 J,

j 1=

∑

i 1=

∑

⎝

⎛

j 1=

∑

i 1=

∑

⎠

⎞

186

5.2.2. Ораничения в частных задачах синтеза

а) На связи межд задачами, т. е. задан раф

.(5.8)

б) На связи межд злами, т. е. задан раф

.(5.9)

в) На общие затраты на реализацию задач в AСУ

m . (5.10)

) На затраты на реализацию задач в злах

m . (5.11)

д) На за рз аждо о зла

m π

, j = , (5.12)

де λ

— интенсивность постпления i-той задачи на решение. Воз-

можны дополнительные требования  равномерности за рзи злов.

е) На общее время решения всех задач

m T. (5.13)

ж) На время решения отдельных задач

m τ

, i = . (5.14)

5.2.3. Первая частная задача синтеза

оптимальной стртры АСУ

Необходимо та распределить i задач i = межд j злами

j = , чтобы обеспечить минимм общих затрат (5.5) или ми-

нимм обще о времени решения (5.6) при исполнении о ра-

ничений на за рз аждо о из злов (5.12), или на затраты в

аждом j-том зле (5.11).

j 1=

∑

i 1=

∑

доп

i 1=

∑

доп

i 1=

∑

1 J,

j 1=

∑

i 1=

∑

i 1=

∑

1 I,

1 J,

187

Математичесая модель этой задачи может быть записана

следющим образом: найти

min (5.15)

при

m b

, j = , (5.16)

m 1, i = , x

= {1, 0}. (5.17)

В этих соотношениях:

— затраты (время решения) i-той задачи в j-том зле;

— допстимые затраты (за рза) в j-том зле;

— переменная, равная 1, если i-тая задача решается в j-том

зле, и равная 0 — в противном слчае.

Условие (5.17) означает, что аждая задача должна решаться

тольо в одном зле.

Наиболее добным для решения данно о ласса задач являет-

ся метод «ветвей и раниц». Применительно  данной задаче он

залючается в направленном движении по вершинам дерева,

полченно о птем фисирования части переменных x

, x

= {0, 1}.

Вершины перво о ровня полчают, поочередно зарепляя

первю задач за первым злом, вторым и т. д., т. е. фисиря

= 1 для j = 1, 2, 3, … при i = 1.

Вершины второ о ровня полчают, фисиря = 1 для

j =1, 2, 3, … при i = 2 и т. д. Для m аждой вершины находят оцен

+ , (5.18)

де i* — число рассмотренных ровней ветвления; = a

Страте ия ветвления может быть лчшена за счет использо-

вания специфичесих свойств рассматриваемой задачи, что с-

щественно при решении задач большой размерности.

Вначале из матрицы оэффициентов ||a

|| системы (5.15) ис-

лючаем все элементы, для оторых выполняется словие a

> b

i = , j = . При этом для любой строчи возможны следю-

щие варианты:

j 1=

∑

i 1=

∑

j 1=

∑

i 1=

∑

1 J,

i 1=

∑

1 I,

x′

″

ii*<

∑

ii*≥

∑

min

1 I, 1 J,

186

5.2.2. Ораничения в частных задачах синтеза

а) На связи межд задачами, т. е. задан раф

.(5.8)

б) На связи межд злами, т. е. задан раф

.(5.9)

в) На общие затраты на реализацию задач в AСУ

m . (5.10)

) На затраты на реализацию задач в злах

m . (5.11)

д) На за рз аждо о зла

m π

, j = , (5.12)

де λ

— интенсивность постпления i-той задачи на решение. Воз-

можны дополнительные требования  равномерности за рзи злов.

е) На общее время решения всех задач

m T. (5.13)

ж) На время решения отдельных задач

m τ

, i = . (5.14)

5.2.3. Первая частная задача синтеза

оптимальной стртры АСУ

Необходимо та распределить i задач i = межд j злами

j = , чтобы обеспечить минимм общих затрат (5.5) или ми-

нимм обще о времени решения (5.6) при исполнении о ра-

ничений на за рз аждо о из злов (5.12), или на затраты в

аждом j-том зле (5.11).

j 1=

∑

i 1=

∑

доп

i 1=

∑

доп

i 1=

∑

1 J,

j 1=

∑

i 1=

∑

i 1=

∑

1 I,

1 J,

187

Математичесая модель этой задачи может быть записана

следющим образом: найти

min (5.15)

при

m b

, j = , (5.16)

m 1, i = , x

= {1, 0}. (5.17)

В этих соотношениях:

— затраты (время решения) i-той задачи в j-том зле;

— допстимые затраты (за рза) в j-том зле;

— переменная, равная 1, если i-тая задача решается в j-том

зле, и равная 0 — в противном слчае.

Условие (5.17) означает, что аждая задача должна решаться

тольо в одном зле.

Наиболее добным для решения данно о ласса задач являет-

ся метод «ветвей и раниц». Применительно  данной задаче он

залючается в направленном движении по вершинам дерева,

полченно о птем фисирования части переменных x

, x

= {0, 1}.

Вершины перво о ровня полчают, поочередно зарепляя

первю задач за первым злом, вторым и т. д., т. е. фисиря

= 1 для j = 1, 2, 3, … при i = 1.

Вершины второ о ровня полчают, фисиря = 1 для

j =1, 2, 3, … при i = 2 и т. д. Для m аждой вершины находят оцен

+ , (5.18)

де i* — число рассмотренных ровней ветвления; = a

Страте ия ветвления может быть лчшена за счет использо-

вания специфичесих свойств рассматриваемой задачи, что с-

щественно при решении задач большой размерности.

Вначале из матрицы оэффициентов ||a

|| системы (5.15) ис-

лючаем все элементы, для оторых выполняется словие a

> b

i = , j = . При этом для любой строчи возможны следю-

щие варианты:

j 1=

∑

i 1=

∑

j 1=

∑

i 1=

∑

1 J,

i 1=

∑

1 I,

x′

″

ii*<

∑

ii*≥

∑

min

1 I, 1 J,

188

— ислючены все элементы а

, то да решение отстствет;

— остался лишь один элемент a

, он обязательно входит в оп-

тимальное решение, если оно сществет. Значение b

за-

меняется на b

—а

, и этот элемент в дальнейшем поисе

не частвет;

— осталось несольо элементов, они частвют в дальней-

шем поисе оптимально о решения.

5.2.4. Вторая частная задача синтеза

оптимальной стртры АСУ

Необходимо та распределить i задач i = межд j злами

j = , чтобы обеспечить минимм общих затрат (5.5) или ми-

нимм обще о времени решения (5.6) при выполнении о раниче-

ний на общее время решения (5.13) или общие затраты (5.10) со-

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

Математичесая модель этой задачи может быть записана

следющим образом: найти

min (5.19)

при

m B. (5.20)

m 1, x

= {1, 0}. (5.21)

В этих соотношениях:

— затраты (время решения) i-той задачи в j-том зле;

— время решения (затраты) i-той задачи в j-том зле;

B — общее время решения (затраты) всех задач.

Для решения этой задачи прежде все о бертся минимальные

элементы в аждой строе матрицы оэффициентов ||a

|| и про-

веряется выполнение словия (5.20) для соответствющих эле-

ментов матрицы оэффициентов ||b

||.

Если словие (5.20) выполняется, это и бдет оптимальным

решением.

Если словие (5.20) не выполняется, то из матрицы оэффи-

циентов ||a

|| и ||b

|| ислючают те элементы, оторые не мо т

1 I,

1 J,

j 1=

∑

i 1=

∑

j 1=

∑

i 1=

∑

189

войти ни в одно допстимое решение. Для это о последова-

тельно рассматриваются все элементы матрицы ||a

|| и проверя-

ется словие

+ b

+ m B, l = ,j = , (5.22)

де — минимальный элемент в соответствющей строе;

— рассматриваемый элемент, j ≠ l.

Иначе оворя, аждая задача последовательно зарепляется за

аждым из злов и проверяется выполнение словия (5.20) в лч-

шем слчае.

Если словие (5.22) наршается, то соответствющий эле-

мент b

не входит в допстимое решение и ислючается из мат-

рицы ||a

||. Из матрицы ||a

|| ислючается соответствющий эле-

мент а

Из словия (5.21) следет, что в аждой строе может быть

тольо один элемент. Поэтом min без чета выра-

жения (5.18) равен . Отсюда, если для элементов

одновременно выполняются словия a

l a

и b

l b

, (j ≠ l), то

эти элементы мо т быть ислючены из рассмотрения.

Хотя ислючение элементов не все да приводит  опти-

мальном решению, однао объем вычислений резо сораща-

ется.

Далее использется метод «ветвей и раниц». В отличие от

предыдщей задачи, ветвление осществляется с четом о рани-

чения (5.20), что сщественно соращает число рассматриваемых

вариантов. Оцена для аждой вершины находится по элементам

матрицы (5.19) анало ично предыдщей задаче (5.18). О раниче-

ние при этом имеет вид

+ , (5.23)

де i* — ровень ветвления;

= b

i 1=

l 1−

∑

il1+=

∑

1 I, 1 J,

j 1=

∑

i 1=

∑

min a

j 1=

∑

i 1=

∑

ii*<

∑

ii*≥

∑

min

188

— ислючены все элементы а

, то да решение отстствет;

— остался лишь один элемент a

, он обязательно входит в оп-

тимальное решение, если оно сществет. Значение b

за-

меняется на b

—а

, и этот элемент в дальнейшем поисе

не частвет;

— осталось несольо элементов, они частвют в дальней-

шем поисе оптимально о решения.

5.2.4. Вторая частная задача синтеза

оптимальной стртры АСУ

Необходимо та распределить i задач i = межд j злами

j = , чтобы обеспечить минимм общих затрат (5.5) или ми-

нимм обще о времени решения (5.6) при выполнении о раниче-

ний на общее время решения (5.13) или общие затраты (5.10) со-

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

Математичесая модель этой задачи может быть записана

следющим образом: найти

min (5.19)

при

m B. (5.20)

m 1, x

= {1, 0}. (5.21)

В этих соотношениях:

— затраты (время решения) i-той задачи в j-том зле;

— время решения (затраты) i-той задачи в j-том зле;

B — общее время решения (затраты) всех задач.

Для решения этой задачи прежде все о бертся минимальные

элементы в аждой строе матрицы оэффициентов ||a

|| и про-

веряется выполнение словия (5.20) для соответствющих эле-

ментов матрицы оэффициентов ||b

||.

Если словие (5.20) выполняется, это и бдет оптимальным

решением.

Если словие (5.20) не выполняется, то из матрицы оэффи-

циентов ||a

|| и ||b

|| ислючают те элементы, оторые не мо т

1 I,

1 J,

j 1=

∑

i 1=

∑

j 1=

∑

i 1=

∑

189

войти ни в одно допстимое решение. Для это о последова-

тельно рассматриваются все элементы матрицы ||a

|| и проверя-

ется словие

+ b

+ m B, l = ,j = , (5.22)

де — минимальный элемент в соответствющей строе;

— рассматриваемый элемент, j ≠ l.

Иначе оворя, аждая задача последовательно зарепляется за

аждым из злов и проверяется выполнение словия (5.20) в лч-

шем слчае.

Если словие (5.22) наршается, то соответствющий эле-

мент b

не входит в допстимое решение и ислючается из мат-

рицы ||a

||. Из матрицы ||a

|| ислючается соответствющий эле-

мент а

Из словия (5.21) следет, что в аждой строе может быть

тольо один элемент. Поэтом min без чета выра-

жения (5.18) равен . Отсюда, если для элементов

одновременно выполняются словия a

l a

и b

l b

, (j ≠ l), то

эти элементы мо т быть ислючены из рассмотрения.

Хотя ислючение элементов не все да приводит  опти-

мальном решению, однао объем вычислений резо сораща-

ется.

Далее использется метод «ветвей и раниц». В отличие от

предыдщей задачи, ветвление осществляется с четом о рани-

чения (5.20), что сщественно соращает число рассматриваемых

вариантов. Оцена для аждой вершины находится по элементам

матрицы (5.19) анало ично предыдщей задаче (5.18). О раниче-

ние при этом имеет вид

+ , (5.23)

де i* — ровень ветвления;

= b

i 1=

l 1−

∑

il1+=

∑

1 I, 1 J,

j 1=

∑

i 1=

∑

min a

j 1=

∑

i 1=

∑

ii*<

∑

ii*≥

∑

min

190

5.2.5. Третья частная задача синтеза

оптимальной стртры АСУ

Необходимо та распределить i задач i = межд j злами

j = , чтобы обеспечить минимм общих затрат (5.5) или мини-

мм обще о времени решения (5.6) при выполнении о раниче-

ний на общее время решения (5.13) и за рз злов (5.12), либо

на общие затраты (5.10) и за рз злов (5.12) соответственно.

Математичесая модель этой задачи может быть записана в

следющем виде: найти

min (5.24)

при

m B, (5.25)

m c

, j = , (5.26)

m 1, x

= {0,1}. (5.27)

Для решения этой задачи прежде все о из матриц оэффици-

ентов ||a

||, ||b

||, ||c

|| ислючаются элементы, оторые заведомо

не мо т войти в оптимальное решение. Ислючение элементов

и с

из матриц систем (5.25) и (5.26) осществляется анало ич-

но рассмотренной выше, т. е. ислючаются все элементы, для о-

торых не выполняется словие (5.22). Оцена для матрицы оэф-

фициентов (5.24) находится анало ично оцене системы (5.18) в

первой задаче.

5.3. Примеры частных задач синтеза

оптимальной стртры АСУ

Пример 1.

Сначала решим методом «ветвей и раниц» след-

ющю задач: найти минимм

min (5.28)

Пример имеет целью продемонстрировать процедр ветвления.

1 I,

1 J,

j 1=

∑

i 1=

∑

j 1=

∑

i 1=

∑

1 J,

∑

j 1=

∑

i 1=

∑

191

при

= 1, (5.29)

= 1, (5.30)

= {0, 1}, (5.31)

= . (5.32)

Условие (5.29) означает, что аждый зел может решать толь-

о одн задач. Условие (5.30) означает, что аждая задача может

решаться тольо в одном зле.

Бдем изображать множество вариантов ржами, в верхней

части оторых проставлен номер множества, а в нижней — зна-

чение нижней раницы (рис. 5.1).

i 1=

∑

1-ÿ çàäà÷

çà óçëîì 4

2-ÿ çàäà÷à

çà óçëîì 3

3-ÿ çàäà÷à

çà óçëîì 1

4-ÿ çàäà÷à

çà óçëîì 2

Рис. 5.1. Процедра ветвления