Program Studi Manajemen • FEB UNDIP
Manajemen Sains
Pertemuan 5 — Model Transportasi & Penugasan Dari gudang ke pelanggan dengan biaya minimum — dua model klasik Operations Research (Riset Operasi) yang dipakai setiap hari di Bulog, JNE, hingga BPK RI.
RPS MINGGU 5 • SUB-CPMK4 • DURASI 2 × 50 MENIT
Selamat datang di Pertemuan 5, sebuah pertemuan yang akan memperkenalkan Anda pada dua model paling banyak dipakai dalam dunia logistik dan manajemen sumber daya manusia: model transportasi dan model penugasan. Bayangkan Anda menjadi manajer logistik Bulog yang harus mendistribusikan beras dari tiga gudang regional ke empat kota tujuan — pertanyaannya bukan "apakah bisa dikirim", melainkan "bagaimana cara mengirim dengan total biaya paling rendah". Itulah esensi model transportasi. Di bagian kedua, kita akan belajar model penugasan: bayangkan BPK RI (Badan Pemeriksa Keuangan) perlu menetapkan empat tim auditor ke empat satuan kerja — siapa dikirim ke mana agar total waktu penyelesaian minimum? Dua model ini adalah aplikasi langsung dari LP (Linear Programming — pemrograman linear) yang sudah Anda pelajari, dengan struktur khusus yang memungkinkan penyelesaian lebih efisien. Siapkan diri Anda untuk banyak berhitung — pertemuan ini sangat hands-on. Tujuan Pembelajaran Hari Ini Setelah pertemuan ini, Anda mampu (Sub-CPMK4):
CAPAIAN 1
1
Menyusun tabel transportasi (supply, demand, cost matrix) & membedakan balanced vs unbalanced
CAPAIAN 2
2
Menerapkan NWC dan VAM untuk solusi awal, lalu mengoptimalkan dengan MODI Method
CAPAIAN 3
3
Menerapkan Hungarian Method langkah demi langkah untuk masalah penugasan 4×4
CAPAIAN 4
4
Mengenali kasus khusus: masalah maksimasi dan matriks tidak seimbang (unbalanced)
Hari ini kita memiliki empat tujuan konkret. Pertama, Anda akan mampu membaca masalah logistik nyata dan mengubahnya menjadi tabel transportasi yang siap dihitung. Kedua, Anda akan menguasai dua teknik mencari solusi awal — NWC yang cepat dan VAM yang lebih akurat — lalu memperbaikinya ke optimal menggunakan MODI Method. Ketiga, Anda akan menerapkan Hungarian Method secara lengkap, langkah demi langkah, untuk masalah penugasan 4 karyawan dan 4 tugas. Keempat, Anda akan tahu cara menangani dua kasus khusus yang sering muncul di soal ujian: masalah maksimasi dan matriks tidak seimbang. Jadikan keempat poin ini sebagai daftar periksa Anda di akhir kelas. Distribusi Efisien = Keunggulan Bisnis Seberapa besar dampak keuangan dari keputusan distribusi?
3 gudang regional, 4 provinsi tujuan Biaya angkut Rp 50–200 per kg Total distribusi ~1.200 ton/hari Selisih metode buruk vs optimal: Rp ratusan juta per hari 4 tim auditor, 4 satker (satuan kerja) berbeda Penugasan salah $\to$ audit mundur berminggu-minggu Risiko keterlambatan LKPP (Laporan Keuangan Pemerintah Pusat) Berdampak pada pengesahan APBN tahun berikutnya Model transportasi & penugasan = LP dengan struktur khusus yang dapat diselesaikan tanpa solver komputer .
Sebelum masuk ke teknik, saya ingin Anda memahami mengapa model ini penting secara bisnis dan kebijakan publik. Bulog mendistribusikan jutaan ton beras setiap tahun — keputusan rute distribusi yang buruk dapat memboroskan miliaran rupiah anggaran subsidi. Di sektor privat, perusahaan seperti Indofood, Unilever, dan Sido Muncul memiliki jaringan distribusi ke ratusan gudang nasional; optimasi rute distribusi bisa menghemat 10–20% biaya logistik, yang langsung mempengaruhi margin keuntungan. Di sektor publik, BPK setiap tahun harus menugaskan ribuan auditor ke ribuan satker — penugasan yang tidak efisien memperlambat penyelesaian LKPP yang harus selesai sebelum deadline konstitusional. Model yang kita pelajari hari ini adalah alat yang digunakan para manajer tersebut, disederhanakan ke bentuk yang bisa Anda kerjakan dengan kertas dan pensil. Blok 1 dari 4
Struktur Masalah Transportasi
Supply · Demand · Cost Matrix · Balanced vs Unbalanced · NWC · VAM
Kita mulai dari fondasi. Sebelum bisa menyelesaikan masalah transportasi, Anda harus memahami komponennya: apa itu sumber (supply — pasokan yang tersedia), apa itu tujuan (demand — kebutuhan yang harus dipenuhi), dan bagaimana matriks biaya dibaca. Jangan lewatkan bagian ini — mahasiswa yang langsung loncat ke teknik tanpa paham struktur masalah sering membuat kesalahan pada soal ujian. Blok 1 ini memberi Anda cetak biru yang akan dipakai ulang untuk semua contoh berikutnya. Ingat, setiap pertemuan kita selalu membangun di atas fondasi sebelumnya. Komponen Masalah Transportasi Masalah transportasi memiliki enam komponen utama:
Komponen Simbol Arti Sumber (supply ) i = 1, 2, …, m Pabrik/gudang/produsen yang memiliki stok Tujuan (demand ) j = 1, 2, …, n Gudang/toko/konsumen yang membutuhkan pasokan Biaya pengiriman $c_{ij}$ Biaya per unit mengirim dari sumber i ke tujuan j Kapasitas sumber $s_{i}$ Total unit yang bisa dikirim dari sumber i Kebutuhan tujuan $d_{j}$ Total unit yang dibutuhkan di tujuan j Variabel keputusan $x_{ij}$ Jumlah unit yang dikirim dari i ke j (nilai yang dicari )
Minimumkan $Z = \sum\sum c_{ij} \cdot x_{ij}$
Constraint: $\sum_{j} x_{ij} \leq s_{i}$ (tiap sumber) | $\sum_{i} x_{ij} \geq d_{j}$ (tiap tujuan) | $x_{ij} \geq 0$
Masalah transportasi pada dasarnya adalah LP (Linear Programming) khusus. Anda punya m sumber dan n tujuan — dalam contoh kita nanti, m=3 pabrik dan n=4 gudang. Setiap pasangan (i,j) punya biaya c_ij per unit, dan kita mencari alokasi x_ij yang meminimumkan total biaya sambil memenuhi semua kapasitas sumber dan kebutuhan tujuan. Perhatikan bahwa constraint supply bersifat "kurang dari atau sama dengan" — sumber tidak harus habis semua — sedangkan constraint demand bersifat "lebih dari atau sama dengan" — tujuan harus dipenuhi minimal. Kalau semua supply habis terpakai DAN semua demand terpenuhi persis, masalah disebut balanced — dan inilah kondisi paling mudah diselesaikan. Balanced vs Unbalanced — Syarat & Solusi Dummy Langkah pertama sebelum menghitung: cek apakah masalah seimbang (balanced ).
Kondisi Syarat Tindakan Balanced $\sum s_{i} = \sum d_{j}$ Langsung selesaikan Excess supply $\sum s_{i}$ > $\sum d_{j}$ Tambah dummy destination dengan demand = selisih; biaya dummy = 0 Excess demand $\sum s_{i}$ < $\sum d_{j}$ Tambah dummy source dengan supply = selisih; biaya dummy = 0
Dummy = baris/kolom fiktif biaya-nol yang ditambahkan agar masalah menjadi balanced. Unit yang "dialokasikan ke dummy" berarti tidak jadi dikirim (idle capacity atau unmet demand).
Sebelum menjalankan satu pun metode penyelesaian, selalu cek dulu apakah masalah Anda balanced atau tidak. Cukup jumlahkan semua supply dan semua demand — kalau sama, Anda beruntung, langsung lanjut ke metode. Kalau supply lebih besar dari demand, artinya ada barang yang tidak akan terkirim — tambahkan satu kolom tujuan fiktif (dummy destination) dengan kebutuhan sebesar selisihnya dan biaya nol. Logikanya: barang yang "dikirim ke dummy" berarti disimpan di gudang, tidak kemana-mana. Sebaliknya kalau demand lebih besar dari supply, tambahkan baris sumber fiktif dengan biaya nol — ini merepresentasikan kebutuhan yang tidak terpenuhi. Dalam contoh pertemuan ini, kita sengaja memilih angka balanced agar bisa fokus ke teknik utamanya. Alur Penyelesaian Masalah Transportasi Tiga tahap berurutan — jangan dilewati:
TAHAP 1 Formulasi Buat tabel supply/demand/cost Cek balanced; dummy jika perlu TAHAP 2 Solusi Awal NWC (cepat) atau VAM (lebih baik) Hasilkan m+n−1 sel terisi TAHAP 3 Optimasi (MODI) Hitung u, v, w; cek w≥0 Iterasi loop jika ada w<0 Aturan wajib: tepat (m+n−1) sel terisi . Lebih $\to$ error; kurang $\to$ degenerasi (solusi degenerasi — jumlah sel terisi kurang dari m+n−1, MODI tidak bisa berjalan).
Penting untuk Anda pahami bahwa penyelesaian transportasi tidak langsung ke jawaban akhir — ada tiga tahap berurutan yang tidak boleh dilewati. Tahap pertama adalah formulasi: mengubah narasi masalah ke dalam tabel dengan baris=sumber, kolom=tujuan, sel=biaya. Tahap kedua adalah mencari solusi awal — ini bukan jawaban optimal, hanya titik awal yang feasible (layak — memenuhi semua constraint). Tahap ketiga adalah optimasi menggunakan MODI Method untuk memastikan kita benar-benar di titik biaya minimum. Satu aturan yang sering terlupakan: solusi harus memiliki tepat m+n-1 sel yang terisi. Untuk kasus kita dengan 3 sumber dan 4 tujuan: m+n-1 = 3+4-1 = 6 sel. North-West Corner Method (NWC) — Cara Tercepat NWC: isi sel mulai pojok kiri-atas, gerak ke kanan atau ke bawah.
1 Mulai di sel kiri-atas (north-west corner — pojok barat-laut)2 Alokasikan: $x_{ij} =$ min(supply$_{i}$, demand$_{j})$3 Kurangi supply baris dan demand kolom4 Supply habis $\to$ turun ke baris berikutnya; demand habis $\to$ geser kanan. Ulangi.Tabel 3×4 — arah pengisian NWC START FINISH F₁ F₂ F₃ W₁ W₂ W₃ W₄ NWC mengabaikan biaya sepenuhnya — hanya memperhatikan posisi . Karenanya sering menghasilkan solusi awal yang mahal.
NWC adalah metode paling sederhana untuk mendapatkan solusi awal. Logikanya sangat intuitif: seperti membaca tabel dari pojok kiri-atas, selalu isi sebanyak yang bisa Anda isi, lalu geser ke kanan atau ke bawah. Keunggulannya: cepat dan tidak pernah salah secara prosedur. Kelemahan besarnya: NWC sama sekali tidak memperhatikan biaya — dia mengisi sel berurutan tanpa peduli apakah c_ij itu kecil atau besar. Karena itu, solusi NWC biasanya jauh dari optimal dan butuh banyak iterasi MODI untuk diperbaiki. Dalam contoh kita, NWC akan menghasilkan biaya 3.050, sementara optimal adalah 2.100 — selisih 31% yang signifikan. Hitung dari Nol 1 — NWC: 3 Pabrik × 4 Gudang Data: Supply F₁=300, F₂=400, F₃=500 (total 1.200) | Demand W₁=250, W₂=350, W₃=400, W₄=200 (total $1.200) \to$ Balanced ✓
Langkah Perhitungan Alokasi $1 - F_{1}\to W_{1}$ min(300, 250) = 250; F₁ sisa 50; W₁ habis $\to$ geser kanan 250 $2 - F_{1}\to W_{2}$ min(50, 350) = 50; F₁ habis $\to$ turun ke F₂; W₂ sisa 300 50 $3 - F_{2}\to W_{2}$ min(400, 300) = 300; F₂ sisa 100; W₂ habis $\to$ geser kanan 300 $4 - F_{2}\to W_{3}$ min(100, 400) = 100; F₂ habis $\to$ turun ke F₃; W₃ sisa 300 100 $5 - F_{3}\to W_{3}$ min(500, 300) = 300; F₃ sisa 200; W₃ habis $\to$ geser kanan 300 $6 - F_{3}\to W_{4}$ min(200, 200) = 200; selesai 200
Total Biaya NWC: 250×2 + 50×3 + 300×2 + 100×5 + 300×3 + 200×2Rp 3.050 | 6 sel = m+n−1 = 3+4−1 = 6 ✓ | Solusi awal — belum optimal
Mari kita kerjakan NWC langkah demi langkah dengan data konkret yang akan kita pakai sepanjang pertemuan ini. Pada langkah 1, kita di pojok kiri-atas F₁ ke W₁: supply F₁=300 dan demand W₁=250, ambil minimum=250; supply F₁ tersisa 50, demand W₁ habis jadi kita geser ke kanan ke W₂. Langkah 2: F₁ ke W₂; supply F₁=50 dan demand W₂=350, ambil 50; F₁ habis jadi turun ke F₂. Perhatikan bahwa kita tidak sekali pun melihat angka biaya — NWC murni prosedural. Setelah enam langkah, kita dapat total biaya Rp 3.050 — tapi ini masih "draft pertama" yang perlu kita periksa. Hitungan ini juga membuktikan bahwa ada tepat 6 sel terisi, artinya tidak degenerasi. Vogel's Approximation Method (VAM) — Ide Penalty VAM: pilih alokasi yang menghindari "hukuman" (penalty ) terbesar jika tidak memilih sel biaya terendah.
Untuk setiap baris & kolom, hitung penalty = biaya terkecil ke-2 − biaya terkecil ke-1 Penalty tinggi = "mahal kalau tidak pilih sel biaya minimum di sini" Pilih baris/kolom dengan penalty tertinggi $\to$ alokasikan ke sel biaya terendah Hapus baris/kolom terpenuhi $\to$ hitung ulang penalty $\to$ ulangi NWC: abaikan biaya, isi urutan posisi VAM: pertimbangkan biaya relatif $\to$ solusi awal jauh lebih baik VAM historis: hanya 5–10% di atas optimal NWC historis: bisa 30–40% di atas optimal VAM seringkali langsung menghasilkan solusi optimal VAM jauh lebih cerdas dari NWC karena mempertimbangkan biaya relatif. Idenya begini: kalau Anda tidak mengalokasikan ke jalur termurah di suatu baris, berapa ekstra biaya yang harus Anda tanggung? Itulah "penalty" — selisih biaya terkecil kedua dikurangi terkecil pertama. Baris atau kolom dengan penalty tertinggi adalah yang paling "mendesak" untuk diprioritaskan. VAM memaksa Anda selalu mengisi kebutuhan paling mendesak terlebih dahulu. Hasilnya jauh lebih baik dari NWC, dan dalam kasus kita, VAM standar bahkan langsung menghasilkan solusi optimal. Hitung dari Nol 2 — VAM: Alokasi Berdasarkan Penalty Data sama dengan HDN-1. Cost matrix: F₁=[2,3,1,4], F₂=[3,2,5,2], F₃=[4,1,3,2]
Iter Penalty Tertinggi Perhitungan Alokasi Nilai 1 Kolom W₃: penalty = 3−1 = 2 min cost $W_{3} = F_{1}\to W_{3} (c=1)$; min(300,400) = 300 $F_{1}\to W_{3}$ 300 2 W₃ sisa 100: penalty W₃ = 2 min cost W₃ (tersisa) $= F_{3}\to W_{3} (c=3)$; min(500,100) = 100 $F_{3}\to W_{3}$ 100 3 Kolom W₂: penalty = 2 min cost $W_{2} = F_{3}\to W_{2} (c=1)$; min(400,350) = 350 $F_{3}\to W_{2}$ 350 4 Baris F₃: penalty = 2 min cost F₃ sisa $= F_{3}\to W_{4} (c=2)$; min(50,200) = 50 $F_{3}\to W_{4}$ 50 5 Baris F₂: penalty = 1 $F_{2}\to W_{4} (c=2)$ < $F_{2}\to W_{1} (c=3)$; min(400,150) = 150 $F_{2}\to W_{4}$ 150 6 Sisa $F_{2}\to W_{1} = 250$ (sisa supply F₂ dan demand W₁) $F_{2}\to W_{1}$ 250
Total Biaya VAM: Rp 2.100
Perbandingan: Rp 3.050 Rp 2.100 $\to$ lebih hemat 31\%Sudah optimal! MODI akan mengkonfirmasi.
Perhatikan betapa VAM jauh lebih hemat dibanding NWC — hasil VAM standar langsung menghasilkan 2.100 versus NWC 3.050, hampir sepertiga lebih murah. Kunci VAM ada pada iterasi 1: dengan penalty terbesar di kolom W₃ (nilai 2), VAM langsung melihat bahwa F₁ ke W₃ berbiaya sangat rendah (1) dan segera mengalokasikan maksimal ke sana. Di iterasi 2, VAM konsisten mengikuti aturan standar: pilih sel biaya TERENDAH di baris/kolom penalty tertinggi — W₃ masih penalty tertinggi, dan min cost di W₃ yang tersisa adalah F₃ ke W₃ (biaya=3), bukan F₂ ke W₃ (biaya=5). Dengan mengikuti aturan standar ini secara konsisten, VAM langsung mencapai nilai optimal 2.100 tanpa perlu satu pun iterasi MODI. Coba Sendiri: Alokasikan Sendiri via NWC atau VAM Jalankan alokasi bertahap pada matriks supply-demand memakai NWC atau VAM, lalu bandingkan total biaya masing-masing metode terhadap kasus 3 pabrik x 4 gudang yang baru kita kerjakan.
🧪 Buka kalkulator penuh (Ranking alokasi optimal)
Ajak satu mahasiswa maju untuk menjalankan NWC pada widget ini, lalu mahasiswa lain menjalankan VAM pada data yang sama. Minta keduanya membandingkan total biaya akhir — kelas akan melihat sendiri bahwa VAM biasanya menghasilkan solusi awal yang jauh lebih dekat ke optimal dibanding NWC, persis seperti perbandingan Rp 3.050 versus Rp 2.100 yang baru kita hitung. Ini jadi jembatan alami menuju MODI Method di blok berikutnya, yang akan memverifikasi apakah hasil VAM itu benar-benar sudah optimal. Blok 2 dari 4
Optimasi dengan MODI Method
u + v = c · Opportunity Cost · Loop · Pivot
Kita tahu solusi VAM (2.100) jauh lebih baik dari NWC (3.050) — tapi apakah 2.100 itu sudah minimum mutlak? Kita tidak bisa hanya mengandalkan intuisi VAM; MODI Method (Modified Distribution Method) adalah alat verifikasi yang memberi kepastian matematis. Blok 2 ini adalah tentang verifikasi optimalitas: menggunakan sistem persamaan u+v=c untuk memeriksa apakah masih ada jalur distribusi yang lebih murah yang belum dimanfaatkan. Dalam kasus kita, VAM standar ternyata sudah langsung menghasilkan solusi optimal — MODI akan mengkonfirmasinya dengan semua w_ij positif. MODI Method — Prinsip & Rumus MODI (Modified Distribution Method) — verifikasi apakah solusi saat ini sudah optimal.
$$u_{i} + v_{j} = c_{ij} (sel terisi; set u_{1}=0)$$
$$w_{ij} = c_{ij} - u_{i} - v_{j} (sel kosong)$$
Optimal jika: semua $w_{ij} \geq 0$Jika ada $w_{ij}$ < 0: masukkan sel itu ke basis via loop
$w_{ij} \geq 0$ : jalur (i,j) tidak menghemat; jangan dipakai$w_{ij}$ < 0 : setiap unit yang dialihkan ke (i,j) menghemat $|w_{ij}|$ per unit$u_{i}$ = harga bayangan baris i (dual variable)$v_{j}$ = harga bayangan kolom jθ (theta) = jumlah unit yang dialihkan = min nilai di sel yang dikurangi dalam loop MODI Method terlihat rumit tapi pada intinya sederhana: kita menetapkan "harga bayangan" u dan v (dual variables) untuk setiap baris dan kolom, lalu menggunakannya untuk memeriksa apakah ada sel kosong yang bisa menghemat biaya. Mulai dengan menetapkan u_1 = 0 sebagai konvensi, lalu selesaikan sistem persamaan u_i + v_j = c_ij hanya untuk sel yang terisi — ini memberi kita semua nilai u dan v. Setelah itu, hitung w_ij = c_ij minus u_i minus v_j untuk setiap sel kosong. Kalau semua w_ij nol atau positif, tidak ada penghematan lagi — solusi kita sudah optimal. Kalau ada yang negatif, kita harus melakukan perbaikan via loop. Cara Membentuk Loop MODI dari Nol Loop MODI = rantai sel tertutup yang memungkinkan alokasi digeser tanpa melanggar constraint.
1 Mulai dari sel kosong $w_{ij}$ < 0 — beri tanda (+) 2 Gerak hanya horizontal atau vertikal , berbelok hanya di sel terisi 3 Tanda bergantian: $+ \to - \to + \to -$ dst. (kembali ke awal)4 Loop harus tertutup — kembali ke titik awalθ = min nilai di sel bertanda (−) Sel (+): tambahkan θ Sel (−): kurangi θ (satu sel menjadi $0 \to$ keluar basis) Sel kandidat (+): masuk basis Hitung ulang u, v, w — ulangi sampai semua w ≥ 0 Dalam contoh utama pertemuan ini, VAM standar langsung menghasilkan solusi optimal sehingga tidak ada $w_{ij}$ < 0 dan loop tidak diperlukan. Prosedur loop di atas berlaku umum ketika ada sel negatif.
Ini adalah langkah yang paling sering membuat pemula berhenti saat mengerjakan MODI — loop terlihat "muncul begitu saja" di slide tapi sebenarnya ada prosedur sistematis untuk menemukannya. Pertama, identifikasi sel kosong dengan w_ij negatif — itulah titik awal loop Anda, beri tanda plus. Dari sana, gerak hanya ke kanan atau ke kiri hingga menemukan sel terisi di baris yang sama, lalu belok ke atas atau ke bawah ke sel terisi lain, dan seterusnya sampai kembali ke titik awal. Syarat kritisnya: setiap belokan HARUS terjadi di sel yang sudah terisi. Sel bertanda minus adalah yang akan dikurangi sebesar theta — dan theta dipilih sebagai nilai terkecil di antara sel-sel minus agar tidak ada yang menjadi negatif. Hitung dari Nol 3 — MODI: Verifikasi Solusi VAM Solusi VAM: $F_{1}\to W_{3}=300; F_{2}\to W_{1}=250; F_{2}\to W_{4}=150; F_{3}\to W_{2}=350; F_{3}\to W_{3}=100; F_{3}\to W_{4}=50$. Set $u_{1}=0$.
Persamaan Perhitungan Nilai $u_{1}+v_{3}=1$ $F_{1}\to W_{3}; u_{1}=0$ $v_{3}=1$ $u_{3}+v_{3}=3$ $F_{3}\to W_{3}; v_{3}=1$ $u_{3}=2$ $u_{3}+v_{2}=1$ $F_{3}\to W_{2}; u_{3}=2$ $v_{2}=-1$ $u_{3}+v_{4}=2$ $F_{3}\to W_{4}; u_{3}=2$ $v_{4}=0$ $u_{2}+v_{4}=2$ $F_{2}\to W_{4}; v_{4}=0$ $u_{2}=2$ $u_{2}+v_{1}=3$ $F_{2}\to W_{1}; u_{2}=2$ $v_{1}=1$
u = [0, 2, 2] | v = [1, −1, 1, 0]
Sel Kosong Perhitungan w = c−u−v Status $F_{1}\to W_{1}$ 2 − 0 − 1 = +1 ✓ OK $F_{1}\to W_{2}$ 3 − 0 − (−1) = +4 ✓ OK $F_{1}\to W_{4}$ 4 − 0 − 0 = +4 ✓ OK $F_{2}\to W_{2}$ 2 − 2 − (−1) = +1 ✓ OK $F_{2}\to W_{3}$ 5 − 2 − 1 = +2 ✓ OK $F_{3}\to W_{1}$ 4 − 2 − 1 = +1 ✓ OK
Semua $w_{ij} \geq 0 \to$ Solusi VAM sudah optimal!
MODI dipakai untuk memverifikasi apakah solusi awal kita sudah optimal. Kita set u_1=0 lalu selesaikan sistem u+v=c untuk keenam sel yang terisi — hasilnya u=[0,2,2] dan v=[1,-1,1,0]. Kemudian hitung w_ij untuk setiap sel kosong: ternyata semua w_ij positif, artinya tidak ada jalur yang lebih murah yang belum dimanfaatkan. Inilah keunggulan VAM standar: dengan memilih sel biaya terendah secara konsisten, VAM seringkali langsung menghasilkan solusi yang sudah atau sangat dekat optimal. Penghematan total dibanding NWC: 3.050 minus 2.100 = 950 unit biaya, atau 31%. Interpretasi Solusi: Biaya Minimum & Opportunity Cost Setelah solusi optimal ditemukan, apa yang bisa kita simpulkan?
Rute Alokasi Biaya/unit Total Interpretasi $F_{1} \to W_{3}$ 300 1 300 F₁ kirim semua ke W₃ — jalur paling murah untuk F₁ $F_{2} \to W_{1}$ 250 3 750 F₂ penuhi semua kebutuhan W₁ $F_{2} \to W_{4}$ 150 2 300 F₂ kirim sisa ke W₄ $F_{3} \to W_{2}$ 350 1 350 F₃ penuhi semua kebutuhan W₂ — jalur paling murah F₃ $F_{3} \to W_{3}$ 100 3 300 F₃ bantu penuhi sisa W₃ $F_{3} \to W_{4}$ 50 2 100 F₃ bantu penuhi sisa W₄ TOTAL 1.200 2.100 Biaya minimum ✓
Solusi Optimal Terverifikasi — semua $w_{ij} \geq 0$. Penghematan vs NWC: 3.050 - 2.100 = 950 unit (31\%) .
Membaca tabel solusi optimal bukan sekadar melihat angka — ada keputusan manajerial di baliknya. Perhatikan bahwa F₁ mengalokasikan semua kapasitasnya ke W₃: ini masuk akal karena biaya F₁ ke W₃ = 1 adalah yang terkecil di seluruh matriks. F₃ juga mendominasi pengiriman ke W₂ dengan biaya 1, sementara F₂ dengan biaya sedang melayani W₁ dan W₄. Intuisi manajerial dari MODI: setiap pabrik "spesialisasi" melayani gudang yang paling hemat biayanya, dan pabrik dengan kapasitas lebih besar (F₃=500) mengambil peran ganda. Dalam konteks Bulog, ini berarti keputusan rute distribusi bukan sembarangan — ada metodologi ilmiah di baliknya. Coba Sendiri: Lebih Cepat, Lebih Mahal — Di Titik Mana Berhenti? Mode transportasi cepat (udara) mahal; mode lambat (laut) murah. Geser bobot antara kecepatan dan biaya untuk melihat rute optimal bergeser.
Ajak mahasiswa menaikkan bobot kecepatan dan mengamati rute udara menjadi layak meski biayanya tinggi — ilustrasi bahwa matriks biaya pada model transportasi bukan sekadar ongkos, tetapi bisa memuat dimensi kinerja lain yang ditimbang manajer. Studi Kasus 1 — Distribusi Beras Bulog Jawa–Sumatra Bulog mendistribusikan beras dari 3 gudang regional ke 4 kabupaten/kota. Biaya angkut (Rp ribu/ton) — ilustrasi edukatif:
Pekalongan (250 ton) Tegal (350 ton) Demak (400 ton) Batang (200 ton) Supply Semarang 200 300 100 400 300 Surabaya 300 200 500 200 400 Medan 400 100 300 200 500
Solusi Optimal: Rp 210.000 ribu (= Rp 210 juta)
vs NWC (Rp 305 juta): Rp 95 juta per distribusi∼Rp 1,14 miliar/tahun
Kasus ini dirancang untuk menunjukkan skala dampak nyata dari model yang kita pelajari. Angka biaya per ton adalah ilustrasi edukatif berdasarkan struktur biaya logistik domestik Indonesia — Anda bisa melihat bahwa jarak geografis memengaruhi biaya: gudang Semarang paling murah ke Demak karena paling dekat, sedangkan Medan mahal ke semua tujuan Jawa kecuali Tegal. Penghematan 31% per siklus distribusi, dikalikan 12 kali setahun, menghasilkan penghematan lebih dari Rp 1 miliar hanya dari satu wilayah. Bayangkan Bulog memiliki ratusan gudang di seluruh Indonesia — itulah skala nilai yang dihasilkan oleh optimasi manajemen sains. Perusahaan logistik besar seperti JNE, SiCepat, dan Pertamina benar-benar menggunakan model semacam ini dalam sistem TI mereka. Blok 3 dari 4
Masalah Penugasan & Hungarian Method
n×n matrix · Row reduction · Column reduction · Zero coverage · Optimal assignment
Kita beralih ke keluarga kedua dari model yang dipelajari hari ini: masalah penugasan (assignment problem). Prinsipnya mirip transportasi — meminimumkan total biaya/waktu/usaha — tetapi dengan struktur khusus: setiap "sumber" hanya bisa melayani tepat satu "tujuan" dan sebaliknya. Ini seperti menetapkan satu auditor ke satu satker, satu salesman ke satu wilayah, atau satu mesin ke satu pekerjaan. Algoritmanya, Hungarian Method (Metode Hungaria), diselesaikan sepenuhnya dengan operasi pengurangan matriks — tidak perlu LP solver dan bisa dikerjakan tangan. Struktur Masalah Penugasan Penugasan adalah kasus khusus transportasi: supply$_{i} =$ demand$_{j} = 1$ untuk semua i, j.
Aspek Transportasi Penugasan Sumber m pabrik/gudang n karyawan/mesin Tujuan n gudang/kota n tugas/pekerjaan Kapasitas $s_{i}$ (variasi) 1 (tepat satu) Matriks m×n (persegi panjang) n×n (selalu persegi) Alokasi Parsial boleh Satu-ke-satu eksklusif (one-to-one )
Matriks penugasan 4×4 (jam):
T1 T2 T3 T4 K1 9 2 7 8 K2 6 4 3 7 K3 5 8 1 8 K4 7 6 9 4
$c_{ij} =$ waktu penyelesaian tugas j oleh karyawan i, dalam jam
Perbedaan paling penting antara transportasi dan penugasan adalah pada struktur matriks. Dalam transportasi, supply dan demand bisa puluhan atau ratusan unit; dalam penugasan, selalu satu-ke-satu. Ini membuatnya lebih ketat: Anda tidak bisa membagi seorang auditor ke dua satker sekaligus, dan satu satker tidak bisa diaudit dua tim sekaligus. Matriks penugasan selalu persegi (n kali n): kalau ada 4 karyawan dan 4 tugas, matriks 4 kali 4. Data yang kita pakai adalah matriks waktu 4 kali 4: K1 butuh 9 jam untuk T1 dan hanya 2 jam untuk T2. Tujuan kita: tentukan siapa mengerjakan apa agar total jam minimum. Hungarian Method — Tahapan Utama Hungarian Method (Metode Hungaria) — dikembangkan Harold Kuhn (1955), algoritma tepat untuk masalah penugasan.
LANGKAH 1 Row Reduction Kurangi tiap baris dengan nilai min baris LANGKAH 2 Column Reduction Kurangi tiap kolom dengan nilai min kolom LANGKAH 3 Zero Coverage Tutup semua nol; hitung garis minimum. Jika =n → OPTIMAL LANGKAH 4 Augmentasi Jika garis < n: cari min tidak tertutup; kurangi/tambah; ulangi Setelah row + column reduction, cari n nol independen (tidak ada di baris/kolom yang sama). Jika ketemu langsung $\to$ OPTIMAL tanpa augmentasi.
Hungarian Method dikembangkan oleh matematikawan Harold Kuhn pada 1955, diinspirasi karya Dénes König dan Jenő Egerváry. Idenya brilian: dengan pengurangan baris dan kolom, kita tidak mengubah penugasan optimal — biaya relatif antar sel tetap sama, hanya skala berubah. Kita ingin menemukan n nol yang "independen" — satu di setiap baris dan satu di setiap kolom, tidak berbagi. Jika setelah dua langkah pertama kita sudah bisa menemukan n nol independen, selesai — tidak perlu augmentasi. Jika belum, kita lakukan augmentasi untuk menciptakan nol tambahan. Langkah 1–2: Row & Column Reduction Terapkan pada matriks 4×4:
Matriks Awal
T1 T2 T3 T4 Min K1 9 2 7 8 2 K2 6 4 3 7 3 K3 5 8 1 8 1 K4 7 6 9 4 4
Setelah Row Reduction
T1 T2 T3 T4 Col min K1 7 0 5 6 K2 3 1 0 4 K3 4 7 0 7 K4 3 2 5 0 Col min 3 0 0 0
Setelah Column Reduction
T1 T2 T3 T4 K1 4 0 5 6 K2 0 1 0 4 K3 1 7 0 7 K4 0 2 5 0
Nol: K1T2, K2T1, K2T3, K3T3, K4T1, K4T4
Proses row reduction dan column reduction sangat mekanis — sekadar pengurangan aritmetika. Untuk row reduction: K1 minimum=2, kurangi semua elemen K1 dengan 2; hasilnya K1 menjadi 7, 0, 5, 6. Lakukan hal sama untuk K2 (min=3), K3 (min=1), K4 (min=4). Setelah row reduction, setiap baris pasti memiliki minimal satu nol. Untuk column reduction, periksa kolom mana yang belum punya nol: kolom T1 minimumnya 3, kurangi semua elemen T1 dengan 3; T2, T3, T4 sudah punya nol jadi minimum=0, tidak berubah. Setelah keduanya, kita punya matriks tereduksi. Sekarang pertanyaannya: bisakah kita pilih 4 nol yang independen — tidak berbagi baris maupun kolom? Coba Sendiri: Jalankan Row & Column Reduction Sendiri Kurangi baris dan kolom pada matriks penugasan, tutup nol dengan garis minimum, dan ulangi hingga penugasan optimal satu-ke-satu tercapai.
Minta mahasiswa mengubah satu elemen matriks biaya dan ulangi reduction — tunjukkan bahwa jumlah garis minimum yang diperlukan berubah. Inilah inti tes konvergensi Hungarian yang membedakannya dari heuristik biasa. Hitung dari Nol 4 — Hungarian Method 4×4 Lanjutan Slide 20. Matriks tereduksi $\to$ cari 4 nol independen.
Langkah Greedy Perhitungan Nilai K1: hanya 1 nol di T2 Tugaskan $K1\to T2$; coret baris K1, kolom T2 $K1\to T2 ✓$ K3: setelah T2 coret, hanya T3 Tugaskan $K3\to T3$; coret baris K3, kolom T3 $K3\to T3 ✓$ K2: setelah T3 coret, hanya T1 Tugaskan $K2\to T1$; coret baris K2, kolom T1 $K2\to T1 ✓$ K4: setelah T1 coret, hanya T4 Tugaskan $K4\to T4$ $K4\to T4 ✓$
4 nol independen ditemukan $\to$ Solusi Optimal ✓ (Teorema König: min garis = n = 4)
Penugasan Optimal (dari matriks asli):
Karyawan Tugas Biaya (jam) K1 T2 2 K2 T1 6 K3 T3 1 K4 T4 4 Total 13 jam ✓
Alternatif: $K1\to T1, K2\to T2, K3\to T3, K4\to T4 = 9+4+1+4 =$ 18 jam (+5)
Kunci penugasan optimal ada pada prosedur greedy yang sistematis — BUKAN intuisi kasus per kasus. Aturannya: cari baris atau kolom yang hanya punya SATU nol, tetapkan penugasan itu, coret baris dan kolomnya, ulangi. Terapkan ke kasus kita: K1 paling mudah — hanya punya satu nol di T2, langsung tetapkan dan coret. Setelah K1 dan T2 dicoret, K3 hanya punya satu nol tersisa di T3, tetapkan dan coret. Setelah T3 dicoret, K2 hanya punya satu nol tersisa di T1, tetapkan dan coret. K4 tinggal T4. Hasilnya: total biaya 2+6+1+4=13 jam. Optimalitasnya dijamin oleh Teorema König: jumlah garis minimum yang menutup semua nol = 4 = n. Blok 4 dari 4
Kasus Khusus & Studi Kasus Indonesia
Maksimasi · Tidak Seimbang · BPK RI · Rangkuman
Dua model yang kita pelajari — transportasi dan penugasan — dalam contoh sebelumnya selalu berupa minimasi biaya dan matriks seimbang. Kenyataan di lapangan lebih beragam: kadang kita ingin memaksimalkan (laba, produktivitas), dan kadang jumlah sumber tidak sama dengan tujuan. Blok terakhir ini membekali Anda dengan dua trik sederhana untuk mengadaptasi model ke situasi tersebut, dilanjutkan dengan studi kasus penugasan auditor BPK RI yang lebih kontekstual. Kasus Khusus: Maksimasi & Penugasan Tidak Seimbang Dua situasi yang sering muncul di soal ujian dan praktik nyata:
Ubah ke minimasi: $c'_{ij} = M - c_{ij} (M =$ nilai terbesar dalam matriks) Alternatif: $c'_{ij} = -c_{ij} \to$ minimasi $\to$ balik tanda hasil Contoh: $[10, 8, 12, 7] \to M=12 \to [2, 4, 0, 5] \to$ minimasi Wajib: konversi SEBELUM row & column reductionLebih banyak karyawan dari tugas $(n_{K}$ > $n_{T})$: tambah tugas dummy biaya 0 Lebih banyak tugas dari karyawan $(n_{T}$ > $n_{K})$: tambah karyawan dummy biaya 0 Karyawan yang "ditugaskan ke dummy" = idle (tidak mendapat tugas periode ini) Prinsip: persegikan matriks dulu, baru jalankan Hungarian Di dunia nyata, manajer seringkali tidak ingin meminimumkan biaya tetapi memaksimumkan output. Misalnya: menetapkan tim sales ke wilayah berdasarkan proyeksi revenue, bukan biaya. Triknya sederhana: cari nilai terbesar dalam matriks (M), lalu kurangi semua elemen dengan M. Matriks yang tadinya "profit besar = baik" berubah menjadi "angka kecil = baik" — persis format minimasi yang bisa kita jalankan. Untuk matriks tidak seimbang, selalu "persegikan" dengan dummy: kalau ada 4 karyawan dan 3 tugas, tambah kolom tugas dummy ke-4 dengan biaya 0 di semua barisnya. Dua trik ini membuat Hungarian Method berlaku universal untuk hampir semua variasi masalah penugasan. Studi Kasus 2 — Penugasan Tim Audit BPK RI ke Satker BPK RI (Badan Pemeriksa Keuangan) perlu menugaskan 4 tim auditor ke 4 satker (satuan kerja). Minimumkan total waktu penyelesaian.
Matriks waktu penyelesaian (minggu) — ilustrasi edukatif:
Kemenkeu Kemenkes Kominfo BNPB Tim A 9 2 7 8 Tim B 6 4 3 7 Tim C 5 8 1 8 Tim D 7 6 9 4
Matriks identik dengan HDN-4 — untuk efisiensi waktu kuliah. Angka = ilustrasi, bukan data BPK aktual.
Hasil Hungarian Method (dari HDN-4):
Tim Satker Waktu (mgg) Tim A Kemenkes 2 Tim B Kemenkeu 6 Tim C Kominfo 1 Tim D BNPB 4 Total 13 minggu ✓
Penugasan sembarang: bisa mencapai 25–30 minggu . Penghematan waktu hingga 17 minggu .
Kasus BPK RI ini mencerminkan kenyataan administrasi pemerintahan Indonesia. BPK setiap tahun memeriksa ribuan satker — LKPP (Laporan Keuangan Pemerintah Pusat) harus selesai diperiksa sebelum batas waktu konstitusional. Penugasan yang tidak efisien bisa menyebabkan audit mundur berminggu-minggu, yang berdampak pada keterlambatan pengesahan APBN tahun berikutnya. Perhatikan bahwa Tim C ke Kominfo hanya membutuhkan 1 minggu — Tim C adalah spesialis PNBP (Penerimaan Negara Bukan Pajak — jenis penerimaan negara di luar pajak) yang sangat relevan dengan profil Kominfo. Intuisi ini dikonfirmasi secara matematis oleh algoritma — inilah kekuatan manajemen sains: mengubah intuisi menjadi keputusan terverifikasi. Coba Sendiri: Konsolidasi Pengiriman — Hemat Biaya atau Tambah Emisi? Menggabungkan beberapa pengiriman ke satu armada sering menurunkan biaya, tetapi memengaruhi emisi dan waktu. Eksplorasi trade-off konsolidasi di sini.
Tekankan bahwa model transportasi modern tidak hanya meminimalkan biaya — emisi karbon dan service level juga menjadi kriteria. Diskusikan kapan solusi biaya-minimum murni tidak lagi cukup di dunia rantai pasok berkelanjutan. Peta Konsep: Transportasi vs Penugasan Dua model, satu keluarga LP — perbedaan dan persamaannya:
Dimensi Transportasi Penugasan Tujuan Min total biaya pengiriman Min total biaya/waktu penugasan Matriks m×n (persegi panjang) n×n (selalu persegi) Alokasi Fraksional boleh $(x_{ij}$ bebas) Biner: 0 atau 1 (satu-ke-satu) Solusi awal NWC atau VAM Tidak diperlukan Optimasi MODI Method Hungarian Method Sel terisi Tepat m+n−1 sel Tepat n sel Kasus khusus Dummy row/col jika unbalanced Dummy row/col + konversi maksimasi Contoh Indonesia Distribusi beras Bulog Penugasan auditor BPK RI
Keduanya adalah LP khusus dengan struktur integer otomatis — tidak perlu solver integer programming (unimodularitas total).
Sebelum kita tutup, mari konsolidasikan pemahaman dengan melihat kedua model secara bersamaan. Transportasi dan penugasan sama-sama adalah LP (Linear Programming), tapi keduanya memiliki struktur yang sangat khusus sehingga bisa diselesaikan dengan algoritma dedikasi yang jauh lebih efisien dari simplex umum. Perbedaan kunci: transportasi mengizinkan alokasi parsial (F₁ bisa mengirim 250 ke W₁ dan 50 ke W₂), sementara penugasan harus eksklusif satu-ke-satu. Satu persamaan penting yang sering ditanyakan di ujian: kedua model menghasilkan solusi integer secara otomatis — Anda tidak perlu membulatkan jawaban — karena struktur LP-nya memiliki sifat matematis yang disebut unimodularitas total. Persiapan Pertemuan 6 Pertemuan 5 selesai. Yang perlu Anda ingat dan siapkan:
Transportasi: NWC (awal) $\to$ VAM (lebih baik) $\to$ MODI (optimal); tepat m+n−1 selContoh kita: NWC$=3.050 \to$ VAM standar=2.100 (optimal, dikonfirmasi MODI)Penugasan: row reduction $\to$ column reduction $\to$ cari n nol independenContoh kita: Hungarian $4\times 4 \to$ total 13 jam optimalKasus khusus: dummy (unbalanced) $\cdot M-c_{ij}$ (maksimasi)Baca materi Pertemuan 6: Analisis Keputusan dalam Ketidakpastian (payoff table, maximax/maximin, EV/EVPI) Kerjakan minimal 2 soal latihan Lampiran B — model hanya dikuasai dengan latihan Refleksi: di bisnis atau karier Anda nanti, di mana mungkin Anda menghadapi masalah transportasi atau penugasan? Bawa catatan metode — pertemuan berikutnya langsung masuk soal Hari ini kita telah menempuh perjalanan panjang dari memahami struktur masalah distribusi hingga mengoptimalkan solusinya secara matematis. Tiga metode yang kita kuasai — VAM, MODI, Hungarian Method — adalah alat standar Operations Research yang diajarkan di kampus bisnis terbaik dunia dan dipakai oleh praktisi logistik, supply chain, dan manajemen SDM setiap hari. Pertemuan berikutnya akan membahas Analisis Keputusan dalam Ketidakpastian — bagaimana memutuskan ketika kita tidak tahu pasti apa yang akan terjadi: payoff table, kriteria maximax, maximin, dan nilai informasi sempurna (EVPI). Sebelum pertemuan berikutnya, sangat saya rekomendasikan Anda mengerjakan minimal dua soal dari Lampiran B untuk memastikan prosedur sudah tertanam dengan baik. Manajemen Sains • FEB UNDIP
Terima Kasih
Pertemuan 5 — Model Transportasi & Penugasan
NWC $\to 3.050$
Solusi awal cepat
VAM+MODI $\to 2.100$
Optimal (hemat 31%)
Hungarian $\to 13$ jam
Penugasan optimal
Selamat! Anda telah menyelesaikan Pertemuan 5 Manajemen Sains. Tiga angka kunci yang perlu Anda ingat: NWC menghasilkan biaya awal 3.050, VAM dan MODI membuktikan solusi optimal 2.100 — penghematan 31% — dan Hungarian Method menemukan penugasan optimal dengan total 13 jam. Di balik angka-angka ini, ada prinsip yang lebih besar: bahwa keputusan distribusi dan penugasan yang terlihat sederhana di kehidupan sehari-hari sebenarnya memiliki solusi matematis yang terverifikasi. Itulah kekuatan manajemen sains. Sampai jumpa di Pertemuan 6. 📖 Bacaan pendalaman: Lean Six Sigma , Studi Kelayakan Bisnis , Cost-Benefit Analysis .