×

Menguasai Program Linier Bulat Lewat Contoh Soal dan Pembahasan Lengkap

Menguasai Program Linier Bulat Lewat Contoh Soal dan Pembahasan Lengkap
contoh soal

Program linier bulat (integer linear programming) adalah salah satu metode dalam matematika terapan dan operasi riset yang digunakan untuk memecahkan masalah optimisasi di mana variabel keputusan harus berupa bilangan bulat. Berbeda dengan program linier biasa, program linier bulat sering digunakan ketika solusi pecahan tidak praktis, misalnya dalam penjadwalan, pengalokasian sumber daya, dan perencanaan produksi.

Artikel ini akan membahas konsep dasar program linier bulat, langkah-langkah penyelesaiannya, serta memberikan contoh soal lengkap beserta pembahasan. Dengan pemahaman yang tepat, siswa maupun mahasiswa dapat lebih mudah memahami metode ini dan menerapkannya dalam berbagai kasus nyata.

Baca juga : Apa Itu Matematika? Sebuah Petualangan Menuju Dunia Logika dan Pengetahuan

Konsep Dasar Program Linier Bulat

  1. Definisi
    Program linier bulat adalah masalah optimisasi linier dengan syarat:

Maks/min Z=c1x1+c2x2+…+cnxn\text{Maks/min } Z = c_1x_1 + c_2x_2 + … + c_nx_nMaks/min Z=c1​x1​+c2​x2​+…+cn​xn​

🔖 Baca juga:
Kumpulan Contoh Soal Gaya Belajar Visual Auditori dan Kinestetik

dengan kendala: a11x1+a12x2+…+a1nxn≤b1a_{11}x_1 + a_{12}x_2 + … + a_{1n}x_n \leq b_1 a11​x1​+a12​x2​+…+a1n​xn​≤b1​

dan semua xix_ixi​ harus bilangan bulat.

  1. Jenis Variabel Bulat
  • Binary integer: xi=0x_i = 0xi​=0 atau 111, sering untuk keputusan ya/tidak.
  • General integer: xi=0,1,2,…x_i = 0, 1, 2, …xi​=0,1,2,…
  1. Perbedaan dengan Program Linier Biasa
  • Solusi program linier biasa bisa berupa bilangan pecahan.
  • Program linier bulat mengharuskan solusi berupa bilangan bulat.
  • Akibatnya, solusi bulat biasanya lebih sulit ditemukan dan memerlukan metode khusus seperti branch and bound atau enumerasi.

Langkah Penyelesaian Program Linier Bulat

  1. Identifikasi variabel keputusan
    Tentukan variabel yang mewakili keputusan dalam masalah.
  2. Tentukan fungsi tujuan (objective function)
    Fungsi tujuan bisa maksimisasi (profit, output) atau minimisasi (biaya, waktu).
  3. Tentukan kendala (constraints)
    Kendala berupa batasan sumber daya, kapasitas, waktu, atau jumlah minimum/maksimum.
  4. Tentukan syarat bulat
    Semua variabel keputusan harus bilangan bulat.
  5. Penyelesaian
  • Metode enumerasi (cocok untuk soal kecil).
  • Branch and bound (untuk soal kompleks).
  • Software (Excel Solver, Lingo, Matlab, dsb.)

Contoh Soal Program Linier Bulat dan Pembahasan

Soal 1 (Sederhana – Maksimisasi)
Sebuah pabrik ingin memproduksi dua jenis produk, A dan B.

  • Profit per produk A = 5 juta, produk B = 8 juta.
  • Ketersediaan bahan baku: 40 unit.
  • Produk A membutuhkan 2 unit bahan baku per buah, produk B membutuhkan 4 unit.
  • Tujuan: Maksimalkan profit.
  • Variabel keputusan harus bilangan bulat.

Model Matematika:
Variabel: x=jumlah produk A,y=jumlah produk Bx = \text{jumlah produk A}, \quad y = \text{jumlah produk B} x=jumlah produk A,y=jumlah produk B

Fungsi tujuan: Z=5x+8y→maksimalZ = 5x + 8y \to \text{maksimal} Z=5x+8y→maksimal

Kendala: 2x+4y≤402x + 4y \leq 40 2x+4y≤40 x,y≥0,bilangan bulatx, y \geq 0, \text{bilangan bulat}x,y≥0,bilangan bulat

Pembahasan:

  1. Coba nilai y maksimal dulu: y = 10 → 4×10 = 40 → x = 0
    Profit = 5(0)+8(10)=80
  2. Coba y=9 → 4×9=36 → sisa bahan 4 unit → x = 2
    Profit = 5×2 + 8×9 = 10 + 72 = 82 ✅
  3. Coba y=8 → 4×8=32 → sisa bahan 8 unit → x = 4
    Profit = 5×4 + 8×8 = 20 + 64 = 84 ✅
  4. Coba y=7 → 4×7=28 → sisa bahan 12 unit → x=6
    Profit = 5×6 + 8×7 = 30 + 56 = 86 ✅
  5. Coba y=6 → 4×6=24 → sisa bahan 16 unit → x=8
    Profit = 5×8 + 8×6 = 40 + 48 = 88 ✅
  6. Coba y=5 → 4×5=20 → sisa bahan 20 unit → x=10
    Profit = 5×10 + 8×5 = 50 + 40 = 90 ✅
  7. Coba y=4 → 4×4=16 → sisa bahan 24 unit → x=12
    Profit = 5×12 + 8×4 = 60 + 32 = 92 ✅
  8. Coba y=3 → 4×3=12 → sisa bahan 28 unit → x=14
    Profit = 5×14 + 8×3 = 70 + 24 = 94 ✅
  9. Coba y=2 → 4×2=8 → sisa bahan 32 unit → x=16
    Profit = 5×16 + 8×2 = 80 + 16 = 96 ✅
  10. Coba y=1 → 4×1=4 → sisa bahan 36 unit → x=18
    Profit = 5×18 + 8×1 = 90 + 8 = 98 ✅
  11. Coba y=0 → x=20
    Profit = 5×20 + 8×0 = 100 ✅ ✅

