4 Langkah Penyelesaian Program Linear

Soal program linear biasanya berbentuk cerita. Untuk menyelesaikannya ada empat tahap, yaitu membuat model matematika (sistem pertidaksamaan linear), menggambarkannya serta menentukan daerah himpunan penyelesaian (DHP), menentukan titik pojok, dan menentukan nilai optimum sesuai permasalahan. Pada halaman ini akan dibahas bagaimana penyelesaian soal program linear melalui sebuah contoh.

Perhatikan contoh soal program linear berikut.

Luas sebuah daerah parkir adalah 1.760 m². Luas rata-rata untuk mobil kecil 4 m² dan mobil besar 20 m². Daya tampung daerah parkir maksimum 200 kendaraan. Jika biaya parkir mobil kecil Rp5.000 dan mobil besar Rp10.000, tentukan penghasilan maksimum yang dapat diperoleh tempat parkir tersebut.

Merancang Model Matematika

Model matematika terdiri dari dua kelompok, yaitu kendala dan fungsi objektif. Kendala berupa sistem pertidaksamaan linear yang sesuai dengan permasalahan pada soal, sedangkan fungsi objektif berupa fungsi yang menjelaskan tujuan (meminimumkan atau memaksimumkan).

Tips menentukan model matematika SPtLDV dari soal cerita:

• Buatlah tabel yang sesuai dengan soal cerita.
• Jika terdapat kata kunci tidak kurang dari, minimal, memerlukan, dan sebagainya, gunakan tanda lebih besar atau sama dengan (≥).
• Jika terdapat kata kunci tidak lebih dari, maksimal, hanya dapat menampung, hanya memiliki, dan sebagainya, gunakan tanda lebih kecil atau sama dengan (≤).
• Jika tidak ada syarat minimal, tambahkan pertidaksamaan x≥0 dan y≥0.

Dari soal di atas, kita misalkan
x: banyak mobil kecil yang parkir
y: banyak mobil besar yang parkir

Jika digambarkan pada sebuah tabel, permasalahan di atas menjadi seperti berikut

Tabel ini sifatnya tidak wajib, tetapi dengan adanya tabel kita bisa lebih mudah menentukan model matematika dari soal program linear. Berikut model matematikanya.

x+y≤200
x+5y≤440
x≥0
y≥0
f(x,y)=5.000x+10.000y

Pertidaksamaan x+5y≤440 merupakan bentuk sederhana dari 4x+20y≤1.760

Dari model matematika di atas, 4 pertidaksamaan pertama yang merupakan sistem pertidaksamaan linear disebut sebagai KENDALA. Sedangkan fungsi yang berada pada baris terakhir disebut sebagai FUNGSI OBJEKTIF.

Menggambar Grafik Sesuai Model Matematika

Grafik yang digambarkan berupa daerah himpunan penyelesaian (DHP) dari sistem pertidaksamaan linear yang merupakan kendala pada model matematika. Langkah pertama dalam menggambar DHP dari sistem pertidaksamaan linear adalah menggambarkan grafik dari masing-masing persamaan linear.

 

Berikutnya adalah menentukan DHP sesuai sistem pertidaksamaan linear yang terdapat pada kendala.

Menentukan Titik Pojok

Titik pojok adalah titik-titik pada daerah himpunan penyelesaian (DHP) dan merupakan titik potong garis dengan garis atau garis dengan sumbu koordinat. Dari gambar di atas, terdapat 4 titik pojok yang digambarkan sebagai berikut.

Titik O merupakan titik potong kedua sumbu koordinat, titik A dan C merupakan titik potong garis dengan sumbu koordinat, sedangkan titik B merupakan titik potong kedua garis. Titik O, A, dan C mudah ditentukan hanya dengan memperhatikan gambar. Sedangkan titik B dapat ditentukan melalui penyelesaian sistem persamaan linear (eliminasi-substitusi). Keempat titik pojok dari gambar di atas adalah sebagai berikut.

Menentukan Nilai Maksimum atau Minimum

Nilai maksimum/minimum sebuah permasalahan program linear adalah nilai fungsi objektif yang paling besar/kecil dari titik-titik yang terdapat pada daerah himpunan penyelesaian. Secara umum, nilai ini diperoleh dari titik pojok.

Dalam menentukan titik pojok mana yang sesuai, dapat dilakukan dengan cara uji titik pojok ke fungsi objektif atau dengan garis selidik.

Menentukan nilai maksimum atau minimum menggunakan metode uji titik pojok adalah dengan cara substitusi titik-titik pojok ke fungsi objektif. Nilai hasil substitusi terbesar merupakan nilai maksimum, sedangkan nilai hasil substitusi terkecil merupakan nilai minimum. Berikut adalah penentuan nilai maks/min menggunakan metode uji titik pojok untuk soal di atas.

Sedangkan dengan metode garis selidik adalah dengan cara menggambar garis-garis sejajar dengan gradien sesuai fungsi objektif dan berpotongan dengan setiap titik pojok. Untuk fungsi objektif dengan koefisien positif, nilai maksimum dicapai di titik pojok yang dilalui garis selidik paling kanan, sedangkan nilai minimumnya dicapai di titik pojok yang dilalui garis selidik paling kiri. (Silakan dicoba sebagai latihan)

Dari hasil uji titik pojok di atas dapat disimpulkan bahwa penghasilan maksimum yang diperoleh tempat parkir sebesar Rp1.300.000,00 dan terjadi ketika mobil kecil yang parkir sebanyak 140 kendaraan, sedangkan mobil besar yang parkir sebanyak 60 kendaraan.