Operation Research and Analysis

Apa itu Model Matematika

Dipublikasikan oleh Dias Perdana Putra pada 12 Februari 2024


Pengertian Model Matematika

Model matematika adalah deskripsi abstrak dari sistem konkret dengan menggunakan konsep dan bahasa matematika. Proses pengembangan model matematika disebut pemodelan matematika. Model matematika digunakan dalam matematika terapan dan ilmu alam (misalnya fisika, biologi, ilmu bumi, kimia) dan disiplin ilmu teknik (misalnya ilmu komputer, teknik elektro), serta dalam sistem non-fisik seperti ilmu sosial. (seperti ekonomi, psikologi, sosiologi, ilmu politik). Matematika juga dapat diajarkan sebagai mata pelajaran mandiri .Penggunaan model matematika untuk memecahkan masalah dalam operasi komersial atau militer merupakan bagian besar dari bidang riset operasi.Model matematika juga digunakan dalam musik, linguistik dan filsafat (misalnya secara intensif dalam filsafat analitis). Sebuah model dapat membantu menjelaskan suatu sistem, menguji pengaruh berbagai komponen, dan membuat prediksi tentang perilaku.

Klasifikasi

Pemodelan matematika dapat dibagi menjadi beberapa kategori seperti: B. linier vs. nonlinier, statis vs. dinamis, eksplisit vs. implisit, diskrit vs. kontinu, deterministik vs.probabilistik (stokastik), deduktif, induktif atau geser dan strategis vs. non-strategis.Pertama, perbedaan antara model linier dan nonlinier bergantung pada jenis operator dalam model matematika. Model linier memiliki operator linier sedangkan model nonlinier memiliki operator nonlinier. Misalnya, dalam model statistik linier, hubungan parameter dianggap linier meskipun mungkin nonlinier dalam variabel prediktor.Hal yang sama berlaku untuk persamaan diferensial linier, yang masih dapat memiliki ekspresi nonlinier.Perbedaan model statis dan dinamis terletak pada perhitungan waktu. Model dinamis merepresentasikan perubahan keadaan sistem dari waktu ke waktu, sedangkan model statis mengasumsikan bahwa sistem berada dalam keadaan setimbang dan tidak berubah seiring waktu.Lebih jauh lagi, perbedaan antara eksplisit dan implisit bergantung pada pengetahuan tentang parameter masukan. Suatu model dikatakan eksplisit jika seluruh parameter masukan diketahui dan keluarannya dapat dihitung dengan jumlah perhitungan yang terbatas.Sebaliknya, suatu model dikatakan implisit ketika parameter keluaran diketahui dan masukan yang bersangkutan harus diselesaikan melalui prosedur berulang.Pemodelan dapat bersifat diskrit atau kontinu, bergantung pada apakah objek direpresentasikan secara diskrit sebagai partikel dalam model molekul atau secara kontinu sebagai medan kecepatan fluida dalam pipa.Dalam model deterministik, setiap kombinasi nilai variabel ditentukan secara unik oleh parameter dan keadaan sebelumnya, sedangkan model stokastik menyertakan unsur keacakan dan variabel dijelaskan bukan oleh nilai unik tetapi oleh distribusi probabilitas.Pemodelan deduktif didasarkan pada struktur logis dan berbasis teori, sedangkan pemodelan induktif didasarkan pada temuan empiris dan generalisasinya. Pemodelan mengambang tidak bergantung pada teori atau observasi dan hanya merupakan penerapan struktur yang diharapkan.Terakhir, model strategis dalam teori permainan berbeda karena model tersebut memodelkan agen dengan insentif yang tidak sesuai, seperti spesies yang bersaing atau penawar dalam lelang. Model strategis mengasumsikan bahwa para pemain adalah pengambil keputusan otonom yang secara rasional memilih tindakan yang memaksimalkan fungsi tujuan mereka. Tantangan utama ketika menggunakan model strategis adalah definisi dan kuantifikasi konsep solusi seperti ekuilibrium Nash. Model strategis mempunyai sifat menarik dalam memisahkan pemikiran tentang aturan main dari pemikiran tentang perilaku para pemain.

Konstruksi

Dalam bisnis dan teknik, model matematika dapat digunakan untuk memaksimalkan hasil tertentu. Sistem yang sedang dipertimbangkan memerlukan masukan tertentu. Hubungan antara input dan output sistem juga bergantung pada variabel lain: variabel keputusan, variabel keadaan, variabel eksogen dan variabel acak.Variabel keputusan terkadang disebut variabel independen. Variabel eksogen terkadang disebut parameter atau konstanta.Variabel-variabel tersebut tidak independen satu sama lain karena variabel keadaan bergantung pada keputusan, input, variabel acak dan eksogen. Selain itu, variabel keluaran bergantung pada keadaan sistem (diwakili oleh variabel keadaan).Tujuan dan batasan suatu sistem dan penggunanya dapat direpresentasikan sebagai fungsi variabel keluaran atau variabel keadaan. Fungsi tujuan bergantung pada perspektif pengguna model. Tergantung pada konteksnya, fungsi tujuan juga disebut sebagai indeks kinerja karena merupakan salah satu ukuran yang menarik bagi pengguna.Meskipun tidak ada batasan jumlah fungsi tujuan dan batasan yang dapat dimiliki suatu model, penggunaan atau pengoptimalan model menjadi lebih kompleks (secara komputasi) seiring dengan bertambahnya jumlah fungsi tujuan.Misalnya, para ekonom sering menggunakan aljabar linier ketika menggunakan model input-output. Model matematika kompleks dengan banyak variabel dapat dikonsolidasikan menggunakan vektor, dimana satu simbol mewakili beberapa variabel.

