Pemrograman Linear: Metode Garis Selidik

Salah satu ilmu matematika yang banyak digunakan untuk memecahkan masalah efisiensi produksi, waktu maupun distribusi adalah pemrograman linear. Pada masa perang dunia II, sejarah mencatat berkat keberhasilan para matematikawan memecahkan masalah pemrograman linear, Amerika mampu memenangi perang melawan Jepang karena lebih memiliki strategi yang efisien. Pemrograman linear sendiri konsep dasarnya sudah dipelajari sejak SMP kelas VIII. Namun, siswa baru benar-benar berkenalan dan belajar pemrograman linear di bangku SMA kelas XII.

Masalah pada pemrograman linear terbagi menjadi dua bagian yaitu constrains (kendala) dan fungsi tujuan. Fungsi tujuan berupa fungsi yang merujuk pada tujuan yang ingin dicapai seperti meminimalkan biaya produksi dan distribusi atau memaksimalkan keuntungan yang diperoleh. Sedangkan, kendala berperan sebagai batasan yang harus dipenuhi dalam mencapai tujuan misalnya total waktu produksi tidak lebih dari 24 jam atau banyaknya bahan produksi yang tersedia hanya 100 kg. Fungsi tujuan dalam pemrograman linear biasanya menuju pada dua tujuan yaitu memaksimalkan atau meminimalkan. Fungsi tujuan yang memaksimalkan biasanya berupa permasalahan tertang terbatasnya waktu, biaya, bahan, atau tenaga (sumber daya). Di lain pihak, fungsi tujuan yang meminimalkan biasanya berupa permasalahan tentang distribusi, biaya produksi, waktu yang diperlukan, dsb.

Masalah pemrograman linear biasanya disajikan dalam dua jenis yaitu 1) masalah dalam bentuk persamaan matematika dan 2) masalah dalam bentuk soal cerita. Untuk lebih mudah memahami tentang pemrograman linear, pada artikel ini akan dibahas satu contoh masalah terlebih dahulu yaitu contoh masalah dalam bentuk persamaan matematika. Sedangkan, masalah dalam bentuk soal cerita akan dibahas pada artikel lain.

Untuk menyelesaikan masalah pemrograman linear ada beberapa cara yaitu:

1.      Metode Garis selidik

2.      Metode titid sudut

3.      Metode gradien

4.      Metode simpleks

Artikel kali ini hanya akan membahas satu metode saja yaitu metode garis selidik. Metode gradien akan dibahas pada artikel lain, sedangkan metode simpleks hanya digunakan untuk masalah pemrograman linear yang sudah jauh lebih kompleks. Pada artikel ini contoh kedua akan diselesaikan dengan metode garis selidik dan contoh kedua akan diselesaikan dengan metode titik sudut. Dari dua contoh tersebut nanti akan dibuat perbandingan.

Berikut ini contoh masalah dalam bentuk persamaan matematika dan diselesaikan dengan metode garis selidik:

Carilah nilai x dan y sehingga fungsi f(x,y) = 3x+4y bernilai maksimal dengan kendala bahwa:

Jawab: Metode garis selidik

Langkah pertama adalah dengan menggambar kendala yang ada pada bidang kartesius dan tandai area yang mungkin. Namun, kendala yang berupa pertidaksamaan harus diubah dulu menjadi persamaan garis.

Gambarkan pada bidang koordinat kartesius. Tentukan areanya dengan mencoba sembarang dua titik yang berlainan pihak misal satu titik yang berada di atas garis dan satu titik yang di bawah garis. Area tersebut kemudian di arsir.

  

Langkah kedua adalah menentukan daerah yang memenuhi kendala (Feasible area). Feasible area diperoleh dari hasil irisan area kendala 1 dan area kendala 2. Kemudian, garis selidik dibuat dari fungsi tujuan pada bidang yang sama dengan feasible area.

Langkah terakhir yaitu menggunakan garis selidik untuk mendapatkan penyelesaian yang optimal. Cara menggunakannya yaitu:

Perhatikan bahwa penyelesaian optimal haruslah terletak pada feasible area karena jika tidak, maka penyelesaian tersebut tidak memenuhi syarat kendala. Garis selidik harus digerakkan dari bawah ke atas sampai titik potong terakhir dengan feasible area. Titik potong terakir inilah yang berarti nilai fungsi tujuan adalah yang paling maksimal. Oleh karena itu, garis hijau harus dibayangkan bergerak dari bawah ke atas.

  Jadi penyelesaian optimalnya yaitu (3,3) dan nilai maksimalnya yaitu 21.

Tahukah kalian bagaimana pergerakan garis selidik jika fungsi tujuannya adalah meminimalkan?? Garis selidik akan bergerak dari atas ke arah bawah bawah sampai titik potong yang terakhir dengan feasible area.

Dapat dilihat bahwa titik potong terakhir yaitu (3,3) merupakan titik potong garis kendala 1 dan garis kendala 2. Hubungan antara penyelesaian optimal dan titik potong garis-garis kendal merupakan bagian dari metode titik sudut. Metode ini akan dibahas lebih lanjut pada artikel lain. Jika ada pertanyaan, kritik, saran, atau masukan silahkan tuliskan pada kolom komentar.