Program linear yakni suatu metode penentuan nilai optimum dr sebuah dilema linear. Nilai optimum (optimal atau minimum) diperoleh dr nilai dlm suatu himpunan penyelesaiaan persoalan linear. Di dlm persoalan linear terdapat fungsi linear yg bisa disebut sebagai fungsi objektif. Persyaratan, batasan, & hambatan dlm persoalan linear merupakan sistem pertidaksamaan linear.
Daftar Isi
Model Matematika Program Linear
Persoalan dlm acara linear yg masih dinyatakan dlm kalimat-kalimat pernyataan biasa , kemudian diubah kedalam model matematika. Model matematika merupakan pernyataan yg menggunakan peubah & notasi matematika.
Sebagai gambaran, produsen sepatu menciptakan 2 model sepatu memakai 2 bahan yg berbeda. Komposisi model pertama terdiri dr 200 gr bahan pertama & 150 gr materi kedua. Sedangkan komposisi versi kedua terdiri dr 180 gr materi pertama & 170 gr materi kedua. Persediaan di gudang materi pertama 72 kg & bahan kedua 64 kg. Harga model pertama yakni Rp. 500.000,00 & versi kedua Rp. 400.000,00. Jika ditarik kesimpulan/disederhanakan dlm bentuk tabel menjadi berikut:
Dengan peubah dr jumlah optimal versi 1 yakni x & model 2 adalah y, & hasil penjualan optimal yaitu f(x, y) = 500.000x + 400.000y. Dengan syarat:
- Jumlah maksimal materi 1 adalah 72.000 gr, maka 200x + 180y ≤ 72.000.
- Jumlah maksimal materi 2 adalah 64.000 gr, maka 150x + 170y ≤ 64.000
- Masing-masing model mesti yang dibuat.
Model matematika untuk menerima jumlah pemasaran yg maksimum ialah:
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 & batasan-batas-batas pertidaksamaan linear yg mempunyai himpunan solusi. Himpunan solusi yg ada merupakan titik-titik dlm diagram cartesius yg kalau koordinatnya disubstitusikan kedalam fungsi linear mampu memenuhi standar yg ditentukan.
Nilai optimum fungsi objektif dr suatu persoalan linear dapat diputuskan dgn metode grafik. Dengan menyaksikan grafik dr fungsi objektif & batas-batas-batasannya mampu diputuskan letak titik yg menjadi nilai optimum. Langkah-langkahnya sebagai berikut :
- Menggambar himpunan solusi dr semua batasan syarat yg ada di cartesius.
- Menentukan titik-titik ekstrim yg merupakan perpotongan garis batasan dgn garis batasan yg lainnya. Titik-titik ekstrim tersebut merupakan himpunan solusi dr batasannya & memiliki kemungkinan besar membuat fungsi menjadi optimum.
- Menyelidiki nilai optimum fungsi objektif dgn dua agenda yakni :
- 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 yakni
ax + by = Z
Nilai Z diberikan sembarang nilai. Garis ini dibuat sesudah grafik himpunan penyelesaian pertidaksamaan dibentuk. Garis selidik awal dibuat di area himpunan solusi permulaan. Kemudian dibuat garis-garis yg sejajar dgn garis selidik permulaan. Berikut anutan untuk memudahkan penyelidikian nilai fungsi optimum:
Cara 1 (syarat a > 0)
- Jika maksimum, maka dibuat garis yg sejajar garis selidik permulaan sehingga membuat himpunan solusi berada di kiri garis tersebut. Titik yg dilalui garis tersebut yaitu titik maksimum.
Jika minimum, maka dibentuk garis yg sejajar garis selidik permulaan sehingga menciptakan himpunan solusi berada di kanan garis tersebut. Titik yg dilalui garis tersebut ialah titik minimum.
Cara 2 (syarat b > 0)
- Jika maksimum, maka dibuat garis yg sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di bawah garis tersebut. Titik yg dilalui garis tersebut ialah titik maksimum.
- Jika minimum, maka dibuat garis yg sejajar garis selidik awal sehingga membuat himpunan penyelesaian berada di atas garis tersebut. Titik yg dilalui garis tersebut adalah titik minimum.
Untuk nilai a < 0 & b < 0 berlaku kebalikan dr kedua cara yg dijelaskan di atas.
Membandingkan Nilai Fungsi Tiap Titik Ekstrim
Menyelidiki nilai optimum dr fungsi objektif pula dapat dilakukan dgn apalagi dulu memilih titik-titik potong dr garis-garis batas yg ada. Titik-titip potong tersebut merupakan nilai ekstrim yg memiliki potensi memiliki nilai maksimum di salah satu titiknya.
Berdasarkan titik-titik tersebut ditentukan nilai masing-masing fungsinya, kemudian dibandingkan. Nilai terbesar 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 diketahui titik A & B mempunyai 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 dicapai pada pada grafik ini!
Pembahasan 2:
Titik ekstrim pada gambar yaitu:
- A tak mungkin maksimum karena titik paling kiri.
- B(3, 6)
- C(8, 2)
- D(8, 0)
Nilai tiap titik ekstrim yakni:
Sehingga nilai maksimum ada pada titik yg melalui 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 menampung 400 kg buah. Tentukan jumlah apel & pisang supaya 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 karena tak ada apel
- C(250, 0) bukan optimum alasannya adalah 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 Wargamasyarakat.org lainnya: