Maksimum şəbəkə axını. Maksimum axını tapmaq üçün alqoritm

Drenaj işarələnənə qədər bu əməliyyatı təkrar edirik. Axın etiketsiz qalsa, tapılan axın maksimumdur və işarələnmiş təpələri işarəsiz olanlarla birləşdirən qövslər dəsti minimal kəsik təşkil edir.

3. Ehtiyatın etiketlənməsinə icazə verin (j+, ε(t)), Sonra f(j,t) ilə əvəz edin f(j,t)+ε(t). Səhmlər işarələnibsə (j-, ε(t)), Bu f(j,t) ilə əvəz edin f(j,t)-ε(t). Gəlin zirvəyə çıxaq j. Əgər j işarəsi var (i+, ε(j)), sonra əvəz edirik f(i,j) haqqında f(i,j)+ε(t), və əgər (i-, ε(j)), f(j,i) ilə əvəz edin f(j,i)-ε(t). Gəlin zirvəyə çıxaq i. Mənbəyə çatana qədər bu əməliyyatı təkrar edirik s. Axın dəyişməsi dayanır, bütün işarələr silinir və 2-ci addıma keçin

NÜMUNƏ 3.14.

M 4 K

TASK. Şəbəkədə ən yüksək axını tapın

ALQORİTM

Təpə nöqtəsini qeyd edək s= x 0. Qalanların hamısı x i-dir.

Mərhələ 1.

1. Qövsləri doymamış istənilən yolu seçin.

2. Bu yolda doymuş qövs qalmayana qədər axının miqdarını bir artırırıq.

Tam axın qurulana qədər axının artırılması prosesini davam etdiririk, yəni. hər hansı bir yol ən azı bir doymuş qövsdən ibarət olacaqdır.

Mərhələ 2.

2. Əgər х i artıq işarələnmiş təpədirsə, onda (+i) doymamış qövslərin x i-dən getdiyi bütün etiketlənməmiş təpələri və (–i) indeksi ilə axını sıfırdan fərqli olan qövslərin getdiyi bütün işarələnməmiş təpələri qeyd edirik. üçün х i.

3. Əgər bu proses nəticəsində təpə nöqtəsi qeyd olunarsa t, sonra arasında s Və t bütün təpələri əvvəlki təpələrin nömrələri ilə işarələnmiş bir yol var. Bu yolun bütün qövslərində hərəkət edərkən axını bir artırırıq s Kimə t qövsün istiqaməti hərəkət istiqaməti ilə üst-üstə düşür və qövs əks istiqamətə malikdirsə, bir azaldılır. 1-ci addıma keçək.

4. Zaman üst t prosesin dayandırıldığını qeyd etmək mümkün deyil və nəticədə şəbəkənin ən böyük axınıdır.

QEYD. Birinci mərhələni tamamlamadan 2-ci mərhələyə keçə bilərsiniz (misal 3.16-a bax).

NÜMUNƏ 3.15.

9

HƏLL:

Verilmiş nəqliyyat şəbəkəsində tam axın aşkar edilmişdir. Doymuş qövslər vurğulanır

Bu şəbəkədə siz son təpəni də qeyd edə bilərsiniz və işarələmənin nəticəsi eyni olacaq. Axını dəyişdirərək, son təpəni qeyd etmək mümkün olmayan bir şəbəkə əldə edirik, ona görə də içindəki axın ən böyük və 10-a bərabərdir.

NÜMUNƏ 3.16.

8 2 1

Verilmiş nəqliyyat şəbəkəsində natamam axın aşkar edilmişdir

Şəbəkəni qeyd edək və alqoritmə uyğun olaraq içindəki axını artıraq. alırıq

Bu şəbəkədə siz son təpəni də qeyd edə bilərsiniz və işarələmənin nəticəsi eyni olacaq. Axını dəyişdirərək, son təpəni qeyd etmək mümkün olmayan bir şəbəkə əldə edirik, buna görə içindəki axın ən böyük və 6-ya bərabərdir.

Bölmə IV. DİNAMİK PROQRAMLAMA.

Optimal çoxmərhələli həllər tapmaq üçün dinamik proqramlaşdırmadan istifadə edilir. Məsələn, avadanlıqların dəyişdirilməsi üçün uzunmüddətli planlaşdırma; sənayenin bir neçə il ərzində fəaliyyəti. O, optimallıq prinsipindən istifadə edir, ona görə hər hansı yeni qismən həll əldə edilmiş vəziyyətə nisbətən optimal olmalıdır.

