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

2026-08-24T22:57:07Z

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

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

2026-08-24T22:19:13Z

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

Halaman baru

'''Program linear''' atau '''pemrograman linear''' adalah metode untuk memperoleh hasil optimal dari suatu [[model matematika]] yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika (juga dikenal dengan [[Optimisasi (matematika)|optimisasi matematika]]).

Secara lebih formal, program linear adalah sebuah teknik [[optimisasi]] untuk [[Fungsi kerugian|fungsi objektif]] [[linear]], dengan kendala (beberapa) [[persamaan linear]] dan [[pertidaksamaan]] linear. [[Ruang feasibel|Daerah feasibel]] dari kendala berupa sebuah [[Politop cembung|politop konveks]], yakni sebuah [[Himpunan (matematika)|himpunan]] yang didefinisikan dari perpotongan banyak (namun terhingga) ''half spaces''. Sedangkan fungsi objektif berupa fungsi (linear) bernilai [[Bilangan riil|real]] yang terdefinisi pada politop tersebut. Sebuah [[algoritme]] program linear akan mencari sebuah titik pada politop, yang menyebabkan fungsi objektif akan menghasilkan nilai terkecil (atau terbesar); jika titik tersebut ada.

Program linear adalah masalah yang dapat dinyatakan dalam [[Bentuk kanonik|bentuk kanonik (baku)]] sebagai

<math> \begin{align}
& \text{Cari sebuah vektor} && \mathbf{x} \\
& \text{yang memaksimumkan} && \mathbf{c}^T \mathbf{x}\\
& \text{dengan kendala} && A \mathbf{x} \leq \mathbf{b} \\
& \text{dan} && \mathbf{x} \ge \mathbf{0}.
\end{align} </math>

Disini, komponen-komponen dari <math>\mathbf{x}</math> adalah variabel yang ingin ditentukan nilainya. Vektor <math>\mathbf{c}</math> adalah vektor koefisien fungsi objektif, sedangkan <math>\mathbf{b}</math> adalah vektor nilai kunci. [[Fungsi kerugian|Fungsi objektif]] adalah fungsi yang nilainya ingin dimaksimumkan atau diminimumkan, dalam kasus ini berupa fungsi <math>\mathbf x\mapsto\mathbf{c}^T\mathbf{x}</math>. Matriks <math>\mathbf{A}</math> berisi koefisien-koefisien dari persamaan (dan pertidaksamaan) kendala-kendala. Pertidaksamaan <math>\mathbf{A}\mathbf{x} \leq \mathbf{b}</math> dan <math>\mathbf{x} \geq \mathbf{0}</math> menyatakan daerah pencarian titik untuk mengoptimisasi fungsi objektif. Dalam konteks ini, dua vektor dapat dibandingkan jika keduanya memiliki dimensi yang sama. Vektor <math>\mathbf{x}</math> dikatakan lebih kecil atau sama dengan vektor <math>\mathbf{y}</math>, jika semua nilai komponen vektor <math>\mathbf{x}</math> lebih kecil atau sama dengan nilai komponen <math>\mathbf{y}</math> yang bersesuaian.

Program linear dapat diterapkan dalam berbagai bidang studi. metode ini digunakan secara luas di bidang [[matematika]] dan secara khusus di bidang bisnis, [[ekonomi]], dan [[teknologi]]. Banyak bidang industri juga menerapkan program linear, seperti [[transportasi]], pengelolaan energi, telekomunikasi, dan [[manufaktur]]. Program ini terbukti berguna dalam memecahkan masalah perencanaan, penjadwalan, dan desain.

== Sejarah ==

Masalah menyelesaikan sebuah sistem pertidaksamaan linear dapat dilacak ke [[Joseph Fourier|Fourier]], yang pada tahun 1827 menerbitkan sebuah metode untuk menemukan solusinya. Metode ini selanjutnya diberi nama [[eliminasi Fourier-Motzkin]].

Pada tahun 1939, seorang [[matematikawan]] dan [[ekonom]] [[Uni Soviet]], [[Leonid Kantorovich]], membuat formulasi program linear dari masalah yang serupa dengan formulasi masalah program saat ini. Ia juga mengusulkan sebuah metode untuk menyelesaikannya. Formulasi ini ia kembangkan pada masa [[Perang Dunia II]], untuk merencanakan pengeluaran dan pendapatan agar mengurangi rugi bagi tentara dan meningkatkan kerugian bagi musuh. Karya Kantorovich awalnya dihiraukan oleh [[USSR]]. Pada saat yang sama dengan Kantorovich, ekonom Amerika-Belanda [[Tjalling Koopmans|T. C. Koopmans]] memformulasikan masa [[ekonomi klasik]] dalam bentuk program linear. Kantorovich dan Koopmans nantinya mendapatkan [[Penghargaan Nobel Ekonomi|penghargaan Nobel bidang ekonomi]] tahun 1975. Pada tahun 1941, [[Frank Lauren Hitchcock]] juga memformulasikan masalah transportasi dalam bentuk program linear, dan memberikan solusi yang sangat mirip dengan [[metode simpleks]]. Hitchcock meninggal pada tahun 1957 dan penghargaan Nobel tidak diberikan secara anumerta.

Sepanjang tahun 1946–1947, [[George Dantzig|George B. Dantzig]] secara independen mengembangkan formulasi program linear yang umum agar dapat digunakan dalam masalah perencanaan di [[Angkatan Udara Amerika Serikat|Angkata Udara Amerika Serikat]]. Di tahun 1947, juga menemukan [[metode simpleks]] yang untuk pertama kalinya menyelesaikan banyak masalah program linear secara efisien. Ketika Dantzig melakukan pertemuan dengan [[John von Neumann]] untuk mendiskusikan metode simpleksnya, Neumann langsung memberikan [[konjektur]] tentang teori tentang dualitas; dari realisasinya bahwa ini ekuivalen dengan masalah yang ia kerjakan di bidang [[Game theory|teori permainan]]. Dantzig memberikan bukti formal pada sebuah laporan yang tidak dipublikasikan, "''A Theorem on Linear Inequalities''" pada 5 Januari 1948. Karya Dantzig dipublikasikan ke publik pada tahun 1951. Dalam masa setelah perang, banyak industri yang menerapkan metodenya dalam masalah perencanaan harian mereka.

Contoh masalah yang diberikan Dantzig adalah menemukan penugasan 70 orang ke 70 pekerjaan. Daya komputasi untuk mengecek semua permutasi kemungkinan penugasan sangat besar, melebihi banyaknya partikel yang ada di [[Alam semesta teramati|alam semesta yang teramati]]. Namun, butuh waktu yang singkat untuk menemukan solusi ketika masalah disusun sebagai program linear dan menerapkan [[Metode simpleks|algoritme simpleks]]. Teori yang mendasari program linear secara drastis mengurangi banyaknya kemungkinan solusi yang perlu dicek.

Masalah program linear dibuktikan dapat diselesaikan dalam waktu [[polinomial]] oleh [[Leonid Khachiyan]] pada tahun 1979. Namun baru pada tahun 1984 terobosan besar di bidang teori dan praktik terjadi, ketika [[Narendra Karmarkar]] memperkenalkan metode ''interior-point'' untuk menyelesaikan masalah program linear.

== Bentuk baku ==
''Bentuk baku'' atau ''bentuk standar'' dari program linear adalah bentuk yang umum dan paling yang mudah dipahami untuk menjelaskan permasalahan program linear. Bentuk ini terdiri dari tiga bagian:
* Sebuah fungsi tujuan yang ingin dimaksimumkan, sebagai contoh <math>f(x_1, x_2, \dots, x_n) = c_1x_1 + c_2x_2 + \dots + c_nx_n</math>
*Batasan atau kendala dari permasalahan, dinyatakan dalam bentuk<math display="block">\begin{aligned}
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &\leq b_1 \\
a_{21}x_1 + a_{22}x_2 + \dots + a_{1n}x_n &\leq b_2 \\
\vdots\quad& \\
a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &\leq b_m
\end{aligned}</math>

* dan variabel-variabel bernilai nonnegatif <math>x_1, x_2, \dots, x_n \geq 0
</math>

Bentuk ini juga bisa ditulis dalam ''bentuk matriks,'' atau secara lebih ringkas sebagai<math display="inline">\text{max}\;\{\mathbf{c}^T\mathbf{x} \;|\; \mathbf{x} \in \mathbb{R}^n \land \mathbf{Ax} \leq \mathbf{b} \land \mathbf{x} \geq 0\}</math>Formulasi lainnya, seperti masalah minimisasi, masalah dengan pertidaksamaan melibatkan operator <math>\geq</math>, juga masalah melibatkan variabel yang dapat bernilai negatif, selalu dapat disusun menjadi bentuk baku.

=== Contoh ===
Misalkan seorang petani memiliki sepetak lahan, anggap <math>L</math> km2, dan ingin mendapatkan untung dengan menanam singkong dan jagung. Petani memiliki jumlah pupuk dan [[pestisida]] yang terbatas, masing-masing sebanyak <math>U</math> dan <math>E</math> kilogram. Satu km2 tanaman singkong memerlukan <math>U_1</math> kg pupuk dan <math>E_1</math> kg pestisida, sedangkan satu km2 tanaman jagung <math>U_2</math> kg pupuk dan <math>E_2</math> kg pestisida. Dengan sedikit perhitungan, petani tersebut menemukan harga jual singkong per km2 sebesar <math>J_1</math> rupiah, sedangkan <math>J_2</math>rupiah adalah harga jual jagung per km2. Anggap <math>x_1</math> dan <math>x_2</math> secara berurutan adalah luas lahan yang ditanami singkong dan jagung. Keuntungan yang maksimum dapat diperoleh petani dengan memilih nilai yang optimal bagi <math>x_1</math> dan <math>x_2</math>. Menyatakan permasalahan tersebut dalam bentuk baku, kita mendapatkan program linear:

Masalah tersebut dapat disusun dalam bentuk matriks sebagai:
: maksimumkan <math>\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} </math>
: dengan kendala <math>\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. </math>

== Bentuk imbuhan ==
Program linear juga dapat dinyatakan dalam bentuk imbuhan (''augmented form, slacks form'') agar dapat diselesaikan dengan [[metode simpleks]]. Bentuk ini menggunakan variabel-variabel nonnegatif yang disebut lempai (''slack'') untuk mengubah bentuk-bentuk pertidaksamaan dalam kendala menjadi bentuk persamaan. Selanjutnya permasalahan dapat ditulis ulang dalam bentuk matriks sebagai:
: Maksimumkan <math>z</math>
:Dengan kendala<math>
\begin{bmatrix}
1 & -\mathbf{c}^T & 0 \\
0 & \mathbf{A} & \mathbf{I}
\end{bmatrix}
\begin{bmatrix}
z \\ \mathbf{x} \\ \mathbf{s}
\end{bmatrix} =
\begin{bmatrix}
0 \\ \mathbf{b}
\end{bmatrix}
</math>

Disini, <math>\mathbf{s}</math> adalah vektor berisi variabel-variabel lempai (<math>\mathbf{s} \ge 0</math>), dan <math>\mathbf{x}</math> adalah vektor keputusan. Variabel <math>z</math> 'menyimpan' nilai dari fungsi objektif yang ingin dioptimalkan.

=== Contoh ===
Menggunakan contoh permasalahan petani di atas, bentuk imbuhan ditulis sebagai

:
Dalam bentuk ini, <math>x_3, x_4, x_5</math> merupakan variabel-variabel lempai, yang secara berurutan menyatakan luas lahan yang tidak digunakan, banyak pupuk yang tersisa, dan banyak pestisida yang tersisa (atau tidak digunakan). Dalam bentuk matriks formulasi tersebut dinyatakan sebagai:
: maksimumkan <math>z</math>:
: <math>
\begin{bmatrix}
1 & -S_1 & -S_2 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 \\
0 & F_1 & F_2 & 0 & 1 & 0 \\
0 & P_1 & P_2 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5
\end{bmatrix} =
\begin{bmatrix}
0 \\ L \\ F \\ P
\end{bmatrix}, \,
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5
\end{bmatrix} \ge 0.
</math>

== Contoh kasus sederhana ==
Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan [[metode simpleks]]. Karena batasan visualisasi, metode grafik hanya dapat digunakan untuk menyelesaikan program linear dengan dua atau tiga variabel. Metode simpleks dapat digunakan tanpa memiliki batasan jumlah variabel, tetapi lebih rumit daripada metode grafik. Dalam bagian ini, akan dibahas cara [[penyelesaian masalah]] program linear dua variabel dengan menggunakan metode grafik. Berikut sebuah masalah memaksimumkan keuntungan:

<blockquote>Seorang pemilik tanah mengubah lahan seluas 150 m2 yang dia miliki menjadi tempat parkir. Melihat keadaan ekonomi di daerahnya, ia menetapkan harga parkir untuk mobil sebesar Rp. 3000 dan harga parkir untuk motor sebesar Rp. 2000. Dari pengukuran didapatkan bahwa satu motor memerlukan 1 m2 petak tanah, sedangkan satu mobil memerlukan 3 m2. Malangnya, desain dari tempat parkir hanya memungkinkan untuk menampung maksimum 100 kendaraan. Setelah beberapa bulan, pemilik tanah memerlukan data keuntungan maksimum yang mungkin ia diperoleh, sebagai salah satu pertimbangannya untuk memperbaiki desain tempat parkir tersebut. </blockquote>

Secara umum, terdapat beberapa tahapan dalam menyelesaikan sebuah program linear, yakni: menentukan variabel-variabel keputusan dari masalah, dan dilanjutkan dengan membuat fungsi objektif. Setelah itu setiap kendala/batasan perlu diformulasikan dalam bentuk persamaan atau pertidaksamaan. Tahap berikutnya adalah menentukan/mengecek daerah penyelesaian, karena sedikit banyak hal ini akan berpengaruh pada [[algoritma pencarian]] solusi yang perlu digunakan. Masalah program linear dianggap terselesaikan, ketika titik optimal sudah ditemukan (dan sudah dapat diartikan/dimaknai). Untuk permasalahan di atas, kita dapat menyusun program linear berikut:
* Mencari maksimum dari <math>f(x, y) = 3.000x + 2.000y</math> (keuntungan parkir dalam rupiah)
* dengan kendala:
*# <math>x + y \le 100</math> (batas jumlah kendaraan)
*# <math>3x + y \le 150</math> (batas luas kendaraan dalam m2)
*# <math>x \ge 0</math> (jumlah tidak boleh negatif)
*# <math>y \ge 0</math> (jumlah tidak boleh negatif)
dengan <math>x</math> dan <math>y</math> masing-masing menyatakan banyak mobil dan motor yang terparkir.

Pada metode grafik, kita membentuk persamaan garis dari setiap kendala program linear. Hal ini dilakukan dengan mengubah setiap pertidaksamaan menjadi bentuk persamaan. Sebagai contoh, persamaan garis dari kendala <math>3x + y \le 150</math> adalah <math>3x + y = 150</math>. Selanjutnya, kita mencatat setiap titik yang terbentuk dari semua perpotongan dua persamaan garis yang mungkin. Tabel berikut berisi titik perpotongan dari persamaan garis pada kolom dengan persamaan garis pada baris.
Titik-titik perpotongan yang memenuhi semua kendala (berwarna hijau pada tabel) adalah solusi feasibel (yang mungkin) dari permasalahan program linear. Langkah berikutnya yang perlu dilakukan adalah menghitung fungsi objektif <math>f(x, y) = 3.000x + 2.000y</math> pada keempat titik tersebut.
Dari tabel di atas, terlihat bahwa keuntungan maksimum yang dapat diperoleh adalah Rp 225.000. Hal ini tercapai ketika tempat parkir terisi dengan 25 mobil dan 75 motor.

== Dualitas ==
Setiap masalah program linear, yang juga dikenal dengan masalah ''primal'', dapat diubah menjadi sebuah masalah ''dual''. Masalah dual juga merupakan sebuah program linear, dan solusi masalah ini memberikan sebuah batas atas untuk nilai optimal dari masalah primal. Untuk mendapatkan dual dari masalah primal, ada cara sistematis yang perlu dilakukan:

* Setiap variabel pada program linear primal akan menjadi kendala di program linear dual.
* Setiap konstrain pada program linear primal akan menjadi konstrain di program linear dual.
* Arah fungsi objektif akan berbalik—masalah memaksimumkan di primal akan menjadi masalah meminimumkan di dual, dan sebaliknya.

Dalam bentuk matriks, hubungan masalah primal dengan masalah dual dapat ditunjukkan dengan:

* Maksimumkan <math>\mathbf{c}^\text{T}\mathbf{x}</math> dengan kendala <math>\mathbf{A}\mathbf{x} \leq \mathbf{b}</math> dan <math>\mathbf{x} \geq \mathbf{0}</math>; akan memiliki masalah dual ''simetrik'' Minimimumkan <math>\mathbf{b}^\text{T}\mathbf{y}</math> dengan kendala <math>\mathbf{A}^\text{T}\mathbf{y} \geq \mathbf{c}</math> dan <math>\mathbf{y} \geq \mathbf{0}</math>.
* Maksimumkan <math>\mathbf{c}^\text{T}\mathbf{x}</math> dengan kendala <math>\mathbf{A}\mathbf{x} \leq \mathbf{b}</math>; akan memiliki masalah dual ''asimetrik'' Minimumkan <math>\mathbf{b}^\text{T}\mathbf{y}</math> dengan kendala <math>\mathbf{A}^\text{T}\mathbf{y} = \mathbf{c}</math> dan <math>\mathbf{y} \geq \mathbf{0}</math>.

Ada dua ide mendasar pada teori dualitas. Ide pertama adalah fakta bahwa (untuk kasus dual simetrik) dual dari masalah dual suatu program linear, adalah masalah primal asal dari program linear tersebut. Selain itu, setiap solusi feasibel dari program linear akan memberikan batas untuk nilai optimal dari fungsi objektif masalah dualnya. Teorema dualitas lemah menyatakan bahwa nilai fungsi objektif dari masalah dual pada setiap solusi feasibel, akan memberikan batas pada nilai fungsi objektif masalah primal pada setiap solusi feasibelnya. Jenis batas (batas atas atau batas bawah) yang terjadi bergantung pada jenis optimisasi yang dikerjakan (memaksimumkan atau meminimumkan). Teorema dualitas kuat menyatakan jika masalah primal memiliki sebuah solusi optimal <math>\mathbf{x}^*</math>, maka masalah dual juga memiliki sebuah solusi optimal <math>\mathbf{y}^*</math>, dan keduanya terikat oleh hubungan <math>\mathbf{c}^\text{T}\mathbf{x}^* = \mathbf{b}^\text{T}\mathbf{y}^*</math>.

