Тооцооллын алгоритм хамгийн их урсгалсүлжээнд
АЛХАМ 1. Анхны даалгавар.Одоогийн үнэ цэнэ А тСүлжээний хамгийн их урсгалыг 0 утгыг өгдөг. АЛХАМ 2. Сүлжээнд бие даасан маршрутуудыг сонгох, тэдгээрийн урсгалыг тодорхойлох.Сүлжээний эх үүсвэрээс угаалтуур хүртэлх бүх боломжит маршрутуудаас бид бие даасан маршрутуудыг сонгодог М 1 , … , М к, байхгүй нийтлэг оройнууд, эхнийхээс бусад (эх сурвалж v ба) ба эцсийн (ус зайлуулах v хамт). Сонгосон маршрут бүрийн хувьд М и(1£ би£ к) хамгийн их урсгалыг тодорхойлно А(М и).АЛХАМ 3. Сүлжээний хамгийн их урсгалын одоогийн утгыг засах.Бид олсон зүйлсийг нэмнэ АЛХАМ 2бие даасан маршрут дахь хамгийн их урсгалын утгууд М 1 , … , М кодоогийн нийт хамгийн их сүлжээний урсгалд: А т:= A t + A(М 1)+ А(М 2)+…+ А(М к)АЛХАМ 4. Сүлжээний засвар.олсон АЛХАМ 2хамгийн их урсгал А(М 1), … , А(М к) харгалзах сүлжээний нумын багтаамжаас хассан. Тэг үлдэгдэл багтаамжтай нумыг арилгана. АЛХАМ 5. Алгоритмын гүйцэтгэлийг шалгах.Хэрэв залруулсны дараа сүлжээнд эх сурвалжаас ямар ч маршрут үлдэхгүй бол v банөөцлөх v хамт, дараа нь сүлжээнд шаардагдах хамгийн их урсгал нь олсон гүйдэлтэй тэнцүү байна А:= А т, бүх сүлжээний хүчин чадал дууссан тул алгоритм дуусгавар болно. Хэрэв тохируулсан сүлжээнд эх үүсвэрээс замууд байгаа бол v банөөцлөх v хамт, дараа нь очно уу АЛХАМ 2ба алгоритмын гүйцэтгэлийн үргэлжлэл . Жишээ 2.Энэ алгоритмыг ашиглан 1.15-р зурагт сүлжээний хамгийн их урсгалыг ол. Шийдэл.АЛХАМ 1. Анхны даалгавар. А т: = 0.Би давталт. АЛХАМ 2. Сүлжээнд бие даасан маршрутуудыг сонгох, тэдгээрийн урсгалыг тодорхойлох.гэх мэт М 1 явах зам( v ба =V 1 , В 2 , В 5 , v =V-тэй 7), жишээнд авч үзсэн 1. Түүний хувьд А(М 1) = 10.
Мөн бие даасан байдлаар тусгаарлахад хялбар байдаг М 1 маршрут М 2 = (v ба =V 1 , В 3 , В 6 , v =V-тэй 7). Үүний хамгийн их дамжуулах чадварыг тооцоолж, нумын дамжуулалтыг тохируулцгаая. А(М 2)= мин{г 13 , г 36 , г 67 } = мин{45, 40, 30} = 30. г 13¢ = d 13 - 30 = 15, г 36¢ = d 36 - 30 = 10, г 67¢ = d 67 - 30 = 0.
АЛХАМ 3. Сүлжээний хамгийн их урсгалын одоогийн утгыг засах. А т:= A t + A(М 1)+ А(М 2) = 0 + 10+ 30 = 40.АЛХАМ 4. Сүлжээний засвар.олсон АЛХАМ 2хамгийн их урсгал А(М 1), А(М 2) маршрутуудад М 1 , М 2-ыг тэдгээрийн нумын багтаамжаас хасна. Тэг үлдэгдэл багтаамжтай нумыг арилгана. Үр дүнг 1.16 а-р зурагт үзүүлэв. a) b) Зураг 1.16. Давталтын дараа сүлжээний засварын үр дүн IТэгээд IISTEP 5. Алгоритмын гүйцэтгэлийг шалгах.Тохируулах сүлжээнд (Зураг 1.16 а) эх үүсвэрээс гарах маршрутууд байдаг v банөөцлөх v хамт, Жишээлбэл М 3 = (v ба =V 1 , В 4 , В 2 , В 5 , v =V-тэй 7). Алгоритмын гүйцэтгэлийг үргэлжлүүлж байна .II давталт. АЛХАМ 2.Бидний цорын ганц бие даасан зам М 3 = (v ба =V 1 , В 4 , В 2 , В 5 , v =V-тэй 7). Түүнд:
А(М 3)= мин{г 14 , г 42 , г 25 , г 57 } = мин{15, 10, 10, 15} = 10.
г 14¢ = d 14 - 10 = 5, г 42¢ = d 42 - 10 = 0, г 25¢ = d 25 - 10 = 0, г 57¢ = d 57 - 10 = 5.
АЛХАМ 3. A t:= A t + A(М 3) = 40 + 10= 50.АЛХАМ 4. Сүлжээний засвар.Хамгийн их урсгал А(М 3) маршрутын нумуудаас хасах М 13 . Үр дүнг 1.16 б-р зурагт үзүүлэв.
АЛХАМ 5.Тохируулах сүлжээнд эх үүсвэрээс живэх чиглэл байхгүй. А:= А т:= 50, алгоритмын гүйцэтгэл. Хариулт: 1.15-р зурагт сүлжээнд байгаа хамгийн их урсгал нь 50.Сүлжээнд хэд хэдэн эх үүсвэрийг зааж өгсөн бол энэ нь шинэ нийтлэг эх үүсвэрийг нэвтрүүлэх замаар дуусгавар болох бөгөөд энэ нь эх сурвалжтай хязгааргүй хүчин чадалтай нумаар холбогдсон байна. Дараа нь асуудал шийдэгдэнэ ердийн алгоритм руу. Анхны эх үүсвэрээр дамжин өнгөрөх шаардлагатай урсгалууд нь шинэ нийтлэг эх үүсвэрээс тэдгээрт орох шинээр нэмэгдсэн нумын дагуух урсгалууд байх болно. Сүлжээнд хэд хэдэн ус зайлуулах хоолой байгаа бол ижил зүйлийг хий.
Сүлжээний төлөвлөлт
Нилээд төвөгтэй объектыг зохион бүтээх, бүтээх аливаа ажил ( төсөл) хэд хэдэн жижиг бүрэлдэхүүн хэсгүүдэд хувааж болно. -аас зөв сонголтЭдгээр алхмуудын дараалал нь бүхэл бүтэн төслийн цаг хугацаанаас хамаарна.
Төслийг хэрэгжүүлэх бүх арга хэмжээг багц хэлбэрээр үзүүлэв үйл явдалТэгээд ажилладаг. Үйл явдлыг төслийн бие даасан үе шатууд гэж нэрлэдэг. Ажил бол түүнийг дуусгах үйл явц юм. Төслийг дуусгахад шаардлагатай бүх арга хэмжээ, ажлыг хоёр туйлтай сүлжээ хэлбэрээр төлөөлж болно G =({v ба, v z} , V, X), үүнд:
болон бүгд үйл явдалоройн багцаар тэмдэглэгдсэн V,тэдний дунд онцолсон анхны үйл явдал v ба(ажлын эхлэл) ба эцсийн үйл явдал v z(бүх төслийг дуусгах), сүлжээний дотоод оройг тодорхойлно завсрын үйл явдлууд- үйл явцад дуусгах шаардлагатай үе шатууд төслийн хэрэгжилт,
б) бүх зүйл ажилхос үйл явдлуудыг холбосон нумуудаар тэмдэглэгдсэн байдаг - оройнууд.
Энэ сүлжээний график дүрслэлийг нэрлэдэг сүлжээний диаграм.Үйлдлүүдийн дарааллыг зааж өгөхийн тулд сүлжээний диаграммд оруулна уу зохиомол бүтээлүүд, ямар нэгэн үйлдэл хийхтэй холбоогүй. Харгалзах ажлыг тасархай нумаар тэмдэглэв.
Жишээ болгон зарим үйлдвэрлэлийн зохион байгуулалтыг авч үзье. Төсөл нь дараахь ажлыг шаарддаг.
I) маркетингийн судалгаа, II) тоног төхөөрөмжийн дизайны өмнөх судалгаа, III) борлуулалтын сүлжээг зохион байгуулах, IV) явуулах зар сурталчилгааны кампанит ажил, V) үйлдвэрлэлийн тоног төхөөрөмжийн техникийн тодорхойлолтыг боловсруулах, VI) боловсруулах техникийн баримт бичигүйлдвэрлэлийн байр, харилцаа холбоо, VII) стандартын тоног төхөөрөмж худалдан авах, VIII) стандартын бус тоног төхөөрөмжийн зураг төсөл боловсруулах, үйлдвэрлэх, IX) үйлдвэрлэлийн байгууламж барих, харилцаа холбоо суурилуулах, X) стандартын тоног төхөөрөмжийг суурилуулах, XI) стандартын бус тоног төхөөрөмжийг суурилуулах. , XII) ашиглалтад оруулах.
Бид эдгээр ажлыг сүлжээний диаграммд харгалзах тоонуудтай нумаар тэмдэглэнэ.
Энэ төслийн үйл явдлууд дараах байдалтай байна.
1) ажил эхлэх (анхны үйл явдал), 2) дуусгах Маркетингийн судалгаа, 3) зураг төслийн өмнөх судалгааг дуусгах, 4) борлуулалтын сүлжээг зохион байгуулах, 5) сурталчилгааны кампанит ажлыг зохион байгуулах, 6) үйлдвэрлэлийн тоног төхөөрөмжийн техникийн нөхцөлийг бэлтгэх, 7) үйлдвэрлэлийн байр, харилцаа холбооны техникийн баримт бичгийг боловсруулж дуусгах. , 8) стандартын тоног төхөөрөмж худалдан авах ажлыг дуусгах, 9) стандартын бус тоног төхөөрөмжийн зураг төсөл боловсруулах, үйлдвэрлэх ажлыг дуусгах, 10) үйлдвэрлэлийн байгууламж барих, харилцаа холбоог суурилуулах ажлыг дуусгах, 11) тоног төхөөрөмжийг суурилуулах, ашиглалтад оруулах ажлыг дуусгах,
12) төслийг дуусгах (эцсийн үйл явдал).
Бид оройг үйл явдалтай харгалзах тоогоор холбодог. Сүлжээний диаграмТөслийн хэрэгжилтийг Зураг дээр үзүүлэв. 1.17:
Зураг.1.17. Төсөл хэрэгжүүлэх сүлжээний хуваарь
Гамильтоны мөчлөг
График нь матриц хэлбэрээр өгөгдсөн бөгөөд нүднүүд нь цэгүүдийн хоорондох хөдөлгөөний зардлыг тодорхойлдог. Утгагүй замыг арилгахын тулд ∞ тэмдгийг үндсэн диагональ дээр байрлуулна.
Учир нь Хэрэв үүссэн матриц нь тэг элементгүй багана агуулж байвал бид хамгийн бага элементийг олж, энэ баганын бүх элементүүдээс хасах болно.
| А | Б | C | Д | |
| А | ∞ | |||
| Б | ∞ | |||
| C | ∞ | |||
| Д | ∞ |
Бүх хасагдсан элементүүдийг нэгтгэж, мөчлөгийн доод хязгаарыг авцгаая онд= 2+2+3+2+1=10
1.2. Матрицын бүх тэг элементүүдийг үнэлье.
Хүснэгтэнд тэгийн тооцоог үзүүлэх нь тохиромжтой.
| А | Б | C | Д | |
| А | ||||
| Б | ||||
| C | ||||
| Д |
θ=max γ=γ A C =2
1.3. Замуудын багцыг хоёр дэд бүлэгт хуваацгаая: Q А.С.– нуман (AC) ба Q агуулсан замууд А.С.– нум (AC) агуулаагүй замууд. Хоёрдахь дэд багцын доод хязгаар нь: in / = in + θ =10+2=12.
Эхний дэд олонлогийн хил хязгаарыг тооцоолохын тулд бид нэг дарааллаар бага хэмжээтэй матриц руу шилжиж, A мөр ба С баганыг хөндлөн гаргана. Урвуу замыг (CA) арилгахын тулд шинэ матрицад бид харгалзах нүдэнд ∞ тэмдгийг тавина.
Үүссэн 2+0=2 матрицын заагийг тооцоолъё
мөн гогцооны доод хил дээр нэмнэ. Энэ хэмжээ дотор // =10+2=12 бөгөөд эхний дэд олонлогийн хил хязгаар болно.
1.4. Бүх унжсан оройнуудын хилийг харьцуулж, хамгийн бага хилтэй оройг сонгоцгооё. Хэрэв эдгээр оройн хоёр цэг байгаа бол тэдгээрийн аль нэгийг нь сонгоно уу. Энэ бол Q-ийн дээд хэсэг юм А.С., доод хязгаар нь =12.
Тооцооллын хамгийн дээд хэмжээг сонгоцгооё θ=max γ=γ BD =3
-д / =12+3=15.
1.6. Бид дараагийн бүх цэгүүдийг өмнөхтэй адил гүйцэтгэдэг.
Тооцооллын хамгийн дээд хэмжээг сонгоцгооё θ=max γ=γ C B =∞
in / =in+ θ=∞
| А | |
| Д |
Энэ матрицын бүх мөр, баганууд тэгийг агуулна. Тиймээс хязгаар нь 12-той тэнцүү хэвээр байна.
ДААЛГАВАР. Тээврийн сүлжээн дэх хамгийн их урсгалын утгыг ол.
АСУУДЛЫН ТОГТОЛЦОО.
Сүлжээний тээврийн асуудлыг авч үзье ( Би, Д, Г) өгөгдсөн нумын багтаамжтай c(i,j).
Хоёр тогтмол оройг сонгоцгооё: с- эх сурвалж ба т- ус зайлуулах. Сүлжээнд дамжуулах s→t тоон функцийг дуудъя е, нумануудын багц дээр тодорхойлогдсон бөгөөд дараахь зүйлийг хангана шугаман тэгшитгэлба тэгш бус байдал:
0≤ f(i,j) ≤c(i,j)ямар ч хувьд (и, ж)
Хувьсагчийг нэмэгдүүлэхийн тулд шаардлагатай x
Таслах Lоройг тусгаарлах сүлжээнд с т
нумын багц гэж нэрлэдэг 
Ямар ч байсан s→t дор хаяж нэг зүсэгдсэн нумыг агуулна.
ОНОВЧТОЙ БАЙДЛЫН ШАЛГУУР: Бодит сүлжээн дээр дурын урсгалын утга нь зүсэлтийн нэвтрүүлэх чадвараас хэтрэхгүй бөгөөд хамгийн их урсгалын утга нь зүсэлтийн хамгийн бага дамжуулалттай тэнцүү байна.
ЖИШЭЭ 3.12.
М 9 К
М 8 К
ЖИШЭЭ 3.13.
М 2 К
ШИЙДЭЛ :
Гарч буй нумын багтаамж (T,B) нь харгалзах орой руу орох нумын нийт багтаамжаас давсан байна. Сүлжээ бодит болохын тулд бид c(T,B)=5-ийг орлуулна.
Бүх зүсэлтүүдийн нэвтрүүлэх чадварын утгыг олж тооцоолъё. (K,V) – (T,V) хамгийн бага дамжуулах чадвартай зүсэлт =6. Тиймээс хамгийн их урсгал =6.
Хэд хэдэн эх үүсвэр, угаалтуур бүхий сүлжээг нэг эх үүсвэр, угаалтуур бүхий сүлжээ болгон бууруулж болно.
ЖИШЭЭ. Хэд хэдэн S эх үүсвэр ба шингээгч T байх болтугай ( тээврийн асуудал). Хоёр зангилаа s*, t* болон бүх нумуудыг (s*, S) , (T,t*) нэмж сүлжээгээ өргөжүүлье. Тохиргоогоор багтаамжийн функцийг тодорхойлъё
ТЭМДЭГТ БАЙРШУУЛАХ АРГА.
1. Анхны урсгал f(i,j) = 0.
Маягттай байх энэ сүлжээний оройнуудад шошго оноож өгье (i+, ε)эсвэл
(i - , ε).Эх сурвалжийг тэмдэглэе (-, ∞),
тэдгээр . ε(s)= ∞.
2. Аливаа тэмдэглэгдсэн оройн хувьд би
бүх шошгогүй оройг сонго j
Үүний төлөө f(i,j)
Ус зайлуулах суваг тэмдэглэгдэх хүртэл бид энэ үйлдлийг давтана. Хэрэв урсгал нь шошгогүй хэвээр байвал олсон урсгал нь хамгийн их байх ба тэмдэглэгдсэн оройг тэмдэглэгээгүй цэгүүдтэй холбосон нумуудын багц нь хамгийн бага зүсэлт үүсгэдэг.
3. Хувьцааг шошготой болго (j+, ε(t)), Дараа нь f(j,t)-ээр солино f(j,t)+ε(t). Хэрэв хувьцаа тэмдэглэгдсэн бол (j-, ε(t)), Тэр f(j,t)-ээр солино f(j,t)-ε(t). Оргил руугаа явцгаая j. Хэрэв jтэмдэгтэй (i+, ε(j)), дараа нь бид солино f(i,j)дээр f(i,j)+ε(t), мөн хэрэв (i-, ε(j)), f(j,i)-ээр солино f(j,i)-ε(t). Оргил руугаа явцгаая би. Бид эх сурвалжид хүрэх хүртэл энэ үйлдлийг давтана с.Урсгалын өөрчлөлт зогсч, бүх тэмдэг арилж, 2-р алхам руу орно
ЖИШЭЭ 3.14.
М 4 К
| 1 алхам | 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,V)=0 |
| Алхам 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 |
| Алхам 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 |
| Алхам 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 |
| Алхам 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 |
| Алхам 6 | A → (-, ∞) M → (A+,1) | Урсгал нь оновчтой f=10 Хамгийн бага зүсэлт: М→Т-М→Р-М→TO |
ДААЛГАВАР. Сүлжээний хамгийн өндөр урсгалыг ол
АЛГОРИТМ
Оройг тэмдэглэе s= x 0. Бусад нь бүгд x i.
1-р шат.
1. Бүх нумууд нь ханаагүй ямар ч замыг сонго.
2. Бид ханасан нум байхгүй болтол энэ замын дагуух урсгалын хэмжээг нэгээр нэмэгдүүлнэ.
Бид бүрэн урсгалыг барих хүртэл урсгалыг нэмэгдүүлэх үйл явцыг үргэлжлүүлнэ, i.e. ямар ч зам дор хаяж нэг ханасан нум агуулна.
2-р шат.
2. Хэрвээ х i нь аль хэдийн тэмдэглэгдсэн орой бол (+i) ханаагүй нумууд х i-ээс очдог бүх тэмдэглэгээгүй оройг (–i) индексээр тэгээс өөр урсгалтай нумууд гардаг бүх тэмдэглэгдээгүй оройг тэмдэглэнэ. х i.
3. Хэрэв энэ үйл явцын үр дүнд орой тэмдэглэгдсэн бол т, дараа нь хооронд сТэгээд тБүх оройг нь өмнөх оройнуудын тоогоор тэмдэглэсэн зам байдаг. Бид энэ замын бүх нуман дахь урсгалыг нэгээр нэмэгдүүлдэг сруу тнумын чиглэл нь хөдөлгөөний чиглэлтэй давхцаж байгаа бөгөөд хэрэв нум нь эсрэг чиглэлтэй байвал нэгээр багасна. 1-р алхам руу шилжье.
4. Дээд талд байх үед түйл явц дууссан гэж тэмдэглэх боломжгүй бөгөөд үүнээс үүсэх урсгал нь сүлжээний хамгийн том урсгал юм.
ЖИЧ. Та эхний шатыг дуусгахгүйгээр 2-р шат руу явж болно (жишээ 3.16-г үзнэ үү).
ЖИШЭЭ 3.15.
9
ШИЙДЭЛ:
Өгөгдсөн тээврийн сүлжээнд бүрэн урсгал олдсон. Ханасан нумуудыг тодруулсан
Энэ сүлжээнд та мөн төгсгөлийн оройг тэмдэглэж болох бөгөөд тэмдэглэгээний үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид эцсийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 10-тай тэнцүү байна.
ЖИШЭЭ 3.16.
8 2 1
Өгөгдсөн тээврийн сүлжээнд бүрэн бус урсгал илэрсэн
Сүлжээг тэмдэглэж, алгоритмын дагуу урсгалыг нэмэгдүүлье. Бид авдаг
Энэ сүлжээнд та мөн төгсгөлийн оройг тэмдэглэж болох бөгөөд тэмдэглэгээний үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид эцсийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 6-тай тэнцүү байна.
IV хэсэг. Динамик програмчлал.
Динамик програмчлалыг олон үе шаттай оновчтой шийдлүүдийг олоход ашигладаг. Тухайлбал, тоног төхөөрөмжийг солих урт хугацааны төлөвлөлт; салбарын үйл ажиллагаа хэдэн жилийн . Энэ нь оновчтой байх зарчмыг ашигладаг бөгөөд үүний дагуу аливаа шинэ хэсэгчилсэн шийдэл нь хүрсэн төлөвтэй харьцуулахад оновчтой байх ёстой.
Нэгийг олон удаа шийдсэн нь дээр энгийн даалгаварнэгээс илүү төвөгтэй.
АСУУДАЛ 1. Хоёр цэгийн хоорондох хамгийн ашигтай замын тухай.
А ба В хоёр цэгийг холбосон замыг барих шаардлагатай бөгөөд хоёр дахь нь эхнийхээс зүүн хойд зүгт байрладаг. Энгийнээр хэлэхэд, зам тавих нь хэд хэдэн алхмаас бүрдэх бөгөөд алхам бүрт бид хойд эсвэл зүүн тийш шилжих боломжтой гэж үзье. Дараа нь аливаа зам нь шаталсан тасархай шугам бөгөөд сегментүүд нь координатын тэнхлэгүүдийн аль нэгэнд параллель байна. Эдгээр хэсэг тус бүрийг барих зардал нь мэдэгдэж байна.
ЖИШЭЭ 4.1. А-аас В хүртэлх хамгийн бага замыг ол.
Сүүлийн алхам бол T.V. Сүүлчийн алхамаас өмнө бид ТВ-д нэг алхмаар хүрч болох цэгүүд дээр байж болно. Ийм хоёр цэг байдаг (систем нь хоёр муж улсын аль нэгэнд байж болно). Тэд тус бүрийн хувьд t.V хүрэх цорын ганц сонголт байдаг: нэг нь - зүүн тийш шилжих; нөгөөгийн хувьд - хойд зүгт. Тохиолдол бүрт 4 ба 3-ын зардлыг бичье.
4
Одоо эцсийн өмнөх алхамыг оновчтой болгоё. Өмнөх алхмын дараа бид C 1, C 2, C 3 гэсэн гурван цэгийн аль нэгэнд орж болно.
C 1 цэгийн хувьд зөвхөн нэг удирдлага байна (үүнийг сумаар тэмдэглэе) - зүүн тийш шилжих бөгөөд зардал нь 2 (энэ алхамд) + 4 (дараагийн алхамд) = 6 болно. Үүний нэгэн адил С 3 зүйлийн хувьд зардал 2+3=5 болно. t.C 2-ийн хувьд зүүн эсвэл хойд зүг рүү явах хоёр удирдлага байдаг. Эхний тохиолдолд зардал 3+3=6, хоёр дахь тохиолдолд 1+4=5 байна. Энэ нь болзолт оновчтой хяналт нь хойшоо явах явдал юм. Үүнийг сумаар тэмдэглээд харгалзах зардлыг оруулъя.
| |
| |
| |
| ДААЛГАВАР 2. Машиныг ачих тухай (үүргэвчний тухай). N зүйл байна. Мэдэгдэж буй жин a i ба үнэ цэнэ φi зүйл бүр. ≤ жин барих чадвартай үүргэвчийг дүүргэх шаардлагатай Р , хамгийн их үнэ цэнэтэй зүйлсийн багц.
Үүргэвчийг ачаалах үйл явцыг N үе шатанд хувааж болно. Алхам бүрт бид асуултыг шийддэг: энэ зүйлийг авах уу, авахгүй юу? Алхам бүрт зөвхөн 2 удирдлага байдаг: хяналт =1, хэрэв бид энэ зүйлийг авбал; ба 0 - хэрэв бид үүнийг авахгүй бол. Дараагийн алхамын өмнөх системийн төлөв байдал нь S жингээр тодорхойлогддог бөгөөд өмнөх алхмуудыг гүйцэтгэсний дараа (зарим зүйл аль хэдийн ачаалагдсан) бүрэн ачаалагдах хүртэл бидний мэдэлд хэвээр байна. үүргэвчин дэх чөлөөт зайны хэмжээ. АЛГОРИТМ. 1. Сүүлийн алхамаас эхэлцгээе. Үүргэвчний чөлөөт зайны талаар янз бүрийн таамаглал дэвшүүлье: S=0.1,...R. Сүүлчийн зүйлийг үүргэвчиндээ хангалттай хадгалах зайтай бол хийцгээе. 2. Өмнөх алхам бүрт бүх боломжит S төлөвийн хувьд объектыг авах эсвэл авахгүй байх 2 сонголтыг авч үздэг. Тохиолдол бүрийн олзыг одоогийн болон дараагийн оновчтой алхамын олсон ашгийн нийлбэрээр олъё. Бид үр дүнг туслах хүснэгтэд оруулна. 3. Эхний алхамд бид зөвхөн цорын ганц боломжтой S=R төлөвийг авч үзнэ. 4. "Ухрах" замаар шийдлийг олцгооё, өөрөөр хэлбэл. Эхний шатанд оновчтой хяналтыг авч, хоёр дахь шатанд системийн төлөвийг өөрчилнө: S=R– x 1 a 1мөн энэ төлөвийн хамгийн оновчтой хяналтын х 2-г сонгоно. гэх мэт. ЖИШЭЭ 4.2. Анхны өгөгдөл
Үндсэн хүснэгт
Туслах хүснэгт.
Хариулт: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 ДААЛГАВАР 3. Нөөцийн хуваарилалтын тухай. P 1, P 2,... P N N аж ахуйн нэгжүүд байдаг бөгөөд тэдгээр нь х хэмжээний нөөцийг хуваарилсан тохиолдолд тус бүр нь φ k (x) орлогыг бий болгодог. Нийт орлого хамгийн их байхын тулд А хэмжээтэй нөөцийг объектуудын хооронд хуваарилах шаардлагатай. k-т аж ахуйн нэгжид хуваарилагдсан нөөцийн хэмжээг x k гэж үзье. Дараа нь авч үзэж буй асуудал нь ердийн асуудал болж буурдаг шугаман програмчлал.
Асуудлыг динамик програмчлалын бодлого гэж томъёолъё. Эхний алхамд бид P 1 аж ахуйн нэгжид, хоёр дахь нь - P 2-д хөрөнгө оруулалт хийх болно. Удирддаг систем дотор энэ тохиолдолд- хуваарилагдсан хөрөнгө. Алхам бүрийн өмнөх системийн төлөв байдал нь нэг параметрээр тодорхойлогддог - хараахан хөрөнгө оруулаагүй байгаа хөрөнгийн нөөц. Энэ асуудалд шат шатны хяналт нь аж ахуйн нэгжүүдэд хуваарилагдсан хөрөнгө юм. Нийт орлого хамгийн их байх хамгийн оновчтой хяналтыг (x 1, x 2,...x N) олох шаардлагатай. | 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 |
Хариулт: x 1 =1; x 3 =0; x 3 =4; W=3.5
НЭГДСЭН АЛГОРИТМ
1. Системийг тайлбарлана уу. Өөрөөр хэлбэл, алхам бүрийн өмнө хяналттай системийн төлөв байдлыг ямар үзүүлэлтээр тодорхойлдог болохыг олж мэдээрэй. Хяналттай системийн тайлбарыг аль болох хялбаршуулж, шаардлагагүй нарийн ширийн зүйлээр хэт ачаалалгүйгээр даалгавраа зөв, "даруухан" тавьж чаддаг байх нь чухал юм.
2. Үйлдлийг үе шат (үе шат) болгон хуваах. Удирдлагад тавьсан бүх боломжийн хязгаарлалтыг энд харгалзан үзэх ёстой. Алхам нь хангалттай бага байх ёстой бөгөөд ингэснээр алхмын хяналтын оновчлолын процедур нь нэлээд энгийн байх ёстой; Үүний зэрэгцээ алхам нь хэтэрхий жижиг байх ёсгүй бөгөөд ингэснээр оновчтой шийдлийг олох процедурыг төвөгтэй болгодог шаардлагагүй тооцоолол хийхгүй байх ёстой, гэхдээ оновчтой шийдэлд мэдэгдэхүйц өөрчлөлт оруулахгүй байх ёстой. зорилгын функц.
3. Алхам бүрийн хяналтын багц x i болон тэдгээрт тавигдах хязгаарлалтыг олж мэд.
4. Хэрэв өмнө нь систем S төлөвт байсан бол x i удирдлага нь i шатанд ямар ашиг авчрахыг тодорхойл. Төлбөрийн функцуудыг бичнэ үү:
w i =f i (S, x i)
5. Х i дээр удирдлагын нөлөөгөөр системийн төлөв байдал хэрхэн өөрчлөгдөхийг тодорхойлно 1-р алхам, өөрөөр хэлбэл төлөвийн өөрчлөлтийн функцийг бичих.
S / =φ i (S, x i)
6. Мэдэгдэж байгаа функцээр нөхцөлт оновчтой олзыг илэрхийлэх үндсэн давтагдах динамик програмчлалын тэгшитгэлийг бич.
W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))
7. Үйлдвэрлэх нөхцөлт оновчлолЭцсийн алхам хэрхэн дууссан талаар янз бүрийн таамаглал дэвшүүлж, эдгээр таамаглал бүрийн хувьд хамгийн сүүлийн алхамд нөхцөлт (алхам ямар нэгэн зүйлээр дууссан гэсэн нөхцөл дээр үндэслэн сонгосон) оновчтой хяналтыг олох.
W m (S)= max(f m (S, x m))
8. Эцсийн өмнөх алхамаас эхлээд эхний алхам хүртэл (буцаж) нөхцөлт оновчлолыг гүйцэтгэнэ.
9. Үйлдвэрлэх болзолгүй оновчлолхяналт, алхам бүрт холбогдох зөвлөмжийг "унших": эхний алхамд олсон оновчтой хяналтыг авч, системийн төлөвийг өөрчлөх, олсон төлөвийн хувьд хоёр дахь алхамд оновчтой хяналтыг олох гэх мэт. сүүлчийн алхам хүртэл.
ОНОВЧТОЙ БАЙХ ЗАРЧИМ. Дараагийн алхамд орохын өмнө системийн төлөв байдал ямар ч байсан, энэ үе шатанд хяналтыг сонгох шаардлагатай бөгөөд ингэснээр энэ алхам дахь ашиг болон дараагийн бүх үе шатанд оновчтой ашиг хамгийн их байх болно.
Динамик програмчлалын зарчим нь алхам бүрийг бусдаас үл хамааран тусад нь оновчтой болгодог гэсэн үг биш юм. Хэрэв энэ алхам нь дараагийн алхамуудад сайн ялах боломжоо алдах юм бол тодорхой нэг алхам дээр үр дүнтэй байх хяналтыг сонгох нь ямар учиртай вэ?
Практикт үйл ажиллагааг тодорхой бус хугацаагаар төлөвлөх тохиолдол байдаг. Ийм тохиолдлын загвар нь бүх алхмууд тэнцүү байх хязгааргүй алхамт хяналттай процесс юм. Энд ялалтын функц болон төлөвийг өөрчлөх функц нь алхамын дугаараас хамаарахгүй.
Бүлэг V. ЗУРАГЧЛАЛЫН ЗАГВАРЧИЛГАА
Энэхүү алгоритмын санаа нь эх үүсвэрээс живэх хүртэлх эерэг урсгал бүхий төгсгөл хүртэлх замыг олох явдал юм.
(Анхны) багтаамжтай (i, j) ирмэгийг авч үзье. Алгоритмыг гүйцэтгэх явцад энэ хүчин чадлын зарим хэсгийг өгөгдсөн ирмэгээр дамжин өнгөрөх урсгалаар "авдаг" бөгөөд үүний үр дүнд ирмэг бүр нь үлдэгдэл багтаамжтай байх болно. Бичих - үлдэгдэл зурвасын өргөн. Бүх ирмэгүүд нь үлдэгдэл багтаамжтай сүлжээг үлдэгдэл гэж нэрлэнэ.
i зангилаанаас урсгалыг хүлээн авч буй дурын j зангилааны хувьд бид тэмдэглэгээг тодорхойлно, үүнд j зангилаанаас i зангилаа руу урсах урсгалын утга байна. Хамгийн их урсгалыг олохын тулд бид дараах алхмуудыг гүйцэтгэдэг.
Бүх ирмэгийн хувьд бид үлдэгдэл хүчин чадлыг анхны хүчин чадалтай тэнцүү гэж тогтоосон, өөрөөр хэлбэл. = тэнцүү гэж үзье. 1-р зангилааг шошготойгоор оноож тэмдэглэе. Бид i=1 гэж таамаглаж байна.
Бүх j-д эерэг үлдэгдэл багтаамж >0 бүхий ирмэгийн дагуу I зангилаанаас очиж болох j зангилааны багц. Хэрэв бид 3-р үе шатыг хийвэл, үгүй бол бид 4-т очно.
Бид k зангилаанаас ийм зүйлийг олдог. Бид k зангилааг шошготой байрлуулж тэмдэглэе. Хэрэв k=n бол төгсгөл хоорондын зам олдож, 5-р шат руу явна, үгүй бол i=k гэж тохируулаад 2-р шат руу буцна.
Буцаах. Хэрэв i=1 бол төгсгөл хоорондын зам боломжгүй бөгөөд 6 руу очно уу. Хэрэв i зангилааны өмнөхөн хаяглагдсан r зангилаа олоод r зангилааны зэргэлдээх зангилааны багцаас хасна. Бид i=r гэж тохируулаад 2-р шат руу буцна.
Үлдэгдэл сүлжээний тодорхойлолт. Эх зангилаа (зангилаа 1) -ээс угаалтуур зангилаа (зангилаа n) хүртэл p_th олсон төгсгөл хүртэлх замыг дайран өнгөрөх зангилааны багцаар тэмдэглэе. Дараа нь энэ замаар өнгөрөх хамгийн их урсгалыг
Төгсгөл хүртэлх замыг бүрдүүлдэг ирмэгүүдийн үлдэгдэл багтаамж нь урсгалын чиглэлд тодорхой хэмжээгээр буурч, эсрэг чиглэлд ижил хэмжээгээр нэмэгддэг.
Тэр. Төгсгөлийн замд орсон ирмэгийн (i, j) хувьд одоогийн үлдэгдэл хүчин чадал өөрчлөгдөнө.
1) хэрэв урсгал i зангилаанаас j хүртэл явбал,
2) хэрэв урсгал j зангилаанаас i хүртэл явбал.
a) m төгсгөл хоорондын зам олдвол хамгийн их урсгалыг дараах байдлаар илэрхийлнэ
б) Ирмэгийн эхний ба эцсийн хүчин чадлын утгуудыг (i, j) авч үзвэл бид энэ ирмэгээр дамжин өнгөрөх оновчтой урсгалыг дараах байдлаар тооцоолж болно. Үүнийг тавья. Хэрэв >0 бол ирмэгээр (i, j) дамжин өнгөрөх урсгал тэнцүү байна. Хэрэв >0 бол урсгал тэнцүү байна. (>0 ба >0 аль аль нь боломжгүй тохиолдолд).
Жишээ 1. Сүлжээний хамгийн их урсгалыг ол Зураг. 1
Давталт 1. =
3) k=3, учир нь. Бид 3-р зангилааг шошготойгоор оноож, тэмдэглэнэ. i=3 ба 2 руу буцах)
5) k=5 ба. Бид 5-р зангилааг шошгоор тэмдэглэнэ. Бид дамжин өнгөрөх замыг олж авдаг.
6) бид төгсгөл хүртэлх замыг 5-р зангилаанаас эхлээд 1-р зангилаагаар төгссөн шошгон дээр тодорхойлно: . Тэгээд. Бид зам дээрх үлдэгдэл хүчин чадлыг тооцоолно.
Давталт 2.
1) ба зангилаа 1-ийг шошгоор тэмдэглэнэ. i=1
2") (тиймээс 5-р зангилааг оруулаагүй болно
3") k=4 ба зангилаа 4-ийг шошгон дээр тэмдэглэнэ. i=4 ба 2 руу буцах)
2""") (1 ба 3-р зангилаанууд тэмдэглэгдсэн тул тэдгээрийг оруулаагүй болно)
3""") k=5 ба. Бид 5-р зангилааг шошгон дээр тэмдэглэнэ. Төгсгөл хүртэлх замыг олж авна. 5 руу очно уу)
Давталт 3.
1) ба зангилаа 1-ийг шошгоор тэмдэглэнэ. i=1
3) k=2, зангилаа 2-ыг шошгон дээр тэмдэглэнэ. i=2 ба 2 руу буцах)
3") k=3 ба. 3-р зангилааг шошготой тэмдэглэнэ. i=3 ба 2 руу буцна уу)
2") (үүнээс хойш) 4 рүү очно уу)
4) 3-р зангилааны шошго нь өмнөх зангилааны дугаарыг харуулна. Энэ давталт дээр 3-р зангилаа цаашид анхааралдаа авахгүй бөгөөд түүний шошгыг зурсан байна. 2 руу буцах)
2""") (3-р зангилаа төгсгөл хүртэлх замаас хасагдсан тул)
3""") ба. Бид 5-р цэгийг шошготойгоор тэмдэглэнэ. Төгсгөл хүртэлх замыг олж авна. 5 руу очно уу)
5) би. Бид зам дээрх үлдэгдэл хүчин чадлыг тооцоолно.
Давталт 4. Энэ давталт дээр зам нь
Давталт 5. Энэ давталт дээр зам нь
Давталт 6: 1-р зангилаанаас үүссэн бүх ирмэгүүд нь тэг үлдэгдэл багтаамжтай тул шинэ төгсгөл хоорондын зам боломжгүй. Шийдлийг тодорхойлохын тулд 6) руу очно уу
6) сүлжээн дэх урсгалын хамгийн их хэмжээ нь нэгжтэй тэнцүү байна.
Төрөл бүрийн ирмэгийн дагуух урсгалын утгыг анхны хүчин чадлын утгуудаас хамгийн сүүлийн үлдэгдэл хүчин чадлын утгыг хасч тооцдог.
Тооцооллын үр дүн: хүснэгт. 1
|
Урсгалын хэмжээ |
чиглэл |
||
|
(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) |
Хамгийн их урсгалыг олох алгоритмын график дараалсан гүйцэтгэл (жишээ 1)
e) f) Дамжуулах зам байхгүй
Цагаан будаа.
Тээврийн системийн талаархи анхны мэдээлэл, жишээлбэл, үйлдвэр доторх, Зураг дээр үзүүлэв. 2, мөн хүснэгтээр тодорхойлж болно (Хүснэгт 2).
Хүснэгт 2. Хамгийн их урсгалын асуудлын анхны өгөгдөл
Тээврийн системийн хамгийн дээд хүчин чадал нь 6-аас хэтрэхгүй, учир нь 0-р цэгээс 6-аас илүүгүй ачаа, тухайлбал 1-р цэг хүртэл 2 нэгж, 2-р цэг хүртэл 3 нэгж, 3-р цэг хүртэл 1 нэгж ачаа илгээх боломжтой. Дараа нь 0 цэгээс гарах 6 нэгж ачаа бүгд эцсийн цэгт хүрсэн эсэхийг шалгах шаардлагатай. 1-р цэгт ирсэн 2 нэгж ачааг 4-р цэг рүү шууд илгээх боломжтой. 2-р цэгт ирсэн ачаа хуваах шаардлагатай: 2 нэгжийг 4-р цэг рүү нэн даруй, 1 нэгжийг 3-р завсрын цэг рүү (2 ба 4-р цэгүүдийн хоорондох хэсгийн багтаамж хязгаарлагдмал тул) илгээнэ. Дараах ачааг 3-р цэгт хүргэсэн: 0-р цэгээс 1 нэгж, 3-р цэгээс 1 нэгж. Бид тэдгээрийг 4-р цэг рүү илгээдэг. Тиймээс тээврийн системийн хамгийн их нэвтрүүлэх чадвар нь 6 нэгж ачаа юм. Энэ тохиолдолд 1-ээс 2-р цэгийн хоорондох дотоод хэсгүүдийг (салбарууд), түүнчлэн 1-ээс 3-р цэгүүдийн хоорондох хэсгийг ашиглахгүй. 1-ээс 4-р цэгийн хоорондох салбарыг бүрэн ачаагүй - 2 нэгж ачааг түүнтэй хамт илгээдэг. дамжуулах чадвар 3 нэгж. Шийдлийг хүснэгт хэлбэрээр гаргаж болно (Хүснэгт 3)
Хүснэгт 3. Хамгийн их урсгалын асуудлыг шийдэх
|
Гарах цэг |
Очих газар |
Тээврийн төлөвлөгөө |
Дамжуулах зурвасын өргөн |
Урсгалыг нэмэгдүүлэх шугаман програмчлалын асуудал.Шугаман програмчлалын хувьд хамгийн их урсгалын бодлогыг томъёолъё. K цэгээс М цэг хүртэлх тээвэрлэлтийн эзэлхүүнийг X KM гэж үзье. Зураг. 2 K = 0,1,2,3, M = 1,2,3,4, тээвэрлэлт нь зөвхөн өндөр тоотой цэг хүртэл боломжтой. Энэ нь X KM нийт 9 хувьсагчтай гэсэн үг, тухайлбал X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Шугаман програмчлалын бодлого нь хамгийн их байлгахад чиглэгдсэн. урсгал нь дараах хэлбэртэй байна.
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 км? 0, K, M = 0, 1, 2, 3, 4
Энд F нь зорилгын функц, нөхцөл (0) нь тээврийн системд бараа орохыг тодорхойлдог. Нөхцөл (1) - (3) системийн 1-3 дугаар зангилааны тэнцвэрийн харьцааг тогтооно. Өөрөөр хэлбэл, дотоод зангилаа бүрийн хувьд орж ирж буй барааны урсгал нь гарч буй урсгалтай тэнцүү бөгөөд бараа нь системд хуримтлагддаггүй бөгөөд дотор нь "төрдөггүй". Нөхцөл (4) нь системээс ачааллыг "гарах" нөхцөл юм. Нөхцөл (0)-ын хамт энэ нь системийн бүхэлдээ тэнцвэрийн харьцааг бүрдүүлдэг ("оролт" нь "гаралт"-тай тэнцүү). Дараах есөн тэгш бус байдал нь тээврийн системийн бие даасан "салбар" -ын хүчин чадлыг хязгаарладаг. Дараа нь хөдөлгөөний хэмжээ, зорилгын функцийн сөрөг бус байдлыг харуулав. Сүүлчийн тэгш бус байдал нь зорилгын функцийн хэлбэр (харилцаа (0) эсвэл (4)) болон хөдөлгөөний эзлэхүүний сөрөг бус байдлаас үүдэлтэй нь тодорхой байна. Гэсэн хэдий ч сүүлчийн тэгш бус байдал нь зарим зүйлийг агуулдаг ерөнхий мэдээлэл- ачааны эерэг эзэлхүүнийг системээр дамжуулж болно, эсвэл тэг (жишээлбэл, систем дотор тойрог хөдөлгөөн байгаа бол) сөрөг биш (энэ нь эдийн засгийн утгагүй, гэхдээ албан ёсны) математик загварЭнэ талаар "мэдэхгүй").
Түгээх сүлжээнд бүтээгдэхүүний зохистой хуваарилалтыг төлөвлөхдөө сувгийн хүчин чадлыг хэрэглэгчдийн хэрэгцээ, үйлдвэрлэлийн үйлдвэрийн хүчин чадалтай уялдуулах шаардлагатай. Энэ ангиллын асуудлыг хамгийн их урсгалыг олох замаар шийддэг.
Түгээлтийн сүлжээг авч үзье (Зураг 4.21), үүнд 0 цэг (орц, жишээлбэл, бэлэн бүтээгдэхүүний үйлдвэрлэгчийн агуулах) ба П (гарц, түгээлтийн төв, бөөний болон жижиглэнгийн худалдааны байгууллагын агуулах, хэрэглэгч) болон нуман (сегмент) бүрийг холбох цэгүүд би Тэгээд j, dij > 0 тоо холбоотой, гэж нэрлэдэг нэвтрүүлэх чадвар нумууд. Дамжуулах чадвар нь хамгийн дээд хэмжээг тодорхойлдог зөвшөөрөгдөх хэмжээнэгж хугацаанд харгалзах нумын дагуу өнгөрөх материалын урсгал.
Цагаан будаа. 4.21.
-аас нумын дагуу өнгөрч буй бүтээгдэхүүний тоо хэмжээ би өмнө j , бид үүнийг нумын дагуух урсгал гэж нэрлэх болно ( би ,j ) ба -аар тэмдэглэнэ. Энэ нь ойлгомжтой
Сүлжээний завсрын цэг рүү орж буй бүх материалын урсгал түүнээс бүрэн гарах ёстойг харгалзан үзвэл бид олж авна.
Орц, гарц дахь урсгалын тэгш байдлыг хангах байгалийн шаардлагаас
Бид Z-ийн утгыг сүлжээн дэх урсгалын утга гэж нэрлээд, дээрх нөхцлүүдийн дагуу Z-ийг нэмэгдүүлэх асуудлыг тавина.
Хамгийн их урсгалыг олох нь хамгийн бага зүсэлтийн нэвтрүүлэх чадварыг олоход хүргэдэг.
Бүх нийтийн хайлтын алгоритмыг матриц хэлбэрээр авч үзье.
Алгоритмын эхний үе шат нь матрицыг бүтээхээс бүрдэнэ Д 0, дамжуулах чадварын утгуудыг оруулсан болно (чиглэлгүй нумын хувьд бид матрицын элементүүдийн тэгш хэмтэй утгыг авдаг).
Алгоритмын гол үе шатууд нь тодорхой замыг олох, энэ зам дагуух урсгалыг засах явдал юм.
Замыг олохдоо бид тэмдэглэгээний процессыг ашигладаг. Бид матрицын тэг мөр ба баганыг * тэмдгээр тэмдэглэнэ (сүлжээний оролт). Бид хайж буй 0-р мөрөнд харгалзах багануудыг индексээр тэмдэглээрэй
баганын шошгыг мөр рүү шилжүүлнэ. Дараа нь бид i-р тэмдэглэгдсэн мөрийг авч, дотроос нь тэмдэглэгээгүй баганыг хайж, индекс шошготой таарч байна.
Бид баганын шошгыг мөр рүү шилжүүлж, n-р баганыг тэмдэглэх хүртэл энэ процессыг үргэлжлүүлнэ.
Дараа нь " эсрэгээр"Индексийн тусламжтайгаар бид η-р орой руу хөтөлсөн замыг олж, замын нумын багтаамжийг (матрицын элементүүд) бууруулна. В n ба тэгш хэмтэй элементүүдийг ижил хэмжээгээр нэмэгдүүлнэ.
Энэ процедур нь тэмдэглэгээ хүртэл үргэлжилнэ n -Топууд боломжгүй зүйл болохгүй.
Хамгийн их урсгалыг анхны матрицаас хасах замаар олж болно Д 0, хүчин чадлын матрицын дээрх залруулгын дараа олж авсан:
Жишээ 4.4
Үйлдвэрлэл нь Москвад байрладаг. Бүтээгдэхүүн түгээхийн тулд компани нь янз бүрийн түвшний түгээлтийн төвүүдээр дамжуулан компанитай хамтран ажилладаг зуучлагчдыг татдаг. ОХУ-ын Европын хэсэгт төв түгээлтийн төвөөр үйлчилдэг бөөний худалдааны 1 үйлдвэр байдаг. Бөөний 2-р үйлдвэр нь ойрын гадаадад (Украйн, Беларусь) үйл ажиллагаа явуулдаг бөгөөд бүс нутгийн түгээлтийн төвөөр үйлчилдэг. Тус компани нь орон нутгийн зах зээлд (Москва, Москва муж) өөрийн үйлчлүүлэгчидтэй байдаг - хотын түгээлтийн төвөөс бүтээгдэхүүн хүлээн авдаг жижиглэн худалдаачид. Бүс, хотын түгээлтийн төвүүдийг төв түгээх төвөөс тэжээдэг.
Түгээх сүлжээний нэг хэсгийг онцолж үзье.
- үйлдвэрлэлийн аж ахуйн нэгжийн бэлэн бүтээгдэхүүний агуулах;
- төв түгээх төв;
- бүс нутгийн түгээлтийн төв;
- хотын түгээлтийн төв;
- хоёр бөөний аж ахуйн нэгж;
- компанийн эзэмшдэг жижиглэн худалдааны цэг;
- хэрэглэгчид.
Цагаан будаа. 4.22.
Түгээх сүлжээний холбоос бүрийг тоогоор тодорхойлж, хүчин чадлыг нумын дээгүүр байрлуулцгаая. Холболтын төрлөөс хамааран дамжуулах чадварыг үйлдвэрлэлийн хүчин чадлын хэмжээ, хэрэглэгчдийн төлөвлөсөн хэрэгцээ (эрэлт), зах зээлийн багтаамжаар илэрхийлж болно.
Бүтээгдэхүүний түгээлтийн сүлжээний графикийг Зураг дээр үзүүлэв. 4.23. Матриц бүтээцгээе Д 0, Бид түгээлтийн сүлжээний холбоосуудын дамжуулах чадварын утгыг оруулна (Зураг 4.24).
Цагаан будаа. 4.23.
Цагаан будаа. 4.24.
Тэг эгнээнээс 1, 2, 3-р оройг (мөр-багана) μ = 0 индексээр тэмдэглэнэ. V, 30.10 ба 10-тай тэнцүү байна.
Тэмдэглэгдсэн 1-р мөрөөс 4 ба 5-р оройг μ = 1 ба V4 = min (30,15) = 15, V5 = min (30,10) = 10 индексээр тэмдэглэнэ.
3-р мөрөнд бид 6-р оройг, эцэст нь 4-р мөрөнд - 7-р оройг тэмдэглэнэ (Зураг 4.25).
Цагаан будаа. 4.25.
μ-ийн дагуу буцах замаар бид замыг олно: 4-ээс 7-р орой руу, 1-ээс 4-р орой руу, 0-ээс 1-р орой руу; тохируулагч элементүүд Д Урсгалын утга бүрт 0 V7 = 15.
Дараагийн алхам нь 5-р урсгалтай замыг өгдөг (Зураг 4.26).
Цагаан будаа. 4.26.
Дараагийн алхам нь зурагт үзүүлсэн үр дүнг өгнө. 4.27.
Цагаан будаа. 4.27.
Цаашид тэмдэглэгээ хийх боломжгүй. Эндээс бид хамгийн их урсгалын матрицыг авдаг (Зураг 4.28).
Цагаан будаа. 4.28.
Сүлжээний хамгийн их урсгалыг олох алгоритмыг хэрэглэсний үр дүнд үр дүнг Зураг дээр үзүүлэв. 4.29. Графикийн нуман дээр харуулсан хаалтанд байгаа хос тоонууд нь нумын хамгийн их дамжуулах чадвар ба сүлжээнд нийлүүлэх санал болгож буй барааны хэмжээг заана.
Нуман дамжих урсгалын нийлбэр v, нь нумын ослын урсгалын нийлбэртэй тэнцүү байна w; энэ нийлбэрийг урсгалын утга гэж нэрлэдэг. Бид юуны түрүүнд хамгийн их урсгал гэж нэрлэгддэг хамгийн их утгатай урсгалыг сонирхох болно. IN ерөнхий тохиолдолсүлжээ нь хэд хэдэн өөр өөр хамгийн их урсгалтай байж болох ч тэдгээрийн утга нь ижил байх ёстой. (4)
N = (V,D,a) сүлжээгээр дамжих хамгийн их урсгалыг судлах нь огтлолын тухай ойлголттой нягт холбоотой, i.e. ямар ч энгийн гинжин хэлхээний шинж чанарыг агуулсан диграф D нумын ийм А олонлог vВ А-д хамаарах нумыг дайран өнгөрнө.Зүсэлтийн багтаамж нь түүнд хамаарах нумын багтаамжийн нийлбэр юм. Боломжит хамгийн бага дамжуулалттай зүсэлтийг хамгийн бага зүсэлт гэж нэрлэдэг.
Аливаа урсгалын хэмжээ нь ямар ч зүсэлтийн дамжуулах чадвараас хэтрэхгүй, тиймээс хамгийн их урсгалын хэмжээ нь хамгийн бага зүсэлтийн нэвтрүүлэх чадвараас хэтрэхгүй. Гэсэн хэдий ч энэ хоёр нь тодорхойгүй байна сүүлийн тоонуудүргэлж бие биетэйгээ тэнцүү байх; Энэ үр дүнг Америкийн математикч Форд, Фулкерсон нар 1955 онд гаргаж, хамгийн их урсгал ба хамгийн бага зүсэлтийн теорем гэж нэрлэжээ.
Теорем (хамгийн их урсгал ба хамгийн бага зүсэлтийн тухай). Аливаа сүлжээнд хамгийн их урсгалын хэмжээ нь хамгийн бага зүсэлтийн хүчин чадалтай тэнцүү байна.
Хамгийн их урсгал ба хамгийн бага зүсэлтийн теорем нь өгөгдсөн урсгал нь хамгийн их эсвэл үгүй эсэхийг шалгах боломжийг олгодог, гэхдээ зөвхөн маш энгийн сүлжээнүүдийн хувьд. Мэдээжийн хэрэг, бодит байдал дээр бид том, нарийн төвөгтэй сүлжээнүүдтэй харьцах ёстой бөгөөд ерөнхийдөө энгийн сонголтоор хамгийн их урсгалыг олоход хэцүү байдаг. Бүхэл тоо дамжуулах чадвартай аль ч сүлжээнд хамгийн их урсгалыг олох нэг алгоритмыг тайлбарлая.
1-р алхам. Эхлээд тэгээс өөр утгатай урсгалыг сонгоё (хэрэв ийм урсгал байгаа бол). Жишээлбэл, хэрэв N нь зурагт үзүүлсэн сүлжээ юм. 29.3, дараа нь зурагт үзүүлсэн урсгал. 29.4. Бидний сонгосон анхны урсгалын утга их байх тусам дараагийн алхамууд хялбар байх болно гэдгийг тэмдэглэх нь зүйтэй.
Алхам 2. N дээр үндэслэн бид урсгалын чиглэлийг эсрэгээр нь өөрчилснөөр шинэ N сүлжээг байгуулна. Илүү нарийвчлалтайгаар (a) = 0 байх аливаа а нум нь анхны хүчин чадлаараа N'-д үлдэж, ямар ч a нум нь багтаамжтай a нумаар, (a) багтаамжтай эсрэг талын нумаар солигдоно. Бидний жишээн дээрх N сүлжээг Зураг дээр үзүүлэв. 29.5. Орой vэх үүсвэр байхаа больж, угаалтуур болжээ.
Алхам 3. Хэрэв N' сүлжээнд бид тэгээс ялгаатай урсгалыг олж чадна vв, дараа нь үүнийг анхны урсгалд нэмж, N-д илүү том утгатай шинэ урсгалыг авч болно. Одоо та сүлжээг байгуулахдаа N'-ийн оронд N' шинэ утсыг ашиглан 2-р алхамыг давтаж болно. Энэ процедурыг давтснаар бид эцэст нь тэгээс өөр урсгалгүй N' сүлжээнд хүрэх болно; дараа нь харгалзах урсгал нь хамгийн их урсгал байх болно. Жишээлбэл, Зураг дээр. 29.5 нуман дундуур урсдаг тэгээс өөр урсгал байдаг ( v, u), (у,з), (z,x), (x,y) ба ( у,) нь нэгтэй тэнцүү бөгөөд үлдсэн нумуудаар дамжин өнгөрөх урсгалууд нь тэгтэй тэнцүү байна. Зураг дээрх урсгалд энэ урсгалыг нэмбэл. 29.4, бид зурагт үзүүлсэн урсгалыг олж авна. 29.6; 2-р алхамыг давтах нь энэ нь хамгийн их урсгал гэдгийг харуулахад хялбар юм.
Ашигласан номууд:
(1) http://pgap.chat.ru/zap/zap264.htm#0
(2) Асанов М.О., Баранский В.А., Расин В.В. Дискрет математик: матроид график, алгоритм
(3) Басакер Р., Саати Т. Төгсгөлийн график ба сүлжээ.
(4) Вилсон Р. Графикийн онолын танилцуулга