Birini dəfələrlə həll etmək daha yaxşıdır sadə tapşırıq bir dəfədən çox mürəkkəbdir.

PROBLEM 1. İki nöqtə arasında ən sərfəli marşrut haqqında.

İkincisi birincinin şimal-şərqində yerləşən iki A və B nöqtəsini birləşdirən bir yol çəkmək tələb olunur. Sadəlik üçün deyək ki, yolun çəkilməsi bir sıra addımlardan ibarətdir və hər addımda biz ya şimala, ya da şərqə doğru hərəkət edə bilərik. Sonra hər hansı bir yol, seqmentləri koordinat oxlarından birinə paralel olan pilləli bir qırıq xəttdir. Bu bölmələrin hər birinin tikintisinin xərcləri məlumdur.

NÜMUNƏ 4.1. A-dan B-yə olan minimum yolu tapın.

Son addım TV-yə nail olmaqdır. Son addımdan əvvəl biz bir addımda TV-yə çata biləcəyimiz nöqtələrdə ola bilərdik. İki belə nöqtə var (sistem iki vəziyyətdən birində ola bilər). Onların hər biri üçün t.V-ə çatmaq üçün tək bir seçim var: biri üçün - şərqə hərəkət edin; digəri üçün - şimala. Hər bir halda 4 və 3 xərcləri yazaq.

4

İndi sondan əvvəlki addımı optimallaşdıraq. Əvvəlki addımdan sonra biz üç nöqtədən birinə düşə bilərdik: C 1, C 2, C 3.

C 1 nöqtəsi üçün yalnız bir nəzarət var (bir ox ilə qeyd edək) - şərqə doğru hərəkət edin və xərclər 2 (bu addımda) + 4 (növbəti addımda) = 6 olacaq. Eynilə, C 3-cü maddə üçün xərclər 2+3=5 olacaqdır. t.C 2 üçün iki nəzarət var: şərqə və ya şimala gedin. Birinci halda xərclər 3+3=6, ikinci halda isə 1+4=5 olacaqdır. Bu o deməkdir ki, şərti optimal nəzarət şimala getməkdir. Onu ox ilə qeyd edək və müvafiq xərcləri daxil edək.

Cavab: x 1 =1; x 3 =0; x 3 =4; W=3.5

ÜMUMİ ALQORİTM

1. Sistemi təsvir edin. Yəni hər addımdan əvvəl idarə olunan sistemin vəziyyətini hansı parametrlərlə xarakterizə etdiyini öyrənin. Nəzarət olunan sistemin təsvirini mümkün qədər sadələşdirərək, lazımsız detallarla yükləmədən, düzgün və "təvazökarlıqla" vəzifəni təyin edə bilmək vacibdir.

2. Əməliyyatı mərhələlərə (mərhələlərə) bölün. Burada rəhbərliyə qoyulan bütün ağlabatan məhdudiyyətlər nəzərə alınmalıdır. Addım kifayət qədər kiçik olmalıdır ki, addım nəzarətinin optimallaşdırılması proseduru kifayət qədər sadə olsun; və addım, eyni zamanda, optimal həllin tapılması prosedurunu çətinləşdirən, lakin optimal həlldə əhəmiyyətli bir dəyişikliyə səbəb olmayan lazımsız hesablamalar aparmamaq üçün çox kiçik olmamalıdır. məqsəd funksiyası.

3. Hər bir addım üçün x i addım idarəetmə dəstini və onlara qoyulan məhdudiyyətləri tapın.

4. İdarəetmə x i-nin i-mərhələdə hansı qazancı gətirdiyini müəyyənləşdirin, əgər bundan əvvəl sistem S vəziyyətində idisə, yəni. Ödəniş funksiyalarını yazın:

w i =f i (S, x i)

5. İdarəetmə x i-nin təsiri altında sistemin vəziyyətinin necə dəyişdiyini müəyyən edin 1-ci addım, yəni. hal dəyişmə funksiyalarını yazın.

S / =φ i (S, x i)

6. Artıq məlum funksiya vasitəsilə şərti optimal qazancı ifadə edən əsas təkrarlanan dinamik proqramlaşdırma tənliyini yazın.

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. İstehsal et şərti optimallaşdırma son addımın necə başa çatdığına dair müxtəlif fərziyyələr irəli sürmək və bu fərziyyələrin hər biri üçün son mərhələdə şərti (addımın bir şeylə başa çatması şərti əsasında seçilmiş) optimal nəzarəti tapmaq.

