Optimasi kombinatorial

Optimasi kombinatorial merupakan subbidang optimasi matematis yang terdiri dari pencarian objek yang optimal dari sekumpulan objek berhingga, dimana himpunan solusi fisibel adalah diskrit atau dapat direduksi menjadi himpunan diskrit. Masalah optimasi kombinatorial yang umum adalah masalah travelling salesman ("TSP"), masalah pohon merentang minimum ("MST"), dan masalah knapsack. Dalam banyak masalah seperti itu, seperti yang disebutkan sebelumnya, pencarian lengkap tidak dapat dilacak, sehingga algoritma khusus yang dengan cepat mengesampingkan sebagian besar ruang pencarian atau algoritma perkiraan harus digunakan sebagai gantinya.

Optimasi kombinatorial berkaitan dengan riset operasi, teori algoritma, dan teori kompleksitas komputasi. Ini memiliki aplikasi penting di beberapa bidang, termasuk kecerdasan buatan, pembelajaran mesin, teori lelang, rekayasa perangkat lunak, matematika terapan, dan ilmu komputer teoretis.

Beberapa literatur penelitian menganggap optimasi diskrit terdiri dari pemrograman integer bersama dengan optimasi kombinatorial (yang pada gilirannya terdiri dari masalah optimasi yang berhubungan dengan struktur grafik), meskipun semua topik ini memiliki literatur penelitian yang terkait erat. Ini sering melibatkan penentuan cara untuk secara efisien mengalokasikan sumber daya yang digunakan untuk menemukan solusi untuk masalah matematika.

Aplikasi

Logistik

• Optimalisasi rantai pasokan
• Mengembangkan jaringan jari-jari dan tujuan maskapai terbaik
• Memutuskan taksi mana dalam armada yang akan dirutekan untuk mengambil tarif
• Menentukan cara pengiriman paket yang optimal
• Mengalokasikan pekerjaan kepada orang-orang secara optimal
• Merancang jaringan distribusi air
• Masalah ilmu kebumian (misalnya laju aliran reservoir)

Metode

Ada banyak literatur tentang algoritma waktu polinomial untuk kelas khusus tertentu dari optimasi diskrit. Sejumlah besar itu disatukan oleh teori pemrograman linier. Beberapa contoh masalah optimasi kombinatorial yang dicakup oleh kerangka kerja ini adalah jalur terpendek dan pohon jalur terpendek, aliran dan sirkulasi, pohon rentang, pencocokan, dan masalah matroid.

Untuk masalah optimasi diskrit lengkap NP, literatur penelitian saat ini mencakup topik-topik berikut:

• waktu polinomial kasus khusus yang dapat dipecahkan secara tepat dari masalah yang dihadapi (misalnya, masalah yang dapat diselesaikan dengan parameter tetap)
• algoritme yang berkinerja baik pada instans "acak" (mis. untuk masalah penjual keliling)
• algoritma aproksimasi yang berjalan dalam waktu polinomial dan menemukan solusi yang mendekati optimal
• memecahkan contoh dunia nyata yang muncul dalam praktik dan tidak selalu menunjukkan perilaku kasus terburuk dalam masalah NP-lengkap (misalnya contoh TSP dunia nyata dengan puluhan ribu node [6]).

Masalah optimasi kombinatorial dapat dilihat sebagai pencarian elemen terbaik dari beberapa set item diskrit; oleh karena itu, pada prinsipnya, segala jenis algoritma pencarian atau metaheuristik dapat digunakan untuk menyelesaikannya. Mungkin pendekatan [kata musang] yang paling dapat diterapkan secara universal adalah cabang-dan-terikat (algoritma tepat yang dapat dihentikan kapan saja untuk berfungsi sebagai heuristik), cabang-dan-potong (menggunakan optimasi linier untuk menghasilkan batas), dinamis pemrograman (konstruksi solusi rekursif dengan jendela pencarian terbatas) dan pencarian tabu (algoritma swapping tipe serakah). Namun, algoritma pencarian generik tidak dijamin untuk menemukan solusi optimal terlebih dahulu, juga tidak dijamin berjalan cepat (dalam waktu polinomial). Karena beberapa masalah optimasi diskrit adalah NP-complete, seperti masalah travelling salesman (decision),[7] hal ini diharapkan kecuali P=NP.

