Home / Matematika / program linear

Program Linear

  • 10 min read

Penulis : Abdulaziz H

Program linear – Pernah gak sih kamu mendengar kalimat yang bilang bahwa ‘Bahasa dan Matematika itu adalah ibu dari segala ilmu‘? Kalau pernah, tahukah kamu mengapa bisa sampai muncul kalimat seperti itu? Bahasa dan matematika disebut sebagai ‘ibu dari semua ilmu’ karena dalam semua ilmu pasti terdapat penggunaan bahasa dan matematika. Misalkan, dalam pelajaran sosiologi saat kita membahas tentang sosialisasi.

Berapa banyak sosialisasi dapat terjadi kepada seseorang dalam sehari? Siapa saja yang bisa melakukan sosialisasi? Jumlah kata-kata yang efektif untuk melakukan sosialisasi itu berapa banyak (panjang-pendeknya pesan)? Dari ketiga pertanyaan tersebut sudah terlihat bahwa itu akan terjawab dengan menggunakan matematika (Angka, persentase, dll), sama halnya dengan bahasa, sudah jelas digunakan untuk berkomunikasi.

Contoh di atas adalah salah satu bukti bahwa matematika itu ada dalam keseharian kita. Memang banyak diantara kita yang masih belum menyadari kegunaan matematika dalam kehidupan sehari-hari. Bahkan tidak jarang yang masih bingung ‘untuk apa belajar matematika?’. Nah, materi yang akan kita bahas bersama kali ini akan sangat menarik loh.

Pasalnya, kita dapat melihat salah satu bukti kegunaan matematika sebagai optimalisasi saat melakukan sebuah tindakan maupun mengambil keputusan. Inilah Program Linear.

Baca juga tulisan lain dari bacaboy:

Apa itu Program Linear

Program linear adalah proses berhitung dari berbagai macam persamaan linear yang saling berhubungan pada sebuah situasi atau kejadian tertentu. Biasanya, proses ini bertujuan untuk menemukan nilai atau tindakan yang ‘paling baik’ untuk dilakukan dalam situasi tersebut.

Program linear dapat memecahkan berbagai macam masalah, mulai dari yang paling sederhana hingga masalah kompleks dengan cara membuat asumsi-asumsi sederhana.

Contoh sederhana yang terjadi dalam keseharian kita misalnya saat harus berbagi makanan dengan teman atau saudara—walaupun dalam kenyataannya kita tidak menggunakan rumus tertentu ataupun fungsi matematika, ini salah satu contoh kasus yang sering terjadi.

Di lain sisi, contoh masalah kompleks yang bisa dipecahkan oleh program linear misalnya data barang di gudang penyimpanan perusahaan supermarket, banyaknya bahan produksi dan karyawan yang diperlukan untuk membuat suatu produk, hingga urutan paling optimal untuk mengantar paket barang dalam suatu daerah agar jarak yang ditempuh adalah yang terpendek.

denah pengiriman barang

Dalam kehidupan nyata, banyak sekali variabel yang bisa mempengaruhi. Saking banyaknya, tentu akan sulit untuk menghitungnya sendiri. Namun tenang, untuk variabel yang jumlahnya banyak kita bisa menggunakan tools khusus—seperti OpenSolver, ‘R’ dan lainnya. Untuk bisa mengoperasikan toolsnya, kita tentunya harus bisa memahami konsep linear terlebih dahulu.

Bagaimana Menuliskan Kejadian Sehari-hari Dalam Model Matematika?

Hampir setiap kejadian yang terjadi dalam kehidupan kita dapat dituliskan menjadi sebuah model matematika. Karena kejadian yang kita alami pasti memiliki perbedaan setiap kali terjadi, maka biasanya sebuah model matematika yang didasarkan pada kejadian keseharian akan berbentuk menjadi pertidaksamaan linear. Cara untuk menuliskannya bisa mengikuti 4 langkah-langkah sederhana di bawah ini :

Tulikan Ketentuan-ketentuan Yang Ada : Biasanya program linear mempunyai data dalam bentuk tabel, grafik, maupun studi kasus. Maka untuk membuat model matematika, kita harus menuliskan terlebih dahulu ketentuan yang kita ketahui.

Buatlah Pemisalan : Pemisalan bertujuan untuk memudahkan kita dalam menghitung objek-objek yang belum diketahui. Caranya dengan memisalkannya menjadi variabel-variabel (Contoh x dan y).

Buatlah Pertidaksamaan Linear : Setelah variabel ditentukan dan sudah mengetahui ketentuannya, kita tinggal menyusunnya menjadi sistem pertidaksamaan linear.

Tentukan Fungsi Objektif : Fungsi objektif sering juga disebut fungsi tujuan adalah fungsi yang akan kita maksimumkan atau minimumkan.

Nilai Optimum Fungsi Objektif

