Program Linier – Definisi, Model Matematika dan Contoh Soalnya
Hallo sobat artikel kali ini membahas pemrograman linear mulai dari definisi, nilai dan fungsinya, berikut model beserta contoh soalnya.
Program linier adalah program yang digunakan sebagai metode, umumnya digunakan untuk memecahkan masalah seperti alokasi sumber daya, dan tujuan utamanya adalah untuk menentukan nilai minimum atau maksimum.
Untuk lebih jelasnya mari kita simak pembahasan selengkapnya dibawah ini :
Definisi pemrograman linier
pemrograman linier adalah program yang digunakan sebagai metode untuk mencari nilai optimal dari suatu masalah linier.
Nilai optimal atau maksimum atau minimum dapat diperoleh dari nilai dalam rangkaian solusi masalah linier.
Dalam masalah linier terdapat fungsi linier yang bisa disebut fungsi tujuan.
Persyaratan, kendala, dan pembatasan dalam masalah linier adalah sistem pertidaksamaan linier.
Lihat tabel di bawah ini dengan masalah maksimum dan minimum:
| MASALAH MAKSIMAL | MASALAH MINIMAL |
|---|---|
| Maksimum f (x,y) = kapak + oleh | minimum f (x,y) = kapak + oleh |
| Kondisi: c1x + d1y ≤ k1 c2x + d2y ≤ k2 x ≥ 0 y ≥ 0 |
Kondisi: m1x + n1y ≤ k1 m2x + n2y ≤ k2 x ≥ 0 y ≥ 0 |
| Dengan ABCD adalah koefisien dan k adalah konstanta | Dengan a,b,m,n adalah koefisien dan k adalah konstanta |
Nilai optimal dari fungsi tujuan
Fungsi tujuan adalah fungsi linier dan begitu juga kendala pertidaksamaan linier yang memiliki himpunan solusi.
Himpunan solusi yang sudah ada sebelumnya adalah dalam bentuk titik-titik pada diagram Kartesius di mana ketika koordinat disubstitusikan ke dalam fungsi linier, mereka dapat memenuhi persyaratan yang ditentukan.
Nilai optimal dari fungsi objektif suatu masalah linier dapat ditentukan dengan menggunakan metode grafis.
Dengan melihat grafik fungsi tujuan dan batasannya, kita dapat menentukan letak titik yang memiliki nilai optimal.
Langkah-langkahnya adalah sebagai berikut:
- Gambarkan himpunan solusi dari semua kendala kondisional yang sudah ada di Cartesian.
- Tentukan titik ekstrim dimana garis batas berpotongan dengan garis batas lainnya. Titik ekstrim adalah himpunan solusi untuk kendala dan memiliki probabilitas tinggi untuk dapat membuat fungsi menjadi optimal.
- Pengujian nilai optimal fungsi tujuan menggunakan dua metode, yaitu:
- Mengenakan garis yang terdengar dan juga
- Bandingkan setiap nilai fungsi tujuan pada setiap titik ekstrim.
1. Menggunakan baris kueri
Garis probe dapat diperoleh dari fungsi tujuan f(x,y) = ax + dengan di mana garis probe adalah:
kapak + oleh = Z
Nilai Z pada nilai berapa pun.
Garis ini dibuat setelah grafik himpunan penyelesaian pertidaksamaan juga dibuat.
Baris pertama probe akan diproduksi di area pemukiman dari awal. Kemudian garis paralel ditarik menggunakan garis probe awal.
Pedoman berikut akan membantu menentukan nilai fungsional yang optimal:
Metode 1 (kondisi a > 0), yaitu:
- Jika maksimum, garis harus ditarik sejajar dengan garis probe awal sehingga satu set solusi dapat dihasilkan di sebelah kiri garis itu. Titik di mana garis melewati adalah titik maksimum.
Jika minimum, buat garis sejajar dengan garis awal penyelidikan sehingga ada himpunan solusi di sebelah kanan garis itu.
Titik yang dilalui garis adalah titik minimum.
Lihat grafik di bawah ini:
Cara ke-2 (kondisi b > 0) yaitu:
- Jika maksimum: Artinya, ditarik garis yang sejajar dengan garis probe awal, menciptakan serangkaian solusi yang berada di bawah garis tersebut. Titik yang dilalui garis adalah titik maksimum.
- Jika minimum: Jadi gambarlah garis yang sejajar dengan garis awal penyelidikan, sehingga dihasilkan himpunan penyelesaian yang terletak di atas garis ini. Titik yang dilalui garis adalah titik minimum.
Lihatlah grafik di bawah ini:
Untuk nilai a < 0 dan juga b < 0, berlaku kebalikan dari kedua metode yang dijelaskan di atas.
2. Bandingkan dengan nilai fungsi pada setiap titik ekstrim
Pemeriksaan dengan nilai optimal fungsi sasaran dapat dilakukan dengan terlebih dahulu menentukan titik potong dari suatu garis batas yang ada. Titik potong merupakan nilai ekstrim yang berpotensi memiliki nilai maksimum pada salah satu titik.
Berdasarkan poin-poin tersebut, dapat ditentukan nilai masing-masing fungsi, yang kemudian dibandingkan.
Nilai terbesar adalah nilai maksimum dan juga nilai terkecil adalah nilai minimum.
Model matematika dari program linier
Masalah program linier yang masih dirumuskan dalam pernyataan umum kemudian diubah menjadi model matematika.
Model matematika adalah pernyataan yang menggunakan variabel dan notasi matematika.
Sebagai ilustrasi:
Sebuah produsen sepatu memproduksi 2 model sepatu dari 2 bahan yang berbeda. Komposisi model pertama adalah 200 g bahan pertama dan 150 g bahan kedua.
Sedangkan komposisi model kedua terdiri dari 180 gram bahan pertama dan 170 gram bahan kedua. Stok di gudang material pertama sebanyak 76 kg dan stok di gudang kedua sebanyak 64 kg.
Harga model pertama Rp 500.000,00 dan model kedua harganya Rp 400.000,00.
Ketika diselesaikan atau disederhanakan dalam bentuk tabel, bunyinya sebagai berikut:
| jenis sepatu | kain 1 | kain 2 | harga sepatu | jumlah sepatu |
|---|---|---|---|---|
| model 1 | 200 gram | 150g | Rp500.000,00 | x |
| model 2 | 180g | 170g | Rp400.000,00 | j |
| Ketersediaan | 72.000 gram | 64.000 gram |
Dengan perubahan dari bilangan optimal model 1 yaitu x dan model 2 yaitu y, serta hasil turnover optimal yaitu f(x,y) = 500.000x + 400.000y. Dengan beberapa syarat:
- Jika jumlah maksimum bahan 1 adalah 72.000g, maka 200x + 150y ≤ 72.000.
- Jika jumlah maksimum bahan 2 adalah 64.000 g, maka 180x + 170y ≤ 64.000
- Setiap orang di setiap model harus dibuat.
Model matematika untuk mencapai jumlah penjualan maksimum adalah:
| PEMODELAN MAKSIMAL |
|---|
| Maksimum f(x,y) = 500.000 + 400.000 tahun |
| Persyaratan: 200x +150y ≤ 72.000 180 x +170j ≤ 64.000 x ≥ 0 y ≥ 0 |
Contoh soal program linier
Tentukan di mana dalam diagram ini nilai maksimum dari fungsi f(x, y) = 4x + 5y harus tercapai!
Diskusi 2:
Titik ekstrim pada gambar di atas adalah:
- A tidak bisa maksimal karena titik A paling kiri.
- B(3, 6)
- C(8, 2)
- D(8, 0)
Nilai pada setiap titik ekstrim adalah:
Sehingga dapat dilihat hasilnya, nilai maksimum hanya pada titik yang melalui garis BC dimana nilai maksimumnya adalah 42.
Hal tersebut dapat admin sampaikan pada materi kali ini yaitu tentang linear programming. Kami berharap materi yang dibahas dalam artikel ini dapat membawa pemahaman dan manfaat bagi pembaca semua.
Baca juga:
