PEMA4205 — Program Linear

1. Suatu sistem persamaan linear memiliki matriks augmented. Setelah dilakukan operasi baris elementer, diperoleh matriks eselon baris. Apa yang dimaksud dengan matriks eselon baris?

A. Matriks yang semua entri di bawah diagonal utama adalah nol
B. Matriks yang setiap barisnya memiliki leading 1 (pivot) dan entri di bawah pivot adalah nol
C. Matriks yang semua entri di atas dan di bawah diagonal utama adalah nol
D. Matriks yang hanya memiliki satu solusi

Jawaban: B. Matriks eselon baris memiliki ciri: setiap baris tidak nol dimulai dengan angka 1 (leading 1), dan entri di bawah leading 1 semuanya nol.

2. Dalam program linear, suatu titik disebut penyelesaian dasar layak (basic feasible solution) jika memenuhi kendala dan memiliki berapa variabel tak nol (basis)?

A. Sebanyak jumlah kendala
B. Sebanyak jumlah variabel total
C. Sebanyak jumlah variabel basis yang sama dengan jumlah kendala fungsional
D. Semua variabel harus tak nol

Jawaban: C. Penyelesaian dasar layak memiliki jumlah variabel basis (variabel tak nol) sama dengan jumlah kendala fungsional (tidak termasuk kendala non-negatif).

3. Dalam metode grafik untuk program linear dua variabel, daerah layak (feasible region) adalah:

A. Himpunan semua titik yang memenuhi fungsi tujuan
B. Himpunan semua titik yang memenuhi semua kendala termasuk kendala non-negatif
C. Himpunan semua titik yang memberikan nilai optimal
D. Himpunan semua titik yang tidak memenuhi kendala

Jawaban: B. Daerah layak merupakan irisan dari semua kendala (termasuk non-negatif) sehingga setiap titik di dalamnya memenuhi seluruh batasan masalah.

4. Operasi baris elementer yang digunakan dalam metode simplex untuk mempertukarkan variabel basis disebut:

A. Operasi pivot
B. Reduksi Gauss-Jordan
C. Eliminasi Gaussian
D. Metode Gauss-Seidel

Jawaban: A. Dalam simplex, operasi pivot dilakukan untuk mengganti satu variabel keluar dari basis dengan variabel masuk, dengan melakukan operasi baris elementer pada baris pivot.

5. Pada algoritma simplex baku, variabel yang dipilih untuk masuk ke basis adalah variabel nonbasis yang memiliki koefisien pada baris fungsi tujuan:

A. Positif terbesar (untuk masalah maksimasi)
B. Negatif terbesar (untuk masalah maksimasi)
C. Nol
D. Tidak bergantung tanda

Jawaban: B. Untuk masalah maksimasi, variabel dengan koefisien negatif terbesar dalam baris Z (paling negatif) dipilih masuk basis karena akan meningkatkan Z.

6. Dalam metode M (Charnes), artificial variable ditambahkan ke kendala untuk:

A. Mengubah pertidaksamaan menjadi persamaan
B. Mempercepat konvergensi
C. Mendapatkan penyelesaian dasar awal (basic feasible solution)
D. Mengubah fungsi tujuan menjadi nonlinear

Jawaban: C. Artificial variable ditambahkan untuk memberikan variabel basis awal yang memenuhi kendala, karena kendala dengan tanda ≥ atau = belum memiliki basis.

7. Metode simplex dua-fase digunakan ketika:

A. Semua kendala bertanda ≤
B. Terdapat kendala bertanda ≥ atau = tanpa variabel basis awal yang jelas
C. Jumlah variabel lebih banyak dari kendala
D. Fungsi tujuan adalah minimasi

Jawaban: B. Simplex dua-fase diperlukan jika tidak ada penyelesaian dasar layak awal yang jelas, biasanya karena adanya kendala ≥ atau = yang memerlukan artificial variable.

8. Masalah dual dari masalah primal (maksimasi, kendala ≤, variabel non-negatif) memiliki bentuk:

A. Maksimasi, kendala ≥, variabel non-negatif
B. Minimasi, kendala ≥, variabel non-negatif
C. Minimasi, kendala ≤, variabel bebas
D. Maksimasi, kendala =, variabel non-negatif

