Optimisasi adalah salah satu cabang penting dalam matematika terapan yang berfokus pada menemukan solusi terbaik dari sekumpulan alternatif. Ini bisa berarti memaksimalkan atau meminimalkan fungsi objektif berdasarkan batasan-batasan tertentu. Optimisasi memiliki aplikasi luas dalam berbagai bidang, seperti ekonomi, rekayasa, manajemen, dan ilmu komputer. Dua jenis optimisasi yang paling umum adalah pemrograman linear (linear programming) dan pemrograman non-linear (non-linear programming).
Pemrograman linear (PL) adalah metode optimisasi di mana fungsi objektif dan semua batasan yang terlibat adalah fungsi linear. Ini berarti bahwa variabel-variabel dalam permasalahan PL hanya muncul dalam pangkat satu dan tidak ada interaksi non-linear antar variabel. Contoh klasik dari pemrograman linear adalah masalah maximizing profit dalam konteks produksi, di mana perusahaan ingin menentukan berapa banyak produk yang harus dibuat untuk memaksimalkan keuntungan dengan batasan seperti biaya bahan baku dan tenaga kerja.
Masalah pemrograman linear umumnya diformulasikan sebagai:Maksimalkan (atau Minimalkan)c1x1+c2x2+⋯+cnxn\text{Maksimalkan (atau Minimalkan)} \quad c_1x_1 + c_2x_2 + \cdots + c_nx_nMaksimalkan (atau Minimalkan)c1x1+c2x2+⋯+cnxn Dengan syarata11x1+a12x2+⋯+a1nxn≤b1\text{Dengan syarat} \quad a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1Dengan syarata11x1+a12x2+⋯+a1nxn≤b1 a21x1+a22x2+⋯+a2nxn≤b2a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2a21x1+a22x2+⋯+a2nxn≤b2 ⋮\vdots⋮ x1,x2,…,xn≥0x_1, x_2, \ldots, x_n \geq 0x1,x2,…,xn≥0
Di sini, fungsi objektif c1x1+c2x2+⋯+cnxnc_1x_1 + c_2x_2 + \cdots + c_nx_nc1x1+c2x2+⋯+cnxn merepresentasikan tujuan yang ingin dicapai, seperti memaksimalkan keuntungan atau meminimalkan biaya. Batasan-batasan a11x1+a12x2+⋯+a1nxn≤b1a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1a11x1+a12x2+⋯+a1nxn≤b1 menggambarkan batasan fisik atau sumber daya yang harus dipenuhi. Variabel-variabel x1,x2,…,xnx_1, x_2, \ldots, x_nx1,x2,…,xn biasanya mewakili kuantitas yang dioptimalkan, seperti jumlah produk yang diproduksi.
Salah satu algoritma yang terkenal untuk menyelesaikan masalah pemrograman linear adalah Simplex Method yang ditemukan oleh George Dantzig pada tahun 1947. Metode ini efisien dan dapat menyelesaikan masalah besar dengan cukup cepat. Di zaman modern, metode Simplex dan variasinya digunakan dalam perangkat lunak optimisasi seperti CPLEX dan Gurobi.
Pemrograman linear memiliki banyak aplikasi, termasuk:
Berbeda dengan pemrograman linear, pemrograman non-linear (PNL) digunakan ketika fungsi objektif atau batasan memiliki bentuk non-linear, seperti melibatkan kuadrat atau interaksi antar variabel. Dalam banyak kasus di dunia nyata, hubungan antar variabel tidak selalu linier, sehingga pemrograman non-linear lebih realistis dan relevan untuk berbagai aplikasi.
Masalah pemrograman non-linear biasanya diformulasikan sebagai:Maksimalkan (atau Minimalkan)f(x1,x2,…,xn)\text{Maksimalkan (atau Minimalkan)} \quad f(x_1, x_2, \ldots, x_n)Maksimalkan (atau Minimalkan)f(x1,x2,…,xn) Dengan syaratgi(x1,x2,…,xn)≤biuntuk semuai\text{Dengan syarat} \quad g_i(x_1, x_2, \ldots, x_n) \leq b_i \quad \text{untuk semua} \quad iDengan syaratgi(x1,x2,…,xn)≤biuntuk semuai x1,x2,…,xn≥0x_1, x_2, \ldots, x_n \geq 0x1,x2,…,xn≥0
Dalam masalah PNL, fungsi objektif f(x1,x2,…,xn)f(x_1, x_2, \ldots, x_n)f(x1,x2,…,xn) dan/atau batasan gi(x1,x2,…,xn)g_i(x_1, x_2, \ldots, x_n)gi(x1,x2,…,xn) bisa berbentuk kuadrat, polinomial, atau fungsi eksponensial, membuat masalah ini lebih kompleks untuk diselesaikan dibanding pemrograman linear.
Tidak ada metode tunggal yang dapat digunakan untuk menyelesaikan semua masalah non-linear. Beberapa metode yang umum digunakan antara lain:
Pemrograman non-linear juga memiliki aplikasi yang luas, termasuk:
Perbedaan utama antara pemrograman linear dan non-linear terletak pada kompleksitas dan bentuk fungsi objektif serta batasannya. Pemrograman linear lebih mudah dipecahkan karena memiliki struktur yang sederhana dan algoritma yang lebih efisien. Sebaliknya, pemrograman non-linear membutuhkan pendekatan yang lebih canggih karena bentuk fungsi yang lebih kompleks.
Namun, meskipun lebih kompleks, pemrograman non-linear sering kali lebih akurat dalam merepresentasikan permasalahan dunia nyata yang melibatkan hubungan non-linear antar variabel.
Optimisasi, baik dalam bentuk pemrograman linear maupun non-linear, adalah alat penting dalam memecahkan berbagai masalah di dunia nyata. Sementara pemrograman linear lebih mudah dipahami dan diaplikasikan, pemrograman non-linear memungkinkan model yang lebih kompleks dan realistis. Dengan perkembangan teknologi dan metode optimisasi, kita semakin mampu menyelesaikan masalah-masalah yang dulu sulit diatasi, memberikan kontribusi besar dalam bidang ekonomi, rekayasa, hingga ilmu komputer.
sumber : Bazaraa, M. S., Sherali, H. D., & Shetty, C. M. (2013). Nonlinear Programming: Theory and Algorithms. John Wiley & Sons.