Informasi apriori

Masalah pemodelan matematika sering diklasifikasikan ke dalam model kotak hitam atau model kotak putih, bergantung pada seberapa banyak informasi apriori tentang sistem yang tersedia. Model kotak hitam adalah sistem yang tidak tersedia informasi apriori. Model kotak putih (juga disebut kotak kaca atau kotak transparan) adalah sistem yang berisi semua informasi yang diperlukan. Dalam praktiknya, semua sistem berada di antara model kotak hitam dan kotak putih, sehingga konsep ini hanya berguna sebagai panduan intuitif saat memutuskan pendekatan mana yang akan diambil.Secara umum, yang terbaik adalah menggunakan informasi apriori sebanyak mungkin untuk membuat model lebih akurat.Oleh karena itu, model kotak putih umumnya dianggap lebih sederhana karena model berperilaku benar bila informasi digunakan dengan benar. Informasi apriori sering kali datang dalam bentuk pengetahuan tentang jenis fungsi yang menghubungkan variabel berbeda. Misalnya, ketika kita memodelkan cara kerja suatu obat dalam sistem tubuh manusia, kita mengetahui bahwa jumlah obat dalam darah biasanya mengalami penurunan fungsi secara eksponensial. Namun masih adaparameter yang belum diketahui; Seberapa cepat jumlah obat berkurang dan berapa jumlah awal obat di dalam darah? Oleh karena itu, contoh ini bukanlah model kotak putih murni.Parameter-parameter ini harus diestimasi dengan cara tertentu sebelum model dapat digunakan.Dalam model kotak hitam kami mencoba memperkirakan bentuk fungsional dari hubungan antara variabel dan parameter numerik dalam fungsi-fungsi ini. Misalnya, dengan menggunakan informasi apriori, kita dapat memperoleh serangkaian fungsi yang dapat mendeskripsikan sistem secara memadai. Jika tidak ada informasi apriori, kami mencoba menggunakan fungsi seumum mungkin untuk mencakup semua model yang berbeda. Pendekatan yang umum digunakan untuk model kotak hitam adalahjaringan saraf tiruan, yang biasanya tidak membuat asumsi tentang data masukan.Alternatifnya, algoritma NARMAX (model rata-rata bergerak autoregresif nonlinier dengan masukan eksogen), dikembangkan sebagai bagian dari identifikasi sistem nonlinier, dapat digunakan untuk memilih istilah model, menentukan struktur model, dan memperkirakan parameter yang tidak diketahui dengan adanya gangguan nonlinier. linier dan berkorelasi. Keuntungan model NARMAX dibandingkan jaringan saraf adalah NARMAX menghasilkan model yang dapat ditulis dan dihubungkan ke prosesyang mendasarinya, sedangkan jaringan saraf menghasilkan perkiraan buram.

 

Disadur dari : https://en.wikipedia.org/wiki/Mathematical_model

Selengkapnya
Apa itu Model Matematika

Operation Research and Analysis

Pengenalan Dynamic Programming dan Penerapannya

Dipublikasikan oleh Dias Perdana Putra pada 12 Februari 2024


Pengenalan Dynamic Programming
Pemrograman dinamis adalah metode optimasi matematis dan paradigma algoritmik. Metode ini dikembangkan oleh Richard Bellman pada tahun 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik dirgantara hingga ekonomi. Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang kompleks dengan memecahnya secara rekursif menjadi sub-masalah yang lebih sederhana. Meskipun beberapa masalah pengambilan keputusan tidak dapat diurai dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali diurai secara rekursif. Hal yang sama berlaku dalam ilmu komputer: Jika suatu masalah dapat diselesaikan secara optimal dengan membaginya menjadi sub-masalah dan kemudian secara rekursif mencari solusi optimal untuk sub-masalah tersebut, maka ini disebut substruktur optimal.Jika submasalah dapat disarangkan secara rekursif dalam masalah yang lebih besar sehingga metode pemrograman dinamis dapat diterapkan, maka terdapat hubungan antara nilai masalah yang lebih besar dan nilai submasalah tersebut. Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.

Persamaan Matematis

Dalam optimasi matematis, pemrograman dinamis mengacu pada penyederhanaan keputusan dengan memecahnya menjadi serangkaian langkah keputusan dari waktu ke waktu. Proses ini melibatkan pendefinisian barisan fungsi nilai V1, V2, ..., Vn, yang mewakili keadaan sistem pada waktu i dari 1 sampai n, dimana Vn(y) adalah nilai dalam keadaan y pada saat terakhir. Utara.Nilai Vi pada waktu sebelumnya dapat dicari mundur dengan menggunakan persamaan Bellman. Untuk i = 2, ..., n, Vi-1 pada setiap state dihitung dari Vi dengan memaksimumkan fungsi keuntungan dari keputusan pada waktu i-1 dan fungsi Vi pada state baru pada saat pengambilan keputusan tersebut.Proses ini menghasilkan Vi-1 untuk status yang diperlukan. Pada keadaan awal sistem, V1 merupakan nilai solusi optimal. Nilai optimal dari variabel keputusan dapat dikembalikan secara individual setelah perhitungan dilakukan.

Computer Science

Ada dua atribut utama yang harus dimiliki suatu masalah agar pemrograman dinamis dapat diterapkan: substruktur optimal dan submasalah yang tumpang tindih. Ketika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah yang tidak tumpang tindih, strategi ini disebut “membagi dan menaklukkan.”Oleh karena itu, pengurutan gabungan dan pengurutan cepat tidak diklasifikasikan sebagai masalah pemrograman dinamis.

Substruktur optimal berarti bahwa solusi terhadap masalah optimasi tertentu dapat diperoleh dengan kombinasi solusi optimal dari submasalahnya. Substruktur optimal biasanya dijelaskan dengan rekursi.Misalnya, pada graf G = (V, E), jalur terpendek p dari simpul u ke simpul v mewakili substruktur optimal: ambil setiap simpul perantara w pada lintasan terpendek p. Jika p memang merupakan jalur terpendek, jalur tersebut dapat dibagi menjadi subjalur p1 dari u ke w dan p2 dari w ke v, sehingga jalur ini adalah yang terpendek di antara simpul-simpul yang bersesuaian (menggunakan metode potong-dan-tempel yang dijelaskan pada
argumen). Pengantar algoritma). Oleh karena itu, solusi dapat dengan mudah dirumuskan untuk mencari jalur terpendek secara rekursif, seperti halnya dengan algoritma Bellman-Ford atau algoritma Floyd-Warshall.

Tumpang tindih submasalah berarti ruang submasalah harus kecil, yaitu. H. algoritma rekursif apa pun yang menyelesaikan masalah harus menyelesaikan submasalah yang sama berulang kali, bukan membuat submasalah baru. Misalnya, perhatikan rumus rekursif untuk menghasilkan deret Fibonacci: Fi = Fi-1 + Fi-2, dengan kasus dasar F1 = F2 = 1. Maka F43 = F42 + F41 dan F42 = F41 + F40. Sekarang F41 diisi menjadi subpohon rekursif dari F43 dan juga F42. Meskipun jumlah totalsubmasalah sangat kecil (hanya 43), jika kita menggunakan solusi rekursif naif seperti ini, kita akan menyelesaikan masalah yang sama berulang kali.Pemrograman dinamis memperhitungkan fakta ini dan menyelesaikan setiap sub-masalah hanya satu kali.

Hal ini dapat dicapai dengan salah satu dari dua cara:

  • Top down approach: Ini adalah akibat langsung dari perumusan masalah secara rekursif. Jika solusi suatu masalah dapat dirumuskan secara rekursif menggunakan solusi dari submasalahnya dan submasalah tersebut tumpang tindih, kita dapat dengan mudah mencatat atau menyimpan solusi dari submasalah tersebut dalam sebuah tabel. Setiap kali kita mencoba memecahkan submasalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah submasalah tersebut sudah terpecahkan. Jikasolusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak, kita selesaikan submasalah dan tambahkan solusinya ke tabel.

  • Bottom up approach: Setelah kita merumuskan solusi suatu masalah secara rekursif dalam bentuk submasalah, kita dapat mencoba merumuskan kembali masalah dari bawah ke atas: pertama-tama kita mencoba menyelesaikan submasalah terkecil dan membangun solusi berdasarkan solusinya. Sub-masalahnya adalah yang terbesar. Hal ini juga biasanya dilakukan dalam bentuk tabel, dengan menghasilkan solusi secara berulang untuk submasalah yang semakin besar menggunakan solusi
    untuk submasalah yang lebih kecil. Misalnya kita sudah mengetahui nilai F41 dan F40, kita bisa langsung menghitung nilai F42.

Beberapa bahasa pemrograman dapat secara otomatis menyimpan hasil pemanggilan fungsi dengan serangkaian argumen tertentu untuk mempercepat evaluasi panggilan berdasarkan nama (mekanisme ini disebut panggilan demi permintaan). Beberapa bahasa mengizinkan hal ini secara portabel (misalnya Skema, Common Lisp, Perl, atau D). Beberapa bahasa memiliki hafalan otomatis, seperti: B. Prolog dan J Tabled, yang mendukung hafalan dengan kata keterangan M. Namun, ini hanya mungkin untuk fungsi yang transparan secara referensial. Penghafalan juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan ulang seperti Bahasa Wolfram.

Contoh Algoritma :

  • Algoritma Dijkstra untuk masalah jalur terpendek
  • Deret Fibonacci

Disadur dari : https://en.wikipedia.org/wiki/Dynamic_programming

Selengkapnya
Pengenalan Dynamic Programming dan Penerapannya

Operation Research and Analysis

Pencarian Lokal Berulang

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022


Pencarian Lokal Berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi pencarian lokal atau metode mendaki bukit untuk memecahkan masalah optimasi diskrit.

Metode pencarian lokal bisa macet di minimum lokal, di mana tidak ada tetangga yang lebih baik yang tersedia.

Modifikasi sederhana terdiri dari panggilan iterasi ke rutin pencarian lokal, setiap kali dimulai dari konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang, dan menyiratkan bahwa pengetahuan yang diperoleh selama fase pencarian lokal sebelumnya tidak digunakan. Pembelajaran menyiratkan bahwa sejarah sebelumnya, misalnya memori tentang minima lokal yang ditemukan sebelumnya, ditambang untuk menghasilkan titik awal yang lebih baik dan lebih baik untuk pencarian lokal.

Asumsi implisitnya adalah distribusi berkerumun dari minima lokal: ketika meminimumkan suatu fungsi, menentukan minima lokal yang baik lebih mudah ketika memulai dari minimum lokal dengan nilai rendah daripada saat memulai dari titik acak. Satu-satunya peringatan adalah untuk menghindari kurungan di baskom atraksi tertentu, sehingga tendangan untuk mengubah peminim lokal menjadi titik awal untuk lari berikutnya harus cukup kuat, tetapi tidak terlalu kuat untuk menghindari kembali ke restart acak tanpa memori.

Pencarian Lokal Berulang didasarkan pada pembuatan urutan solusi optimal lokal dengan:

  1. mengganggu minimum lokal saat ini;
  2. menerapkan pencarian lokal setelah memulai dari solusi yang dimodifikasi.

Kekuatan gangguan harus cukup untuk mengarahkan lintasan ke cekungan tarikan yang berbeda yang mengarah ke optimum lokal yang berbeda.

Algoritma Gangguan

Algoritma gangguan untuk ILS bukanlah tugas yang mudah. Tujuan utamanya adalah untuk tidak terjebak dalam minimum lokal yang sama dan untuk mendapatkan properti ini benar, operasi undo dilarang. Meskipun demikian, permutasi yang baik harus mempertimbangkan banyak nilai, karena ada dua jenis permutasi buruk:

  1. terlalu lemah: kembali ke minimum lokal yang sama
  2. terlalu kuat: restart acak

Gangguan Tolok Ukur

Prosedurnya terdiri dari memperbaiki sejumlah nilai untuk gangguan sedemikian rupa sehingga nilai-nilai ini signifikan misalnya: pada probabilitas rata-rata dan tidak jarang. Setelah itu, pada saat runtime akan memungkinkan untuk memeriksa plot benchmark untuk mendapatkan ide rata-rata pada instance yang dilewati.

Gangguan Adaptif

Karena tidak ada fungsi apriori yang memberi tahu mana yang merupakan nilai yang paling cocok untuk gangguan tertentu, kriteria terbaik adalah membuatnya adaptif. Misalnya Battiti dan Protasi mengusulkan algoritma pencarian reaktif untuk MAX-SAT yang sangat cocok dengan kerangka kerja ILS. Mereka melakukan skema gangguan "terarah" yang diimplementasikan oleh algoritma pencarian tabu dan setelah setiap gangguan mereka menerapkan algoritma keturunan lokal standar. Cara lain untuk mengadaptasi gangguan adalah dengan mengubah secara deterministik kekuatannya selama pencarian.

Mengoptimalkan Gangguan

Prosedur lain adalah mengoptimalkan sub-bagian dari masalah, dengan mengaktifkan properti not-undo. Jika prosedur ini memungkinkan, semua solusi yang dihasilkan setelah gangguan cenderung sangat baik. Selanjutnya bagian-bagian baru juga dioptimalkan.

Kesimpulan

Metode ini telah diterapkan pada beberapa masalah optimasi kombinatorial termasuk masalah Penjadwalan Job Shop, Masalah Flow-Shop, Masalah Perutean Kendaraan serta banyak lainnya.

 

Sumber Artikel: en.wikipedia.org

Selengkapnya
Pencarian Lokal Berulang

Operation Research and Analysis

Mendaki Bukit

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022


Dalam analisis numerik, mendaki bukit adalah teknik optimasi matematis yang termasuk dalam keluarga pencarian lokal. Ini adalah algoritma iteratif yang dimulai dengan solusi arbitrer untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan membuat perubahan bertahap pada solusi. Jika perubahan menghasilkan solusi yang lebih baik, perubahan tambahan lainnya dilakukan pada solusi baru, dan seterusnya sampai tidak ada perbaikan lebih lanjut yang dapat ditemukan.

Misalnya, mendaki bukit dapat diterapkan pada masalah salesman keliling. Sangat mudah untuk menemukan solusi awal yang mengunjungi semua kota tetapi kemungkinan akan sangat buruk dibandingkan dengan solusi optimal. Algoritme dimulai dengan solusi semacam itu dan membuat perbaikan kecil untuknya, seperti mengubah urutan kunjungan dua kota. Akhirnya, rute yang jauh lebih pendek kemungkinan akan diperoleh.

Pendakian bukit menemukan solusi optimal untuk masalah cembung – untuk masalah lain hanya akan menemukan optima lokal (solusi yang tidak dapat diperbaiki oleh konfigurasi tetangga), yang belum tentu solusi terbaik (optimal global) dari semua solusi yang mungkin ( ruang pencarian). Contoh algoritma yang memecahkan masalah cembung dengan mendaki bukit termasuk algoritma simpleks untuk pemrograman linier dan pencarian biner.: 253  Untuk mencoba menghindari terjebak dalam optima lokal, seseorang dapat menggunakan restart (yaitu pencarian lokal berulang), atau lebih skema kompleks berdasarkan iterasi (seperti pencarian lokal berulang), atau pada memori (seperti optimasi pencarian reaktif dan pencarian tabu), atau pada modifikasi stokastik tanpa memori (seperti simulasi anil).

Kesederhanaan relatif dari algoritme menjadikannya pilihan pertama yang populer di antara algoritme pengoptimalan. Ini digunakan secara luas dalam kecerdasan buatan, untuk mencapai keadaan tujuan dari simpul awal. Pilihan yang berbeda untuk node berikutnya dan node awal digunakan dalam algoritma terkait. Meskipun algoritme yang lebih canggih seperti simulasi anil atau pencarian tabu dapat memberikan hasil yang lebih baik, dalam beberapa situasi mendaki bukit juga berfungsi dengan baik. Pendakian bukit seringkali dapat menghasilkan hasil yang lebih baik daripada algoritma lain ketika jumlah waktu yang tersedia untuk melakukan pencarian terbatas, seperti dengan sistem waktu nyata, selama sejumlah kecil peningkatan biasanya menyatu pada solusi yang baik (solusi optimal atau pendekatan dekat). Di sisi lain, bubble sort dapat dilihat sebagai algoritme pendakian bukit (setiap pertukaran elemen yang berdekatan mengurangi jumlah pasangan elemen yang tidak teratur), namun pendekatan ini jauh dari efisien bahkan untuk N yang sederhana, karena jumlah pertukaran yang diperlukan bertambah secara kuadrat.

Mendaki bukit adalah algoritme kapan saja: ia dapat mengembalikan solusi yang valid bahkan jika terputus kapan saja sebelum berakhir.

Deskripsi matematika

Mendaki bukit mencoba untuk memaksimalkan (atau meminimalkan) fungsi target f(\mathbf {x} ), di mana \mathbf {x} adalah vektor nilai kontinu dan/atau diskrit. Pada setiap iterasi, mendaki bukit akan menyesuaikan satu elemen di \mathbf {x} dan menentukan apakah perubahan meningkatkan nilai f(\mathbf {x} ). (Perhatikan bahwa ini berbeda dari metode penurunan gradien, yang menyesuaikan semua nilai dalam \mathbf {x} pada setiap iterasi sesuai dengan gradien bukit.) Dengan mendaki bukit, perubahan apa pun yang meningkatkan f(\mathbf {x} ) diterima, dan proses berlanjut sampai tidak ada perubahan yang dapat ditemukan untuk meningkatkan nilaif(\mathbf {x} ). Maka \mathbf {x} dikatakan "optimal secara lokal".

Dalam ruang vektor diskrit, setiap nilai yang mungkin untuk \mathbf {x}  dapat divisualisasikan sebagai simpul dalam graf. Pendakian bukit akan mengikuti grafik dari titik ke titik, selalu meningkat (atau menurun) secara lokal nilai f(\mathbf {x} ), hingga maksimum lokal (atau minimum lokal ) x_{m} tercapai.

Varian

Dalam pendakian bukit sederhana, simpul terdekat pertama dipilih, sedangkan pada pendakian bukit tercuram semua penerus dibandingkan dan yang paling dekat dengan solusi dipilih. Kedua bentuk gagal jika tidak ada node yang lebih dekat, yang mungkin terjadi jika ada maxima lokal di ruang pencarian yang bukan solusi. Pendakian bukit pendakian terjal mirip dengan pencarian terbaik-pertama, yang mencoba semua kemungkinan ekstensi jalur saat ini, bukan hanya satu.

Pendakian bukit stokastik tidak memeriksa semua tetangga sebelum memutuskan bagaimana cara bergerak. Sebaliknya, ia memilih tetangga secara acak, dan memutuskan (berdasarkan jumlah peningkatan pada tetangga itu) apakah akan pindah ke tetangga itu atau memeriksa yang lain.

Penurunan koordinat melakukan pencarian garis sepanjang satu arah koordinat pada titik saat ini di setiap iterasi. Beberapa versi penurunan koordinat secara acak memilih arah koordinat yang berbeda masing-masing erasi.

Pendakian bukit yang dimulai ulang secara acak adalah meta-algoritma yang dibangun di atas algoritma pendakian bukit. Ini juga dikenal sebagai pendakian bukit Shotgun. Ini secara iteratif melakukan pendakian bukit, setiap kali dengan kondisi awal acak x_{0}. x_{m} terbaik dipertahankan: jika rangkaian baru mendaki bukit menghasilkan x_{m} yang lebih baik daripada status tersimpan, ini akan menggantikan status tersimpan.

Pendakian bukit yang dimulai ulang secara acak adalah algoritma yang sangat efektif dalam banyak kasus. Ternyata seringkali lebih baik menghabiskan waktu CPU menjelajahi ruang, daripada mengoptimalkan dengan hati-hati dari kondisi awal

Masalah

Maksimum lokal

Sebuah permukaan dengan dua maxima lokal. (Hanya salah satunya adalah maksimum global.) Jika seorang pendaki bukit dimulai di lokasi yang buruk, mungkin menyatu ke maksimum yang lebih rendah.

Mendaki bukit tidak serta merta menemukan maksimum global, tetapi mungkin bertemu pada maksimum lokal. Masalah ini tidak terjadi jika heuristiknya cembung. Namun, karena banyak fungsi pendakian bukit yang tidak cembung mungkin sering gagal mencapai maksimum global. Algoritme pencarian lokal lainnya mencoba mengatasi masalah ini seperti pendakian bukit stokastik, jalan acak, dan anil simulasi.

Meskipun banyak maxima lokal dalam grafik ini, maksimum global masih dapat ditemukan dengan menggunakan simulasi annealing. Sayangnya, penerapan simulasi anil adalah masalah khusus karena bergantung pada penemuan lompatan keberuntungan yang meningkatkan posisi. Dalam contoh ekstrem seperti itu, pendakian bukit kemungkinan besar akan menghasilkan maksimum lokal.

