40 Soal UT EKMA4413 Riset Operasi (Edisi 2) Lengkap dengan Kunci Jawaban dan Pembahasan Terbaru

40 soal pilihan ganda untuk UT EKMA4413 – Riset Operasi (Edisi 2) lengkap dengan kunci jawaban dan pembahasan.

Soal 1–10: Pemrograman Linear & Simplex

1. Sebuah pabrik membuat produk A dan B. Keuntungan per unit A = 50, B = 40. Waktu mesin terbatas 100 jam; A membutuhkan 2 jam/unit; B membutuhkan 1 jam/unit. Bahan terbatas 80 unit; A membutuhkan 1 bahan/unit; B membutuhkan 0.5 bahan/unit. Model LP untuk memaksimalkan keuntungan:
   A. Max Z = 50x1 + 40x2 s.t. 2x1 + x2 ≤ 100; x1 + 0.5x2 ≤ 80; x1,x2 ≥ 0
   B. Max Z = 50x1 + 40x2 s.t. 2x1 + x2 ≥ 100; x1 + 0.5x2 ≤ 80; x1,x2 ≥ 0
   C. Max Z = 50x1 + 40x2 s.t. 2x1 + x2 ≤ 100; x1 + 0.5x2 ≥ 80; x1,x2 ≥ 0
   D. Max Z = 50x1 + 40x2 s.t. 2x1 + x2 ≤ 100; x1 + 0.5x2 ≤ 80; x1,x2 ≤ 0
   Jawaban: A
   Pembahasan: Tuliskan fungsi objektif sesuai keuntungan dan kendala waktu/bahan dengan tanda ≤ karena sumber terbatas; variabel nonnegatif.

2. Untuk soal (1), titik asal (0,0) dan titik potong kendala (2x1 + x2 =100) dengan x2=0 memberi (50,0) ? Pilih yang benar:
   A. (50,0) feasible
   B. (100,0) feasible
   C. (40,20) feasible
   D. (0,100) feasible
   Jawaban: C (40,20) adalah titik pada 2x1 + x2 = 100 yang juga memenuhi bahan.
   Pembahasan (aritmetik): Jika x1=40,x2=20 → 2·40 + 20 = 80+20 = 100 (memenuhi waktu). Cek bahan: x1 + 0.5x2 = 40 + 0.5·20 = 40 + 10 = 50 ≤ 80 → feasible. (50,0) bukan solusi karena x1=50 → 2·50=100 waktu terpenuhi, bahan = 50 > 80? Bahan = 50 ≤80 so (50,0) juga feasible; tapi (50,0) tidak ada di pilihan.

3. Dalam metode Simplex maksimum (konvensi cj − zj dipakai), variabel entering dipilih sebagai:
   A. Paling positif (cj − zj)
   B. Paling negatif (cj − zj)
   C. Baris dimana rasio minimum terjadi
   D. Variabel slack terbesar
   Jawaban: B
   Pembahasan: Untuk masalah maximization, kolom dengan reduced cost (cj − zj) paling negatif menunjukkan peningkatan Z terbesar jika variabel masuk basis (konvensi ini umum saat menggunakan cj − zj); setelah memilih entering, gunakan aturan rasio minimum untuk menentukan leaving.

4. LP: Max Z = 3x1 + 2x2 s.t. x1 + 2x2 ≤ 8; 3x1 + 2x2 ≤ 12; x1,x2 ≥ 0. Titik optimal (nilai Z maksimum) adalah:
   A. Zmax = 24 di (8,0)
   B. Zmax = 12 di (2,3) dan (4,0) (multiple optimum)
   C. Zmax = 14 di (2,4)
   D. Zmax = 20 di (0,10)
   Jawaban: B
   Pembahasan (langkah): Hitung pojok feasible: (0,0):Z=0; (8,0) feasibility? cek kedua: 3·8 + 2·0 =24 ≤12? Salah → (8,0) tidak feasible. Sisi x2=0 → batas x1 ≤4 (dari 3x1 ≤12) → (4,0): Z=3·4=12. Intersection kedua kendala: solve x1+2x2=8 and 3x1+2x2=12 → subtract →2x1=4 → x1=2 → x2=3 → Z=3·2+2·3=6+6=12. Jadi dua titik (2,3) dan (4,0) memberi Z=12 (multiple optimum).

5. Pernyataan: “Jika semua reduced costs ≥ 0 di tabel simplex untuk problem maximization, maka solusi saat ini optimum.” Pilih:
   A. Benar
   B. Salah
   Jawaban: A
   Pembahasan: Untuk maximization, kondisi optimal adalah tidak ada reduced cost negatif (menggunakan konvensi cj − zj), sehingga tidak ada variable nonbasis yang dapat meningkatkan Z.

6. Dalam metode Two-Phase untuk masalah dengan kendala = dan ≥, tujuan fase pertama adalah:
   A. Maksimumkan fungsi objektif asli langsung
   B. Menemukan solusi dasar feasible awal (mengeliminasi variabel artifisial)
   C. Menggunakan metode grafis
   D. Menentukan sensitivitas harga bayangan
   Jawaban: B
   Pembahasan: Fase I meminimumkan jumlah variabel artifisial untuk menemukan feasible basis awal; setelah artifisial dihapus, lanjut ke Fase II untuk optimasi fungsi asli.

7. Pada LP terikat (binding constraint), nilai slack = …
   A. Positif
   B. 0
   C. Negatif
   D. Bisa negatif atau positif
   Jawaban: B
   Pembahasan: Kendala yang mengikat berarti batas tercapai → RHS − LHS = 0 → slack = 0.

8. Jika sebuah variabel memiliki nilai bayangan (shadow price) positif untuk kendala sumber, artinya:
   A. Menambah 1 unit sumber akan menurunkan Z optimum
   B. Menambah 1 unit sumber akan meningkatkan Z optimum sebesar nilai bayangan (selama rentang kepekaan)
   C. Kendala tidak berpengaruh
   D. Model infeasible
   Jawaban: B
   Pembahasan: Shadow price menunjukkan perubahan marjinal pada nilai objektif per unit peningkatan RHS untuk kendala, selama dalam rentang validitas.

9. Dalam analisis sensitivitas, rentang keefektifan koefisien tujuan (allowable increase/decrease) memberi tahu:
   A. Berapa banyak RHS berubah sebelum solusi berubah
   B. Berapa banyak koefisien tujuan dapat berubah tanpa mengubah basis optimal
   C. Berapa banyak variabel bisa ditambahkan
   D. Tidak ada kegunaan praktis
   Jawaban: B
   Pembahasan: Rentang allowable pada koefisien tujuan menunjukkan perubahan yang bisa terjadi pada koefisien tanpa merubah basis optimal (tetap pada variabel yang sama mendasar).

10. Solusi degenerasi pada simplex terjadi bila:
    A. Semua slack > 0
    B. Sebuah basic variable = 0
    C. Semua reduced costs negatif
    D. Problem unbounded
    Jawaban: B
    Pembahasan: Degenerasi: ada basic variable yang bernilai nol → dapat menyebabkan pivot siklik jika tidak hati-hati.

---

Soal 11–18: Transportasi & Assignment

11. Masalah transportasi dasar: empat gudang (supply: 20, 30, 25, 25) dan tiga pelanggan (demand: 40, 35, 25). Total supply=100 dan demand=100. Sebuah solusi dasar feasible memiliki berapa dasar variabel bebas?
    A. 7
    B. 9
    C. 6
    D. 8
    Jawaban: A (m + n − 1 = 4 + 3 − 1 = 6? Wait kalkulasi.)
    Pembahasan: Rumus jumlah basic variable untuk solusi dasar nondegenerate = m + n − 1. m=4, n=3 → 4+3−1 = 6. Jadi jawaban yang benar adalah C (6). (Perbaikan: pilih C.)

12. Metode Northwest Corner memberi:
    A. Solusi optimal langsung
    B. Solusi dasar feasible awal (membutuhkan uji optimalitas seperti MODI)
    C. Selalu minimalkan biaya
    D. Hanya untuk balanced problems dengan m=n
    Jawaban: B
    Pembahasan: Northwest Corner hanya memberi solusi awal feasible; perlu diperiksa & ditingkatkan menggunakan MODI atau Stepping Stone.

