Kuliah · Kuliah · Aljabar

Riset Operasi

Riset Operasi memakai model matematika untuk mengambil keputusan terbaik dengan sumber daya terbatas. Intinya adalah program linear: memaksimumkan atau meminimumkan fungsi tujuan linear terhadap kendala linear, yang diselesaikan dengan metode simpleks dan dipahami lebih dalam lewat dualitas. Struktur khusus program linear melahirkan algoritma efisien untuk transportasi, penugasan, dan jaringan (lintasan terpendek dan jalur kritis proyek).

Daftar isi
  1. Konsep
  2. Rumus
  3. Contoh soal
  4. Kesalahan umum
  5. Coba sendiri
  6. Kuis 5 soal
  7. Tanya jawab
  8. Topik terkait
  9. Untuk guru

Konsep Riset Operasi

Bab 1 — Program linear dan metode grafik

Model program linear (PL) terdiri atas variabel keputusan, fungsi tujuan Z=cTxZ = c^{T}x, dan kendala Ax≤bAx \le b, x≥0x \ge 0. Himpunan titik yang memenuhi semua kendala disebut daerah layak; daerah ini konveks.

Teorema fundamental PL: jika masalah PL punya solusi optimum, salah satu solusi optimum terletak di titik pojok daerah layak. Untuk dua variabel, gambar kendala, tentukan titik pojok, lalu bandingkan nilai ZZ di setiap titik (atau geser garis selidik). Kemungkinan hasil: solusi tunggal, solusi optimum ganda (garis selidik sejajar sisi daerah layak), tak terbatas, atau tak layak.

Bab 2 — Metode simpleks

Metode simpleks berjalan dari satu titik pojok ke titik pojok tetangga yang lebih baik. Langkahnya:

  1. Ubah ke bentuk baku: tambahkan variabel slack pada kendala ≤\le (kurangkan surplus dan tambahkan variabel buatan untuk kendala ≥\ge atau ==, lalu pakai metode Big-M atau dua fase).
  2. Variabel masuk: kolom dengan koefisien baris ZZ paling negatif (untuk maksimasi).
  3. Variabel keluar: uji rasio minimum biaik\frac{b_i}{a_{ik}} hanya untuk aik>0a_{ik} > 0.
  4. Lakukan operasi baris (pivot) dan ulangi sampai semua koefisien baris ZZ tak negatif.

Setiap tabel simpleks berkaitan dengan satu solusi layak basis, yaitu satu titik pojok.

Bab 3 — Dualitas dan analisis sensitivitas

Setiap PL (primal) max⁡ cTx\max\, c^{T}x dengan Ax≤bAx \le b, x≥0x \ge 0 memiliki dual min⁡ bTy\min\, b^{T}y dengan ATy≥cA^{T}y \ge c, y≥0y \ge 0. Dualitas lemah: untuk solusi layak apa pun, cTx≤bTyc^{T}x \le b^{T}y. Dualitas kuat: jika salah satu punya optimum berhingga, keduanya punya dan nilainya sama.

Variabel dual optimum yi∗y_i^{\ast} disebut harga bayangan (shadow price): kenaikan nilai optimum bila ruas kanan kendala ke-ii ditambah satu satuan (selama basis tidak berubah). Nilai ini terbaca di baris ZZ tabel simpleks akhir pada kolom slack. Kelengkapan komplementer: jika kendala primal tidak aktif (slack positif), harga bayangannya nol.

Bab 4 — Transportasi dan penugasan

Masalah transportasi mengirim barang dari mm sumber (pasokan sis_i) ke nn tujuan (permintaan djd_j) dengan biaya satuan cijc_{ij}. Jika seimbang (∑si=∑dj\sum s_i = \sum d_j), solusi basis memuat m+n−1m + n - 1 variabel. Solusi awal dicari dengan sudut barat laut, biaya terkecil, atau metode Vogel; optimalitasnya diuji dengan metode MODI (ui+vj=ciju_i + v_j = c_{ij} pada sel basis, dan sel nonbasis dengan cij−ui−vj<0c_{ij} - u_i - v_j < 0 masih dapat memperbaiki biaya).

Masalah penugasan adalah kasus khusus dengan setiap pasokan dan permintaan bernilai 1: nn pekerja ke nn tugas. Metode Hungaria mengurangkan minimum baris dan kolom, lalu mencari nn nol yang saling bebas.

Bab 5 — Analisis jaringan

