20 Contoh Soal Program Linear & Pembahasannya

by ADMIN 46 views
Iklan Headers

Halo, para pejuang matematika! Kali ini kita bakal ngobrolin soal program linear. Pasti banyak yang bertanya-tanya, nih, apa sih program linear itu dan kenapa kita perlu mempelajarinya? Tenang aja, guys, program linear itu sebenarnya seru banget lho kalau kita paham konsepnya. Intinya, program linear itu adalah salah satu metode dalam matematika yang digunakan untuk mencari nilai optimal (maksimum atau minimum) dari suatu fungsi tujuan, dengan mempertimbangkan kendala-kendala yang ada. Kendala ini biasanya diwujudkan dalam bentuk pertidaksamaan linear.

Wah, kedengarannya keren ya? Tapi jangan pusing dulu. Konsep program linear ini banyak banget aplikasinya di kehidupan sehari-hari, lho. Mulai dari masalah bisnis, ekonomi, sampai urusan produksi. Misalnya, seorang pengusaha mau menentukan berapa banyak produk A dan produk B yang harus diproduksi agar keuntungannya maksimal, tapi dengan modal dan bahan baku yang terbatas. Nah, di sinilah program linear berperan!

Di artikel ini, kita akan membahas 20 contoh soal program linear yang mencakup berbagai tingkatan kesulitan, mulai dari yang dasar sampai yang lebih menantang. Nggak cuma soalnya aja, tapi kita juga akan bahas pembahasannya secara tuntas biar kalian makin jago dan nggak salah langkah. Siap? Yuk, kita mulai petualangan kita di dunia program linear!

Memahami Konsep Dasar Program Linear

Sebelum kita terjun ke contoh soalnya, penting banget nih buat kita semua paham dulu konsep dasarnya. Apa sih yang dimaksud dengan fungsi tujuan? Fungsi tujuan ini adalah sebuah fungsi matematis yang ingin kita cari nilai optimalnya, apakah itu nilai maksimum atau minimum. Biasanya, fungsi tujuan ini merepresentasikan keuntungan, biaya, atau hasil yang ingin dicapai.

Contohnya, kalau dalam kasus pengusaha tadi, fungsi tujuannya bisa jadi: Keuntungan = (Harga Jual Produk A - Biaya Produksi Produk A) x Jumlah Produk A + (Harga Jual Produk B - Biaya Produksi Produk B) x Jumlah Produk B. Nah, kita ingin mencari berapa jumlah Produk A dan Produk B yang bikin nilai 'Keuntungan' ini sebesar-besarnya.

Terus, apa lagi yang perlu kita pahami? Ada yang namanya kendala atau batasan. Kendala ini adalah kondisi-kondisi yang membatasi kita dalam mencapai tujuan. Dalam program linear, kendala ini biasanya berupa pertidaksamaan linear. Contohnya, jumlah bahan baku A yang tersedia tidak boleh lebih dari 100 unit, atau waktu produksi total tidak boleh melebihi 8 jam. Kendala-kendala inilah yang bikin masalahnya jadi menarik dan nggak sesederhana menghitung untung rugi biasa.

Selain itu, ada juga yang namanya variabel keputusan. Variabel keputusan ini adalah hal-hal yang bisa kita ubah atau tentukan untuk mencapai tujuan. Dalam contoh pengusaha tadi, variabel keputusannya adalah jumlah Produk A yang diproduksi dan jumlah Produk B yang diproduksi. Kita perlu mencari nilai dari variabel-variabel inilah yang akan membuat fungsi tujuan menjadi optimal, sambil memenuhi semua kendala yang ada.

Untuk menyelesaikan soal program linear, biasanya kita akan menggunakan metode grafik atau metode simplex. Metode grafik ini cocok untuk masalah yang hanya memiliki dua variabel keputusan, karena kita bisa memvisualisasikan kendala-kendalanya dalam bentuk grafik dua dimensi dan mencari titik-titik pojok yang memenuhi semua kendala. Titik-titik pojok inilah yang nanti akan diuji di fungsi tujuan untuk mencari nilai optimalnya.

Sedangkan metode simplex itu lebih canggih dan bisa digunakan untuk masalah dengan banyak variabel keputusan. Tapi tenang aja, untuk sebagian besar soal program linear di tingkat SMA atau awal perkuliahan, metode grafik biasanya sudah cukup memadai. Yang penting, kalian paham dulu cara mengubah soal cerita menjadi model matematika yang terdiri dari fungsi tujuan dan sistem pertidaksamaan linear dari kendala-kendalanya. Itu langkah paling krusial, guys!

Soal 1-5: Dasar Program Linear

Oke, guys, sekarang saatnya kita mulai latihan soalnya. Kita akan mulai dari yang paling dasar dulu ya, biar kalian kebayang gimana sih bentuk soal program linear itu dan bagaimana cara menyelesaikannya. Pastikan kalian siapin catatan dan pulpen ya, biar bisa sambil latihan!

Soal 1: Seorang pengrajin membuat dua jenis kerajinan tangan, yaitu vas bunga dan patung. Untuk membuat satu vas bunga, dibutuhkan waktu 2 jam kerja dan biaya Rp10.000. Untuk membuat satu patung, dibutuhkan waktu 3 jam kerja dan biaya Rp20.000. Pengrajin tersebut memiliki waktu kerja maksimal 60 jam per minggu dan modal maksimal Rp400.000 per minggu. Jika keuntungan dari penjualan satu vas bunga adalah Rp30.000 dan satu patung adalah Rp50.000, tentukan keuntungan maksimal yang dapat diperoleh pengrajin tersebut!

Pembahasan Soal 1: Pertama-tama, kita perlu menentukan variabel keputusannya. Misalkan:

  • x = jumlah vas bunga yang diproduksi
  • y = jumlah patung yang diproduksi

