Contoh Soal Program Linear dan Penyelesaiannya Kelas 11
Program linear adalah model matematika yang digunakan untuk mengoptimalkan tujuan, seperti memaksimalkan keuntungan atau meminimalkan biaya, dengan mempertimbangkan batasan-batasan tertentu. Program linear banyak digunakan dalam dunia bisnis, ekonomi, dan rekayasa.
Salah satu aplikasi program linear yang banyak dijumpai adalah dalam mengalokasikan sumber daya secara optimal. Misalnya, sebuah perusahaan ingin memproduksi dua jenis produk, A dan B, yang membutuhkan bahan baku X dan Y. Perusahaan memiliki persediaan bahan baku X sebanyak 100 unit dan bahan baku Y sebanyak 150 unit. Penjualan produk A menghasilkan keuntungan Rp10.000 per unit, sedangkan produk B menghasilkan keuntungan Rp15.000 per unit.
Penyelesaian dengan Metode Grafik
Salah satu metode yang dapat digunakan untuk menyelesaikan program linear adalah metode grafik. Metode ini dapat digunakan untuk menyelesaikan masalah program linear yang hanya memiliki dua variabel.
- Buat grafik untuk batasan-batasan masalah program linear.
- Tentukan titik-titik potong dari batasan-batasan tersebut.
- Tandai wilayah yang memenuhi semua batasan.
- Tentukan nilai tujuan untuk setiap titik sudut wilayah yang memenuhi batasan.
- Pilih titik sudut yang memberikan nilai tujuan optimal.
Dalam contoh di atas, batasan-batasan masalah program linear dapat dinyatakan sebagai berikut:
| Batasan | Persamaan |
|---|---|
| Persediaan bahan baku X | 100x + 150y ≤ 100 |
| Persediaan bahan baku Y | 100x + 150y ≤ 150 |
| Non-negatif | x ≥ 0, y ≥ 0 |
Dengan menggambar grafik untuk batasan-batasan tersebut dan menentukan titik-titik potongnya, dapat diperoleh wilayah layak masalah program linear sebagai berikut:
Titik-titik sudut wilayah layak tersebut adalah:
- (0, 0)
- (1, 0)
- (0, 1)
- (2/3, 1)
Dengan menghitung nilai tujuan untuk setiap titik sudut, dapat diperoleh:
| Titik Sudut | Nilai Tujuan |
|---|---|
| (0, 0) | Rp0 |
| (1, 0) | Rp10.000 |
| (0, 1) | Rp15.000 |
| (2/3, 1) | Rp16.666,67 |
Berdasarkan perhitungan di atas, diperoleh bahwa titik sudut (2/3, 1) memberikan nilai tujuan optimal sebesar Rp16.666,67. Artinya, perusahaan harus memproduksi 2/3 unit produk A dan 1 unit produk B untuk memaksimalkan keuntungan.
Penyelesaian dengan Metode Simpleks
Selain metode grafik, program linear juga dapat diselesaikan dengan menggunakan metode simpleks. Metode ini lebih sistematis dan dapat digunakan untuk menyelesaikan masalah program linear dengan lebih dari dua variabel.
Langkah-langkah metode simpleks:
- Ubah masalah program linear menjadi bentuk baku.
- Buat tabel simpleks awal.
- Pilih variabel masuk dan variabel keluar.
- Lakukan operasi baris elementer untuk memperbarui tabel simpleks.
- Ulangi langkah 3 dan 4 sampai diperoleh solusi optimal.
Untuk contoh di atas, langkah-langkah metode simpleks dapat dilakukan sebagai berikut:
1. Mengubah masalah menjadi bentuk baku
Tambahkan variabel slack pada setiap batasan agar menjadi persamaan.
| Batasan | Persamaan Baku |
|---|---|
| Persediaan bahan baku X | 100x + 150y + s1 = 100 |
| Persediaan bahan baku Y | 100x + 150y + s2 = 150 |
| Non-negatif | x ≥ 0, y ≥ 0, s1 ≥ 0, s2 ≥ 0 |
2. Membuat tabel simpleks awal
Buat tabel simpleks awal dengan variabel keputusan, variabel slack, dan variabel tujuan sebagai berikut:
| Variabel | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x | 1 | 0 | 1 | 0 | 0 |
| y | 0 | 1 | 0 | 1 | 0 |
| s1 | 100 | 150 | 1 | 0 | 100 |
| s2 | 100 | 150 | 0 | 1 | 150 |
| z | -10.000 | -15.000 | 0 | 0 | 0 |
3. Memilih variabel masuk dan variabel keluar
Pilih variabel masuk sebagai variabel yang memiliki koefisien negatif terkecil pada baris tujuan (z). Dalam kasus ini, variabel masuk adalah x.
Pilih variabel keluar sebagai variabel yang memiliki rasio terkecil antara nilai RHS dan koefisien variabel masuk pada kolom variabel masuk. Dalam kasus ini, variabel keluar adalah s1.
4. Melakukan operasi baris elementer
Lakukan operasi baris elementer untuk membuat nilai variabel masuk pada baris variabel keluar sama dengan 1 dan membuat nilai variabel lainnya pada kolom variabel masuk sama dengan 0.
Tabel simpleks setelah operasi baris elementer:
| Variabel | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x | 1 | 0 | 1 | 0 | 0 |
| y | 0 | 1 | -1/3 | 1/3 | 0 |
| s1 | 0 | 0 | 1/3 | -1/3 | 100 |
| s2 | 0 | 0 | 2/3 | 1/3 | 50 |
| z | 0 | 0 | -10.000/3 | -5.000/3 | 16.666,67 |
5. Mengulangi langkah 3 dan 4
Ulangi langkah 3 dan 4 sampai diperoleh solusi optimal. Dalam kasus ini, solusi optimal sudah diperoleh pada iterasi pertama.
Solusi optimal:
- x = 2/3
- y = 1
- s1 = 0
- s2 = 0
Dengan demikian, nilai tujuan optimal adalah Rp16.666,67.
FAQ
Q: Apa itu program linear?
