Wilayah yang Layak

Dipublikasikan oleh Siti Nur Rahmawati

22 Agustus 2022, 11.32

Masalah dengan lima kendala linier (berwarna biru, termasuk kendala non-negatif). Dengan tidak adanya kendala bilangan bulat, himpunan yang layak adalah seluruh wilayah yang dibatasi oleh warna biru, tetapi dengan kendala bilangan bulat itu adalah himpunan titik-titik merah. (Wikipedia)

Dalam optimasi matematis, daerah fisibel, himpunan fisibel, ruang pencarian, atau ruang solusi adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel pilihan) dari masalah optimasi yang memenuhi kendala masalah, yang berpotensi termasuk pertidaksamaan, persamaan, dan pertidaksamaan. batasan bilangan bulat. Ini adalah kumpulan kandidat solusi awal untuk masalah, sebelum kumpulan kandidat dipersempit.

Misalnya, pertimbangkan masalah meminimalkan fungsi {\displaystyle x^{2}+y^{4}} sehubungan dengan variabel x dan y,, tunduk pada{\displaystyle 1\leq x\leq 10} dan {\displaystyle 5\leq y\leq 12.\,}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 {\displaystyle x^{2}+y^{4}.}

Dalam banyak masalah, himpunan layak mencerminkan kendala bahwa satu atau lebih variabel harus non-negatif. Dalam masalah pemrograman bilangan bulat murni, himpunan layak adalah himpunan bilangan bulat (atau beberapa subset daripadanya). Dalam masalah pemrograman linier, himpunan layak adalah politop cembung: wilayah dalam ruang multidimensi yang batas-batasnya dibentuk oleh hyperplanes dan sudut-sudutnya 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 di mana ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya, dan tidak melalui sembarang titik di luar himpunan layak. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah pemrograman linier, dan mereka sangat menarik karena, jika masalah memiliki fungsi tujuan cembung yang dimaksimalkan, umumnya akan lebih mudah diselesaikan dengan adanya konveks. himpunan layak dan setiap optimum lokal juga akan menjadi optimum 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 layak dapat dibatasi atau tidak dibatasi. Sebagai contoh, himpunan fisibel yang didefinisikan oleh himpunan kendala {x ≥ 0, y ≥ 0} tidak terbatas karena di beberapa arah tidak ada batasan seberapa jauh seseorang dapat pergi dan masih berada di daerah fisibel. Sebaliknya, himpunan layak yang dibentuk oleh himpunan kendala {x ≥ 0, y ≥ 0, x + 2y ≤ 4} dibatasi karena luasnya pergerakan ke segala arah dibatasi oleh kendala.

Dalam masalah pemrograman linier dengan n variabel, kondisi yang diperlukan tetapi tidak mencukupi untuk himpunan layak untuk dibatasi adalah bahwa jumlah kendala paling sedikit n + 1 (seperti yang diilustrasikan oleh contoh di atas).

Jika himpunan layak tidak terbatas, mungkin ada atau mungkin tidak optimal, tergantung pada spesifikasi fungsi tujuan. Sebagai contoh, jika daerah fisibel didefinisikan oleh himpunan kendala {x ≥ 0, y ≥ 0}, maka masalah memaksimalkan x + y tidak optimal karena setiap kandidat solusi dapat ditingkatkan dengan meningkatkan x atau y; namun jika masalahnya adalah untuk meminimalkan x + y, maka ada optimum (khususnya pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, dan dalam algoritma pencarian (topik dalam ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin di wilayah yang layak dari masalah yang diberikan. Solusi kandidat tidak harus menjadi solusi yang mungkin atau masuk akal untuk masalah—hanya dalam himpunan yang memenuhi semua kendala; yaitu, dalam himpunan solusi yang layak. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering mempersempit himpunan solusi kandidat ke subset dari solusi layak, yang poinnya tetap sebagai solusi kandidat sementara solusi layak lainnya selanjutnya dikeluarkan sebagai kandidat.

Ruang dari semua solusi kandidat, sebelum titik fisibel dikeluarkan, disebut daerah fisibel, himpunan fisibel, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kendala masalah. Kepuasan kendala adalah proses menemukan titik dalam himpunan yang layak.

Algoritma genetika

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

Kalkulus

Dalam kalkulus, solusi optimal dicari dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan disamakan dengan nol, dan setiap nilai dari variabel pilihan yang memenuhi persamaan ini dipandang sebagai solusi kandidat (sementara yang tidak dikesampingkan sebagai calon). Ada beberapa cara di mana solusi kandidat mungkin bukan solusi yang sebenarnya. Pertama, mungkin memberikan minimum ketika maksimum sedang dicari (atau sebaliknya), dan kedua, mungkin tidak memberikan minimum atau maksimum melainkan titik pelana atau titik belok, di mana jeda sementara dalam kenaikan lokal. atau jatuhnya fungsi terjadi. Solusi kandidat tersebut mungkin dapat dikesampingkan dengan menggunakan uji turunan kedua, yang kepuasannya cukup untuk solusi kandidat setidaknya optimal secara lokal. Ketiga, solusi kandidat mungkin optimum lokal tetapi bukan optimum global.

Dalam mengambil antiturunan dari monomial bentuk x^{n}, solusi kandidat menggunakan rumus kuadratur Cavalieri adalah {\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.} Kandidat solusi ini sebenarnya benar kecuali jika {\displaystyle n=-1.}

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 untuk menyelesaikan masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; jika ditolak sebagai optimal, simpul yang berdekatan dianggap sebagai kandidat solusi berikutnya. Proses ini dilanjutkan sampai solusi kandidat ditemukan menjadi yang optimal.

 

Sumber Artikel: en.wikipedia.org