Optimasi membantu Anda menemukan hasil terbaik yang mendatangkan keuntungan, mengurangi biaya, atau menetapkan parameter yang menyebabkan kegagalan proses bisnis.
Proses ini juga disebut pemrograman matematika. Ini memecahkan masalah penentuan distribusi sumber daya terbatas yang diperlukan untuk mencapai tujuan yang ditetapkan oleh kepala masalah optimasi. Dari semua opsi yang mungkin, diinginkan untuk menemukan opsi yang memaksimalkan (atau mengurangi) parameter pengontrol, misalnya, keuntungan atau biaya. Model optimasi juga disebut preskriptif atau normatif karena model tersebut berusaha menemukan strategi yang layak untuk bisnis.
Riwayat perkembangan
Linear programming (LP) bekerja dengan kelas masalah optimasi di mana semua kendalanya linier.
Mempresentasikan sejarah singkat perkembangan LP:
- Pada tahun 1762, Lagrange memecahkan masalah optimasi sederhana dengan kendala kesetaraan.
- Pada tahun 1820, Gauss memutuskansistem persamaan linear menggunakan eliminasi.
- Pada tahun 1866, Wilhelm Jordan menyempurnakan metode pencarian galat kuadrat terkecil sebagai kriteria yang cocok. Ini sekarang disebut metode Gauss-Jordan.
- Komputer digital muncul pada tahun 1945.
- Danzig menemukan metode simpleks pada tahun 1947.
- Pada tahun 1968, Fiacco dan McCormick memperkenalkan metode Inside Point.
- Pada tahun 1984, Karmarkar menerapkan metode interior untuk menyelesaikan program linier, menambahkan analisis inovatifnya.
LP telah terbukti menjadi alat yang sangat kuat baik untuk pemodelan masalah dunia nyata dan sebagai teori matematika yang diterapkan secara luas. Namun, banyak masalah optimasi yang menarik adalah non-linier.
Apa yang harus dilakukan dalam kasus ini? Studi masalah tersebut melibatkan campuran bervariasi aljabar linier, kalkulus multivariat, analisis numerik, dan metode komputasi. Para ilmuwan sedang mengembangkan algoritma komputasi, termasuk metode titik interior untuk pemrograman linier, geometri, analisis himpunan dan fungsi cembung, dan studi masalah terstruktur khusus seperti pemrograman kuadrat.
Optimasi nonlinier memberikan pemahaman mendasar tentang analisis matematis dan banyak digunakan di berbagai bidang seperti teknik, analisis regresi, manajemen sumber daya, eksplorasi geofisika, dan ekonomi.
Klasifikasi masalah optimasi
Sebuah langkah penting dalamProses optimasi adalah klasifikasi model, karena algoritma solusi mereka disesuaikan dengan tipe tertentu.
1. Masalah dengan optimasi diskrit dan berkelanjutan. Beberapa model masuk akal hanya jika variabel mengambil nilai dari subset bilangan bulat diskrit. Lainnya berisi data yang dapat mengambil nilai nyata apa pun. Mereka biasanya lebih mudah untuk dipecahkan. Peningkatan dalam algoritme, dikombinasikan dengan kemajuan teknologi komputer, telah secara dramatis meningkatkan ukuran dan kompleksitas masalah optimasi pemrograman linier.
2. Optimalisasi tidak terbatas dan terbatas. Perbedaan penting lainnya adalah tugas di mana tidak ada batasan pada variabel. Ini dapat berkisar dari penduga sederhana hingga sistem persamaan dan ketidaksetaraan yang memodelkan hubungan kompleks antara data. Masalah optimasi tersebut dapat diklasifikasikan lebih lanjut sesuai dengan sifat fungsi (linier dan non-linier, cembung dan mulus, terdiferensiasi dan tidak terdiferensiasi).
3. Tugas kelayakan. Tujuannya adalah untuk menemukan nilai variabel yang memenuhi batasan model tanpa tujuan pengoptimalan tertentu.
4. Tugas pelengkap. Mereka banyak digunakan dalam teknologi dan ekonomi. Tujuannya adalah untuk menemukan solusi yang memenuhi kondisi komplementaritas. Dalam praktiknya, tugas dengan beberapa tujuan sering dirumuskan kembali menjadi satu tujuan.
5. Optimasi deterministik versus stokastik. Optimasi deterministik mengasumsikan bahwa data untuktugas benar-benar akurat. Namun, pada banyak masalah topikal mereka tidak dapat diketahui karena beberapa alasan.
Yang pertama berkaitan dengan kesalahan pengukuran sederhana. Alasan kedua lebih mendasar. Itu terletak pada kenyataan bahwa beberapa data mewakili informasi tentang masa depan, misalnya, permintaan akan suatu produk atau harga untuk periode waktu yang akan datang. Saat mengoptimalkan di bawah kondisi optimasi stokastik, ketidakpastian disertakan dalam model.
Komponen Utama
Fungsi tujuan adalah yang akan diminimalkan atau dimaksimalkan. Sebagian besar jenis masalah optimasi memiliki satu fungsi tujuan. Jika tidak, mereka sering dapat diformulasikan kembali untuk bekerja.
Dua pengecualian untuk aturan ini:
1. Targetkan tugas pencarian. Dalam sebagian besar aplikasi bisnis, manajer ingin mencapai tujuan tertentu sambil memenuhi batasan model. Pengguna tidak terlalu ingin mengoptimalkan sesuatu, jadi tidak masuk akal untuk mendefinisikan fungsi tujuan. Tipe ini biasa disebut sebagai masalah satisfiability.
2. Banyak fitur objektif. Seringkali, pengguna ingin mengoptimalkan beberapa tujuan berbeda sekaligus. Mereka biasanya tidak cocok. Variabel yang mengoptimalkan untuk satu tujuan mungkin bukan yang terbaik untuk yang lain.
Jenis komponen:
- Input terkontrol adalah sekumpulan variabel keputusan yang memengaruhi nilai fungsi tujuan. Dalam tugas produksi, variabel dapat mencakup distribusi berbagai sumber daya yang tersedia atau tenaga kerja yang dibutuhkan untuksetiap tindakan.
- Constraints adalah hubungan antara variabel keputusan dan parameter. Untuk masalah produksi, tidak masuk akal untuk menghabiskan banyak waktu pada aktivitas apa pun, jadi batasi semua variabel "sementara".
- Solusi yang mungkin dan optimal. Nilai keputusan untuk variabel, di mana semua kendala terpenuhi, disebut satisfiable. Sebagian besar algoritme pertama kali menemukannya, lalu mencoba memperbaikinya. Akhirnya, mereka mengubah variabel untuk berpindah dari satu solusi yang layak ke solusi yang lain. Proses ini diulang sampai fungsi tujuan mencapai maksimum atau minimum. Hasil ini disebut solusi optimal.
Algoritma masalah optimasi yang dikembangkan untuk program matematika berikut ini banyak digunakan:
- Cembung.
- Dapat dipisahkan.
- Kuadrat.
- Geometris.
Google Linear Solvers
Optimasi atau pemrograman linier adalah nama yang diberikan untuk proses komputasi untuk memecahkan masalah secara optimal. Ini dimodelkan sebagai satu set hubungan linier yang muncul di banyak disiplin ilmu dan teknik.
Google menawarkan tiga cara untuk menyelesaikan masalah pengoptimalan linier:
- Glop perpustakaan sumber terbuka.
- Pengaya Optimasi Linier untuk Google Spreadsheet.
- Layanan Pengoptimalan Linier di Skrip Google Apps.
Glop terintegrasi dengan Googlepemecah linier. Ini tersedia dalam sumber terbuka. Anda dapat mengakses Glop melalui pembungkus pemecah linier OR-Tools, yang merupakan pembungkus untuk Glop.
Modul pengoptimalan linier untuk Google Spreadsheet memungkinkan Anda melakukan pernyataan linier dari masalah pengoptimalan dengan memasukkan data ke dalam spreadsheet.
Pemrograman kuadrat
Platform Premium Solver menggunakan metode Simplex versi LP/Quadratic yang diperluas dengan batas pemrosesan masalah LP dan QP hingga 2000 variabel keputusan.
SQP Solver untuk masalah skala besar menggunakan implementasi modern dari metode himpunan aktif dengan sparseness untuk menyelesaikan masalah pemrograman kuadrat (QP). Mesin XPRESS Solver menggunakan perpanjangan alami dari metode "Titik Interior" atau Newton Barrier untuk memecahkan masalah QP.
MOSEK Solver menerapkan metode "Inside Point" dan auto-dual yang disematkan. Ini sangat efektif untuk masalah QP yang digabungkan secara longgar. Itu juga dapat memecahkan masalah Scale Quadratic Constraint (QCP) dan Second Order Cone Programming (SOCP).
Perhitungan multi-operasi
Mereka cukup berhasil digunakan dengan penggunaan fitur Microsoft Office, misalnya, memecahkan masalah pengoptimalan di Excel.
Pada tabel di atas, simbolnya adalah:
- K1 - K6 - pelanggan yang perlu menyediakan barang.
- S1 - S6 adalah lokasi produksi potensial yang dapat dibangun untuk ini. Bisa dibuat1, 2, 3, 4, 5 atau semua 6 lokasi.
Ada biaya tetap untuk setiap fasilitas yang tercantum pada kolom I (Fix).
Jika lokasi tidak mengubah apa pun, itu tidak akan dihitung. Maka tidak akan ada biaya tetap.
Identifikasi lokasi potensial untuk mendapatkan biaya terendah.
Dalam kondisi ini, lokasi ditetapkan atau tidak. Kedua status ini adalah: "TRUE - FALSE" atau "1 - 0". Ada enam negara bagian untuk enam lokasi, misalnya, 000001 diatur hanya keenam, 111111 diatur ke semua.
Dalam sistem bilangan biner, ada tepat 63 opsi yang berbeda dari 000001 (1) hingga 111111 (63).
L2-L64 sekarang harus membaca {=GANDA OPERASI (K1)}, ini adalah hasil dari semua solusi alternatif. Maka nilai minimumnya adalah=Min (L) dan alternatif yang sesuai adalah INDEX (K).
Pemrograman Integer CPLEX
Terkadang hubungan linier tidak cukup untuk sampai ke inti masalah bisnis. Hal ini terutama benar ketika keputusan melibatkan pilihan diskrit, seperti apakah akan membuka gudang di lokasi tertentu atau tidak. Dalam situasi ini, pemrograman integer harus digunakan.
Jika masalahnya melibatkan pilihan diskrit dan kontinu, ini adalah program integer campuran. Ini dapat memiliki masalah kuadrat linier, cembung dan kendala orde kedua yang sama.
Program bilangan bulat jauh lebih kompleks daripada program linier, tetapi memiliki aplikasi bisnis yang penting. Perangkat lunakPerangkat lunak CPLEX menggunakan metode matematika yang kompleks untuk memecahkan masalah bilangan bulat. Metodenya melibatkan pencarian sistematis untuk kemungkinan kombinasi variabel diskrit menggunakan relaksasi perangkat lunak linier atau kuadrat untuk menghitung batas pada nilai solusi optimal.
Mereka juga menggunakan LP dan metode pemecahan masalah optimasi lainnya untuk menghitung kendala.
Pemecah Microsoft Excel Standar
Teknologi ini menggunakan implementasi dasar dari metode Simplex utama untuk menyelesaikan masalah LP. Hal ini terbatas pada 200 variabel. "Premium Solver" menggunakan metode simpleks primer yang ditingkatkan dengan batas dua sisi untuk variabel. Platform Premium Solver menggunakan versi diperpanjang dari LP/Quadratic Simplex Solver untuk memecahkan masalah optimasi hingga 2000 variabel keputusan.
LP skala besar untuk platform Premium Solver menerapkan penerapan metode simpleks sederhana dan ganda yang canggih, yang menggunakan sparity dalam model LP untuk menghemat waktu dan memori, strategi lanjutan untuk memperbarui dan matriks refactoring, penetapan harga dan rotasi ganda dan parsial, dan untuk mengatasi degenerasi. Engine ini tersedia dalam tiga versi (mampu menangani hingga 8.000, 32.000, atau variabel dan batasan tak terbatas).
MOSEK Solver mencakup simpleks primer dan ganda, metode yang juga memanfaatkan sparity dan menggunakan strategi lanjutan untuk pembaruan matriks dan "refactorization". Ini memecahkan masalah ukuran tidak terbatas, wasdiuji pada masalah pemrograman linier dengan jutaan variabel keputusan.
Contoh langkah demi langkah di EXCEL
Untuk menentukan model masalah optimasi di Excel, lakukan langkah-langkah berikut:
- Mengatur data untuk masalah dalam spreadsheet dalam bentuk logis.
- Pilih sel untuk menyimpan setiap variabel.
- Buat dalam sel rumus untuk menghitung model matematika target dari masalah optimasi.
- Buat rumus untuk menghitung sisi kiri setiap kendala.
- Gunakan dialog di Excel untuk memberi tahu Solver tentang variabel keputusan, target, batasan, dan batasan yang diinginkan pada parameter tersebut.
- Jalankan "Solver" untuk menemukan solusi optimal.
- Buat lembar Excel.
- Mengatur data untuk masalah di Excel di mana rumus untuk fungsi tujuan dan kendala dihitung.
Pada tabel di atas, sel B4, C4, D4, dan E4 telah dicadangkan untuk mewakili variabel keputusan X 1, X 2, X 3, dan X 4. Contoh keputusan:
- Model bauran produk ($450, $1150, $800, dan $400 laba per produk) masing-masing dimasukkan dalam sel B5, C5, D5, dan E5. Hal ini memungkinkan target untuk dihitung dalam F5=B5B4 + C5C4 + D5D4 + E5E4 atau F5:=SUMPRODUCT (B5: E5, B4: E4).
- Dalam B8 masukkan jumlah sumber daya yang dibutuhkan untuk memproduksi setiap jenis produk.
- Rumus untuk F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Salin inirumus di F9. Tanda dolar di $B$4:$E$4 menunjukkan bahwa rentang sel ini tetap konstan.
- Di G8 masukkan jumlah sumber daya yang tersedia untuk setiap jenis, sesuai dengan nilai batasan di sebelah kanan. Ini memungkinkan Anda untuk mengekspresikannya seperti ini: F11<=G8: G11.
- Ini setara dengan empat batas F8<=G8, F9 <=G9, F10 <=G10 dan F11=0
Bidang aplikasi praktis dari metode
Optimasi linier memiliki banyak aplikasi praktis sebagai contoh masalah optimasi:
Sebuah perusahaan dapat membuat beberapa produk dengan margin kontribusi yang diketahui. Produksi satu unit setiap item memerlukan sejumlah sumber daya terbatas yang diketahui. Tugasnya adalah membuat program produksi untuk menentukan berapa banyak setiap produk yang harus diproduksi agar keuntungan perusahaan maksimal tanpa melanggar batasan sumber daya.
Masalah pencampuran adalah solusi untuk masalah optimasi yang terkait dengan menggabungkan bahan ke dalam produk akhir. Contohnya adalah masalah diet yang dipelajari oleh George Danzig pada tahun 1947. Beberapa bahan baku yang diberikan seperti oat, daging babi dan minyak bunga matahari beserta kandungan gizinya seperti protein, lemak, vitamin A, dan harganya per kilogram. Tantangannya adalah memadukan satu atau lebih produk akhir dari bahan mentah dengan biaya serendah mungkin dengan tetap memperhatikan batas minimum dan maksimum nilai gizinya.
Aplikasi klasik dari masalah optimisasi linier adalah menentukan perutean untuk kebutuhanlalu lintas di jaringan telekomunikasi atau transportasi. Pada saat yang sama, arus harus dirutekan melalui jaringan sedemikian rupa sehingga semua persyaratan lalu lintas terpenuhi tanpa melanggar kondisi bandwidth.
Dalam teori matematika, optimasi linier dapat digunakan untuk menghitung strategi optimal dalam permainan zero-sum untuk dua orang. Dalam hal ini, distribusi probabilitas untuk setiap peserta dihitung, yang merupakan koefisien pencampuran acak dari strateginya.
Tidak ada proses bisnis yang sukses di dunia ini yang mungkin terjadi tanpa optimasi. Ada banyak algoritma optimasi yang tersedia. Beberapa metode hanya cocok untuk jenis masalah tertentu. Penting untuk dapat mengenali karakteristik mereka dan memilih metode solusi yang tepat.
