Apa yang dimaksud dengan fungsi tujuan pada program linier

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).

Table of Contents Show

Dualitas masalah pengepakan dan penutupan
Complementary slackness
Video yang berhubungan

Representasi visual dari sebuah program linear sederhana dengan dua variabel dan enam pertidaksamaan. Himpunan solusi feasibel digambarkan oleh poligon (politop dalam dimensi-2) dengan isi berwarna kuning. Fungsi objektif linear ditandai oleh garis merah dan anak panah: Garis merah menandakan nilai dari fungsi objektif, sedangkan anak panah menandakan arah optimisasi yang diinginkan.

Pada masalah optimisasi dengan tiga variabel, daerah feasibel yang tertutup akan membentuk sebuah polihedron konveks. Program linear bertujuan untuk mencari titik di polihedron yang menghasilkan nilai fungsi objektif tertinggi (atau terendah).

Secara lebih formal, program linear adalah sebuah teknik optimisasi untuk fungsi objektif linear, dengan kendala (beberapa) persamaan linear dan pertidaksamaan linear. Daerah feasibel dari kendala berupa sebuah politop konveks, yakni sebuah himpunan yang didefinisikan dari perpotongan banyak (namun terhingga) half spaces. Sedangkan fungsi objektif berupa fungsi (linear) bernilai 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 (baku) sebagai

$Cari sebuah vektor x yang memaksimumkan c T x dengan kendala A x ≤ b dan x ≥ 0 . {\displaystyle {\begin{aligned}&{\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} \geq \mathbf {0} .\end{aligned}}}$

Disini, komponen-komponen dari $x {\displaystyle \mathbf {x} }$ adalah variabel yang ingin ditentukan nilainya. Vektor $c {\displaystyle \mathbf {c} }$ adalah vektor koefisien fungsi objektif, sedangkan $b {\displaystyle \mathbf {b} }$ adalah vektor nilai kunci. Fungsi objektif adalah fungsi yang nilainya ingin dimaksimumkan atau diminimumkan, dalam kasus ini berupa fungsi $x ↦ c T x {\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }$

. Matriks

A {\displaystyle \mathbf {A} }

berisi koefisien-koefisien dari persamaan (dan pertidaksamaan) kendala-kendala. Pertidaksamaan

A x ≤ b {\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }

dan

x ≥ 0 {\displaystyle \mathbf {x} \geq \mathbf {0} }

menyatakan daerah pencarian titik untuk mengoptimisasi fungsi objektif. Dalam konteks ini, dua vektor dapat dibandingkan jika keduanya memiliki dimensi yang sama. Vektor

x {\displaystyle \mathbf {x} }

dikatakan lebih kecil atau sama dengan vektor

y {\displaystyle \mathbf {y} }

, jika semua nilai komponen vektor

x {\displaystyle \mathbf {x} }

lebih kecil atau sama dengan nilai komponen

y {\displaystyle \mathbf {y} }

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.

Leonid Kantorovich

John von Neumann

Masalah menyelesaikan sebuah sistem pertidaksamaan linear dapat dilacak ke Fourier, yang pada tahun 1827 menerbitkan sebuah metode untuk menemukan solusinya.[1] 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.[2] Formulasi ini ia kembangkan pada masa Perang Dunia II, untuk merencanakan pengeluaran dan pendapatan agar mengurangi rugi bagi tentara dan meningkatkan kerugian bagi musuh.[butuh rujukan] Karya Kantorovich awalnya dihiraukan oleh USSR.[3] Pada saat yang sama dengan Kantorovich, ekonom Amerika-Belanda T. C. Koopmans memformulasikan masa ekonomi klasik dalam bentuk program linear. Kantorovich dan Koopmans nantinya mendapatkan penghargaan Nobel bidang ekonomi tahun 1975.[1] Pada tahun 1941, Frank Lauren Hitchcock juga memformulasikan masalah transportasi dalam bentuk program linear, dan memberikan solusi yang sangat mirip dengan metode simpleks.[2] Hitchcock meninggal pada tahun 1957 dan penghargaan Nobel tidak diberikan secara anumerta.

Sepanjang tahun 1946–1947, George B. Dantzig secara independen mengembangkan formulasi program linear yang umum agar dapat digunakan dalam masalah perencanaan di Angkata Udara Amerika Serikat.[4] Di tahun 1947, juga menemukan metode simpleks yang untuk pertama kalinya menyelesaikan banyak masalah program linear secara efisien.[4] 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 teori permainan.[4] Dantzig memberikan bukti formal pada sebuah laporan yang tidak dipublikasikan, "A Theorem on Linear Inequalities" pada 5 Januari 1948.[3] 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 yang teramati. Namun, butuh waktu yang singkat untuk menemukan solusi ketika masalah disusun sebagai program linear dan menerapkan 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.[5] Namun baru pada tahun 1984 terobosan besar di bidang teori dan praktek terjadi, ketika Narendra Karmarkar memperkenalkan metode interior-point untuk menyelesaikan masalah program linear.[6]

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 $f ( x 1 , x 2 , … , x n ) = c 1 x 1 + c 2 x 2 + ⋯ + c n x n {\displaystyle f(x_{1},x_{2},\dots ,x_{n})=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}}$
Batasan atau kendala dari permasalahan, dinyatakan dalam bentuk
a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ≤ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 1 n x n ≤ b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ≤ b m {\displaystyle {\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}}}

dan variabel-variabel bernilai nonnegatif $x 1 , x 2 , … , x n ≥ 0 {\displaystyle x_{1},x_{2},\dots ,x_{n}\geq 0}$

Bentuk ini juga bisa ditulis dalam bentuk matriks, atau secara lebih ringkas sebagai $max { c T x | x ∈ R n ∧ A x ≤ b ∧ x ≥ 0 } {\textstyle {\text{max}}\;\{\mathbf {c} ^{T}\mathbf {x} \;|\;\mathbf {x} \in \mathbb {R} ^{n}\land \mathbf {Ax} \leq \mathbf {b} \land \mathbf {x} \geq 0\}}$ Formulasi lainnya, seperti masalah minimisasi, masalah dengan pertidaksamaan melibatkan operator $≥ {\displaystyle \geq }$ , juga masalah melibatkan variabel yang dapat bernilai negatif, selalu dapat disusun menjadi bentuk baku.

Contoh

Misalkan seorang petani memiliki sepetak lahan, anggap $L {\displaystyle L}$ km2, dan ingin mendapatkan untung dengan menanam singkong dan jagung. Petani memiliki jumlah pupuk dan pestisida yang terbatas, masing-masing sebanyak $U {\displaystyle U}$ dan $E {\displaystyle E}$ kilogram. Satu km2 tanaman singkong memerlukan $U 1 {\displaystyle U_{1}}$ kg pupuk dan $E 1 {\displaystyle E_{1}}$ kg pestisida, sedangkan satu km2 tanaman jagung $U 2 {\displaystyle U_{2}}$ kg pupuk dan $E 2 {\displaystyle E_{2}}$ kg pestisida. Dengan sedikit perhitungan, petani tersebut menemukan harga jual singkong per km2 sebesar $J 1 {\displaystyle J_{1}}$ rupiah, sedangkan $J 2 {\displaystyle J_{2}}$ rupiah adalah harga jual jagung per km2. Anggap $x 1 {\displaystyle x_{1}}$ dan $x 2 {\displaystyle x_{2}}$ secara berurutan adalah luas lahan yang ditanami singkong dan jagung. Keuntungan yang maksimum dapat diperoleh petani dengan memilih nilai yang optimal bagi $x 1 {\displaystyle x_{1}}$ dan $x 2 {\displaystyle x_{2}}$ . Menyatakan permasalahan tersebut dalam bentuk baku, kita mendapatkan program linear:

Maksimumkan: $J 1 ⋅ x 1 + J 2 ⋅ x 2 {\displaystyle J_{1}\cdot x_{1}+J_{2}\cdot x_{2}}$	(Maksimumkan keuntungan, yakni total penjualan singkong ditambah total penjualan jagung – keuntungan di sini adalah "fungsi objektif")
Dengan kendala:	$x 1 + x 2 ≤ L {\displaystyle x_{1}+x_{2}\leq L}$	(Batasan total lahan yang dapat ditanami)
	$U 1 ⋅ x 1 + U 2 ⋅ x 2 ≤ U {\displaystyle U_{1}\cdot x_{1}+U_{2}\cdot x_{2}\leq U}$	(Batasan banyak pupuk yang dimiliki)
	$E 1 ⋅ x 1 + E 2 ⋅ x 2 ≤ E {\displaystyle E_{1}\cdot x_{1}+E_{2}\cdot x_{2}\leq E}$	(Batasan banyak pestisida yang dimiliki)
	$x 1 ≥ 0 , x 2 ≥ 0 {\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(Luas lahan yang ditanam tidak mungkin negatif).

Masalah tersebut dapat disusun dalam bentuk matriks sebagai:

maksimumkan

[ S 1 S 2 ] [ x 1 x 2 ] {\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}

dengan kendala

[ 1 1 F 1 F 2 P 1 P 2 ] [ x 1 x 2 ] ≤ [ L F P ] , [ x 1 x 2 ] ≥ [ 0 0 ] . {\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}

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

z {\displaystyle z}

Dengan kendala

[ 1 − c T 0 0 A I ] [ z x s ] = [ 0 b ] {\displaystyle {\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}}}