Bentuk kendala dari program linear juga dapat tidak terbatas (''unbounded'') atau tidak feasibel (''infeasible''). Teorema dualitas lemah menunjukkan bahwa jika masalah primal tidak terbatas maka masalah dual yang terbentuk akan tidak feasibel. Dan sebaliknya, jika masalah dual tidak terbatas maka masalah primalnya akan tidak feasibel. Namun, ada kasus kedua jenis masalah (primal dan dual) adalah masalah yang tidak feasibel.

=== Dualitas masalah pengepakan dan penutupan ===
Masalah pengepakan (''packing'') adalah kelas masalah optimisasi yang mencari cara menyusun (mengepak) objek-objek ke dalam sebuah kontainer. Sedangkan, masalah penutupan (''covering'') membahas apakah suatu kombinasi struktur "menutupi" sebuah objek, atau seberapa besar ukuran struktur yang diperlukan agar dapat melakukan hal tersebut. Masalah program linear terkait pengepakan dan penutupan sering muncul sebagai "relaksasi" dari sebuah masalah kombinatorial.

Masalah program linear penutupan memiliki bentuk:
: Minimumkan: <math>\mathbf{b}^\text{T}\mathbf{y}</math>,
: dengan kendala: <math>\mathbf{A}^\text{T}\mathbf{y} \geq \mathbf{c}</math>, <math>\mathbf{y} \geq \mathbf{0}</math>
Dual dari masalah ini masalah program linear pengepakan, yang memiliki bentuk:
: Maksimumkan: <math>\mathbf{c}^\text{T}\mathbf{x}</math>,
: dengan kendala: <math>\mathbf{A}\mathbf{x} \leq \mathbf{b}</math>, <math>\mathbf{x} \geq \mathbf{0}</math>.
Dalam kedua jenis permasalahan ini, matriks <math>\mathbf{A}</math>, vektor <math>\mathbf{b}</math>, dan vektor <math>\mathbf{c}</math>, bernilai nonnegatif.

=== Complementary slackness ===
Solusi optimal dari dual dapat didapatkan hanya dengan mengetahui solusi optimal dari masalah primal, dengan menggunakan teorema ''complementary slackness''. Teorema ini menyatakan:

Misalkan <math>\mathbf{x} = (x_1, x_2, \dots, x_n)</math> adalah solusi feasibel di masalah primal, dan <math>\mathbf{y} = (y_1, y_2, \dots, y_m)</math> adalah solusi feasibel di masalah dual. Misalkan pula <math>\mathbf{w} = (w_1, w_2, \dots, w_m)</math> adalah variabel lempai (''slack'') di masalah primal, dan <math>\mathbf{z} = (z_1, z_2, \dots, z_n)</math> adalah variabel lempai di masalah dual. Vektor <math>\mathbf{x}</math> dan <math>\mathbf{y}</math> optimal di jenis masalah mereka masing masing, [[jika dan hanya jika]]:

* <math>x_j z_j = 0</math> untuk <math>j = 1,2,\dots, n</math>, dan
* <math>w_i y_i = 0</math> untuk <math>i = 1,2,\dots, m</math>.

Jadi, jika variabel lempai ke-''i'' dari masalah primal tidak bernilai nol, maka variabel keputusan ke-''i'' dari masalah dual akan bernilai nol; dan sebaliknya.
== Referensi ==

== Bacaan lebih lanjut ==
*
*
*
*

== Pranala luar ==

* [http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html Guidance On Formulating LP Problems]
* [http://glossary.computing.society.informs.org/ Mathematical Programming Glossary]
* [http://lpsolve.sourceforge.net/4.0/LinearProgrammingFAQ.htm The Linear Programming FAQ]
* [http://plato.asu.edu/bench.html Benchmarks For Optimisation Software]

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Program+linear&oldid=29578443 Wikipedia bahasa Indonesia], revisi 29578443 (2026-08-14T18:41:12Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Program linear - Riwayat revisi

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

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