Selanjutnya, kita susun fungsi tujuan yang ingin dimaksimalkan, yaitu keuntungan:

  • Keuntungan (Z) = 30.000x + 50.000y

Kemudian, kita buat sistem pertidaksamaan linear dari kendala-kendala yang ada:

  1. Kendala waktu kerja: 2x + 3y ≤ 60 (total waktu kerja tidak boleh lebih dari 60 jam)
  2. Kendala modal: 10.000x + 20.000y ≤ 400.000 (total biaya tidak boleh lebih dari Rp400.000). Kita bisa sederhanakan menjadi x + 2y ≤ 40 dengan membagi kedua sisi dengan 10.000.
  3. Kendala non-negatif (jumlah kerajinan tidak mungkin negatif): x ≥ 0 y ≥ 0

Sekarang, kita gambar grafik dari pertidaksamaan-pertidaksamaan tersebut untuk mencari daerah penyelesaiannya. Titik-titik pojok dari daerah penyelesaian inilah yang akan kita uji pada fungsi tujuan.

  • Untuk 2x + 3y = 60: Jika x = 0, maka 3y = 60 -> y = 20. Titik (0, 20). Jika y = 0, maka 2x = 60 -> x = 30. Titik (30, 0).
  • Untuk x + 2y = 40: Jika x = 0, maka 2y = 40 -> y = 20. Titik (0, 20). Jika y = 0, maka x = 40. Titik (40, 0).

Perhatikan bahwa kedua garis melewati titik (0, 20). Kita perlu mencari titik potong kedua garis: Dari x + 2y = 40, kita dapat x = 40 - 2y. Substitusikan ke 2x + 3y = 60: 2(40 - 2y) + 3y = 60 80 - 4y + 3y = 60 80 - y = 60 y = 80 - 60 y = 20 Jika y = 20, maka x = 40 - 2(20) = 40 - 40 = 0. Jadi titik potongnya adalah (0, 20).

Wah, sepertinya ada kesalahan dalam perhitungan titik potong saya atau soalnya, karena kedua garis justru bertemu di sumbu y. Mari kita periksa lagi persamaan garisnya. Oh iya, persamaan kedua adalah x + 2y = 40. Mari kita cari titik potongnya lagi. Dari x + 2y = 40, kita dapatkan x = 40 - 2y. Substitusikan ke 2x + 3y = 60: 2(40 - 2y) + 3y = 60 80 - 4y + 3y = 60 80 - y = 60 y = 20. Jika y = 20, maka x = 40 - 2(20) = 0. Titik potongnya memang (0, 20).

Ini artinya, salah satu kendala mungkin tidak terlalu membatasi dibandingkan yang lain, atau memang titik potongnya ada di sumbu. Mari kita gambar ulang daerah penyelesaiannya.

  • Garis 1: 2x + 3y = 60. Memotong sumbu x di (30, 0) dan sumbu y di (0, 20).
  • Garis 2: x + 2y = 40. Memotong sumbu x di (40, 0) dan sumbu y di (0, 20).

Karena kedua pertidaksamaan adalah '≤', maka daerah penyelesaiannya adalah di bawah kedua garis tersebut. Dengan tambahan x ≥ 0 dan y ≥ 0, daerah penyelesaiannya dibatasi oleh sumbu x, sumbu y, dan garis 2x + 3y = 60 (karena garis ini lebih 'ketat' di dekat titik potong di sumbu x dibandingkan garis kedua).

Titik-titik pojok daerah penyelesaian adalah:

  • (0, 0)
  • (30, 0) (titik potong 2x + 3y = 60 dengan sumbu x)
  • (0, 20) (titik potong kedua garis dengan sumbu y)

Sekarang, kita substitusikan titik-titik pojok ini ke fungsi tujuan Z = 30.000x + 50.000y:

  • Di (0, 0): Z = 30.000(0) + 50.000(0) = 0
  • Di (30, 0): Z = 30.000(30) + 50.000(0) = 900.000
  • Di (0, 20): Z = 30.000(0) + 50.000(20) = 1.000.000

Jadi, keuntungan maksimal yang dapat diperoleh pengrajin tersebut adalah Rp1.000.000 dengan memproduksi 0 vas bunga dan 20 patung.

Soal 2: Sebuah toko roti memproduksi dua jenis kue, yaitu kue coklat dan kue keju. Untuk membuat satu kue coklat, dibutuhkan 50 gram tepung dan 20 gram gula. Untuk membuat satu kue keju, dibutuhkan 40 gram tepung dan 30 gram gula. Persediaan tepung yang dimiliki toko adalah 2500 gram dan persediaan gula adalah 1500 gram. Jika keuntungan dari penjualan satu kue coklat adalah Rp2.000 dan satu kue keju adalah Rp3.000, tentukan keuntungan maksimal yang dapat diperoleh toko roti tersebut!

Pembahasan Soal 2: Variabel keputusan:

  • x = jumlah kue coklat yang diproduksi
  • y = jumlah kue keju yang diproduksi

Fungsi tujuan (Keuntungan, Z):

  • Z = 2.000x + 3.000y

Sistem pertidaksamaan linear dari kendala:

  1. Kendala tepung: 50x + 40y ≤ 2500 (disederhanakan menjadi 5x + 4y ≤ 250)
  2. Kendala gula: 20x + 30y ≤ 1500 (disederhanakan menjadi 2x + 3y ≤ 150)
  3. Kendala non-negatif: x ≥ 0 y ≥ 0

Gambar grafik dan cari titik-titik pojok:

  • Garis 1: 5x + 4y = 250 Jika x = 0, 4y = 250 -> y = 62.5. Titik (0, 62.5). Jika y = 0, 5x = 250 -> x = 50. Titik (50, 0).
  • Garis 2: 2x + 3y = 150 Jika x = 0, 3y = 150 -> y = 50. Titik (0, 50). Jika y = 0, 2x = 150 -> x = 75. Titik (75, 0).

Cari titik potong kedua garis: Dari 2x + 3y = 150, kita dapat 2x = 150 - 3y -> x = 75 - 1.5y. Substitusikan ke 5x + 4y = 250: 5(75 - 1.5y) + 4y = 250 375 - 7.5y + 4y = 250 375 - 3.5y = 250 3.5y = 375 - 250 3.5y = 125 y = 125 / 3.5 y = 250 / 7 ≈ 35.71

Jika y = 250/7, maka x = 75 - 1.5(250/7) = 75 - (3/2)(250/7) = 75 - 375/7 = (525 - 375)/7 = 150/7 ≈ 21.43. Titik potongnya adalah (150/7, 250/7).

Titik-titik pojok daerah penyelesaian adalah:

  • (0, 0)
  • (50, 0) (titik potong 5x + 4y = 250 dengan sumbu x)
  • (0, 50) (titik potong 2x + 3y = 150 dengan sumbu y)
  • (150/7, 250/7) (titik potong kedua garis)

Uji titik pojok pada fungsi tujuan Z = 2.000x + 3.000y:

  • Di (0, 0): Z = 2.000(0) + 3.000(0) = 0
  • Di (50, 0): Z = 2.000(50) + 3.000(0) = 100.000
  • Di (0, 50): Z = 2.000(0) + 3.000(50) = 150.000
  • Di (150/7, 250/7): Z = 2.000(150/7) + 3.000(250/7) = (300.000 + 750.000) / 7 = 1.050.000 / 7 ≈ 150.000

Wah, hasil perhitungan titik potong (150/7, 250/7) memberikan nilai Z yang hampir sama dengan titik (0, 50). Mari kita hitung eksaknya untuk titik potongnya: Z = 1.050.000 / 7 Z = 150.000

Artinya, ada kemungkinan nilai keuntungan maksimal terjadi di sepanjang segmen garis yang menghubungkan (0, 50) dan titik potongnya (150/7, 250/7) jika fungsi tujuan sejajar dengan salah satu kendala. Namun, jika kita lihat nilai Z yang didapat, titik (0, 50) memberikan keuntungan Rp150.000. Titik (50, 0) memberikan Rp100.000. Titik potong (150/7, 250/7) memberikan Z = 1.050.000/7 = 150.000.

Jika kita amati lebih teliti, titik (0, 50) berarti memproduksi 0 kue coklat dan 50 kue keju. Dengan ini, total tepung yang terpakai adalah 50(0) + 40(50) = 2000 gram (sisa 500g). Total gula yang terpakai 20(0) + 30(50) = 1500 gram (pas).

Titik potong (150/7, 250/7) berarti memproduksi sekitar 21 kue coklat dan 35 kue keju. Ini adalah nilai yang tidak bulat, yang mungkin tidak realistis dalam produksi kue. Dalam kasus seperti ini, seringkali kita perlu mempertimbangkan pembulatan ke bawah untuk mendapatkan solusi integer yang valid, atau memang soal ini mengizinkan solusi pecahan.

Jika kita anggap solusi integer, kita perlu mengevaluasi titik-titik integer di sekitar (150/7, 250/7) yang memenuhi kendala. Namun, berdasarkan perhitungan titik pojok, nilai maksimum Rp150.000 tercapai di titik (0, 50) dan juga di titik potong (150/7, 250/7). Jadi, keuntungan maksimalnya adalah Rp150.000.

Soal 3: Nilai maksimum dari fungsi objektif f(x, y) = 5x + 4y yang memenuhi syarat x + y ≤ 8, 2x + y ≤ 10, x ≥ 0, dan y ≥ 0 adalah...

Pembahasan Soal 3: Di sini, fungsi tujuan dan kendalanya sudah diberikan dalam bentuk matematis, jadi kita tinggal mencari daerah penyelesaiannya.

Fungsi tujuan: f(x, y) = 5x + 4y Kendala:

  1. x + y ≤ 8
  2. 2x + y ≤ 10
  3. x ≥ 0
  4. y ≥ 0

Gambar grafik:

  • Garis 1: x + y = 8 (titik (0, 8) dan (8, 0))
  • Garis 2: 2x + y = 10 (titik (0, 10) dan (5, 0))

Cari titik potong kedua garis: Dari x + y = 8 -> y = 8 - x. Substitusikan ke 2x + y = 10: 2x + (8 - x) = 10 x + 8 = 10 x = 2 Jika x = 2, maka y = 8 - 2 = 6. Titik potongnya adalah (2, 6).

Titik-titik pojok daerah penyelesaian (yang dibatasi oleh x ≥ 0, y ≥ 0, dan kedua garis di bawahnya):

  • (0, 0)
  • (5, 0) (titik potong 2x + y = 10 dengan sumbu x)
  • (0, 8) (titik potong x + y = 8 dengan sumbu y)
  • (2, 6) (titik potong kedua garis)

Uji titik pojok pada fungsi tujuan f(x, y) = 5x + 4y:

  • Di (0, 0): f(0, 0) = 5(0) + 4(0) = 0
  • Di (5, 0): f(5, 0) = 5(5) + 4(0) = 25
  • Di (0, 8): f(0, 8) = 5(0) + 4(8) = 32
  • Di (2, 6): f(2, 6) = 5(2) + 4(6) = 10 + 24 = 34

Nilai maksimum adalah 34.

Soal 4: Suatu pekerjaan dapat diselesaikan dalam waktu t jam dengan biaya C juta rupiah. Hubungan antara t dan C dinyatakan oleh fungsi C(t) = t^2 - 10t + 45. Jika waktu pengerjaan dibatasi 2 ≤ t ≤ 8, tentukan biaya minimum yang mungkin dikeluarkan!

Pembahasan Soal 4: Ini soal program linear tapi sedikit berbeda karena melibatkan fungsi kuadrat. Namun, prinsip mencari nilai minimum dalam interval tertentu tetap berlaku. Kita perlu mencari nilai minimum dari fungsi C(t) = t^2 - 10t + 45 pada interval [2, 8].

Fungsi kuadrat C(t) = t^2 - 10t + 45 adalah parabola yang terbuka ke atas. Nilai minimumnya terjadi di titik puncak atau di ujung interval jika titik puncak berada di luar interval.

Untuk mencari titik puncak parabola at^2 + bt + c, absisnya adalah -b / 2a. Dalam kasus ini, a = 1, b = -10. Absis titik puncak (waktu pengerjaan) = -(-10) / (2 * 1) = 10 / 2 = 5.

Karena t = 5 berada dalam interval [2, 8], maka nilai minimum terjadi di t = 5.

Substitusikan t = 5 ke dalam fungsi C(t): C(5) = (5)^2 - 10(5) + 45 C(5) = 25 - 50 + 45 C(5) = 20

Kita juga perlu memeriksa nilai di ujung interval untuk memastikan:

  • Di t = 2: C(2) = (2)^2 - 10(2) + 45 = 4 - 20 + 45 = 29
  • Di t = 8: C(8) = (8)^2 - 10(8) + 45 = 64 - 80 + 45 = 29

Jadi, biaya minimum yang mungkin dikeluarkan adalah 20 juta rupiah.

Soal 5: Sebuah perusahaan mebel memproduksi meja dan kursi. Untuk memproduksi satu meja, diperlukan 4 jam kerja dan 1 meter kubik kayu. Untuk memproduksi satu kursi, diperlukan 2 jam kerja dan 0.5 meter kubik kayu. Perusahaan memiliki persediaan 240 jam kerja dan 50 meter kubik kayu. Jika keuntungan per meja adalah Rp300.000 dan per kursi adalah Rp150.000, tentukan kombinasi produksi meja dan kursi agar keuntungan maksimal.

Pembahasan Soal 5: Variabel keputusan:

  • x = jumlah meja yang diproduksi
  • y = jumlah kursi yang diproduksi

Fungsi tujuan (Keuntungan, Z):

  • Z = 300.000x + 150.000y (dapat disederhanakan menjadi Z = 3x + 1.5y jika kita bekerja dengan satuan ratus ribu)

Sistem pertidaksamaan linear dari kendala:

  1. Kendala jam kerja: 4x + 2y ≤ 240 (disederhanakan menjadi 2x + y ≤ 120)
  2. Kendala kayu: 1x + 0.5y ≤ 50 (disederhanakan menjadi 2x + y ≤ 100)
  3. Kendala non-negatif: x ≥ 0 y ≥ 0

Gambar grafik:

  • Garis 1: 2x + y = 120 (titik (0, 120) dan (60, 0))
  • Garis 2: 2x + y = 100 (titik (0, 100) dan (50, 0))

Perhatikan bahwa kedua garis memiliki gradien yang sama (m = -2). Ini berarti kedua garis tersebut sejajar. Karena kendala berbentuk '≤', maka daerah penyelesaiannya adalah di bawah kedua garis. Dengan tambahan x ≥ 0 dan y ≥ 0, daerah penyelesaiannya adalah yang dibatasi oleh sumbu x, sumbu y, dan garis yang lebih 'ketat', yaitu 2x + y = 100.

Titik-titik pojok daerah penyelesaian adalah:

  • (0, 0)
  • (50, 0) (titik potong 2x + y = 100 dengan sumbu x)
  • (0, 100) (titik potong 2x + y = 100 dengan sumbu y)

Uji titik pojok pada fungsi tujuan Z = 300.000x + 150.000y:

  • Di (0, 0): Z = 300.000(0) + 150.000(0) = 0
  • Di (50, 0): Z = 300.000(50) + 150.000(0) = 15.000.000
  • Di (0, 100): Z = 300.000(0) + 150.000(100) = 15.000.000

Dalam kasus ini, nilai maksimum terjadi di dua titik pojok, yaitu (50, 0) dan (0, 100). Ini berarti, keuntungan maksimal sebesar Rp15.000.000 dapat dicapai dengan memproduksi 50 meja dan 0 kursi, ATAU 0 meja dan 100 kursi. Selain itu, setiap kombinasi (x, y) yang terletak pada segmen garis yang menghubungkan kedua titik tersebut juga akan memberikan keuntungan maksimal, selama kombinasi tersebut memenuhi semua kendala.

Namun, ada baiknya kita periksa kembali kendala. Garis 2x + y = 120 memberikan batasan yang lebih 'longgar' daripada 2x + y = 100. Jadi, seharusnya daerah penyelesaiannya dibatasi oleh 2x + y = 100. Jika kita menguji titik (60,0) pada kendala kedua: 2(60) + 0 = 120, ini melebihi 100. Jadi (60,0) tidak valid.

Jika daerah penyelesaian dibatasi oleh 2x + y = 100, maka titik pojoknya adalah (0,0), (50,0), dan (0,100). Di titik (50,0), Z = 15.000.000. Di titik (0,100), Z = 15.000.000. Jadi, keuntungan maksimalnya memang Rp15.000.000.

Kombinasi produksi yang optimal adalah memproduksi 50 meja dan 0 kursi ATAU 0 meja dan 100 kursi, atau kombinasi lain di sepanjang garis 2x + y = 100 antara kedua titik tersebut yang memenuhi x>=0, y>=0.

Soal 6-10: Penerapan Program Linear Lebih Lanjut