Definisi formal

Secara formal, masalah optimisasi kombinatorial adalah empat kali lipat, di mana

•  adalah sekumpulan instance;
• diberikan contoh adalah himpunan hingga dari solusi layak;
• diberikan contoh dan solusi yang layak dari , menunjukkan ukuran , yang biasanya real positif.
• adalah fungsi tujuan, dan merupakan  atau .

Tujuannya adalah kemudian untuk menemukan beberapa contoh solusi optimal, yaitu solusi yang layak  dengan

Untuk setiap masalah optimasi kombinatorial, ada masalah keputusan terkait yang menanyakan apakah ada solusi yang layak untuk ukuran tertentu . Misalnya, jika ada graf yang berisi simpul dan , masalah pengoptimalan mungkin "menemukan jalur dari ke  yang menggunakan tepi paling sedikit". Masalah ini mungkin memiliki jawaban, katakanlah, 4. Masalah keputusan yang sesuai adalah "apakah ada jalur dari ke  yang menggunakan 10 sisi atau lebih sedikit?" Masalah ini dapat dijawab dengan sederhana 'ya' atau 'tidak'.

Bidang algoritme aproksimasi berkaitan dengan algoritme untuk menemukan solusi yang mendekati optimal untuk masalah sulit. Versi keputusan yang biasa kemudian merupakan definisi masalah yang tidak memadai karena hanya menentukan solusi yang dapat diterima. Meskipun kita dapat memperkenalkan masalah keputusan yang sesuai, masalah tersebut kemudian secara lebih alami dicirikan sebagai masalah optimasi.

Masalah optimasi NP

Masalah optimasi NP (NPO) adalah masalah optimasi kombinatorial dengan kondisi tambahan berikut.[9] Perhatikan bahwa polinomial yang dirujuk di bawah ini adalah fungsi dari ukuran input fungsi masing-masing, bukan ukuran beberapa set implisit dari instance input.

• ukuran setiap solusi yang layak dibatasi secara polinomial dalam ukuran instance yang diberikan ,
• bahasa dan  dapat dikenali dalam waktu polinomial, dan
• adalah waktu polinomial yang dapat dihitung.

Ini menyiratkan bahwa masalah keputusan yang sesuai ada di NP. Dalam ilmu komputer, masalah optimasi yang menarik biasanya memiliki sifat-sifat di atas dan oleh karena itu merupakan masalah NPO. Masalah juga disebut masalah optimasi-P (PO), jika ada algoritma yang menemukan solusi optimal dalam waktu polinomial. Seringkali, ketika berhadapan dengan kelas NPO, seseorang tertarik pada masalah optimasi yang versi keputusannya adalah NP-complete. Perhatikan bahwa hubungan kekerasan selalu berkaitan dengan beberapa pengurangan. Karena hubungan antara algoritma aproksimasi dan masalah optimasi komputasi, reduksi yang mempertahankan aproksimasi dalam beberapa hal lebih disukai untuk subjek ini daripada reduksi Turing dan Karp biasa. Contoh pengurangan seperti itu adalah pengurangan-L. Untuk alasan ini, masalah optimasi dengan versi keputusan NP-complete tidak selalu disebut NPO-complete.

NPO dibagi menjadi beberapa subkelas berikut menurut perkiraannya:

• NPO(I): Sama dengan FPTAS. Berisi masalah Knapsack.
• NPO(II): Sama dengan PTAS. Berisi masalah penjadwalan Makespan.
• NPO(III): :Kelas masalah NPO yang memiliki algoritma polinomial-waktu yang menghitung solusi dengan biaya paling banyak c kali biaya optimal (untuk masalah minimisasi) atau biaya paling sedikit {\displaystyle 1/c}1/c dari biaya optimal (untuk masalah maksimisasi). Dalam buku Hromkovi[yang mana?], yang dikecualikan dari kelas ini adalah semua masalah NPO(II) kecuali jika P=NP. Tanpa pengecualian, sama dengan APX. Berisi MAX-SAT dan metrik TSP.
• NPO(IV): :Kelas masalah NPO dengan algoritma waktu polinomial yang mendekati solusi optimal dengan rasio polinomial dalam logaritma dari ukuran input. Dalam buku Hromkovi, semua masalah NPO(III) dikeluarkan dari kelas ini kecuali P=NP. Berisi masalah set cover.
• NPO(V): :Kelas masalah NPO dengan algoritma waktu polinomial yang mendekati solusi optimal dengan rasio yang dibatasi oleh beberapa fungsi pada n. Dalam buku Hromkovic, semua masalah
• NPO(IV) dikeluarkan dari kelas ini kecuali P=NP. Berisi masalah TSP dan klik.

