2. Program Linier a. Defenisi Program linier adalah metode untuk mendapatkan penyelesaian optimum dari suatu fungsi sasaran yang mengandung kendala atau batasan yang dapat dibuat dalam bentuk sistem pertidaksamaan linier Diantara himpunan penyelesaian dari sistem pertidaksamaan linier ada satu penyelesaian terbaik yang disebut penyelesaian optimum yang dapat merupakan nilai maksimum atau minimum dari fungsi sasaran yang biasa disebut fungsi tujuan atau fungsi objektif Permasalahan yang akan diselesaikan harus dijabarkan dalam bahasa matematika yang disebut model matematika Untuk memudahkan membuat model matematika sebaiknya permasalahan dibuatkan dalam bentuk tabel Contoh : UMPTN 1991 Seorang anak diharuskan makan dua jenis tablet setiap hari. Tablet pertama mengandung 5 unit vitamin A dan 3 unit vitamin B, sedangkan tablet kedua mengandung 10 unit vitamin A dan 1 unit vitamin B. Dalam sehari anak membutuhkan 20 unit vitamin A dan 5 unit vitamin B. Jika harga tablet pertama Rp 4,00/biji dan tablet kedua Rp 8,00/biji, maka pengeluaran minimum untuk pembelian tablet per hari Permasalahan di atas dalam bentuk tabel Tablet I 𝑥 Tablet II 𝑦 Batasan Vitamin A 5 10 Minimal 20 Vitamin B 3 1 Minimal 5 Harga/Biji 4 8 Tabel di atas diterjemahkan kedalam model matematika sebagai berikut Vitamin A 5𝑥 + 10𝑦 ≥ 20 Vitamin B 3𝑥 + 𝑦 ≥5 Tambahan batasan adalah anak diharuskan makan kedua jenis tablet setiap hari dan model matematikanya adalah 𝑥 ≥ 0 dan 𝑦 ≥ 0
Fungsi objektifnya adalah meminimalkan pengeluaran untuk pembelian tablet model matematikanya adalah 𝑓!"#"!$! 𝑥, 𝑦 = 4𝑥 + 8𝑦 Secara keseluruhan model matematikanya adalah 5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5 𝑥 ≥0 𝑦 ≥0 𝑓!"#"!$! 𝑥, 𝑦 = 4𝑥 + 8𝑦 Himpunan penyelesaiannya gunakan cara pada bagian 1.b dan 1.c Gambar garis 5𝑥 + 10𝑦 = 20 dan garis 3𝑥 + 𝑦 = 5
Ambil titik uji 0,0 dan subtitusikan ke dalam pertidaksamaan 5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5 5 0 + 10 0 ≥ 20 3 0 + 0 ≥ 5 0+0 ≥ 20 0+0 ≥5 0 ≥ 20 0 ≥5 Pertidaksamaan salah Pertidaksamaan salah Daerah 5𝑥 + 10𝑦 ≥ 20 Daerah 3𝑥 + 𝑦 ≥ 5 Di atas garis 5𝑥 + 10𝑦 = 20 Di atas garis 3𝑥 + 𝑦 = 5 Untuk daerah 𝑥 ≥ 0 terletak di sebelah kanan sumbu Y Untuk daerah 𝑦 ≥ 0 terletak di atas sumbu Y Irisannya atau himpunan penyelesaiannya adalah daerah yang berwarna gelap yang merupakan kumpulan pasangan titik titik yang memenuhi ke empat pertidaksamaan linier di atas Untuk mencari titik optimum digunakan metode titik sudut dan garis selidik
b. Metode Titik Sudut Nilai optimum (maksimum/minimum) fungsi terletak pada titik sudut daerah yang diarsir Titik sudut adalah perpotongan antara garis pembatas himpunan penyelesaiannya Untuk mencari titik sudut atau perpotongan dua garis bisa digunakan metode subtitusi, metode eliminasi pada pelajaran sistem persamaan linier atau menggunakan motode determinan , metode invers pada pelajaran matriks
Dengan menggunakan salah satu metode di atas akan didapatkan titik titik sudut daerah yang diarsir ! ! Titik ! , ! adalah perpotongan garis 5𝑥 + 10𝑦 = 20 dan 3𝑥 + 𝑦 = 5 Titik 0,5 adalah perpotongan garis 3𝑥 + 𝑦 = 5 dan sumbu Y Titik 4,0 adalah perpotongan garis 5𝑥 + 10𝑦 = 20 dan sumbu X Masukkan nilai 𝑥, 𝑦 dari titik titik sudut tersebut dan bandingkan nilainya ! !
Nilai di titik
𝑓 𝑥, 𝑦
,
! !
= =
Nilai di titik 4,0
= 4𝑥 + 8𝑦 !
=4
!" ! !"
!
+
+8 !" !
𝑓 𝑥, 𝑦
! !
= 4𝑥 + 8𝑦 =4 4 +8 0 = 16 + 0 = 16
Nilai di titik 0,5 𝑓 𝑥, 𝑦
= 4𝑥 + 8𝑦 =4 0 +8 5 = 0 + 40 = 40
!
= 16
Nilai minimumnya adalah 16 karena ada dua titik yang memenuhi maka nilai minimum terletak pada garis 5𝑥 + 10𝑦 = 20 yang memuat kedua titik
c. Metode Garis Selidik Fungsi objektif suatu program linier berbentuk 𝑓 𝑥, 𝑦 = 𝑎𝑥 + 𝑏𝑦 ! merupakan persamaan garis dengan gradien 𝑚 = − ! 𝑎 𝑚 = − 𝑏 Seperti diketahui penyelesaian optimum terletak pada titik sudut atau titik potong antara garis pada daerah yang diarsir 𝑥! , 𝑦! ! Garis selidik adalah garis dengan gradien 𝑚 = − ! yang melalui titik sudut daerah yang diarsir 𝑥! , 𝑦! Persamaan garis selidik adalah 𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥! 𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥! 𝑦 − 𝑦! = 𝑚𝑥 − 𝑚𝑥! 𝑦 = 𝑚𝑥 − 𝑚𝑥! + 𝑦! 𝑦 = 𝑚𝑥 + 𝑦! − 𝑚𝑥! Kita ketahui juga persamaan garis dapat ditulis sebagai 𝑦 = 𝑚𝑥 + 𝑐 dimana 𝑐 adalah ordinat titik potong garis dengan sumbu Y sehingga 𝑦 = 𝑚𝑥 + 𝑦! − 𝑚𝑥! 𝑚𝑥 + 𝑐 = 𝑚𝑥 + 𝑦! − 𝑚𝑥! 𝑐 = 𝑦! − 𝑚𝑥! 𝑐! = 𝑦! − 𝑚𝑥! Nilai maksimum adalah garis selidik yang terletak paling atas Nilai minimum adalah garis selidik yang terletak paling bawah Nilai maksimum adalah garis selidik dengan 𝑐! paling besar Nilai minimum adalah garis selidik dengan 𝑐! paling kecil
Pada contoh soal sebelumnya daerah yang diarsir adalah himpunan penyelesaian dari model matamatika 5𝑥 + 10𝑦 ≥ 20 3𝑥 + 𝑦 ≥5 𝑥 ≥0 𝑦 ≥0 ! ! 𝑓!"#"!$! 𝑥, 𝑦 = 4𝑥 + 8𝑦 dimana 𝑚 = − ! = − !
Dari grafik terlihat garis selidik paling bawah (minimum) melaui titik dan 4,0 persamaannya adalah 𝑦 − 𝑦! = 𝑚 𝑥 − 𝑥! 𝑦−0
! !
,
! !
!
= − ! 𝑥 − 4 !
𝑦 = −!𝑥 + 2 Titik potongnya dengan sumbu Y adalah 2 terletak paing bawah sehingga titik sudut yang dilalui garis ini memberikan nilai fungsi objektif minimum Dari grafi terlihat dua titik sudut dilalui dengan garis selidik yang sama ! ! sehingga dikatakan nilai minimum merupakan ruas garis antara titik ! , ! dan 4,0 Hal ini terjadi karena gradien garis 5𝑥 + 10𝑦 = 20 sama dengan gradien ! fungsi objektif 𝑚 = − ! Grafik hanya mempunyai titik minimum dan tidak mempunyai titik maksimum karena daerah yang diarsir terbuka atau kumpulan titik titik daerah yang diarsir jumlahnya tak berhingga Jika daerah yang diarsir merupakan daerah terbuka maka program linier mempunyai hanya titik maksimum atau titik minimum saja Jika daerah yang diarsir tertutup atau berbentuk poligon maka program linier mempunyai titik maksimum dan titik minimum
