Program linear (linear programming) adalah salah satu teknik dalam riset operasional yang digunakan paling luas.LP merupakan teknik dalam mengalokasikan sumberdaya langka yang dimiliki perusahaan pada berbagai pilihan investasi untuk mencapai tujuan tunggal seperti maksimalisasi keuntungan atau minimalisasi biaya (Furqon, 2010).
Linear programming (LP) atau pemrograman linear (PL) adalah suatu pendekatan matematis untuk menyelesaikan suatu permasalahan agar didapatkan hasil yang optimal.Permasalahan yang sering diselesaikan dengan Linear Programming adalah dalam pengalokasian factor-faktor produksi yang terbatas jumlahnya terhadap berbagai kemungkinan produksi sehingga didapatkan manfaat yang optimal (maksimal dan minimal).Sasaran maksimal, misalnya secara efisien sehingga manfaat yang ingin dicapai (jumlah produksi/nilai penjualan/laba, dan lain-lain) menjadi maksimal. Sasaran minimal misalnya, bagaimana mencari kombinasi produksi agar penggunaan faktor-faktor produksi minimal tetapi manfaat yang dicapai (dari kombinasi produksi) tidak lebih rendah dari angka yang diinginkan ( Tarigan, 2005).
Program linear yang diterjemahkan dari Linear Programming (LP) adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas diantara diantara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalokasian ini akan muncul manakala seseorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut.Program linear ini menggunakan model matematis untuk menjelaskan persoalan yang dihadapinya.Sifat “linear” disini memberi arti bahwa seluruh fungsi matematis dalam model ini merupakan fungsi yang linear, sedangkan kata “programa” merupakan sinonim untuk perencanaan.Dengan demikian, programa linear (LP) adalah perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil yang mencapai tujuan terbaik diantara seluruh alternatif yang fisibel (Dimyati dan Akhmad, 2006).
Program linear adalah sebuah alat deterministik yang berarti bahwa semua parameter model diasumsikan diketahui dengan pasti.Tetapi, dalam kehidupan nyata, jarang seseorang menghadapi masalah dimana terdapat kepastian yang sesungguhnya.Teknik LP mengkompensasi “kekurangan ini” dengan memberikan analisis pasca-optimum dan analisis parametris yang sistematis untuk memungkinkan pengambilan keputusan yang bersangkutan (Taha, 1996).
Metode simpleks mengidentifikasi titik ekstrim atau titik sudut secara lajabar. Metode simplek mengharuskan agar setiap batasan ditempatkan dalam bentuk standar yang khusus dimana semua batasan diekspresikan sebagai persamaan dengan menambahkan variabel slack dan surplus sebagaimana diperlukan. Jenis konversi ini umumnya menghasilkan sekelompok persamaan dimana jumlah variabel adalah lebih besar dari pada jumlah persamaan, yang umumnya berarti bahwa persamaan tersebut menghasilkan jumlah persamaan, yang umumnya berarti bahwa persamaan tersebut menghasilkan sejumlah titik pemecahan yang tidak terbatas.Titik ekstrim dari ruang ini dapat diidentifikasi secara aljabar sebagai pemecah dasar (basic solution) dari sistem persamaan simultan tersebut. Dasar teori aljabar linear, sebuah pemecahan dasar diperoleh dengan menetapkan beberapa variabel yang sebanyak selisih antara jumlah total variabel dengan jumlah total persamaan memiliki nilai sama dengan nol dan lalu memecahkan variabel sisa, dengan ketentuan bahwa kondisi tersebut menghasilkan satu pemecahan yang unik (Taha, 1996).
