Menyelesaikan Masalah Program Linear Dengan Metode Garis Selidik

Menentukkan nilai optimum (maksimum dan minimum) fungsi objektif suatu program linear dapat menggunakan uji titik pojok. Dalam metode uji titik pojok, tiap titik pojok (x, y) yang terletak pada daerah himpunan penyelesaian disubstitusikan ke fungsi tujuan ax + by. Dari hasil perhitungan tadi, kemudian dipilih nilai maksimum maupun nilai minimum bentuk objektif ax + by.

Selain menggunakan metode uji titik pojok, kita juga dapat menggunakan metode Garis Selidik. kita dapat menggunakan metode Garis Selidik. Garis Selidik adalah grafik persamaan dari fungsi tujuan yang digunakan untuk menentukan solusi optimum. Untuk lebih memahami garis selidik perhatikan gambar berikut

Keempat garis pada gambar menggambarkan garis-garis selidik atau dikenal pula dengan garis keuntungan dengan k$_1$ < k$_2$ < k$_3$ < k$_4$. Keempat garis merupakan garis-garis yang sejajar. Dalam masalah program linear, pada umumnya titik yang dilalui garis selidik yang letaknya melalui atau paling dekat dengan titik pangkal (0, 0) maka kita akan mendapatkan nilai fungsi objektif yang minimum. Dan sebaliknya, titik yang garis selidik yang paling jauh dari titik pangkal, maka kita akan mendapatkan nilai fungsi objektif yang maksimum. Dengan kata lain, semakin besar nilai k maka kita akan mendapatkan solusi maksimum sedangkan semakin kecil nilai k maka kita akan mendapatkan solusi minimum.

Nah, sekarang coba perhatikan gambar berikut!

Garis manakah yang akan memberikan solusi maksimum? Tentu jawabanya adalah garis ax + by = k$_3$. Garis ax + by = k$_3$ melalui titik P(x$_1$, y$_1$) yang berada dalam daerah penyelesaian sehingga, (a, b) merupakan solusi yang menyebabkan fungsi objektif/tujuan menjadi maksimum.

Bagaimana caranya menggambar garis selidik? Jika fungsi objektifnya f(x, y) = ax + by, maka garis selidiknya adalah ax + by = k dengan k adalah bilangan real. Untuk memudahkan persamaan garis selidik dapat kita tentukan yaitu ax + by = ab dimana k = ab. Dengan demikian akan lebih mudah menggambar garis selidiknya karena titik potong garis selidik dengan sumbu x adalah (b, 0) dan titik potong sumbu y-nya adalah (0, a).

Dari uraian di atas kita dapat membuat langkah-langkah penyelesaian masalah program linear dengan metode Garis Selidik yaitu:

1. Tentukan model matematika dari masalah program linear yang akan kita selesaikan dalam bentuk sistem pertidaksamaan linear
2. Lukis/gambar pertidaksamaan dan tentukan daerah penyelesaianya
3. Buat garis selidik ax + by = k, sesuai dengan fungsi objektif f(x, y) = ax + by dan temukan solusi optimumnya (maksimum atau minimum)

Untuk lebih jelasnya perhatikan contoh soal berikut!

Contoh 1

Diketahui

3x + y ≤ 15

x + 2y ≤ 10

x ≥ 0

y ≥ 0

Tentukan nilai maksimum dari fungsi objektif f(x, y) = 2x + 5y

Penyelesaian

3x + y ≤ 15

x + 2y ≤ 10

x ≥ 0

y ≥ 0

f(x, y) = 2x + 5y

Catatan:
Jika belum paham menggambar sistem pertidaksamaan linear dua variabel silahkan baca artikel Sistem Pertidaksamaan Linear Dua Variabel. Untuk menentukan titik potong garis dapat menggunakan metode Eliminasi Substitusi

Kemudian buat garis selidik 2x + 5y = 10, kemudian geser ke atas garis selidik tersebut. Dari gambar terlihat bahwa garis yang sejajar garis selidik 2x + 5y =10 dan terletak paling jauh dari titik pangkal melalui titik (0, 5) yang termasuk himpunan penyelesaian. Sehingga, titik (0, 5) menyebabkan fungsi objektif menjadi maksimum yaitu:
f(0, 5) = 2(0) + 5(5) = 25
Jadi, nilai maksimum dari fungsi objektifnya adalah 25

Contoh 2
Pak Agus hendak mengangkut 60 ton barang dari gudang ke tokonya. Untuk itu, ia menyewa dua jenis truk. Truk A berkapasitas 3 ton dan truk B berkapasitas 2 ton. Harga sewa truk A Rp.500.000 dan truk B Rp400.000. Dengan cara sewa demikian, ia harus menyewa truk sekurang-kurangnya 24 buah. Tentukan banyak truk A dan truk B yang harus di sewa Pak Agus agar biayanya menjadi seminimum mungkin!

Penyelesaian
Model Matematika
3x + 2y ≤ 60
x + y ≥ 24

x ≥ 0

y ≥ 0
f(x, y) = 500000x + 400000y

Garis selidik 500000x + 400000y = 200000000000 dengan nilai k yang cukup besar dan tentu kita akan kesulitan untuk menggambarnya. Untuk itu, nilai k yang digunakan k = 2000000, garis selidiknya menjadi 500000x + 400000y = 2000000 atau apabila disederhanakan dengan membagi kedua ruas 100000 maka kita dapatkan garis selidik 5x + 4y = 20.

Setelah digeser didapatlah garis yang sejajar dengan garis 5x + 4y = 20 dan paling dekat dengan titik  pangkal serta titik yang dilaluinya adalah titik (20, 0). Sehingga titik (20, 0) akan memberikan solusi minimum
f(20, 0) = 500000(20) + 400000(0) = 1000000
Jadi, agar biaya menjadi minimum pak Agus harus menyewa 20 unit truk A dan tidak menyewa truk B dengan biaya sebesar Rp10.000.000

Pada prakteknya nanti, untuk memudahkan penentuan solusi optimum dengan menggunakan garis selidik anda dapat membuat garis selidik dan kemudian taruhlah penggaris sejajar dengan garis dan kemudian geser ke atas atau ke bawah untuk menemukan solusi optimum yang anda cari.

Kelemahan dari metode ini, adalah soal-soal yang memuat gambar  kadang-kadang tidak digambar dengan baik sehingga hasil yang didapatkan belum tentu benar. Untuk itu kita harus menggambar ulang secara manual tentunya dengan teliti dan benar. Dalam hal ini diperlukan keterampilan menggambarkan pertidaksamaan dan menentukan daerah penyelesaianya. Sehingga, hasil yang didapatkan diharapkan menjadi benar.

Jika dengan metode ini anda masih ragu dengan hasil yang didapatkan, anda dapat menggunakan metode Uji Titik Pojok. Namun, metode Uji Titik Pojok memerlukan langkah yang cukup panjang.

Share :