PENGERTIAN PROGRAM LINEAR

Ryan Alfaridzi
XI IPS 2

31

Pengertian Program Linear

Program linear adalah suatu metode penentuan nilai optimum dari suatu persoalan linear. Nilai optimum (maksimal atau minimum) diperoleh dari nilai dalam suatu himpunan penyelesaiaan persoalan linear. Di dalam persoalan linear terdapat fungsi linear yang bisa disebut sebagai fungsi objektif. Persyaratan, batasan, dan kendala dalam persoalan linear merupakan sistem pertidaksamaan linear.

Model Matematika Program Linear
Model matematika merupakan pernyataan yang menggunakan peubah dan notasi matematika. 

Sebagai ilustrasi, produsen sepatu membuat 2 model sepatu menggunakan 2 bahan yang berbeda. Komposisi model pertama terdiri dari 200 gr bahan pertama dan 150 gr bahan kedua. Sedangkan komposisi model kedua terdiri dari 180 gr bahan pertama dan 170 gr bahan kedua. Persediaan di gudang bahan pertama 72 kg dan bahan kedua 64 kg. Harga model pertama adalah Rp. 500.000,00 dan model kedua Rp. 400.000,00. Jika disimpulkan/disederhanakan dalam bentuk tabel menjadi berikut:

 

Dengan peubah dari jumlah optimal model 1 adalah x dan model 2 adalah y, dan hasil penjualan optimal adalah f(x, y) = 500.000x + 400.000y. Dengan syarat:

• Jumlah maksimal bahan 1 adalah 72.000 gr, maka 200x + 180y ≤ 72.000.
• Jumlah maksimal bahan 2 adalah 64.000 gr, maka 150x + 170y ≤ 64.000
• Masing-masing model harus terbuat.

Model matematika untuk mendapat jumlah penjualan yang maksimum adalah:
Maksimum f(x, y) = 500.000x + 400.000y
Syarat:

• 200x + 180y ≤ 72.000
• 150x + 170y ≤ 64.000
• x ≥ 0
• y ≥ 0

Nilai Optimum Fungsi Objektif

Fungsi objektif yaitu fungsi linear dan batasan-batasan pertidaksamaan linear yang memiliki sebuah himpunan penyelesaian. Himpunan penyelesaian yang ada ialah berupa titik-titik dalam diagram cartesius yang apabila koordinatnya disubstitusikan kedalam fungsi linear maka dapat memenuhi persyaratan yang ditentukan.

Nilai optimum fungsi objektif dari suatu persoalan linear bisa ditentukan dengan menggunakan metode grafik. Dengan melihat grafik dari fungsi objektif dan batasan-batasannya, maka kita bisa tentukan letak titik yang menjadi nilai optimum.

Langkah-langkahnya yaitu sebagai berikut :

• Menggambar himpunan penyelesaian dari semua batasan syarat yang ada pada cartesius.
• Menentukan titik-titik ekstrim yang merupakan perpotongan pada garis batasan dengan garis batasan yang lainnya. Titik-titik ekstrim tersebut adalah himpunan penyelesaian dari batasannya dan memiliki suatu kemungkinaan besar akan membuat fungsi menjadi optimum.
• Meneliti nilai optimum fungsi objektif dengan dua acara, yaitu :
  • Menggunakan garis selidik, dan
  • Membandingkan nilai fungsi objektif pada tiap titik ekstrim.

1. Menggunakan Garis Selidik

Garis selidik dapat diperoleh dari fungsi objektif f(x, y) = ax + by yang mana garis selidiknya ialah:

ax + by = Z

Nilai Z diberikan sembarang nilai.

Garis ini dibuat setelah grafik himpunan penyelesaian pertidaksamaannya juga dibuat.

Garis selidik awal dibuat di area himpunan penyelesaian awal. Lalu kemudian dibuat garis-garis yang sejajar dengan garis selidik awal.

Berikut adalah pedoman untuk mempermudah penyelidikian nilai fungsi optimum:

Cara 1 (syarat a > 0), yaitu:

• Apabila maksimum, maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di kiri garis tersebut. Titik yang dilalui garis tersebut ialah titik maksimum.

Apabila minimum, maka dibuatlah garis yang sejajar garis selidik awal sehingga akan membuat suatu himpunan penyelesaian berada di kanan garis tersebut.

Titik yang dilalui garis tersebut ialah titik minimum.

Perhatikan grafik dibawah:

Cara ke- 2 (syarat b > 0), yaitu:

• Apabila maksimum: maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di bawah garis tersebut. Titik yang dilalui garis tersebut ialah titik maksimum.
• Apabila minimum: maka dibuat garis yang sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di atas garis tersebut. Titik yang dilalui garis tersebut ialah titik minimum.

Perhatikanlah grafik dibawah berikut:

Bagi nilai a < 0 dan b < 0 maka berlaku sebuah kebalikan dari kedua cara yang dijelaskan di atas.

2. Membandingkan Nilai Fungsi Tiap Titik Ekstrim

Menyelidiki nilai optimum dari fungsi objektif juga dapat dilaksanakan dengan terlebih dahulu menentukan titik-titik potong dari suatu garis-garis batas yang ada. Titik-titik potong tersebut merupakan nilai ekstrim yang berpotensi memiliki nilai maksimum pada salah satu titiknya.

Berdasarkan titik-titik tersebut, maka dapat ditentukan nilai masing-masing fungsinya, yakni kemudian dibandingkan.

Nilai terbesar merupakan nilai maksimum dan nilai terkecil adalah merupakan nilai minimum.

Contoh Soal
1. Tentukan nilai minimum f(x, y) = 9x + y pada daerah yang dibatasi oleh 2 ≤ x ≤ 6, dan 0 ≤ y ≤ 8 serta x + y ≤ 7.
pembahasan:

• Langkah 1: menggambar grafiknya

• Langkah 2: menentukan titik ekstrim

Dari gambar, ada 4 titik ekstrim, yaitu: A, B, C, D dan himpunan penyelesaiannya ada di area yang diarsir.

• Langkah 3: menyelidiki nilai optimum

Dari grafik diketahui titik A dan B memiliki y = 0, sehingga kemungkinan menjadi nilai minimum. Kedua titik disubstitusikan kedalam f(x, y) = 9x + y untuk dibandingkan.

Dengan membandingkan, disimpulkan titik A memiliki nilai minimum 18

2. Tentukan dimana nilai maksimum fungsi f(x, y) = 4x + 5y yang akan dicapai pada pada grafik ini!

 

pembahasan:

Titik ekstrim pada gambar adalah:

• A tidak mungkin maksimum karena titik paling kiri.
• B(3, 6)
• C(8, 2)
• D(8, 0)

Nilai tiap titik ekstrim adalah:

• 
• 
• 

Sehingga nilai maksimum ada pada titik yang melalui garis BC dengan nilai maksimum 42.