Model Jaringan (Riset Operasi)

From Systems analysis Wiki
Jump to navigation Jump to search

Model Jaringan (dalam riset operasi; Ingg. Network models) — adalah kelas model matematika yang merepresentasikan masalah dalam bentuk graf (jaringan), di mana simpul (node) melambangkan objek atau keadaan, sedangkan sisi (busur) melambangkan hubungan atau proses di antara mereka[1]. Dalam konteks optimasi, jaringan sering dipahami sebagai graf berarah yang dalam analisis operasional secara langsung disebut "jaringan"; simpul-simpul jaringan tersebut dinamakan node, sedangkan sisi-sisinya dinamakan busur[2].

Model jaringan merupakan alat yang ampuh untuk menganalisis dan mengoptimalkan sistem-sistem kompleks di bidang-bidang seperti logistik, telekomunikasi, manajemen proyek, dan keuangan. Kekuatannya terletak pada tingkat abstraksi yang tinggi: sebuah node dapat mewakili kota, router komputer, atau tahap proyek, sedangkan sebuah busur dapat mewakili jalan, saluran komunikasi, atau operasi teknologi.

Definisi dan Terminologi

Dasar bagi model jaringan adalah teori graf. Konsep-konsep kuncinya adalah:

  • Jaringan aliran (Ingg. flow network): graf berarah di mana setiap sisi memiliki kapasitas (capacity) dan aliran (flow). Dalam graf ini terdapat dua simpul khusus: sumber (source), tempat aliran berasal, dan muara (sink), tempat aliran masuk[1].
  • Hukum kekekalan aliran: Untuk setiap simpul yang bukan merupakan sumber atau muara, total aliran masuk harus sama dengan total aliran keluar. Kondisi ini merupakan analog diskret dari hukum-hukum kekekalan fisika[3].
  • Perencanaan jaringan: Model yang merepresentasikan proyek sebagai sekumpulan operasi (busur) dan kejadian (node) yang saling berkaitan. Jaringan semacam ini merupakan graf berarah tanpa siklus, yang mencerminkan urutan pelaksanaan pekerjaan[4].

Sifat dan Teorema Utama

Model jaringan memiliki sejumlah sifat khusus yang memungkinkan penerapan algoritma-algoritma yang sangat efisien untuk penyelesaiannya.

  • Keseluruhbilangan solusi: Banyak masalah optimasi jaringan (misalnya, masalah aliran maksimum atau jalur terpendek) memiliki sifat unimodularitas penuh pada matriks kendala. Berkat sifat ini, jika parameter masalah (kapasitas, panjang) berupa bilangan bulat, maka solusi optimal yang ditemukan dengan metode pemrograman linier juga akan berupa bilangan bulat tanpa perlu menambahkan kendala tambahan[5][6].
  • Teorema aliran maksimum dan potongan minimum: Hasil sentral dalam teori aliran. Menyatakan bahwa nilai maksimum aliran dari sumber ke muara sama dengan kapasitas minimum di antara semua potongan yang memisahkan sumber dan muara. Teorema ini menetapkan kriteria optimalitas untuk aliran dan menjadi dasar bagi banyak algoritma[6][7].
  • Prinsip optimalitas untuk jalur terpendek: Jika jalur dari titik A ke titik C merupakan jalur terpendek, maka setiap bagian dari jalur tersebut (misalnya, dari titik antara B ke C) juga merupakan jalur terpendek antara simpul-simpul yang bersangkutan. Sifat ini, yang menjadi dasar pemrograman dinamis, memastikan kebenaran algoritma-algoritma seperti algoritma Dijkstra[8].
  • Sifat-sifat pohon rentang minimum (PRM):
  • Sifat potongan: Untuk setiap potongan graf, sisi dengan bobot minimum yang melintasi potongan tersebut termasuk dalam setidaknya satu PRM.
  • Sifat siklus: Dalam setiap siklus graf, sisi dengan bobot maksimum tidak termasuk dalam satu pun PRM.

Sifat-sifat ini menjadi dasar kebenaran algoritma "serakah" Prim dan Kruskal[9].

Masalah Utama Optimasi Jaringan

  • Masalah jalur terpendek: Menemukan jalur dengan total panjang (bobot) minimum antara dua node yang ditentukan. Diselesaikan dengan algoritma Dijkstra (untuk bobot non-negatif) atau algoritma Bellman-Ford (untuk bobot sembarang)[8].
  • Masalah aliran maksimum: Menentukan aliran maksimum yang mungkin dari sumber ke muara dengan kapasitas busur yang diberikan. Metode penyelesaian klasik adalah algoritma Ford–Fulkerson[6].
  • Masalah pohon rentang minimum: Menemukan subgraf yang menghubungkan semua simpul jaringan dan memiliki total biaya sisi yang minimum.
  • Metode jalur kritis (CPM): Dalam model jaringan perencanaan, menentukan urutan pekerjaan terpanjang yang menetapkan waktu minimum penyelesaian seluruh proyek. Pekerjaan di jalur ini memiliki cadangan waktu nol[10].

Contoh-Contoh

  • Jalur terpendek: Pencarian rute optimal oleh sistem navigasi antara dua titik di peta kota, di mana kota-kota adalah node dan jalan-jalan adalah busur dengan bobot yang sama dengan panjang atau waktu perjalanan.
  • Aliran maksimum: Penentuan kapasitas maksimum jaringan pipa, di mana stasiun pompa adalah node dan pipa adalah busur dengan kapasitas terbatas.
  • Pohon rentang minimum: Perancangan jaringan komunikasi (misalnya, pemasangan kabel serat optik) untuk menghubungkan beberapa kota dengan total panjang kabel minimum.
  • Jalur kritis: Dalam proyek pembangunan rumah, di mana pekerjaan-pekerjaan (peletakan fondasi, pembangunan dinding, pemasangan atap) memiliki durasi yang ditentukan dan ketergantungan teknologi, jalur kritis menentukan jangka waktu minimum penyelesaian pembangunan. Setiap keterlambatan pekerjaan di jalur ini akan menyebabkan keterlambatan seluruh proyek[10].

Lihat Juga

  • Riset operasi
  • Teori graf
  • Masalah transportasi
  • Metode jalur kritis
  • PERT

Catatan

  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=Model_Jaringan_(Riset_Operasi)&oldid=4484"