Masalah NPO disebut berbatas polinomial (PB) jika, untuk setiap instance dan untuk setiap solusi , ukurannya dibatasi oleh fungsi polinomial dengan ukuran . Kelas NPOPB adalah kelas masalah NPO yang berbatas polinomial.

Masalah khusus

Ini adalah daftar dinamis dan mungkin tidak akan pernah dapat memenuhi standar kelengkapan tertentu. Anda dapat membantu dengan menambahkan item yang hilang dengan sumber terpercaya.

Tur wiraniaga keliling yang optimal melalui 15 kota terbesar di Jerman. Ini adalah tur terpendek di antara 43.589.145.600 kemungkinan tur yang mengunjungi setiap kota tepat satu kali.

• Masalah tugas
• Masalah penutupan
• Masalah kepuasan kendala
• Masalah pemotongan stok
• Masalah himpunan yang mendominasi
• Pemrograman bilangan bulat
• Masalah ransel
• Variabel relevan minimum dalam sistem linier
• Pohon merentang minimum
• Masalah penjadwalan perawat
• Setel masalah penutup
• Penjadwalan toko kerja
• Masalah penjual keliling
• Masalah penjadwalan ulang kendaraan
• Masalah perutean kendaraan
• Masalah penugasan target senjata
• Masalah pengepakan tempat sampah

Disadur dari: en.wikipedia.org

Teori Konstruktivisme didefinisikan sebagai pembelajaran yang bersifat generatif, yaitu tindakan mencipta sesuatu makna dari apa yang dipelajari. Konstruktivisme sebenarnya bukan merupakan gagasan yang baru, apa yang dilalui dalam kehidupan kita selama ini merupakan himpunan dan pembinaan pengalaman demi pengalaman. Ini menyebabkan seseorang mempunyai pengetahuan dan menjadi lebih dinamis. Pendekatan konstruktivisme mempunyai beberapa konsep umum seperti:

1. Pelajar aktif membina pengetahuan berasaskan pengalaman yang sudah ada.
2. Dalam konteks pembelajaran, pelajar seharusnya mampu membina pengetahuan mereka secara mandiri.
3. Pentingnya membina pengetahuan secara aktif oleh pelajar sendiri melalui proses saling memengaruhi antara pembelajaran terdahulu dengan pembelajaran terbaru.
4. Unsur terpenting dalam teori ini ialah seseorang membina pengetahuan dirinya secara aktif dengan cara membandingkan informasi baru dengan pemahamannya yang sudah ada.
5. Ketidakseimbangan merupakan faktor motivasi pembelajaran yang utama. Faktor ini berlaku apabila seorang pelajar menyadari gagasan-gagasannya tidak konsisten atau sesuai dengan pengetahuan ilmiah.
6. Bahan pengajaran yang disediakan perlu mempunyai perkaitan dengan pengalaman pelajar untuk menarik minat pelajar.

Sumber Artikel : Wikipedia

Pendidikan lingkungan hidup adalah suatu proses untuk membangun populasi manusia di dunia yang sadar dan peduli terhadap lingkungan total (keseluruhan) dan segala masalah yang berkaitan dengannya, dan masyarakat yang memiliki pengetahuan, ketrampilan, sikap dan tingkah laku, motivasi serta komitmen untuk bekerja sama , baik secara individu maupun secara kolektif , untuk dapat memecahkan berbagai masalah lingkungan saat ini, dan mencegah timbulnya masalah baru. (UNESCO, Deklarasi Tbilisi, 1977)

Prinsip Pendidikan Lingkungan Hidup