Pegunungan dan gang

Sebuah punggungan

Punggungan adalah masalah yang menantang bagi pemanjat bukit yang mengoptimalkan dalam ruang terus menerus. Karena pemanjat bukit hanya menyesuaikan satu elemen dalam vektor pada satu waktu, setiap langkah akan bergerak dalam arah yang sejajar sumbu. Jika fungsi target membuat punggungan sempit yang menanjak ke arah yang tidak searah sumbu (atau jika tujuannya adalah meminimalkan, gang sempit yang menurun ke arah yang tidak searah sumbu), maka pemanjat bukit hanya dapat mendaki punggung bukit (atau menuruni gang) dengan zig-zag. Jika sisi punggung bukit (atau gang) sangat curam, maka pemanjat bukit mungkin terpaksa mengambil langkah yang sangat kecil karena zig-zag menuju posisi yang lebih baik. Dengan demikian, mungkin diperlukan waktu yang tidak masuk akal untuk naik ke punggung bukit (atau menuruni gang).

Sebaliknya, metode penurunan gradien dapat bergerak ke segala arah sehingga punggung bukit atau gang dapat naik atau turun. Oleh karena itu, penurunan gradien atau metode gradien konjugasi umumnya lebih disukai daripada mendaki bukit ketika fungsi target dapat dibedakan. Akan tetapi, pemanjat bukit memiliki keuntungan karena tidak memerlukan fungsi target yang dapat dibedakan, sehingga pemanjat bukit mungkin lebih disukai bila fungsi targetnya kompleks.

Dataran

Masalah lain yang terkadang terjadi dengan pendakian bukit adalah dataran tinggi. Dataran tinggi ditemui ketika ruang pencarian datar, atau cukup datar sehingga nilai yang dikembalikan oleh fungsi target tidak dapat dibedakan dari nilai yang dikembalikan untuk wilayah terdekat karena presisi yang digunakan oleh mesin untuk mewakili nilainya. Dalam kasus seperti itu, pemanjat bukit mungkin tidak dapat menentukan ke arah mana ia harus melangkah, dan mungkin mengembara ke arah yang tidak pernah mengarah pada perbaikan. 

 

Sumber Artikel: en.wikipedia.org

Selengkapnya
Mendaki Bukit

Operation Research and Analysis

Kontrol Proses Statistik

Dipublikasikan oleh Siti Nur Rahmawati pada 22 Agustus 2022


Kontrol proses statistik (SPC) adalah metode kontrol kualitas yang menggunakan metode statistik untuk memantau dan mengendalikan suatu proses. Ini membantu memastikan bahwa proses beroperasi secara efisien, menghasilkan lebih banyak produk yang sesuai dengan spesifikasi dengan lebih sedikit limbah (pengerjaan ulang atau skrap). SPC dapat diterapkan pada proses apa pun di mana output "produk yang sesuai" (produk yang memenuhi spesifikasi) dapat diukur. Alat utama yang digunakan dalam SPC termasuk grafik lari, grafik kontrol, fokus pada peningkatan berkelanjutan, dan desain eksperimen. Contoh proses di mana SPC diterapkan adalah jalur manufaktur.

SPC harus dipraktekkan dalam dua fase: Fase pertama adalah pembentukan awal proses, dan fase kedua adalah penggunaan proses produksi secara teratur. Pada fase kedua, keputusan periode yang akan diperiksa harus dibuat, tergantung pada perubahan kondisi 5M&E (Man, Machine, Material, Method, Movement, Environment) dan tingkat keausan suku cadang yang digunakan dalam proses manufaktur (suku cadang mesin , jig, dan perlengkapan).

Keuntungan SPC dibandingkan metode kontrol kualitas lainnya, seperti "inspeksi", adalah bahwa metode ini menekankan deteksi dini dan pencegahan masalah, daripada koreksi masalah setelah terjadi.

Selain mengurangi pemborosan, SPC dapat mengurangi waktu yang dibutuhkan untuk menghasilkan produk. SPC memperkecil kemungkinan produk jadi perlu dikerjakan ulang atau dibuang.

Sejarah

Kontrol proses statistik dipelopori oleh Walter A. Shewhart di Bell Laboratories pada awal 1920-an. Shewhart mengembangkan peta kendali pada tahun 1924 dan konsep keadaan kendali statistik. Kontrol statistik setara dengan konsep pertukaran[1][2] yang dikembangkan oleh ahli logika William Ernest Johnson juga pada tahun 1924 dalam bukunya Logic, Part III: The Logical Foundations of Science.[3] Bersama dengan tim di AT&T yang mencakup Harold Dodge dan Harry Romig, ia juga bekerja untuk menempatkan inspeksi pengambilan sampel pada basis statistik yang rasional. Shewhart berkonsultasi dengan Kolonel Leslie E. Simon dalam penerapan peta kendali untuk pembuatan amunisi di Picatinny Arsenal Angkatan Darat pada tahun 1934. Penerapan yang berhasil itu membantu meyakinkan Ordnance Angkatan Darat untuk melibatkan George Edwards dari AT&T untuk berkonsultasi tentang penggunaan kendali mutu statistik di antara divisi-divisinya dan kontraktor pada pecahnya Perang Dunia II.

W. Edwards Deming mengundang Shewhart untuk berbicara di Sekolah Pascasarjana Departemen Pertanian AS dan menjabat sebagai editor buku Shewhart Statistical Method from the Viewpoint of Quality Control (1939), yang merupakan hasil dari kuliah tersebut. Deming adalah arsitek penting kursus singkat kendali mutu yang melatih industri Amerika dalam teknik-teknik baru selama Perang Dunia II. Lulusan kursus masa perang ini membentuk masyarakat profesional baru pada tahun 1945, American Society for Quality Control, yang memilih Edwards sebagai presiden pertamanya. Deming melakukan perjalanan ke Jepang selama Pendudukan Sekutu dan bertemu dengan Persatuan Ilmuwan dan Insinyur Jepang (JUSE) dalam upaya untuk memperkenalkan metode SPC ke industri Jepang.[4][5]

Sumber variasi 'umum' dan 'khusus'

Shewhart membaca teori statistik baru yang keluar dari Inggris, terutama karya William Sealy Gosset, Karl Pearson, dan Ronald Fisher. Namun, dia mengerti bahwa data dari proses fisik jarang menghasilkan kurva distribusi normal (yaitu, distribusi Gaussian atau 'kurva lonceng'). Dia menemukan bahwa data dari pengukuran variasi di bidang manufaktur tidak selalu berperilaku seperti data dari pengukuran fenomena alam (misalnya, gerakan partikel Brown). Shewhart menyimpulkan bahwa sementara setiap proses menampilkan variasi, beberapa proses menampilkan variasi yang wajar bagi proses (sumber variasi "umum"); proses-proses ini ia gambarkan berada dalam kendali (statistik). Proses lain juga menampilkan variasi yang tidak ada dalam sistem kausal dari proses sepanjang waktu (sumber variasi "khusus"), yang digambarkan Shewhart sebagai tidak terkendali.

Aplikasi untuk proses non-manufaktur

Kontrol proses statistik sesuai untuk mendukung setiap proses berulang, dan telah diterapkan di banyak pengaturan di mana misalnya sistem manajemen mutu ISO 9000 digunakan, termasuk audit keuangan dan akuntansi, operasi TI, proses perawatan kesehatan, dan proses administrasi seperti pengaturan pinjaman dan administrasi, penagihan pelanggan, dll. Terlepas dari kritik atas penggunaannya dalam desain dan pengembangan, ini adalah tempat yang tepat untuk mengelola tata kelola data semi-otomatis dari operasi pemrosesan data volume tinggi, misalnya di gudang data perusahaan, atau manajemen kualitas data perusahaan sistem. [7]

Dalam Capability Maturity Model (CMM) 1988, Institut Rekayasa Perangkat Lunak menyarankan agar SPC dapat diterapkan pada proses rekayasa perangkat lunak. Praktek Level 4 dan Level 5 dari Capabil ity Maturity Model Integration (CMMI) menggunakan konsep ini.

Penerapan SPC untuk non-repetitive, proses pengetahuan-intensif, seperti penelitian dan pengembangan atau rekayasa sistem, telah menghadapi skeptisisme dan tetap kontroversial.

Dalam No Silver Bullet, Fred Brooks menunjukkan bahwa kompleksitas, persyaratan kesesuaian, kemampuan berubah, dan ketidaktampakan perangkat lunak menghasilkan variasi yang melekat dan esensial yang tidak dapat dihilangkan. Ini menyiratkan bahwa SPC kurang efektif dalam pengembangan perangkat lunak daripada di, misalnya, manufaktur.

Variasi dalam pembuatan

Dalam manufaktur, kualitas didefinisikan sebagai kesesuaian dengan spesifikasi. Namun, tidak ada dua produk atau karakteristik yang sama persis, karena setiap proses mengandung banyak sumber variabilitas. Dalam pembuatan massal, secara tradisional, kualitas barang jadi dipastikan dengan inspeksi produk pasca-manufaktur. Setiap artikel (atau sampel artikel dari lot produksi) dapat diterima atau ditolak sesuai dengan seberapa baik memenuhi spesifikasi desainnya, SPC menggunakan alat statistik untuk mengamati kinerja proses produksi untuk mendeteksi variasi yang signifikan sebelum menghasilkan produksi barang di bawah standar. Setiap sumber variasi pada setiap titik waktu dalam suatu proses akan jatuh ke dalam salah satu dari dua kelas.

(1) Penyebab umum

Penyebab 'umum' kadang-kadang disebut sebagai sumber variasi 'tidak dapat ditentukan', atau 'normal'. Ini mengacu pada sumber variasi apa pun yang secara konsisten bertindak pada proses, yang biasanya ada banyak. Jenis penyebab ini secara kolektif menghasilkan distribusi yang stabil secara statistik dan berulang dari waktu ke waktu.

(2) Penyebab khusus

Penyebab 'khusus' kadang-kadang disebut sebagai sumber variasi yang 'dapat dialihkan'. Istilah ini mengacu pada setiap faktor yang menyebabkan variasi yang hanya mempengaruhi beberapa keluaran proses. Mereka sering terputus-putus dan tidak dapat diprediksi.

Sebagian besar proses memiliki banyak sumber variasi; kebanyakan dari mereka adalah kecil dan dapat diabaikan. Jika sumber variasi yang dapat ditetapkan yang dominan terdeteksi, berpotensi mereka dapat diidentifikasi dan dihilangkan. Ketika mereka dihapus, prosesnya dikatakan 'stabil'. Ketika suatu proses stabil, variasinya harus tetap dalam batas-batas yang diketahui. Yaitu, setidaknya, sampai sumber variasi lain yang dapat ditentukan terjadi.

