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".
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.
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.
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.
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 :
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".
gambar garis selidiknya :
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.
$ 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 :
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 :
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.