13. Untuk problem assignment 3×3, Hungarian method menjamin:
    A. Solusi optimal dalam polinomial waktu (deterministik)
    B. Hanya solusi heuristik
    C. Memerlukan LP relaxation untuk optimalitas
    D. Tidak bekerja untuk cost matrix bukan persegi
    Jawaban: A
    Pembahasan: Hungarian method menyelesaikan masalah assignment (square cost matrix) secara exact dalam waktu polinomial O(n^3).

14. Dalam uji optimalitas MODI untuk transportasi, nilai opportunity cost negatif pada sel nonbasic artinya:
    A. Tidak perlu perbaikan
    B. Mengindikasikan solusi dapat diperbaiki (ada pengurangan biaya)
    C. Masalah infeasible
    D. Harus menambah variable artifisial
    Jawaban: B
    Pembahasan: Opportunity cost (reduced cost) negatif menunjukkan memasukkan alokasi di sel tersebut menurunkan total biaya → solusi belum optimal.

15. Masalah transportasi: jika total supply ≠ total demand, langkah praktis adalah:
    A. Menolak masalah
    B. Menambahkan dummy supply atau dummy demand sehingga balance
    C. Kurangi demand terbesar
    D. Gunakan Hungarian method
    Jawaban: B
    Pembahasan: Menambahkan baris/kolom dummy untuk menyeimbangkan total.

16. Dalam assignment dengan biaya (time) matrix, tujuan biasanya:
    A. Maksimalkan total waktu
    B. Minimalkan total biaya/waktu
    C. Hanya mencari feasible matching
    D. Maksimalkan jumlah tugas terselesaikan tanpa biaya
    Jawaban: B

17. Definisi degenerasi di transportasi terjadi bila:
    A. Ada lebih banyak basic variable daripada m+n−1
    B. Ada kurang dari m+n−1 basis positif (beberapa basic variable bernilai nol)
    C. Semua dasar variabel > 0
    D. Masalah unbalanced
    Jawaban: B

18. Metode Vogel’s Approximation Method (VAM) menghasilkan:
    A. Solusi awal feasible lebih baik rata-rata daripada Northwest Corner atau Least Cost
    B. Solusi optimal selalu
    C. Solusi infeasible untuk balanced problem
    D. Hanya digunakan kalau cost negatif
    Jawaban: A
    Pembahasan: VAM adalah heuristic yang sering memberikan solusi awal dengan biaya lebih rendah dibanding NW Corner.

---

Soal 19–25: Jaringan (Shortest Path, MST, Max Flow, Minimum Cut)

19. Pada graf berarah berberat nonnegatif, algoritma Dijkstra digunakan untuk:
    A. Menemukan minimum spanning tree
    B. Menemukan shortest path single-source ke semua simpul
    C. Menyelesaikan max flow
    D. Menemukan minimum matching
    Jawaban: B

20. Pada graf tak berarah, algoritma Kruskal menghasilkan:
    A. Shortest path dari satu sumber
    B. Minimum spanning tree (MST)
    C. Max flow
    D. Semua sisi dengan bobot minimal
    Jawaban: B

21. Untuk masalah max flow, teorema Max-Flow Min-Cut menyatakan:
    A. Nilai maksimum aliran ≤ kapasitas minimum cut
    B. Nilai maksimum aliran sama dengan kapasitas minimum cut (maksimal = minimal)
    C. Aliran maksimum tidak berkaitan dengan cut
    D. Cut selalu lebih besar dua kali aliran
    Jawaban: B

22. Dalam algoritma Edmonds-Karp (BFS augmenting path), kompleksitas waktu untuk graf dengan V simpul dan E sisi adalah kira-kira:
    A. O(V + E)
    B. O(E^2 V)
    C. O(VE^2)
    D. O(E log V)
    Jawaban: C (O(V E^2) — variasi umum)
    Pembahasan: Edmonds-Karp adalah implementasi Ford-Fulkerson dengan BFS yang memberi bound O(V E^2).

