Форд-Фулкерсоны аргыг ашиглан хамгийн их урсгалыг олох жишээ. Хамгийн их урсгалыг олох арга
Компьютерийн сүлжээний захиалагчдын хооронд мэдээлэл солилцох, олон компьютерийн цогцолбор дээр зэрэгцэн тооцоолох, асуудлын шийдлийг хэд хэдэн процессоруудад хуваарилах, компьютерийн сүлжээнд хуваалцсан санах ойг ашиглах, процессор бүр хуваалцсан санах ойн модулиудад хандах хандалт хязгаарлагдмал байх үед. өгөгдсөн хугацааны интервалд хамгийн их хэмжээний мэдээллийг шилжүүлэх асуудал үүсдэг.
Тээврийн системийг ажиллуулах явцад тээврийн нэгжийг сүлжээний зангилааны хооронд солилцох үед хамгийн их тоог шилжүүлэх асуудал үүсдэг. тээврийн нэгжүүдтодорхой хугацааны дотор.
Эрчим хүчийг шилжүүлэх үед цахилгаан сүлжээ, дамжуулах хоолойн систем дэх шингэн, тухайн хугацаанд эрчим хүч, бодисыг хамгийн их хэмжээгээр хуваарилах, шилжүүлэх асуудал үүсдэг.
Сүлжээний нэг онцлог нь эхийн орой ба шингээгч орой байгаа, график дахь бүх шугамын сегментийн чиглэл, гогцоо, олон нум байхгүй байх явдал юм.
Сүлжээнд x i зангилаанаас x j зангилаа хүртэл дамжих мэдээлэл, энерги, бодисын хэмжээг гэнэ урсгал болон j ij гэж тэмдэглэнэ.
Нуман (x i , x j) алгасаж болох хамгийн том урсгалыг нэрлэнэ нэвтрүүлэх чадвар нумууд ба ij -ээр тэмдэглэгдсэн байдаг.
ij-тэй 0£j ij £ нь ойлгомжтой.
Х 0 эх орой дээр урсгалын утга нь x 0 оройноос гарч буй бүх нумын дагуух урсгалын нийлбэр юм, өөрөөр хэлбэл. j=å i j 0i + .
Угаалтуурын орой дээр х k , урсгалын утга нь х k орой руу орж буй бүх нумын дагуух урсгалуудын нийлбэр юм. j=å i j ik - .
Аливаа завсрын оройн x i-ийн хувьд гарах урсгалын нийлбэр нь ирж буй урсгалын нийлбэртэй тэнцүү байна, i.e. å j j ij + =å k j ik - .
Зураг дээр. 3.29-ийг үзүүлэв нөхцөлт сүлжээ, эх зангилаа x 0 , шингээгч зангилаа x k болон хоёр завсрын зангилаа x i ба x j зэргийг агуулсан. Нуман тус бүр дээр хаалтанд урсгалын тэмдэглэгээ ба зурвасын өргөнхаргалзах нум. Энэ тохиолдолд сүлжээнд нийлүүлэх урсгал нь j=(j 0i +j 0j), сүлжээнээс шилжүүлсэн урсгал нь j=(j ik +j jk), x i оройноос x j орой хүртэлх урсгалтай тэнцүү байна. j ij -тэй тэнцүү байна. X i оройн хувьд j 0i =(j ij +j ik), оройн хувьд x j - j jk =(j 0j +j ij) байна.
Графикийн оройн олонлог нь огтлолцдоггүй хоёр дэд олонлогт хуваагдсан ба тэдгээрийн нэг нь эх орой, нөгөө нь живэх оройг агуулдаг бол эдгээр хоёр олонлогийг холбосон нумын олонлог үүсдэг. зүсэлт Мөн i , түүний зурвасын өргөн нь нумын зурвасын өргөнүүдийн нийлбэртэй тэнцүү байна. Ийм хэд хэдэн зүсэлт байж болно.
Хүснэгтэнд сүлжээний дөрвөн хэсгийг Зураг дээр үзүүлэв. 3.29
| Зүсэлт | нумын багтаамж Сij | нэвтрүүлэх чадвар | ||||
| C 0 i | C 0 j | C i j | С би к | C jk | хэсэг С(A i) | |
| А 1 | C 0i + C 0j | |||||
| А 2 | С 0j +С ij +С ik | |||||
| А 3 | С ik +С jk | |||||
| А 4 | С 0i +С ij +С jk |
Жишээлбэл, А 1 зүсэлтийн хувьд бид X'=(x 0 ) ба X\X'=(x i , x j , x k ), A 2-д - X'=(x 0 , x i ) болон X\X' \u003d байна. (x j, x k), A 3-ийн хувьд - X'=(x 0, x i, x j) ба X\X'=(x k), A 4-ийн хувьд - X'=(x 0, x j) ба X\X'= (x i , x k ).
Мэдээжийн хэрэг, хамгийн их урсгалын утга нь тухайн хэсгийн хамгийн бага нэвтрүүлэх чадвараар хязгаарлагддаг, i.e.
j max =min(C(A i))
Тиймээс, өгөгдсөн нумын багтаамжтай сүлжээн дэх хамгийн их урсгалыг зүсэлтийн дамжуулалтыг тооцоолж, тэдгээрийн хамгийн бага хэмжээг сонгох замаар олж болно. Гэсэн хэдий ч энэ шийдлийн тусламжтайгаар нуман дээрх урсгалын тархалт тодорхойгүй хэвээр байна.
Нуман дээрх урсгалын тархалтыг хайх хэд хэдэн алгоритмыг боловсруулсан. Тэдний дунд онцгой байр суурийг Форд-Фулкерсоны алгоритм эзэлдэг бөгөөд түүний мөн чанар нь графикийн оройг тэмдэглэх явдал юм.
Графикийн дээд талын шошго нь урсах урсгалыг өөрчлөх боломжийг харуулж байна өгөгдсөн ороймөн энэ өөрчлөлтийн эх үүсвэрийг заана. Зураг дээр. 3.30 нь алгоритмын мөн чанарыг тайлбарласан сүлжээний хэсэг юм.
Хэрэв нумын дагуу (x s , x i) урсгалыг нэмэгдүүлэх боломжтой бол (j si< c si), то вершину х i следует пометить +s , что указывает на источник увеличения потока.
Хэрэв нумын дагуу (x i , x j) урсгалыг нэмэгдүүлэх боломжтой бол j ij< c ij , то вершину х j пометить +i . Это означает, что приращение потока Dj si пойдет по направлению дуги (х i , х j) от вершины х s .
Хэрэв нум (x s , x i) ханасан бол, i.e. j si =c si , тэгвэл +s шошгыг x i орой дээр байрлуулах боломжгүй. Иймд x i оройг тэмдэглээгүй бол x j оройг +i гэж тэмдэглэж болохгүй.
Хэрэв нумын дагуу (x t , x j) урсгалыг нэмэгдүүлэх боломжтой бол, i.e. j tj< c tj , то вершину х j следует пометить +t , что указывает на источник увеличения потока.
Хэрэв х j оройг +i гэж тэмдэглээгүй бол сүлжээний фрагмент дахь урсгалыг нэмэгдүүлэхийн тулд нуман дахь урсгалыг (х i , х j) багасгаж, фрагментийн бусад нумын дагуу цааш нь ус зайлуулах хоолой руу чиглүүлэх хэрэгтэй. . Үүнийг харуулахын тулд x i оройг - j гэж тэмдэглэв. Энэ нь хэсэг дэх урсгалын нийт өсөлтөөр (x i , x j) үүнийг Dj tj утгаар бууруулах ёстой гэсэн үг юм.
Хэрэв нум нь ханасан бол (x t, x j), i.e. j tj =c tj , тэгвэл +t шошгыг x j орой дээр байрлуулах боломжгүй. Иймд x j оройг тэмдэглээгүй бол x i оройг -j гэж тэмдэглэж болохгүй.
Хэрэв нумууд (х s , х i) ба (х t , х j) хоёулаа ханасан байвал Dj si ба Dj tj урсгалыг нэмэгдүүлэх боломжгүй гэсэн үг бол x i ба x j оройн дээр шошго тавих боломжгүй болно. мөн сүлжээний дараагийн оройг угаалтуурын орой хүртэл үргэлжлүүлэн тэмдэглэнэ.
Ийнхүү урсгалын хамгийн их утгад х s ба x t эхийн оройноос нумын дагуух x i ба x j шингээгч орой хүртэл хүрнэ.
Форд-Фулкерсоны алгоритм:
1-р алхам: графикийн бүх оройд 0,1,2,...k индекс оноох; энд 0 нь графикийн эх зангилааны индекс, k нь графикийн живэх зангилааны индекс;
алхам 2: эхний оройд "0" гэсэн шошгыг оноох;
алхам 3: тэмдэглэгдсэн х s оройноос ханаагүй нумууд очдог бүх тэмдэглэгдээгүй оройг х i , нумын дагуух x s оройноос урсах урсгалыг нэмэгдүүлэх боломжийг илэрхийлдэг “+s” индексээр тэмдэглэнэ (х s , х i) ;
алхам 4: бүх тэмдэглэгдээгүй оройнууд x i , тэдгээрээс нумууд (ханасан эсвэл ханаагүй) тэмдэглэгдсэн орой руу х j , "-j" индексээр тэмдэглэсэн бөгөөд энэ нь нумын дагуух x j орой руу урсах урсгалыг багасгах боломжийг илтгэнэ (x i , x j) ;
алхам 5: хэрэв эдгээр үйлдлүүдийн үр дүнд шингээгчийн орой x k тэмдэглэгдсэн бол сүлжээний эхний ба эцсийн оройнуудын хооронд бүх орой нь өөр өөр бөгөөд тэмдэг хүртэл тэмдэглэгдсэн байдаг. Шилжилтийг бүрдүүлдэг өмнөх оройнуудын индексүүд, тэдгээрийн дагуу та урсгалыг нэмэгдүүлж, 6-р алхам руу очно уу, үгүй бол төгсгөл.
алхам 6: 5-р алхамд үүссэн маршрутын урсгалыг нэг нэгээр нь нэмэгдүүлж, 3-р алхам руу орно.
Алгоритмын төгсгөлийн шинж тэмдэг бол угаалтуурын оройг тэмдэглэх боломжгүй юм.
Жишээ: Зураг дээр. 3.31 графикийг өгөв. Сүлжээнд хамгийн их урсгал ба түүний тархалтын утгыг ол.
Нуман бүр дээр (x i , x j) урсгал ба дамжуулах чадварын утгыг - (j ij , c ij) заана.
Бүх тооцоог хоёр хүснэгтийн хүснэгтэд нэгтгэн харуулав a)
| x i | давталтын алхам | ||||||
| x 0 | |||||||
| x 1 | +0 | +0 | +0 | +0, -3 | -3 | - | - |
| x 2 | +0;+3 | +0;+3 | +0 | +0 | +0 | +0 | - |
| x 3 | +0;+1 | +0;+1 | +0;+1 | +0 | +0 | - | - |
| х к | +1;+2;+3 | +1;+2 | +1;+2 | +1;+2 | +1,+2 | +2 | - |
хүснэгт b)
| (x i , x j) | ij-тэй | давталтын алхам | ||||||
| (x 0, x 1) | ||||||||
| (x 0, x 2) | ||||||||
| (x 0, x 3) | ||||||||
| (x 1, x 3) | ||||||||
| (x 1, x k) | ||||||||
| (x 2, x k) | ||||||||
| (x 3, x 2) | ||||||||
| (x 3, x k) |
Хүснэгт a)-д давталтын алхам бүр дээр графикийн орой тус бүрийн хувьд боломжит шошгыг зааж өгсөн ба b хүснэгтэд нуман дагуух урсгалын өсөлтийг (x i , x j) өгсөн болно. Графикийн ханасан нумуудыг тодоор тэмдэглэв
Эхний давталтын алхамын үр дүнд шилжилт хийх боломжтой: n 0k = ((x k, x 1, x 0); (x k, x 2, x 0); (x k, x 2, x 3, x 0); (x k, x 2, x 3, x 1, x 0);
(x k, x 3, x 0); (x k, x 3, x 1, x 0)). n 0k =(x k, x 3, x 0)-г сонгоё. Dj=1 дээрх урсгалын өсөлт нь m=((x 0 , x 3), (x 3 , x k)) маршрутын дагуу дамждаг.
Хоёр дахь шатанд ижил шилжилт хийх боломжтой. n 0k =(x k , x 3 , x 0) шилжилтийг сонгоё. Dj=1 дээрх урсгалын өсөлт нь m=((x 0 , x 3), (x 3 , x k)) маршрутын дагуу дамждаг. Энэ тохиолдолд нум (x 3 , x k) ханасан байна, өөрөөр хэлбэл j 3k =c 3k =2.
Гурав дахь алхамд шилжилт хийх боломжтой: n 0k = ((x k, x 1, x 0); (x k, x 2, x 0); (x k, x 2, x 3, x 0); (x k, x) 2, x 3, x 1, x 0)). n 0k =(x k, x 2, x 3, x 1, x 0)-г сонгоё. Dj=1 дээрх урсгалын өсөлт нь m=((x 0 , x 1), (x 1 , x 3), (x 3 , x 2), (x 2 , x k)) маршрутын дагуу явагдана. Энэ тохиолдолд нум нь ханасан (x 3, x 2), өөрөөр хэлбэл j 32 \u003d c 32 \u003d 1 болж хувирдаг.
Дөрөв дэх алхамд шилжилт хийх боломжтой: n 0k =((x k, x 1, x 0); (x k, x 2, x 0)). n ok =(x k, x 1, x 0)-г сонгоё. Урсгалын өсөлт Dj=1 нь m=((x 0 , x 1), (x 1 , x k)) маршрутын дагуу явна. Энэ тохиолдолд нум нь ханасан (x 0, x 1), өөрөөр хэлбэл j 01 \u003d c 01 \u003d 2 болж хувирдаг.
Тав дахь алхамд шилжилт хийх боломжтой: n 0k \u003d ((x k, x 1, -x 3, x 0); (x k, x 2, x 0)). n ok =(x k, x 1, -x 3, x 0)-г сонгоё. Урсгалын өсөлт Dj=1 нь m=((x 0 , x 3), (x 3 , x 1), (x 1 , x k))), маршрутын дагуу явна. Энэ тохиолдолд нум нь ханасан (x 0, x 3) болж хувирна, өөрөөр хэлбэл j 03 \u003d c 03 \u003d 3.
Зургаа дахь алхамд нумууд (x 0, x 1) ба (x 0, x 3) ханасан тул зөвхөн нэг шилжилт хийх боломжтой n 0k \u003d (x k, x 2, x 0). Урсгалын өсөлт Dj=1 нь m=((x 0 , x 2), (x 2 , x k)) маршрутын дагуу явна. Энэ тохиолдолд нум нь ханасан (x 0, x 2), өөрөөр хэлбэл j 02 \u003d c 02 \u003d 1 болж хувирдаг.
Долоо дахь алхамд (x 0, x 1), (x 0, x 3) ба (x 0, x 2) нумууд ханасан, шошго тавих боломжгүй тул x o-оос x k руу шилжих боломжгүй. оройнууд x 1, x 2, болон x 3 .
Сүлжээнд урсдаг
Хамгийн их урсгалын асуудал
E оройгуудын багц ба E цэгээс авсан зарим эрэмбэлэгдсэн хос оройг холбосон нумын багцаас бүрдсэн сүлжээг өгье. Бид үүнийг тэгш хэмтэй график гэж үзэх болно, өөрөөр хэлбэл нум () сүлжээнд орсон бол, дараа нь энэ нь тэгш хэмтэй нумыг агуулдаг (), гэхдээ бодит байдал дээр ийм нум байхгүй байж болно. Тодорхой байхын тулд бид сүлжээний оройд дараах тоонуудыг онооно: . Орой бүр нь эрч хүчээр тодорхойлогддог. ,-ийн оройг эх үүсвэр гэж нэрлэдэг бөгөөд оройг нь угаалтуур, бусад нь завсрын цэг юм. Зарим урсгалыг эх үүсвэрээс угаалтуур руу нэг төрлийн бодис (хий, шингэн) эсвэл тээвэрлэлт - сүлжээний зам дагуу явуулдаг. Сүлжээний нуман () бүрт нумын зурвасын өргөн гэж нэрлэгддэг дугаар өгөгддөг. Нумын багтаамж гэдэг нь нэгж цаг тутамд өнгөрөх хамгийн их урсгал юм. Let , болон үлдсэн оройн хувьд, дараа нь - цорын ганц эх үүсвэр, - цорын ганц угаалтуур, ба - сүлжээний завсрын зангилаанууд.
Даалгавар нь тухайн сүлжээнд эх үүсвэрээс угаалтуур хүртэлх урсгалын хамгийн их утгыг тодорхойлох явдал юм. Сүлжээний эх үүсвэрээс угаалтуур хүртэлх урсгалын дагуу бид сүлжээний бүх нумын дагуух урсгалын багцыг () гэсэн үг бөгөөд нумын дагуух урсгал хаана байна (), 
, нэгж хугацаанд түүгээр хөдөлсөн бодисын хэмжээтэй тэнцүү байна. Математикийн хувьд хамгийн их урсгалын асуудлыг дараах байдлаар томъёолсон болно: бүгдэд сөрөг бус утгыг олох, хамгийн их байлгах.
(3.9)
хязгаарлалттай:
(3.11)
Нөхцөл (3.9) нь эх үүсвэрээс урсах буюу угаалтуур руу урсах бодисын хэмжээтэй тэнцүү байх хамгийн их урсгалын утгыг илэрхийлнэ. Нөхцөл (3.10) нь нуман тус бүрийн дагуух урсгал нь сөрөг бус байх ёстой бөгөөд түүний багтаамжаас хэтрэхгүй байх ёстой; (3.11) нөхцөлөөс аливаа завсрын орой руу урсах бодисын хэмжээ нь түүнээс урсаж буй бодисын хэмжээтэй тэнцүү байна.
Одоогоор бид нэг эх үүсвэр, угаалтууртай сүлжээг авч үзсэн. Гэвч бодит байдал дээр эх үүсвэр, угаалтуурын тоо дур зоргоороо байж болно. Топологийн бага зэрэг өөрчлөлтийн тусламжтайгаар энэ төрлийн асуудлыг аль хэдийн авч үзсэн асуудлууд руу бууруулж болохыг харуулъя.
Үүнийг жишээгээр тайлбарлая.
Гурван эх үүсвэр, хоёр угаалтуураас бүрдэх сүлжээг авч үзье (Зураг 3.10). Энэ сүлжээг тодорхой болгохын тулд дараах асуудлыг тайлбарлая.
Газрын тос олборлох газрууд газарзүйн байршилд байрладаг. Үйлдвэрлэсэн газраасаа газрын тосыг зарим завсрын цэгээр дамжуулан боловсруулах үйлдвэрт хүргэдэг. Тэдгээрийг холбосон тээврийн маршрут бүхий цэгүүдийн багцыг Зураг дээр сүлжээ хэлбэрээр дүрсэлсэн болно. 3.10, нумууд нь хурдны замд, орой нь бие даасан цэгүүдэд (уул уурхайн талбай, үйлдвэр, шахуургын станц эсвэл төмөр замын станц) тохирно. Тээврийн хурдны замын нэвтрүүлэх чадварыг сүлжээний нумануудад хуваарилдаг. Аль нь болохыг тодорхойлохын тулд дээд хэмжээгазрын тосыг үйлдвэрлэлийн талбайгаас боловсруулах үйлдвэр рүү зөөвөрлөх боломжтой тул нэг зохиомол эх үүсвэр, нэг зохиомол угаалтуур нэмж сүлжээг өргөжүүлэх шаардлагатай (зураг дээрх зохиомол нумуудыг тасархай шугамаар зурсан).
Мэдээжийн хэрэг, анхны сүлжээ болон өргөтгөсөн сүлжээн дэх урсгалын хэмжээ нь анхны сүлжээний нумын дамжуулалтаар тодорхойлогддог. Тиймээс, олон тооны эх үүсвэрээс угаалтуур хүртэлх хамгийн их урсгалын асуудал нь нэг эх үүсвэрээс нэг угаалтуур хүртэлх хамгийн их урсгалын асуудалтай тэнцүү юм.
Цагаан будаа. 3.10. Зохиомол эх сурвалж ба угаалтуурын танилцуулга
Жишээ 3
Excel програмын хамгийн их урсгалын асуудлыг шийдэх жишээг өгье. Зарим тээврийн сүлжээг авч үзье (Зураг 3.11.). Мөн бид замын хөдөлгөөний урсгал зарим нумын хоёр чиглэлд явж болно гэж таамаглаж байна (Мэдээжийн хэрэг, энэ тохиолдол нь нэг чиглэлтэй хөдөлгөөний урсгалаас илүү ерөнхий бөгөөд шийдвэрлэхэд илүү төвөгтэй байдаг). Зураг нь хоёр чиглэлд хамгийн их дамжуулах чадварыг харуулж байна: жишээлбэл, 4 нэгжийн эрчимтэй урсгалыг 3-р цэгээс 6-р цэг хүртэл, мөн ижил урсгалыг 6-р цэгээс 3-р цэг хүртэл тээвэрлэж болно (төгсгүүдэд тэг байна) зарим нумууд нь холбогдох чиглэлд тээвэрлэх боломжгүй гэсэн үг юм). Сүлжээний хамгийн их дамжуулах чадварыг бүхэлд нь тодорхойлох шаардлагатай, өөрөөр хэлбэл. хамгийн их утгаурсгал .
Цагаан будаа. 3.11. сүлжээний диаграмжишээ 3.
Шийдэл.
Завсрын сүлжээний зангилаа бүрийн хувьд орж ирж буй нийт урсгал нь нийт гарах урсгалтай тэнцүү байх ёстой гэж үздэг тул асуудлыг дараах байдлаар томъёолж болно.
Хязгаарлагдмал дор нэмэгдүүлэх:
Зурагт заасны дагуу ажлын хуудсан дээрх өгөгдлийг оруулъя. 3.12.
Цагаан будаа. 3.12. Хамгийн их урсгалын асуудлыг шийдвэрлэх өгөгдөл
A6: Q6 нүднүүдийн мужийг хувьсагчдын тооцоолсон утгуудад онооно. A8:A14 нүднүүд, мөн F13 зорилтот нүдэнд дараах томьёог оруулна
| C6+D6+I6-E6-H6-J6 |
|
| G6+N6+H6+K6-L6-I6-M6-P6 |
|
| F13 (зорилтот) |
Шийдлийг хайж эхэлсний дараа бид дараахь хязгаарлалтуудыг нэвтрүүлэх болно.
Харилцах цонхонд Шийдэл хайж байна өөрчлөх нүдний мужийг A6:Q6 гэж зааж өгнө.
Шийдлийн үр дүнд бид хариултыг авна: ; нуман дахь урсгалыг доор үзүүлэв
| Цэгүүд (зангилаа) | Цэгүүд (зангилаа) | ||
Энэ асуудал нь өвөрмөц бус оновчтой шийдэлтэй, өөрөөр хэлбэл хамгийн их урсгал нь 17 нэгж байвал нуман дээрх урсгалын өөр хуваарилалт байж болно гэдгийг тэмдэглэх нь зүйтэй.
Түгээх сүлжээнд бүтээгдэхүүний зохистой хуваарилалтыг төлөвлөхдөө сувгийн зурвасын өргөнийг хэрэглэгчдийн хэрэгцээ, хүчин чадалтай уялдуулах шаардлагатай. үйлдвэрлэлийн аж ахуйн нэгж. Энэ ангиасуудлыг хамгийн их урсгалыг олох аргаар шийддэг.
0 цэгийг тодруулсан түгээлтийн сүлжээг (Зураг 4.21) авч үзье (оролт, жишээлбэл, агуулах гэх мэт. бэлэн бүтээгдэхүүнүйлдвэрлэгч) ба П (гарц, түгээлтийн төв, бөөний болон жижиглэнгийн худалдааны байгууллагын агуулах, хэрэглэгч) болон нуман (сегмент) бүрийг холбох цэгүүд би болон j, тоо dij > 0 оноогдсон, дуудагдсан нэвтрүүлэх чадвар нумууд. Дамжуулах чадварын утга нь нэгж хугацаанд харгалзах нумыг дамжин өнгөрөх материалын урсгалын хамгийн их зөвшөөрөгдөх хэмжээг тодорхойлдог.
Цагаан будаа. 4.21.
-аас нумын дагуу өнгөрөх бүтээгдэхүүний хэмжээ би өмнө j , бид нумын дагуух урсгалыг дуудах болно ( би ,j ) ба -аар тэмдэглэнэ. Энэ нь ойлгомжтой
Хэрэв бид сүлжээний завсрын цэг рүү орсон бүх материалын урсгал нь түүнийг бүрэн орхих ёстойг харгалзан үзвэл бид олж авна.
-аас байгалийн эрэлтБидэнд байгаа оролт ба гаралтын урсгалын тэгш байдал
Бид Z-ийн утгыг сүлжээн дэх урсгалын утга гэж нэрлээд дээр дурдсан нөхцлөөр Z-ийг хамгийн их байлгах асуудлыг тавина.
Хамгийн их урсгалын эрэл хайгуул нь хамгийн бага зүсэлтийн нэвтрүүлэх чадварыг хайх хүртэл буурдаг.
Бүх нийтийн хайлтын алгоритмыг матриц хэлбэрээр авч үзье.
Алгоритмын эхний үе шат нь матрицыг бүтээхээс бүрдэнэ Д 0, зурвасын өргөний утгуудыг оруулсан (чиглээгүй нумын хувьд бид матрицын элементүүдийн тэгш хэмтэй утгыг авдаг).
Алгоритмын үндсэн алхамууд нь ямар нэг замыг хайж олох, энэ замын дагуух урсгалыг засах явдал юм.
Зам хайхдаа бид тэмдэглэгээ хийх процессыг ашигладаг. Бид матрицын хоосон мөр ба баганыг (сүлжээний оролт) * тэмдгээр тэмдэглэнэ. 0-р мөрөнд бид харгалзах багануудыг индексээр тэмдэглэнэ
болон баганын шошгыг мөр рүү шилжүүлэх. Дараа нь бид ί-р тэмдэглэгдсэн мөрийг авч, дотор нь тэмдэглэгээгүй баганыг хайж, шошго-индексийг харьцуулна.
Бид баганын шошгыг мөрөнд шилжүүлж, 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-р орой хүртэл; элементүүдийг тохируулах Д V7 = 15 урсгалын утгаар 0.
Дараагийн алхам нь 5-р урсгалтай замыг өгдөг (Зураг 4.26).
Цагаан будаа. 4.26.
Дараагийн алхам нь зурагт үзүүлсэн үр дүнг өгнө. 4.27.
Цагаан будаа. 4.27.
Цаашид тэмдэглэгээ хийх боломжгүй. Эндээс бид хамгийн их урсгалын матрицыг авдаг (Зураг 4.28).
Цагаан будаа. 4.28.
Сүлжээний хамгийн их урсгалыг олох алгоритмыг хэрэглэсний үр дүнд үр дүнг Зураг дээр үзүүлэв. 4.29. Графикийн нуман дээр харуулсан хаалтанд байгаа хос тоонууд нь нумын хамгийн их дамжуулах чадвар ба сүлжээнд нийлүүлэх санал болгож буй хэмжээг харуулна.
Гамильтоны мөчлөг
График нь матриц хэлбэрээр өгөгдсөн бөгөөд нүднүүд нь цэгүүдийн хоорондох хөдөлгөөний зардлыг агуулдаг. Өөртөө утгагүй замыг оруулахгүйн тулд ∞ тэмдгийг үндсэн диагональ дээр байрлуулсан.
Учир нь үүссэн матрицад тэг элементгүй багана байгаа бол бид түүний хамгийн бага элементийг олж, энэ баганын бүх элементүүдээс хасна.
| А | Б | C | Д | |
| А | ∞ | |||
| Б | ∞ | |||
| C | ∞ | |||
| Д | ∞ |
Бүх хассан элементүүдийг нийлбэрлээд мөчлөгийн доод хязгаарыг гарга -д = 2+2+3+2+1=10
1.2. Матрицын бүх тэг элементүүдийг тооцоолъё.
Хүснэгтэнд тэгийн тооцоог үзүүлэх нь тохиромжтой.
| А | Б | C | Д | |
| А | ||||
| Б | ||||
| C | ||||
| Д |
θ=max γ=γ A C =2
1.3. Бид замуудын багцыг хоёр дэд бүлэгт хуваадаг: Q АСнь нум (AC) ба Q агуулсан замууд юм АС– нум (AC) агуулаагүй замууд. Хоёрдахь дэд олонлогийн хувьд доод хязгаар нь: in / \u003d in + θ \u003d 10 + 2 \u003d 12.
Эхний дэд олонлогийн хязгаарыг тооцоолохын тулд бид матриц руу бага зэрэг дарааллаар орж, A мөр ба С баганыг устгана. Шинэ матрицад буцах замыг (CA) хасахын тулд бид харгалзах нүдэнд ∞ тэмдгийг тавина.
Үүссэн 2+0=2 матрицын заагийг тооцоол
ба гогцооны доод хязгаарт нэмнэ. Энэ хэмжээ дотор // =10+2=12 бөгөөд эхний дэд олонлогийн хил хязгаар болно.
1.4. Бүх унжсан оройнуудын хил хязгаарыг харьцуулж, хамгийн бага зааг бүхий оройг сонго. Хэрэв эдгээр оройн хоёр цэг байгаа бол тэдгээрийн аль нэгийг нь сонгоно уу. Энэ бол дээд Q АС, доод хязгаар нь =12.
Бид хамгийн их тооцооллыг сонгодог θ=max γ=γ BD =3
in / \u003d 12 + 3 \u003d 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, B) - (T, B) хамгийн бага дамжуулах чадвартай хэсэг =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). Оргил руугаа явцгаая би. Бид эх сурвалжид хүрэх хүртэл энэ үйлдлийг давтана s .Урсгалын өөрчлөлт зогсч, бүх тэмдэг арилж, 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, B)=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 Хамгийн бага зүсэлт: М→Т-М→Р-М→руу |
ДААЛГАВАР. Сүлжээний хамгийн өндөр урсгалыг ол
АЛГОРИТМ
Оройг тэмдэглэ s= x 0. Бусад бүх зүйл - x i.
1-р шат.
1. Бүх нумууд нь ханаагүй ямар ч замыг сонго.
2. Энэ замын дагуух урсгалын утгыг ханасан нум байхгүй болтол нэгээр нэмэгдүүлнэ.
Бид бүрэн урсгалыг барих хүртэл урсгалыг нэмэгдүүлэх үйл явцыг үргэлжлүүлнэ, i.e. ямар ч зам дор хаяж нэг ханасан нум агуулна.
2-р шат.
2. Хэрвээ x i нь аль хэдийн шошготой орой бол бид (+i) x i-ээс ханаагүй нумууд орох бүх шошгогүй оройг, мөн тэг биш урсгалтай нумууд гарах бүх тэмдэглэгээгүй оройг (–i) индексээр тэмдэглэнэ. x i хүртэл.
3. Хэрэв энэ процессын үр дүнд оройг тэмдэглэсэн бол т, дараа нь хооронд сболон тзам байгаа бөгөөд түүний бүх оройг өмнөх оройнуудын тоогоор тэмдэглэсэн байдаг. Энэ замын бүх нуман дахь урсгалыг хөдөлж байх үед нэгээр нэмэгдүүлнэ сруу тнумын чиглэл нь хөдөлгөөний чиглэлтэй ижил байх ба хэрэв нум нь эсрэг чиглэлтэй бол нэгээр буурна. Бид 1-р цэг рүү шилждэг.
4. Дээд талд байх үед тпроцессыг дуусгавар болсон гэж тэмдэглэх боломжгүй бөгөөд үр дүнд нь гарсан урсгал нь сүлжээний хамгийн том урсгал юм.
ЖИЧ. Та эхний шатыг дуусгахгүйгээр 2-р шат руу явж болно (жишээ 3.16-г үзнэ үү).
ЖИШЭЭ 3.15.
9
ШИЙДЭЛ:
Өгөгдсөн тээврийн сүлжээнд бүрэн урсгал олддог. Ханасан нумуудыг тодруулсан
Энэ сүлжээнд та мөн төгсгөлийн оройг шошголох боломжтой бөгөөд шошгоны үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид төгсгөлийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 10-тай тэнцүү байна.
ЖИШЭЭ 3.16.
8 2 1
Өгөгдсөн тээврийн сүлжээнд бүрэн бус урсгал илэрсэн
Сүлжээг тэмдэглэж, алгоритмын дагуу урсгалыг нэмэгдүүлье. Авах
Энэ сүлжээнд та мөн төгсгөлийн оройг шошголох боломжтой бөгөөд шошгоны үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид төгсгөлийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 6-тай тэнцүү байна.
IV хэсэг. Динамик програмчлал.
Динамик програмчлалыг олон үе шаттай оновчтой шийдлүүдийг олоход ашигладаг. Тухайлбал, тоног төхөөрөмжийг солих урт хугацааны төлөвлөлт; салбарын үйл ажиллагаа хэдэн жилийн . Энэ нь оновчтой байх зарчмыг ашигладаг бөгөөд үүний дагуу аливаа шинэ хэсэгчилсэн шийдэл нь хүрсэн төлөв байдлын хувьд оновчтой байх ёстой.
Нэг асуудлыг олон удаа шийдсэн нь дээр энгийн даалгаварнэгээс илүү төвөгтэй.
АСУУДАЛ 1. Хоёр цэгийн хоорондох хамгийн ашигтай аргын тухай.
А ба В хоёр цэгийг холбосон замыг барих шаардлагатай бөгөөд хоёр дахь нь эхнийхээс зүүн хойд зүгт байрладаг. Энгийн байх үүднээс зам тавих нь хэд хэдэн шат дамжлагаас бүрдэх бөгөөд алхам бүртээ хойд эсвэл зүүн тийшээ хөдөлж болно гэж бодъё. Дараа нь аливаа зам нь шат дамжлага юм эвдэрсэн шугам, сегментүүд нь координатын тэнхлэгүүдийн аль нэгэнд параллель байна. Эдгээр сегмент бүрийн барилгын өртөг нь мэдэгдэж байна.
ЖИШЭЭ 4.1. А-аас В хүртэлх хамгийн богино замыг ол.
Сүүлийн алхам бол T.V-д хүрэх явдал юм. Өмнө нь сүүлчийн алхамБид ТВ-д нэг алхамаар хүрч болох цэгүүдэд байж болно. Ийм хоёр цэг байдаг (систем нь хоёр муж улсын аль нэгэнд байж болно). Тэдний хувьд В цэгт хүрэх цорын ганц арга зам байдаг: нэг нь зүүн тийш; нөгөөгийн хувьд - хойд зүгт. Тохиолдол бүрт 4 ба 3-ын зардлыг бичье.
4
Одоо бид эцсийн өмнөх алхамыг оновчтой болгож байна. Өмнөх алхамын дараа бид С 1 , С 2 , С 3 гэсэн гурван цэгийн аль нэгэнд хүрч болно.
С 1 цэгийн хувьд зөвхөн нэг удирдлага байдаг (түүнийг сумаар тэмдэглэнэ) - зүүн тийш шилжих бол зардал нь 2(энэ алхамд)+4(дараагийн шатанд)=6 болно. Үүний нэгэн адил t.C 3-ийн хувьд зардал нь 2+3=5 болно. С 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 \u003d 0; x 3 =1; x2=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; x3=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. ЗУРАГЧИЛСАН ЗАГВАРЧИЛАЛ
Форд-Фулкерсоны алгоритмыг ашиглан тээврийн сүлжээн дэх хамгийн их урсгалыг олох асуудлыг шийдэж, сүлжээний S хэсгийг байгуул.
Анхны өгөгдөл:
Өгөгдсөн сүлжээ S(X,U)
- сүлжээний эх үүсвэр; - сүлжээний угаалтуур, энд ∈X; ∈X.
Нумын хүчин чадлын утгыг нумын чиглэлийн дагуу өгсөн болно: i индексээс j индекс хүртэл.
r=39; r=44; r=33; r=53; r = 10;
r=18; r=95; r=16; r = 23; r=61;
r=81; r=71; r=25; r=15; r=20
1. Сүлжээнд тэг урсгалыг тохируулах (бүх нуман дээр урсгалын утга 0 байна). Тэг урсгал нь сүлжээн дэх анхны зөвшөөрөгдсөн урсгал юм. Нуман тус бүрийн урсгалын утгыг нумын дамжуулалтын хаалтны гадна талд зааж өгнө.). "0"-тэй тэнцэх урсгалын утгыг заагаагүй байна.
2. Сүлжээнд x0 оройноос x7 орой руу чиглэсэн замыг (дураар) сонгоно уу:
X0-X1-X4-X6-X7
3. Хай 
мөн энэ хэмжээгээр урсгалыг нэмэгдүүлнэ. X1-X4 ирмэгийг авч үзсэн гэж тэмдэглэсэн. 
4. Бид өөр нэг арга замыг сонгодог, жишээлбэл: X0-X2-X5-X7, бид олдог 
мөн энэ хэмжээгээр урсгалыг нэмэгдүүлнэ. Бид X0-X2 ирмэгийг авч үзсэний дагуу тэмдэглэнэ. 
5. Бид өөр нэг аргыг сонгоно, жишээлбэл: X0-X3-X2-X5-X7, урсгалыг олж, энэ утгаараа нэмэгдүүлнэ. Бид X3-X2 ирмэгийг авч үзсэний дагуу тэмдэглэнэ. 
6. X0-ээс X7 хүртэлх зам байхгүй, бид урсгалын өсөлтийг нэгтгэн дүгнэж байна: 25+10+20=55.
Дүгнэлт: хамгийн их урсгал нь 55 байна.
2) S сүлжээний хэсгийг байгуул.
Оройг тэмдэглэх журам.
Анхны төлөв: бүх оройнууд шошгогүй байна.
X0 оройг тэмдэглэсэн байна. Нуман ханаагүй бүх оройг тэмдэглэгээ (улаан тойрог) өгдөг. 
Бид хамгийн бага зүсэлтийн нумуудыг тодорхойлдог: эдгээр нь эхлэл нь тэмдэглэгдсэн орой дээр байрлах нумууд бөгөөд төгсгөлүүд нь тэмдэглэгээгүй орой дээр байрладаг.
Эдгээр нь нумууд юм:
Тиймээс энэ сүлжээний хамгийн бага зүсэлт 
Хамгийн их урсгалын тооцоо