W m (S)= maks (f m (S, x m))

8. Sondan əvvəlki addımdan başlayaraq birinci addımla bitən şərti optimallaşdırmanı həyata keçirin (geriyə doğru).

9. İstehsal et qeyd-şərtsiz optimallaşdırma nəzarət etmək, hər addımda müvafiq tövsiyələri “oxumaq”: ilk addımda tapılan optimal idarəetməni götürün və sistemin vəziyyətini dəyişdirin, tapılan vəziyyət üçün ikinci addımda optimal idarəetməni tapın və s. son addıma qədər.

OPTİMALLIQ PRİNSİPİ. Növbəti addımdan əvvəl sistemin vəziyyətindən asılı olmayaraq, bu addımda nəzarəti seçmək lazımdır ki, bu addımda qazanc və bütün sonrakı addımlarda optimal gəlir maksimum olsun.

Dinamik proqramlaşdırma prinsipi hər bir addımın digərlərindən asılı olmayaraq ayrıca optimallaşdırılmasını nəzərdə tutmur. Əgər bu addım bizi sonrakı addımlarda yaxşı qələbə qazanmaq imkanından məhrum edəcəksə, konkret bir addımda effektivliyi maksimum olan nəzarəti seçməyin nə mənası var?

Təcrübədə əməliyyatın qeyri-müəyyən müddətə planlaşdırılmalı olduğu hallar var. Belə bir vəziyyət üçün model, bütün addımların bərabər olduğu sonsuz addımlı idarə olunan bir prosesdir. Burada qalib funksiya və vəziyyət dəyişmə funksiyası addım sayından asılı deyil.

Bölmə V. SİMULASYON MODELLEŞMESİ

Bu dərslik diskret riyaziyyat və/və ya qrafik nəzəriyyəsi üzrə kurslar alan tələbələr üçün nəzərdə tutulub.

Onun köməyi ilə siz “Şəbəkədə maksimum axın və minimum kəsmə” mövzusunu mənimsəyəcəksiniz.

• Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz.=|Əgər sizdə MATLAB varsa, bu səhifəyə keçin: orada sizin hesablama skriptinə (proqramına) müdaxilə etmək imkanınız var. Burada şəbəkədə maksimum axın problemi onu xətti proqramlaşdırma məsələsinə endirməklə həll edilir. Aşağıdakı qeydi təqdim edək:
• n=|V| − qrafik ölçüsü (təpələrin sayı);
• m E Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz.× n| − qrafik kardinallığı (kənarların sayı); A− ölçülü şəbəkə diqrafının insident matrisi i; onun hər bir elementi bir ik=1 əgər -dən A-yuxarı çıxır i k bir ik-i qövs; A=−1, əgər varsa
• s inci təpə daxil olur
• t-i qövs; Və
• =0 digər hallarda; belə bir matrisin hər sütununda tam olaraq bir, bir mənfi bir, qalanları isə sıfırdır;− şəbəkənin mənbə təpəsinin sayı; bu təpədən yalnız qövslər çıxmalı və hər hansı digər təpə mənbədən əlçatan olmalıdır; − s m − şəbəkə sink təpəsinin sayı; bu təpəyə yalnız qövslər daxil olmalıdır və hər hansı digər təpədən drenaja çıxmaq mümkün olmalıdır;
• =0 digər hallarda; belə bir matrisin hər sütununda tam olaraq bir, bir mənfi bir, qalanları isə sıfırdır; a − t s m ;
• m yalnız birləri ehtiva etməlidir, çünki mənbədən yalnız qövslər çıxmalıdır; t m -şəbəkə diqrafının insident matrisinin -ci sıra s; t yalnız mənfi olanları ehtiva etməlidir, çünki drenaja yalnız qövslər daxil olmalıdır;
• st − şəbəkə diqrafının insidans matrisi n oradan atılanlarla ci və ci xətlər; bir ik e
• − uzunluğunun sütun vektoru − şəbəkə diqrafının insidans matrisi n oradan atılanlarla ; onun hər bir elementində e k bir ik daxil olan axının böyüklüyü olacaq

ci qövs;

c

c k

• ≥0 ötürmə qabiliyyətini təyin edir ci və ci qövs. ci və = ; onun hər bir elementində Sonra maksimum şəbəkə axını problemi xətti proqramlaşdırma problemi kimi tərtib edilə bilər:
• Mənbədən (1) çıxan ümumi axın maksimumlaşdırılır. Üstəlik, hər hansı bir ara təpədə daxil olan axın çıxan axına (2) bərabərdir və qövslərin tutumu məhduddur (3).
• iki belə komponent varsa, atılan qövslər minimal kəsik verir;
• ikidən çox əlaqəli komponentlər görünsə, şəbəkə diqrafında bir neçə minimal kəsik var (müvafiq xətti proqramlaşdırma problemi degenerasiyadır).