23. Shortest path pada graf berikut (arah & bobot nonnegatif): dari A ke D melalui A→B (2), B→C (3), A→C (6), C→D (1). Jarak terpendek A→D adalah:
    A. 6
    B. 7
    C. 5
    D. 4
    Jawaban: B (A→B→C→D = 2+3+1 = 6? Wait)
    Pembahasan: Hitung jalur: A→B→C→D = 2 + 3 + 1 = 6; A→C→D = 6 + 1 = 7; A→B and B→? check; sehingga jarak terpendek = 6. Jadi jawaban A (6). (Perbaikan pilih A.)

24. Dalam MST dengan Prim, jika graf terhubung memiliki n simpul, MST memiliki berapa sisi?
    A. n
    B. n − 1
    C. n + 1
    D. 2n
    Jawaban: B

25. Pada network flow, residual capacity c_f(u,v) = …
    A. c(u,v) + flow(u,v)
    B. c(u,v) − flow(u,v) untuk arah maju, dan flow(u,v) untuk arah balik
    C. flow(u,v) − c(u,v)
    D. Selalu nol
    Jawaban: B

---

Soal 26–30: PERT/CPM & Scheduling

26. Dalam CPM, critical path adalah:
    A. Path dengan jumlah durasi minimum
    B. Path dengan jumlah durasi maksimum (menentukan makespan)
    C. Path yang memiliki slack positif
    D. Path yang dapat diparalelkan
    Jawaban: B

27. Jika pada PERT waktu aktivitas acak dengan distribusi beta, expected time (te) dihitung sebagai:
    A. (a + b + c)/3
    B. (a + 4m + b)/6
    C. (a + b)/2
    D. (m + b)/2
    Jawaban: B
    Pembahasan: Dalam notasi PERT: pessimistic b, optimistic a, most likely m → te = (a + 4m + b)/6.

28. Dalam CPM, float (slack) suatu aktivitas = …
    A. LS − ES atau LF − EF
    B. ES + EF
    C. LS + LF
    D. LF − EF − LS
    Jawaban: A

29. Dalam scheduling single machine dengan objective minimalkan makespan dan job independent (tak ada release time), algoritma optimal adalah:
    A. Shortest Processing Time first (SPT)
    B. Longest Processing Time first (LPT)
    C. FCFS
    D. Tidak relevan — semua urutan sama makespan
    Jawaban: D untuk single machine makespan (Cmax) total processing time tetap sama jadi urutan tidak mempengaruhi makespan.
    Pembahasan: Untuk satu mesin nonpreemptive, makespan = sum p_i (tetap). Namun urutan mempengaruhi lateness/tardiness, tapi bukan makespan.

30. Jika ada dua jalur kritis yang keduanya menentukan durasi proyek, maka:
    A. Proyek pasti selesai lebih cepat
    B. Proyek tidak punya slack sama sekali pada aktivitas di kedua jalur
    C. Salah satu jalur pasti mempunyai slack positif
    D. Ini tidak mempengaruhi sensitivity
    Jawaban: B
    Pembahasan: Aktivitas pada jalur kritis slack = 0; jika dua jalur kritis, aktivitas pada keduanya tidak punya slack → lebih sensitif terhadap penundaan.

---

Soal 31–34: Antrian (Queueing)

31. Model M/M/1 dengan arrival rate λ dan service rate μ, kondisi kestabilan mensyaratkan:
    A. λ > μ
    B. λ < μ
    C. λ = μ
    D. λ ≤ 0
    Jawaban: B
    Pembahasan: Untuk steady state, server utilization ρ = λ/μ < 1 → λ < μ.

32. Untuk M/M/1, rata-rata jumlah pelanggan pada sistem L = ρ / (1 − ρ). Jika λ = 2 per jam dan μ = 5 per jam, L = ?
    A. 0.4
    B. 0.5
    C. 0.666...
    D. 0.666? Compute: ρ = 2/5 = 0.4 → L = 0.4/(1−0.4)=0.4/0.6=2/3 ≈ 0.6667
    Jawaban: C (2/3 ≈ 0.6667)

