Program linear merupakan teknik matematik untuk mendapat alternatif penggunaan terbaik atas sumber-sumber organisasi perusahaan. Kata sifat linear dipakai untuk menggambarkan relasi antara dua atau lebih variabel, relasi yang eksklusif dan persis proporsional.
Linear berarti bahwa semua fungsi matematis yang disajikan dalam model ini haruslah fungsi linear atau secara mudah sanggup dikatakan bahwa persamaan tersebut bila digambarkan pada grafik akan membentuk garis lurus.
Dalam relasi linear antara jumlah kerja dan output sebagai contoh, 10% perubahan jumlah jam produksi dalam beberapa operasi akan menjadikan 10% perubahan output. Sedangkan kata acara menyatakan perencanaan dengan memakai teknik matematik tertentu untuk mendapat kemungkinan pemecahan terbaik atas kasus yang melibatkan sumber yang serba terbatas.
Makara acara linear meliputi perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum menurut model matematis diantara alternatif yang mungkin dengan memakai fungsi linear.
Program linear sendiri mempunyai 2 teknik pemecahan, yaitu dengan metode grafik dan simpleks :
1. Metode Grafik
Metode grafik sanggup dipakai untuk pemecahan kasus acara linear berdimensi 2 x n atau m x 2. Maksudnya yaitu metode grafik hanya sanggup dipakai untuk pemecahan persamaan yang mempunyai dua variabel. Jika suatu persamaan mempunyai 3 variabel atau lebih, maka metode grafik sudah tidak berlaku.
Misalnya :
2 X1 + 3 X2 ≤ 200.
Berdasarkan persamaan diatas metode grafik masih sanggup digunakan.
Berdasarkan persamaan diatas metode grafik masih sanggup digunakan.
2 X1 + 3 X2 + 4 X3 ≤ 200.
Sedangkan untuk persamaan tersebut, metode grafik sudah tidak sanggup dipakai lagi, sehingga diharapkan metode lainya menyerupai metode simpleks.
Sedangkan untuk persamaan tersebut, metode grafik sudah tidak sanggup dipakai lagi, sehingga diharapkan metode lainya menyerupai metode simpleks.
Untuk lebih jelasnya perihal metode grafik sanggup dilihat pada :
2. Metode Simpleks
Metode simpleks dikembangkan pertama kali oleh Goerge dantzing pada tahun 1947. Sifat dari metode ini yaitu iterative, dimana penyelesaian kasus melalui tahapan perhitungan yang berulang-ulang hingga solusi optimum.
Metode simpleks ini sanggup dipakai untuk pemecahan kasus berdimensi 2 x n atau m x 2 menyerupai metode grafis. Selain itu, metode simpleks sanggup menuntaskan kasus yang mempunyai 3 variabel atau lebih.
Jadi, metode simpleks ini sanggup dipakai untuk menuntaskan semua kasus acara linear. Hanya saja, lantaran metode ini cukup rumit, sangat disarankan kalau dalam soal yang hanya mempunyai 2 variabel, metode yang terbaik untuk dipakai yaitu metode grafik. Sedangkan metode simpleks hanya dipakai untuk menuntaskan kasus yang mempunyai 3 variabel atau lebih.
Untuk lebih jelasnya perihal metode simpleks sanggup dilihat pada :
Hanya saja, sebelum memecahkan soal baik dengan metode grafik atau metode simpleks, diharapkan formulasi dari acara linear itu sendiri. Formulasi diharapkan sebagai langkah awal dalam perhitungan. Untuk lebih jelasnya perihal formulasi acara linear, sanggup dibaca di :
Syarat Utama Persoalan Program Linear
Sebelum ke pemecahan kasus linear, perlu diketahui syarat-syarat utama kasus linear yaitu :
- Perusahaan harus mempunyai tujuan untuk dicapai. Tujuan perusahaan itu sanggup memaksimumkan keuntungan (pendapatan) atau meminimumkan resiko (biaya,waktu).
- Harus ada alternatif tindakan yang salah satu dasarnya akan mencapai tujuan. Sebagai contoh, apakah perusahaan harus mengalokasikan kapasitas industrinya untuk menciptakan produk A dan B dalam perbandingan misal 50:50?, 25:50?, 70:30?, dan sebagainya.
- Sumber harus merupakan persediaan terbatas. Misal perusahaan mempunyai jumlah jam mesin terbatas, sehingga kalau harus menciptakan produk A dan B, maka semakin banyak waktu yang dipakai untuk menciptakan produk A, akan semakin sedikit B yang sanggup dibuat.
- Harus sanggup menyatakan tujuan dan segenap keterbatasannya sebagai kesamaan atau ketidaksamaan matematik.
Asumsi-Asumsi Dasar Program Linear
1. Asumsi kesebandingan (proporsional)
Kontribusi setiap variabel keputusan terhadap fungsi tujuan yaitu sebanding dengan nilai variabel keputusan.
Contoh : kita memproduksi 10 unit produk jenis I dari rujukan diatas, maka kontribusinya terhadap fungsi tujuan yaitu 10 kali bantuan setiap unit jenis I yaitu 10 x 2000 = Rp.20.000.
2. Asumsi additivity (penambahan)
Asumsi ini menyatakan bahwa nilai fungsi tujuan setiap kegiatan tidak saling menghipnotis atau dalam acara linear dianggap bahwa kenaikan nilai fungsi tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan sanggup ditambahkan tanpa menghipnotis nilai Z yang diperoleh dari kegiatan lain atau sanggup dikatakan bahwa tidak ada relasi antara satu kegiatan dengan kegiatan lain.
Misal : Z = 8 X1 + 10 X2, untuk X1 = 6 dan X2 = 8 maka Z = 128.
Jika X1 bertambah atau berkurang, maka pertambahan atau pengurangan X1 sanggup eksklusif ditambahkan atau dikurangi pada nilai Z, tanpa menghipnotis belahan Z yang diperoleh dari X2.
3. Divisibility (pembagian)
Asumsi ini menyatakan bahwa output yang dihasilkan oleh setiap kegiatan sanggup berupa bilangan pecahan.
4. Asumsi deterministik (kepastian)
Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model acara linear sanggup diperkirakan dengan pasti. Dalam kenyataannya parameter model jarang bersifat deterministik, lantaran keadaan masa depan jarang diketahui dengan pasti. Untuk mengetahui ketidakpastian parameter maka dikembangkan teknik analisis sensitivitas, guna menguji nilai solusi bagaimana kepekaanya terhadap perubahan-perubahan parameter.
Pengartian Dalam Program Linear
- Feasible Solution
- Infeasible Solution
- Optimal Solution
- Multiple Optimal Solution
- Boundary Equation
- No Optimal Solution
Suatu solusi yang memenuhi seluruh pembatas yang ada pada kasus tersebut. Pada rujukan diatas feasible solutionnya yaitu O-ABCD.
Suatu solusi dimana tidak ada titik-titik secara serentak memenuhi semua hambatan dalam kasus tersebut.
Feasible solution yang memperlihatkan nilai terbaik bagi fungsi tujuannya. Terbaik diartikan nilai terbesar untuk tujuan maksimasi dan nilai terkecil untuk tujuan minimasi. Pada rujukan diatas titik C merupakan optimal solution.
Ini terjadi kalau fungsi tujuan terletak pada lebih dari satu titik optimal. Multiple optimal solution akan memperlihatkan keluwesan dalam menentukan solusi bagi pengambil keputusan.
Ini terjadi apabila ada hambatan dengan tanda "sama dengan", dan terjadi kawasan feasible yang terletak pada garis tersebut.
Terjadi kalau suatu kasus tidak mempunyai penyelesaian optimal, disebabkan oleh tidak ada feasible solution dan juga disebabkan oleh adanya batasan yang tidak membatasi besar nilai Z.