1. Mempertimbangkan lingkungan sebagai suatu totalitas — alami dan buatan, bersifat teknologi dan sosial (ekonomi, politik, kultural, historis, moral, estetika);
2. Merupakan suatu proses yang berjalan secara terus menerus dan sepanjang hidup, dimulai pada zaman pra sekolah, dan berlanjut ke tahap pendidikan formal maupun non formal;
3. Mempunyai pendekatan yang sifatnya interdisipliner, dengan menarik/mengambil isi atau ciri spesifik dari masing-masing disiplin ilmu sehingga memungkinkan suatu pendekatan yang holistik dan perspektif yang seimbang.
4. Meneliti (examine) issue lingkungan yang utama dari sudut pandang lokal, nasional, regional dan internasional, sehingga siswa dapat menerima insight mengenai kondisi lingkungan di wilayah geografis yang lain;
5. Memberi tekanan pada situasi lingkungan saat ini dan situasi lingkungan yang potensial, dengan memasukkan pertimbangan perspektif historisnya;
6. Mempromosikan nilai dan pentingnya kerja sama lokal, nasional dan internasional untuk mencegah dan memecahkan masalah-masalah lingkungan;
7. Secara eksplisit mempertimbangkan/memperhitungkan aspek lingkungan dalam rencana pembangunan dan pertumbuhan;
8. Memampukan peserta didik untuk mempunyai peran dalam merencanakan pengalaman belajar mereka, dan memberi kesempatan pada mereka untuk membuat keputusan dan menerima konsekuensi dari keputusan tersebut;
9. Menghubungkan (relate) kepekaan kepada lingkungan, pengetahuan, ketrampilan untuk memecahkan masalah dan klarifikasi nilai pada setiap tahap umur, tetapi bagi umur muda (tahun-tahun pertama) diberikan tekanan yang khusus terhadap kepekaan lingkungan terhadap lingkungan tempat mereka hidup;
10. Membantu peserta didik untuk menemukan (discover), gejala-gejala dan penyebab dari masalah lingkungan;
11. Memberi tekanan mengenai kompleksitas masalah lingkungan, sehingga diperlukan kemampuan untuk berpikir secara kritis dengan ketrampilan untuk memecahkan masalah.
12. Memanfaatkan beraneka ragam situasi pembelajaran (learning environment) dan berbagai pendekatan dalam pembelajaran mengenai dan dari lingkungan dengan tekanan yang kuat pada kegiatan-kegiatan yang sifatnya praktis dan memberikan pengalaman secara langsung (first – hand experience).

Fokus

Pendidikan Lingkungan Hidup berfokus pada:

• Kepedulian dan sensitifitas terhadap lingkungan hidup dan tantangannya.
• Pengetahuan dan pemahaman tentang lingkungan hidup dan tantangannya.
• Perubahan perilaku terhadap lingkungan hidup dan mengembangkan peningkatan kualitas lingkungan hidup.
• Keahlian untuk mengantisipasi terjadinya permasalahan lingkungan hidup.
• Partisipasi untuk menerapkan pengetahuan dan keahlian terkait program lingkungan hidup.

Sejarah

Pada tahun 1977/1978 rintisan Garis‐garis Besar Program Pengajaran Lingkungan Hidup diujicobakan di 15 Sekolah Dasar Jakarta. Pada tahun 1979 di bawah koordinasi Kantor Menteri Negara Pengawasan Pembangunan dan Lingkungan Hidup (Meneg PPLH) dibentuk Pusat Studi Lingkungan (PSL) di berbagai perguruan tinggi negeri dan swasta, di mana pendidikan Analisis Mengenai Dampak Lingkungan (AMDAL mulai dikembangkan).

Tahun 1986, Pendidikan Lingkungan Hidup dan Kependudukan dimasukkan ke dalam pendidikan formal dengan dibentuknya mata pelajaran Pendidikan kependudukan dan lingkungan hidup (PKLH). Depdikbud merasa perlu untuk mulai mengintegrasikan PKLH ke dalam semua mata pelajaran

Sejak tahun 1989/1990, berbagai pelatihan tentang lingkungan hidup telah diperkenalkan oleh Departemen Pendidikan Nasional bagi guru-guru SD, SMP dan SMA termasuk Sekolah Kejuruan.

