MATA4230 — Pemrograman Linear

1. Sebuah perusahaan memproduksi dua jenis produk, X dan Y. Setiap unit produk X membutuhkan 2 jam kerja mesin A dan 1 jam kerja mesin B. Setiap unit produk Y membutuhkan 1 jam kerja mesin A dan 3 jam kerja mesin B. Mesin A tersedia 8 jam per hari, mesin B tersedia 12 jam per hari. Keuntungan per unit X adalah Rp40.000 dan per unit Y adalah Rp30.000. Berapakah fungsi tujuan dari model program linear yang tepat?

A. Maksimum Z = 30.000 X + 40.000 Y
B. Maksimum Z = 40.000 X + 30.000 Y
C. Minimum Z = 40.000 X + 30.000 Y
D. Maksimum Z = 8 X + 12 Y

Jawaban: B. Fungsi tujuan adalah memaksimumkan keuntungan, dimana keuntungan X Rp40.000 dan Y Rp30.000, sehingga Z = 40.000 X + 30.000 Y.

2. Dalam model program linear, variabel keputusan biasanya dilambangkan dengan huruf tertentu. Jika sebuah perusahaan ingin menentukan jumlah produksi dua barang A dan B, maka variabel keputusan yang tepat adalah

A. A dan B
B. X1 dan X2
C. Z dan C
D. S1 dan S2

Jawaban: B. Variabel keputusan dalam program linear umumnya dilambangkan dengan X1, X2, dan seterusnya untuk mewakili jumlah produk yang akan diproduksi.

3. Sebuah pabrik roti memproduksi roti manis dan roti asin. Roti manis membutuhkan 200 gram tepung dan 50 gram gula. Roti asin membutuhkan 150 gram tepung dan 30 gram garam. Tepung yang tersedia 10 kg per hari, gula 2 kg per hari, dan garam 1 kg per hari. Keuntungan roti manis Rp5.000 dan roti asin Rp4.000. Manakah kendala yang benar untuk ketersediaan gula jika variabel keputusan adalah X (roti manis) dan Y (roti asin)?

A. 50 X + 0 Y ≤ 2000
B. 50 X + 0 Y ≤ 10000
C. 50 X + 30 Y ≤ 2000
D. 50 X + 30 Y ≤ 200

Jawaban: A. Roti asin tidak menggunakan gula, sehingga koefisien untuk Y adalah 0. Gula tersedia 2 kg = 2000 gram, jadi kendalanya 50 X + 0 Y ≤ 2000.

4. Dalam merumuskan model program linear, langkah pertama yang harus dilakukan adalah

A. menentukan fungsi tujuan
B. menentukan kendala
C. mengidentifikasi variabel keputusan
D. menyelesaikan masalah

Jawaban: C. Langkah pertama dalam pemodelan program linear adalah mengidentifikasi variabel keputusan yang mewakili keputusan yang akan diambil.

5. Seorang petani memiliki lahan seluas 100 hektar. Ia akan menanam padi dan jagung. Setiap hektar padi membutuhkan 2 pekerja dan 1 ton pupuk. Setiap hektar jagung membutuhkan 1 pekerja dan 2 ton pupuk. Tersedia 150 pekerja dan 120 ton pupuk. Keuntungan per hektar padi Rp10.000.000 dan jagung Rp8.000.000. Rumusan fungsi kendala untuk lahan yang benar adalah

A. X + Y ≤ 100
B. X + Y ≥ 100
C. 2X + Y ≤ 100
D. X + Y = 100

Jawaban: A. Lahan yang tersedia adalah 100 hektar, sehingga jumlah lahan yang digunakan untuk padi (X) dan jagung (Y) tidak boleh melebihi 100 hektar: X + Y ≤ 100.

6. Dalam masalah program linear, jika terdapat kendala yang bersumber dari permintaan minimum, maka tanda pertidaksamaan yang digunakan adalah

A. ≤
B. ≥
C. =
D. <

Jawaban: B. Kendala permintaan minimum berarti jumlah produk harus paling tidak sebesar nilai tertentu, sehingga menggunakan tanda ≥.

7. Daerah penyelesaian dari sistem pertidaksamaan 2X + Y ≤ 6, X + Y ≤ 5, X ≥ 0, Y ≥ 0 memiliki titik pojok di (0,0), (3,0), dan satu titik lainnya. Titik apakah itu?

A. (0,5)
B. (1,4)
C. (2,2)
D. (0,6)

Jawaban: B. Titik potong antara 2X+Y=6 dan X+Y=5 adalah (1,4) karena substitusi menghasilkan X=1, Y=4. Titik (0,0), (3,0), (0,5), dan (1,4) membentuk daerah penyelesaian.

8. Daerah penyelesaian dari sistem pertidaksamaan X + Y ≤ 4, X ≥ 0, Y ≥ 0 jika digambarkan dalam grafik akan berbentuk

A. segitiga
B. persegi panjang
C. segiempat
D. garis lurus

Jawaban: A. Daerah yang dibatasi oleh X+Y≤4, X≥0, Y≥0 adalah segitiga dengan titik pojok (0,0), (4,0), dan (0,4).

9. Fungsi tujuan maksimum Z = 3X + 2Y dengan kendala X + 2Y ≤ 6, 2X + Y ≤ 8, X ≥ 0, Y ≥ 0. Nilai maksimum Z dicapai pada titik

A. (0,3)
B. (4,0)
C. (10/3, 4/3)
D. (0,0)

Jawaban: C. Titik potong X+2Y=6 dan 2X+Y=8 adalah (10/3, 4/3). Nilai Z = 3(10/3)+2(4/3)=10+8/3=38/3. Bandingkan dengan Z di (0,3)=6, (4,0)=12, (0,0)=0. Nilai maksimum di (10/3,4/3).

10. Titik (0,0) pada daerah penyelesaian program linear disebut juga titik

A. optimal
B. ekstrim
C. basis
D. origin

Jawaban: D. Titik (0,0) adalah titik asal atau origin dalam sistem koordinat kartesius.

