Program Linear : Nilai Optimum dengan Garis Selidik

         Blog Koma - Selain metode "uji titik pojok", terdapat metode lain yang digunakan sebagai alternatif untuk menentukan nilai optimum dari suatu fungsi tujuan. Metode alternatif tersebut dikenal sebagai metode garis selidik. Pada artikel ini kita akan membahas Program Linear : Nilai Optimum dengan Garis Selidik. Untuk memudahkan mempelajari materi Program Linear : Nilai Optimum dengan Garis Selidik ini, sebaiknya kita harus menguasai dulu materi "Persamaan dan Grafik Bentuk Linear", "Menentukan Daerah Penyelesaian (Arsiran) sistem Pertidaksamaan", dan "Menyusun Model Matematika".

Nilai Optimum dengan Garis Selidik
       Jika bentuk umum fungsi tujuan dinotasikan dengan $ z = f(x, y) = ax + by \, $ maka bentuk umum garis selidik dinotasikan dengan $ \, ax + by = k , $ dengan $ \, k \in R \, $ dimana $ k \, $ sembarang bilangan yang kita pilih. Garis selidik $ ax + by = k (k \in R) $ merupakan himpunan garis-garis yang sejajar. Dua buah garis dikatakan sejajar jika memiliki gradien yang sama.

       Pada dasarnya, metode garis selidik dilakukan dengan cara menggeser garis selidik secara sejajar ke arah kiri, kanan, atas, atau bawah sampai garis tersebut memotong titik-titik pojok daerah himpunan penyelesaian sistem pertidaksamaan linear dua variabel. Untuk fungsi tujuan maksimum, titik optimum dicapai jika semua himpunan penyelesaian dari kendala-kendala sistem pertidaksamaan linear dua variabel berada di bawah atau sebelah kiri garis selidik. Adapun untuk fungsi tujuan minimum, titik optimum dicapai jika semua himpunan penyelesaian berada di atas atau sebelah kanan garis selidik dengan syarat koefisien $ y \, $ harus positif ($ b > 0 $). Jika koefisien $ y \, $ negatif ($b < 0$), maka berlaku sebaliknya.
Langkah-langkah metode Garis Selidik
Langkah-langkah Menentukan nilai Optimum dengan Garis Selidik :
i). Buat model matematikanya yang teridiri dari kendala dan fungsi tujuan;
ii). Tentukan grafik dan daerah himpunan penyelesaiannya (DHP);
iii). Tentukan persamaan garis selidik dari fungsi tujuannya;
Untuk mendapatkan nilai maksimum, geser garis selidik secara sejajar ke arah kanan atau atas sampai memotong titik paling jauh dari daerah himpunan penyelesaian. Titik yang paling jauh tersebut merupakan titik yang memaksimumkan fungsi tujuan.
iv). Untuk mendapatkan nilai minimum, geser garis selidik secara sejajar ke arah kiri atau bawah sampai memotong titik paling dekat dari daerah himpunan penyelesaian. Titik yang paling dekat tersebut merupakan titik yang meminimumkan fungsi tujuan.

Perhatikan gambar ilustrasi garis selidik berikut ini :
Berdasarkan gambar tersebut, titik A merupakan titik yang meminimum kan fungsi tujuan (objektif ) dan titik D merupakan titik yang me maksimum kan tujuan.
Contoh soal nilai optimum dengan garis selidik :
1). Tentukan nilai maksimum dari fungsi tujuan $ z = f(x, y) = 3x + 4y \, $ dan fungsi kendalanya adalah
$ x + 2y \leq 10 , \, 4x + 3y \leq 24, \, x \geq 0 , \, y \geq 0 $

Penyelesaian :
*). Menentukan grafik dan daerah himpunan penyelesaiannya (DHP) :
Silahkan baca : "Persamaan dan Grafik Bentuk Linear", dan "Menentukan Daerah Penyelesaian (Arsiran) sistem Pertidaksamaan".
*). Fungsi tujuannya : $ z = f(x, y) = 3x + 4y $, bentuk umum garis selidiknya adalah $ 3x + 4y = k $ . Untuk memudahkan menggambar, kita pilih nilai $ k = 12 \, $ sehingga persamaan garis selidiknya adalah $ 3x + 4y = 12 $.
gambar garis selidiknya :
Berdasarkan gambar garis selidik di atas, garis selidik yang digeser secara sejajar ke kanan atau ke atas, memotong titik terjauh dari himpunan penyelesaian sistem pertidaksamaan linear dua variabel yang diketahui, yaitu titik B. Koordinat titik B setelah dicari adalah $(\frac{18}{5}, \frac{16}{5})$.
Artinya fungsi tujuannya maksimum pada titik pojok B.
*). Menentukan nilai maksimumnya dengan substitusi titik B ke fungsi tujuannya :
$ f(x,y) = f(\frac{18}{5}, \frac{16}{5}) = 3 \times \frac{18}{5} + 4 \times \frac{16}{5} = 23,6 $.
Jadi, nilai maksimum dari fungsi tujuannya adalah 23,6.

*). Bagaimana dengan nilai minimumnya?
Perhatikan gambar garis selidiknya, garis selidik harus digeser ke kiri atau ke bawah seperti gambar berikut.
Berdasarkan gambar tersebut, titik O(0, 0) merupakan titik paling dekat dari himpunan penyelesaian sistem pertidaksamaan linear dua variabel yang diberikan. Dengan demikian, nilai minimum fungsi tujuan yang diberikan dicapai pada titik O(0, 0), yaitu
$ z = f(x, y) = 3x + 4y = 3(0) + 4(0) = 0 $ .
Sehingga nilai minimum fungsi tujuannya adalah 0.

2). Tentukan nilai maksimum fungsi tujuan $ f(x,y) = 80x + 125y \, $ yang memenuhi kendala $ x + y \leq 350, \, 600x + 1.000y \leq 300.000 , \, x \geq 0, \, y \geq 0 $.

Penyelesaian :
*). Gambar grafik dan DHP nya :
*). Fungsi tujuan dari masalah program linear tersebut adalah $ 80x + 125y $. Bentuk umum garis selidiknya $ ax + by = k \, $ , kita pilih $ k = 10.000 , \, $ sehingga garis selidiknya menjadi $ 80x + 125y = 10.000 \, $ atau $ \, 16x + 25y = 2.000 $ .
catatan : nilai $ k \, $ bebas kita pilih, tapi kita pilih yang mudah dalam menggambar.
*). Oleh karena yang dicari adalah nilai maksimum maka geser garis selidik ke kanan atau atas seperti pada gambar berikut.
gambar garis selidik dan pergeserannya :
*). Berdasarkan gambar di atas, garis selidik yang digeser secara sejajar ke kanan atau ke atas, memotong titik terjauh dari himpunan penyelesaian pertidaksamaan linear dua variabel di titik B (125, 225).
Dengan demikian, nilai fungsi tujuan $ z = 80x + 125y \, $ maksimum dicapai di titik B (125, 225).
*). Menentukan nilai maksimum dengan substitusi titik B ke fungsi tujuan :
$ f(x,y) = 80x + 125y \rightarrow f(125,225) = 80 \times 125 + 125 \times 225 = 38.125 $.
Jadi, nilai maksimum fungsi tujuan $ z = 80x + 125y \, $ adalah 38.125.

Catatan :
Dari dua contoh soal di atas, dapat disimpulkan bahwa metode garis selidik digunakan hanya untuk menentukan titik pojok mana yang menyebabkan fungsi tujuannya memiliki nilai optimum. Hanya saja metode garis selidik memerlukan ketelitian dalam menggambar dan menggeser garis selidiknya, jangan sampai salah.

4 komentar:

  1. bos.. apa maksudnya lambang dolar ($) itu..??

    BalasHapus
    Balasan
    1. Hallow @Nas Dompu,

      Lambang dolar ($) itu hanya digunakan dalam penulisan simbol-simbol matematika atau untuk menampilkan equation nya.

      Kalau pada saat lihat artikelnya masih muncul lambang dolar, maka tunggu sebentar atau refresh saja halamannya sehingga lambag dolarnya hilang.

      Terimakasih untuk kunjungannya ke blog koma ini.

      Hapus
  2. Itu digeser sejauh apa....apa yg menentukan bergesarannya....
    A

    BalasHapus
    Balasan
    1. Hallow @Dwi,

      Terima kasih untuk pertanyaannya.

      Garis selidik kita geser sejajar garis fungsi ojektifnya (fungsi tujuannya) sejauh sampai kena titik pojok terakhirnya yang ingin kita cari nilai optimumnya.

      Jika fungsi objektifnya $ z = ax + by + c $ dengan koefisien $ y $ positif, maka fungsi tujuan akan maksimum pada titik pojok yang paling atas, sehingga kita geser garis selidiknya sampai melewati titik pojok yang paling atas, dan untuk nilai minimumnya adalah titik pojok yang paling di bawah atau titik pojok yang dilalui oleh garis selidik dengan digeser sampai paling bawah.

      Seperti itu penjelasannya.

      Semoga bisa membantu.

      Terima kasih untuk kunjungannya ke blog koma ini.

      Hapus