Pemrograman integer
Dari Wikipedia, ensiklopedia bebas
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 linear
Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini. Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala. Tag ini diberikan pada Desember 2024. |
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. [1]
Jika beberapa variabel keputusan tidak diskrit, masalah tersebut dikenal sebagai masalah "pemrograman bilangan bulat campuran"[2]
Bentuk Standar dan Kanon PLI
Ringkasan
Perspektif
Dalam pemrograman linear integer, bentuk kanon berbeda dari bentuk standart. Sebuah program linear integer dalam bentuk kanonisnya itu diekspresikan sehingga, (diingat bahwa ini adalah vektor yang akan ditentukan):[3]
dan bentuk standar PLI adalah
Dimana adalah vektor dan adalah matriks. Dalam program linear, PLI tidak dalam bentuk standarnya bisa dikonversi menjadi bentuk standar dengan menghilangkan pertidaksamaan, mengenalkan pada variabel slack () dan menggantikan variabel-variabel yang tidak dibatasi tanda dengan perbedaan dua variabel yang dibatasi tanda
Contoh
Ringkasan
Perspektif

Plot disamping menunjukkan permasalahan yang ada.
Titik integer yang layak ditunjukkan dengan warna merah, garis putus-putus merah menunjukkan bagian cembung, yang bagian polihedron cembung terkecil yang memuat semua titik ini. Garis biru bersama dengan sumbu koordinat menentukan polihedron relaksasi LP, yang diberikan oleh pertidaksamaan tanpa kendala integralitas. Sasaran optimasi adalah untuk menggerakkan garis putus-putus hitam sejauh mungkin ke atas sambil tetap menentuh polihedron. Maka, solusi optimal dari masalah integer adalah titik dan yang keduanya memiliki nilai objektif 2, Optimisasi unik relaksasi adalah dengan nilai objektif 2.8. Jika solusi relaksasi dibulatkan ke integer terdekat, maka solusi tersebut tidak layak untuk PLI.
Bukti NP-hardness
Wikiwand - on
Seamless Wikipedia browsing. On steroids.