Program Linear : Menyelesaikan Masalah Program Linear || Bagian 2

 

2. Menyelesaikan Masalah Program Linear

        Nah, setelah soal cerita diubah kedalam model matematika. Maka soal tersebut diselesaikan dengan mencari nilai optimum nya. Lalu, apa itu nilai optimum? Nilai optimum adalah nilai maksimum atau nilai minimum dari suatu masalah program linear yang diberikan. Nilai optimum terletak pada salah satu titik sudut daerah penyelesaian. Untuk memecahkan masalah program linear, dapat digunakan dua metode, yaitu dengan metode uji titik pojok dan metode garis selidik.

a. Menentukan nilai optimum fungsi objektif dengan metode uji titik pojok

           Untuk menentukan nilai optimum dengan menggunakan metode uji titik pojok, lakukan langkah-langkah berikut.

1)   Buatlah tabel bantuan untuk menentukan sumber daya atau kendala-kendala dari permasalahan program linear yang dimaksud

2)  Tentukan sumber daya atau kendala-kendala dari permasalahan program linear yang dimaksud.

3)  Gambarlah daerah penyelesaian dari sumber daya atau kendala-kendala dalam masalah program linear tersebut.

4)  Tentukan titik-titik pojok dari daerah penyelesaian itu.

5)  Substitusikan koordinat setiap titik pojok itu ke dalam fungsi objektif.

6)   Bandingkan nilai-nilai fungsi objektif tersebut. Nilai terbesar berarti menunjukkan nilai maksimum dari fungsi f(x, y), sedangkan nilai terkecil berarti menunjukkan nilai minimum dari fungsi f(x, y).

Contoh 

Pak Eko memiliki area parkir seluas 1.960 m2. Luas rata-rata untuk motor adalah 2 $m^{2}$ dan mobil 4 $m^{2}$. Daya tampung maksimum hanya 600 kendaraan, biaya parkir motor adalah Rp. 2.000,00 dan mobil adalah Rp. 5.000,00. jika area parkir pak eko terisi penuh dan tidak ada kendaraan yang pergi dan datang, maka hasil maksimum tempat parkir tersebut adalah?

penyelesaian

Misalkan motor x dan mobil y, maka dapat disusun model matematika sebagai berikut:

Bagian sistem pertidaksamaan linear: x ≥ 0, y ≥ 0, 2x + 4y ≤ 1960 $(x + 2y ≤ 980)$, dan x + y ≤ 600 dengan x dan y ∈ R

Bagian fungsi objektif ƒ(x,y) = 2000x + 5000y

x + 2y ≤ 980

Garis x + 2y ≤ 980 digambar dengan menghubungkan titik $(0,490)$ dan titik $(980,0)$, karena kurang dari maka daerah mendekati 0

x + y ≤ 600

Garis x + y ≤ 600 digambar dengan menghubungkan titik $(0,600)$ dan titik $(600,0)$, karena kurang dari maka daerah mendekati 0

Titik potong dari garis x + 2y ≤ 980, dan x + y ≤ 600 adalah $(220,380)$

Grafik himpunan penyelesaian dari sistem pertidaksamaan linear x ≥ 0, y ≥ 0, x + 2y ≤ 980, 

dan x + y ≤ 600 dengan x dan y ∈ R ditunjukkan oleh daerah yang diarsir

Koordinat titik-titik pojok yang terletak pada daerah himpunan penyelesaian adalah A$(50,0)$, B$(30,20)$, dan C$(0,80)$

Nilai fungsi objektif ƒ(x,y) = 2000x + 5000y untuk koordinat titik-titik pojok yang didapat dengan tabel berikut.

Jadi, hasil maksimum tempat parkir tersebut adalah Rp. 2.340.000,00 

b. Menentukan nilai optimum fungsi objektif dengan metode garis selidik

          Cara yang mudah untuk menemukan nilai optimum dari suatu bentuk

objektif adalah dengan menggunakan garis selidik. Garis selidik adalah garis yang diperkirakan berpotongan dengan garis lain yang mendekati nilai optimum.

Bentuk umum garis selidik adalah:

Ax + by = k; k ∈ R

ax + by diperoleh dari bentuk obyektif. Garis selidik ini semakin jauh dari titik O$(0,0)$ harganya semakin besar.

Langkah – langkah penggunaan garis selidik untuk menentukan nilai optimum sebagai berikut.

1)  Buatlah tabel bantuan untuk menentukan sumber daya atau kendala-kendala dari permasalahan program linear yang dimaksud

2)  Gambar daerah penyelesaian dari permasalahan yang diketahui.

3)  Buat persamaan garis selidik awal ax + by = k, dengan k = ab. Kemudian, gambar garis tersebut dengan titik potong pada sumbu Y pada titik $(0,a)$.

4)  Buat garis – garis selidik lain yang sejajar dengan garis selidik awal melalui titik-titik ekstrim $(titik sudut)$ daerah penyelesaian.

5) Tentukan titik optimum dengan ketentuan.

6) Titik maksimum adalah titik ekstrim yang dilalui oleh garis selidik yang paling kanan.

7) Titik minimum adalah titik ekstrim yang dilalui oleh garis selidik yang paling kiri.

8) Tentukan nilai optimum dengan memasukkan nilai variabel x dan y pada titik optimum ke fungsi objektif.

Contoh

Seorang pedagang roti memiliki modal Rp.60.000,00. Ia merencanakan menjual roti A dan roti B. Roti A dibeli dari agen Rp.600,00 per bungkus, sedangkan roti B dibeli dari agen Rp.300,00 per bungkus. Keuntungan yang diperoleh pedagang itu adalah Rp.150,00 untuk setiap penjualan sebungkus roti A dan Rp.100,00 untuk setiap penjualan sebungkus roti B. oleh karena keterbatasan tempat, pedagang roti itu hanya akan menyediakan 150 bungkus roti. Tentukan keuntungan  maksimum yang dapat diperoleh oleh pedagang?

Penyelesaian

Langkah 1

Masalah program linear diatas diubah dalam bentuk model matematika sebagai berikut.

600x + 300y ≤ 60000  2x + y ≤ 200

x + y ≤ 150

x ≥ 0

y ≥ 0

f $(x,y)$ = 150x + 100y

 

Persamaan 1 : 2x + y ≤ 200 $(100, 200)$

Persamaan 2 : x + y ≤ 150 $(150, 150)$

Maka titik potong dari 2x + y ≤ 200 dan x + y ≤ 150 adalah $(50, 100)$

Langkah 2

Kemudian buat garis selidik 150x + 100y = 15000. Kemudian, gambarlah garis-garis yang sejajar dengan garis 150x + 100y = 15000 sampai diperoleh garis yang melalui titik pojok terjauh dari titik O $(0,0)$. 

Dari gambar tersebut, titik B $(50,100)$ adalah titik terjauh yang dilalui oleh garis yang sejajar dengan garis selidik 150x + 100y = 15000. Oleh karena itu, titik B $(50,100)$ adalah titik maksimum. Nilai maksimumnya diperoleh dengan mensubstitusikan titik B $(50,100)$ ke fungsi objektif.

f $(x,y)$ = 150x + 100y

f $(x,y)$ = 150$(50)$ + 100$(100)$ = 17.500

Dengan demikian, keuntungan maksimum yang dapat diperoleh oleh pedagang yaitu Rp.17.500,00