ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 98
Скачиваний: 1
‘1'ав как величины Clj Сесть целые чиода, то решение долж но быть целочиолеаным. В связи о этим, если отдельные компо- ' вентн не целые числа, то они должны оыть приведены к целым пу
тем умножения на коэффициент 10^ |
(где |
У |
- максимальное чис |
||
ло разрядов пооде запятой для одной из компонент). |
|||||
Однако симплекс-метод приводит непосредственно к цело-, |
|||||
численному решении лишь немногих задач, |
|
|
|
||
2 .* . Нормирование матриц параметров алгоритмов |
|||||
Пусть задано некоторое множество |
|
|
наборов проотых |
||
алгоритмов |
|
|
|
|
|
Е й =* < ОСj tj» > , |
|
( t - l , |
2.*— » ма ) , |
||
I |
|
q |
. |
1, |
2»..-» 4 ) . |
и пуоть множество решений алгоритма |
И |
описано системой |
|||
проотых матриц |
X u # |
*• • |
X m if |
||
|
|||||
X , |
X z i f • • • |
XttUf |
|||
|
|
|
|
|
|
XiHif |
Хгпгр |
• • |
• |
|
|
Води требования к отдельным параметрам алгоритма М не заданы, одвахо необходимо выбрать из каждого набора но од ному алгоритму оптимальному в некотором смысле, то решим зту задачу следующим образом.
ПривадЖкомпонанты воех^матриц~^Г''к единой норме, качестве которой для каждой матрицы выберем максимальное значе ние компоненты в этой м а т р и ц е max. Пронормировав вое остальные кошоненты матриц, получим следующую оиотему проотых матриц-норм:
Ei
X'jifma»
& & £.'
RjcfeЩ if max
|
Х т р |
|
|
^4j>mor |
|
Обозначив |
OCil-f |
|
X № ma* |
||
|
||
|
b i t ? |
|
Нзс, |
S ia f |
|
|
8 i« if |
- 53 - |
Em |
|
U |
||
OCaip |
^Crnip |
|
OCjLjitnax |
Х Щ та% |
|
& m . . . . |
Х т гр |
|
OCjtf"*»* |
||
|
0(J^i-ymax |
|
j> max |
~ b |
, |
имеем |
|
b a tj1 • ■• B n tif
bm *f
’ ‘ *
Для определения эффективности простого алгоритма соста вим сушу равнозначных пронормированных компонент, принадле
жащих кортежу одного алгоритма. Обозначив через |
Н ф ^1 про |
нормированную эффективность Е j i —го алгоритма, |
имеем |
н Ф р - Z B ^ , |
|
Иа каждого j -го набора ф^{,выбирается по одному
алгоритмы которых и будем очитать оптималь
н ей по норме. |
|
Еоли по одному из параметров алгоритма |
М наложено |
ограничение, то данный параметр не нормируется. |
Остальные пак* |
раметры нормируются я для них составляется сумма норм
|
Н Фi и “ |
£f - .i 6|**’ |
( ? + ? ') ■ |
где |
P - параметр, |
aa который налояeao ограничение. Из |
|
H<ty составляется матрица. Тогда задачу выбора оптимального)
по норне варианта модно решить из системы двух матриц |
||||
|
E t |
e * |
* |
Cm |
|
X tlf0 |
X i t f * |
• • |
|
Х ?° ~ |
|
X z z f a |
• |
•X m•z f |
|
|
• |
• X ♦m „ |
|
|
|
X z t i t f |
||
|
|
bz I f |
4 , 4 |
b m i f |
Н |
ф B 2if- |
Ъзлf |
4 4 4 |
b m z f |
ЬпМ"?
одним из приведенных методов/ минимизируя параметр, полученный
из матрицы М ф |
. ' |
|
Таким яе образом"можно найти оптимальные по норме ал |
||
горитмы |
ELjl , |
если наложены ограничения на несколько пара |
метров , |
что приводит к росту системы матриц. |
|
Данный метод нозволяет быстрее других находить оптималь ные по норме варианты, которые могут быть и не оптимальны в смысле нормированной эффективности. _____
2 .5 . Выбор управляемей машины для эффективной реализации алгоритмов управления
Вопросы описания эффективности алгоритма,рассмотренные в начале настоящей главы,применяю! не только к оптимизации алгорит ма управленйя,на\я к целенаправленному выбору варианта эффектив
ной реализации алгоритма управления на одной из заданного парка
г---.----------- |
-55 - |
управляицих вычислительных машин. Однако в данном олучае опи санию эффективности подлежит не только алгоритм, но ■ УВМ о точки врения реализации заданного алгоритма на конкретной ма шине»
1 . Задачу эффективной реализации исходного алгоритма на одной из множества управляющих машин сформулируем следую
щим образом. |
|
|
|
Пусть имеетоя парк из ГО |
управляющих вычислительннх |
||
машин. Для каждой |
L -й машины ( |
t = 1 , 2 , . . . , m |
) из |
вестны ее технические характеристики и набор реализуемых опера ций (оиотеыа команд)
O i -
где j - номер операций ( j « 1 , 2 , . . . , p t ) .
Кроме того, заданный класс алгоритмов управления пред ставлен в виде математических зависимостей.
Задача оостоит в том, чтобы из имеющегося парка УВЫвы брать ту, на которой заданный алгоритм управления реализовался он наилучоим образом, т .е . имея наименьшим время реализации, программа алгоритма разместилась бы в памяти машины, результа ты вычислений имели бы погрешность меньше допустимой.
Одним из опоообов решения этой задачи является ооставле ние программ для каждой машины. Оценив эффективность каждой программы,путем сравнения выбираем ту или иную УВМ. Однако этот путь требует значительного времени и больших экономических затрат.
В настоящем параграфе рассматривается более экономичный метод выбора варианты для аффективной реализации алгоритма.
2 . Супрооть метода. Программу алгоритма управления со ставим для гипотетической машины, которую ватем мохно формаль но транспонировать на июоую из парша УВМ. Сиотеыа команд ( Go )
гипотетической машина определяется из
1
56 -
где |
| |
|
= 1 , 2 , . . . , Р» . |
|
|
|
|
|
||
|
|
Сравнение транспонированных программ для конкретных |
|
|||||||
УВМ иудем осуществлять по трда критериям (показателям): |
|
|||||||||
|
|
1 . |
Погрешность вычисления - |
Д |
(абсолютная или относи |
|||||
|
|
|
|
|
|
|
тельная) ; |
|
|
|
|
|
2 . |
Объем долговременной памяти |
( D ° ), |
выраженный в |
|
||||
чиоле ячеек. |
. |
|
|
|
|
|
|
|||
|
|
3 . |
Время реализации ( Т i , "выраженное в единицах |
|
||||||
времени реализации наиболее короткой операции. |
|
|
|
|||||||
|
|
Для определения этих показателей алгоритма опишем эф |
|
|||||||
фективность отдела шс ее элементарных участков кортежами |
|
|||||||||
|
|
|
|
А ~ < л , д » |
хК , > , |
|
|
|
||
где |
Д |
- |
погрешность; |
|
|
|
|
|
||
K |
д |
- |
объем программы (чиоло команд); |
.= , |
Т |
) { |
||||
- |
I |
оистемаW - |
констант ( |
1 |
,2,^ . . |
|||||
X- время реализации.
Вкачестве элементарных участию программы алгоритма
для гипотетической машины примем ее отдельные операции (коман ды). Эффективность оистемы команд (СК) (?«* выразим через пока затели СК G i заданного парка машин. Это мг зо предотавить н виде следующей оистемы кортежей:
4. |
Д н |
ди К и |
tT u |
> |
|
<• Д 12 |
diZ |
K li |
Kiz |
> |
|
< A i m |
d i m |
Kifti |
'C’im |
> |
|
|
|
|
|
|
(2 .II) |
< Д а ь 0 2 1 K at X ai У |
|||||
< |
Д и а 0 a a |
К аа |
|
> |
|
< |
Д ап дат Кгт |
> |
|||
• Ь.
г
|
< Д р о ! |
6pol |
Kpol |
t f o i |
> |
|
^ орс «^< Л Р°г |
Ф°2 KP°Z Z ?et |
> |
||
|
< Д p0M |
dpottl Kpein tpoffl > |
|||
ИЛИ |
< A j L |
d j i |
Kj-i. |
£ j i > |
|
. |
^ C- ~ i, 2; >*> УЩ |
j |
|
Pe ) . |
|
|
|
||||
|
Следует заметить, что -CK |
(jo |
гипотетической машины |
||
должна быть совместимой с |
системой команд любой ЦВМ из имею |
||||
щегося парка. Совместимость системы команд предполагает так же совместимость операций.
Совместимыми операциями будем называть те, которые мо гут быть заменены в t -й машине по своему смыолу либо одной командой, либо программой (подпрограммой).
Например, операция сложения из Go является совместимой с операцией сложения практически любых УВМ. Совместимыми яв ляются также операции деления и элементарные функции, т.к. они могут быть представлены в t -й машине одной командой или программой (подпрограммой).
Однако совместимость СК Go будем относить не только к СК парка рассматриваемых УВМ, но и к исходному алгоритму. Эффективность (сиотема 2 .II) оценивается для тех операций Ц\
G o , которые входят в состав программы алгоритма. Операций СК Go , не участвующие в вычисления, нет надобности оцени
вать по эффективности, и они могут быть вычеркнуты из списка
Go . Вели |
вое оставшиеся операции, |
используемые в програм |
ме. могут быть |
реализованы на любой из |
ftl УВМ, то такую СК |
Go будем называть совместимой.
Одна и та же команда СК Go может находиться в различных соотношениях к соответствующей операции СК Ос .
Будем различать совместимые, программно-совместимые, подпрограммно-совместимые и несовместимые операции. Дадим их определения. \ ,