Program linear ialah sebuah metode penentuan nilai optimum dr sebuah masalah linear. Nilai optimum (optimal atau minimum) diperoleh dr nilai dlm suatu himpunan penyelesaiaan dilema linear. Di dlm duduk perkara linear terdapat fungsi linear yg mampu disebut sebagai fungsi objektif. Persyaratan, batas-batas, & hambatan dlm persoalan linear merupakan tata cara pertidaksamaan linear.
Model Matematika Program Linear
Persoalan dlm program linear yg masih dinyatakan dlm kalimat-kalimat pernyataan biasa , kemudian diubah kedalam model matematika. Model matematika merupakan pernyataan yg memakai peubah & notasi matematika.
Sebagai ilustrasi, produsen sepatu membuat 2 versi sepatu menggunakan 2 materi yg berlawanan. Komposisi model pertama terdiri dr 200 gr materi pertama & 150 gr bahan kedua. Sedangkan komposisi model kedua terdiri dr 180 gr materi pertama & 170 gr bahan kedua. Persediaan di gudang materi pertama 72 kg & bahan kedua 64 kg. Harga versi pertama adalah Rp. 500.000,00 & versi kedua Rp. 400.000,00. Jika ditarik kesimpulan/disederhanakan dlm bentuk tabel menjadi berikut:
Dengan peubah dr jumlah optimal model 1 yakni x & versi 2 yaitu y, & hasil pemasaran optimal yaitu f(x, y) = 500.000x + 400.000y. Dengan syarat:
- Jumlah optimal materi 1 adalah 72.000 gr, maka 200x + 180y ≤ 72.000.
- Jumlah optimal bahan 2 ialah 64.000 gr, maka 150x + 170y ≤ 64.000
- Masing-masing versi harus yang dibuat.
Model matematika untuk mendapat jumlah pemasaran yg maksimum yakni:
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 merupakan fungsi linear & batas-batas-batas-batas pertidaksamaan linear yg memiliki himpunan solusi. Himpunan penyelesaian yg ada merupakan titik-titik dlm diagram cartesius yg bila koordinatnya disubstitusikan kedalam fungsi linear mampu menyanggupi patokan yg diputuskan.
Nilai optimum fungsi objektif dr suatu persoalan linear mampu diputuskan dgn metode grafik. Dengan melihat grafik dr fungsi objektif & batas-batas-batasannya mampu diputuskan letak titik yg menjadi nilai optimum. Langkah-langkahnya sebagai berikut :
- Menggambar himpunan solusi dr semua batas-batas syarat yg ada di cartesius.
- Menentukan titik-titik ekstrim yg merupakan perpotongan garis batasan dgn garis batas-batas yg yang lain. Titik-titik ekstrim tersebut merupakan himpunan penyelesaian dr batasannya & memiliki kemungkinan besar membuat fungsi menjadi optimum.
- Menyelidiki nilai optimum fungsi objektif dgn dua jadwal yaitu :
- Menggunakan garis selidik
- Membandingkan nilai fungsi objektif tiap titik ekstrim
Menggunakan Garis Selidik
Garis selidik diperoleh dr fungsi objektif f(x, y) = ax + by dimana garis selidiknya yaitu
ax + by = Z
Nilai Z diberikan sembarang nilai. Garis ini dibuat sesudah grafik himpunan solusi pertidaksamaan dibentuk. Garis selidik permulaan dibentuk di area himpunan solusi permulaan. Kemudian dibentuk garis-garis yg sejajar dgn garis selidik permulaan. Berikut fatwa untuk membuat lebih mudah penyelidikian nilai fungsi optimum:
Cara 1 (syarat a > 0)
- Jika maksimum, maka dibuat garis yg sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di kiri garis tersebut. Titik yg dilalui garis tersebut yakni titik maksimum.
Jika minimum, maka dibuat garis yg sejajar garis selidik permulaan sehingga menciptakan himpunan solusi berada di kanan garis tersebut. Titik yg dilalui garis tersebut adalah titik minimum.
Cara 2 (syarat b > 0)
- Jika maksimum, maka dibuat garis yg sejajar garis selidik permulaan sehingga membuat himpunan penyelesaian berada di bawah garis tersebut. Titik yg dilalui garis tersebut yaitu titik maksimum.
- Jika minimum, maka dibuat garis yg sejajar garis selidik permulaan sehingga menciptakan himpunan solusi berada di atas garis tersebut. Titik yg dilalui garis tersebut yakni titik minimum.
Untuk nilai a < 0 & b < 0 berlaku kebalikan dr kedua cara yg diterangkan di atas.
Membandingkan Nilai Fungsi Tiap Titik Ekstrim
Menyelidiki nilai optimum dr fungsi objektif pula dapat dijalankan dgn terlebih dahulu menentukan titik-titik potong dr garis-garis batas yg ada. Titik-titip potong tersebut merupakan nilai ekstrim yg memiliki peluang mempunyai nilai maksimum di salah satu titiknya.
Berdasarkan titik-titik tersebut diputuskan nilai masing-masing fungsinya, kemudian dibandingkan. Nilai paling besar merupakan nilai maksimum & nilai terkecil merupakan nilai minimum.
Contoh Soal Program Linear & Pembahasan
Contoh Soal 1
Tentukan nilai minimum f(x, y) = 9x + y pada daerah yg dibatasi oleh 2 ≤ x ≤ 6, & 0 ≤ y ≤ 8 serta x + y ≤ 7.
Pembahasan 1:
- Langkah 1 menggambar grafiknya
- Langkah 2 menentukan titik ekstrim
Dari gambar, ada 4 titik ekstrim, yakni: A, B, C, D & himpunan penyelesaiannya ada di area yg diarsir.
- Lankah 3 mengusut nilai optimum
Dari grafik dimengerti titik A & B memiliki y = 0, sehingga kemungkinan menjadi nilai minimum. Kedua titik disubstitusikan kedalam f(x, y) = 9x + y untuk dibandingkan.
Dengan membandingkan, ditarik kesimpulan titik A mempunyai nilai minimum 18
Contoh Soal 2
Tentukan dimana nilai maksimum fungsi f(x, y) = 4x + 5y yg akan diraih pada pada grafik ini!
Pembahasan 2:
Titik ekstrim pada gambar adalah:
- A tak mungkin maksimum alasannya adalah titik paling kiri.
- B(3, 6)
- C(8, 2)
- D(8, 0)
Nilai tiap titik ekstrim ialah:
Sehingga nilai maksimum ada pada titik yg lewat garis BC dgn nilai maksimum 42.
Contoh Soal 3
Pedagang buah memiliki modal Rp. 1.000.000,00 untuk membeli apel & pisang untuk dijual kembali. Harga beli tiap kg apel Rp 4000,00 & pisang Rp 1.600,00. Tempatnya hanya mampu memuat 400 kg buah. Tentukan jumlah apel & pisang biar kapasitas maksimum.
Pembahasan 3:
Diketahui:
Dengan syarat:
- Kapasitas tempat: x + y ≤ 400
- Modal: 4.000x + 1.600y ≤ 1.000.000
- x ≥ 0
- y ≥ 0
Diagramnya:
Titik ekstrim:
- A(0, 400) bukan optimum sebab tak ada apel
- C(250, 0) bukan optimum alasannya tak ada pisang
dgn metode eliminasi 2 persamaan diatas diperoleh:
Sehingga jumlah masimum:
- Apel: 150 kg
- Pisang: 250 kg
Kontributor: Alwin Mulyanto, S.T.
Alumni Teknik Sipil FT UI
Materi Sosiologiku.com lainnya: