Bimbel SBMPTN / SIMAK
Bimbel Tes SMAKBO
Pemrograman linier, teknik pemodelan matematika di mana fungsi linier dimaksimalkan atau diminimalkan ketika mengalami berbagai kendala. Teknik ini berguna untuk memandu keputusan kuantitatif dalam perencanaan bisnis, dalam teknik industri, dan—pada tingkat yang lebih rendah—dalam ilmu sosial dan fisika.
Apa itu Pemrograman Linier?
Pemrograman linier (LP) atau disebut juga Optimasi Linier dapat didefinisikan sebagai masalah memaksimalkan atau meminimalkan fungsi linier yang dikenai kendala linier. Kendala tersebut dapat berupa persamaan atau ketidaksetaraan. Masalah optimasi melibatkan perhitungan keuntungan dan kerugian. Masalah pemrograman linier adalah kelas penting dari masalah optimasi, yang membantu untuk menemukan daerah yang layak dan mengoptimalkan solusi untuk memiliki nilai fungsi tertinggi atau terendah.
Dengan kata lain, pemrograman linier dianggap sebagai metode optimasi untuk memaksimalkan atau meminimalkan fungsi tujuan dari model matematika yang diberikan dengan himpunan beberapa persyaratan yang diwakili dalam hubungan linier. Tujuan utama dari masalah program linier adalah untuk menemukan solusi optimal.
Pemrograman linier adalah metode untuk mempertimbangkan ketidaksetaraan yang berbeda yang relevan dengan situasi dan menghitung nilai terbaik yang diperlukan untuk diperoleh dalam kondisi tersebut. Beberapa asumsi yang diambil saat bekerja dengan pemrograman linier adalah:
- Jumlah kendala harus dinyatakan dalam istilah kuantitatif
- Hubungan antara kendala dan fungsi tujuan harus linier
- Fungsi linier (yaitu, fungsi tujuan) harus dioptimalkan
Komponen Pemrograman Linier
Komponen dasar LP adalah sebagai berikut:
- Variabel Keputusan
- Kendala
- Data
- Fungsi Tujuan
Karakteristik Pemrograman Linier
Berikut ini adalah lima karakteristik masalah program linier:
Kendala – Batasan harus dinyatakan dalam bentuk matematika, mengenai sumber daya.
Fungsi Tujuan - Dalam suatu masalah, fungsi tujuan harus ditentukan secara kuantitatif.
Linearitas – Hubungan antara dua atau lebih variabel dalam fungsi harus linier. Artinya derajat variabelnya adalah satu.
Keterbatasan – Harus ada angka input dan output yang terbatas dan tidak terbatas. Dalam kasus, jika fungsi memiliki faktor tak hingga, solusi optimal tidak layak.
Non-negatif – Nilai variabel harus positif atau nol. Seharusnya tidak menjadi nilai negatif.
Variabel Keputusan – Variabel keputusan akan menentukan output. Ini memberikan solusi akhir dari masalah. Untuk masalah apapun, langkah pertama adalah mengidentifikasi variabel keputusan.
Masalah Pemrograman Linier
Masalah Pemrograman Linier (LPP) adalah masalah yang berkaitan dengan mencari nilai optimal dari fungsi linier yang diberikan. Nilai optimal dapat berupa nilai maksimum atau nilai minimum. Di sini, fungsi linier yang diberikan dianggap sebagai fungsi tujuan. Fungsi tujuan dapat berisi beberapa variabel, yang tunduk pada kondisi dan harus memenuhi himpunan pertidaksamaan linier yang disebut kendala linier. Masalah program linier dapat digunakan untuk mendapatkan solusi optimal untuk skenario berikut, seperti masalah manufaktur, masalah diet, masalah transportasi, masalah alokasi dan sebagainya.
Metode untuk Memecahkan Masalah Pemrograman Linier
Masalah pemrograman linier dapat diselesaikan dengan menggunakan metode yang berbeda, seperti metode grafis, metode simpleks, atau dengan menggunakan alat seperti R, pemecah terbuka dll. Di sini, kita akan membahas dua teknik terpenting yang disebut metode simpleks dan metode grafis dalam rinci.
Metode Simpleks Pemrograman Linier
Metode simpleks adalah salah satu metode yang paling populer untuk menyelesaikan masalah program linier. Ini adalah proses iteratif untuk mendapatkan solusi optimal yang layak. Dalam metode ini, nilai variabel dasar terus ditransformasikan untuk mendapatkan nilai maksimum untuk fungsi tujuan. Algoritma untuk metode simpleks pemrograman linier disediakan di bawah ini:
Langkah 1: Menetapkan masalah yang diberikan. (yaitu,) tuliskan kendala pertidaksamaan dan fungsi tujuan.
Langkah 2: Ubah pertidaksamaan yang diberikan menjadi persamaan dengan menambahkan variabel slack ke setiap ekspresi pertidaksamaan.
Langkah 3: Buat tablo simpleks awal. Tulislah fungsi tujuan pada baris paling bawah. Di sini, setiap kendala ketidaksetaraan muncul di barisnya sendiri. Sekarang, kita dapat merepresentasikan masalah dalam bentuk matriks yang diperbesar, yang disebut tablo simpleks awal.
Langkah 4: Identifikasi entri negatif terbesar di baris bawah, yang membantu mengidentifikasi kolom pivot. Entri negatif terbesar di baris bawah mendefinisikan koefisien terbesar dalam fungsi tujuan, yang akan membantu kita meningkatkan nilai fungsi tujuan secepat mungkin.
Langkah 5: Hitung hasil bagi. Untuk menghitung hasil bagi, kita perlu membagi entri di kolom paling kanan dengan entri di kolom pertama, tidak termasuk baris bawah. Hasil bagi terkecil mengidentifikasi baris. Baris yang diidentifikasi dalam langkah ini dan elemen yang diidentifikasi dalam langkah akan diambil sebagai elemen pivot.
Langkah 6: Lakukan pivoting untuk membuat semua entri lain di kolom adalah nol.
Langkah 7: Jika tidak ada entri negatif
Langkah 8: Akhirnya, tentukan solusi yang terkait dengan tablo simpleks akhir
Metode Grafis
Metode grafis digunakan untuk mengoptimalkan program linier dua variabel. Jika masalah memiliki dua variabel keputusan, metode grafis adalah metode terbaik untuk menemukan solusi optimal. Dalam metode ini, himpunan pertidaksamaan dikenai kendala. Kemudian pertidaksamaan diplot pada bidang XY. Setelah semua pertidaksamaan diplot dalam grafik XY, daerah yang berpotongan akan membantu menentukan daerah yang layak. Wilayah yang layak akan memberikan solusi optimal serta menjelaskan semua nilai yang dapat diambil oleh model kami. Mari kita lihat contoh di sini dan memahami konsep pemrograman linier dengan cara yang lebih baik.
Contoh:
Hitung nilai maksimal dan minimal dari z = 5x + 3y untuk kendala berikut.
x + 2 tahun 14
3x – y 0
x – y 2
Penyelesaian:
Tiga ketidaksetaraan menunjukkan kendala. Luas bidang yang akan diberi tanda adalah daerah fisibel.
Persamaan optimasi (z) = 5x + 3y. Anda harus mencari titik sudut (x,y) yang memberikan nilai z terbesar dan terkecil.
Untuk memulainya, selesaikan dulu setiap pertidaksamaan.
x + 2y 14 y -(1/2)x + 7
3x – y 0 y 3x
x – y 2 y x – 2
Berikut adalah grafik untuk persamaan di atas.
Pemrograman Linier - Grafik
Sekarang pasangkan garis untuk membentuk sistem persamaan linier untuk menemukan titik sudut.
y = -(½) x + 7
y = 3x
Memecahkan persamaan di atas, kita mendapatkan titik sudut sebagai (2, 6)
y = -1/2 x + 7
y = x – 2
Memecahkan persamaan di atas, kita mendapatkan titik sudut sebagai (6, 4)
y = 3x
y = x – 2
Memecahkan persamaan di atas, kita mendapatkan titik sudut sebagai (-1, -3)
Untuk sistem linier, nilai maksimum dan minimum persamaan optimasi terletak pada sudut wilayah kelayakan. Oleh karena itu, untuk menemukan solusi optimal, Anda hanya perlu memasukkan ketiga titik ini ke dalam z = 3x + 4y
(2, 6) :
z = 5(2) + 3(6) = 10 + 18 = 28
(6, 4):
z = 5(6) + 3(4) = 30 + 12 = 42
(-1, –3):
z = 5(-1) + 3(-3) = -5 -9 = -14
Jadi, maksimum z = 42 terletak pada (6, 4) dan minimum z = -14 terletak pada (-1, -3)
Semoga bermanfaat.
Bimbel SBMPTN - SIMAK UI
Bimbel Tes SMAKBO
Info Bimbel SBMPTN 2021 :
Info Bimbel SIMAK 2021 :