Lintasan terpendek dari satu simpul ke simpul lain pada graf berbobot tak negatif dicari dengan algoritma Dijkstra: tetapkan label sementara, pilih simpul berlabel terkecil sebagai permanen, lalu perbarui tetangganya. Pohon rentang minimum (Kruskal atau Prim) dipakai untuk jaringan kabel atau pipa termurah.

Dalam manajemen proyek, CPM menghitung waktu mulai paling awal (ES) dengan lintasan maju dan waktu paling lambat (LS) dengan lintasan mundur. Aktivitas dengan slack LS−ES=0LS - ES = 0 membentuk jalur kritis, yaitu lintasan terpanjang yang menentukan durasi proyek. PERT menambahkan ketidakpastian dengan estimasi waktu a+4m+b6\frac{a + 4m + b}{6}.

Rumus

Bentuk umum program linear
max⁡Z=cTxd.k.Ax≤b, x≥0\max Z = c^{T}x \quad \text{d.k.} \quad Ax \le b, \ x \ge 0
Pasangan dual
min⁡W=bTyd.k.ATy≥c, y≥0\min W = b^{T}y \quad \text{d.k.} \quad A^{T}y \ge c, \ y \ge 0
Dualitas lemah
cTx≤bTyc^{T}x \le b^{T}y
Uji optimal MODI
ui+vj=cij (sel basis),cˉij=cij−ui−vj≥0u_i + v_j = c_{ij} \ \text{(sel basis)}, \quad \bar{c}_{ij} = c_{ij} - u_i - v_j \ge 0
Waktu harapan PERT
te=a+4m+b6t_e = \frac{a + 4m + b}{6}

Contoh soal riset operasi dan pembahasan

Contoh 1 · Mudah

Program linear dengan metode grafik

UMKM tahu-tempe di Sumedang memproduksi xx kuintal tahu dan yy kuintal tempe per minggu. Kendala kedelai x+y≤8x + y \le 8 dan jam mesin 2x+y≤122x + y \le 12, dengan x,y≥0x, y \ge 0. Laba (juta rupiah) Z=4x+3yZ = 4x + 3y. Tentukan laba maksimum.

Lihat langkah penyelesaian
  1. Titik pojok daerah layak: (0,0)(0, 0), (6,0)(6, 0), (0,8)(0, 8), dan perpotongan x+y=8x + y = 8 dengan 2x+y=122x + y = 12, yaitu (4,4)(4, 4).
  2. Nilai ZZ: Z(0,0)=0Z(0, 0) = 0, Z(6,0)=24Z(6, 0) = 24, Z(0,8)=24Z(0, 8) = 24, Z(4,4)=16+12=28Z(4, 4) = 16 + 12 = 28.
  3. Maksimum di titik pojok (4,4)(4, 4).

Laba maksimum Rp28 juta dengan 4 kuintal tahu dan 4 kuintal tempe.

Contoh 2 · Sedang

Metode simpleks untuk masalah yang sama

Selesaikan masalah UMKM di atas dengan metode simpleks dan tunjukkan nilai ZZ pada setiap iterasi.

Lihat langkah penyelesaian
  1. Bentuk baku: x+y+s1=8x + y + s_1 = 8, 2x+y+s2=122x + y + s_2 = 12, Z−4x−3y=0Z - 4x - 3y = 0. Solusi awal s1=8s_1 = 8, s2=12s_2 = 12, Z=0Z = 0.
  2. Iterasi 1: xx masuk (koefisien −4-4). Rasio 81=8\frac{8}{1} = 8 dan 122=6\frac{12}{2} = 6, jadi s2s_2 keluar. Hasil: x=6−12y−12s2x = 6 - \frac{1}{2}y - \frac{1}{2}s_2 dan Z=24+y−2s2Z = 24 + y - 2s_2.
  3. Iterasi 2: yy masuk (koefisien baris ZZ adalah −1-1). Baris s1s_1: 12y+s1−12s2=2\frac{1}{2}y + s_1 - \frac{1}{2}s_2 = 2 dengan rasio 4, lebih kecil daripada rasio baris xx (61/2=12\frac{6}{1/2} = 12). Jadi y=4−2s1+s2y = 4 - 2s_1 + s_2.
  4. Akhir: Z=28−2s1−s2Z = 28 - 2s_1 - s_2. Semua koefisien tak negatif, jadi optimum Z=28Z = 28 di x=4x = 4, y=4y = 4.

Nilai ZZ berturut-turut 0, 24, lalu 28 (optimum).

