Apa itu Masalah Optimisasi

Masalah optimisasi dalam matematika berkaitan dengan menemukan solusi terbaik dari sejumlah alternatif yang layak. Istilah "terbaik" atau "optimal" merujuk pada solusi yang memaksimalkan atau meminimalkan suatu fungsi tertentu, sering disebut sebagai "fungsi tujuan". Masalah optimisasi tersebar luas di berbagai bidang, termasuk penelitian operasi, ilmu komputer, pembelajaran mesin, ekonomi, dan rekayasa.

Fungsi Tujuan

Pada intinya, setiap masalah optimisasi memiliki fungsi tujuan. Fungsi ini mewakili jumlah yang perlu diminimalkan atau dimaksimalkan. Dalam bentuk umum, masalah optimisasi dapat didefinisikan sebagai berikut:

Jika kita mencari untuk memaksimalkan fungsi, masalah didefinisikan sebagai:

\max f(x)

Jika kita mencari untuk meminimalkan fungsi, masalah didefinisikan sebagai:

\min f(x)

Dalam kedua kasus ini, f(x) mewakili fungsi tujuan, dan x adalah variabel keputusan atau variabel yang dapat kita kendalikan atau ubah.

Batasan

Batasan adalah pembatas atau kondisi yang harus dipenuhi oleh solusi. Ini bisa berupa kesetaraan atau ketidaksamaan yang melibatkan variabel keputusan. Kumpulan semua titik x yang memenuhi batasan ini disebut sebagai himpunan layak. Kita menunjukkan himpunan layak dengan S. Oleh karena itu, bentuk umum dari masalah optimisasi adalah:

Jika kita mencari untuk memaksimalkan fungsi:

\max f(x) \text{ subject to } x \in S

Jika kita mencari untuk meminimalkan fungsi:

\min f(x) \text{ subject to } x \in S

Dalam persamaan-persamaan ini, batasan mendefinisikan himpunan S. Batasan bisa direpresentasikan dalam bentuk kesetaraan dan ketidaksamaan sebagai berikut:

\begin{align*} g_i(x) & \leq 0, i = 1,...,m \\ h_j(x) & = 0, j = 1,...,p \end{align*}

Dalam persamaan-persamaan ini, g_i(x) mewakili batasan ketidaksamaan dan h_j(x) mewakili batasan kesetaraan. Angka m dan p mewakili jumlah batasan ketidaksamaan dan kesetaraan secara berturut-turut.

Nilai Optimal dan Solusi Optimal

Nilai optimal dari masalah optimisasi merujuk pada nilai terbaik yang mungkin dari fungsi tujuan yang diberikan batasan. Jika masalah adalah masalah minimisasi, nilai optimal adalah nilai terendah yang mungkin dari fungsi tujuan di atas himpunan layak. Jika itu adalah masalah maksimisasi, itu adalah nilai tertinggi yang mungkin.

Solusi optimal, biasanya biasanya dilambangkan dengan x^*, adalah nilai khusus (atau nilai-nilai) dari variabel keputusan x yang menghasilkan nilai optimal dari fungsi tujuan. Dalam istilah matematika:

Jika kita mencari untuk memaksimalkan fungsi, solusi optimal didefinisikan sebagai:

x^* = \arg\max_{x \in S} f(x)

Jika kita mencari untuk meminimalkan fungsi, solusi optimal didefinisikan sebagai:

x^* = \arg\min_{x \in S} f(x)

Dalam persamaan-persamaan ini, x^* mewakili variabel keputusan yang menghasilkan nilai optimal dari fungsi tujuan. Perlu diperhatikan bahwa dalam masalah optimisasi, mungkin ada lebih dari satu solusi optimal, yaitu lebih dari satu x^* yang menghasilkan nilai optimal f(x).

Jenis-Jenis Umum Masalah Optimisasi

Dalam praktiknya, masalah optimisasi memiliki berbagai bentuk, tergantung pada sifat fungsi tujuan dan batasan, serta jenis nilai yang dapat diambil oleh variabel keputusan.

Optimisasi Kontinu

Masalah optimisasi kontinu melibatkan variabel keputusan yang dapat mengambil nilai dalam rentang kontinu tertentu. Masalah seperti ini umum terjadi dalam berbagai bidang seperti pembelajaran mesin, penjadwalan, alokasi resource, di mana variabel dapat mengambil rentang nilai yang kontinu.

Ada beberapa jenis masalah optimisasi kontinu, masing-masing ditandai oleh sifat fungsi tujuan dan batasan. Misalnya, jika fungsi tujuan dan batasan keduanya linear, maka masalah tersebut adalah masalah pemrograman linear. Namun, jika fungsi tujuan dan/atau batasan bersifat non-linear, maka masalah tersebut adalah masalah pemrograman non-linear.

Pemrograman Linear

Pemrograman Linear (LP) adalah jenis dasar dari masalah optimisasi kontinu di mana baik fungsi tujuan maupun batasan bersifat linear. Dalam masalah pemrograman linear, setiap variabel dalam fungsi tujuan dan batasan muncul dengan derajat satu dan tidak dikalikan dengan variabel lainnya. Masalah LP umum terjadi dalam bidang-bidang seperti penelitian operasi, logistik, manajemen rantai pasokan, dan lainnya, karena kesederhanaan relatifnya dan adanya algoritma solusi yang efisien.

Pemrograman Non-linear

Masalah Pemrograman Non-linear (NLP) adalah masalah optimisasi di mana fungsi tujuan, batasan, atau keduanya bersifat non-linear. Pemrograman non-linear memungkkinkan penggandaan rentang masalah dunia nyata yang dapat dimodelkan dibandingkan dengan pemrograman linear. Namun, non-linearitas juga memperkenalkan kompleksitas tambahan ke dalam masalah tersebut.

Pemrograman Kuadratik

Pemrograman Kuadratik adalah jenis khusus dari pemrograman non-linear di mana fungsi tujuan bersifat kuadratik, sedangkan batasannya bersifat linear. Pemrograman kuadratik umum digunakan dalam pembelajaran mesin dan statistik untuk masalah seperti support vector machines dan optimisasi portofolio.

Quadratically Constrained Programming (QCP)

Quadratically Constrained Programming (QCP) adalah bentuk yang lebih kompleks dari pemrograman kuadratik di mana batasannya juga dapat bersifat kuadratik. Masalah QCP dapat memodelkan berbagai skenario lebih banyak daripada pemrograman kuadratik sederhana, namun juga lebih sulit untuk diselesaikan.

Second-Order Cone Programming

Second-Order Cone Programming (SOCP) adalah jenis masalah optimisasi konveks yang meluaskan pemrograman linear dan kuadratik. SOCP dapat menangani berbagai masalah yang lebih luas dibandingkan LP dan QP sambil tetap menjaga keluwesan dan efisiensi optimisasi.

Semi-Definite Programming

Semi-Definite Programming (SDP) adalah jenis optimisasi konveks di mana variabel keputusan adalah matriks, dan batasan mengharuskan matriks ini semi-definit. SDP menemukan aplikasi dalam teori kontrol, pemrosesan sinyal, dan teori informasi kuantum, di antara bidang-bidang lainnya.

Pemrograman Konveks

Pemrograman Konveks adalah subclass dari pemrograman non-linear di mana fungsi tujuan bersifat konveks, dan batasan membentuk himpunan konveks. Masalah pemrograman konveks memiliki sifat bahwa minimum lokal juga merupakan minimum global, yang membuatnya sangat layak di antara masalah pemrograman non-linear.

Optimisasi Diskret

Optimisasi Diskret melibatkan masalah di mana variabel keputusan hanya dapat mengambil nilai-nilai diskrit. Masalah semacam ini sering muncul dalam bidang seperti ilmu komputer, logistik, penelitian operasi, dan transportasi, di mana keputusan sering melibatkan pilihan di antara himpunan alternatif yang terbatas atau terhitung tak terhingga.

Integer Programming

Masalah Integer Programming (IP) melibatkan variabel keputusan yang hanya dapat mengambil nilai bilangan bulat. Masalah ini muncul dalam skenario di mana nilai pecahan tidak masuk akal, seperti ketika menentukan jumlah unit yang akan diproduksi atau jumlah truk yang diperlukan untuk pengiriman.

Mixed-Integer Programming

Dalam masalah Mixed-Integer Programming (MIP), beberapa variabel keputusan harus memiliki nilai bilangan bulat, sementara yang lain dapat berupa nilai kontinu. Masalah ini umum terjadi dalam bidang seperti perencanaan produksi dan logistik, di mana keputusan dapat melibatkan kombinasi pilihan diskret dan kuantitas kontinu.

Optimisasi Kombinatorial

Masalah Optimisasi Kombinatorial melibatkan pencarian objek terbaik dari himpunan objek yang terbatas. Dalam masalah ini, variabel keputusan sering mewakili apakah suatu objek tertentu harus atau tidak harus disertakan dalam solusi, yang menghasilkan jumlah potensial solusi yang kombinatorial. Contoh masalah optimisasi kombinatorial termasuk traveling salesman problem dan masalah knapsack (pemilihan objek untuk mengisi ransel dengan bobot tertentu).

Optimisasi Global

Masalah Optimisasi Global melibatkan pencarian solusi optimal mutlak di antara semua solusi yang mungkin, daripada hanya mencari optimum lokal yang tidak dapat ditingkatkan hanya dengan mempertimbangkan solusi tetangga. Masalah semacam ini dapat sangat sulit untuk dipecahkan, terutama ketika ruang pencarian besar atau fungsi tujuan memiliki banyak optimum lokal. Teknik optimisasi global sering menggunakan strategi untuk melampaui optimum lokal dalam mencari optimum global.

Optimisasi Stokastik

Optimisasi Stokastik adalah kerangka kerja untuk memodelkan masalah optimisasi yang melibatkan ketidakpastian. Sementara optimisasi tradisional berurusan dengan menemukan keputusan terbaik dengan mempertimbangkan sekumpulan masukan dan batasan tertentu, optimisasi stokastik memperkenalkan variabel acak ke dalam model untuk mewakili ketidakpastian. Masalah optimisasi yang dihasilkan bertujuan untuk menemukan keputusan terbaik dengan mempertimbangkan distribusi probabilitas dari parameter yang tidak pasti.

Dalam kesimpulannya, masalah optimisasi memiliki beragam bentuk dan jenis, tergantung pada sifat fungsi tujuan, batasan, dan nilai yang dapat diambil oleh variabel keputusan. Pemahaman yang baik tentang jenis-jenis umum masalah optimisasi ini dapat membantu dalam memodelkan, merancang, dan menyelesaikan masalah optimisasi dalam berbagai bidang.