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
Konsep Riset Operasi
Bab 1 — Program linear dan metode grafik
Model program linear (PL) terdiri atas variabel keputusan, fungsi tujuan , dan kendala , . 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 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:
- Ubah ke bentuk baku: tambahkan variabel slack pada kendala (kurangkan surplus dan tambahkan variabel buatan untuk kendala atau , lalu pakai metode Big-M atau dua fase).
- Variabel masuk: kolom dengan koefisien baris paling negatif (untuk maksimasi).
- Variabel keluar: uji rasio minimum hanya untuk .
- Lakukan operasi baris (pivot) dan ulangi sampai semua koefisien baris tak negatif.
Setiap tabel simpleks berkaitan dengan satu solusi layak basis, yaitu satu titik pojok.
Bab 3 — Dualitas dan analisis sensitivitas
Setiap PL (primal) dengan , memiliki dual dengan , . Dualitas lemah: untuk solusi layak apa pun, . Dualitas kuat: jika salah satu punya optimum berhingga, keduanya punya dan nilainya sama.
Variabel dual optimum disebut harga bayangan (shadow price): kenaikan nilai optimum bila ruas kanan kendala ke- ditambah satu satuan (selama basis tidak berubah). Nilai ini terbaca di baris 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 sumber (pasokan ) ke tujuan (permintaan ) dengan biaya satuan . Jika seimbang (), solusi basis memuat variabel. Solusi awal dicari dengan sudut barat laut, biaya terkecil, atau metode Vogel; optimalitasnya diuji dengan metode MODI ( pada sel basis, dan sel nonbasis dengan masih dapat memperbaiki biaya).
Masalah penugasan adalah kasus khusus dengan setiap pasokan dan permintaan bernilai 1: pekerja ke tugas. Metode Hungaria mengurangkan minimum baris dan kolom, lalu mencari 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 membentuk jalur kritis, yaitu lintasan terpanjang yang menentukan durasi proyek. PERT menambahkan ketidakpastian dengan estimasi waktu .
Rumus
Contoh soal riset operasi dan pembahasan
Program linear dengan metode grafik
UMKM tahu-tempe di Sumedang memproduksi kuintal tahu dan kuintal tempe per minggu. Kendala kedelai dan jam mesin , dengan . Laba (juta rupiah) . Tentukan laba maksimum.
Lihat langkah penyelesaian
- Titik pojok daerah layak: , , , dan perpotongan dengan , yaitu .
- Nilai : , , , .
- Maksimum di titik pojok .
Laba maksimum Rp28 juta dengan 4 kuintal tahu dan 4 kuintal tempe.
Metode simpleks untuk masalah yang sama
Selesaikan masalah UMKM di atas dengan metode simpleks dan tunjukkan nilai pada setiap iterasi.
Lihat langkah penyelesaian
- Bentuk baku: , , . Solusi awal , , .
- Iterasi 1: masuk (koefisien ). Rasio dan , jadi keluar. Hasil: dan .
- Iterasi 2: masuk (koefisien baris adalah ). Baris : dengan rasio 4, lebih kecil daripada rasio baris (). Jadi .
- Akhir: . Semua koefisien tak negatif, jadi optimum di , .
Nilai berturut-turut 0, 24, lalu 28 (optimum).
Dual dan harga bayangan
Tuliskan dual masalah UMKM tersebut, lalu tentukan solusi optimum dual dan nilainya.
Lihat langkah penyelesaian
- Dual: minimumkan dengan , , .
- Dari tabel simpleks akhir, koefisien dan di baris adalah 2 dan 1, jadi dan . Keduanya memenuhi kendala dual dengan tanda sama dengan.
- , sama dengan (dualitas kuat).
- Tafsiran: tambahan 1 kuintal kedelai menaikkan laba sekitar Rp2 juta, sedangkan tambahan 1 jam mesin menaikkan Rp1 juta.
, , dan .
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
- Sudut barat laut: , , , . Biaya .
- MODI dengan : , , , . Sel : , jadi biaya dapat diturunkan.
- Loop dengan : , , , .
- Biaya baru . Uji ulang: , , , , ; sel dan bernilai , jadi optimum.
Biaya minimum 610 ratus ribu rupiah (Rp61 juta).
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
- Lintasan maju: A selesai hari ke-3, B ke-4. C mulai 3, selesai 5. D mulai , selesai 9. E mulai , selesai 12.
- Lintasan mundur dari 12: E paling lambat mulai 9, D mulai 4, C mulai 7, B mulai 0, A mulai 1.
- Slack: A = 1, B = 0, C = 4, D = 0, E = 0. Jalur kritis B–D–E dengan panjang .
Durasi minimum 12 hari dengan jalur kritis B–D–E.
Kesalahan yang sering terjadi
Coba sendiri
Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.
Pembahasan
, , , . Maksimum 24 di .
Tiga teknisi ditugaskan ke tiga lokasi, masing-masing satu. Biaya (ratus ribu rupiah):
| Teknisi | Lokasi 1 | Lokasi 2 | Lokasi 3 |
|---|---|---|---|
| A | 9 | 2 | 7 |
| B | 6 | 4 | 3 |
| C | 5 | 8 | 1 |
Pembahasan
Penugasan A ke lokasi 2, B ke lokasi 1, C ke lokasi 3 berbiaya . Dari keenam permutasi, nilai lainnya 10, 14, 16, 20, dan 21.
Pembahasan
E selesai dan F selesai . Durasi proyek 11 hari dengan jalur kritis A–D–F.
Kuis 5 soal
Kerjakan semua soal, lalu periksa sekaligus.
Pembahasan
Kolom dengan koefisien paling negatif memberi kenaikan per satuan terbesar. Rasio minimum dipakai untuk memilih variabel keluar.
Pembahasan
Benar, ini teorema dualitas kuat.
Pembahasan
Banyak variabel basis . Pilihan D adalah banyak seluruh sel.
Pembahasan
A, B, dan C adalah langkah baku pembentukan tabel. D salah karena rasio hanya untuk entri positif; E salah karena daerah layak bisa tak terbatas.
Pembahasan
, , , jadi dan .
Latihan tanpa batas
Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.
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
Pelajari dulu (prasyarat)
- Tidak ada prasyarat khusus.
Topik lanjutan
- Belum ada.
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.