33. Untuk M/M/1, rata-rata waktu di sistem W = 1 / (μ − λ). Dengan λ=2, μ=5 → W = 1/(5−2) = 1/3 jam = 20 menit. Pilih jawaban:
    A. 1/3 jam (20 menit)
    B. 1/5 jam
    C. 2/3 jam
    D. 1 jam
    Jawaban: A

34. Model M/M/c (c server). Utilization per server ρ = λ/(c μ). Untuk c besar sehingga ρ<1, sistem stabil. Jika λ=10, μ=4, c minimal agar ρ<1?
    A. c≥3 → ρ=10/(3·4)=10/12≈0.833 <1 OK
    B. c=2 → ρ=10/8=1.25 >1 not OK
    C. c=4 → ρ=10/16=0.625 <1 juga OK
    Pilih minimal c:
    Jawaban: A (c=3)

---

Soal 35–40: Inventori, Pemrograman Integer, Simulasi, Dinamik

35. EOQ (Economic Order Quantity) rumus klasik: Q* = sqrt( (2·D·S) / H ) dimana D=permintaan tahunan, S=setup/order cost per order, H=holding cost per unit per tahun. Jika D=10.000 unit, S=50, H=2 → Q* = ?
    Perhitungan: numerator 2·D·S = 2·10.000·50 = 1.000.000. Dibagi H=2 → 500.000. Akar kuadrat sqrt(500.000) ≈ 707.1068.
    A. ≈ 707
    B. ≈ 1000
    C. ≈ 500
    D. ≈ 1414
    Jawaban: A (≈707)
    Pembahasan (digit by digit): 2×10000×50 = 1,000,000; /2 = 500,000; sqrt(500,000) ≈ 707.1068.

36. Dalam pemrograman integer, jika semua variabel harus bernilai integer dan LP relaxation menghasilkan fractional, pendekatan umum adalah:
    A. Menggunakan Branch and Bound atau Branch and Cut
    B. Abaikan integrality
    C. Always rounding up gives optimal
    D. Gunakan simplex biasa dan selesai
    Jawaban: A

37. Dalam metode Monte Carlo simulasi, untuk memperkecil error estimasi sample mean, Anda dapat:
    A. Mengurangi jumlah sampel
    B. Menambah jumlah sampel (n) — error standar turun sebanding 1/√n
    C. Memperbesar varians input
    D. Mengubah seed RNG tapi bukan meningkatkan n
    Jawaban: B

38. Dynamic programming sering dipakai untuk masalah knapsack 0-1. Sifat optimal substructure berarti:
    A. Optimal solusi untuk masalah besar mengandung optimal solusi untuk submasalahnya
    B. Selalu ada greedy solution optimal
    C. Tidak perlu penyimpanan intermediate
    D. Hanya berlaku untuk problem linear
    Jawaban: A

39. Sebuah integer programming: minimize Z = 5x1 + 3x2 s.t. x1 + x2 ≥ 4, x1,x2 ∈ {0,1,2,...}. Solusi integer optimum adalah:
    A. x1=4,x2=0 → Z=20
    B. x1=0,x2=4 → Z=12
    C. x1=2,x2=2 → Z=16
    D. x1=3,x2=1 → Z=18
    Jawaban: C? Let's compute: feasible minima with nonneg integers and x1+x2 ≥4; minimize 5x1+3x2 — cheaper to use x2 (coeff 3) than x1 (5). So best is x1=0,x2=4 → Z=12 (B).
    Pembahasan: All combos: (0,4):12 (optimal), (1,3):5+9=14, (2,2):10+6=16, (3,1)=15+3=18, (4,0)=20. Jadi B.

40. Problema: Anda ingin memodelkan stok persediaan dengan permintaan stok Poisson λ per hari dan review continuous (s, S). Keuntungan penggunaan simulasi dibandingkan analitis mencakup:
    A. Kemampuan menangani asumsi distribusi/perilaku kompleks yang sulit dianalisis secara tertutup
    B. Memberikan formula eksak selalu
    C. Selalu lebih cepat daripada metode analitis
    D. Tidak pernah membutuhkan verifikasi statistik
    Jawaban: A
    Pembahasan: Simulasi fleksibel untuk model kompleks; tidak selalu memberikan formula eksak dan memerlukan verifikasi & jumlah sampel adekuat.