0000083

cych dróg cyklicznych, metody s« bardziej efektywne. ponieważ «oqo być łatwo sprowadzone do metody progremowonle dynamicznego, dla której czoe obliczeń joot proporcjonalny do lloócl wierz -cholkó* eiecl. Natomiast w przypadku oleci cyklicznej wyznaczania prostej drogi ekstromalnoj związane Jest no ogół ze znacz -nyal trudnościami 1 poza nlektóryel wyjftkemi ooówionyel w punkcie 10.3 wymaga atoeowonio metod progromowanio całkowitoliczbo-

wego. Pownf syotemotykę omowlonych metod przedstawia ogólny eche* ■ot blokowy algorytmu wyznaczanie prostych dróg ekstremalnych w standardowych sieciach skierowanych (rys.10.2). Struktura tego algorytmu odpowiada strukturze niniejszego rozdziału. Pozwoli to Czytelnikowi doóć szybko odnaleźć interesujący go materiał i niezbędno metody rozwiązanie zadania [23],

Sieć acykticrna		Sieć cykliuna
w sensie dróg		nr sensie dróg

—s.

.........i r , •. Drogi najkrótsze		Drogi najdłuższe
		.. ,1 .
C/y długości każdej		Czy długości każdej
drogi cyklicznej		drogi cyklicznej
_umi_
■ ,i. r ,		■ i ^t ■

Metoda programomi-nia dy rmiernego (jecnokratne radiowo nie wierzchołków)

Metody programowania całkowltollczbowego lub pełny przegląd

Metoda dendrytaw dróg ekstremalnych (wielokrotne cechowanie wierzchołków)

Rys.10.2

10.2. Drogi proste ekstremalne w sleclch acyklicznych

Problom wyznaczonia drogi ekstremalnej w sieci, której graf nic zawiera dróg cyklicznych, można sformułować w postaci tak zwanogo zadania sterowania optymalnego, w skończonym zbiorze etanów. 6tanaml hipotetycznego, sterowanego obiektu będę wierzchołki sieci, a dopuszczalnymi sterowaniami przy stanie x będę łukl wychodzące z wierzchołka x. Zapis formalny zadania może być następujący (patrz dodatek 2)t

Oana jest sieć S¹ • <g',0. (l}> , gdzie c'• <X^,.u',p'> Jest digrafem bez dróg cyklicznych oraz dwa ustalone wierzchołki x^p i x^k. NoleZy znaleźć tak| drogę <%_xtr(^xP.^xk) •{^x1»^uł*^x2.....^xe*

V%ól.....^ua(^u) ^,xm(^u)4l } ^#bV mLu)

^F^.xtr>

®^Xt.^r kx

^X1 " ^xP' ^X«^_extr)*l " ^xk

przy ograniczeniach i

^x._4l • y(^x,.u,)/ • • 1.2.....■(<“)

y(^x»u)

dla (x,u) : <x,y,u> £ P* dla pozostałych arg^ intów

Cięg łuków { Uj,... ,u_f,...    j} drogi ^u(x^p,x^k) jest cięgiem

sterowań, w wyniku którego etan układu sterowanego zmienia się od stanu poczętkowego Xj • x^p do stanu końcowego    • *^k.

Zbiór x' można zmniejszyć do zbioru X zawierajęcogo tylko te wierzchołki, przez które mogę przechodzić drogi <u(x^p,x ;. Ozneczmy:

C(x^p) - zbiór wierzchołków oslęgalnych z wierzchołka x^p w gra-

k f¹*®'*

*■(« ) - zbiór wierzchołków, z których Jest oslęgalny wierz -chołek x^k w grafie c' j

X . G(x^p)r»*(x^k).

165