11. Diketahui kendala: 3X + 2Y ≤ 12, X + 3Y ≤ 9, X ≥ 0, Y ≥ 0. Manakah titik berikut yang bukan termasuk daerah penyelesaian?

A. (2,1)
B. (1,2)
C. (4,0)
D. (0,5)

Jawaban: D. Periksa (0,5): 3(0)+2(5)=10 ≤ 12 (memenuhi) dan 0+3(5)=15 ≤ 9 (tidak memenuhi). Jadi (0,5) bukan daerah penyelesaian.

12. Untuk menentukan daerah penyelesaian pertidaksamaan 2X – Y ≤ 2, saat menguji titik (0,0) diperoleh hasil

A. 0 ≤ 2, benar, sehingga daerah penyelesaian memuat (0,0)
B. 0 ≤ 2, salah, sehingga daerah penyelesaian tidak memuat (0,0)
C. 0 ≤ 2, benar, sehingga daerah penyelesaian tidak memuat (0,0)
D. 0 ≤ 2, salah, sehingga daerah penyelesaian memuat (0,0)

Jawaban: A. Substitusi (0,0) ke 2X – Y ≤ 2 menghasilkan 0 ≤ 2 yang benar, maka daerah penyelesaian memuat titik (0,0).

13. Dalam program linear, suatu fungsi disebut fungsi linear jika memenuhi sifat

A. aditif dan homogen
B. konveks dan cekung
C. diskrit dan kontinu
D. simetris dan asimetris

Jawaban: A. Fungsi linear memiliki sifat aditif f(x+y)=f(x)+f(y) dan homogen f(kx)=kf(x).

14. Himpunan titik-titik yang memenuhi semua kendala dalam program linear disebut

A. daerah layak
B. daerah optimal
C. himpunan solusi
D. ruang vektor

Jawaban: A. Daerah layak adalah himpunan semua titik yang memenuhi seluruh kendala dari masalah program linear.

15. Jika suatu program linear memiliki daerah layak yang tidak terbatas, kemungkinan solusi optimalnya adalah

A. tidak ada solusi
B. solusi tunggal
C. solusi tak terbatas
D. tak tentu

Jawaban: C. Daerah layak tak terbatas dapat menyebabkan fungsi tujuan tidak memiliki batas atas (maksimum) atau bawah (minimum), sehingga solusi optimal tak terbatas.

16. Konsep konveksitas dalam program linear berkaitan dengan sifat daerah layak yang berbentuk

A. cekung
B. cembung
C. lurus
D. melengkung

Jawaban: B. Daerah layak dalam program linear adalah himpunan cembung (konveks), yaitu ruas garis antara dua titik di dalamnya juga berada di dalam himpunan.

17. Dalam metode grafik, solusi optimal program linear selalu terletak pada

A. pusat daerah layak
B. sumbu koordinat
C. salah satu titik sudut daerah layak
D. sembarang titik

Jawaban: C. Teorema dasar program linear menyatakan bahwa jika ada solusi optimal, maka solusi tersebut terletak di salah satu titik sudut (ekstrim) dari daerah layak.

18. Dalam pemrograman linear, suatu solusi yang memenuhi semua kendala disebut dengan solusi …

A. basis
B. tidak layak
C. optimal
D. layak

Jawaban: D. Solusi yang memenuhi semua kendala dan tidak melanggar batasan disebut solusi layak.

19. Daerah yang memenuhi semua kendala dalam program linear disebut sebagai daerah …

A. infeasible
B. terbuka
C. feasible
D. takterbatas

Jawaban: C. Daerah yang memuat semua titik yang memenuhi kendala disebut daerah feasible, tempat semua solusi layak berada.

20. Titik sudut atau pojok dari daerah feasible dalam metode grafik juga sering disebut sebagai titik …

A. slack
B. infeasible
C. ekstrim
D. surplus

Jawaban: C. Titik ekstrim atau titik pojok adalah titik sudut daerah feasible yang menjadi kandidat solusi optimal.

21. Fungsi tujuan dalam program linear dua variabel digambarkan sebagai garis lurus yang disebut …

A. garis kendala
B. garis isoprofit atau isocost
C. garis sumbu
D. garis lurus biasa

Jawaban: B. Garis yang mewakili nilai fungsi tujuan yang sama disebut garis isoprofit (untuk maksimasi) atau isocost (untuk minimasi).

22. Jika daerah feasible suatu program linear tidak terbatas (unbounded), maka kemungkinan solusi optimal adalah …

A. tidak ada
B. solusi tunggal
C. solusi berganda
D. solusi pada titik pusat

Jawaban: A. Saat daerah feasible tidak terbatas, solusi optimal mungkin tidak dapat ditemukan karena fungsi tujuan dapat terus meningkat atau menurun tanpa henti.

23. Metode grafik dalam program linear hanya dapat digunakan jika jumlah variabel keputusan maksimal sebanyak …

A. 1
B. 2
C. 3
D. 4

Jawaban: B. Metode grafik hanya efektif untuk dua variabel keputusan karena dapat divisualisasikan dalam bidang dua dimensi.

24. Dalam metode grafik, jika fungsi tujuan digerakkan sejajar hingga menyentuh titik ekstrim terakhir sebelum keluar daerah feasible, maka titik tersebut adalah solusi …

A. tidak terbatas
B. infeasible
C. suboptimal
D. optimal

Jawaban: D. Titik ekstrim yang disentuh garis fungsi tujuan paling ujung pada daerah feasible merupakan solusi optimal.

25. Pada sistem persamaan linear dengan dua persamaan dan tiga variabel, jumlah variabel yang dapat dipilih sebagai variabel nonbasis adalah …

A. 2
B. 1
C. 3
D. 0

Jawaban: B. Dengan dua persamaan, terdapat dua variabel basis, sehingga satu variabel sisanya menjadi variabel nonbasis.

26. Metode eliminasi Gauss-Jordan digunakan untuk menyelesaikan sistem persamaan linear dengan mengubah matriks menjadi bentuk …

