--- title: "Pemrograman Linear" source: "https://systems-analysis.info/int/Pemrograman_Linear" wiki: "systems-analysis.info/int" article: "Pemrograman_Linear" language: "id" categories: - "Category:Indonesian" - "Category:Mathematical modeling" - "Category:Operations research" revision_id: 5474 wiki_created_at: 2026-09-06T23:49:48Z wiki_modified_at: 2026-09-06T23:49:48Z downloaded_at: 2026-09-07T23:08:41Z --- # Pemrograman Linear **Pemrograman linear** — adalah cabang pemrograman matematis dan metode riset operasi yang banyak digunakan, yang membahas pengembangan teori dan metode penyelesaian masalah pencarian ekstremum (maksimum atau minimum) dari suatu fungsi linear dengan adanya kendala-kendala linear. Pemrograman linear (PL) merupakan salah satu alat paling kuat dan sering digunakan untuk menyelesaikan masalah optimasi dalam bidang ekonomi, manajemen, perencanaan, logistik, dan bidang-bidang lainnya. ## Subjek dan Tujuan **Tugas utama pemrograman linear** — menemukan cara terbaik (optimal) untuk mengalokasikan sumber daya yang terbatas guna mencapai suatu tujuan tertentu, ketika baik tujuan maupun kendala penggunaan sumber daya dapat dinyatakan dalam bentuk hubungan linear. - Pemrograman linear memungkinkan penyelesaian berbagai masalah praktis, seperti: - Perencanaan produksi yang optimal. - Optimasi arus transportasi (masalah transportasi). - Distribusi investasi yang optimal. - Pemotongan material yang optimal. Masalah penugasan. ## Formulasi Matematis Masalah PL Masalah standar pemrograman linear dirumuskan sebagai berikut: Diperlukan pencarian nilai-nilai variabel keputusan yang memaksimalkan atau meminimalkan fungsi tujuan linear. Pada variabel keputusan dikenakan kendala berupa sistem persamaan linear dan/atau pertidaksamaan linear. Pada umumnya, ditambahkan syarat non-negatifitas variabel keputusan (nilainya harus lebih besar atau sama dengan nol), yang sering kali ditentukan oleh makna fisik atau ekonomi dari masalah tersebut. Secara matematis, hal ini berarti bekerja dengan fungsi-fungsi linear dan sistem persamaan/pertidaksamaan linear. ## Konsep Dasar PL - Variabel keputusan (Variabel terkendali): Besaran yang nilainya perlu ditentukan dalam proses penyelesaian masalah (misalnya, volume produksi berbagai produk, jumlah sumber daya yang dialokasikan ke berbagai tujuan). - Fungsi tujuan: Fungsi linear dari variabel keputusan yang nilainya perlu dimaksimalkan atau diminimalkan. Fungsi ini secara kuantitatif menyatakan tujuan masalah (misalnya, total keuntungan, total biaya). - Kendala: Sistem persamaan linear dan/atau pertidaksamaan linear yang harus dipenuhi oleh variabel keputusan. Kendala mencerminkan batas sumber daya, persyaratan teknologi, target rencana, dan kondisi-kondisi lain dari masalah. - Daerah penyelesaian yang layak (DPL): Himpunan semua kombinasi nilai variabel keputusan yang memenuhi seluruh kendala masalah. Secara geometris dalam ruang multidimensi, DPL berupa polihedron cembung (poliedron), yang mungkin tidak terbatas atau kosong. - Penyelesaian yang layak: Setiap kombinasi nilai variabel yang termasuk dalam DPL. - Penyelesaian optimal: Penyelesaian yang layak di mana fungsi tujuan mencapai nilai ekstremumnya (maksimum atau minimum). Jika penyelesaian optimal ada, ia selalu berada di batas DPL, setidaknya di salah satu titik sudut polihedron cembung DPL (teorema dasar PL). ## Metode Penyelesaian Masalah PL Terdapat beberapa metode utama untuk menyelesaikan masalah pemrograman linear: - Metode grafis: Diterapkan untuk masalah dengan dua variabel keputusan. Memungkinkan penggambaran DPL dan fungsi tujuan secara visual pada bidang datar, serta pencarian penyelesaian optimal melalui analisis titik-titik sudut DPL atau pergeseran garis level fungsi tujuan. - Metode simpleks: Algoritma iteratif universal yang dikembangkan oleh George Dantzig. Metode ini secara berturut-turut berpindah dari satu titik sudut DPL ke titik sudut yang berdekatan, memperbaiki nilai fungsi tujuan pada setiap langkah, hingga ditemukan penyelesaian optimal. Merupakan metode klasik dan paling dikenal untuk penyelesaian masalah PL. - Metode titik interior: Kelas algoritma alternatif yang muncul setelah metode simpleks. Metode-metode ini bergerak menuju penyelesaian optimal di dalam DPL, bukan melalui batas-batasnya. Metode-metode ini sangat efektif untuk menyelesaikan masalah PL berdimensi sangat besar. ## Dualitas dalam Pemrograman Linear Setiap masalah pemrograman linear (yang disebut masalah primal) dapat dipasangkan dengan masalah PL lain yang disebut masalah dual. Masalah primal dan dual saling berkaitan erat: Penyelesaian satu masalah memberikan informasi tentang penyelesaian masalah lainnya. Nilai optimal fungsi tujuan pada kedua masalah adalah sama (jika keduanya ada). Variabel masalah dual memiliki interpretasi ekonomi yang penting — variabel-variabel tersebut berkorespondensi dengan harga bayangan (atau estimasi dual) dari sumber daya, yang menunjukkan seberapa besar nilai optimal fungsi tujuan masalah primal akan berubah akibat perubahan kecil pada kendala sumber daya yang bersangkutan. ## Penerapan PL Pemrograman linear diterapkan secara luas dalam: - Ekonomi dan bisnis (perencanaan produksi, logistik, keuangan, pemasaran). - Industri (optimasi proses teknologi, manajemen persediaan, pemotongan material). - Transportasi (optimasi rute, jadwal). Pertanian (optimasi lahan tanam, ransum pakan). - Energi (optimasi beban kapasitas pembangkit listrik). ## Literatur - *Dantzig, G.* Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966. - *Yudin, D. B., Goldstein, E. G.* Линейное программирование (теория, методы и приложения). — М.: Наuka, 1969. - *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017) - *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021) ## Lihat Juga - Riset operasi - Optimasi - Fungsi tujuan - Kendala - Daerah penyelesaian yang layak - Penyelesaian optimal