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 m2. Luas rata-rata untuk mobil kecil 4 m2 dan mobil besar 20 m2. 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

Jenis Kendaraan Banyak Mobil Luas Biaya
Mobil kecil x 4 5.000
Mobil besar y 20 10.000
tersedia 200 1.760

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.

x+y=200
x y (x,y)
0 200 (0,200)
200 0 (200,0)
 
x+5y=440
x y (x,y)
0 88 (0,88)
440 0 (440,0)

Grafik persamaan linear dari model matematika kendala program linear

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

Daerah himpunan penyelesaian (DHP) sistem pertidaksamaan linear kendala program linear

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 pojok pada daerah himpunan penyelesaian (DHP)

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.

Titik Pojok Koordinat
O (0,0)
A (0,88)
B (140,60)
C (200,0)

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.

Titik Pojok NIlai Fungsi Objektif
f(x,y)=5.000x+10.000y
O(0,0) 0
A(0,88) 5.000(0)+10.000(88)=880.000
B(140,60) 5.000(140)+10.000(60)=1.300.000
C(200,0) 5.000(200)+10.000(0)=1.000.000

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.

Oleh Opan
Dibuat
Seorang guru matematika yang hobi menulis tiga bahasa, yaitu bahasa indonesia, matematika, dan php. Dari ketiganya terwujudlah website ini sebagai sarana berbagi pengetahuan yang dimiliki.

Demi menghargai hak kekayaan intelektual, mohon untuk tidak menyalin sebagian atau seluruh halaman web ini dengan cara apa pun untuk ditampilkan di halaman web lain atau diklaim sebagai karya milik Anda. Tindakan tersebut hanya akan merugikan diri Anda sendiri. Jika membutuhkan halaman ini dengan tujuan untuk digunakan sendiri, silakan unduh atau cetak secara langsung.

Protected by Copyscape