A. segitiga atas
B. eselon baris
C. eselon baris tereduksi
D. identitas

Jawaban: C. Gauss-Jordan menghasilkan bentuk eselon baris tereduksi, di mana setiap kolom utama hanya memiliki satu elemen 1 dan sisanya 0.

27. Jika dalam eliminasi Gauss-Jordan ditemukan baris yang seluruh elemennya nol kecuali elemen konstanta, maka sistem persamaan tersebut …

A. memiliki solusi basis
B. memiliki solusi tunggal
C. memiliki solusi tak hingga
D. tidak memiliki solusi

Jawaban: D. Baris seperti [0 0 … | c] dengan c bukan nol menunjukkan ketidakkonsistenan, sehingga sistem tidak memiliki solusi.

28. Operasi baris elementer yang menukar dua baris dalam matriks disebut sebagai operasi …

A. pertukaran baris
B. penskalaan baris
C. penggantian baris
D. penjumlahan baris

Jawaban: A. Pertukaran baris adalah salah satu operasi baris elementer yang mengubah urutan baris matriks.

29. Jika dalam eliminasi Gauss-Jordan sebuah kolom memiliki elemen utama (pivot) bernilai nol maka langkah yang tepat adalah …

A. hapus baris tersebut
B. lanjutkan ke kolom berikutnya
C. tukar baris dengan baris di bawahnya yang memiliki elemen bukan nol
D. kalikan baris dengan nol

Jawaban: C. Jika pivot nol, baris harus ditukar dengan baris di bawahnya yang memiliki elemen bukan nol pada kolom yang sama.

30. Dalam metode simpleks, bentuk baku mensyaratkan semua kendala pertidaksamaan diubah menjadi persamaan dengan menambahkan variabel …

A. slack
B. surplus
C. buatan
D. basis

Jawaban: A. Kendala berjenis ≤ diubah dengan menambahkan variabel slack yang mewakili kapasitas yang tidak terpakai.

31. Variabel yang nilainya ditetapkan nol dalam solusi basis awal metode simpleks disebut variabel …

A. nonbasis
B. basis
C. slack
D. artifisial

Jawaban: A. Variabel nonbasis adalah variabel yang bernilai nol, sedangkan variabel basis memiliki nilai positif pada iterasi tertentu.

32. Pada metode simpleks, matriks koefisien yang terdiri dari kolom-kolom variabel basis disebut matriks …

A. simpleks
B. identitas
C. koefisien
D. basis

Jawaban: D. Matriks basis adalah submatriks dari koefisien kendala yang berisi kolom-kolom variabel basis yang saling bebas linear.

33. Bentuk baku program linear maksimasi memiliki fungsi tujuan dengan arah …

A. Z = maksimum
B. Z = minimum
C. Z = nol
D. Z = tak hingga

Jawaban: A. Bentuk baku untuk masalah maksimasi ditulis dengan fungsi tujuan Z = maksimum dan semua variabel nonnegatif.

34. Setiap pertidaksamaan dalam bentuk baku yang memiliki tanda ≥ harus ditambahkan variabel …

A. slack
B. surplus
C. buatan
D. basis

Jawaban: B. Kendala ≥ membutuhkan variabel surplus untuk mengubahnya menjadi persamaan, karena kelebihan sisi kiri dikurangi.

35. Dalam metode simpleks, untuk mengubah pertidaksamaan linear menjadi bentuk baku, variabel yang ditambahkan pada pertidaksamaan dengan tanda "≤" adalah…

A. variabel keputusan
B. variabel surplus
C. variabel slack
D. variabel buatan

Jawaban: C. Variabel slack ditambahkan pada pertidaksamaan berjenis ≤ untuk mengubahnya menjadi persamaan

36. Pada bentuk baku program linear, fungsi tujuan yang semula maksimasi atau minimasi harus diubah menjadi…

A. bentuk eksplisit dengan semua variabel di ruas kiri
B. bentuk persamaan dengan ruas kanan nol
C. bentuk optimal
D. bentuk pertidaksamaan

Jawaban: A. Fungsi tujuan dalam bentuk baku dituliskan secara eksplisit dengan semua variabel dipindahkan ke ruas kiri

37. Dalam tabel simpleks awal, baris pertama setelah baris judul biasanya disebut…

A. baris fungsi tujuan
B. baris kendala
C. baris variabel basis
D. baris nilai

Jawaban: A. Pada tabel simpleks, baris pertama setelah judul kolom adalah baris fungsi tujuan atau baris Z

38. Pertama kali dalam iterasi simpleks, variabel yang masuk ke basis ditentukan berdasarkan nilai pada baris fungsi tujuan yaitu…

A. nilai terkecil positif
B. nilai terbesar positif
C. nilai nol
D. nilai negatif terbesar

Jawaban: D. Pada masalah maksimasi, variabel dengan koefisien negatif terbesar pada baris Z dipilih sebagai entering variable

39. Untuk menentukan variabel yang keluar dari basis dalam tabel simpleks, digunakan rasio minimum dari…

A. nilai ruas kanan dibagi elemen kolom kunci
B. elemen pivot dibagi nilai ruas kanan
C. koefisien baris Z dibagi elemen kolom kunci
D. elemen kolom kunci dibagi nilai variabel basis

Jawaban: A. Rasio minimum dihitung dengan membagi nilai ruas kanan dengan elemen positif pada kolom kunci

40. Pada tabel simpleks, kolom pertama dari kiri biasanya berisi…

A. variabel keputusan
B. variabel basis
C. koefisien fungsi tujuan
D. nilai ruas kanan

Jawaban: B. Kolom pertama pada tabel simpleks biasanya menampilkan variabel-variabel yang menjadi basis saat itu

41. Proses mengubah elemen pivot menjadi 1 dan elemen lain pada kolom pivot menjadi 0 pada metode simpleks disebut…

A. penentuan basis
B. eliminasi Gauss
C. iterasi simpleks
D. operasi baris elementer

Jawaban: D. Langkah ini adalah operasi baris elementer yang diterapkan pada tabel simpleks untuk memperbarui basis

42. Pada tabel simpleks optimal untuk masalah maksimasi, semua koefisien pada baris fungsi tujuan harus…

A. negatif
B. positif atau nol
C. ber nilai positif semua
D. sama dengan nol

Jawaban: B. Untuk masalah maksimasi, kondisi optimal adalah semua koefisien baris Z bernilai ≥ 0

43. Jika dalam iterasi simpleks diperoleh nilai ruas kanan negatif pada salah satu baris kendala, maka solusi yang dihasilkan adalah…

A. solusi optimal
B. solusi tidak layak
C. solusi tak terbatas
D. solusi degenerasi

Jawaban: B. Nilai ruas kanan negatif pada kendala menunjukkan bahwa solusi dasar tidak memenuhi syarat nonnegativitas sehingga tidak layak

44. Langkah pertama dalam menggunakan metode simpleks adalah mengubah model program linear ke dalam…

A. bentuk grafik
B. bentuk dual
C. bentuk baku
D. bentuk kanonik

Jawaban: C. Langkah awal metode simpleks adalah mengubah model ke bentuk baku dengan menambahkan variabel slack atau surplus

45. Pada tabel simpleks, baris Z diperbarui dengan cara…

A. mengurangi baris Z lama dengan 1
B. mengalikan baris Z dengan koefisien pivot
C. menambahkan baris Z dengan baris pivot
D. mengurangkan baris Z lama dengan (koefisien entering variable dikali baris pivot)

Jawaban: D. Pembaruan baris Z dilakukan dengan mengurangi baris Z lama dengan hasil kali koefisien entering variable dan baris pivot baru

46. Jika semua rasio minimum pada kolom kunci bernilai tak terdefinisi karena elemen kolom kunci bernilai negatif atau nol, maka masalah tersebut memiliki…

A. solusi tak terbatas
B. solusi optimal alternatif
C. solusi optimal tunggal
D. solusi tidak layak

Jawaban: A. Jika tidak ada elemen positif pada kolom kunci maka tidak ada pembatas pertumbuhan dan solusi menjadi tak terbatas

47. Untuk pertidaksamaan berjenis "≥", variabel yang ditambahkan untuk mengubahnya menjadi persamaan adalah…

A. variabel surplus dan variabel buatan
B. variabel slack
C. variabel buatan saja
D. variabel keputusan baru

Jawaban: A. Pertidaksamaan ≥ memerlukan variabel surplus untuk mengurangi ruas kiri dan variabel buatan untuk membantu solusi awal

48. Dalam metode simpleks dengan variabel buatan, teknik yang digunakan untuk memaksa variabel buatan keluar dari basis adalah…

A. metode grafik
B. metode dual simpleks
C. metode big M
D. metode cabang dan batas

Jawaban: C. Metode big M memberikan penalti besar pada fungsi tujuan sehingga variabel buatan akan keluar dari basis

49. Pada masalah minimasi dengan semua kendala berjenis ≥, solusi awal yang diperoleh dengan variabel buatan akan menghasilkan…

A. solusi optimal
B. solusi layak basis awal
C. solusi tak terbatas
D. solusi tidak layak

Jawaban: D. Variabel buatan memberikan solusi basis awal yang layak secara artifisial tetapi fungsi tujuan belum optimal

50. Koefisien fungsi tujuan untuk variabel buatan pada metode big M untuk masalah minimasi adalah…

A. 0
B. bilangan negatif sangat besar (-M)
C. bilangan positif sangat besar (M)
D. 1

Jawaban: C. Untuk masalah minimasi, variabel buatan diberi koefisien M (bilangan positif besar) agar diminimalkan hingga nol

51. Sistem persyaratan campuran (gabungan ≤, =, ≥) dalam bentuk baku memerlukan penambahan…

A. hanya variabel slack
B. variabel slack, surplus, dan buatan sesuai jenis pertidaksamaan
C. hanya variabel surplus
D. variabel keputusan baru

Jawaban: B. Setiap jenis pertidaksamaan memerlukan variabel yang berbeda: slack untuk ≤, surplus dan buatan untuk ≥, serta buatan untuk =

52. Dalam metode simpleks, jika semua pertaksamaan kendala berjenis '≥', maka untuk mengubahnya ke bentuk baku diperlukan penambahan variabel…

A. surplus
B. slack
C. basis buatan
D. nonbasis

Jawaban: A. Karena pertaksamaan '≥' membutuhkan variabel surplus untuk mengurangi ruas kiri agar menjadi persamaan.

53. Pada kendala berjenis '≥', variabel buatan ditambahkan dengan tujuan…

A. membantu mencapai solusi optimal
B. mengurangi jumlah variabel
C. mengubah fungsi tujuan
D. membentuk matriks identitas sebagai basis awal

Jawaban: D. Variabel buatan diperlukan untuk menyediakan basis awal dalam bentuk matriks identitas pada iterasi pertama.

54. Metode dua fase digunakan untuk menyelesaikan masalah program linear jika kendala mengandung…

A. variabel buatan
B. pertaksamaan '≤' saja
C. variabel slack
D. variabel keputusan negatif

Jawaban: A. Metode dua fase diperlukan ketika ada variabel buatan, misalnya karena kendala berjenis '≥' atau persamaan.

55. Dalam sistem persyaratan campuran, kendala yang berbentuk persamaan ( = ) ditangani dengan menambahkan…

A. variabel surplus
B. variabel buatan
C. variabel slack
D. variabel keputusan

Jawaban: B. Kendala persamaan tidak memiliki slack atau surplus, sehingga perlu variabel buatan untuk basis awal.

56. Jika suatu kendala berbentuk '3×1 + 2×2 ≥ 10' diubah ke bentuk baku, variabel yang ditambahkan adalah…

A. variabel surplus dan variabel buatan
B. variabel slack dan variabel buatan
C. hanya variabel surplus
D. hanya variabel buatan

Jawaban: A. Kendala '≥' membutuhkan surplus dan karena surplus tidak memberikan basis, perlu ditambah variabel buatan.