Solusi optimal: x=20, y=0, Profit maksimal = 100 juta

Soal 2 (Binary Integer)
Sebuah perusahaan ingin memilih proyek yang tersedia: P1, P2, P3.

  • Profit P1=50 juta, P2=60 juta, P3=40 juta.
  • Perusahaan hanya bisa memilih dua proyek karena keterbatasan dana.
    Tentukan proyek yang harus dipilih agar profit maksimal.

Model Matematika:
Variabel biner: x1,x2,x3={1dipilih0tidakx_1, x_2, x_3 = \begin{cases}1 & dipilih \\ 0 & tidak\end{cases} x1​,x2​,x3​={10​dipilihtidak​

Fungsi tujuan: Z=50×1+60×2+40×3→maksimumZ = 50x_1 + 60x_2 + 40x_3 \to maksimum Z=50×1​+60×2​+40×3​→maksimum

Kendala: x1+x2+x3≤2x_1 + x_2 + x_3 \le 2 x1​+x2​+x3​≤2

Pembahasan:

  • Kombinasi terbaik 2 proyek dengan profit terbesar: P1 + P2 = 50+60=110 ✅
  • P1 + P3 = 50+40=90
  • P2 + P3 = 60+40=100
  • Optimal → pilih P1 dan P2, Z maksimal = 110 juta

Soal 3 (Soal Kendala Kompleks)
Sebuah pabrik ingin memproduksi meja dan kursi:

  • Meja profit 200 rb, kursi 150 rb
  • Bahan kayu tersedia 12 unit
  • Meja butuh 3 unit, kursi butuh 2 unit
  • Tenaga kerja tersedia 10 jam
  • Meja butuh 2 jam, kursi butuh 1 jam

Tentukan kombinasi produksi meja dan kursi untuk profit maksimal.

Model Matematika:
Variabel: x = meja, y = kursi Z=200x+150y→maksimalZ = 200x + 150y \to maksimal Z=200x+150y→maksimal

Kendala: 3x+2y≤12(bahankayu)3x + 2y \le 12 \quad (bahan kayu) 3x+2y≤12(bahankayu) 2x+1y≤10(tenagakerja)2x + 1y \le 10 \quad (tenaga kerja) 2x+1y≤10(tenagakerja) x,y≥0,bilangan bulatx, y \ge 0, \text{bilangan bulat}x,y≥0,bilangan bulat

Pembahasan (enumerasi):

  1. Coba x=0 → 2y≤12 & y≤10 → y max=6 → Z=0+150*6=900
  2. x=1 → 3+2y≤12 → 2y≤9 → y≤4, 2+ y≤10 → y≤8 → y max=4 → Z=200+150*4=200+600=800 ❌
  3. x=2 → 6+2y≤12 → 2y≤6 → y≤3, 4+y≤10 → y≤6 → y max=3 → Z=400+150*3=400+450=850
  4. x=3 → 9+2y≤12 → 2y≤3 → y≤1, 6+ y≤10 → y≤4 → y max=1 → Z=600+150*1=750 ❌
  5. x=4 → 12+2y≤12 → 2y≤0 → y=0, 8+0≤10 ✅ → Z=200*4=800 ❌

Solusi optimal: x=2, y=3 → Profit maksimal = 850 rb

Tips Menguasai Program Linier Bulat

  1. Tentukan variabel keputusan dengan jelas.
  2. Buat fungsi tujuan dan kendala dengan teliti.
  3. Gunakan metode enumerasi untuk soal kecil, branch and bound untuk soal besar.
  4. Periksa semua kombinasi bilangan bulat yang memenuhi kendala.
  5. Gunakan software solver untuk soal kompleks agar lebih efisien.

Baca juga : FEB Teknokrat Hadirkan Vice President Pegadaian: Bedah Peluang Investasi Emas

Kesimpulan
Program linier bulat adalah alat penting dalam optimisasi nyata di dunia industri, bisnis, dan manajemen sumber daya. Dengan latihan soal sederhana hingga kompleks, siswa dapat memahami cara menyusun model matematika, menerapkan kendala, dan menentukan solusi optimal dengan bilangan bulat.

Latihan soal berbasis kasus nyata, seperti pembuatan produk atau pemilihan proyek, membuat konsep lebih mudah dipahami dan siap diaplikasikan dalam ujian maupun studi kasus nyata.

Penulis : adilah az-zahra

Tag

Related Posts

Post Comment

You May Have Missed