Hesablama alqoritmi maksimum axınşəbəkələrdə
ADDIM 1. İlkin tapşırıqlar. Cari dəyər A tŞəbəkədəki maksimum axın 0 dəyəri ilə təyin olunur. ADDIM 2. Şəbəkədə müstəqil marşrutların seçilməsi və onlarda axınların müəyyən edilməsi.Şəbəkədə mənbədən lavaboya qədər bütün mümkün marşrutlar toplusundan müstəqil marşrutlar seçirik M 1 , … , M k, olmayan ümumi təpələr, ilkin istisna olmaqla (mənbə v və) və son (drenaj v ilə). Hər seçilmiş marşrut üçün M i(1£ i£ k) maksimum axını təyin edin A(M i).ADDIM 3. Şəbəkədə maksimum axının cari qiymətinin korreksiyası. Tapılanları əlavə edirik ADDIM 2 müstəqil marşrutlarda maksimum axınların dəyərləri M 1 , … , M k cari ümumi maksimum şəbəkə axınına: A t:= A t + A(M 1)+ A(M 2)+…+ A(M k)ADDIM 4. Şəbəkə korreksiyası. tapıldı ADDIM 2 maksimum axınlar A(M 1), … , A(M k)müvafiq şəbəkə qövslərinin tutumundan çıxılır. Sıfır qalıq tutumu olan qövslər çıxarılır. ADDIM 5. Alqoritmin tamamlanmasının yoxlanılması.Əgər düzəlişdən sonra şəbəkədə mənbədən heç bir marşrut yoxdursa v və ehtiyat etmək v ilə, onda şəbəkədə tələb olunan maksimum axın tapılan cərəyana bərabərdir A:= A t, bütün şəbəkə tutumu tükəndiyi üçün alqoritm dayandırılır. Tənzimlənmiş şəbəkədə mənbədən marşrutlar varsa v və ehtiyat etmək v ilə, sonra gedin ADDIM 2 və alqoritmin icrasının davamı . Misal 2. Bu alqoritmdən istifadə edərək Şəkil 1.15-də şəbəkədə maksimum axını tapın. Həlli. ADDIM 1. İlkin tapşırıqlar. A t: = 0.təkrarlama. ADDIM 2. Şəbəkədə müstəqil marşrutların seçilməsi və onlarda axınların müəyyən edilməsi. kimi M 1 marşrut ( v və = V 1 , V 2 , V 5 , v s = V 7), 1-ci misalda nəzərdən keçirilir. Onun üçün A(M 1) = 10.
Müstəqilliyi təcrid etmək də asandır M 1 marşrut M 2 = (v və = V 1 , V 3 , V 6 , v s = V 7). Bunun üçün maksimum ötürmə qabiliyyətini hesablayaq və qövslərin ötürmə qabiliyyətini tənzimləyək: A(M 2)=dəq{d 13 , d 36 , d 67 } =dəq{45, 40, 30} = 30. d 13¢ = d 13 - 30 = 15, d 36¢ = d 36 - 30 = 10, d 67¢ = d 67 - 30 = 0.
ADIM 3. Şəbəkədə maksimum axının cari dəyərinin korreksiyası. A t:= A t + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.ADDIM 4. Şəbəkə korreksiyası. tapıldı ADDIM 2 maksimum axınlar A(M 1), A(M 2) marşrutlarda M 1 , M 2 onların qövslərinin tutumundan çıxarılır. Sıfır qalıq tutumu olan qövslər çıxarılır. Nəticə Şəkil 1.16 a-da verilmişdir. a) b) Şəkil 1.16. İterasiyalardan sonra şəbəkə korreksiyasının nəticəsi I Və IISTEP 5. Alqoritmin tamamlanmasının yoxlanılması. Tənzimlənmiş şəbəkədə (şəkil 1.16 a) mənbədən marşrutlar var v və ehtiyat etmək v ilə, Misal üçün M 3 = (v və = V 1 , V 4 , V 2 , V 5 , v s = V 7). Alqoritmin icrasının davam etdirilməsi .II iterasiya. ADDIM 2. Yeganə müstəqil marşrut olaraq götürürük M 3 = (v və = V 1 , V 4 , V 2 , V 5 , v s = V 7). Onun üçün:
A(M 3)=dəq{d 14 , d 42 , d 25 , d 57 } =dəq{15, 10, 10, 15} = 10.
d 14¢ = d 14 - 10 = 5, d 42¢ = d 42 - 10 = 0, d 25¢ = d 25 - 10 = 0, d 57¢ = d 57 - 10 = 5.
ADDIM 3. A t:= A t + A(M 3) = 40 + 10= 50.ADDIM 4. Şəbəkə korreksiyası. Maksimum axın A(M 3) marşrutun qövslərindən çıxın M 13. Nəticə Şəkil 1.16 b-də verilmişdir.
ADDIM 5. Tənzimlənmiş şəbəkədə mənbədən batma marşrutu qalmayıb. A:= A t:= 50, alqoritmin tamamlanması. Cavab:Şəkil 1.15-də şəbəkədə maksimum axın 50-dir.Şəbəkədə bir neçə mənbə göstərilibsə, o, qeyri-məhdud tutumlu qövslərlə orijinal mənbələrə qoşulan yeni ümumi mənbənin təqdim edilməsi ilə tamamlanır. Sonra problem həll olunur adi alqoritmə. Orijinal mənbələrdən tələb olunan axınlar yeni ümumi mənbədən onlara daxil olan yeni əlavə edilmiş qövslər boyunca axınlar olacaqdır. Şəbəkədə bir neçə drenaj varsa, eyni şeyi edin.
Şəbəkə planlaşdırılması
Kifayət qədər mürəkkəb bir obyektin layihələndirilməsi və ya qurulması üçün hər hansı bir vəzifə ( layihə) bir sıra kiçik komponent mərhələlərinə bölünə bilər. From düzgün seçim Bu addımların ardıcıllığı bütün layihənin vaxtından asılıdır.
Layihənin həyata keçirilməsi üçün bütün tədbirlər toplusu təqdim olunur hadisələr Və işləyir. Hadisələr layihənin fərdi mərhələləri adlanır. İş onu tamamlamaq prosesidir. Layihəni başa çatdırmaq üçün lazım olan bütün tədbirlər və iş kompleksi iki qütblü şəbəkə şəklində təqdim edilə bilər G =({v və, v z} , V, X), burada:
və hamısı hadisələr təpələr toplusu ilə qeyd olunur V, arasında xüsusi vurğulanır ilkin hadisə v və(işin başlanğıcı) və yekun hadisə v z(bütün layihənin tamamlanması), şəbəkənin daxili təpələrini müəyyənləşdirir ara hadisələr- prosesdə tamamlanması lazım olan addımlar layihənin icrası,
b) hər şey iş hadisə cütlərini - təpələri birləşdirən qövslərlə işarələnir.
Bu şəbəkənin qrafik təsviri adlanır şəbəkə diaqramı. Hərəkətlərin ardıcıllığını göstərmək üçün şəbəkə diaqramına da daxil olun uydurma əsərlər heç bir hərəkətin yerinə yetirilməsi ilə əlaqəli olmayan. Müvafiq işlər kəsikli qövslərlə göstərilir.
Nümunə olaraq bəzi istehsalın təşkilini nəzərdən keçirək. Layihə aşağıdakı işləri tələb edir:
I) marketinq tədqiqatı, II) avadanlıqlar üzrə dizayndan əvvəl tədqiqat, III) satış şəbəkəsinin təşkili, IV) Reklam kampaniyası, V) istehsal avadanlıqları üçün texniki şərtlərin işlənməsi, VI) işlənməsi texniki sənədlər istehsal binaları və kommunikasiyalar üçün, VII) standart avadanlığın alınması, VIII) qeyri-standart avadanlığın layihələndirilməsi və istehsalı, IX) istehsal müəssisələrinin tikintisi və kommunikasiyaların quraşdırılması, X) standart avadanlıqların quraşdırılması, XI) qeyri-standart avadanlıqların quraşdırılması , XII) istismara verilməsi.
Bu işləri şəbəkə diaqramında müvafiq nömrələri olan qövslərlə işarə edəcəyik.
Bu layihədə hadisələr aşağıdakılar olacaq:
1) işə başlama (ilkin hadisə), 2) tamamlama marketinq araşdırması, 3) layihəqabağı tədqiqatların tamamlanması, 4) satış şəbəkəsinin təşkili, 5) reklam kampaniyasının təşkili, 6) istehsal avadanlıqları üçün texniki şərtlərin hazırlanması, 7) istehsalat binaları və kommunikasiyalar üçün texniki sənədlərin hazırlanmasının tamamlanması , 8) standart avadanlıqların alınmasının başa çatdırılması, 9) qeyri-standart avadanlıqların layihələndirilməsi və istehsalının başa çatdırılması, 10) istehsal müəssisələrinin tikintisinin və kommunikasiyaların quraşdırılmasının başa çatdırılması, 11) avadanlıqların quraşdırılması və istismara verilməsi işlərinin başa çatdırılması,
12) layihənin başa çatması (yekun tədbir).
Biz təpələri müvafiq ədədlərlə hadisələrlə əlaqələndiririk. Şəbəkə diaqramı Layihənin həyata keçirilməsi Şəkildə göstərilmişdir. 1.17:
Şəkil 1.17. Layihə şəbəkə cədvəli
Hamilton dövrləri
Qrafik matris şəklində verilir, burada xanalar nöqtələr arasında hərəkətin dəyərini müəyyənləşdirir. Öz içindəki mənasız yolu aradan qaldırmaq üçün ∞ simvolu əsas diaqonalda yerləşdirilir.
Çünki Əgər alınan matrisdə sıfır elementləri olmayan sütun varsa, onda biz onun içindəki minimum elementi tapıb onu bu sütunun bütün elementlərindən çıxaracağıq.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Bütün çıxılan elementləri yekunlaşdıraq və dövrün aşağı sərhədini alaq in= 2+2+3+2+1=10
1.2. Matrisin bütün sıfır elementlərini qiymətləndirək.
Cədvəldə sıfırların təxmini təqdim edilməsi rahatdır.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ A C =2
1.3. Yollar dəstini iki alt çoxluğa bölək: Q A.C.– qövs (AC) və Q olan yollar A.C.– qövs (AC) olmayan yollar. İkinci alt çoxluq üçün aşağı həddi olacaq: in / = in + θ =10+2=12.
Birinci alt çoxluq üçün sərhədi hesablamaq üçün biz A-sətirini və C-sütununu keçərək bir sıra aşağı olan matrisə keçirik. Yeni matrisdə tərs yolu (CA) aradan qaldırmaq üçün müvafiq xanaya ∞ işarəsini qoyuruq.
Nəticədə 2+0=2 matrisinin sərhədini hesablayaq
və onu döngənin alt sərhədinə əlavə edin. Bu məbləğ // =10+2=12 və birinci alt çoxluq üçün sərhəd olacaq.
1.4. Bütün asma təpələrin sərhədlərini müqayisə edək və ən kiçik sərhədi olan təpəni seçək. Bu təpələrdən ikisi varsa, onlardan hər hansı birini seçin. Bu Q-nın zirvəsidir A.C., onun aşağı həddi =12.
Gəlin təxminlərin maksimumunu seçək θ=max γ=γ BD =3
in / =12+3=15.
1.6. Bütün sonrakı nöqtələri əvvəlkilərə bənzər şəkildə yerinə yetiririk.
Gəlin təxminlərin maksimumunu seçək θ=max γ=γ C B =∞
in / =in+ θ=∞
| A | |
| D |
Bu matrisin bütün sətir və sütunlarında sıfırlar var. Beləliklə, limit 12-yə bərabər olaraq qalır.
TASK. Nəqliyyat şəbəkəsində maksimum axının qiymətini tapın.
PROBLEMİN FORMULASI.
Şəbəkədə nəqliyyat problemini nəzərdən keçirin ( I, D, G) verilmiş qövs tutumları ilə c(i,j).
Gəlin iki sabit təpə seçək: s- mənbə və t- drenaj. Şəbəkədə yayım s→t ədədi funksiyanı çağıraq f, qövslər toplusunda müəyyən edilir və aşağıdakıları təmin edir xətti tənliklər və bərabərsizliklər:
0≤ f(i,j) ≤c(i,j) hər hansı üçün (i,j)
Bir dəyişəni maksimuma çatdırmaq üçün tələb olunur x
L kəsin təpələri ayıran şəbəkədə s t
qövslər çoxluğu adlanır 
İstənilən şəkildə s→t ən azı bir kəsilmiş qövs ehtiva edir.
OPTİMALLIQ MEYARLARI: real şəbəkədə ixtiyari axının qiyməti kəsilmənin ötürmə qabiliyyətini aşmır və maksimum axının dəyəri kəsilmənin minimum ötürmə qabiliyyətinə bərabərdir.
NÜMUNƏ 3.12.
M 9 K
M 8 K
NÜMUNƏ 3.13.
M 2 K
HƏLL :
Çıxan qövsün tutumu (T,B) müvafiq təpəyə daxil olan qövslərin ümumi tutumunu üstələyir. Şəbəkənin real olması üçün c(T,B)=5 əvəz edirik.
Bütün kəsiklərin ötürmə qabiliyyətinin dəyərini tapıb hesablayaq. (K,V) – (T,V) minimum ötürmə qabiliyyəti =6 olan kəsmə. Beləliklə, maksimum axın =6.
Bir neçə mənbə və yuvası olan bir şəbəkə bir mənbə və sink olan bir şəbəkəyə endirilə bilər.
NÜMUNƏ. Bir neçə mənbə S və batan T olsun ( nəqliyyat problemi). İki qovşaq s*, t* və bütün qövsləri (s*, S) , (T,t*) əlavə edərək şəbəkəni genişləndirək. Tutum funksiyasını təyin edərək təyin edək
NARƏLƏRİN YERLƏŞDİRİLMƏSİ METODU.
1. İlkin axın f(i,j) = 0.
Gəlin bu şəbəkənin formasına sahib olan təpələrinə etiketlər təyin edək (i+, ε) və ya
(i - , ε). Mənbəni qeyd edək (-, ∞),
olanlar . ε(s)= ∞.
2. Hər hansı işarələnmiş təpə üçün i
bütün etiketlənməmiş təpələri seçin j
hansı üçün f(i,j)
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
| 1 addım | A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( K,B)=0 |
| Addım 2 | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| Addım 3 | A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| Addım 4 | A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| Addım 5 | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( M,T)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| Addım 6 | A → (-, ∞) M → (A+,1) | Axın optimaldır f=10 Minimum kəsim: M→T-M→R-M→TO |
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, buna görə 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, ona görə də 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 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-yə çatmaq üçün yalnız 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.
| |
| |
| |
| Tapşırıq 2. Avtomobilin yüklənməsi haqqında (kürək çantası haqqında). N element var. Məlum çəki a i və dəyər φi hər bir maddə. ≤ çəki saxlaya bilən kürək çantasını doldurmaq üçün tələb olunur R , ən böyük dəyərə malik olan belə elementlər dəsti.
Sırt çantasının yüklənməsi prosesi N mərhələyə bölünə bilər. Hər addımda biz suala qərar veririk: bu əşyanı götürmək, ya götürməmək? Hər addımda yalnız 2 nəzarət var: nəzarət =1, bu elementi götürsək; və 0 – qəbul etməsək. Növbəti addımdan əvvəl sistemin vəziyyəti əvvəlki addımlar tamamlandıqdan sonra (bəzi elementlər artıq yüklənmişdir) tam yüklənmənin sonuna qədər bizim ixtiyarımızda qalan S çəkisi ilə xarakterizə olunur, yəni. sırt çantasındakı boş yerin miqdarı. ALQORİTM. 1. Son addımdan başlayaq. Sırt çantasındakı boş yer haqqında müxtəlif fərziyyələr edək: S=0.1,…R. Kifayət qədər saxlama yeri varsa, sonuncunu bel çantasına qoyaq. 2. Hər bir əvvəlki addımda bütün mümkün S halları üçün 2 variantı nəzərdən keçiririk: obyekti götürmək və ya götürməmək. Gəlin hər bir halda qazancı cari addımda və artıq optimallaşdırılmış növbəti addımda qazancların cəmi kimi tapaq. Nəticələri köməkçi cədvələ daxil edəcəyik. 3. İlk addımda biz yalnız mümkün olan yeganə vəziyyəti S=R hesab edirik. 4. “geriyə doğru hərəkət etməklə” həll yolu tapaq, yəni. Birinci addımda optimal nəzarəti ələ alaraq, ikinci mərhələdə sistemin vəziyyətini dəyişdiririk: S=R– x 1 a 1 və bu vəziyyət üçün optimal idarə x 2 seçin. və s. NÜMUNƏ 4.2. İlkin məlumatlar
Əsas masa
Köməkçi masa.
Cavab: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 TAPŞIQ 3. Resursların bölüşdürülməsinə dair. P 1, P 2,... P N N müəssisəsi var ki, onların hər biri x məbləğində resurs ayrıldıqda φ k (x) gəlir gətirir. A kəmiyyətində mövcud olan resursun obyektlər arasında bölüşdürülməsi tələb olunur ki, ümumi gəlir maksimum olsun. x k k-ci müəssisəyə ayrılmış resursun miqdarı olsun. Sonra baxılan problem adi problemə endirilir xətti proqramlaşdırma.
Problemi dinamik proqramlaşdırma problemi kimi formalaşdıraq. Birinci addım üçün P 1 müəssisəsinə, ikincisi üçün P 2-yə və s. İdarə olunan sistem bu halda- paylanan vəsaitlər. Hər bir addımdan əvvəl sistemin vəziyyəti bir parametr ilə xarakterizə olunur - hələ sərmayə qoyulmamış mövcud vəsait ehtiyatı. Bu problemdə mərhələli nəzarət müəssisələrə ayrılan vəsaitlərdir. Ümumi gəlirin maksimum olduğu optimal nəzarəti (x 1, x 2,...x N) tapmaq tələb olunur: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
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 mərhələdə idarəetməni seçmək lazımdır ki, bu addımda qazanc və bütün sonrakı addımlarda optimal qazanc 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 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 müəyyən bir kənardan keçən axınlarla "götürülür", nəticədə hər bir 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. Biz fərz edirik ki, i=1.
Bütün j üçün müsbət qalıq tutumu >0 olan kənar boyunca I qovşağından gedə biləcəyiniz j qovşaqları 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ə qaytarmaq. Ə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. 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 alınır. 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
|
Axın miqdarı |
istiqamət |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
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
|
Çıxış nöqtəsi |
Təyinat |
Nəqliyyat planı |
Bant |
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. Şək. 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 var, yəni X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Xətti proqramlaşdırma problemi maksimuma çatmağa yönəlmişdir. 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. Daha sonra hərəkət həcmlərinin qeyri-mənfiliyi 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 haqda "bilmir").
Dağıtım şəbəkəsində məhsulların rasional paylanmasını planlaşdırarkən kanalın tutumunu müştərilərin ehtiyacları və istehsalat zavodunun gücü ilə əlaqələndirmək lazımdır. Bu sinif problemləri maksimum axını tapmaqla həll olunur.
Bir paylama şəbəkəsini nəzərdən keçirək (Şəkil 4.21), burada 0 nöqtəsi (giriş, məsələn, hazır məhsul istehsalçısının anbarı) və P (çıxış, paylama mərkəzləri, topdan və pərakəndə satış təşkilatlarının anbarları, istehlakçı) və hər bir qövs (seqment) birləşdirici nöqtələr i Və j, dij > 0 rəqəmi əlaqələndirilir, çağırılır ötürmə qabiliyyəti qövslər. Ötürmə dəyəri maksimumu xarakterizə edir icazə verilən miqdar vaxt vahidi üçün müvafiq qövs boyunca keçə bilən material axını.
düyü. 4.21.
Bir qövs boyunca keçən məhsulların miqdarı i əvvəl j , biz onu qövs boyunca axın adlandıracağıq ( i ,j ) və ilə işarələnir. Aydındır ki
Şəbəkənin ara nöqtəsinə daxil olan bütün material axınının ondan tamamilə çıxmalı olduğunu nəzərə alsaq, əldə edirik.
Bizdə olan giriş və çıxışda axınların bərabərliyi təbii tələbindən
Z dəyərini şəbəkədəki axının dəyəri adlandıracağıq və yuxarıdakı şərtlərə uyğun olaraq Z-ni maksimuma çatdırmaq problemini qoyacağıq.
Maksimum axını tapmaq minimum kəsmə qabiliyyətini tapmaqdan ibarətdir.
Matris formasında universal axtarış alqoritmini nəzərdən keçirək.
Alqoritmin ilkin mərhələsi matrisin qurulmasından ibarətdir D 0, ötürmə dəyərlərinin daxil edildiyi (istiqamətsiz bir qövs üçün matris elementlərinin simmetrik dəyərlərini alırıq).
Alqoritmin əsas addımları müəyyən bir yolu tapmaq və bu yol boyunca axını düzəltməkdir.
Yol taparkən biz işarələmə prosesindən istifadə edirik. * simvolu ilə matrisin sıfır sətirini və sütununu qeyd edirik (şəbəkə girişi). Axtardığımız 0-cı sətirdə müvafiq sütunları indekslərlə qeyd edirik
və sütun etiketlərini sətirlərə köçürün. Sonra i-ci işarələnmiş cərgəni götürürük, içərisində indeks etiketlərini uyğunlaşdırdığımız işarəsiz sütunu axtarırıq.
Sütun etiketlərini sətirlərə köçürür və n-ci sütun işarələnənə qədər bu prosesi davam etdiririk.
Sonra " tərsinə"İndekslərdən istifadə edərək η-ci təpəyə aparan yolu tapırıq, yolun qövslərinin (matris elementləri) tutumunu azaldırıq. V n və simmetrik elementləri eyni miqdarda artırın.
Bu prosedur nişanlanana qədər davam edir n -zirvələr qeyri-mümkün olmayacaq.
Maksimum axını orijinal matrisdən çıxmaqla tapmaq olar D 0, tutum matrisinin yuxarıdakı düzəlişindən sonra əldə edilmişdir:
Misal 4.4
İstehsalat Moskvada yerləşir. Məhsulları yaymaq üçün şirkət müxtəlif səviyyələrdə paylama mərkəzləri vasitəsilə şirkətlə işləyən vasitəçiləri cəlb edir. Rusiyanın Avropa hissəsində mərkəzi paylama mərkəzi tərəfindən xidmət edilən topdansatış müəssisəsi 1 var. Topdansatış müəssisəsi 2 yaxın xaricdə (Ukrayna, Belarusiya) fəaliyyət göstərir və regional paylama mərkəzi tərəfindən xidmət göstərilir. Şirkətin yerli bazarda (Moskva və Moskva vilayəti) öz müştəriləri var - şəhər paylama mərkəzindən məhsul alan pərakəndə satıcılar. Regional və şəhər paylama mərkəzləri mərkəzi paylama mərkəzindən doldurulur.
Dağıtım şəbəkəsinin bir hissəsini vurğulayaq:
- istehsal müəssisəsinin hazır məhsul anbarı;
- mərkəzi paylama mərkəzi;
- regional paylama mərkəzi;
- şəhər paylama mərkəzi;
- iki topdansatış müəssisəsi;
- şirkətə məxsus pərakəndə satış məntəqəsi;
- istehlakçılar.
düyü. 4.22.
Paylayıcı şəbəkənin hər bir keçidini bir nömrə ilə təyin edək və tutumu qövslərin üstünə qoyun. Keçirmə qabiliyyəti, əlaqənin növündən asılı olaraq, istehsal gücünün həcmi, istehlakçıların planlaşdırılmış ehtiyacı (tələbi) və bazar tutumu ilə ifadə edilə bilər.
Məhsul paylama şəbəkəsinin qrafiki Şəkildə göstərilmişdir. 4.23. Gəlin bir matris quraq D 0, paylayıcı şəbəkə əlaqələrinin ötürmə qabiliyyətinin dəyərlərini daxil edirik (Şəkil 4.24).
düyü. 4.23.
düyü. 4.24.
Sıfır cərgədən 1, 2 və 3 təpələrini (sətir-sütunlar) μ = 0 indeksləri ilə qeyd edirik və V, 30.10 və 10-a bərabərdir.
İşarələnmiş 1-ci sətirdən 4 və 5-ci təpələri μ = 1 və V4 = min (30,15) = 15, V5 = min (30,10) = 10 indeksləri ilə qeyd edin.
3-cü sətirdən 6-cı təpəni və nəhayət, 4-cü sətirdən – 7-ci təpəni qeyd edirik (şəkil 4.25).
düyü. 4.25.
μ boyunca geriyə getməklə yolu tapırıq: 4-dən 7-ci təpəyə, 1-dən 4-cü təpəyə, 0-dan 1-ci təpəyə; tənzimləyici elementlər D 0 hər axın dəyəri V7 = 15.
Növbəti addım 5 axını olan bir yol verir (şək. 4.26).
düyü. 4.26.
Növbəti addım Şəkildə göstərilən nəticəni verir. 4.27.
düyü. 4.27.
Əlavə işarələmə mümkün deyil. Buradan maksimum axın matrisini alırıq (şək. 4.28).
düyü. 4.28.
Şəbəkədə maksimum axını tapmaq üçün alqoritmin tətbiqi nəticəsində nəticələr Şəkil 1-də təqdim olunur. 4.29. Qrafikin qövslərində göstərilən mötərizələrdəki rəqəm cütləri qövsün maksimum ötürmə qabiliyyətini və şəbəkəyə verilən malların tövsiyə olunan həcmini göstərir.
Qövslərdən keçən axınların cəmi v, qövslərdən keçən axınların cəminə bərabərdir w; bu məbləğə axın dəyəri deyilir. Bizi ilk növbədə mümkün olan ən böyük dəyərə malik axınlar - sözdə maksimum axınlar maraqlandıracaq. 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 diqrafik D qövslərinin belə A çoxluğu v V 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 ötürmə qabiliyyətini aşmır və buna görə də hər hansı maksimum axının böyüklüyü heç bir minimum kəsilmənin ötürücülük qabiliyyətini aşmır. 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ə amerikalı riyaziyyatçılar Ford və Fulkerson tərəfindən alınmış 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 v 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 v 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 siz şəbəkə 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ə olunmuş Kitablar:
(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ş