Tahun 1996 terbentuk Jaringan Pendidikan Lingkungan (JPL) antara LSM-LSM yang berminat dan menaruh perhatian terhadap pendidikan lingkungan. Hingga tahun 2004 tercatat 192 anggota JPL yang bergerak dalam pengembangan dan pelaksanaan pendidikan lingkungan. Tahun 2013, JPL melaksanakan Pertemuan Nasional Jaringan Pendidikan Lingkungan di Jogjakarta.

Pada tahun 1996 disepakati kerja sama pertama antara Departemen Pendidikan Nasional dan Kementerian Negara Lingkungan Hidup, No. 0142/U/1996 dan No Kep: 89/MENLH/5/1996 tentang Pembinaan dan Pengembangan Pendidikan Lingkungan Hidup tanggal 21 Mei 1996, yang diperbaharui pada tahun 2005 (nomor: Kep No 07/MenLH/06/2005 No 05/VI/KB/2005 tanggal 5 Juli 2005) dan tahun 2010. Sebagai tindak lanjut dari kesepakatan tahun 2005, pada tahun 2006 Kementerian Lingkungan Hidup mengembangkan program pendidikan lingkungan hidup pada jenjang pendidikan dasar dan menengah melalui program Adiwiyata. Program ini dilaksanakan di 10 sekolah di Pulau Jawa sebagai sekolah model dengan melibatkan perguruan tinggi dan LSM yang bergerak di bidang Pendidikan Lingkungan Hidup.

Kementerian Lingkungan Hidup sejah tahun 2006 mengembangkan Program Sekolah Adiwiyata. Sejak tahun 2006 sampai 2011 yang ikut partisipasi dalam program Adiwiyata baru mencapai 1.351 sekolah dari 251.415 sekolah (SD, SMP, SMA, SMK) Se‐Indonesia, diantaranya yang mendapat Adiwiyata mandiri : 56 sekolah, Adiwiyata: 113 sekolah, calon Adiwiyata 103 sekolah, atau total yang mendapat penghargaan Adiwiyata mencapai 272 Sekolah (SD, SMP, SMA, SMK) Se‐Indonesia.

Kategori Pendidikan Lingkungan Hidup

PLH dikategorikan menjadi:

1. PLH formal yaitu kegiatan pendidikan di bidang lingkungan hidup yang diselenggarakan melalui sekolah yang terdiri atas pendidikan dasar, menengah, dan tinggi yang dilakukan secara terstruktur dengan menggunakan metode pendekatan kurikulum yang terintegrasi maupun kurikulum yang monolitik atau tersendiri
2. PLH non-formal adalah kegiatan pendidikan di bidang lingkungan hidup yang dilakukan di luar sekolah yang dapat dilaksanakan secara terstruktur dan berjenjang, misalnya AMDAL, ISO, dan PPNS.

Sumber Artikel : Wikipedia

Matematika komputasional 

Matematika komputasi mencakup studi matematika dalam matematika serta bidang ilmiah di mana ilmu komputer memainkan peran sentral dan penting, menekankan algoritma, metode numerik, dan perhitungan simbolik.

Matematika komputasi terapan adalah penggunaan matematika untuk mengaktifkan dan meningkatkan perhitungan komputasi dalam matematika terapan. Matematika Komputasi juga dapat merujuk pada penggunaan komputer dalam matematika itu sendiri. Hal ini termasuk penggunaan komputer untuk perhitungan matematis (aljabar komputer), studi tentang apa yang dapat (dan tidak dapat) dikomputerisasi dalam matematika (metode efektif), perhitungan apa yang dapat dilakukan dengan teknologi saat ini (Teori Kompleksitas), dan demonstrasi apa yang diperlukan. mungkin dilakukan. diterima. dilakukan di komputer (tes asisten).

Bidang matematika komputasi

Matematika komputasi, sebagai cabang yang berkembang dari matematika terapan pada awal 1950-an, melibatkan beragam aspek yang mencakup ilmu komputasi atau komputasi ilmiah, yang mencakup pemecahan masalah matematika melalui simulasi komputer daripada metode analitik matematika terapan.