Jawaban: B. Aturan dual: primal maksimasi dengan kendala ≤ akan menjadi dual minimasi dengan kendala ≥, dan jumlah variabel dual sama dengan jumlah kendala primal.

9. Dalam simplex direvisi, matriks basis digunakan untuk memperbarui:

A. Hanya koefisien fungsi tujuan
B. Semua koefisien kendala dan fungsi tujuan
C. Hitung harga Dual (dual price) dan arah perbaikan tanpa memperbarui seluruh tabel
D. Hanya ruas kanan

Jawaban: C. Simplex direvisi menggunakan matriks basis untuk menghitung variabel dual dan menentukan entering variabel, sehingga lebih efisien karena tidak perlu memperbarui seluruh tabel.

10. Analisis sensitivitas dalam program linear mengkaji:

A. Perubahan solusi optimal jika koefisien fungsi tujuan atau ruas kanan berubah
B. Kecepatan algoritma
C. Banyaknya iterasi simplex
D. Struktur matriks kendala

Jawaban: A. Analisis sensitivitas mempelajari dampak perubahan parameter (misal harga, ketersediaan sumber daya) terhadap solusi optimal.

11. Dalam program integer, metode enumerasi implisit bekerja dengan cara:

A. Menyelesaikan secara grafis
B. Mengevaluasi semua kemungkinan solusi integer secara eksplisit
C. Mencari solusi optimal dengan menyaring cabang-cabang yang tidak layak secara implisit, tanpa mengevaluasi semua titik
D. Mengubah semua variabel menjadi kontinu

Jawaban: C. Enumerasi implisit mengeksplorasi ruang solusi secara sistematis dengan memangkas (pruning) cabang yang tidak mungkin menghasilkan solusi optimal.

12. Metode cabang dan batas (branch and bound) untuk program integer memecah masalah menjadi submasalah yang lebih kecil, lalu menghitung batas atas atau bawah. Proses pemecahan ini disebut:

A. Pemotongan (cutting)
B. Percabangan (branching)
C. Pemilihan (selection)
D. Relaksasi

Jawaban: B. Branching adalah proses membagi masalah menjadi dua submasalah atau lebih dengan memberikan batasan tambahan pada variabel.

13. Model transportasi bertujuan untuk:

A. Memaksimalkan jarak pengiriman
B. Meminimumkan biaya pengiriman atau memaksimumkan keuntungan dari sumber ke tujuan dengan memperhatikan kapasitas dan permintaan
C. Menentukan rute terpanjang
D. Mengoptimalisasi jumlah kendaraan

Jawaban: B. Model transportasi mengalokasikan produk dari sumber ke tujuan agar biaya total minimum atau keuntungan maksimum dengan kendala pasokan dan permintaan.

14. Dalam model transportasi, metode stepping stone digunakan untuk:

A. Menentukan solusi awal
B. Mengevaluasi dan memperbaiki solusi yang ada dengan mencari sel nonbasis yang dapat mengurangi biaya
C. Menentukan biaya transportasi
D. Menyeimbangkan pasokan dan permintaan

Jawaban: B. Metode stepping stone mengevaluasi sel nonbasis dengan membentuk jalur tertutup untuk menghitung perubahan biaya dan menentukan apakah solusi masih bisa diperbaiki.

15. Masalah penugasan adalah kasus khusus dari:

A. Program linear integer
B. Model transportasi dengan jumlah pekerja dan tugas sama, dan setiap pekerja hanya mendapat satu tugas
C. Program nonlinear
D. Masalah dual

Jawaban: B. Masalah penugasan merupakan bentuk khusus dari model transportasi di mana setiap sumber (pekerja) memiliki pasokan 1 dan setiap tujuan (tugas) memiliki permintaan 1, sehingga biaya total diminimalkan.

16. Metode Hungaria digunakan untuk menyelesaikan masalah penugasan dengan langkah awal:

A. Menjumlahkan semua biaya
B. Mengurangkan biaya terkecil pada setiap baris dan kemudian setiap kolom dari seluruh biaya
C. Membagi semua biaya dengan jumlah pekerja
D. Mengalikan biaya dengan faktor konstanta

Jawaban: B. Langkah pertama Metode Hungaria adalah mengurangi setiap biaya pada baris dengan biaya terkecil di baris tersebut, lalu melakukan hal yang sama pada setiap kolom.

17. Perangkat lunak solver (seperti Solver Excel) digunakan untuk:

A. Menggambar grafik program linear
B. Menghitung nilai optimal program linear dan melakukan analisis sensitivitas secara numerik
C. Menulis kode program
D. Membuat tabel simplex secara manual

Jawaban: B. Solver merupakan alat bantu komputasi untuk menemukan solusi optimal berbagai model termasuk linear programming, serta menyediakan laporan analisis sensitivitas.

18. Diberikan matriks A = [[1,2],[3,4]] dan B = [[5,6],[7,8]]. Hasil dari A + B adalah …

A. [[6,8],[10,12]]
B. [[5,12],[21,32]]
C. [[6,9],[11,13]]
D. [[4,6],[10,12]]

Jawaban: A. Penjumlahan matriks dilakukan dengan menjumlahkan elemen yang seletak: (1+5)=6, (2+6)=8, (3+7)=10, (4+8)=12 sehingga hasilnya adalah [[6,8],[10,12]].

19. Suatu sistem pertidaksamaan linear memiliki penyelesaian dasar layak jika …

A. semua variabelnya berharga nol
B. semua titik potong memenuhi kendala nonnegatif
C. matriks kendala berbentuk persegi
D. fungsi tujuan bernilai maksimum

Jawaban: B. Penyelesaian dasar layak adalah solusi dari sistem persamaan linear yang memenuhi kendala nonnegatif, artinya semua titik potong yang menjadi basis harus berada di daerah layak.

20. Dalam metode grafik, daerah yang memenuhi semua kendala disebut …

A. daerah basis
B. daerah layak
C. daerah simplex
D. daerah dual

Jawaban: B. Daerah layak (feasible region) adalah himpunan semua titik yang memenuhi seluruh kendala, termasuk kendala nonnegatif.

21. Operasi baris elementer yang digunakan dalam metode pivot bertujuan untuk …

A. menambah jumlah variabel
B. membuat elemen pivot menjadi 1 dan elemen lain di kolom pivot menjadi 0
C. mengubah fungsi tujuan menjadi minimum
D. menghilangkan kendala nonnegatif

Jawaban: B. Dalam metode pivot, operasi baris elementer dilakukan untuk mengubah elemen pivot menjadi 1 dan elemen lainnya di kolom pivot menjadi 0, sehingga diperoleh solusi basis baru.

22. Bentuk baku algoritma simplex mensyaratkan bahwa …

A. semua kendala berupa pertidaksamaan ≤
B. semua variabel harus nonnegatif dan fungsi tujuan dimaksimumkan
C. semua kendala berupa persamaan dan variabel bebas
D. fungsi tujuan harus diminimumkan

Jawaban: B. Bentuk baku simplex mensyaratkan semua variabel nonnegatif, fungsi tujuan dimaksimumkan (atau diminimumkan dengan tanda yang sesuai), dan kendala berupa persamaan dengan variabel slack.

23. Metode M (Big M) Charnes digunakan untuk menangani program linear yang memiliki …

A. variabel slack
B. kendala dengan tanda = atau ≥
C. hanya dua variabel
D. fungsi tujuan nonlinear

Jawaban: B. Metode M digunakan ketika terdapat kendala dengan tanda = atau ≥, yang memerlukan penambahan variabel buatan (artificial variable) dengan koefisien penalty M pada fungsi tujuan.

24. Dalam metode simplex dua fase, fase pertama bertujuan untuk …

A. memaksimumkan fungsi tujuan asli
B. menghilangkan variabel buatan dengan meminimumkan jumlahnya
C. menentukan solusi dual
D. mengubah kendala menjadi pertidaksamaan

Jawaban: B. Fase pertama dari metode dua fase bertujuan untuk meminimumkan jumlah variabel buatan, sehingga diperoleh solusi basis layak awal tanpa variabel buatan.

25. Masalah dual dari program linear primal yang memaksimumkan Z = 3×1 + 2×2 dengan kendala x1 + x2 ≤ 4, 2×1 + x2 ≤ 6, x1,x2 ≥ 0 adalah …

