Pemrograman integer

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. (Desember 2024)

Optimalisasi permasalahan matematis yang terikat pada integerTemplat:SHORTDESC:Optimalisasi permasalahan matematis yang terikat pada integer

Masalah pemrograman integer adalah sebuah optimalisasi matematis atau program kelayakan yang di mana beberapa atau seluruh variabel terikat menjadi integer. Dalam banyak konteks, istilah ini merujuk pada "pemrograman linier integer" (PLI), di mana fungsi objektif dan ikatan (selain ikatan integer) adalah linear

Pemrograman integer adalah NP-lengkap. Secara khusus, kasus khusus dari pemrograman linear integer 0-1, di mana 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

Dalam pemrograman linear integer, bentuk kanon berbeda dari bentuk standart. Sebuah program linear integer dalam bentuk kanonisnya itu diekspresikan sehingga, (diingat bahwa ini adalah x {\displaystyle \mathbf {x} } $\mathbf {x}$ vektor yang akan ditentukan):^[3]

memaksimalkan x ∈ Z n c T x bergantung pada A x ≤ b , x ≥ 0 {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{memaksimalkan}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{bergantung pada}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}} ${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{memaksimalkan}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{bergantung pada}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

dan bentuk standar PLI adalah

maximize x ∈ Z n c T x subject to A x + s = b , s ≥ 0 , x ≥ 0 , {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}} ${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}$

Di mana c ∈ R n , b ∈ R m {\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}} $\mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}$ adalah vektor dan A ∈ R m × n {\displaystyle A\in \mathbb {R} ^{m\times n}} $A\in \mathbb {R} ^{m\times n}$ adalah matriks. Dalam program linear, PLI tidak dalam bentuk standarnya bisa dikonversi menjadi bentuk standar dengan menghilangkan pertidaksamaan, mengenalkan pada variabel slack ( s {\displaystyle \mathbf {s} } $\mathbf {s}$ ) dan menggantikan variabel-variabel yang tidak dibatasi tanda dengan perbedaan dua variabel yang dibatasi tanda

Contoh

Plot disamping menunjukkan masalah yang ada.

memaksimalkan x , y ∈ Z y bergantung pada − x + y ≤ 1 3 x + 2 y ≤ 12 2 x + 3 y ≤ 12 x , y ≥ 0 {\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{memaksimalkan}}}\quad &y\\{\text{bergantung pada}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}} ${\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{memaksimalkan}}}\quad &y\\{\text{bergantung pada}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}$

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 ( 1 , 2 ) {\displaystyle (1,2)} $(1,2)$ dan ( 2 , 2 ) {\displaystyle (2,2)} $(2,2)$ yang keduanya memiliki nilai objektif 2, Optimisasi unik relaksasi adalah ( 1.8 , 2.8 ) {\displaystyle (1.8,2.8)} $(1.8,2.8)$ dengan nilai objektif 2.8. Jika solusi relaksasi dibulatkan ke integer terdekat, maka solusi tersebut tidak layak untuk PLI.

Bukti NP-hardness

Berikut ini adalah pengurangan dari penutup vorteks minimum ke pemrograman integer yang akan berfungsi sebagai bukti kesulitan NP.

Jadikan G = ( V , E ) {\displaystyle G=(V,E)} $G=(V,E)$ menjadi graf yang tak berarah. Definisikan program linear sebagai berikut:

min ∑ v ∈ V y v y v + y u ≥ 1 ∀ u , v ∈ E y v ∈ Z + ∀ v ∈ V {\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}} ${\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}$

Mengingat batasan tersebut membatasi y v {\displaystyle y_{v}} $y_{v}$ 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, y v {\displaystyle y_{v}} $y_{v}$ bisa menjadi bagian menjadi 1 untuk tiap v ∈ C {\displaystyle v\in C} $v\in C$ dan menjadi 0 untuk setiap v ∉ C {\displaystyle v\not \in C} $v\not \in C$ . Sehingga memberi solusi yang layak untuk program integer. Dengan demikian, maka dapat disimpulkan bahwa jika kita meminimalkan jumlah y v {\displaystyle y_{v}} $y_{v}$ , kita juga telah menemukan penutup titik sudut minimum.^[4]

Referensi

↑ Karp, Richard M. (1972). "Reducibility among Combinatorial Problems" (PDF). Dalam R. E. Miller; J. W. Thatcher; J.D. Bohlinger (ed.). Complexity of Computer Computations. New York: Plenum. hlm. 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.{{cite book}}: Pemeliharaan CS1: Lokasi penerbit (link)
↑ "Mixed-Integer Linear Programming (MILP): Model Formulation" (PDF). Diakses tanggal 16 April 2018.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Papadimitriou, C. H.; Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Mineola, NY: Dover. ISBN 0486402584.
↑ Erickson, J. (2015). "Integer Programming Reduction" (PDF). Diarsipkan dari asli (PDF) tanggal 18 Mei 2015.{{cite web}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)

Artikel ini tidak memiliki konten kategori. Bantulah dengan menambah kategori yang sesuai sehingga artikel ini terkategori dengan artikel lain yang sejenis.