Disiplin ini mencakup penerapan metode numerik seperti aljabar linier numerik dan solusi numerik persamaan diferensial parsial, serta metode stokastik seperti metode Monte Carlo untuk mengatasi representasi ketidakpastian dalam konteks komputasi ilmiah.

Matematika komputasi juga mencakup analisis numerik dan teori metode numerik, kompleksitas komputasi, aljabar komputer, dan sistem aljabar komputer. Selain itu, penelitian berbantuan komputer diterapkan dalam berbagai bidang matematika, seperti logika, matematika diskrit, kombinatorik, teori bilangan, dan topologi aljabar komputasi.

Aspek kriptografi dan keamanan komputer, termasuk pengujian primalitas, faktorisasi, kurva eliptik, dan matematika blockchain, juga menjadi bagian dari matematika komputasi. Disiplin ini juga merambah ke linguistik komputasi, geometri aljabar komputasi, teori grup komputasi, geometri komputasi, teori bilangan komputasi, topologi komputasi, statistik komputasi, teori informasi algoritma, teori permainan algoritma, dan ekonomi matematika yang melibatkan penerapan matematika dalam ekonomi, keuangan, dan sebagian akuntansi. Ini juga mencakup eksplorasi matematika eksperimental.

Disadur dari : en.wikipedia.org

Ekonomi rumah tangga, ilmu domestik atau ilmu rumah adalah sebuah bidang studi^[1] yang mempelajari hubungan antara individu, keluarga, komunitas, dan lingkungan tempat mereka tinggal.

Sumber Artikel : Wikipedia

Feasible Region

Dalam optimasi matematis, wilayah, himpunan, ruang pencarian, atau ruang solusi yang layak adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel yang dipilih) dari suatu masalah optimasi yang memenuhi batasan masalah tersebut. , yang mungkin mengandung kesenjangan, persamaan dan ketidaksetaraan. pembatasan bilangan bulat. Ini adalah rangkaian solusi pertama yang mungkin untuk mengatasi masalah tersebut sebelum mempersempit kelompok kandidat.

Misalnya, pertimbangkan masalah meminimalkan fungsi sehubungan dengan variabel dan , tunduk pada dan Di sini himpunan layak adalah himpunan pasangan (x,y) yang nilai x paling sedikit 1 dan paling banyak 10 dan nilai y paling sedikit 5 dan paling banyak 12. Himpunan masalah yang layak terpisah dari fungsi tujuan, yang menyatakan kriteria yang akan dioptimalkan dan yang dalam contoh di atas adalah

Dalam banyak permasalahan, himpunan layak mencerminkan batasan bahwa satu atau lebih variabel tidak boleh negatif. Untuk permasalahan pemrograman yang hanya menggunakan bilangan bulat, himpunan bilangan bulat (atau bagiannya) adalah himpunan yang diperbolehkan. Dalam permasalahan program linier, himpunan layak adalah politop cembung: wilayah ruang multidimensi yang batasnya dibentuk oleh bidang hiper dan simpulnya adalah simpul.

Kepuasan kendala adalah proses menemukan titik di wilayah yang layak.

Daerah fisibel tertutup dari masalah program linier dengan tiga variabel adalah polihedron cembung.

Himpunan layak cembung

Dalam masalah pemrograman linier, serangkaian kendala linier menghasilkan wilayah layak cembung dari nilai-nilai yang mungkin untuk variabel-variabel tersebut. Dalam kasus dua variabel daerah ini berbentuk poligon sederhana cembung.

Himpunan layak cembung adalah himpunan yang ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya dan tidak melalui suatu titik di luar himpunan layak tersebut. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah program linier, dan sangat menarik karena masalah dengan fungsi tujuan konveks yang dimaksimalkan umumnya lebih mudah diselesaikan jika ada solusi cembung. set yang diizinkan, dan setiap maksimum lokal juga merupakan maksimum global.

Tidak ada set yang layak

