Modelo ng network (pananaliksik ng operasyon)

From Systems analysis Wiki
Jump to navigation Jump to search

Mga Modelo ng Network (sa pananaliksik ng operasyon; Ingles: Network models) — ito ay isang klase ng mga matematikal na modelo na naglalarawan ng isang problema sa anyo ng isang graph (network), kung saan ang mga vertex (node) ay kumakatawan sa mga bagay o estado, at ang mga gilid (arko) — ang mga koneksyon o proseso sa pagitan nila[1]. Sa konteksto ng optimisasyon, ang network ay kadalasang nauunawaan bilang isang directed graph, na sa operational analysis ay direktang tinatawag na "network"; ang mga vertex ng naturang network ay tinatawag na mga node, at ang mga gilid — mga arko[2].

Ang mga modelo ng network ay isang makapangyarihang kasangkapan para sa pagsusuri at optimisasyon ng mga kumplikadong sistema sa mga larangang tulad ng logistika, telekomunikasyon, pamamahala ng proyekto, at pananalapi. Ang kanilang lakas ay nakasalalay sa mataas na antas ng abstraksiyon: ang isang node ay maaaring kumatawan sa isang lungsod, isang computer router, o isang yugto ng proyekto, at ang isang arko — isang daan, isang channel ng komunikasyon, o isang teknolohikal na operasyon.

Kahulugan at Terminolohiya

Ang pundasyon ng mga modelo ng network ay ang teorya ng graph. Ang mga pangunahing konsepto ay:

  • Network ng daloy (Ingles: flow network): isang directed graph kung saan ang bawat gilid ay may kapasidad (capacity) at daloy (flow). Sa graph, dalawang espesyal na vertex ang natutukoy: ang pinagmulan (source), kung saan nagmumula ang daloy, at ang patutunguhan (sink), kung saan ito pumapasok[1].
  • Batas ng pangangalaga ng daloy: Para sa anumang vertex na hindi pinagmulan o patutunguhan, ang kabuuang papasok na daloy ay dapat na katumbas ng kabuuang papalabas na daloy. Ang kondisyong ito ay isang discrete na katumbas ng mga pisikal na batas ng pangangalaga[3].
  • Pagpaplano ng network: Isang modelo na nagpapakita ng isang proyekto bilang isang hanay ng magkakaugnay na operasyon (mga arko) at mga kaganapan (mga node). Ang mga naturang network ay directed acyclic graph, na sumasalamin sa pagkakasunud-sunod ng pagsasagawa ng mga gawain[4].

Mga Pangunahing Katangian at Theorem

Ang mga modelo ng network ay nagtataglay ng ilang espesyal na katangian na nagpapahintulot sa paggamit ng mga napaka-episyenteng algorithm para sa kanilang solusyon.

  • Integridad ng mga solusyon: Maraming problema sa network optimization (halimbawa, ang problema ng maximum flow o pinakamaikling landas) ay nagtataglay ng katangian ng kumpletong unimodularity ng matrix ng mga hadlang. Dahil dito, kung ang mga parameter ng problema (mga kapasidad, haba) ay mga integer, kung gayon ang optimal na solusyon na natuklasan sa pamamagitan ng mga pamamaraan ng linear programming ay magiging integer din nang hindi nangangailangan ng mga karagdagang hadlang[5][6].
  • Theorem ng maximum flow at minimum cut: Isang sentral na resulta ng teorya ng daloy. Itinatag nito na ang maximum na halaga ng daloy mula sa pinagmulan hanggang sa patutunguhan ay katumbas ng minimum na kapasidad sa lahat ng mga hiwa na naghihiwalay sa pinagmulan at patutunguhan. Itinatag ng theorem na ito ang pamantayan ng optimality para sa daloy at siyang pundasyon ng maraming algorithm[6][7].
  • Prinsipyo ng optimality para sa pinakamaikling landas: Kung ang landas mula sa punto A hanggang sa punto C ay ang pinakamaikli, kung gayon ang anumang bahagi nito (halimbawa, mula sa intermediate na punto B hanggang sa C) ay pinakamaikling landas din sa pagitan ng mga kaukulang vertex. Ang katangiang ito, na siyang pundasyon ng dynamic programming, ay nagpapatunay ng kawastuhan ng mga algorithm tulad ng algorithm ni Dijkstra[8].
  • Mga katangian ng minimum spanning tree (MST):
  • Katangian ng hiwa: Para sa anumang hiwa ng graph, ang gilid na may pinakamababang timbang na tumatawid sa hiwa ay kabilang sa hindi bababa sa isang MST.
  • Katangian ng siklo: Sa anumang siklo ng graph, ang gilid na may pinakamataas na timbang ay hindi kabilang sa kahit isang MST.

Sa mga katangiang ito nakabatay ang kawastuhan ng mga "greedy" na algorithm nina Prim at Kruskal[9].

Mga Pangunahing Problema sa Network Optimization

  • Problema ng pinakamaikling landas: Hanapin ang landas na may pinakamababang kabuuang haba (timbang) sa pagitan ng dalawang itinakdang node. Nilulutas gamit ang algorithm ni Dijkstra (para sa mga di-negatibong timbang) o ang algorithm ni Bellman-Ford (para sa mga arbitrary na timbang)[8].
  • Problema ng maximum flow: Tukuyin ang pinakamataas na posibleng daloy mula sa pinagmulan hanggang sa patutunguhan sa mga itinakdang kapasidad ng mga arko. Ang klasikong paraan ng solusyon — ang algorithm ni Ford–Fulkerson[6].
  • Problema ng minimum spanning tree: Hanapin ang subgraph na nagkokonekta sa lahat ng vertex ng network at may pinakamababang kabuuang gastos ng mga gilid.
  • Paraan ng kritikal na landas (CPM): Sa mga modelo ng network ng pagpaplano, tukuyin ang pinakamahabang pagkakasunud-sunod ng mga gawain, na nagtatakda ng pinakamababang posibleng oras ng pagkumpleto ng buong proyekto. Ang mga gawain sa landas na ito ay may zero na time reserve[10].

Mga Halimbawa

  • Pinakamaikling landas: Paghahanap ng pinakamainam na ruta ng isang navigation system sa pagitan ng dalawang punto sa mapa ng lungsod, kung saan ang mga lungsod ay mga node at ang mga daan ay mga arko na may mga timbang na katumbas ng haba o oras ng biyahe.
  • Maximum flow: Pagtukoy ng maximum na kapasidad ng isang network ng mga pipeline, kung saan ang mga pumping station ay mga node at ang mga tubo ay mga arko na may limitadong kapasidad.
  • Minimum spanning tree: Pagdidisenyo ng isang network ng komunikasyon (halimbawa, paglalagay ng fiber optic cable) para ikonekta ang ilang lungsod na may pinakamababang kabuuang haba ng cable.
  • Kritikal na landas: Sa isang proyekto ng pagtatayo ng bahay, kung saan ang mga gawain (pagtatayo ng pundasyon, pagtatayo ng mga pader, pag-install ng bubong) ay may itinakdang tagal at mga teknolohikal na dependensya, tinutukoy ng kritikal na landas ang pinakamababang takdang panahon ng pagkumpleto ng konstruksyon. Ang anumang pagkaantala sa isang gawain sa landas na ito ay magreresulta sa pagkaantala ng buong proyekto[10].

Tingnan din

  • Pananaliksik ng operasyon
  • Teorya ng graph
  • Problema sa transportasyon
  • Paraan ng kritikal na landas
  • PERT

Mga Tala

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Modelo_ng_network_(pananaliksik_ng_operasyon)&oldid=4594"