A. meminimumkan W = 4y1 + 6y2 dengan kendala y1 + 2y2 ≥ 3, y1 + y2 ≥ 2, y1,y2 ≥ 0
B. meminimumkan W = 3y1 + 2y2 dengan kendala y1 + y2 ≤ 4, y1 + y2 ≤ 6
C. memaksimumkan W = 4y1 + 6y2 dengan kendala y1 + 2y2 ≤ 3
D. memaksimumkan W = 3y1 + 2y2 dengan kendala y1 + y2 ≥ 4

Jawaban: A. Dual dari masalah maksimasi dengan kendala ≤ adalah masalah minimasi dengan kendala ≥. Koefisien fungsi tujuan primal menjadi ruas kanan dual, dan sebaliknya.

26. Dalam simplex direvisi, invers matriks basis digunakan untuk …

A. menentukan koefisien fungsi tujuan
B. memperbaharui solusi dengan cepat tanpa mengulang seluruh tabel
C. menambah variabel baru
D. mengubah tanda kendala

Jawaban: B. Simplex direvisi menggunakan invers matriks basis untuk memperbaharui solusi secara efisien, sehingga tidak perlu menghitung ulang seluruh tabel simplex.

27. Analisis sensitivitas pada program linear bertujuan untuk …

A. menentukan solusi optimal baru jika terjadi perubahan pada koefisien fungsi tujuan atau ruas kanan kendala
B. menghitung nilai fungsi tujuan
C. mengubah variabel keputusan
D. menambah jumlah kendala

Jawaban: A. Analisis sensitivitas mempelajari dampak perubahan parameter (seperti koefisien fungsi tujuan atau konstanta ruas kanan) terhadap solusi optimal tanpa menyelesaikan masalah dari awal.

28. Metode enumerasi implisit digunakan untuk menyelesaikan masalah program integer dengan …

A. mengevaluasi semua kemungkinan solusi secara eksplisit
B. menelusuri cabang-cabang solusi yang layak secara sistematis dan mengeliminasi yang tidak optimal
C. mengubah variabel integer menjadi kontinu
D. menggunakan metode grafik

Jawaban: B. Enumerasi implisit adalah metode yang mengevaluasi solusi secara sistematis dengan memangkas cabang-cabang yang tidak menghasilkan solusi optimal, sehingga tidak perlu mengevaluasi semua kemungkinan.

29. Dalam metode cabang dan batas (branch and bound), langkah 'branching' berarti …

A. menentukan batas atas dan bawah solusi
B. memecah masalah menjadi submasalah dengan menambahkan kendala baru pada variabel integer
C. menyelesaikan relaksasi linear
D. menghentikan pencarian jika solusi ditemukan

Jawaban: B. Branching adalah proses memecah masalah menjadi submasalah dengan menambahkan kendala (misalnya x ≤ a atau x ≥ a+1) pada variabel yang belum integer, sehingga membentuk cabang-cabang pencarian.

30. Model transportasi bertujuan untuk …

A. memaksimumkan total biaya pengiriman
B. mendistribusikan barang dari sumber ke tujuan dengan biaya minimum
C. menentukan jumlah produksi
D. mengalokasikan tenaga kerja

Jawaban: B. Model transportasi adalah model program linear yang bertujuan mendistribusikan barang dari beberapa sumber ke beberapa tujuan dengan biaya total minimum, memenuhi penawaran dan permintaan.

31. Metode sudut barat laut (Northwest Corner) dalam model transportasi digunakan untuk …

A. mencari solusi optimal
B. menentukan solusi awal layak
C. menghitung biaya transportasi
D. mengurangi kapasitas sumber

Jawaban: B. Metode sudut barat laut adalah salah satu metode untuk mendapatkan solusi awal layak pada masalah transportasi dengan mengalokasikan barang mulai dari pojok kiri atas tabel.

32. Dalam metode Hungarian, langkah pertama yang dilakukan adalah …

A. membentuk matriks biaya
B. mengurangkan setiap baris dengan elemen terkecil di baris tersebut
C. menandai semua baris yang tidak memiliki nol
D. menentukan alokasi optimal

Jawaban: B. Langkah pertama metode Hungarian adalah mengurangi setiap elemen dalam baris dengan nilai terkecil pada baris tersebut, sehingga setiap baris memiliki minimal satu nilai nol.

33. Jika suatu masalah penugasan diselesaikan dengan metode transportasi, maka …

A. kapasitas setiap sumber dan permintaan setiap tujuan harus sama dengan 1
B. jumlah sumber dan tujuan harus berbeda
C. biaya harus berupa bilangan bulat
D. tidak perlu memenuhi kendala nonnegatif

Jawaban: A. Masalah penugasan merupakan kasus khusus transportasi di mana setiap sumber (pekerja) memiliki kapasitas 1 dan setiap tujuan (tugas) memiliki permintaan 1.

34. Perangkat lunak solver dalam program linear dapat digunakan untuk …

A. hanya menghitung matriks
B. menentukan nilai optimal program linear dan analisis sensitivitas
C. menggambar grafik saja
D. menyelesaikan persamaan nonlinear

Jawaban: B. Solver adalah perangkat lunak yang dapat menentukan solusi optimal dari masalah program linear serta melakukan analisis sensitivitas terhadap perubahan parameter.

35. Matriks A memiliki ordo 3×4, dan matriks B berordo 4×5. Perkalian matriks A x B menghasilkan matriks dengan ordo…

A. 3×4
B. 4×5
C. 3×5
D. 5×3

Jawaban: C. Ordo hasil perkalian matriks (m x n) dengan (n x p) adalah m x p, jadi 3 x 5.

36. Suatu sistem pertidaksamaan linear memiliki daerah layak yang berbentuk poligon tertutup. Penyelesaian dasar layak dari sistem tersebut terdapat pada…

A. Pusat poligon
B. Titik-titik sudut poligon
C. Sisi-sisi poligon
D. Daerah di luar poligon

Jawaban: B. Penyelesaian dasar layak dari sistem pertidaksamaan linear selalu terletak pada titik-titik sudut daerah layak.

37. Dalam metode grafik untuk memaksimumkan fungsi tujuan Z = 3x + 2y dengan kendala x + y ≤ 4, x ≥ 0, y ≥ 0, jika titik pojok yang dievaluasi adalah (0,4), (4,0), dan (2,2), maka nilai Z maksimum adalah…

A. 8
B. 10
C. 12
D. 6

Jawaban: C. Evaluasi: Z(0,4)=8, Z(4,0)=12, Z(2,2)=10. Nilai maksimum adalah 12 pada titik (4,0).

38. Operasi baris elementer (OBE) pada matriks yang bertujuan untuk membuat elemen pivot menjadi 1 dan elemen lain pada kolom pivot menjadi 0 disebut…

A. Operasi penjumlahan baris
B. Operasi perkalian baris dengan skalar
C. Operasi pivot
D. Operasi determinan

Jawaban: C. Operasi pivot dalam OBE digunakan untuk mengubah matriks sehingga elemen pivot bernilai 1 dan elemen lain di kolomnya bernilai 0.

39. Dalam algoritma simpleks baku, jika pada tabel simpleks terdapat baris fungsi tujuan yang semua koefisien variabel nonbasanya bernilai nonpositif, maka…

A. Solusi belum optimal, perlu iterasi
B. Solusi sudah optimal
C. Tidak ada solusi layak
D. Masalah memiliki solusi tak terbatas

Jawaban: B. Kondisi optimal dalam simpleks baku adalah ketika semua koefisien pada baris fungsi tujuan untuk variabel nonbasa ≤ 0.

40. Metode M Charnes digunakan untuk menyelesaikan masalah program linear yang memiliki kendala bertipe…

A. ≤
B. =
C. ≥
D. Semua jenis kendala

Jawaban: C. Metode M Charnes (metode big M) khusus digunakan untuk menangani kendala bertipe ≥ atau = yang memerlukan variabel buatan.

41. Dalam metode simpleks dua fase, fase pertama bertujuan untuk…

A. Mencari solusi optimal
B. Menghilangkan variabel buatan dan mendapatkan solusi layak awal
C. Menganalisis sensitivitas
D. Menentukan dualitas

