Bayangkan lagi asyik belajar, eh tiba-tiba nemu soal program linear yang pakai surplus variable di Modul 5. Padahal di Modul 4 slack variable aja masih belepotan. Dua modul itu beda tipis tapi sering bikin kacau. MATA4230 Pemrograman Linear ini teori dan hitungannya nempel terus, jadi harus jeli pas mengubah bentuk pertidaksamaan. kumpulan soal Universitas Terbuka di sini bisa bantu kamu bedain kasus modul 4 dan 5 biar nggak salah langkah.
Biar nggak tambah bingung, coba langsung deh lihat soal UT Matematika yang kami kumpulkan per kegiatan belajar. Mulai dari Modul 3 soal eliminasi Gauss-Jordan sampai Modul 9 metode cabang dan batas dari pemrograman integer. Soal-soal itu penting banget karena sering nguji pemahaman dasar kamu. latihan UAS UT ini nyusunnya rapi biar kamu bisa suka-suka pilih KB yang masih rawan salah.
Soal Ujian UT di bawah ini cakupannya langsung ke inti tiap KB, dari daerah penyelesaian di Modul 1 sampai simpleks revisi di Modul 8. Setiap soal dilengkapi kunci jawaban dan pembahasan buat ngecek apakah logika kamu udah bener. Langsung coba aja satu per satu, nanti ketahuan mana bagian yang masih perlu diulang.
Soal UT MATA4230 Pemrograman Linear
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?
Fungsi tujuan adalah memaksimumkan keuntungan, dimana keuntungan X Rp40.000 dan Y Rp30.000, sehingga Z = 40.000 X + 30.000 Y.
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
Variabel keputusan dalam program linear umumnya dilambangkan dengan X1, X2, dan seterusnya untuk mewakili jumlah produk yang akan diproduksi.
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)?
Roti asin tidak menggunakan gula, sehingga koefisien untuk Y adalah 0. Gula tersedia 2 kg = 2000 gram, jadi kendalanya 50 X + 0 Y ≤ 2000.
Dalam merumuskan model program linear, langkah pertama yang harus dilakukan adalah
Langkah pertama dalam pemodelan program linear adalah mengidentifikasi variabel keputusan yang mewakili keputusan yang akan diambil.
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
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.
Dalam masalah program linear, jika terdapat kendala yang bersumber dari permintaan minimum, maka tanda pertidaksamaan yang digunakan adalah
Kendala permintaan minimum berarti jumlah produk harus paling tidak sebesar nilai tertentu, sehingga menggunakan tanda ≥.
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?
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.
Daerah penyelesaian dari sistem pertidaksamaan X + Y ≤ 4, X ≥ 0, Y ≥ 0 jika digambarkan dalam grafik akan berbentuk
Daerah yang dibatasi oleh X+Y≤4, X≥0, Y≥0 adalah segitiga dengan titik pojok (0,0), (4,0), dan (0,4).
Fungsi tujuan maksimum Z = 3X + 2Y dengan kendala X + 2Y ≤ 6, 2X + Y ≤ 8, X ≥ 0, Y ≥ 0. Nilai maksimum Z dicapai pada titik
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).
Titik (0,0) pada daerah penyelesaian program linear disebut juga titik
Titik (0,0) adalah titik asal atau origin dalam sistem koordinat kartesius.
Diketahui kendala: 3X + 2Y ≤ 12, X + 3Y ≤ 9, X ≥ 0, Y ≥ 0. Manakah titik berikut yang bukan termasuk daerah penyelesaian?
Periksa (0,5): 3(0)+2(5)=10 ≤ 12 (memenuhi) dan 0+3(5)=15 ≤ 9 (tidak memenuhi). Jadi (0,5) bukan daerah penyelesaian.
Untuk menentukan daerah penyelesaian pertidaksamaan 2X – Y ≤ 2, saat menguji titik (0,0) diperoleh hasil
Substitusi (0,0) ke 2X – Y ≤ 2 menghasilkan 0 ≤ 2 yang benar, maka daerah penyelesaian memuat titik (0,0).
Dalam program linear, suatu fungsi disebut fungsi linear jika memenuhi sifat
Fungsi linear memiliki sifat aditif f(x+y)=f(x)+f(y) dan homogen f(kx)=kf(x).
Himpunan titik-titik yang memenuhi semua kendala dalam program linear disebut
Daerah layak adalah himpunan semua titik yang memenuhi seluruh kendala dari masalah program linear.
Jika suatu program linear memiliki daerah layak yang tidak terbatas, kemungkinan solusi optimalnya adalah
Daerah layak tak terbatas dapat menyebabkan fungsi tujuan tidak memiliki batas atas (maksimum) atau bawah (minimum), sehingga solusi optimal tak terbatas.
Konsep konveksitas dalam program linear berkaitan dengan sifat daerah layak yang berbentuk
Daerah layak dalam program linear adalah himpunan cembung (konveks), yaitu ruas garis antara dua titik di dalamnya juga berada di dalam himpunan.
Dalam metode grafik, solusi optimal program linear selalu terletak pada
Teorema dasar program linear menyatakan bahwa jika ada solusi optimal, maka solusi tersebut terletak di salah satu titik sudut (ekstrim) dari daerah layak.
Dalam pemrograman linear, suatu solusi yang memenuhi semua kendala disebut dengan solusi …
Solusi yang memenuhi semua kendala dan tidak melanggar batasan disebut solusi layak.
Daerah yang memenuhi semua kendala dalam program linear disebut sebagai daerah …
Daerah yang memuat semua titik yang memenuhi kendala disebut daerah feasible, tempat semua solusi layak berada.
Titik sudut atau pojok dari daerah feasible dalam metode grafik juga sering disebut sebagai titik …
Titik ekstrim atau titik pojok adalah titik sudut daerah feasible yang menjadi kandidat solusi optimal.
Fungsi tujuan dalam program linear dua variabel digambarkan sebagai garis lurus yang disebut …
Garis yang mewakili nilai fungsi tujuan yang sama disebut garis isoprofit (untuk maksimasi) atau isocost (untuk minimasi).
Jika daerah feasible suatu program linear tidak terbatas (unbounded), maka kemungkinan solusi optimal adalah …
Saat daerah feasible tidak terbatas, solusi optimal mungkin tidak dapat ditemukan karena fungsi tujuan dapat terus meningkat atau menurun tanpa henti.
Metode grafik dalam program linear hanya dapat digunakan jika jumlah variabel keputusan maksimal sebanyak …
Metode grafik hanya efektif untuk dua variabel keputusan karena dapat divisualisasikan dalam bidang dua dimensi.
Dalam metode grafik, jika fungsi tujuan digerakkan sejajar hingga menyentuh titik ekstrim terakhir sebelum keluar daerah feasible, maka titik tersebut adalah solusi …
Titik ekstrim yang disentuh garis fungsi tujuan paling ujung pada daerah feasible merupakan solusi optimal.
Pada sistem persamaan linear dengan dua persamaan dan tiga variabel, jumlah variabel yang dapat dipilih sebagai variabel nonbasis adalah …
Dengan dua persamaan, terdapat dua variabel basis, sehingga satu variabel sisanya menjadi variabel nonbasis.
Metode eliminasi Gauss-Jordan digunakan untuk menyelesaikan sistem persamaan linear dengan mengubah matriks menjadi bentuk …
Gauss-Jordan menghasilkan bentuk eselon baris tereduksi, di mana setiap kolom utama hanya memiliki satu elemen 1 dan sisanya 0.
Jika dalam eliminasi Gauss-Jordan ditemukan baris yang seluruh elemennya nol kecuali elemen konstanta, maka sistem persamaan tersebut …
Baris seperti [0 0 … | c] dengan c bukan nol menunjukkan ketidakkonsistenan, sehingga sistem tidak memiliki solusi.
Operasi baris elementer yang menukar dua baris dalam matriks disebut sebagai operasi …
Pertukaran baris adalah salah satu operasi baris elementer yang mengubah urutan baris matriks.
Jika dalam eliminasi Gauss-Jordan sebuah kolom memiliki elemen utama (pivot) bernilai nol maka langkah yang tepat adalah …
Jika pivot nol, baris harus ditukar dengan baris di bawahnya yang memiliki elemen bukan nol pada kolom yang sama.
Dalam metode simpleks, bentuk baku mensyaratkan semua kendala pertidaksamaan diubah menjadi persamaan dengan menambahkan variabel …
Kendala berjenis ≤ diubah dengan menambahkan variabel slack yang mewakili kapasitas yang tidak terpakai.
Variabel yang nilainya ditetapkan nol dalam solusi basis awal metode simpleks disebut variabel …
Variabel nonbasis adalah variabel yang bernilai nol, sedangkan variabel basis memiliki nilai positif pada iterasi tertentu.
Pada metode simpleks, matriks koefisien yang terdiri dari kolom-kolom variabel basis disebut matriks …
Matriks basis adalah submatriks dari koefisien kendala yang berisi kolom-kolom variabel basis yang saling bebas linear.
Bentuk baku program linear maksimasi memiliki fungsi tujuan dengan arah …
Bentuk baku untuk masalah maksimasi ditulis dengan fungsi tujuan Z = maksimum dan semua variabel nonnegatif.
Setiap pertidaksamaan dalam bentuk baku yang memiliki tanda ≥ harus ditambahkan variabel …
Kendala ≥ membutuhkan variabel surplus untuk mengubahnya menjadi persamaan, karena kelebihan sisi kiri dikurangi.
Dalam metode simpleks, untuk mengubah pertidaksamaan linear menjadi bentuk baku, variabel yang ditambahkan pada pertidaksamaan dengan tanda "≤" adalah…
Variabel slack ditambahkan pada pertidaksamaan berjenis ≤ untuk mengubahnya menjadi persamaan
Pada bentuk baku program linear, fungsi tujuan yang semula maksimasi atau minimasi harus diubah menjadi…
Fungsi tujuan dalam bentuk baku dituliskan secara eksplisit dengan semua variabel dipindahkan ke ruas kiri
Dalam tabel simpleks awal, baris pertama setelah baris judul biasanya disebut…
Pada tabel simpleks, baris pertama setelah judul kolom adalah baris fungsi tujuan atau baris Z
Pertama kali dalam iterasi simpleks, variabel yang masuk ke basis ditentukan berdasarkan nilai pada baris fungsi tujuan yaitu…
Pada masalah maksimasi, variabel dengan koefisien negatif terbesar pada baris Z dipilih sebagai entering variable
Untuk menentukan variabel yang keluar dari basis dalam tabel simpleks, digunakan rasio minimum dari…
Rasio minimum dihitung dengan membagi nilai ruas kanan dengan elemen positif pada kolom kunci
Pada tabel simpleks, kolom pertama dari kiri biasanya berisi…
Kolom pertama pada tabel simpleks biasanya menampilkan variabel-variabel yang menjadi basis saat itu
Proses mengubah elemen pivot menjadi 1 dan elemen lain pada kolom pivot menjadi 0 pada metode simpleks disebut…
Langkah ini adalah operasi baris elementer yang diterapkan pada tabel simpleks untuk memperbarui basis
Pada tabel simpleks optimal untuk masalah maksimasi, semua koefisien pada baris fungsi tujuan harus…
Untuk masalah maksimasi, kondisi optimal adalah semua koefisien baris Z bernilai ≥ 0
Jika dalam iterasi simpleks diperoleh nilai ruas kanan negatif pada salah satu baris kendala, maka solusi yang dihasilkan adalah…
Nilai ruas kanan negatif pada kendala menunjukkan bahwa solusi dasar tidak memenuhi syarat nonnegativitas sehingga tidak layak
Langkah pertama dalam menggunakan metode simpleks adalah mengubah model program linear ke dalam…
Langkah awal metode simpleks adalah mengubah model ke bentuk baku dengan menambahkan variabel slack atau surplus
Pada tabel simpleks, baris Z diperbarui dengan cara…
Pembaruan baris Z dilakukan dengan mengurangi baris Z lama dengan hasil kali koefisien entering variable dan baris pivot baru
Jika semua rasio minimum pada kolom kunci bernilai tak terdefinisi karena elemen kolom kunci bernilai negatif atau nol, maka masalah tersebut memiliki…
Jika tidak ada elemen positif pada kolom kunci maka tidak ada pembatas pertumbuhan dan solusi menjadi tak terbatas
Untuk pertidaksamaan berjenis "≥", variabel yang ditambahkan untuk mengubahnya menjadi persamaan adalah…
Pertidaksamaan ≥ memerlukan variabel surplus untuk mengurangi ruas kiri dan variabel buatan untuk membantu solusi awal
Dalam metode simpleks dengan variabel buatan, teknik yang digunakan untuk memaksa variabel buatan keluar dari basis adalah…
Metode big M memberikan penalti besar pada fungsi tujuan sehingga variabel buatan akan keluar dari basis
Pada masalah minimasi dengan semua kendala berjenis ≥, solusi awal yang diperoleh dengan variabel buatan akan menghasilkan…
Variabel buatan memberikan solusi basis awal yang layak secara artifisial tetapi fungsi tujuan belum optimal
Koefisien fungsi tujuan untuk variabel buatan pada metode big M untuk masalah minimasi adalah…
Untuk masalah minimasi, variabel buatan diberi koefisien M (bilangan positif besar) agar diminimalkan hingga nol
Sistem persyaratan campuran (gabungan ≤, =, ≥) dalam bentuk baku memerlukan penambahan…
Setiap jenis pertidaksamaan memerlukan variabel yang berbeda: slack untuk ≤, surplus dan buatan untuk ≥, serta buatan untuk =
Dalam metode simpleks, jika semua pertaksamaan kendala berjenis '≥', maka untuk mengubahnya ke bentuk baku diperlukan penambahan variabel…
Karena pertaksamaan '≥' membutuhkan variabel surplus untuk mengurangi ruas kiri agar menjadi persamaan.
Pada kendala berjenis '≥', variabel buatan ditambahkan dengan tujuan…
Variabel buatan diperlukan untuk menyediakan basis awal dalam bentuk matriks identitas pada iterasi pertama.
Metode dua fase digunakan untuk menyelesaikan masalah program linear jika kendala mengandung…
Metode dua fase diperlukan ketika ada variabel buatan, misalnya karena kendala berjenis '≥' atau persamaan.
Dalam sistem persyaratan campuran, kendala yang berbentuk persamaan ( = ) ditangani dengan menambahkan…
Kendala persamaan tidak memiliki slack atau surplus, sehingga perlu variabel buatan untuk basis awal.
Jika suatu kendala berbentuk '3×1 + 2×2 ≥ 10' diubah ke bentuk baku, variabel yang ditambahkan adalah…
Kendala '≥' membutuhkan surplus dan karena surplus tidak memberikan basis, perlu ditambah variabel buatan.
Pada metode simpleks dengan kendala campuran, fungsi tujuan fase pertama adalah…
Fase pertama bertujuan meminimalkan total variabel buatan untuk mendapatkan solusi layak awal.
Diberikan kendala: x1 + x2 = 5 dan x1 – x2 ≥ 3. Setelah diubah ke bentuk baku, jumlah variabel buatan yang ditambahkan adalah…
Kendala persamaan butuh 1 variabel buatan, kendala '≥' butuh surplus dan 1 variabel buatan, total 2 buatan.
Dalam metode simpleks, jika terdapat kendala '2×1 + 3×2 ≤ 15' dan 'x1 + x2 ≥ 4', bentuk baku yang tepat adalah…
Kendala '≤' ditambah slack, kendala '≥' dikurangi surplus dan ditambah variabel buatan agar ada basis.
Keadaan khusus dalam program linear terjadi ketika fungsi tujuan sejajar dengan salah satu kendala yang mengikat, sehingga menghasilkan…
Ketika fungsi tujuan sejajar dengan kendala aktif, ada banyak titik optimal pada segmen garis.
Dalam tabel simpleks, keadaan degenerasi ditandai dengan…
Degenerasi terjadi jika satu atau lebih variabel basis memiliki nilai nol pada kolom solusi.
Jika dalam iterasi simpleks tidak ada variabel yang memenuhi syarat untuk meninggalkan basis (nilai rasio minimum tak terdefinisi), maka masalah memiliki…
Jika rasio tidak terdefinisi karena koefisien negatif atau nol, fungsi tujuan dapat membesar tak terbatas.
Penyebab utama terjadinya masalah infeasible dalam program linear adalah…
Infeasible terjadi ketika tidak ada titik yang memenuhi seluruh kendala secara bersamaan.
Pada tabel simpleks, jika koefisien baris tujuan untuk suatu variabel nonbasis adalah nol dan solusi optimal telah tercapai, maka masalah tersebut menunjukkan…
Nol pada baris tujuan variabel nonbasis menandakan ada variabel lain yang bisa masuk dengan nilai fungsi sama.
Dalam masalah maksimisasi, jika pada iterasi simpleks semua koefisien baris tujuan sudah nonpositif tetapi masih ada variabel buatan positif pada basis, maka…
Keberadaan variabel buatan positif pada basis saat optimal menunjukkan tidak ada solusi layak.
Keadaan khusus berupa multiple optimal solutions sering dimanfaatkan dalam…
Adanya banyak solusi optimal memberi fleksibilitas dalam pengambilan keputusan, terkait analisis sensitivitas.
Pada metode simpleks, jika terdapat kendala 'x1 – 2×2 ≥ 0' dan fungsi tujuan maksimisasi, maka bentuk baku yang benar adalah…
Kendala '≥' memerlukan surplus (-s1) dan variabel buatan untuk basis awal.
Jika suatu program linear memiliki solusi optimal alternatif, maka nilai fungsi tujuan pada semua titik optimal tersebut adalah…
Solusi optimal alternatif memberikan nilai fungsi tujuan yang identik pada setiap titik layak yang optimal.
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…
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.
Dalam masalah program linear, jika dua atau lebih titik pojok yang berbeda menghasilkan nilai fungsi tujuan yang sama dan optimal, maka keadaan ini disebut…
Solusi optimal alternatif terjadi ketika terdapat lebih dari satu solusi optimal yang menghasilkan nilai fungsi tujuan yang sama.
Dalam masalah program linear primal yang merupakan masalah maksimasi dengan kendala ≤, maka bentuk dual dari masalah tersebut adalah…
Primal maksimasi dengan kendala ≤ memiliki dual berupa minimasi dengan kendala ≥.
Jika masalah primal memiliki solusi optimal, maka pada dual akan berlaku sifat…
Sifat utama dualitas menyatakan bahwa jika primal memiliki solusi optimal maka dual juga memiliki solusi optimal dengan nilai fungsi tujuan yang sama.
Dalam hubungan primal-dual, nilai variabel dual pada optimalitas disebut juga sebagai…
Nilai variabel dual pada solusi optimal sering disebut sebagai harga bayangan karena menunjukkan perubahan nilai fungsi tujuan akibat perubahan satu unit sumber daya.
Jika primal adalah masalah minimasi dengan kendala ≥, maka dual dari masalah tersebut adalah…
Primal minimasi dengan kendala ≥ memiliki dual berupa maksimasi dengan kendala ≤.
Dalam model dualitas, jika kendala primal berbentuk persamaan, maka variabel dual yang bersesuaian bersifat…
Kendala persamaan pada primal menyebabkan variabel dual yang bersesuaian tidak terbatas tandanya (unrestricted in sign).
Metode simpleks-dual digunakan untuk menyelesaikan masalah program linear yang…
Metode simpleks-dual digunakan ketika solusi awal tidak fisibel tetapi sudah memenuhi kondisi optimalitas.
Langkah pertama dalam metode simpleks-dual adalah memastikan bahwa baris fungsi tujuan sudah memenuhi kondisi…
Metode simpleks-dual dimulai dari tabel yang sudah optimal (semua koefisien baris tujuan ber tanda sesuai) tetapi belum fisibel.
Dalam metode simpleks-dual, variabel yang keluar basis adalah variabel basis dengan nilai paling…
Variabel basis dengan nilai negatif yang paling besar (paling negatif) dipilih untuk keluar basis agar mencapai fisibilitas.
Dalam metode simpleks-dual, rasio untuk menentukan variabel yang masuk basis dihitung dari…
Rasio dihitung dengan membagi koefisien baris tujuan (yang bertanda sesuai) dengan koefisien baris kendala pada kolom pivot, lalu dipilih rasio terkecil.
Jika dalam metode simpleks-dual semua koefisien pada baris variabel yang akan keluar basis bernilai non-negatif, maka masalah tersebut…
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).
Dalam metode simpleks revisi, matriks yang digunakan untuk memperbarui solusi adalah…
Metode simpleks revisi menggunakan invers dari matriks basis untuk memperbarui solusi dan menghitung koefisien yang diperlukan.
Keuntungan utama metode simpleks revisi dibandingkan metode simpleks biasa adalah…
Metode simpleks revisi hanya menghitung elemen yang diperlukan, sehingga lebih efisien dalam penggunaan memori dan perhitungan.
Dalam pemrograman parametrik, perubahan parameter pada koefisien fungsi tujuan akan mempengaruhi…
Perubahan koefisien fungsi tujuan mengubah kemiringan garis fungsi tujuan, yang dapat mengubah titik optimal tanpa mengubah daerah fisibel.
Dalam pemrograman parametrik, jika suatu parameter terus diubah dan solusi optimal berubah, maka kondisi yang harus dipenuhi agar solusi tetap optimal adalah…
Untuk mempertahankan optimalitas, koefisien baris fungsi tujuan harus tetap memenuhi kondisi optimalitas (non-negatif untuk maksimasi) selama perubahan parameter.
Dalam Metode Simpleks Revisi, matriks basis (B) digunakan untuk menghitung koefisien variabel nonbasis. Manakah dari pernyataan berikut yang BENAR mengenai peran matriks basis?
Matriks basis B adalah submatriks dari matriks koefisien kendala yang terdiri dari kolom-kolom variabel basis, dan berukuran m x m.
Dalam pemrograman parametrik, ketika nilai parameter λ berubah secara kontinu, bagaimana perubahan solusi optimal terjadi jika koefisien fungsi tujuan berubah?
Dalam pemrograman parametrik, ketika koefisien fungsi tujuan berubah secara linear dengan parameter λ, solusi optimal berubah secara diskrit pada titik kritis yang disebut breakpoint.
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?
Perubahan parameter λ pada koefisien fungsi tujuan dapat mengubah koefisien relatif variabel dan menyebabkan variabel lain masuk ke basis pada titik kritis tertentu.
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?
Ketika λ melampaui batas atas stabilitas basis, solusi basis tidak lagi layak, sehingga dual simplex digunakan untuk mencari basis baru yang layak.
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?
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.
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?
Perubahan ruas kanan menyebabkan nilai variabel basis berubah. Basis tidak layak jika salah satu nilai variabel basis menjadi negatif, yang menandakan perlunya dual pivot.
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?
Pada solusi optimal relaksasi linear, jika ada variabel yang bernilai pecahan, dilakukan pencabangan untuk memaksa variabel tersebut menjadi bilangan bulat.
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?
Percabangan dilakukan dengan menambahkan kendala x1 ≤ 2 dan x1 ≥ 3, karena nilai pecahan 2.5 dipisah menjadi dua daerah integer yang tidak tumpang tindih.
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?
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).
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?
Kedua cabang memiliki nilai Z lebih besar dari best solution integer (20), sehingga keduanya berpotensi menghasilkan solusi integer yang lebih baik dan perlu dilanjutkan.
Dalam algoritma Branch and Bound, manakah kondisi yang menyebabkan suatu node dinyatakan sebagai terminal node (tidak perlu dicabangkan lagi)?
Semua kondisi di atas menyebabkan node tidak perlu dicabangkan: solusi integer layak, tidak layak, atau batas atas lebih rendah dari best solution.
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?
Dengan x1=4, dari kendala 3×1 + x2 ≤ 12, diperoleh x2=0. Z=3(4)+2(0)=12.
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:
Nilai Z=17 lebih rendah dari best solution integer 18, sehingga subproblem tersebut tidak akan menghasilkan solusi yang lebih baik (pruning).
Dalam metode Branch and Bound untuk masalah minimasi, manakah pernyataan yang SALAH?
Tidak ada aturan baku bahwa variabel dengan nilai pecahan terkecil harus dipilih; pemilihan variabel untuk pencabangan bisa berdasarkan berbagai aturan.
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?
Subproblem 3 menghasilkan solusi integer layak dengan Z=18, sehingga menjadi best solution integer sementara.
Dalam pemrograman integer, mengapa metode Branch and Bound memerlukan eksplorasi cabang?
Eksplorasi cabang dilakukan untuk memeriksa kemungkinan solusi integer secara implisit tanpa harus mengevaluasi semua titik integer satu per satu.
Soal simpleks dengan variabel surplus langsung bikin sadar kalau Pemrograman Linear itu soal logika bertahap. Setelah latihan di atas, kamu mungkin sadar sendiri bagian mana yang biasanya bikin mikir dua kali, terutama nomor tentang dualitas atau metode cabang dan batas. Itu wajar, sih. Coba ulang satu modul paling lambat setiap malem sambil ngerjain beberapa soal dari bank soal UAS UT biar polanya makin keingat.
Kalau Ujian UT biasanya campuran soal hitungan dari UTM dan analisis singkat khas UO, di matkul MATA4230 Pemrograman Linear bagian tabel simpleks sama bentuk baku wajib dikuasain betul. Bagian pemrograman integer juga sering muncul walau cuma satu soal doang. Santai aja, karena soal UT tipe hitungan itu pasti ada polanya kok. Tinggal latihan rutin, sisanya soal ngatur waktu pas ujian.
