Program linear: Perbedaan antara revisi

← Revisi sebelumnya Revisi selanjutnya →

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 30 Oktober 2021 03.34

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

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

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

${\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 $\mathbf {x}$ adalah variabel yang ingin ditentukan nilainya. Vektor $\mathbf {c}$ adalah vektor koefisien fungsi objektif, sedangkan $\mathbf {b}$ adalah vektor nilai kunci. Fungsi objektif adalah fungsi yang nilainya ingin dimaksimumkan atau diminimumkan, dalam kasus ini berupa fungsi $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ . Matriks $\mathbf {A}$ berisi koefisien-koefisien dari persamaan (dan pertidaksamaan) kendala-kendala. Pertidaksamaan $\mathbf {A} \mathbf {x} \leq \mathbf {b}$ dan $\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 $\mathbf {x}$ dikatakan lebih kecil atau sama dengan vektor $\mathbf {y}$ , jika semua nilai komponen vektor $\mathbf {x}$ lebih kecil atau sama dengan nilai komponen $\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.

Sejarah

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

Bentuk baku program linear adalah bentuk yang mudah dipahami untuk menjelaskan permasalahan program linear. Bentuk ini terdiri dari tiga bagian:

Suatu fungsi tujuan/objektif

f(x_{1},x_{2},\dots ,x_{n})=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}

Batasan/kendala permasalahan

{\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}}

Variabel nonnegatif

{\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\&\vdots \\x_{n}&\geq 0\end{aligned}}

Bentuk ini juga bisa ditulis dalam bentuk matriks seperti berikut.

{\text{maks}}\{\mathbf {c} ^{T}\mathbf {x} \;|\;\mathbf {Ax} \leq \mathbf {b} \land \mathbf {x} \geq 0\}

Bentuk imbuhan (bentuk lempai/slack)

Program linear juga dapat digambarkan dalam bentuk imbuhan (augmented form) agar dapat diselesaikan dengan metode simpleks. Bentuk ini menggunakan variabel lempai (slack) yang nonnegatif untuk menggantikan pertidaksamaan dalam batasan/kendala. Permasalahan ini dapat ditulis ulang dalam bentuk matriks sebagai berikut.

Maksimalkan

z

pada

{\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}}

dengan

\mathbf {s}

adalah vektor variabel lempai (

\mathbf {s} \geq 0

) dan

\mathbf {x}

adalah vektor penentu.

Penyelesaian

Tahapan umum untuk menyelesaikan program linear adalah

menentukan variabel keputusan;
membuat fungsi objektif;
merumuskan kendala/batasan;
menentukan daerah penyelesaian;
menentukan titik optimal;
mengartikan titik yang diperoleh.

Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan metode simpleks. Metode grafik hanya bisa menyelesaikan program linear dengan hingga dua (grafik dua dimensi) atau tiga variabel (grafik tiga dimensi). Metode simpleks tidak memiliki batasan jumlah variabel, tetapi lebih rumit daripada metode grafik.

Contoh kasus sederhana

Program linear yang memiliki dua variabel dapat digambarkan dalam grafik untuk mempermudah penyelesaian (walau tidak perlu). Berikut contoh soal dan penyelesaiannya.

Harga parkir mobil adalah Rp3 ribu dan harga parkir motor adalah Rp2 ribu. Suatu lahan parkir seluas 150 m² dapat menampung 100 kendaraan. Satu motor menghabiskan 1 m² dan satu mobil menghabiskan 3 m². Bila lahan parkir tersebut disewakan, berapa keuntungan maksimum yang bisa didapat?

Dari soal di atas, dapat disusun program linear berikut:

memaksimalkan $f(x,y)=3.000x+2.000y$ (keuntungan parkir dalam rupiah)
dengan kendala:
1. $x+y\leq 100$ (batas jumlah kendaraan)
2. $3x+y\leq 150$ (batas luas kendaraan dalam m²)
3. $x\geq 0$ (jumlah tidak boleh negatif)
4. $y\geq 0$ (jumlah tidak boleh negatif)

dengan $x$ adalah mobil dan $y$ adalah motor.

Dari empat persamaan itu, dapat diambil empat titik perpotongan yang memenuhi empat persamaan di atas.

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

Hitung fungsi objektif $f(x,y)=3.000x+2.000y$ untuk empat titik tersebut.

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

Dari tabel di atas, dapat dilihat bahwa keuntungan maksimum yang bisa didapat adalah Rp225 ribu dengan 25 mobil dan 75 motor.

Daftar pustaka

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.

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

Bacaan lebih lanjut

Kurnianingsih, Sri (2007). Matematika SMA dan MA 3A Untuk Kelas XII Semester 1 Program IPA. Jakarta: Esis/Erlangga. ISBN 979-734-504-1. (Indonesia)
Kurnianingsih, Sri (2007). Matematika SMA dan MA 3A Untuk Kelas XII Semester 1 Program IPS. Jakarta: Esis/Erlangga. ISBN 979-734-567-X. (Indonesia)

Pranala luar

(Inggris) Guidance On Formulating LP Problems
(Inggris) Mathematical Programming Glossary
(Inggris) The Linear Programming FAQ
(Inggris) Benchmarks For Optimisation Software

[SierksmaZwols2015-1] Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (edisi ke-3rd). CRC Press. hlm. 1. ISBN 978-1498710169.

[Schrijver1998-2] Alexander Schrijver (1998). Theory of Linear and Integer Programming. John Wiley & Sons. hlm. 221–222. ISBN 978-0-471-98232-6.

[dantzig1982-3] 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.

[:0-4] Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. hlm. xxvii. ISBN 0387948333. OCLC 35318475.

[khachiyan79-5] Leonid Khachiyan (1979). "A Polynomial Algorithm for Linear Programming". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.

[karmarkar84-6] Narendra Karmarkar (1984). "A New Polynomial-Time Algorithm for Linear Programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Baris 1: / Baris 1: @@
+[[Berkas:Linear_optimization_in_a_2-dimensional_polytope.svg|jmpl|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.]]
-'''Program linear''' adalah cara untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika.
+[[Berkas:3dpoly.svg|ka|jmpl|Pada masalah optimisasi dengan tiga variabel, daerah feasibel yang tertutup akan membentuk sebuah [[Polihedron cembung|polihedron]] konveks. Program linear bertujuan untuk mencari titik di polihedron yang menghasilkan nilai fungsi objektif tertinggi (atau terendah).]]
+'''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.
-Secara formal, suatu program linear digambarkan sebagai
-<blockquote>usaha untuk memaksimalkan <math>\mathbf{c}^T\mathbf{x}</math> dengan kendala <math>\mathbf{Ax} \leq \mathbf{b}</math> dan <math>\mathbf{x} \geq 0</math></blockquote>
-dengan <math>\mathbf{c}</math> adalah vektor koefisien fungsi tujuan/objektif, <math>\mathbf{A}</math> adalah matriks koefisien persamaan kendala, <math>\mathbf{b}</math> adalah vektor nilai kunci, dan <math>\mathbf{x}</math> adalah vektor peubah/variabel.
+Program linear adalah masalah yang dapat dinyatakan dalam [[Bentuk kanonik|bentuk kanonik (baku)]] sebagai
-Program linear dapat diterapkan dalam berbagai bidang. Ia digunakan secara luas di bidang [[matematika]] dan secara khusus di bidang bisnis, [[ekonomi]], dan [[teknologi]]. Industri pun menerapkan program linear, seperti [[transportasi]], pengelolaan energi, telekomunikasi, dan [[manufaktur]]. Program ini terbukti mampu memecahkan masalah perencanaan, penjadwalan, dan desain.
+<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 ==
+[[Berkas:Leonid_Kantorovich_1975.jpg|jmpl|[[Leonid Kantorovich]]]]
+[[Berkas:JohnvonNeumann-LosAlamos.gif|jmpl|[[John von Neumann]]]]
+Masalah menyelesaikan sebuah sistem pertidaksamaan linear dapat dilacak ke [[Joseph Fourier|Fourier]], yang pada tahun 1827 menerbitkan sebuah metode untuk menemukan solusinya.<ref name="SierksmaZwols2015">{{cite book|author1=Gerard Sierksma|author2=Yori Zwols|year=2015|title=Linear and Integer Optimization: Theory and Practice|publisher=CRC Press|isbn=978-1498710169|edition=3rd|page=1}}</ref> 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.<ref name="Schrijver1998">{{cite book|author=Alexander Schrijver|year=1998|title=Theory of Linear and Integer Programming|publisher=John Wiley & Sons|isbn=978-0-471-98232-6|pages=221–222}}</ref> Formulasi ini ia kembangkan pada masa [[Perang Dunia II]], untuk merencanakan pengeluaran dan pendapatan agar mengurangi rugi bagi tentara dan meningkatkan kerugian bagi musuh.{{Citation needed|date=August 2017}} Karya Kantorovich awalnya dihiraukan oleh [[USSR]].<ref name="dantzig1982">{{cite journal|author=George B. Dantzig|date=April 1982|title=Reminiscences about the origins of linear programming|url=http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|journal=Operations Research Letters|volume=1|issue=2|pages=43–48|doi=10.1016/0167-6377(82)90043-8}}</ref> 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.<ref name="SierksmaZwols2015" /> Pada tahun 1941, [[Frank Lauren Hitchcock]] juga memformulasikan masalah transportasi dalam bentuk program linear, dan memberikan solusi yang sangat mirip dengan [[metode simpleks]].<ref name="Schrijver1998" /> 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]].<ref name=":0">{{Cite book|last1=Dantzig|first1=George B.|last2=Thapa|first2=Mukund Narain|date=1997|title=Linear programming|location=New York|publisher=Springer|isbn=0387948333|page=xxvii|oclc=35318475}}</ref> Di tahun 1947, juga menemukan [[metode simpleks]] yang untuk pertama kalinya menyelesaikan banyak masalah program linear secara efisien.<ref name=":0" /> 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]].<ref name=":0" /> Dantzig memberikan bukti formal pada sebuah laporan yang tidak dipublikasikan, "''A Theorem on Linear Inequalities''" pada 5 Januari 1948.<ref name="dantzig1982" /> 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.<ref name="khachiyan79">{{cite journal|author=Leonid Khachiyan|date=1979|title=A Polynomial Algorithm for Linear Programming|journal=Doklady Akademii Nauk SSSR|volume=224|issue=5|pages=1093–1096}}</ref> 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.<ref name="karmarkar84">{{cite journal|author=Narendra Karmarkar|date=1984|title=A New Polynomial-Time Algorithm for Linear Programming|journal=Combinatorica|volume=4|issue=4|pages=373–395|doi=10.1007/BF02579150|s2cid=7257867}}</ref>
 == Bentuk baku ==
@@ Baris 123: / Baris 147: @@
 * {{cite book|year=2017|title=Matematika untuk SMA/MA/SMK/MAK Kelas XI|last1=Manullang|first1=Sudianto|last2=S.|first2=Andri Kristianto|last3=Hutapea|first3=Tri Andri|last4=Sinaga|first4=Lasker Pangarapan|last5=Sinaga|first5=Bornok|last6=S.|first6=Mangaratua Marianus|last7=Sinambela|first7=Pardomuan N. J. M.|place=Jakarta|publisher=Kementerian Pendidikan dan Kebudayaan|url=http://buku.kemdikbud.go.id/index.php/buku/detail/2a3411db-6de8-459d-8207-366b7c2acc7e|access-date=2020-03-06|archive-date=2020-03-09|archive-url=https://web.archive.org/web/20200309054956/http://buku.kemdikbud.go.id/index.php/buku/detail/2a3411db-6de8-459d-8207-366b7c2acc7e|dead-url=yes}}
 * {{cite book|title=Teknik Riset Operasional|last=Arifien|first=Febianto|chapter=Pemrograman Linier|url=http://febianto.staff.gunadarma.ac.id/Downloads/folder/0.3}}
+<references />
 == Bacaan lebih lanjut ==

Pengawasan otoritas
Umum	Integrated Authority File (Jerman)
Perpustakaan nasional	Prancis (data) Amerika Serikat Jepang Republik Ceko
Lain-lain	Microsoft Academic