Файл: Основы теории алгоритмов учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 105

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

 

 

 

 

 

-

70 -

 

 

 

 

 

 

 

4 .

Найти хотя бы одну подматрицу такую,

что

 

 

 

 

Nk Nkh^ O

,

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

L

A

kN

>0»

(5#6)

 

г д е

N к обозначает определитель

порядка

ty '-i

, полученный

 

из

&

 

отбрасыванием

ее

 

к -о й

отроки.

 

 

 

 

 

Так как в нашем случае

оЦ =

I»

и только при h =р

,

то

условие

^

 

 

 

 

 

 

 

 

 

 

 

 

 

 

^ 7

cUfcl Мк1 >

О

 

 

 

 

 

 

 

 

 

К=1

 

 

 

 

 

В

строки р

 

справедливо лишь при наличии в матрице

 

Это обстоятельство позволяет уменьшить перебор матриц

 

при поиске условия несовместимости системы (3 .1 ). В случае

 

системы строгих однородных неравенств

 

 

 

 

 

 

 

т

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i-L

Qhi

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

условие несовместимости будет

 

 

 

■*

 

 

 

 

 

N k Wk+1 < О ,

( 1 4 К 6 9 - П

 

 

 

 

 

Отсвда

следует,

что

задача определения условий выгодно'

го

применения

И -ей

машины есть

задача

отыскания области

 

А э

с

ее количественной характеристикой

$э . Рассмотрим

некоторые способы нахождения области

А э .

 

 

 

 

Простейшим способом является использование известных

 

при шов

при решении оиотем линейных неравенств.

В зависимости

от

конкретных условий

(число

переменных» число

неравенств)

в

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

 

 

71

-

где О i и h i

-

соответственно верхний и нижний пределы

для переменной

X

I . Очевидно,

что такой метод может быть |

использован лишь при малом количестве переменных и малом чис­ ле неравенств.

При достаточно больших числах переменных и неравенств' иногда бывает удобным использование следующего способа. Каж­ дое из неравенств системы (3.1) разрешается относительно ка­ кой-либо из переменных . Выбор этой переменной зависит ; от типа анализируемой структуры и удобства оценки в конечном

виде. Обозначая

индекс

выбранной переменной через

|

, по­

лучим из системы

(3 .1)

соотношения вида

 

 

 

m

 

 

 

1 У? - ч!

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

ются в виде

соотношений переменной Х^‘ и всех остальных пере­

менных

.

Особое значение для выделения области Дэимеют методы линейного программирования. Графические методы обладают тем

достоинством,

что о их помощью можно найти

не только

экстре- г

мальное значение критерия F ( A , M )

, но

и значения

S 9 .

При этом S э

можно выразить в виде

относительного значения,

представляющего собой отношение площади (или объема) выпуклой области с учетом конкретных ограничений (3.1) к значению пло­

щади

(объема)

области А э , когда ограничения (3 .1) не умень­

шают

облаоти,

заданной уоловием

 

 

- 72

 

 

2

# 1 - 1 .

 

 

В случае даух переменных обяаоть Аэ

представляется в

виде

отрезка прямой

X t+ Х а ,- 1 . При этом

ограничении (3.1)

есть

полуплоскости,

образованные прямыми, проходящими через

начало координат. Условия наличия отрезка, принадлежащего вдем

полуплоскостям одновременно,

выражаются соотношением (3 .6 ),

Относительная величина

5 э

вычисляется как отношение та­

кого отрезка к длине отрезка

прямой

<X)i + X z — 1

при

О ~ X т , Х г . ^ 1

 

,

 

 

Если число переменных равно трем, то максимально воз­

можная величина S э

есть

шющадь равнобедренного треуголь­

ника,

образованного перечислением плоскости 0С*.+ X z + Хз ~ А

с координатными плоскостями. 33 случае наличия ограничений в виде системы (3,1) величина 5 э есть площадь многоугольникаг образованного пересечением плоскости 3Ci + X z + ЭС-з =* 1

с многогранным углом, который является результатом пересече­ ния полуплоскостей, соответствующих неравенствам системы (3 .1 ), Случай трех переменных.можно представить.как случай двух пере­ менных, если исключить одну из них из систем: (3.1) с помощью, соотношения (3 .5 ). При этом область А э представится в виде плоского треугольника.

ВП -мерном случае исключение одной из переменных

приводит

" к (

Wl- I)-мерному пространству, в котором область

А э

представляется в виде ограниченного многомерного кону­

са . При этом определение количественной характеристики S э

конуса оказывается трудной задачей. Таким образом, в случае

 

использование графических методов не представляется

возможным. Для решения задачи нахождения экстремальных значе­ ний критерия F в области А э следует воспользоваться много­ шаговыми алгоритмами линейного программирования. Наиболее гибким и универсальным методом, щшменяемыгл для решения задач линей- ' ного программирования, является хорошо разработанный в насто­ ящее время симплексный метод.

-73 -

•3 ,2 , Алгоритмы, состоящие из операций

сложения и умножения

Анализ вычислительных алгоритмов ■, встречающихся в систе­ мах управления с У8С, показывает, что большинство из них могут быть отнесены к одному из следующих классов:

1. Алгоритмы дискретно-разностной формы.

2. Алгоритмы в виде рядов и полиномов.

3. Логические алгоритмы.

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

= £ а ^ [ м - 1 ] - £ & < и Г > и ]

И>

i - i

а

о переменными коэффициентами Ос

,

Ь L и переменными входными

величинами X f H - i J » Поскольку эти

алгоритмы встречаются в

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

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

Например, одна из возможных микропрограмм, представля­

ющая собой оператор умножения, может быть записана в

виде

 

 

 

Q -0 * { S a K ‘ J Q lQ . ,

 

о-в)

гд е {

}

-

<L -

итерация;

 

 

 

G

L

-

микрооперация установки

i - го регистра в

нуль;

р : 1

-

вычитание единицы из содержимого i -го

регистра;

З ц

-

прибавление содержимого

L-г о регистра

к

содер ­

 

 

 

жимому

^ -г о регистра.

 

 

 

Смотрите также файлы