Contoh 3 · Sedang

Dual dan harga bayangan

Tuliskan dual masalah UMKM tersebut, lalu tentukan solusi optimum dual dan nilainya.

Lihat langkah penyelesaian
  1. Dual: minimumkan W=8u+12vW = 8u + 12v dengan u+2v≥4u + 2v \ge 4, u+v≥3u + v \ge 3, u,v≥0u, v \ge 0.
  2. Dari tabel simpleks akhir, koefisien s1s_1 dan s2s_2 di baris ZZ adalah 2 dan 1, jadi u∗=2u^{\ast} = 2 dan v∗=1v^{\ast} = 1. Keduanya memenuhi kendala dual dengan tanda sama dengan.
  3. W∗=8×2+12×1=28W^{\ast} = 8 \times 2 + 12 \times 1 = 28, sama dengan Z∗Z^{\ast} (dualitas kuat).
  4. Tafsiran: tambahan 1 kuintal kedelai menaikkan laba sekitar Rp2 juta, sedangkan tambahan 1 jam mesin menaikkan Rp1 juta.

u∗=2u^{\ast} = 2, v∗=1v^{\ast} = 1, dan W∗=28W^{\ast} = 28.

Contoh 4 · Sedang

Masalah transportasi dan uji MODI

Dua pabrik P1 (pasokan 50 ton) dan P2 (70 ton) mengirim ke gudang G1, G2, G3 dengan permintaan 30, 40, 50 ton. Biaya per ton (ratus ribu rupiah): P1 ke G1, G2, G3 = 4, 6, 8; P2 = 5, 3, 7. Mulai dari sudut barat laut, tentukan biaya minimum.

Lihat langkah penyelesaian
  1. Sudut barat laut: x11=30x_{11} = 30, x12=20x_{12} = 20, x22=20x_{22} = 20, x23=50x_{23} = 50. Biaya 120+120+60+350=650120 + 120 + 60 + 350 = 650.
  2. MODI dengan u1=0u_1 = 0: v1=4v_1 = 4, v2=6v_2 = 6, u2=−3u_2 = -3, v3=10v_3 = 10. Sel (1,3)(1, 3): 8−0−10=−2<08 - 0 - 10 = -2 < 0, jadi biaya dapat diturunkan.
  3. Loop (1,3)+,(2,3)−,(2,2)+,(1,2)−(1, 3)^{+}, (2, 3)^{-}, (2, 2)^{+}, (1, 2)^{-} dengan θ=20\theta = 20: x11=30x_{11} = 30, x13=20x_{13} = 20, x22=40x_{22} = 40, x23=30x_{23} = 30.
  4. Biaya baru 30×4+20×8+40×3+30×7=61030 \times 4 + 20 \times 8 + 40 \times 3 + 30 \times 7 = 610. Uji ulang: u1=0u_1 = 0, v1=4v_1 = 4, v3=8v_3 = 8, u2=−1u_2 = -1, v2=4v_2 = 4; sel (1,2)(1, 2) dan (2,1)(2, 1) bernilai 2≥02 \ge 0, jadi optimum.

Biaya minimum 610 ratus ribu rupiah (Rp61 juta).

Contoh 5 · Penalaran

Jalur kritis proyek dengan CPM

Proyek renovasi balai desa terdiri atas aktivitas A (3 hari), B (4 hari), C (2 hari, setelah A), D (5 hari, setelah A dan B), dan E (3 hari, setelah C dan D). Tentukan durasi minimum proyek dan jalur kritisnya.

Lihat langkah penyelesaian
  1. Lintasan maju: A selesai hari ke-3, B ke-4. C mulai 3, selesai 5. D mulai max⁡(3,4)=4\max(3, 4) = 4, selesai 9. E mulai max⁡(5,9)=9\max(5, 9) = 9, selesai 12.
  2. Lintasan mundur dari 12: E paling lambat mulai 9, D mulai 4, C mulai 7, B mulai 0, A mulai 1.
  3. Slack: A = 1, B = 0, C = 4, D = 0, E = 0. Jalur kritis B–D–E dengan panjang 4+5+3=124 + 5 + 3 = 12.

Durasi minimum 12 hari dengan jalur kritis B–D–E.

Kesalahan yang sering terjadi

Pada uji rasio simpleks, ikut menghitung baris dengan entri kolom pivot negatif atau nol.
Rasio hanya dihitung untuk entri positif. Entri negatif berarti variabel basis itu justru bertambah saat variabel masuk naik, sehingga tidak membatasi langkah.
Menganggap solusi sudut barat laut sudah optimal.
Sudut barat laut hanya memberi solusi awal yang layak, tanpa memperhatikan biaya. Selalu uji dengan MODI atau batu loncatan dan perbaiki bila ada cˉij<0\bar{c}_{ij} < 0.
Mengira jalur kritis adalah lintasan dengan aktivitas terbanyak atau terpendek.
Jalur kritis adalah lintasan dengan total durasi terpanjang; semua aktivitasnya ber-slack nol, sehingga keterlambatan satu aktivitas menunda seluruh proyek.

Coba sendiri

Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.

Soal 1Aplikasi
Maksimumkan Z=5x+2yZ = 5x + 2y dengan kendala x+y≤6x + y \le 6, x≤4x \le 4, x,y≥0x, y \ge 0. Berapa nilai ZZ maksimum?
Soal 2Aplikasi

Tiga teknisi ditugaskan ke tiga lokasi, masing-masing satu. Biaya (ratus ribu rupiah):

TeknisiLokasi 1Lokasi 2Lokasi 3
A927
B643
C581
Berdasarkan tabel biaya di atas, berapa total biaya penugasan minimum?
Soal 3Penalaran
Aktivitas proyek: A (2 hari), B (5 hari), C (4 hari, setelah A), D (3 hari, setelah A), E (2 hari, setelah B dan C), F (6 hari, setelah D). Berapa hari durasi minimum proyek?
hari

Kuis 5 soal

Kerjakan semua soal, lalu periksa sekaligus.

Soal 1Pemahaman
Pada metode simpleks untuk maksimasi, variabel masuk dipilih dari kolom dengan …
Soal 2Pemahaman
Pernyataan: "Jika masalah primal memiliki solusi optimum berhingga, masalah dualnya juga memiliki solusi optimum dengan nilai fungsi tujuan yang sama." Benar atau salah?
Soal 3Aplikasi
Masalah transportasi seimbang dengan 3 sumber dan 4 tujuan memiliki solusi basis tak merosot dengan banyak variabel basis …
Soal 4Penalaran
Pilih semua pernyataan yang benar tentang program linear dan simpleks.
Pilih semua jawaban yang benar.
Soal 5Penalaran
Primal: maksimumkan Z=3x+2yZ = 3x + 2y dengan x+y≤4x + y \le 4, x+3y≤6x + 3y \le 6, x,y≥0x, y \ge 0. Tanpa menyelesaikan dual secara langsung, berapa nilai optimum masalah dualnya?

Latihan tanpa batas

Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.

Mulai latihan

Tanya jawab

Apakah metode simpleks masih dipakai di era komputer?

Ya. Pemecah (solver) modern memakai simpleks yang disempurnakan dan metode titik interior untuk masalah dengan jutaan variabel, misalnya penjadwalan maskapai, distribusi logistik, dan bauran pakan ternak.

Mengapa perlu mempelajari dualitas?

Dual memberi harga bayangan sumber daya (berapa nilai tambahan satu satuan bahan atau jam kerja), memberi batas atas atau bawah tanpa menyelesaikan primal, dan kadang lebih mudah diselesaikan.

Topik terkait

Ringkasan untuk guru

Tujuan pembelajaran

  • Mahasiswa merumuskan masalah keputusan sebagai program linear dan menyelesaikannya secara grafik.
  • Mahasiswa menjalankan metode simpleks dan menafsirkan tabel akhir, termasuk harga bayangan.
  • Mahasiswa menyusun dual dan memakai teorema dualitas.
  • Mahasiswa menyelesaikan masalah transportasi, penugasan, lintasan terpendek, dan CPM.

Ide aktivitas kelas

  • Studi kasus UMKM lokal: kelompok mewawancarai pelaku usaha, menyusun model PL dari data bahan dan jam kerja, lalu mempresentasikan rekomendasi produksi.
  • Simpleks dengan lembar kerja: mahasiswa membuat tabel simpleks di lembar kerja dan membandingkan hasilnya dengan pemecah bawaan.
  • Jadwal proyek kampus: mahasiswa memodelkan kepanitiaan acara sebagai jaringan aktivitas, mencari jalur kritis, dan menguji dampak keterlambatan.

Acuan: Silabus umum mata kuliah Riset Operasi program sarjana matematika, statistika, dan teknik industri (disusun tim redaksi), elemen Aljabar.

Bagikan latihan ke kelas dengan kode tugas