Disini, $s {\displaystyle \mathbf {s} }$ adalah vektor berisi variabel-variabel lempai ( $s ≥ 0 {\displaystyle \mathbf {s} \geq 0}$ ), dan $x {\displaystyle \mathbf {x} }$ adalah vektor keputusan. Variabel $z {\displaystyle z}$ 'menyimpan' nilai dari fungsi objektif yang ingin dioptimalkan.

Contoh

Menggunakan contoh permasalahan petani di atas, bentuk imbuhan ditulis sebagai

Maksimumkan: $J 1 ⋅ x 1 + J 2 ⋅ x 2 {\displaystyle J_{1}\cdot x_{1}+J_{2}\cdot x_{2}}$	(Fungsi objektif)
Dengan kendala:	$x 1 + x 2 + x 3 = L {\displaystyle x_{1}+x_{2}+x_{3}=L}$	(Batasan dengan imbuhan)
	$U 1 ⋅ x 1 + U 2 ⋅ x 2 + x 4 = U {\displaystyle U_{1}\cdot x_{1}+U_{2}\cdot x_{2}+x_{4}=U}$	(Batasan dengan imbuhan)
	$E 1 ⋅ x 1 + E 2 ⋅ x 2 + x 5 = E {\displaystyle E_{1}\cdot x_{1}+E_{2}\cdot x_{2}+x_{5}=E}$	(Batasan dengan imbuhan)
	$x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 {\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0}$

Dalam bentuk ini, $x 3 , x 4 , x 5 {\displaystyle x_{3},x_{4},x_{5}}$ 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

z {\displaystyle z}

[ 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 ] [ z x 1 x 2 x 3 x 4 x 5 ] = [ 0 L F P ] , [ x 1 x 2 x 3 x 4 x 5 ] ≥ 0. {\displaystyle {\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}}\geq 0.}

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[butuh rujukan], 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:

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.

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 $f ( x , y ) = 3.000 x + 2.000 y {\displaystyle f(x,y)=3.000x+2.000y}$ (keuntungan parkir dalam rupiah)
dengan kendala:
1. $x + y ≤ 100 {\displaystyle x+y\leq 100}$ (batas jumlah kendaraan)
2. $3 x + y ≤ 150 {\displaystyle 3x+y\leq 150}$ (batas luas kendaraan dalam m2)
3. $x ≥ 0 {\displaystyle x\geq 0}$ (jumlah tidak boleh negatif)
4. $y ≥ 0 {\displaystyle y\geq 0}$ (jumlah tidak boleh negatif)

dengan $x {\displaystyle x}$ dan $y {\displaystyle y}$ 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 $3 x + y ≤ 150 {\displaystyle 3x+y\leq 150}$ adalah $3 x + y = 150 {\displaystyle 3x+y=150}$ . 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.

	(1)	(2)	(3)	(4)
(1)	-
(2)	$(25, 75)$	-
(3)	$(0, 100)$	$(0, 150)$	-
(4)	$(100, 0)$	$(50, 0)$	$(0, 0)$	-
Sel yang berwarna hijau memenuhi empat persamaan di atas.

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 $f ( x , y ) = 3.000 x + 2.000 y {\displaystyle f(x,y)=3.000x+2.000y}$ pada keempat titik tersebut.