Jika kendala dari masalah optimasi saling bertentangan, tidak ada titik yang memenuhi semua kendala dan dengan demikian wilayah yang layak adalah himpunan nol. Dalam hal ini masalah tidak memiliki solusi dan dikatakan tidak layak.

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan layak terbatas dan tidak terbatas

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan yang dapat diwujudkan bisa terbatas atau tidak terbatas. Misalnya, himpunan nilai realisasi yang ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0} tidak terhingga karena tidak ada batasan jarak yang dapat ditempuh dalam arah tertentu selama berada dalam rentang nilai realisasi tetap. Sebaliknya, himpunan kemungkinan yang dibentuk oleh himpunan batasan {x ≥ 0, y ≥ 0, x + 2y ≤ 4} adalah terbatas karena amplitudo pergerakan ke segala arah dibatasi oleh batasan tersebut.

Untuk masalah program linier dengan n variabel, kondisi yang diperlukan tetapi tidak cukup untuk membatasi himpunan kemungkinan adalah jumlah batasan paling sedikit n + 1 (seperti yang ditunjukkan pada contoh di atas).

Ketika himpunan kemungkinan tidak terbatas, optimalitas mungkin terjadi atau tidak tergantung pada spesifikasi fungsi tujuan.Misalnya, jika wilayah layak ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0}, maka permasalahan pemaksimalan x + y adalah suboptimal karena setiap solusi yang mungkin dapat diperbaiki dengan meningkatkan x atau y; Namun jika permasalahannya meminimalkan x + y, maka terdapat permasalahan optimal (terutama pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, serta dalam algoritma pencarian (cabang ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin dalam domain yang mungkin dari suatu masalah tertentu. Solusi kandidat tidak harus berupa solusi yang mungkin atau masuk akal terhadap suatu masalah, namun hanya solusi yang memenuhi semua batasan; yaitu, dalam serangkaian solusi yang mungkin. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering kali mereduksi himpunankemungkinan solusi menjadi subkumpulan solusi layak yang poin-poinnya tetap menjadi solusi layak, sementara solusi lain yang mungkin kemudian dikeluarkan sebagai kandidat.

Ruang semua kandidat solusi sebelum mengecualikan titik layak disebut wilayah layak, himpunan layak, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kondisi batas masalah. Kepuasan Kendala adalah proses menemukan titik-titik dalam suatu himpunan yang mungkin.

Algoritma genetika

Dalam kasus algoritma genetik thm, solusi kandidat adalah individu dalam populasi yang dikembangkan oleh algoritma.

Kalkulus

Dalam kalkulus, pencarian solusi optimal dilakukan dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan ditetapkan sama dengan nol, dan nilai apa pun dari variabel terpilih yang memenuhi persamaan ini diperlakukan sebagai kandidat solusi (sementara mereka yang tidak dikecualikan dari daftar peringkat). Solusi potensial mungkin bukan solusi aktual dalam beberapa hal. Pertama, ini mungkin merupakan titik terendah ketika bertujuan untuk mencapai titik tertinggi (atau sebaliknya), dan kedua, mungkin tidak memberikan titik terendah atau tertinggi pada, melainkan sebuah pelana atau titik balik ketika ada jeda sementara dalam pertumbuhan lokal. . Jika tidak, fungsinya akan hilang. Solusi kandidat tersebut dapat dikecualikan dengan uji turunan kedua, yang pemenuhannya cukup untuk membuat solusi kandidat setidaknya optimal secara lokal.Ketiga, solusi potensial mungkin optimal secara lokal namun tidak optimal secara global.

Dalam mengambil antiturunan dari monomial bentuk  solusi kandidat menggunakan rumus kuadratur Cavalieri adalah Kandidat solusi ini sebenarnya benar kecuali jika

Pemrograman linier

Serangkaian kendala pemrograman linier pada dua variabel menghasilkan wilayah nilai yang mungkin untuk variabel tersebut. Masalah dua variabel yang dapat diselesaikan akan memiliki wilayah layak dalam bentuk poligon sederhana cembung jika dibatasi. Dalam algoritma yang menguji titik-titik yang layak secara berurutan, setiap titik yang diuji pada gilirannya merupakan solusi kandidat.

Dalam metode simpleks penyelesaian masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; Jika ditolak sebagai titik optimal, simpul-simpul tetangga dianggap sebagai kandidat solusi berikutnya. Proses ini berlanjut hingga solusi yang diusulkan dianggap optimal.

Disadur dari: en.wikipedia.org