Pemrograman integer: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
←Membuat halaman berisi '{{Short description|Optimalisasi permasalahan matematis yang terikat pada integer}} Permasalahan '''pemrograman integer''' adalah sebuah optimalisasi matematis atau program kelayakan yang dimana beberapa atau seluruh variabel terikat menjadi integer. Dalam banyak konteks, istilah ini merujuk pada "pemrograman linier integer" (PLI), dimana fungsi objektif dan ikatan (selain ikatan integer) adalah fungsi linear...' Tag: |
|||
| (2 revisi perantara oleh 2 pengguna tidak ditampilkan) | |||
Baris 1:
{{Orphan|date=Desember 2024}}
{{Short description|Optimalisasi permasalahan matematis yang terikat pada integer}}
Permasalahan '''pemrograman integer''' adalah sebuah [[optimalisasi matematis]] atau program [[permasalahan pemenuhan kendala
Pemrograman integer adalah [[NP-lengkap]]. Secara khusus, kasus khusus dari pemrograman linear integer 0-1, dimana variabel yang tak diketahui adalah biner, dan hanya pembatasan yang harus dipenuhi adalah salah satu dari [[21 masalah NP-lengkap Karp]].
Baris 65 ⟶ 67:
\end{align}</math>
Mengingat batasan tersebut membatasi <math>y_v</math> menjadi 0 atau 1, setiap solusi yang layak untuk program integer adalah bagian dari simpul. Batasan pertama menyiratkan bahwa setidaknya satu titik akhir dari setiap sisi disertakan dalam bagian ini. Oleh karena itu, slusi tersebut menggambarkan penutup simpul. Selain itu, mengingat beberapa penutup simpul C, <math>y_v</math> bisa menjadi bagian menjadi 1 untuk tiap <math>v\in C</math> dan menjadi 0 untuk setiap <math>v\not\in C</math>. Sehingga memberi solusi yang layak untuk program integer. Dengan demikian, maka dapat disimpulkan bahwa jika kita meminimalkan jumlah <math>y_v</math>, kita juga telah menemukan penutup titik sudut minimum.
{{Uncategorized|date=Desember 2024}}
[[Kategori:Algoritme kombinatorial]]
[[Kategori:Permasalahan komputasi]]
| |||