57. Pada metode simpleks dengan kendala campuran, fungsi tujuan fase pertama adalah…

A. memaksimalkan variabel slack
B. meminimalkan variabel surplus
C. memaksimalkan fungsi asli
D. meminimalkan jumlah variabel buatan

Jawaban: D. Fase pertama bertujuan meminimalkan total variabel buatan untuk mendapatkan solusi layak awal.

58. Diberikan kendala: x1 + x2 = 5 dan x1 – x2 ≥ 3. Setelah diubah ke bentuk baku, jumlah variabel buatan yang ditambahkan adalah…

A. 0
B. 2
C. 1
D. 3

Jawaban: B. Kendala persamaan butuh 1 variabel buatan, kendala '≥' butuh surplus dan 1 variabel buatan, total 2 buatan.

59. Dalam metode simpleks, jika terdapat kendala '2×1 + 3×2 ≤ 15' dan 'x1 + x2 ≥ 4', bentuk baku yang tepat adalah…

A. 2×1+3×2+s1=15 ; x1+x2-s2+a2=4
B. 2×1+3×2+s1=15 ; x1+x2+s2=4
C. 2×1+3×2-s1=15 ; x1+x2+s2=4
D. 2×1+3×2+s1=15 ; x1+x2+a2=4

Jawaban: A. Kendala '≤' ditambah slack, kendala '≥' dikurangi surplus dan ditambah variabel buatan agar ada basis.

60. Keadaan khusus dalam program linear terjadi ketika fungsi tujuan sejajar dengan salah satu kendala yang mengikat, sehingga menghasilkan…

A. solusi tak terbatas
B. solusi optimal tunggal
C. solusi optimal alternatif/ tak terhingga
D. tidak ada solusi

Jawaban: C. Ketika fungsi tujuan sejajar dengan kendala aktif, ada banyak titik optimal pada segmen garis.

61. Dalam tabel simpleks, keadaan degenerasi ditandai dengan…

A. semua koefisien pada baris tujuan negatif
B. tidak ada variabel yang bisa masuk basis
C. baris tujuan memiliki koefisien nol pada variabel nonbasis
D. nilai ruas kanan sama dengan nol pada variabel basis

Jawaban: D. Degenerasi terjadi jika satu atau lebih variabel basis memiliki nilai nol pada kolom solusi.

62. Jika dalam iterasi simpleks tidak ada variabel yang memenuhi syarat untuk meninggalkan basis (nilai rasio minimum tak terdefinisi), maka masalah memiliki…

A. solusi tak terbatas
B. solusi optimal alternatif
C. degenerasi
D. infeasibility

Jawaban: A. Jika rasio tidak terdefinisi karena koefisien negatif atau nol, fungsi tujuan dapat membesar tak terbatas.

63. Penyebab utama terjadinya masalah infeasible dalam program linear adalah…

A. fungsi tujuan tidak linier
B. variabel keputusan bernilai negatif
C. kendala yang saling bertentangan
D. terlalu banyak variabel

Jawaban: C. Infeasible terjadi ketika tidak ada titik yang memenuhi seluruh kendala secara bersamaan.

64. Pada tabel simpleks, jika koefisien baris tujuan untuk suatu variabel nonbasis adalah nol dan solusi optimal telah tercapai, maka masalah tersebut menunjukkan…

A. degenerasi
B. solusi optimal alternatif
C. solusi tak terbatas
D. infeasibility

Jawaban: B. Nol pada baris tujuan variabel nonbasis menandakan ada variabel lain yang bisa masuk dengan nilai fungsi sama.

65. Dalam masalah maksimisasi, jika pada iterasi simpleks semua koefisien baris tujuan sudah nonpositif tetapi masih ada variabel buatan positif pada basis, maka…

A. solusi optimal tercapai
B. solusi tak terbatas
C. masalah infeasible
D. perlu iterasi lanjutan

Jawaban: C. Keberadaan variabel buatan positif pada basis saat optimal menunjukkan tidak ada solusi layak.

66. Keadaan khusus berupa multiple optimal solutions sering dimanfaatkan dalam…

A. optimasi tunggal
B. analisis sensitivitas untuk fleksibilitas
C. metode grafik 3 dimensi
D. degenerasi

Jawaban: B. Adanya banyak solusi optimal memberi fleksibilitas dalam pengambilan keputusan, terkait analisis sensitivitas.

67. Pada metode simpleks, jika terdapat kendala 'x1 – 2×2 ≥ 0' dan fungsi tujuan maksimisasi, maka bentuk baku yang benar adalah…

A. x1-2×2+a1=0
B. x1-2×2+s1=0
C. x1-2×2-s1=0
D. x1-2×2-s1+a1=0

Jawaban: D. Kendala '≥' memerlukan surplus (-s1) dan variabel buatan untuk basis awal.

68. Jika suatu program linear memiliki solusi optimal alternatif, maka nilai fungsi tujuan pada semua titik optimal tersebut adalah…

A. berbeda
B. tidak terdefinisi
C. sama
D. nol

Jawaban: C. Solusi optimal alternatif memberikan nilai fungsi tujuan yang identik pada setiap titik layak yang optimal.

69. Dalam metode simpleks, ketika ditemukan suatu variabel nonbasis memiliki koefisien positif pada baris fungsi tujuan (untuk masalah maksimasi) tetapi kolom yang bersesuaian tidak memiliki koefisien positif pada kendala, maka masalah tersebut mengalami keadaan khusus berupa…

A. infeasibilitas
B. degenerasi
C. solusi optimal alternatif
D. solusi tak terbatas

Jawaban: D. Jika suatu variabel nonbasis memiliki koefisien positif pada fungsi tujuan tetapi kolomnya tidak memiliki koefisien positif pada kendala, maka nilai variabel tersebut dapat dinaikkan tak terhingga sehingga solusi menjadi tak terbatas.

70. Dalam masalah program linear, jika dua atau lebih titik pojok yang berbeda menghasilkan nilai fungsi tujuan yang sama dan optimal, maka keadaan ini disebut…

A. solusi tak terbatas
B. degenerasi
C. solusi optimal alternatif
D. infeasibilitas

Jawaban: C. Solusi optimal alternatif terjadi ketika terdapat lebih dari satu solusi optimal yang menghasilkan nilai fungsi tujuan yang sama.

71. Dalam masalah program linear primal yang merupakan masalah maksimasi dengan kendala ≤, maka bentuk dual dari masalah tersebut 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 berupa minimasi dengan kendala ≥.

72. Jika masalah primal memiliki solusi optimal, maka pada dual akan berlaku sifat…

A. dual belum tentu memiliki solusi optimal
B. dual juga memiliki solusi optimal dengan nilai fungsi tujuan yang sama
C. dual tidak memiliki solusi
D. dual memiliki solusi dengan nilai fungsi tujuan yang berbeda

Jawaban: B. Sifat utama dualitas menyatakan bahwa jika primal memiliki solusi optimal maka dual juga memiliki solusi optimal dengan nilai fungsi tujuan yang sama.

73. Dalam hubungan primal-dual, nilai variabel dual pada optimalitas disebut juga sebagai…

A. koefisien fungsi tujuan
B. variabel surplus
C. nilai slack
D. harga bayangan

Jawaban: D. Nilai variabel dual pada solusi optimal sering disebut sebagai harga bayangan karena menunjukkan perubahan nilai fungsi tujuan akibat perubahan satu unit sumber daya.

74. Jika primal adalah masalah minimasi dengan kendala ≥, maka dual dari masalah tersebut adalah…

A. maksimasi dengan kendala ≥
B. minimasi dengan kendala ≤
C. maksimasi dengan kendala ≤
D. minimasi dengan kendala ≥

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

75. Dalam model dualitas, jika kendala primal berbentuk persamaan, maka variabel dual yang bersesuaian bersifat…

A. non-negatif
B. nol
C. tidak terbatas tandanya
D. negatif

Jawaban: C. Kendala persamaan pada primal menyebabkan variabel dual yang bersesuaian tidak terbatas tandanya (unrestricted in sign).

76. Metode simpleks-dual digunakan untuk menyelesaikan masalah program linear yang…

A. memiliki solusi awal yang tidak fisibel
B. memiliki solusi awal yang fisibel
C. semua kendala bertipe ≥
D. semua variabel tidak terbatas

Jawaban: A. Metode simpleks-dual digunakan ketika solusi awal tidak fisibel tetapi sudah memenuhi kondisi optimalitas.

77. Langkah pertama dalam metode simpleks-dual adalah memastikan bahwa baris fungsi tujuan sudah memenuhi kondisi…

A. fisibilitas
B. integralitas
C. non-negatif
D. optimalitas

Jawaban: D. Metode simpleks-dual dimulai dari tabel yang sudah optimal (semua koefisien baris tujuan ber tanda sesuai) tetapi belum fisibel.

78. Dalam metode simpleks-dual, variabel yang keluar basis adalah variabel basis dengan nilai paling…

A. positif besar
B. positif kecil
C. nol
D. negatif

Jawaban: D. Variabel basis dengan nilai negatif yang paling besar (paling negatif) dipilih untuk keluar basis agar mencapai fisibilitas.

79. Dalam metode simpleks-dual, rasio untuk menentukan variabel yang masuk basis dihitung dari…

A. koefisien baris tujuan dibagi koefisien kolom pivot
B. koefisien kolom pivot dibagi koefisien baris tujuan
C. nilai ruas kanan dibagi koefisien kolom pivot
D. koefisien baris tujuan dibagi nilai ruas kanan

Jawaban: A. Rasio dihitung dengan membagi koefisien baris tujuan (yang bertanda sesuai) dengan koefisien baris kendala pada kolom pivot, lalu dipilih rasio terkecil.

80. Jika dalam metode simpleks-dual semua koefisien pada baris variabel yang akan keluar basis bernilai non-negatif, maka masalah tersebut…

A. tidak memiliki solusi optimal
B. memiliki solusi optimal unik
C. memiliki solusi optimal alternatif
D. mengalami degenerasi

Jawaban: A. Jika semua koefisien pada baris pivot non-negatif, maka tidak ada variabel yang dapat masuk basis untuk memperbaiki fisibilitas, sehingga masalah dinyatakan tidak memiliki solusi optimal (infeasible).

81. Dalam metode simpleks revisi, matriks yang digunakan untuk memperbarui solusi adalah…

A. matriks koefisien kendala awal
B. invers dari matriks basis
C. matriks identitas
D. matriks fungsi tujuan

Jawaban: B. Metode simpleks revisi menggunakan invers dari matriks basis untuk memperbarui solusi dan menghitung koefisien yang diperlukan.

82. Keuntungan utama metode simpleks revisi dibandingkan metode simpleks biasa adalah…

A. lebih sederhana dalam perhitungan
B. mengurangi kebutuhan memori dan perhitungan yang tidak perlu
C. selalu menghasilkan solusi integer
D. dapat digunakan untuk semua jenis kendala

Jawaban: B. Metode simpleks revisi hanya menghitung elemen yang diperlukan, sehingga lebih efisien dalam penggunaan memori dan perhitungan.

83. Dalam pemrograman parametrik, perubahan parameter pada koefisien fungsi tujuan akan mempengaruhi…

A. daerah fisibel
B. invers matriks basis
C. kemiringan garis fungsi tujuan
D. nilai optimal variabel dual

Jawaban: C. Perubahan koefisien fungsi tujuan mengubah kemiringan garis fungsi tujuan, yang dapat mengubah titik optimal tanpa mengubah daerah fisibel.

84. Dalam pemrograman parametrik, jika suatu parameter terus diubah dan solusi optimal berubah, maka kondisi yang harus dipenuhi agar solusi tetap optimal adalah…

A. semua koefisien baris tujuan tetap non-negatif
B. semua nilai ruas kanan tetap non-negatif
C. matriks basis tetap invertible
D. semua variabel basis tetap non-negatif

