Pemrograman linier bukan hanya matematika abstrak. Ini adalah mesin di balik logistik, rantai pasokan, dan manajemen sumber daya. Intinya adalah metode simpleks. Teknik standar ini menemukan hasil terbaik dalam sistem yang ditentukan oleh batasan dan fungsi tujuan.
Pikirkan seperti ini. Anda punya tujuan. Mungkin memaksimalkan keuntungan atau meminimalkan biaya. Anda juga punya batasan. Jam mesin. Bahan mentah. Tenaga kerja. Metode simpleks menavigasi batas-batas ini untuk menemukan puncaknya. Ia tidak menebak. Ini menghitung.
Mengapa Kita Membutuhkan Pendekatan Sistematis
Anda mungkin berpikir Anda bisa membuat grafik dua variabel dan melihat perpotongannya. Itu berfungsi untuk masalah sederhana. Sebuah pabrik membuat dua produk. Anda menggambar garis. Anda menemukan sudut di mana keuntungan mencapai puncaknya. Itu visual. Itu intuitif.
Namun kenyataannya jarang sekali yang bersifat dua dimensi. Masalah nyata melibatkan ratusan persamaan dan ribuan variabel. Jumlah solusi potensial menjadi sangat besar. Menggambar grafik untuk seribu variabel adalah hal yang mustahil. Anda memerlukan dimensi yang tidak dapat Anda lihat.
George Dantzig memecahkan masalah ini pada tahun 1947. Dia bekerja sebagai penasihat matematika untuk Angkatan Udara AS. Militer mempunyai masalah logistik yang sangat besar. Mereka perlu mengoptimalkan rute pasokan dan alokasi sumber daya. Dantzig merancang metode simpleks untuk menghilangkan kebisingan.
Metode ini membatasi jumlah titik ekstrim yang harus diperiksa. Ini mengubah tugas yang mustahil menjadi tugas yang bisa dikelola. Ini tetap menjadi algoritma standar pada komputer saat ini. Salah satu alat paling berguna yang pernah ditemukan.
Cara Kerja Metode Simpleks Langkah demi Langkah
Prosesnya sistematis. Ia berpindah dari satu kemungkinan ke kemungkinan berikutnya. Begini cara penerapannya.
Pertama, ini mengasumsikan Anda memiliki titik awal. Sebuah titik ekstrim. Jika Anda tidak memilikinya, varian yang disebut Fase I akan menemukan titik awal yang memungkinkan atau menentukan bahwa tidak ada solusi.
Selanjutnya, metode ini menguji titik tersebut. Apakah sudah optimal? Spesifikasi aljabar dari soal menjalankan pemeriksaan ini. Jika pengujian gagal, algoritma berpindah ke titik ekstrim yang berdekatan. Ia bergerak di sepanjang tepian. Ia memilih arah dimana fungsi tujuan meningkat pada tingkat tercepat.
Terkadang fungsinya meningkat tanpa batas. Prosedur berhenti dan mengidentifikasi tepi di mana nilainya menjadi positif tak terhingga. Anda telah menemukan solusi tanpa batas.
Jika itu tidak terjadi, Anda akan mencapai titik ekstrim baru. Poin ini setidaknya mempunyai nilai yang sama tingginya dengan poin sebelumnya. Urutannya berulang. Ini berlanjut hingga menemukan titik optimal atau mengidentifikasi ketidakterbatasan.
Secara teori, langkah-langkah tersebut dapat bertambah secara eksponensial dengan jumlah titik ekstrim. Dalam praktiknya, konvergensi berlangsung cepat. Biasanya hanya diperlukan kelipatan kecil dari jumlah titik ekstrim.
Contoh Konkret: Memaksimalkan Keuntungan Pabrik
Mari kita lihat kasus nyata. Sebuah pabrik menghasilkan dua produk. Kami menyebutnya x1 dan x2. Keuntungan tipe kedua dua kali lipat keuntungan tipe pertama. Total keuntungan diwakili oleh persamaan:
x1 + 2×2
Ini adalah fungsi tujuan Anda. Anda ingin memaksimalkannya.
Tentu saja, Anda hanya ingin membuat x2. Ini menghasilkan lebih banyak uang per unit. Namun ada kendala. Anda tidak bisa berproduksi tanpa batas.
Berikut adalah batasan dunia nyata:
- Bahan baku untuk x2 membatasi produksi hingga lima unit per batch (x2 ≤ 5).
- Bahan baku untuk x1 membatasi produksi hingga delapan unit per batch (x1 ≤ 8).
- Waktu mesin memungkinkan maksimal sepuluh unit total (x1 + x2 ≤ 10).
- Anda tidak dapat menghasilkan jumlah negatif (x1 ≥ 0 dan x2 ≥ 0).
Metode simpleks mencari nilai x1 dan x2 yang memaksimalkan keuntungan dalam batasan tersebut. Solusi apa pun adalah sepasang angka (x1, x2). Misalnya, menghasilkan tiga dari x1 dan enam dari x2 adalah titik valid (3, 6).
Jika diplot pada grafik, batasan ini membentuk daerah poligonal. Ini adalah rangkaian solusi yang layak. Titik-titik di luar wilayah ini melanggar satu atau lebih batasan.
Untuk melihat bagaimana metode simpleks mengidentifikasi titik optimal, perhatikan fungsi tujuan x1 + 2×2 = k. Jika Anda menyetel k ke 4, Anda mendapatkan garis pada grafik. Saat Anda menambah k, Anda mendapatkan garis sejajar. Nilai k tertinggi yang masih menyentuh daerah layak adalah keuntungan semaksimal mungkin.
Pada contoh ini, garis k = 15 menyentuh daerah di titik (5, 5). Jika k lebih tinggi, garis berada di luar himpunan layak. Solusi optimalnya adalah memproduksi setiap komoditas dalam jumlah yang sama.
Mengapa Simpul Penting dalam Pemrograman Linier
Hasilnya bukanlah suatu kebetulan. Dalam permasalahan linier, solusi optimal selalu terjadi pada suatu titik. Sebuah titik ekstrim.
Ini adalah sifat mendasar dari pemrograman linier. Fungsinya linier. Kendalanya linier. Bentuknya adalah poligon cembung (atau polihedron dalam dimensi lebih tinggi). Puncak fungsi linier pada himpunan cembung selalu berada pada sudut.
Anda tidak perlu memeriksa setiap titik di wilayah yang memungkinkan. Anda hanya perlu memeriksa simpulnya. Metode simpleks melakukan hal ini. Ia melompat dari titik ke titik. Itu naik ke permukaan wilayah yang memungkinkan. Itu berhenti ketika tidak bisa lebih tinggi.
Terkadang hasil optimal tidaklah unik. Seluruh sisi mungkin menghasilkan nilai maksimum yang sama. Namun metode simpleks tetap akan menemukan salah satu titik optimal tersebut. Ini memberi Anda jawaban yang konkrit. Data yang dapat ditindaklanjuti.
Bagi pelajar dan profesional, memahami mekanisme ini adalah kuncinya. Ini bukan hanya tentang menyelesaikan persamaan. Ini tentang mengetahui cara menavigasi sistem yang kompleks dengan sumber daya yang terbatas. Metode simpleks menyediakan jalannya.
Metode simpleks tidak sekedar menebak jawaban. Ia berjalan di sepanjang tepi wilayah yang memungkinkan, memeriksa simpul hingga menemukan simpul terbaik. Ini dimulai dengan membersihkan matematika. Anda mengambil ketidaksetaraan linier yang berantakan itu dan mengubahnya menjadi persamaan yang bersih. Anda melakukan ini dengan menambahkan “variabel kendur”.
Anggaplah slack sebagai kapasitas yang tersisa. Jika Anda memiliki batasan seperti $x_1 \le 8$, tambahkan variabel $x_3$ sehingga $x_1 + x_3 = 8$. Dan ingat, $x_3$ harus lebih besar atau sama dengan nol. Anda melakukan ini untuk setiap kendala.
- $x_1 + x_3 = 8$ (dengan $x_3 \ge 0$)
- $x_2 + x_4 = 5$ (dengan $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10$ (dengan $x_5 \ge 0$)
Anda juga memerlukan variabel untuk fungsi tujuan itu sendiri. Sebut saja $x_0$. Jika tujuan Anda adalah memaksimalkan $x_0 = x_1 + 2x_2$, tulis ulang menjadi $x_1 + 2x_2 – x_0 = 0$.
Sekarang masalahnya lebih sederhana. Temukan nilai non-negatif untuk $x_1$ hingga $x_5$. Hasilkan $x_0$ sebesar mungkin.
Mulai dari Asal
Di mana Anda memulai? Tempat yang paling mudah adalah titik asal. Tetapkan semua variabel keputusan ke nol. $x_1 = 0$. $x_2 = 0$.
Ini adalah solusi yang valid. Ini adalah titik ekstrem. Faktanya, ini adalah tikungan awal. Nilai objektif $x_0$ juga nol. Tidak bagus, tapi ini adalah langkah yang sah.
Bisakah kita berbuat lebih baik? Ya. Jika Anda meningkatkan salah satu variabel dari nol dan menjaga variabel lainnya tetap nol, $x_0$ akan naik. Pertanyaannya adalah variabel mana yang memberikan keuntungan terbesar bagi Anda.
Perhatikan persamaan objektifnya: $x_1 + 2x_2 – x_0 = 0$. Menata ulang untuk $x_0$, Anda mendapatkan $x_0 = x_1 + 2x_2$.
Meningkatkan $x_1$ menambah 1 ke total. Meningkatkan $x_2$ menambah 2. $x_2$ jelas merupakan pemenangnya. Ini menghasilkan peningkatan terbesar dalam $x_0$ per perubahan unit. Jadi, Anda memilih $x_2$ dan mendorongnya ke atas.
Mencapai Kendala Pertama
Anda tidak dapat meningkatkan $x_2$ selamanya. Variabelnya harus tetap non-negatif. Jika Anda menekan $x_2$ melewati jam 5, ada yang rusak. Secara khusus, lihat batasan kedua: $x_2 + x_4 = 5$.
Jika $x_2 = 6$, maka $x_4$ menjadi -1. Itu tidak diperbolehkan. Persyaratan non-negatif bertindak sebagai penghentian yang sulit. Batasnya adalah 5.
Jadi, Anda menetapkan $x_2 = 5$. Seperti apa solusinya sekarang?
- $x_2 = 5$
- $x_1 = 0$ (masih nol)
- $x_4 = 0$ (variabel ini mencapai batas, jadi sekarang nol)
- $x_3 = 8$ (karena $0 + 8 = 8$)
- $