Model matematika yang terdiri dari begitu banyaknya pertidaksamaan linear akan mempunyai banyak macam peyelesaian pula. Dari semua penyelesaian itu, satu atau lebih memberikan hasil yang paling baik. Hasil inilah yang disebut nilai optimum. Fungsi objektif umumnya dinyatakan dengan rumus :

rumus fungsi objektif

Terdapat 2 metode yang bisa kita pakai untuk menentukan nilai optimum dari fungsi objektif, yaitu metode garis selidik atau metode uji titik pojok. Yuk simak langkah-langkahnya dibawah ini.

Metode Garis Selidik

  1. Gambarkan daerah penyelesaian dari sistem pertidaksamaan 2 variabel.
  2. Tentuka persamaan garis selidik.

Jika f(x, y) = ax + by yang akan dioptimumkan, garis selidik yang digunakan ax + by = k. Nilai k = ab agar lebih mudah.

3. Gambarkan garis selidik sejajar dengan garis ax + by = k dan melalui setiap titik pojok daerah penyelesaian.

4. Tentukan nilai optimum dengan :

  • Memaksimalkan fungsi objektif, pilih garis selidik yang terjauh dari titik asal (0,0).
  • Meminimumkan fungsi objektif, pilih garis selidik yang terdekat dari titik asal (0,0).

Metode Uji Titik Pojok

  1. Gambarkan daerah himpunan penyelesaian dari sistem pertidaksamaan linear 2 variabel.
  2. Tentukan koordinat titik-titik pojok daerah penyelesaian (grafik yang terarsir).
  3. Masukkan setiap titik pojok (x, y) ke dalam nilai fungsi objektif f(x, y) = ax + by.
    • Pilih nilai f(x, y) yang terbesar untuk fungsi objektif maksimum.
    • Pilih nilai f(x, y) yang terkecil untuk fungsi objektif minimum.

Perhatikan contoh soal dibawah ini.

Metode Uji Titik Pojok

Nilai maksimum fungsi objektif f(x, y) = 6x + 8y pada daerah arsiran adalah….

Jawaban :

Pada daerah arsiran terdapat 4 titik pojok yaitu titik (0,0), (4,0), (0,4), dan titik potong garis batas.

  1. Persamaan garis batas yang melalui titik (4,0) dan (0,6) yaitu 3x + 2y = 12.
  2. Persamaan garis batas yang melalui titik (8,0) dan (0,4) yaitu x + 2y = 8.

Kedua garis batas berpotongan pada titik (2,3).

Uji keempat titik pojok ke dalam f(x, y) = 6x + 8y.

(0,0) → f(0,0) = 6(0) + 8(0) = 0

(4,0) → f(4,0) = 6(4) + 8(0) = 24

(0,4) → f(0,4) = 6(0) + 8(4) = 32

(2,3) → f(2,3) = 6(2) + 8(3) = 36

Jadi, nilai maksimumnya adalah 36.

Note : Untuk membantumu memahami materi ini lebih mudah, kamu bisa mengulang kembali materi persamaan garis dan gradien ya.

Itulah pembahasan mengenai program linear. Untuk memperkuat pemahaman materi, yuk coba latihan soal secara mandiri terlebih dahulu kemudian akan kita coba bahas bersama. Biasakan untuk analisis soal secara hati-hati. Semangat belajar!

Contoh Soal dan Pembahasan

  1. Perhatikan sistem pertidaksamaan berikut.

x + 2y > 8

3x + 2y > 12

x > 0 ; y > 0

Nilai minimum fungsi objektif f(x) = 6x + 10y pada sistem pertidaksamaan diatas adalah….

a. 36

b. 42

c. 48

d. 54

e. 60

2. Untuk membuat 1 liter minuman A diperlukan bahan pokok berupa 2 kaleng sari buah dan 1 kaleng susu. Untuk membuat 1 liter minuman B diperlukan bahan pokok berupa 2 kaleng sari buah dan 3 kaleng susu. Di cafe Pak Ardi tersedia 40 kaleng sari buah dan 30 kaleng susu. Satu liter minuman A dijual sehaga Rp30.000, sedangkan 1 liter minumab B dijual seharga Rp50.000. Pendapata maksimum Pak Ardi dari penjualan kedua minuman tersebut adalah….

a. Rp500.000,-

b. Rp550.000,-

c. Rp600.000,-

d. Rp700.000,-

e. Rp750.000,-

3. Sebuah perusahaab akan mengangkut buah-buahan yang terdiri atas 480 kardus buah apel dan 352 peti buah jeruk. Perusahaan tersebut memiliki 2 jenis mobil boks dan truk. Mobil boks dapat mengangkut paling banyak 40 kardus dan 16 peti. Truk dapat mengangkut paling banyak 30 kardus dan 32 peti. Biaya operasional untuk satu mobil boks sebesar Rp100.000,- dan truk sebesar Rp150.000,- sekali jalan. Agar biaya pengeluaran minimum, maka jenis kendaraan yang harus digunakan adalah….