Jawaban: A. Untuk mempertahankan optimalitas, koefisien baris fungsi tujuan harus tetap memenuhi kondisi optimalitas (non-negatif untuk maksimasi) selama perubahan parameter.

85. Dalam Metode Simpleks Revisi, matriks basis (B) digunakan untuk menghitung koefisien variabel nonbasis. Manakah dari pernyataan berikut yang BENAR mengenai peran matriks basis?

A. Matriks basis B adalah matriks yang terdiri dari koefisien variabel slack pada iterasi awal
B. Matriks basis B digunakan untuk menghitung vektor kolom dari variabel nonbasis yang masuk
C. Matriks basis B adalah submatriks dari matriks koefisien kendala yang terdiri dari kolom-kolom variabel basis
D. Matriks basis B selalu berukuran m x n, di mana m adalah jumlah kendala dan n adalah jumlah variabel

Jawaban: C. Matriks basis B adalah submatriks dari matriks koefisien kendala yang terdiri dari kolom-kolom variabel basis, dan berukuran m x m.

86. Dalam pemrograman parametrik, ketika nilai parameter λ berubah secara kontinu, bagaimana perubahan solusi optimal terjadi jika koefisien fungsi tujuan berubah?

A. Solusi optimal tidak pernah berubah untuk sembarang λ
B. Solusi optimal berubah secara diskrit pada titik kritis tertentu
C. Solusi optimal berubah terus menerus mengikuti perubahan λ
D. Solusi optimal hanya berubah jika λ bernilai negatif

Jawaban: B. Dalam pemrograman parametrik, ketika koefisien fungsi tujuan berubah secara linear dengan parameter λ, solusi optimal berubah secara diskrit pada titik kritis yang disebut breakpoint.

87. Diketahui fungsi tujuan maksimasi Z = (2+λ)x1 + (3-λ)x2 dengan kendala x1 + 2×2 ≤ 10 dan x1, x2 ≥ 0. Pada rentang λ = 0 hingga λ = 5, perubahan koefisien fungsi tujuan akan mempengaruhi solusi optimal. Manakah pernyataan yang PALING TEPAT?

A. Nilai λ tidak mempengaruhi nilai variabel basis
B. Perubahan λ hanya mempengaruhi ruas kanan kendala
C. Solusi optimal tetap sama untuk seluruh rentang λ
D. Nilai λ dapat mengubah variabel yang masuk ke basis

Jawaban: D. Perubahan parameter λ pada koefisien fungsi tujuan dapat mengubah koefisien relatif variabel dan menyebabkan variabel lain masuk ke basis pada titik kritis tertentu.

88. Dalam pemrograman parametrik untuk perubahan ruas kanan kendala, misalkan b(λ) = b + λd, di mana d adalah vektor arah perubahan. Manakah yang terjadi ketika λ melampaui batas atas stabilitas basis?

A. Solusi optimal menjadi tidak terbatas
B. Basis tidak lagi layak sehingga diperlukan pivot dual
C. Basis menjadi singular
D. Nilai fungsi tujuan berhenti berubah

Jawaban: B. Ketika λ melampaui batas atas stabilitas basis, solusi basis tidak lagi layak, sehingga dual simplex digunakan untuk mencari basis baru yang layak.

89. Diketahui masalah maksimasi dengan fungsi tujuan Z = (1+λ)x1 + (2-λ)x2, dan kendala: x1 + 2×2 ≤ 10, 3×1 + x2 ≤ 15, x1, x2 ≥ 0. Solusi saat λ=0 adalah x1=4, x2=3 dengan Z=10. Berapa selang λ yang membuat solusi ini tetap optimal?

A. λ ≤ 1/2
B. λ ≥ -1
C. -1 ≤ λ ≤ 1/2
D. λ ≤ 1

Jawaban: C. Koefisien relatif variabel nonbasis dihitung. Pada λ=0, solusi optimal. Dengan menghitung koefisien variabel slack di baris Z, diperoleh batas bawah λ ≥ -1 dan batas atas λ ≤ 1/2 agar semua koefisien tetap nonnegatif.

90. Dalam pemrograman parametrik, jika ruas kanan kendala berubah mengikuti b(λ) = (10, 15) + λ(-2, 1) dan basis terdiri dari variabel x1 dan x2, manakah yang menunjukkan kondisi ketika basis menjadi tidak layak?

A. Nilai variabel basis negatif untuk suatu λ
B. Nilai variabel basis tetap positif untuk seluruh λ
C. Fungsi tujuan menjadi konstan
D. Koefisien fungsi tujuan berubah tanda

Jawaban: A. Perubahan ruas kanan menyebabkan nilai variabel basis berubah. Basis tidak layak jika salah satu nilai variabel basis menjadi negatif, yang menandakan perlunya dual pivot.

91. Dalam pemrograman integer, metode Branch and Bound digunakan untuk menyelesaikan masalah yang memerlukan solusi bilangan bulat. Apa penyebab utama munculnya percabangan (branch) dalam algoritma ini?

A. Kendala kontinuitas dilanggar
B. Adanya variabel yang bernilai pecahan pada solusi optimal kontinu
C. Fungsi tujuan tidak linear
D. Jumlah kendala lebih banyak dari variabel

Jawaban: B. Pada solusi optimal relaksasi linear, jika ada variabel yang bernilai pecahan, dilakukan pencabangan untuk memaksa variabel tersebut menjadi bilangan bulat.

92. Diketahui masalah pemrograman integer: Maksimasi Z = 4×1 + 5×2 dengan kendala 2×1 + 3×2 ≤ 10, 5×1 + 2×2 ≤ 15, x1, x2 ≥ 0 dan integer. Solusi relaksasi linear optimal adalah x1=2.5, x2=1.25, Z=16.25. Jika dilakukan branching pada x1, manakah subproblem yang PALING TEPAT?