Degenerativ problem üçün mənbəyə ən yaxın olan ilk minimal kəsik bu səhifədə qurulur.

Bu səhifədən düzgün istifadə etmək üçün brauzeriniz skriptləri dəstəkləməlidir Java Skripti. Onları yandırın.

Aşağıdakı giriş sahələrinə ilkin məlumatları daxil edin. Şəbəkənin diqrafını çəkmək üçün sizə lazım olan ilk sahədə (daha doğrusu, edə bilərsiniz) təpələrin koordinatlarını daxil etməlisiniz. Onlar matris şəklində müəyyən edilir Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz.×2: birinci sütunda − x th koordinatları, ikincidə - y-e. Nömrələr tam ədədlər, onluq nöqtə ilə və ya eksponensial formada göstərilə bilər. Nömrələri boşluqlarla ayırın. Ümumi miqdar bu giriş sahəsindəki xətlər diqrafın ölçüsünü müəyyən edir Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz.− təpələrin sayı. Bu ilkin məlumatlar (təpə koordinatları) isteğe bağlıdır: əgər onlar göstərilməyibsə, şəbəkə diqrafı düzgün şəkildə çəkiləcək. Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz.-gon və təpələrin sayı növbəti giriş sahəsindəki maksimum təpə sayı ilə müəyyən ediləcək.

Növbəti giriş sahəsində sol tərəf- doldurmaq tələb olunur. O, şəbəkə diqrafının strukturunu müəyyən edir. n Diqrafdakı hər bir qövs iki təpəni birləşdirir. Bu təpələrin nömrələri matris şəklində göstərilmişdir ×2 ikinci giriş sahəsinin sol tərəfində. Hər bir sətirdə əvvəlcə qövsün 1-ci təpəsi (quyruq, mənbə), sonra isə boşluq vasitəsilə qövsün 2-ci təpəsi (ucu, drenajı) müəyyən edilir. Bu sütunlar olmalıdır Kompüterinizdə MATLAB olmasa belə, birbaşa bu təlimatdan siz şəxsiyyət vəsiqənizi hesablaya bilərsiniz. natural ədədlər n 1-dən

Bu sütunların hər birindəki nömrələrin ümumi sayı diqrafın kardinallığını müəyyən edir − qövslərin sayı. , Hesablayın İstiqamətləndirilmiş qrafik verilsin G= hər qövsün hansı istiqamətdə vÎV V axının istiqamətini bildirir (məsələn, avtomobillərin axını), hər bir qövsün tutumu bərabərdir t Və s d(v). t Bir çox zirvələrdə s iki təpəsi vurğulanır t. Vertex s .

axının mənbəyidir, - drenaj. Təpədən keçə biləcək maksimum axını müəyyən etmək tələb olunur V ilə işarə edək x(v)

qövs boyunca hərəkət edən axının miqdarı (6. 1)

v . Aydındır ki 0 £ x(v) £ d(v) , vÎV .

Hər zirvədə)iÎE\(t,s)

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

Üst üçün t

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

təpə üçün s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

Böyüklük Q təpədən çıxan axının böyüklüyüdür t və zirvəyə daxil olur s.

Müəyyən etmək lazımdır

Q ® maks(6.5)

məhdudiyyətlər altında (6.1-6.4).

Kəmiyyətlər Q, x(v) , vÎV, məhdudiyyətləri təmin edən (6.1-6.4) biz şəbəkədə axın adlandıracağıq və əgər onlar dəyəri maksimuma çatdırsalar Q, sonra maksimum axın. Dəyərlərin olduğunu görmək asandır Q=0, x(v)=0, vÎV, şəbəkədə bir axındır.

Problem (6.1-6.5) xətti proqramlaşdırma məsələsidir və simpleks metodu alqoritmlərindən istifadə etməklə həll edilə bilər.

E təpələri çoxluğunu E1 və E2 ayrı iki hissəyə elə bölək ki, tÎE1, sÎE2. Kəsməklə V(E1,E2), ayırmaq t Və s dəsti çağıracağıq V(E1,E2)ÌV belə ki, hər qövs üçün v О V(E1,E2) və ya h1(v)ОE1 Və h2(v)ОE2, və ya h1(v)ОE2 Və h2(v)ОE1.

Gəlin dəsti bölək V(E1,E2) iki hissəyə V(E1,E2,+),V(E1,E2,-) aşağıdakı kimi:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1 Və h2(v)ОE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1 Və h1(v)ОE2)

Kesimin ötürmə qabiliyyətini çağıracağıq

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

Aşağıdakılar doğrudur

Teorem 1. (Maksimum axın və minimum kəsmə haqqında).

İstənilən şəbəkədə mənbədən maksimum axın olur a ehtiyat etmək s minimum ötürmə qabiliyyətinə bərabərdir Q(E1,E2) bütün kəsiklər arasında V(E1,E2), təpələri ayırmaq t Və s.

Qeyd edək ki, maksimum axın içində

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Qoy Q, x(v), vÎV, - bəzi şəbəkə axını, ardıcıllığı

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

təpələri birləşdirən zəncirdir t Və s. Bu zəncirdə təpədən hərəkət istiqamətini təyin edək t Kimə s. qövs v(j) bu zəncirdən onun istiqaməti hərəkət istiqaməti ilə üst-üstə düşürsə düz xətt adlanır t Kimə s, və əksinə. Biz bu zənciri yol adlandıracağıq artan axın, düz qövslər üçünsə ilə işarə edək zəncirlər x(v)< d(v) və əksinə x(v) > 0. Bu dövrədən əlavə bir axın keçirilə bilər q-dən t Kimə sölçüsü q = min(q1,q2), Harada q1=dəq (d(v) -x(v)), minimum zəncirin bütün düz qövsləri üzərində alınır, q1=dəq (x(v)), minimum zəncirin bütün əks qövsləri üzərində alınır.

Teorem 2.

Axın Q, x(v) , vÎV, yalnız və yalnız axını artırmaq üçün heç bir yol olmadıqda maksimumdur.

Şəbəkədə maksimum axın probleminin həlli üçün təklif olunan alqoritm şəbəkədən axını artırmaq üçün bir yol tapmağa əsaslanır. t. Vertex s, bu da öz növbəsində təpə etiketlərinin təşkili prosesinə əsaslanır. Belə deyək

təpə i işarəsi ilə qeyd olunur q(i)>0, və düz qövs də məlumdur v(i), bu axının gəldiyi və ya işarələndiyi , əgər böyüklüyündə bəzi əlavə axın q(i)>0, və əks qövs də məlumdur v(i), bu axının daxil olduğu;

i təpəsinə bütün qonşu təpələri işarələnmişsə baxılır.

Əgər təpə s işarələnibsə, o zaman axını böyüklüklə artırmaq üçün yol tapılıb q, bu yoldan keçən. Alqoritmi təsvir etmək üçün bizə də massiv lazımdır SPW, işarələnmiş təpələrin nömrələrini onların qeyd olunduğu ardıcıllıqla ehtiva edir. C1- massivdəki nömrə SPW baxılan zirvə, C2- bu massivdə sonuncu işarələnmiş təpənin nömrəsi.

Bu alqoritmin ideyası mənbədən lavaboya müsbət axınları olan uç-uca yolları tapmaqdır.

(ilkin) tutumlu kənarı (i, j) nəzərdən keçirək. Alqoritmin icrası zamanı bu tutumun hissələri verilmiş kənardan keçən axınlar tərəfindən “götürülür”, nəticədə hər kənarın qalıq tutumu olacaqdır. Yaz - qalıq bant genişliyi. Bütün kənarlarının qalıq tutumuna malik olduğu şəbəkə qalıq adlanacaqdır.

i qovşağından axın qəbul edən ixtiyari j nodu üçün etiketi təyin edirik, burada j düyündən i qovşağına axan axının qiymətidir. Maksimum axını tapmaq üçün aşağıdakı addımları yerinə yetiririk.

Bütün kənarlar üçün qalıq tutumu ilkin tutuma bərabər təyin edirik, yəni. bərabər tutaq =. Node 1-i etiketlə təyin edək və qeyd edək. Fərz edirik ki, i=1.

Bütün j üçün müsbət qalıq tutumu >0 olan kənar boyunca I düyündən gedə biləcəyiniz j qovşaqlarının dəsti. Əgər 3-cü mərhələni yerinə yetiririksə, əks halda 4-ə keçirik.

