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

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

X f eM

^

■

В каждом

Щ -ом варианте

подсчитываются все

параметры

алгоритма, и если один из вариантов не удовлетворяет

постав­

ся

переход к

tfj+i

варианту.

Этот

процеоо продолжается

до

тех

пор,

пока не будет найден

tfj® -

оптимальный вариант.

Боли несколько вариантов

имеют Х ? ‘м

, то

после

- варианта следует продолжать раочет еще ряда

( Х{#+н

,

}S^®+2 ) вариантов до тех пор, пока в

некотором варианте

бу­

дет

1

X j>*m (

K'i 'w

) >

Х ^ вм wi-fi.

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

другому параметру,

исключив

Х р и

из дальнейшего рассмотрения

Так как все

at

вариантов

удовлетворяют требованиям,

то н а - j

хождение новых частных решений овязано

с перебором всех ot ва­

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

I

предыдущий.

Боли

dt

=

I ,

то

оптимальный вариант

найден и алго -

!

ритмы

E ji ,

составляющие данное решение,

являются наилучшими.

Для большого

числа решений

8

метод последовательных

, •

приближений являетоя предпочтительнее метода перебора, так

как

здесь не рассматриваются варианты

о

Х р м

> X f “n min

,

,

число которых может быть большим.

Последовательные приближения (рио.

2 .2) показаны от

д о

)Г|» = 5 .

Для вариантов

XV, XV XV

ВЫПОЛНЯЮТСЯ уоловия

j

( j f s ) “

( к < ) ~

( у ? )

!

Из трех вариантов

(

V * ,

У«

,

XV

)

можно выбрать

ОДИН,

если минимизировать

по одному из

параметров X i

, Хг.

,

г

- 48

- .............

. . '

i

Х а . Для йктлвыбирается вариант

V? , дляХаипм-Ут,

для

Х*тй1 - Х*5 •

Данный метод можно применять для минимизации независи­

црограшн

с! и времени реализации Ь . Однако

d

совмест­

но

о Л

составляют единую долговременную шмять

D

маши­

ны,

Поэтому для минимизации D можно поступить

следующим об­

$ |«

, минимизирующий параметр d

, а остальные параметры

(кроме

А

) должны удовлетворять заданным требованиям. Для

этого варианта

определяется

I

D j *

-

+

.

где

A j* определяется после операций,

проведенных над выбран­

ными компонентами-множествами матрицы К

. После этого пере­

ходим к

вычислению следующих вариантов 1)

. Для сокращения за­

писи обозначим

= V®

>

тогда

следующие варианты есть

I

$ 2

(

<Ь =

0 , 1 , 2 , . . . , ) .

Для каждого варианта определяют­

ся

Т )0 ,

D

i , .

. . .

В процессе этих вычислений последующие зна-

IDi.e > T)*»ni»t. Процеос

продолжается до

получения D d°> j)xm in .

^Очевидно, что вое последующие варианты

.

)

дадут

i

Если минимизируется параметр b

г т

ограничении d+A=«

j

=*Т)огр , то здесь

будут отличия в

там,

что после операций

: Q над компонентами матрицы d

и матрицы К « после которой

определяется Л , в

каждом варианте вычисляется d + А , для

которой выполняется

d + A ^ Т)ог,р . При выполнении этого

условия осуществляется переход к

следующему варианту.

;

2 .3 . Методы исключения вариантов и линейного

i

программирования

|

Метод исключения вариантов предполагает исключение тех

1. Бели в выбранной матрице омоется компонента

1

поставлеанш требованиям по одному из нардистров.

2 . Если максимальная в матрице компонента

^

Xji-j»max < Хр* ,

nwnmn операция 0

с другими ппиш иииии варанетрами X j i n»w«

даст

м

Хрт -»0Cjij»««ax

. (2<7)

назначениях (проблема амбара)

[5 0 ] .

Обозначай

■*< 4 1 .

Ведячяна

О бмою т ирянамать

только два дискретах iiMimini:

(0 ала I ) ,

Пусть Ctjt - О ,

ного алгоритма

И

,

d j l = I -

волк яошиьауетоя. Пря

«том для каждого набора дамп» выполняться

(X jt+ d |* .- 0 '

+ a i " i ““ 1 *

(2 Л )

U « * . 2 ,

i

. , ж ) .

Для параметров,

которне нажжены офвичшая.

запасать систему лавейя

X uj>Qu

+

+

+

(2.9)

+ X * ij» d * i +

X a ^ < l 2 % - f

+••* +Xwij»a*i ♦

Отг+•“• +

+

C L (%

^

) »

где

Xy*

- агравмчянн на пар—игр

X / .

Составленная цвинма #вавра 2

яля и н п н ш д а т г о

параметра X j

маогг ащ

2

' 5* X iif d n

+ Х о у C Ja.+►• * + Xin^p й * я 4+ (2.ID)