a. Hanya 22 mobil boks

b. Hanya 8 truk

c. 6 mobil boks dan 8 truk

d. 8 mobil boks dan 6 truk

e. 12 mobil boks dan 11 truk

Pembahasan Soal

  1. Ada beberapa langkah yang harus dilakukan :

a. Pertidaksamaan x + 2y > 8 dibatasi oleh garis x + 2y = 8. Garis ini melalui titik (8,0) dan (0,4). Cek titik (0,0) ke x + 2y > 8 diperoleh : 0 + 2(0) = 0 > 8 (Salah), maka arsirannta tidak memuat titik (0,0).

b. Pertidaksamaan 3x + 2y > 12 dibatasi oleh garis 3x + 2y = 12. Garis ini melalui titik (4,0) dan (0,6). Cek titik (0,0) ke pertidaksamaannya diperoleh : 3(0) + 2(0) = 0 > 12 (Salah), maka arsirannya tidak memuat titik (0,0).

c. Penyelesaian x > 0 terletak di kanan sumbu Y, sedangkan y > 0 terletak di atas sumbu X

Daerah peenyelesaiannya seperti grafik di bawah ini.

Uji coba titik pojok ke f(x,y) = 6x + 10y

(8,0) f(8,0) = 6(8) + 10(0) = 48

(2,3) f(2,3) = 6(2) + 10(3) = 42

(0,6) f(0,6) = 6(0) + 10(6) = 60

Jadi, nilai minimumnya adalah 42.

Jawabannya : B

2.Pertama-tama kita misalkan minuman A sebagai x dan minuman B sebagai y. Setelah itu kita tuliskan hal-hal yang kita ketahui.

JENIS MINUMAN

SARI BUAH (KALENG)

SUSU (KALENG)

KEUNTUNGAN

A

2x

1x

30.000x

B

2y

3y

50.000y

Batasan

40

30

 –

Berdasarkan tabel diatas, kita mendapatkan persamaan :

a. 2x + 2y < 40 x + y < 20

b. x + 3y < 30

c. x > 0 dan y > 0

d. Fungsi objektif untuk memaksimumkan f(x,y) = 30.000x + 50.000

Kemudian kita harus mencari titik potong antara garis x + y = 20 dan x + 3y = 30.

x + y = 20 x = 20 – y

Ini akan langsung kita substitusikan ke dalam persamaan x + 3y = 30, sehingga menjadi (20-y) + 3y = 30.

= 20 + 2y = 30

= 2y = 10, maka y = 5, sehingga x = 20 – 5 = 15.

Diperoleh titik potong C (15,5), titik B (0,10), titik A (20,0) dan titik O (0,0). Masukkan nilai titik pojok ke dalam persamaan f(x,y) = 30.000x + 50.000y. Sehingga diperoleh nilai maksimum f(15,5) = 30.000(15) + 50.000(5) = 700.000.

Jawabannya : D

3. Misalkan x adalah banyak mobil boks dan y adalah mobil truk. Kita tuliskan dulu apa yang kita ketahui.

KENDARAAN

APEL

JERUK

OPERASIONAL

Mobil Boks

40x

16x

100.000x

Truk

30y

32y

150.000y

Batasan

480

352

 

Berdasarkan tabel di atas, kita buat sistem pertidaksamaan dengan cara seperti pada no. 2, kemudian kita sederhanakan sehingga didapatkan pertidaksamaan :

4x + 3y > 48 ; menghasilkan titik (0,16)

x + 2y > 22 ; menghasilkan titik (22,0)

Titik temu antara 2 garis pertidaksamaan adalah (6,8).

Titik temu antara 2 garis pertidaksamaan

Fungsi Objektif meminimumkan f(x,y) = 100.000x + 150.000y. Lalu kita lakukan uji titik pojok dengan memasukkan nilai titik pojok ke dalam fungsi objektifnya. Sehingga didapatkan agar biaya pengeluaran minimum, maka f(6,8) = 100.000(6) + 150.000(8) = 1.800.000. Jadi hanya dibutuhkan 6 mobil boks dan 8 mobil truk.

Jawabannya : C

Daftar Pustaka

  • Introductory Guide On Linear Programming For (Aspiring) Data Scientists
    https://www.analyticsvidhya.com/blog/2017/02/lintroductory-guide-on-linear-programming-explained-in-simple-english/
  • Linear Programming – Introduction
    https://www.purplemath.com/modules/linprog.htm
  • Aksin, Nur, Anna Yuni Astuti dan Suparno. 2019. Detik-Detik Ujian Nasional Matematika SMA IPA TA.2019/2020. Jakarta: PT. Penerbit Intan Pariwara.

Baca juga: