Optimisasi Matematika
Optimasi matematika (atau disebut juga optimasi) atau pemrograman matematika adalah pemilihan elemen terbaik, dengan memperhatikan beberapa kriteria, dari beberapa alternatif yang tersedia. Secara umum, optimasi matematika dibagi menjadi dua subbidang: optimasi diskrit dan optimasi kontinu. Masalah optimasi muncul di semua disiplin ilmu kuantitatif mulai dari ilmu komputer dan teknik hingga riset operasi dan ekonomi, dan pengembangan metode solusi telah menjadi perhatian matematika selama berabad-abad.
Dalam pendekatan yang lebih umum, masalah optimasi terdiri dari memaksimalkan atau meminimalkan fungsi nyata dengan secara sistematis memilih nilai input dari dalam himpunan yang diizinkan dan menghitung nilai fungsi tersebut. Generalisasi teori dan teknik optimasi ke formulasi lain merupakan area yang luas dalam matematika terapan.
Sejarah
Fermat dan Lagrange menemukan formula berbasis kalkulus untuk mengidentifikasi titik optimum, sementara Newton dan Gauss mengusulkan metode iteratif untuk menuju titik optimum.
Istilah "pemrograman linier" untuk kasus optimasi tertentu adalah berkat George B. Dantzig, meskipun sebagian besar teorinya telah diperkenalkan oleh Leonid Kantorovich pada tahun 1939. (Pemrograman dalam konteks ini tidak mengacu pada pemrograman komputer, tetapi berasal dari penggunaan program oleh militer Amerika Serikat untuk merujuk pada jadwal pelatihan dan logistik yang diusulkan, yang merupakan masalah yang dipelajari Dantzig pada saat itu). Dantzig mempublikasikan algoritma Simplex pada tahun 1947, dan juga John von Neumann dan peneliti lainnya bekerja pada aspek teoritis pemrograman linier (seperti teori dualitas) pada waktu yang sama.
Peneliti penting lainnya dalam optimasi matematika termasuk yang berikut ini:
- Richard Bellman
- Dimitri Bertsekas
- Michel Bierlaire
- Stephen P. Boyd
- Roger Fletcher
- Martin Grötschel
- Ronald A. Howard
- Fritz John
- Narendra Karmarkar
- William Karush
- Leonid Khachiyan
- Bernard Koopman
- Harold Kuhn
- László Lovász
- David Luenberger
- Arkady Nemirovsky
- Yurii Nesterov
- Lev Pontryagin
- R. Tyrrell Rockafellar
- Naum Z. Shor
- Albert Tucker
Subbidang utama
- Pemrograman cembung mempelajari kasus ketika fungsi objektifnya cembung (minimisasi) atau cekung (maksimisasi) dan set batasannya cembung. Hal ini dapat dilihat sebagai kasus khusus pemrograman nonlinier atau sebagai generalisasi pemrograman kuadratik linier atau cembung.
- Pemrograman linier (LP), sebuah jenis pemrograman cembung, mempelajari kasus di mana fungsi objektif f adalah linier dan batasannya ditentukan hanya dengan menggunakan persamaan dan pertidaksamaan linier. Himpunan kendala seperti itu disebut polihedron atau polytope jika dibatasi.
- Pemrograman kerucut orde dua (SOCP) adalah sebuah program cembung, dan mencakup beberapa jenis program kuadratik.
- Pemrograman semidefinit (SDP) adalah subbidang optimasi cembung di mana variabel-variabel yang mendasarinya adalah matriks semidefinit. Ini adalah generalisasi dari pemrograman kuadratik linier dan cembung.
- Pemrograman kerucut adalah bentuk umum dari pemrograman cembung. LP, SOCP, dan SDP semuanya dapat dilihat sebagai program kerucut dengan jenis kerucut yang sesuai.
- Pemrograman geometris adalah teknik di mana kendala objektif dan ketidaksetaraan yang dinyatakan sebagai posynomial dan kendala kesetaraan sebagai monomial dapat ditransformasikan ke dalam program cembung.
- Pemrograman bilangan bulat mempelajari program linier di mana beberapa atau semua variabel dibatasi untuk mengambil nilai bilangan bulat. Ini tidak cembung, dan secara umum jauh lebih sulit daripada pemrograman linier biasa.
- Pemrograman kuadratik memungkinkan fungsi objektif memiliki suku kuadratik, sementara himpunan layak harus ditentukan dengan persamaan dan ketidaksetaraan linier. Untuk bentuk tertentu dari suku kuadrat, ini adalah jenis pemrograman cembung.
- Pemrograman pecahan mempelajari optimasi rasio dari dua fungsi nonlinier. Kelas khusus program pecahan cekung dapat ditransformasikan menjadi masalah optimasi cembung.
- Pemrograman nonlinier mempelajari kasus umum di mana fungsi tujuan atau kendala atau keduanya mengandung bagian nonlinier. Ini mungkin atau mungkin bukan program cembung. Secara umum, apakah program tersebut cembung atau tidak, akan mempengaruhi tingkat kesulitan dalam menyelesaikannya.
- Pemrograman stokastik mempelajari kasus di mana beberapa kendala atau parameter bergantung pada variabel acak.
- Optimasi robust, seperti halnya pemrograman stokastik, merupakan upaya untuk menangkap ketidakpastian dalam data yang mendasari masalah optimasi. Optimasi kuat bertujuan untuk menemukan solusi yang valid di bawah semua kemungkinan realisasi ketidakpastian yang didefinisikan oleh himpunan ketidakpastian.
- Optimasi kombinatorial berkaitan dengan masalah-masalah di mana himpunan solusi yang layak adalah diskrit atau dapat direduksi menjadi diskrit.
- Optimasi stokastik digunakan dengan pengukuran fungsi acak (noisy) atau input acak dalam proses pencarian.
- Optimasi dimensi tak terbatas mempelajari kasus ketika himpunan solusi yang layak adalah subset dari ruang dimensi tak terbatas, seperti ruang fungsi.
- Heuristik dan metaheuristik membuat sedikit atau tidak ada asumsi tentang masalah yang dioptimalkan. Biasanya, heuristik tidak menjamin bahwa solusi optimal akan ditemukan. Di sisi lain, heuristik digunakan untuk menemukan solusi perkiraan untuk banyak masalah optimasi yang rumit.
- Pemenuhan batasan mempelajari kasus di mana fungsi objektif f adalah konstan (ini digunakan dalam kecerdasan buatan, terutama dalam penalaran otomatis).
- Pemrograman kendala adalah paradigma pemrograman di mana hubungan antar variabel dinyatakan dalam bentuk kendala.
- Pemrograman disjungtif digunakan di mana setidaknya satu kendala harus dipenuhi, tetapi tidak semua. Hal ini sangat berguna dalam penjadwalan.
- Pemetaan ruang adalah sebuah konsep untuk pemodelan dan optimasi sistem rekayasa untuk akurasi model dengan ketelitian tinggi (halus) yang mengeksploitasi model kasar atau model pengganti yang bermakna secara fisik yang sesuai.
Dalam sejumlah subbidang, teknik-teknik ini dirancang terutama untuk optimasi dalam konteks dinamis (yaitu, pengambilan keputusan dari waktu ke waktu):
- Kalkulus variasi Merupakan cabang dari optimasi dimensi tak terbatas yang berkaitan dengan menemukan cara terbaik untuk mencapai suatu tujuan, seperti menemukan permukaan yang batasnya adalah kurva tertentu, tetapi dengan luas area yang paling kecil.
- Teori kontrol optimal adalah generalisasi dari kalkulus variasi yang memperkenalkan kebijakan kontrol.
- Pemrograman dinamis adalah pendekatan untuk menyelesaikan masalah optimasi stokastik dengan parameter model yang bersifat stokastik, acak, dan tidak diketahui. Pendekatan ini mempelajari kasus di mana strategi optimasi didasarkan pada pemecahan masalah menjadi submasalah yang lebih kecil. Persamaan yang menggambarkan hubungan antara submasalah ini disebut persamaan Bellman.
- Pemrograman matematika dengan kendala keseimbangan adalah di mana kendala mencakup ketidaksetaraan variasi atau komplementaritas.
Optimalisasi multi-objektif
Menambahkan lebih dari satu tujuan pada masalah optimasi akan menambah kompleksitas. Sebagai contoh, untuk mengoptimalkan desain struktural, kita menginginkan desain yang ringan dan kaku. Ketika dua tujuan bertentangan, sebuah trade-off harus dibuat. Mungkin ada satu desain yang paling ringan, satu desain yang paling kaku, dan sejumlah desain yang tak terbatas yang merupakan kompromi antara berat dan kekakuan. Himpunan desain trade-off yang meningkatkan satu kriteria dengan mengorbankan kriteria lainnya dikenal sebagai himpunan Pareto. Kurva yang dibuat dengan memplotkan berat terhadap kekakuan dari desain terbaik dikenal sebagai batas Pareto.
Sebuah desain dinilai sebagai "Pareto optimal" (setara dengan "Pareto efisien" atau dalam himpunan Pareto) jika tidak didominasi oleh desain lainnya: Jika desain tersebut lebih buruk daripada desain lain dalam beberapa hal dan tidak lebih baik dalam hal apa pun, maka desain tersebut didominasi dan tidak optimal secara Pareto.
Pilihan di antara solusi "optimal Pareto" untuk menentukan "solusi favorit" didelegasikan kepada pengambil keputusan. Dengan kata lain, mendefinisikan masalah sebagai optimasi multi-objektif menandakan bahwa ada beberapa informasi yang hilang: tujuan yang diinginkan diberikan tetapi kombinasinya tidak dinilai secara relatif satu sama lain. Dalam beberapa kasus, informasi yang hilang dapat diperoleh melalui sesi interaktif dengan pengambil keputusan.
Masalah optimasi multi-objektif telah digeneralisasi lebih lanjut menjadi masalah optimasi vektor di mana urutan (parsial) tidak lagi diberikan oleh urutan Pareto.
Pengoptimalan multi-moda atau global
Masalah optimasi sering kali bersifat multi-modal; artinya, masalah tersebut memiliki beberapa solusi yang baik. Solusi-solusi tersebut dapat berupa solusi yang baik secara global (nilai fungsi biaya yang sama) atau bisa juga berupa solusi yang baik secara global dan solusi yang baik secara lokal. Mendapatkan semua (atau setidaknya beberapa) dari beberapa solusi adalah tujuan dari pengoptimal multi-modal.
Teknik optimasi klasik karena pendekatannya yang berulang-ulang tidak memberikan hasil yang memuaskan ketika digunakan untuk mendapatkan banyak solusi, karena tidak ada jaminan bahwa solusi yang berbeda akan diperoleh bahkan dengan titik awal yang berbeda dalam beberapa kali menjalankan algoritma.Pendekatan umum untuk masalah optimasi global, di mana beberapa ekstrema lokal mungkin ada termasuk algoritme evolusioner, optimasi Bayesian, dan simulated annealing.
Disadur dari : en.wikipedia.org