Biz k node-də belə tapırıq. Gəlin k düyünü yerləşdirək və etiketlə qeyd edək. Əgər k=n olarsa, ucdan uca yol tapılır və 5-ci mərhələyə keçirik, əks halda i=k təyin edib 2-ci mərhələyə qayıdırıq.

Geriyə qayıt. Əgər i=1 olarsa, heç bir ucdan-uca yol mümkün deyil və 6-ya keçin. Əgər i qovşağından dərhal əvvəl etiketlənmiş r düyünü tapırıq və onu r qovşağına bitişik qovşaqlar dəstindən çıxarırıq. i=r təyin edirik və 2-ci mərhələyə qayıdırıq.

Qalıq şəbəkənin tərifi. Mənbə qovşağından (1-ci qovşaq) sink qovşağına (node ​​n) qədər tapılan p_th-nin keçdiyi qovşaqlar dəsti ilə işarə edək

Ucdan uca yolu təşkil edən kənarların qalıq tutumu axın istiqamətində bir miqdar azalır və əks istiqamətdə eyni miqdarda artır.

Bu. Uçdan uca yola daxil olan kənar (i, j) üçün cari qalıq imkanlar dəyişir:

1) axın i düyündən j-ə keçirsə,

2) axın j qovşağından i-yə gedirsə.

a) tapılan m uç-uca yol ilə maksimum axın ilə ifadə edilir

b) Kənarın ilkin və son tutumlarının qiymətlərinə (i, j) malik olmaqla, bu kənardan optimal axını aşağıdakı kimi hesablaya bilərik. qoy onu. Əgər >0 olarsa, kənardan (i, j) keçən axın bərabərdir. Əgər >0 olarsa, axın bərabərdir. (həm >0, həm də >0 qeyri-mümkün olduqda).

Misal 1. Şəbəkədə maksimum axını tapın Şək. 1

İterasiya 1. =

3) k=3, çünki. Node 3-ü bir etiketlə təyin edirik və qeyd edirik. i=3 və 2-yə qayıdın)

5) k=5 və. 5-ci qovşağı etiketlə qeyd edirik. Biz bir keçid yolu alırıq.

6) 5-ci qovşaqdan başlayaraq 1-ci qovşaqla bitən etiketlərlə başdan-başa yolu müəyyən edirik: . Və. Yol boyunca qalıq tutumları hesablayırıq:

İterasiya 2.

1) və 1-ci qovşağı etiketlə qeyd edin. i=1

2") (buna görə də 5 node daxil deyil

3") k=4 və 4-cü qovşağı etiketlə qeyd edin. i=4 və 2-yə qayıdın)

2""") (1 və 3 qovşaqları işarələndiyi üçün onlar daxil edilmir)

3""") k=5 və. 5-ci qovşağı etiketlə qeyd edirik. Başdan sona yol alınır. 5-ə keçin)

İterasiya 3.

1) və 1-ci qovşağı etiketlə qeyd edin. i=1

3) k=2 və 2-ci qovşağı etiketlə qeyd edin. i=2 və 2-yə qayıdın)

3") k=3 və. 3-cü qovşağı etiketlə qeyd edin. i=3 və 2-yə qayıdın)

2") (ci ildən) 4-ə keçin)

4) node 3 etiketi əvvəlki node nömrəsini göstərir. Bu iterasiyada 3-cü qovşaq gələcəkdə nəzərə alınmır; və 2-ə qayıdın)

2""") (çünki qovşaq 3 mümkün uç-uca yoldan çıxarılır)

3""") və. Biz 5-ci qovşağı etiketlə qeyd edirik. Başdan sona yol əldə edilir. 5-ə keçin)

5) i. Yol boyunca qalıq tutumları hesablayırıq:

İterasiya 4. Bu iterasiyada ilə yol

İterasiya 5. Bu iterasiyada ilə yol

İterasiya 6: Node 1-dən yaranan bütün kənarların sıfır qalıq tutumu olduğu üçün yeni uç-uca yollar mümkün deyil. Həll yolunu müəyyən etmək üçün 6-a keçin

6) şəbəkədə maksimum axın həcmi vahidlərə bərabərdir.

Müxtəlif kənarlar boyunca axın dəyərləri ilkin tutum dəyərlərindən ən son qalıq tutum dəyərlərini çıxmaqla hesablanır.

Hesablama nəticələri: cədvəl. 1

Maksimum axını tapmaq üçün alqoritmin qrafik ardıcıl icrası (nümunə 1)

e) f) Keçən yollar yoxdur

düyü.

Nəqliyyat sistemi haqqında ilkin məlumatlar, məsələn, zavodda, Şəkildə göstərilmişdir. 2, cədvəllə də müəyyən edilə bilər (Cədvəl 2).

Cədvəl 2. Maksimum axın problemi üçün ilkin məlumatlar

Aydındır ki, nəqliyyat sisteminin maksimal tutumu 6-dan çox deyil, çünki başlanğıc nöqtədən 0-dan 6 vahiddən çox olmayan yük, yəni 1-ci nöqtəyə 2 vahid, 2-ci nöqtəyə 3 vahid və 3-cü nöqtəyə 1 vahid göndərilə bilməz. Bundan sonra, bütün 6 vahid yükün 0 nöqtəsinə çatmasını təmin etmək lazımdır. bölünməlidir: 2 ədəd dərhal 4-cü bəndə, 1 ədəd isə 3-cü aralıq nöqtəyə göndərilir (2-ci və 4-cü bəndlər arasındakı bölmənin məhdud tutumu ilə əlaqədar). 3-cü məntəqəyə aşağıdakı yüklər çatdırılıb: 0-cı məntəqədən 1 ədəd, 3-cü məntəqədən isə 1 ədəd. Biz onları 4-cü məntəqəyə göndəririk. Beləliklə, sözügedən nəqliyyat sisteminin maksimum keçirmə qabiliyyəti 6 vahid yük təşkil edir. Bu halda, 1-ci və 2-ci bəndlər arasında, habelə 1-ci və 3-cü nöqtələr arasında olan daxili bölmələr (budaqlar) istifadə edilmir, 1-ci və 4-cü nöqtələr arasındakı filial tam yüklənməmişdir - onunla birlikdə 2 ədəd yük göndərilir. ötürmə qabiliyyəti 3 vahiddir. Həll cədvəl şəklində təqdim edilə bilər (Cədvəl 3)

Cədvəl 3. Maksimum axın probleminin həlli

Axının maksimumlaşdırılması üçün xətti proqramlaşdırma problemi. Maksimum axın problemini xətti proqramlaşdırma baxımından formalaşdıraq. X KM K nöqtəsindən M nöqtəsinə daşınmanın həcmi olsun. Şəkilə görə. 2 K = 0,1,2,3, M = 1,2,3,4 və daşınma yalnız daha yüksək rəqəm olan nöqtəyə mümkündür. Bu o deməkdir ki, X KM cəmi 9 dəyişən, yəni X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. axın formasına malikdir:

X 01 + X 02 + X 03 = F (0)

X 01 + X 12 + X 13 + X 14 = 0 (1)

X 02 - X 12 + X 23 + X 24 = 0 (2)

X 03 - X 13 - X 23 + X 34 = 0 (3)

X 14 - X 24 - X 34 = - F (4)

X KM? 0, K, M = 0, 1, 2, 3, 4

Burada F məqsəd funksiyası, şərt (0) malların nəqliyyat sisteminə daxil olmasını təsvir edir. Şərtlər (1) - (3) sistemin 1-3 qovşaqları üçün balans münasibətlərini təyin edir. Başqa sözlə, daxili qovşaqların hər biri üçün daxil olan mal axını sistem daxilində yığılmır və orada “doğmur”. Şərt (4) sistemdən yüklərin “çıxması” şərtidir. (0) şərti ilə birlikdə bütövlükdə sistem üçün balans əlaqəsini təşkil edir (“giriş” “çıxışa” bərabərdir). Aşağıdakı doqquz bərabərsizlik nəqliyyat sisteminin ayrı-ayrı “filiallarının” tutumuna məhdudiyyətlər qoyur. Sonra nəqliyyatın həcminin mənfi olmadığı və məqsəd funksiyası göstərilir. Aydındır ki, sonuncu bərabərsizlik məqsəd funksiyasının (münasibət (0) və ya (4)) formasından və hərəkət həcmlərinin mənfi olmamasından irəli gəlir. Bununla belə, sonuncu bərabərsizlik bəziləri daşıyır ümumi məlumat- sistemdən ya müsbət yük həcmi keçə bilər, ya da sıfır (məsələn, sistem daxilində dairədə hərəkət olarsa), mənfi deyil (iqtisadi məna kəsb etmir, formal riyazi model bu barədə "bilmir").

Qövslərdən keçən axınların cəmi ilə işarə edək, qövslərdən keçən axınların cəminə bərabərdir w; bu məbləğə axın dəyəri deyilir. Biz ilk növbədə mümkün olan ən böyük miqyasda olan axınlarla - sözdə maksimum axınlarla maraqlanacağıq. IN ümumi halşəbəkədə bir neçə fərqli maksimum axın ola bilər, lakin onların dəyərləri eyni olmalıdır. (4)

Şəbəkə vasitəsilə maksimum axınların öyrənilməsi N = (V,D,a) kəsik anlayışı ilə sıx bağlıdır, yəni. hər hansı sadə zəncir kimi xassə olan D diqrafının qövslərinin belə A çoxluğu ilə işarə edək. Vertex A-ya məxsus qövsdən keçir.Kəsimin tutumu ona aid olan qövslərin tutumlarının cəmidir. Mümkün olan ən kiçik ötürmə qabiliyyətinə malik olan kəsiklərə minimal kəsiklər deyilir.

Hər hansı bir axının böyüklüyü heç bir kəsilmənin tutumundan çox deyil və buna görə də, hər hansı bir maksimum axının böyüklüyü heç bir minimum kəsilmənin gücündən çox deyil. Ancaq ikisinin olduğu dərhal aydın deyil son nömrələr həmişə bir-birinə bərabərdir; Bu nəticə 1955-ci ildə Amerika riyaziyyatçıları Ford və Fulkerson tərəfindən əldə edilmiş və maksimum axın və minimum kəsilmə teoremi adlandırılmışdır.

Teorem (maksimum axın və minimum kəsim haqqında). İstənilən şəbəkədə istənilən maksimum axının ölçüsü istənilən minimum kəsilmə qabiliyyətinə bərabərdir.

Maksimum axın və minimum kəsmə teoremi verilmiş axının maksimum olub olmadığını yoxlamağa imkan verir, ancaq kifayət qədər sadə şəbəkələr üçün. Təbii ki, praktikada biz böyük və mürəkkəb şəbəkələrlə məşğul olmalıyıq və ümumilikdə sadə seçimlə maksimum axını tapmaq çətindir. Tam ədəd ötürmə qabiliyyəti olan istənilən şəbəkədə maksimum axını tapmaq üçün bir alqoritmi təsvir edək.

Addım 1. Əvvəlcə sıfırdan fərqli dəyəri olan axını seçək (əgər belə bir axın varsa). Məsələn, N Şəkildə göstərilən şəbəkədirsə. 29.3, sonra Şəkildə göstərilən axın. 29.4. Qeyd etmək lazımdır ki, seçdiyimiz ilkin axının dəyəri nə qədər böyükdürsə, sonrakı addımlar bir o qədər asan olacaq.

Addım 2. N-ə əsaslanaraq, axının istiqamətini əksinə dəyişdirərək yeni N şəbəkəsi qururuq. Daha dəqiq desək, (a) = 0 olan hər hansı a qövsü orijinal tutumu ilə N'-də qalır və hər hansı a qövsü tutumlu a qövsü və tutumlu (a) əks qövslə əvəz olunur. Nümunəmizdəki şəbəkə N Şəkildə göstərilmişdir. 29.5. Vertex ilə işarə edək artıq mənbə deyil, lavabodur.

Addım 3. Əgər N şəbəkəsində sıfırdan fərqli bir axın tapa bilərik ilə işarə edək c, sonra onu ilkin axına əlavə etmək və N-də daha böyük dəyərə malik yeni axın əldə etmək olar. İndi şəbəkəni qurarkən N' əvəzinə yeni ipdən istifadə edərək 2-ci addımı təkrarlaya bilərsiniz. Bu proseduru təkrar etməklə, biz nəhayət sıfırdan fərqli axınları olmayan N' şəbəkəsinə çatacağıq; onda müvafiq axın maksimum axın olacaqdır. Məsələn, Şek. 29.5 qövslərdən keçən sıfırdan fərqli axın var ( v,u), (u,z), (z,x), (x,y) Və ( y,) birə bərabərdir və qalan qövslərdən keçən axınlar sıfıra bərabərdir. Şəkildəki axına bu axını əlavə edirik. 29.4, Şəkildə göstərilən axını əldə edirik. 29,6; 2-ci addımı təkrarlayaraq bunun maksimum axın olduğunu göstərmək asandır.

İstifadə olunan ədəbiyyat:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Asanov M.O., Baranski V.A., Rasin V.V. Diskret riyaziyyat: matroid qrafiklər, alqoritmlər

(3) Başaker R., Saati T. Sonlu qrafiklər və şəbəkələr.

(4) Wilson R. Qrafik nəzəriyyəsinə giriş