Linier programming dikembangkan oleh George Dantzig , seorang Matematisian dari Amerika Serikat pada tahun 1947, ialahsuatu model optimasi persamaan linier berkenaan dengan pengalokasian sumber-sumber yang secara terbatas secara optimal. agar linier programming dapat diterapkan , asumsi-asumsi dasar berikut ini harus dipenuhi :
1. Masalah tersebut harus dapat diubah menjadi permasalahan matematik, yang berarti masalah riil harus dijadikan model matematika baik berupa persamaan linier maupun non linier
2. Keseluruhan system permasalahan dapat dipilah-pilah dalam satuan aktivitas, Misal = a11 x1 + a12 x2 ≤ k1 , dimana x1 dan x2 adalah aktivitas
3. Masing-masing aktivitas harus dapat ditentukan dengan tepat baik jenis maupun letaknya dalam model programasi linier
4. Setiap aktivitas harus dapat dikualifikasikan sehingga masing-masing nilainya dapat dibandingkan
Metoda Grafik
Metoda grafik hanya dapat diterapkan untuk memecahkan maslah-masalah linier programming (LP) yang menyangkut dua variabel keputusan. Sebagai contoh sebuah perusahaan Garmen “Buah Hati (BH)” , memproduksi dua jenis produk yaitu H dan K. Setiap produk H memberikan kontribusi laba sebesar Rp 4,- dan K sebesar Rp 8,-. Setiap satuan unit produk H memerlukan proses selama 8 jam pada mesin A dan 12 jam pada mesin B. Setiap satuan unit produk K memerlukan proses selama 4 jam pada mesin A , 12 jam pada mesin B dan 2 jam pada mesin C. Mesin A mempunuai kapasitas maksimum 240 jam perminggu, mesin B 144 jam perminggu dan mesin C 20 jam perminggu.
Langkah-langkah penyelesaian dengan menggunakan metoda grafik sebagai berikut:
1. Merumuskan masalah dalam bentuk matematika.
Maksimumkan Z = 4 H + 8 K (laba)
8 H + 12 K ≤ 240 (mesin A)
4 H + 12 K ≤ 144 (mesin B)
2 K ≤ 20 (mesin C)
H ≥ 0 dan K ≥ 0 (batasan )
Agar lebih memudahkan kita juga dapat merubah simbul variabel H dan K dengan menggunakan dalam matematika y dan x ( H = y dan K = x ), sehingga bentuk matematika menjadi :
Z = 4 y + 8 x (laba)
8 y + 12 x ≤ 240 (mesin A)
4 y + 12 x ≤ 144 (mesin B)
2 x ≤ 20 (mesin C)
y ≥ 0 dan x ≥ 0 (batasan)
2. Menggambarkan dalam persamaan-persamaan batasan , sehinga persamaan menjadi :
8 y + 12 x = 240 (mesin A)
4 y + 12 x = 144 (mesin B)
2 x = 20 (mesin C)
Pada persamaan 8 y + 12 x = 240, tentukan titik potong pada sumbu x sehingga y = 0 diperoleh titik (20 , 0) dan tentukan titik potong pada sumbu y sehingga x = 0 diperoleh titik (0 ,30)
Pada persamaan 4 y + 12 x = 144, tentukan titik potong pada sumbu x sehingga y = 0 diperoleh titik (12 , 0) dan tentukan titik potong pada sumbu y sehingga x = 0 diperoleh titik (0 ,36)
Pada persamaan 2 x = 20, diperoleh x sebesar x=10 (10,0)
Dari hasil persamaan diatas jika digambarkan pada suatu grafik diperoleh titik perpotongan antara persamaan 8 y + 12 x = 240 dengan persamaan 4 y + 12 x = 144 dan persamaan 4 y + 12 x = 144 dengan 2 x = 20.
Titik perpotongan antara persamaan 8 y + 12 x = 240 dengan persamaan 4 y + 12 x = 144 diperoleh pada titik (4 ,24) , sedangkan persamaan 4 y + 12 x = 144 dengan 2 x = 20 diperoleh titik (10 , 6).
3. Menentukan daerah “feasibilitas” , merupakan daerah batasan dalam suatu ketidaksamaan dimana suatu penyelesaian feasibel akan ditemukan. Dalam kasus ini semua ketidaksamaan adalah bertanda lebih kecil atau sama dengan yang berarti bahwa kita tidak akan mungkin untuk memproduksi berbagai produk yang akan terletak di luar daerah feasibel karena melebihi kapasitas mesin yang tersedia (daerah yang diasir).
4. Menggambarkan daerah tujuan, yaitu menentukan semua kemungkinan-kemungkinan dengan memasukkan titik-tik koordinat dalam suatu persamaan
Titik koordinat dari pertidaksamaan yang memenuhi sebagai berikut :
8 x + 4 y = Z (laba)
( 0 , 0 ) 8 .0 + 4 .0 = 0
(10, 0 ) 8 .10 + 4 .0 = 80
(10 , 6 ) 8 .10 + 4 .6 = 104
( 4 , 24) 8 .4 + 4 .24 = 128
(0 , 30) 8 .0 + 4 .30 = 120
5. Mencari titik optimum, artinya mencari daerah yang mempunyai laba yang maksimum.
Dari hasil subtitusi diatas diperoleh titik yang paling optimal pada koordinat ( 4 , 24) sehingga laba yang diperoleh sebesar 128
Contoh
Luas lahan parkir 360 m2 digunakan untuk parkir mobil dan bus, masing-masing membutuhkan lahan mobil 6 m2 dan bus 24 m2 . Daerah parkir tersebut tidak dapat menampung lebih dari 30 kendaraan. Tentukan jumlah maksimum yang diterima tukang parkir , jika biaya sebuah mobil Rp 1.500, dan sebuah bis Rp 3.000,-