Sekarang, kita akan naik level sedikit, guys! Soal-soal berikutnya akan sedikit lebih kompleks dan membutuhkan pemahaman yang lebih dalam tentang bagaimana menerjemahkan masalah sehari-hari ke dalam model matematika program linear.

Soal 6: Seorang petani memiliki lahan seluas 10 hektar. Ia berencana menanam padi dan jagung. Untuk menanam padi, diperlukan 1 liter pupuk per hektar dan menghasilkan keuntungan Rp500.000 per hektar. Untuk menanam jagung, diperlukan 2 liter pupuk per hektar dan menghasilkan keuntungan Rp700.000 per hektar. Petani tersebut memiliki persediaan pupuk sebanyak 12 liter. Berapa hektar lahan yang harus ditanami padi dan jagung agar keuntungannya maksimal?

Pembahasan Soal 6: Variabel keputusan:

  • x = luas lahan yang ditanami padi (hektar)
  • y = luas lahan yang ditanami jagung (hektar)

Fungsi tujuan (Keuntungan, Z):

  • Z = 500.000x + 700.000y

Sistem pertidaksamaan linear:

  1. Kendala luas lahan: x + y ≤ 10
  2. Kendala pupuk: 1x + 2y ≤ 12
  3. Kendala non-negatif: x ≥ 0 y ≥ 0

Gambar grafik:

  • Garis 1: x + y = 10 (titik (0, 10) dan (10, 0))
  • Garis 2: x + 2y = 12 (titik (0, 6) dan (12, 0))

Cari titik potong kedua garis: Dari x + y = 10 -> x = 10 - y. Substitusikan ke x + 2y = 12: (10 - y) + 2y = 12 10 + y = 12 y = 2 Jika y = 2, maka x = 10 - 2 = 8. Titik potongnya adalah (8, 2).

Titik-titik pojok daerah penyelesaian:

  • (0, 0)
  • (10, 0) (titik potong x + y = 10 dengan sumbu x, perlu dicek apakah memenuhi x + 2y <= 12. 10 + 2(0) = 10 <= 12. Valid)
  • (0, 6) (titik potong x + 2y = 12 dengan sumbu y, perlu dicek apakah memenuhi x + y <= 10. 0 + 6 = 6 <= 10. Valid)
  • (8, 2) (titik potong kedua garis)

Uji titik pojok pada fungsi tujuan Z = 500.000x + 700.000y:

  • Di (0, 0): Z = 0
  • Di (10, 0): Z = 500.000(10) + 700.000(0) = 5.000.000
  • Di (0, 6): Z = 500.000(0) + 700.000(6) = 4.200.000
  • Di (8, 2): Z = 500.000(8) + 700.000(2) = 4.000.000 + 1.400.000 = 5.400.000

Keuntungan maksimal adalah Rp5.400.000 dengan menanam padi seluas 8 hektar dan jagung seluas 2 hektar.

Soal 7: Seorang ibu rumah tangga ingin membeli minimal 10 kg buah-buahan. Ia membutuhkan vitamin A dan vitamin C. Vitamin A terdapat dalam apel (5 unit/kg) dan jeruk (3 unit/kg). Vitamin C terdapat dalam apel (2 unit/kg) dan jeruk (4 unit/kg). Ibu tersebut membutuhkan minimal 20 unit vitamin A dan 24 unit vitamin C. Jika harga apel Rp15.000/kg dan harga jeruk Rp10.000/kg, tentukan biaya minimum yang dikeluarkan ibu tersebut!

Pembahasan Soal 7: Variabel keputusan:

  • x = jumlah apel yang dibeli (kg)
  • y = jumlah jeruk yang dibeli (kg)

Fungsi tujuan (Biaya, C):

  • C = 15.000x + 10.000y

Sistem pertidaksamaan linear:

  1. Minimal 10 kg buah: x + y ≥ 10
  2. Minimal 20 unit vitamin A: 5x + 3y ≥ 20
  3. Minimal 24 unit vitamin C: 2x + 4y ≥ 24 (disederhanakan menjadi x + 2y ≥ 12)
  4. Kendala non-negatif: x ≥ 0 y ≥ 0

Gambar grafik (perhatikan tanda '≥', daerah penyelesaian berada di atas garis):

  • Garis 1: x + y = 10 (titik (0, 10) dan (10, 0))
  • Garis 2: 5x + 3y = 20 (titik (0, 20/3 ≈ 6.67) dan (4, 0))
  • Garis 3: x + 2y = 12 (titik (0, 6) dan (12, 0))

Kita perlu mencari titik-titik potong yang membentuk daerah penyelesaian yang dibatasi oleh ketiga garis di atas sumbu x dan y.

Titik potong Garis 1 dan Garis 3: Dari x + y = 10 -> x = 10 - y. Substitusikan ke x + 2y = 12: (10 - y) + 2y = 12 10 + y = 12 y = 2 Jika y = 2, maka x = 10 - 2 = 8. Titik (8, 2).

Titik potong Garis 2 dan Garis 3: Dari x + 2y = 12 -> x = 12 - 2y. Substitusikan ke 5x + 3y = 20: 5(12 - 2y) + 3y = 20 60 - 10y + 3y = 20 60 - 7y = 20 7y = 40 y = 40/7 ≈ 5.71 Jika y = 40/7, maka x = 12 - 2(40/7) = 12 - 80/7 = (84 - 80)/7 = 4/7 ≈ 0.57. Titik (4/7, 40/7).

Titik potong Garis 1 dan Garis 2: Dari x + y = 10 -> x = 10 - y. Substitusikan ke 5x + 3y = 20: 5(10 - y) + 3y = 20 50 - 5y + 3y = 20 50 - 2y = 20 2y = 30 y = 15 Jika y = 15, maka x = 10 - 15 = -5. Titik (-5, 15). Titik ini tidak valid karena x harus non-negatif.

Titik-titik pojok yang perlu diuji (titik potong yang membentuk daerah layak): Kita perlu menemukan titik-titik potong yang memenuhi SEMUA pertidaksamaan. Daerahnya terbuka ke atas.

Titik-titik sudut yang mungkin adalah:

  1. Potong 5x + 3y = 20 dan x + 2y = 12: Titik (4/7, 40/7). Cek kendala x + y >= 10: 4/7 + 40/7 = 44/7 ≈ 6.28. Ini TIDAK memenuhi x + y >= 10. Jadi titik ini bukan sudut daerah layak.

  2. Potong x + y = 10 dan x + 2y = 12: Titik (8, 2). Cek kendala 5x + 3y >= 20: 5(8) + 3(2) = 40 + 6 = 46. Memenuhi 46 >= 20. Valid.

  3. Potong x + y = 10 dan sumbu x (y=0): Titik (10, 0). Cek kendala 5x + 3y >= 20: 5(10) + 3(0) = 50. Memenuhi 50 >= 20. Valid. Cek kendala x + 2y >= 12: 10 + 2(0) = 10. TIDAK Memenuhi 10 >= 12. Jadi titik ini bukan sudut daerah layak.

  4. Potong x + 2y = 12 dan sumbu x (y=0): Titik (12, 0). Cek kendala x + y >= 10: 12 + 0 = 12. Memenuhi 12 >= 10. Valid. Cek kendala 5x + 3y >= 20: 5(12) + 3(0) = 60. Memenuhi 60 >= 20. Valid.

  5. Potong 5x + 3y = 20 dan sumbu y (x=0): Titik (0, 20/3). Cek kendala x + y >= 10: 0 + 20/3 = 20/3 ≈ 6.67. TIDAK Memenuhi 6.67 >= 10. Jadi titik ini bukan sudut daerah layak.

  6. Potong x + 2y = 12 dan sumbu y (x=0): Titik (0, 6). Cek kendala x + y >= 10: 0 + 6 = 6. TIDAK Memenuhi 6 >= 10. Jadi titik ini bukan sudut daerah layak.

Titik-titik pojok daerah layak (yang memenuhi semua kendala) adalah:

  • (8, 2) (potongan x + y = 10 dan x + 2y = 12)
  • (12, 0) (potongan x + 2y = 12 dengan sumbu x)

Karena daerahnya terbuka ke atas, kita juga perlu mempertimbangkan titik potong 5x + 3y = 20 dengan x + y = 10 yaitu titik (-5, 15) yang tidak valid. Kemungkinan ada titik potong lain yang membentuk daerah layak.

Mari kita identifikasi ulang daerah layak. Kita butuh x >= 0, y >= 0, x+y>=10, 5x+3y>=20, x+2y>=12.

Titik-titik kritis adalah:

  • (10, 0) - memenuhi 1, 2, tapi tidak 3 (10+2(0)=10 < 12).
  • (12, 0) - memenuhi 1, 2, 3. Valid.
  • (0, 10) - memenuhi 1, tapi tidak 2 (5(0)+3(10)=30 >= 20 ok), tidak 3 (0+2(10)=20 >= 12 ok). Jadi (0,10) valid.
  • (4, 0) - memenuhi 2, tapi tidak 1 (4+0=4 < 10).
  • (0, 20/3) - memenuhi 2, tapi tidak 1 (0+20/3 < 10).
  • (0, 6) - memenuhi 3, tapi tidak 1 (0+6=6 < 10).
  • Potongan x+y=10 dan x+2y=12 -> (8, 2). Cek: 5(8)+3(2)=46>=20 OK. Valid.
  • Potongan 5x+3y=20 dan x+2y=12 -> (4/7, 40/7). Cek: x+y=44/7 < 10 TIDAK VALID.
  • Potongan x+y=10 dan 5x+3y=20 -> (-5, 15). TIDAK VALID.

Jadi, titik-titik pojok yang valid adalah: (12, 0), (8, 2), dan (0, 10).

Uji titik pojok pada fungsi tujuan C = 15.000x + 10.000y:

  • Di (12, 0): C = 15.000(12) + 10.000(0) = 180.000
  • Di (8, 2): C = 15.000(8) + 10.000(2) = 120.000 + 20.000 = 140.000
  • Di (0, 10): C = 15.000(0) + 10.000(10) = 100.000

Biaya minimum yang dikeluarkan adalah Rp100.000 dengan membeli 0 kg apel dan 10 kg jeruk.

Soal 8: Nilai minimum dari fungsi f(x, y) = 3x + 2y yang memenuhi syarat x + y ≥ 5, x + 3y ≥ 9, x ≥ 0, dan y ≥ 0 adalah...

Pembahasan Soal 8: Fungsi tujuan: f(x, y) = 3x + 2y Kendala:

  1. x + y ≥ 5
  2. x + 3y ≥ 9
  3. x ≥ 0
  4. y ≥ 0

Gambar grafik (daerah penyelesaian di atas garis):

  • Garis 1: x + y = 5 (titik (0, 5) dan (5, 0))
  • Garis 2: x + 3y = 9 (titik (0, 3) dan (9, 0))

Cari titik potong kedua garis: Dari x + y = 5 -> x = 5 - y. Substitusikan ke x + 3y = 9: (5 - y) + 3y = 9 5 + 2y = 9 2y = 4 y = 2 Jika y = 2, maka x = 5 - 2 = 3. Titik potongnya adalah (3, 2).

Periksa titik-titik pojok yang membentuk daerah layak:

  • Titik potong x + y = 5 dan sumbu y (x=0): (0, 5). Cek x + 3y >= 9: 0 + 3(5) = 15 >= 9. Valid.
  • Titik potong x + 3y = 9 dan sumbu x (y=0): (9, 0). Cek x + y >= 5: 9 + 0 = 9 >= 5. Valid.
  • Titik potong kedua garis: (3, 2). Cek: x+y=3+2=5>=5 (OK). x+3y=3+3(2)=9>=9 (OK). Valid.

Titik-titik pojok daerah penyelesaian adalah (0, 5), (9, 0), dan (3, 2).

Uji titik pojok pada fungsi tujuan f(x, y) = 3x + 2y:

  • Di (0, 5): f(0, 5) = 3(0) + 2(5) = 10
  • Di (9, 0): f(9, 0) = 3(9) + 2(0) = 27
  • Di (3, 2): f(3, 2) = 3(3) + 2(2) = 9 + 4 = 13

Nilai minimum adalah 10.

Soal 9: Sebuah pabrik memproduksi dua jenis barang, A dan B. Untuk memproduksi barang A, dibutuhkan 2 jam mesin dan 1 kg bahan baku. Untuk memproduksi barang B, dibutuhkan 1 jam mesin dan 2 kg bahan baku. Jumlah jam mesin yang tersedia adalah 10 jam per hari, dan jumlah bahan baku yang tersedia adalah 8 kg per hari. Keuntungan per unit barang A adalah Rp4.000 dan per unit barang B adalah Rp3.000. Tentukan jumlah barang A dan B yang harus diproduksi agar keuntungan maksimal.

Pembahasan Soal 9: Variabel keputusan:

  • x = jumlah barang A yang diproduksi
  • y = jumlah barang B yang diproduksi

Fungsi tujuan (Keuntungan, Z):

  • Z = 4.000x + 3.000y

Sistem pertidaksamaan linear:

  1. Kendala jam mesin: 2x + y ≤ 10
  2. Kendala bahan baku: x + 2y ≤ 8
  3. Kendala non-negatif: x ≥ 0 y ≥ 0

Gambar grafik:

  • Garis 1: 2x + y = 10 (titik (0, 10) dan (5, 0))
  • Garis 2: x + 2y = 8 (titik (0, 4) dan (8, 0))

Cari titik potong kedua garis: Dari 2x + y = 10 -> y = 10 - 2x. Substitusikan ke x + 2y = 8: x + 2(10 - 2x) = 8 x + 20 - 4x = 8 20 - 3x = 8 3x = 12 x = 4 Jika x = 4, maka y = 10 - 2(4) = 10 - 8 = 2. Titik potongnya adalah (4, 2).

Titik-titik pojok daerah penyelesaian:

  • (0, 0)
  • (5, 0) (titik potong 2x + y = 10 dengan sumbu x)
  • (0, 4) (titik potong x + 2y = 8 dengan sumbu y)
  • (4, 2) (titik potong kedua garis)

Uji titik pojok pada fungsi tujuan Z = 4.000x + 3.000y:

  • Di (0, 0): Z = 0
  • Di (5, 0): Z = 4.000(5) + 3.000(0) = 20.000
  • Di (0, 4): Z = 4.000(0) + 3.000(4) = 12.000
  • Di (4, 2): Z = 4.000(4) + 3.000(2) = 16.000 + 6.000 = 22.000

Keuntungan maksimal adalah Rp22.000 dengan memproduksi 4 unit barang A dan 2 unit barang B.

Soal 10: Nilai k sehingga sistem pertidaksamaan linear x + y ≤ k, x + 2y ≤ 8, x ≥ 0, y ≥ 0 memiliki solusi optimum dengan nilai maksimum f(x, y) = 3x + 4y sebesar 16 adalah...

Pembahasan Soal 10: Ini adalah soal yang sedikit berbeda, di mana kita perlu mencari nilai parameter k berdasarkan informasi nilai optimum yang sudah diberikan.

Fungsi tujuan: f(x, y) = 3x + 4y. Nilai maksimum = 16. Kendala:

  1. x + y ≤ k
  2. x + 2y ≤ 8
  3. x ≥ 0
  4. y ≥ 0

Gambar grafik kendala yang tidak melibatkan k:

  • Garis 1: x + 2y = 8 (titik (0, 4) dan (8, 0))

Daerah penyelesaian dibatasi oleh x ≥ 0, y ≥ 0, dan x + 2y ≤ 8. Titik-titik pojoknya adalah (0, 0), (8, 0), dan (0, 4).

Sekarang kita masukkan kendala x + y ≤ k. Nilai maksimum fungsi tujuan f(x, y) = 3x + 4y adalah 16. Ini berarti ada satu titik (x, y) dalam daerah layak yang memberikan nilai ini, dan titik tersebut harus merupakan salah satu titik pojok dari daerah layak.

Mari kita uji nilai fungsi tujuan pada titik-titik pojok dari kendala x + 2y ≤ 8:

  • Di (0, 0): f(0, 0) = 3(0) + 4(0) = 0
  • Di (8, 0): f(8, 0) = 3(8) + 4(0) = 24
  • Di (0, 4): f(0, 4) = 3(0) + 4(4) = 16

Karena nilai maksimum yang diberikan adalah 16, maka titik yang memberikan nilai maksimum ini adalah (0, 4).

Titik (0, 4) harus memenuhi semua kendala, termasuk x + y ≤ k. Substitusikan x = 0 dan y = 4 ke dalam x + y ≤ k: 0 + 4 ≤ k 4 ≤ k

Sekarang, kita juga perlu mempertimbangkan kendala x + y ≤ k ini akan membatasi daerah penyelesaian. Titik (0, 4) adalah titik pojok dari daerah yang dibatasi x + 2y <= 8. Agar (0,4) tetap menjadi titik yang memberikan nilai optimum, kendala x+y<=k tidak boleh 'memotong' daerah penyelesaian x+2y<=8 sedemikian rupa sehingga titik pojok lain menjadi optimum.