A. Subproblem A: x1 ≤ 2, subproblem B: x1 ≥ 3
B. Subproblem A: x1 ≤ 2.5, subproblem B: x1 ≥ 2.5
C. Subproblem A: x1 ≤ 2, subproblem B: x1 ≥ 2
D. Subproblem A: x1 ≤ 3, subproblem B: x1 ≥ 4

Jawaban: A. Percabangan dilakukan dengan menambahkan kendala x1 ≤ 2 dan x1 ≥ 3, karena nilai pecahan 2.5 dipisah menjadi dua daerah integer yang tidak tumpang tindih.

93. Dalam metode Branch and Bound, jika suatu subproblem memiliki nilai fungsi tujuan yang lebih rendah dari best solution integer yang sudah ditemukan, apa yang harus dilakukan terhadap subproblem tersebut?

A. Lanjutkan pencabangan subproblem tersebut
B. Hapus subproblem tersebut (pruning) karena tidak akan menghasilkan solusi integer yang lebih baik
C. Selesaikan subproblem dengan metode grafik
D. Ubah fungsi tujuan subproblem menjadi minimasi

Jawaban: B. Subproblem dengan batas atas lebih rendah dari best solution integer tidak perlu dieksplorasi lebih lanjut karena tidak mungkin menghasilkan solusi integer yang lebih baik (pruning).

94. Pada relaksasi linear masalah pemrograman integer, diperoleh solusi optimal dengan nilai Z=24,5 dan x1=3,5; x2=2,8. Best solution integer sementara adalah Z=20. Subproblem pertama dengan kendala x1 ≤ 3 menghasilkan Z=22, sedangkan subproblem dengan x1 ≥ 4 menghasilkan Z=23. Berdasarkan data ini, cabang mana yang layak untuk dilanjutkan?

A. Hanya cabang x1 ≤ 3
B. Hanya cabang x1 ≥ 4
C. Kedua cabang
D. Tidak ada cabang yang layak

Jawaban: C. Kedua cabang memiliki nilai Z lebih besar dari best solution integer (20), sehingga keduanya berpotensi menghasilkan solusi integer yang lebih baik dan perlu dilanjutkan.

95. Dalam algoritma Branch and Bound, manakah kondisi yang menyebabkan suatu node dinyatakan sebagai terminal node (tidak perlu dicabangkan lagi)?

A. Node menghasilkan solusi dengan variabel integer semua
B. Node menghasilkan solusi tidak layak
C. Node memiliki batas atas lebih rendah dari best solution integer
D. Semua jawaban di atas benar

Jawaban: D. Semua kondisi di atas menyebabkan node tidak perlu dicabangkan: solusi integer layak, tidak layak, atau batas atas lebih rendah dari best solution.

96. Diketahui masalah pemrograman integer: Maksimasi Z = 3×1 + 2×2 dengan kendala x1 + 2×2 ≤ 8, 3×1 + x2 ≤ 12, x1, x2 ≥ 0 dan integer. Solusi relaksasi linear adalah x1=3,2; x2=2,4; Z=14,4. Nilai fungsi tujuan pada subproblem setelah branching pada x1 dengan kendala x1 ≤ 3 adalah Z=14. Berapa nilai Z subproblem dengan kendala x1 ≥ 4?

A. 12
B. 13
C. 14
D. 15

Jawaban: A. Dengan x1=4, dari kendala 3×1 + x2 ≤ 12, diperoleh x2=0. Z=3(4)+2(0)=12.

97. Suatu masalah pemrograman integer memiliki solusi optimal kontinu dengan x1=2,75 dan x2=1,5. Best solution integer sementara adalah Z=18. Subproblem dengan x2 ≤ 1 menghasilkan Z=17. Tindakan yang PALING TEPAT terhadap subproblem ini adalah:

A. Lakukan pencabangan lebih lanjut pada subproblem tersebut
B. Hapus subproblem karena nilai Z lebih rendah dari best solution
C. Ubah kendala x2 ≤ 1 menjadi x2 ≤ 0
D. Gabungkan dengan subproblem x2 ≥ 2

Jawaban: B. Nilai Z=17 lebih rendah dari best solution integer 18, sehingga subproblem tersebut tidak akan menghasilkan solusi yang lebih baik (pruning).

98. Dalam metode Branch and Bound untuk masalah minimasi, manakah pernyataan yang SALAH?

A. Pencabangan dilakukan pada variabel dengan nilai pecahan terkecil
B. Subproblem dengan nilai fungsi tujuan lebih besar dari best solution dapat dihapus
C. Subproblem yang tidak layak tidak perlu dieksplorasi lebih lanjut
D. Solusi integer terbaik sementara menjadi batas atas

Jawaban: A. Tidak ada aturan baku bahwa variabel dengan nilai pecahan terkecil harus dipilih; pemilihan variabel untuk pencabangan bisa berdasarkan berbagai aturan.

99. Pada iterasi Branch and Bound, diperoleh hasil berikut: Subproblem 1 (x1 ≤ 3): layak, Z=20, non-integer. Subproblem 2 (x1 ≥ 4): tidak layak. Subproblem 3 (x1 ≤ 2): layak, Z=18, integer. Subproblem 4 (x1 ≥ 5): tidak layak. Manakah yang menjadi best solution integer?

A. Subproblem 1
B. Subproblem 2
C. Subproblem 3
D. Subproblem 4

Jawaban: C. Subproblem 3 menghasilkan solusi integer layak dengan Z=18, sehingga menjadi best solution integer sementara.

100. Dalam pemrograman integer, mengapa metode Branch and Bound memerlukan eksplorasi cabang?

A. Untuk memastikan solusi integer ditemukan dengan memeriksa semua kemungkinan secara implisit
B. Untuk menghitung nilai parameter λ
C. Untuk mengubah fungsi tujuan menjadi linear
D. Untuk mengurangi jumlah kendala

Jawaban: A. Eksplorasi cabang dilakukan untuk memeriksa kemungkinan solusi integer secara implisit tanpa harus mengevaluasi semua titik integer satu per satu.

MATA4230 — Pemrograman Linear

Latihan Tambahan dengan AI