Titik	Nilai (Rp)
$(0, 0)$	0
$(50, 0)$	150.000
$(0, 100)$	200.000
$(25, 75)$	225.000

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.

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 $c T x {\displaystyle \mathbf {c} ^{\text{T}}\mathbf {x} }$ dengan kendala $A x ≤ b {\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$ dan $x ≥ 0 {\displaystyle \mathbf {x} \geq \mathbf {0} }$ ; akan memiliki masalah dual simetrik Minimimumkan $b T y {\displaystyle \mathbf {b} ^{\text{T}}\mathbf {y} }$ dengan kendala $A T y ≥ c {\displaystyle \mathbf {A} ^{\text{T}}\mathbf {y} \geq \mathbf {c} }$ dan $y ≥ 0 {\displaystyle \mathbf {y} \geq \mathbf {0} }$ .
Maksimumkan $c T x {\displaystyle \mathbf {c} ^{\text{T}}\mathbf {x} }$ dengan kendala $A x ≤ b {\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$ ; akan memiliki masalah dual asimetrik Minimumkan $b T y {\displaystyle \mathbf {b} ^{\text{T}}\mathbf {y} }$ dengan kendala $A T y = c {\displaystyle \mathbf {A} ^{\text{T}}\mathbf {y} =\mathbf {c} }$ dan $y ≥ 0 {\displaystyle \mathbf {y} \geq \mathbf {0} }$ .

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 $x ∗ {\displaystyle \mathbf {x} ^{*}}$ , maka masalah dual juga memiliki sebuah solusi optimal $y ∗ {\displaystyle \mathbf {y} ^{*}}$ , dan keduanya terikat oleh hubungan $c T x ∗ = b T y ∗ {\displaystyle \mathbf {c} ^{\text{T}}\mathbf {x} ^{*}=\mathbf {b} ^{\text{T}}\mathbf {y} ^{*}}$ .[7]

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) merupakan 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.[8]

Masalah program linear penutupan memiliki bentuk:

Minimumkan:

b T y {\displaystyle \mathbf {b} ^{\text{T}}\mathbf {y} }

, dengan kendala:

A T y ≥ c {\displaystyle \mathbf {A} ^{\text{T}}\mathbf {y} \geq \mathbf {c} }

y ≥ 0 {\displaystyle \mathbf {y} \geq \mathbf {0} }

Dual dari masalah ini masalah program linear pengepakan, yang memiliki bentuk:

Maksimumkan:

c T x {\displaystyle \mathbf {c} ^{\text{T}}\mathbf {x} }

, dengan kendala:

A x ≤ b {\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }

x ≥ 0 {\displaystyle \mathbf {x} \geq \mathbf {0} }

Dalam kedua jenis permasalahan ini, matriks $A {\displaystyle \mathbf {A} }$ , vektor $b {\displaystyle \mathbf {b} }$ , dan vektor $c {\displaystyle \mathbf {c} }$ , 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 $x = ( x 1 , x 2 , … , x n ) {\displaystyle \mathbf {x} =(x_{1},x_{2},\dots ,x_{n})}$ adalah solusi feasibel di masalah primal, dan $y = ( y 1 , y 2 , … , y m ) {\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{m})}$ adalah solusi feasibel di masalah dual. Misalkan pula $w = ( w 1 , w 2 , … , w m ) {\displaystyle \mathbf {w} =(w_{1},w_{2},\dots ,w_{m})}$ adalah variabel lempai (slack) di masalah primal, dan $z = ( z 1 , z 2 , … , z n ) {\displaystyle \mathbf {z} =(z_{1},z_{2},\dots ,z_{n})}$ adalah variabel lempai di masalah dual. Vektor $x {\displaystyle \mathbf {x} }$ dan $y {\displaystyle \mathbf {y} }$ optimal di jenis masalah mereka masing masing, jika dan hanya jika:

$x j z j = 0 {\displaystyle x_{j}z_{j}=0}$ untuk $j = 1 , 2 , … , n {\displaystyle j=1,2,\dots ,n}$ , dan

$w i y i = 0 {\displaystyle w_{i}y_{i}=0}$ untuk $i = 1 , 2 , … , m {\displaystyle i=1,2,\dots ,m}$ .

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.

^ a b Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (edisi ke-3rd). CRC Press. hlm. 1. ISBN 978-1498710169.
^ a b Alexander Schrijver (1998). Theory of Linear and Integer Programming. John Wiley & Sons. hlm. 221–222. ISBN 978-0-471-98232-6.
^ a b George B. Dantzig (April 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. [pranala nonaktif permanen]
^ a b c Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. hlm. xxvii. ISBN 0387948333. OCLC 35318475.
^ Leonid Khachiyan (1979). "A Polynomial Algorithm for Linear Programming". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.
^ Narendra Karmarkar (1984). "A New Polynomial-Time Algorithm for Linear Programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. Parameter |s2cid= yang tidak diketahui akan diabaikan (bantuan)
^ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. hlm. 81–104. ISBN 3540306978. Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
^ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. hlm. 112. ISBN 9783540653677. Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)

Manullang, Sudianto; S., Andri Kristianto; Hutapea, Tri Andri; Sinaga, Lasker Pangarapan; Sinaga, Bornok; S., Mangaratua Marianus; Sinambela, Pardomuan N. J. M. (2017). Matematika untuk SMA/MA/SMK/MAK Kelas XI. Jakarta: Kementerian Pendidikan dan Kebudayaan. Diarsipkan dari versi asli tanggal 2020-03-09. Diakses tanggal 2020-03-06.
Arifien, Febianto. "Pemrograman Linier". Teknik Riset Operasional.
Kurnianingsih, Sri (2007). Matematika SMA dan MA 3A Untuk Kelas XII Semester 1 Program IPA. Jakarta: Esis/Erlangga. ISBN 979-734-504-1. Parameter |coauthors= yang tidak diketahui mengabaikan (|author= yang disarankan) (bantuan) (Indonesia)
Kurnianingsih, Sri (2007). Matematika SMA dan MA 3A Untuk Kelas XII Semester 1 Program IPS. Jakarta: Esis/Erlangga. ISBN 979-734-567-X. Parameter |coauthors= yang tidak diketahui mengabaikan (|author= yang disarankan) (bantuan) (Indonesia)