Jawaban: B. Fase pertama simpleks dua fase berfokus pada eliminasi variabel buatan untuk memperoleh solusi layak awal.

42. Jika primal masalah program linear adalah maksimasi dengan kendala ≤, maka dualnya adalah…

A. Maksimasi dengan kendala ≥
B. Minimasi dengan kendala ≥
C. Minimasi dengan kendala ≤
D. Maksimasi dengan kendala =

Jawaban: B. Primal maksimasi dengan kendala ≤ memiliki dual minimasi dengan kendala ≥.

43. Dalam simpleks direvisi, invers dari matriks basis digunakan untuk…

A. Menambah jumlah iterasi
B. Menentukan koefisien baris tujuan
C. Menyederhanakan perhitungan dengan hanya memperbarui matriks yang diperlukan
D. Membentuk tabel simpleks lengkap

Jawaban: C. Simpleks direvisi menggunakan invers matriks basis untuk memperbarui informasi secara efisien tanpa menghitung ulang seluruh tabel.

44. Analisis sensitivitas dalam program linear bertujuan untuk…

A. Mengubah fungsi tujuan
B. Melihat pengaruh perubahan parameter terhadap solusi optimal
C. Menghilangkan kendala
D. Menambah variabel baru

Jawaban: B. Analisis sensitivitas mempelajari dampak perubahan parameter (koefisien fungsi tujuan atau kendala) terhadap solusi optimal yang diperoleh.

45. Dalam metode enumerasi implisit untuk program integer, langkah yang dilakukan untuk mengevaluasi solusi adalah dengan…

A. Mencoba semua kemungkinan kombinasi
B. Menggunakan pohon pencarian dan memangkas cabang yang tidak layak
C. Mengubah variabel kontinu menjadi integer
D. Menggunakan metode grafik

Jawaban: B. Enumerasi implisit menggunakan pohon pencarian dengan pemangkasan (branch and bound) untuk mengurangi jumlah solusi yang dievaluasi.

46. Metode cabang dan batas (branch and bound) digunakan untuk menyelesaikan masalah program linear yang…

A. Memiliki kendala nonlinear
B. Variabelnya harus berupa bilangan bulat
C. Fungsi tujuannya linear
D. Semua jawaban salah

Jawaban: B. Metode branch and bound khusus digunakan untuk masalah program integer, di mana variabel keputusan harus berupa bilangan bulat.

47. Dalam model transportasi, jika total penawaran sama dengan total permintaan, maka masalah tersebut disebut…

A. Transportasi tidak seimbang
B. Transportasi seimbang
C. Transshipment
D. Masalah degenerasi

Jawaban: B. Masalah transportasi dikatakan seimbang jika jumlah total penawaran dari semua sumber sama dengan jumlah total permintaan dari semua tujuan.

48. Metode stepping stone dalam transportasi digunakan untuk…

A. Menentukan solusi awal
B. Menguji optimalitas dan memperbaiki solusi
C. Mengubah biaya transportasi
D. Menghitung jumlah barang yang dikirim

Jawaban: B. Metode stepping stone digunakan untuk mengevaluasi apakah solusi transportasi sudah optimal dan jika belum, memperbaikinya dengan jalur batu loncatan.

49. Dalam masalah penugasan dengan metode Hungaria, langkah pertama yang harus dilakukan adalah…

A. Mengurangkan biaya terkecil pada setiap baris
B. Mengurangkan biaya terkecil pada setiap kolom
C. Menjumlahkan semua biaya
D. Membuat tabel biaya baru

Jawaban: A. Metode Hungaria dimulai dengan mengurangi setiap elemen dalam baris dengan nilai minimum baris tersebut.

50. Dalam perangkat lunak solver, analisis sensitivitas dapat dilakukan untuk mengetahui…

A. Nilai variabel keputusan
B. Bayangan harga (shadow price) dan rentang koefisien fungsi tujuan
C. Solusi optimal tunggal
D. Semua jawaban benar

Jawaban: B. Solver menyediakan analisis sensitivitas yang mencakup shadow price (harga bayangan) dan rentang perubahan koefisien fungsi tujuan yang tidak mengubah solusi optimal.

PEMA4205 — Program Linear

Latihan Tambahan dengan AI