Misalnya, lini pengemasan sereal sarapan dapat dirancang untuk mengisi setiap kotak sereal dengan 500 gram sereal. Beberapa kotak akan memiliki sedikit lebih dari 500 gram, dan beberapa akan memiliki sedikit lebih sedikit. Ketika berat paket diukur, data akan menunjukkan distribusi berat bersih.

Jika proses produksi, inputnya, atau lingkungannya (misalnya, mesin on line) berubah, distribusi data akan berubah. Misalnya, karena cam dan puli mesin aus, mesin pengisi sereal dapat memasukkan lebih dari jumlah sereal yang ditentukan ke dalam setiap kotak. Meskipun ini mungkin menguntungkan pelanggan, dari sudut pandang produsen, hal itu boros, dan meningkatkan biaya produksi. Jika pabrikan menemukan perubahan dan sumbernya pada waktu yang tepat, perubahan tersebut dapat diperbaiki (misalnya, cam dan puli diganti).

Dari perspektif SPC, jika berat setiap kotak sereal bervariasi secara acak, beberapa lebih tinggi dan beberapa lebih rendah, selalu dalam kisaran yang dapat diterima, maka proses tersebut dianggap stabil. Jika cam dan puli mesin mulai aus, bobot kotak sereal mungkin tidak acak. Fungsi cam dan puli yang menurun dapat menyebabkan pola linier non-acak dari peningkatan bobot kotak sereal. Kami menyebutnya variasi penyebab umum. Namun, jika semua kotak sereal tiba-tiba beratnya lebih dari rata-rata karena kerusakan tak terduga dari cams dan puli, ini akan dianggap sebagai variasi penyebab khusus.

Aplikasi

Penerapan SPC melibatkan tiga fase kegiatan utama:

  1. Memahami proses dan batasan spesifikasi.
  2. Menghilangkan sumber variasi yang dapat dialihkan (khusus), sehingga prosesnya stabil.
  3. Memantau proses produksi yang sedang berjalan, dibantu dengan penggunaan peta kendali, untuk mendeteksi perubahan yang signifikan dari rata-rata atau variasi.

Bagan kendali

Data dari pengukuran variasi pada titik-titik pada peta proses dipantau menggunakan diagram kendali. Bagan kontrol berusaha membedakan sumber variasi yang "dapat ditetapkan" ("khusus") dari sumber "umum". Sumber "umum", karena merupakan bagian yang diharapkan dari proses, tidak terlalu diperhatikan oleh pabrikan daripada sumber "dapat dialihkan". Menggunakan diagram kendali adalah aktivitas yang berkelanjutan, terus-menerus dari waktu ke waktu.

Proses yang stabil

Ketika proses tidak memicu salah satu "aturan deteksi" bagan kontrol untuk bagan kontrol, itu dikatakan "stabil". Analisis kemampuan proses dapat dilakukan pada proses yang stabil untuk memprediksi kemampuan proses untuk menghasilkan "produk yang sesuai" di masa depan.

Proses yang stabil dapat ditunjukkan dengan tanda tangan proses yang bebas dari varians di luar indeks kemampuan. Tanda tangan proses adalah titik-titik yang diplot dibandingkan dengan indeks kemampuan.

Variasi berlebihan

Ketika proses memicu salah satu dari "aturan deteksi" bagan kontrol (atau sebagai alternatif, kemampuan proses rendah), aktivitas lain dapat dilakukan untuk mengidentifikasi sumber variasi yang berlebihan. Alat yang digunakan dalam kegiatan ekstra ini meliputi: diagram Ishikawa, eksperimen yang dirancang, dan diagram Pareto. Eksperimen yang dirancang adalah sarana untuk mengukur secara objektif kepentingan relatif (kekuatan) sumber variasi. Setelah sumber variasi (penyebab khusus) diidentifikasi, mereka dapat diminimalkan atau dihilangkan. Langkah-langkah untuk menghilangkan sumber variasi mungkin termasuk: pengembangan standar, pelatihan staf, pemeriksaan kesalahan, dan perubahan pada proses itu sendiri atau inputnya.

Metrik stabilitas proses

Saat memantau banyak proses dengan diagram kendali, terkadang berguna untuk menghitung ukuran kuantitatif stabilitas proses. Metrik ini kemudian dapat digunakan untuk mengidentifikasi/memprioritaskan proses yang paling membutuhkan tindakan korektif. Metrik ini juga dapat dilihat sebagai pelengkap metrik kemampuan proses tradisional. Beberapa metrik telah diusulkan, seperti yang dijelaskan dalam Ramirez dan Runger. Yaitu (1) Rasio Stabilitas yang membandingkan variabilitas jangka panjang dengan variabilitas jangka pendek, (2) Uji ANOVA yang membandingkan variasi dalam-subkelompok dengan variasi antar-subkelompok, dan (3) Rasio Ketidakstabilan yang membandingkan jumlah subgrup yang memiliki satu atau lebih pelanggaran aturan Western Electric dengan jumlah total subgrup.

Matematika diagram kendali

Bagan kendali digital menggunakan aturan berbasis logika yang menentukan "nilai turunan" yang menandakan perlunya koreksi. Sebagai contoh,

nilai turunan = nilai terakhir + selisih absolut rata-rata antara N angka terakhir.

 

Sumber Artikel: en.wikipedia.org

Selengkapnya
Kontrol Proses Statistik
« First Previous page 9 of 9