Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:26:48Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.26
Baris 2:		Baris 2:

	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]].		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]].
			<ref>Richard M. Karp. [http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf Complexity of Computer Computations]. New York: Plenum. 1972. hlm. 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.</ref>

			Jika beberapa variabel keputusan tidak diskrit, masalah tersebut dikenal sebagai masalah "pemrograman bilangan bulat campuran"<ref>[http://macc.mcmaster.ca/maccfiles/chachuatnotes/07-MILP-I_handout.pdf Mixed-Integer Linear Programming (MILP): Model Formulation].</ref>
	Jika beberapa variabel keputusan tidak diskrit, masalah tersebut dikenal sebagai masalah "pemrograman bilangan bulat campuran"

	== Bentuk Standar dan Kanon PLI ==		== 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 <math>\mathbf{x}</math> vektor yang akan ditentukan):<ref>C. H. Papadimitriou. ''Combinatorial optimization: algorithms and complexity''. Dover. 1998. ISBN 0486402584.</ref>
	Dalam pemrograman linear integer, ''bentuk kanon'' berbeda dari ''bentuk standart''. Sebuah program linear integer dalam bentuk kanonisnya itu diekspresikan sehingga, (diingat bahwa ini adalah <math>\mathbf{x}</math> vektor yang akan ditentukan):

	:<math> \begin{align}		:<math> \begin{align}
Baris 28:		Baris 27:

	== Contoh ==		== Contoh ==

	Plot disamping menunjukkan masalah yang ada.		Plot disamping menunjukkan masalah yang ada.

Baris 52:		Baris 50:
	\end{align}</math>		\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.		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.<ref>J. Erickson. [https://courses.engr.illinois.edu/cs498dl1/sp2015/solutions/hw10sol.pdf Integer Programming Reduction]. 2015.</ref>

	== Referensi ==		== Referensi ==
			<references />


	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pemrograman+integer&oldid=29188035 Wikipedia bahasa Indonesia], revisi 29188035 (2026-05-02T15:40:33Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pemrograman+integer&oldid=29188035 Wikipedia bahasa Indonesia], revisi 29188035 (2026-05-02T15:40:33Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188035; atribusi sumber disertakan.

2026-08-23T09:54:23Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188035; atribusi sumber disertakan.

Halaman baru

Masalah '''pemrograman integer''' adalah sebuah [[optimalisasi matematis]] atau program [[permasalahan pemenuhan kendala|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 [[fungsi linear (kalkulus)|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]].

Jika beberapa variabel keputusan tidak diskrit, masalah tersebut dikenal sebagai masalah "pemrograman bilangan bulat campuran"

== 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 <math>\mathbf{x}</math> vektor yang akan ditentukan):

:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{memaksimalkan}} && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{bergantung pada} && A \mathbf{x} \le \mathbf{b}, \\
& && \mathbf{x} \ge \mathbf{0}
\end{align} </math>

dan bentuk standar PLI adalah

:<math> \begin{align}
& \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} \ge \mathbf{0}, \\
& && \mathbf{x} \ge \mathbf{0},
\end{align} </math>

Di mana <math>\mathbf{c}\in \mathbb{R}^n, \mathbf{b} \in \mathbb{R}^m</math> adalah vektor dan <math>A \in \mathbb{R}^{m \times n}</math> adalah matriks. Dalam program linear, PLI tidak dalam bentuk standarnya bisa [[algoritma simpleks#Bentuk standar|dikonversi menjadi bentuk standar]] dengan menghilangkan [[pertidaksamaan]], mengenalkan pada variabel ''slack'' (<math>\mathbf{s}</math>) dan menggantikan variabel-variabel yang tidak dibatasi tanda dengan perbedaan dua variabel yang dibatasi tanda

== Contoh ==

Plot disamping menunjukkan masalah yang ada.

:<math> \begin{align}
\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 \ge 0
\end{align} </math>

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 <math>(1,2)</math> dan <math>(2,2)</math> yang keduanya memiliki nilai objektif 2, [[Optimisasi]] unik relaksasi adalah <math>(1.8,2.8)</math> 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 <math>G = (V,E)</math> menjadi graf yang tak berarah. Definisikan program linear sebagai berikut:

:<math> \begin{align}
\min \sum_{v \in V} y_v \\
y_v + y_u & \ge 1 && \forall u,v \in E\\
y_v & \in \mathbb{Z^{+}} && \forall v \in V
\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.

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pemrograman+integer&oldid=29188035 Wikipedia bahasa Indonesia], revisi 29188035 (2026-05-02T15:40:33Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Pemrograman integer - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188035; atribusi sumber disertakan.