Mari kita lihat gradien dari fungsi tujuan 3x + 4y = Z -> 4y = -3x + Z -> y = -3/4 x + Z/4. Gradiennya -3/4. Gradien garis x + y = k adalah -1. Gradien garis x + 2y = 8 adalah -1/2.

Karena gradien fungsi tujuan (-3/4) lebih curam dari gradien x + 2y = 8 (-1/2), maka nilai maksimum cenderung terjadi di titik yang memiliki nilai y lebih tinggi (yaitu (0, 4)).

Jika titik optimum adalah (0, 4), maka titik ini harus memenuhi x + y ≤ k. Maka 0 + 4 ≤ k, sehingga k ≥ 4.

Bagaimana jika ada titik lain yang menjadi optimum karena adanya k? Misalkan titik potong x + y = k dan x + 2y = 8 menjadi titik optimum. Titik potongnya adalah: y = k - x. Substitusi ke x + 2y = 8: x + 2(k - x) = 8 x + 2k - 2x = 8 2k - x = 8 x = 2k - 8 y = k - (2k - 8) = k - 2k + 8 = 8 - k Titik potongnya adalah (2k - 8, 8 - k).

Nilai fungsi tujuan di titik ini adalah: f(2k - 8, 8 - k) = 3(2k - 8) + 4(8 - k) = 6k - 24 + 32 - 4k = 2k + 8

Kita diberikan bahwa nilai maksimum adalah 16. Jadi, 2k + 8 = 16. 2k = 8 k = 4.

Jika k = 4, maka titik potongnya adalah x = 2(4) - 8 = 0 dan y = 8 - 4 = 4. Ini adalah titik (0, 4) yang sudah kita temukan sebelumnya.

Mari kita periksa titik pojok lainnya. Titik (8, 0) memberikan nilai 24, yang lebih besar dari 16. Jadi, kendala x + y ≤ k harus membatasi daerah penyelesaian sehingga titik (8, 0) tidak lagi menjadi bagian dari daerah layak, atau setidaknya bukan titik optimum.

Jika k=4, maka x+y<=4. Titik (8,0) tidak memenuhi 8+0 <= 4. Titik (0,4) memenuhi 0+4 <= 4. Titik potong x+y=4 dan x+2y=8 adalah x=0, y=4. Titik potong x+y=4 dan sumbu x adalah (4,0). Cek (4,0) di x+2y<=8: 4+0<=8 ok. Nilai f(4,0) = 3(4)+4(0) = 12.

Jadi, ketika k=4, daerah layak dibatasi oleh x>=0, y>=0, x+2y<=8, x+y<=4. Titik pojoknya adalah (0,0), (4,0), (0,4). Di (0,0) f=0. Di (4,0) f=12. Di (0,4) f=16.

Ini konsisten dengan nilai maksimum 16 yang terjadi di (0, 4).

Jadi, nilai k adalah 4.

Soal 11-15: Variasi Soal Program Linear

Kita lanjutkan lagi dengan soal-soal yang mungkin punya sedikit 'twist' atau membutuhkan cara pandang yang berbeda.

Soal 11: Nilai maksimum dari f(x, y) = ax + by pada daerah penyelesaian x + y ≤ 6, 2x + y ≤ 10, x ≥ 0, y ≥ 0 adalah 30. Jika nilai minimum tercapai di titik (0, 6), tentukan nilai a dan b!

Pembahasan Soal 11: Pertama, mari kita cari titik-titik pojok daerah penyelesaian dari kendala:

  1. x + y ≤ 6 (garis melalui (0, 6) dan (6, 0))
  2. 2x + y ≤ 10 (garis melalui (0, 10) dan (5, 0))
  3. x ≥ 0
  4. y ≥ 0

Titik potong x + y = 6 dan 2x + y = 10: Kurangkan persamaan kedua dengan persamaan pertama: (2x + y) - (x + y) = 10 - 6 x = 4 Substitusikan x = 4 ke x + y = 6 -> 4 + y = 6 -> y = 2. Titik potongnya adalah (4, 2).

Titik-titik pojok daerah penyelesaian adalah:

  • (0, 0)
  • (5, 0) (titik potong 2x + y = 10 dengan sumbu x)
  • (0, 6) (titik potong x + y = 6 dengan sumbu y)
  • (4, 2) (titik potong kedua garis)

Kita diberikan informasi bahwa nilai maksimum adalah 30 dan terjadi di titik (0, 6). Ini agak aneh karena (0, 6) adalah salah satu titik pojok, bukan satu-satunya. Biasanya, nilai maksimum terjadi di salah satu titik pojok.

Mari kita asumsikan nilai maksimum 30 terjadi di (0, 6). Substitusikan (0, 6) ke f(x, y) = ax + by: f(0, 6) = a(0) + b(6) = 6b Jadi, 6b = 30 -> b = 5.

Sekarang kita tahu f(x, y) = ax + 5y. Kita perlu mencari nilai a. Informasi bahwa nilai maksimum adalah 30 berarti f(x, y) ≤ 30 untuk semua titik (x, y) di daerah penyelesaian.

Kita perlu menguji nilai f(x, y) di titik-titik pojok lainnya:

  • Di (0, 0): f(0, 0) = a(0) + 5(0) = 0
  • Di (5, 0): f(5, 0) = a(5) + 5(0) = 5a
  • Di (4, 2): f(4, 2) = a(4) + 5(2) = 4a + 10
  • Di (0, 6): f(0, 6) = a(0) + 5(6) = 30 (Ini sudah kita pakai)

Karena nilai maksimum adalah 30, maka nilai fungsi di titik pojok lainnya tidak boleh melebihi 30.

  • 5a ≤ 30 -> a ≤ 6
  • 4a + 10 ≤ 30 -> 4a ≤ 20 -> a ≤ 5

Agar kedua kondisi ini terpenuhi, kita perlu a ≤ 5.

Namun, soal juga menyatakan