Pengertian Linear Programming

Linear Programming

1. Pengantar Linear Programming

Keberhasilan suatu teknik riset operasi pada akhirnya diukur berdasarkan penyebaran penggunaannya sebagai suatu alat pengambil keputusan sejak diperkenalkan diakhir tahun 1940 -an, Linear Programming telah terbukti merupakan salah satu riset operasi yang paling efektif. Keberhasilannya berakar dari keluwesannya dalam menjabarkan berbagai situasi kehidupan nyata dibidang – bidang berikut ini, yaitu militer, industri, pertanian, transportasi, ekonomi, kesehatan, dan bahkan ilmu sosial dan perilaku. Disamping itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah – masalah linear programming yang sangat luas merupakan faktor penting dalam tersebarnya penggunaan teknik ini. 

Kegunaan linear programming adalah lebih luas daripada aplikasinya semata – mata. Pada kenyataannya, linear programming harus dipandang sebagai dasar penting pengembangan teknik – teknik riset operasi lainnya, termasuk program integer, stochastic, arus jaringan dan kuadratik. Dalam hal ini, pemahaman akan linear programming adalah penting untuk implementasi teknik – teknik tambahan ini. 

Linear programming adalah sebuah alat deterministic, yang berarti bahwa semua parameter model yang diasumsikan diketahui dengan pasti. Tetapi dalam kehidupan nyata, jarang seseorang mengahadapi masalah dimana terdapat kepastian yang sesungguhnya. Teknik linear programming mengkompensasikan ”kekurangan” ini dengan memberikan analisis paska optimal dan analisis parametrik yang sistematis untuk memungkinkan pengambil keputusan yang bersangkutan untuk menguji sensivitas pemecahan yang optimal yang statis terhadap perubahan diskrit atau kontinue dalam berbagai parameter dari model tersebut. Pada intinya teknik tambahan ini memberikan dimensi dinamis pada sifat pemecahan linear programming yang optimal.

Tujuan dari linear programming adalah suatu hasil yang mencapai tujuan yang ditentukan (optimal) dengan cara yang paling baik diantara semua alternatif yang mungkin dengan batasan sumber daya yang tersedia. Meskipun mengalokasi sumber– sumber daya kepada kegiatan – kegiatan merupakan jenis aplikasi yang paling umum, linear programming mempunyai banyak aplikasi penting lainnya. Sebenarnya, setiap masalah yang metode matematisnya sesuai dengan format umum bagi linear programming merupakan masalah bagi linear programming. Selanjutnya suatu prosedur penyelesaian yang sangat efisien, yang dinamakan metode simpleks, tersedia untuk menyelesaikan masalah – masalah linear programming bahkan untuk masalah yang besar sekalipun.

Linear programming merupakan proses optimasi dengan menggunakan model keputusan yang dapat diformulasikan secara sistematis dan timbul karena adanya keterbatasan dalam mengalokasikan sumber – sumber daya. Linear programming merupakan masalah pemrograman yang harus memenuhi tiga kondisi berikut ini:

1. Variabel – variabel keputusan yang terlibat harus tidak negatif
2. Kriteria – kriteria untuk memilih nilai terbaik dari variabel keputusan dapat diekspresikan sebagai fungsi linear variabel tersebut. Fungsi kriteria itu bisa disebut sebagai ”fungsi objektif”.
3. Aturan – aturan operasi yang mengarahkan proses – proses dapat diekspresikan sebagai suatu set persamaan atau pertidaksamaan linear. Set tersebut dinamakan ”fungsi pembatas”.

2. Pembuatan Model

Untuk menyelesaikan suatu masalah dapat digunakan model linear programming. Adapun langkah – langkah pemodelannya adalah sebagai berikut:

1. Menentukan variabel – variabel dari persoalan.
2. Menentukan batasan – batasan yang harus dikenakan atas variabel untuk memenuhi batasan sistem yang di modelkan.
3. Menentukan tujuan yang harus dicapai untuk menentukan pemecahan Optimal (terbaik) dari semua nilai yang layak dari variabel tersebut. Langkah – langkah pemodelan dapat diformulasikan sebagai berikut:

• Identifikasi variabel, misalnya X1, X2, dan seterusnya
• Fungsi pembatas diformulasikan
• Fungsi tujuan (baik maksimasi ataupun minimasi) dapat diformulasikan

3. Bentuk Baku Formulasi Model Linear Programing

Terdapat 4 buah karakter yang menjadi ciri dari bentuk standar, yaitu sebagai berikut :

1. Semua pembatas berupa persamaan
2. Elemen ruas kanan tiap pembatas adalah non – negatif
3. Semua variabel adalah non – negatif
4. Fungsi tujuan berjenis maksimasi atau minimasi

Pembatas yang pertidaksamaan dapat diubah menjadi persamaan dengan menambah atau mengurangi ruas kiri dengan suatu variabel non – negatif. Variabel baru ini disebut ”varibel slack”, yang harus ditambahkan ke ruas kiri bila dibentuk pertidaksamaan ≤ dan dikurangi bila bentuk pertidaksamaan ≥ variabel slack (Sj) ≥ 0 mempunyai sifat menggunakan satu satuan sumber terbatas untuk setiap satuan Sj yang terjadi, dan juga mempunyai sifat tidak mempengaruhi besaran fungsi tujuan.

Didalam menyelesaikan persoalan linear programming dengan menggunakan metode simpleks, bentuk dasar yang digunakan adalah bentuk standar. Karena itu setiap masalah linear programming harus diubah menjadi bentuk standar sebelum dapat dipecahkan dengan metode simpleks.

Hal lain yang perlu diperhatikan dalam memecahkan masalah persoalan dengan menggunakan metode simpleks adalah harus adanya variabel – variabel basis dalam fungsi pembatas untuk memperoleh solusi awal yang feasible. Untuk fungsi – fungsi pembatas dengan tanda ≤, maka variable basis dapat diperoleh dengan menambahkan varible slack atau sebaliknya. Tetapi apabila fungsi pembatas mempunyai bentuk persamaan, maka tidak selalu diperoleh varible basis. 

Untuk mendapatkan variable basis tersebut, dapat ditambahkan dengan suatu variable semu, yang disebut ”variabel artificial”. Variabel artificial adalah variable yang di tambahkan pada fungsi pembatas mempunyai hubungan persamaan untuk memperoleh basis, atau juga dapat dinyatakan sebagai satuan variable semu (palsu) yang mempunyai sifat menggunakan satu satuan sumber artificial ini mempunyai koefisien fungsi tujuan yang sangat besar, dimana harga ini dapat bernilai negatif atau positif, tergantung pada sifat fungsi tujuannya maksimasi atau minimasi:

Cn = -M ; untuk maksimasi fungsi tujuan

Cn = +M ; untuk minimasi fungsi tujuan Keterangan:

M = bilangan bulat positif yang sangat besar

Cn = koefisien fungsi tujuan untuk variabel artificial X

4. Metode Penyelesaian Grafik Model LP

Masalah LP dapat diilustrasikan dan dipecahkan secara grafik jika ia hanya memiliki dua variabel keputusan (Sri Mulyono, 2007 : 22). Meski masalah-masalah dengan dua variabel jarang terjadi dalam dunia nyata, penafsiran geometris dari metode grafis ini sangat bermanfaat dan dapat menjadi dasar untuk pembentukan metode pemecahan (solusi) yang umum melalui algoritma simpleks.

Sebagai contoh adalah masalah kombinasi produk sederhana seperti berikut. Suatu perusahaan menghasilkan dua barang meja dan kursi dengan kebutuhan sumberdaya dan harga masing-masing barang terlihat pada tabel berikut. Perusahaan ingin memaksimumkan keuntungan, disamping itu, menurut bagian penjualan, permintaan meja tidak akan melebihi 4 unit

Suatu cara sederhana untuk menggambarkan masing-masing persamaan garis adalah dengan menetapkan salah satu variabel dalam suatu persamaan sama dengan nol dan kemudian mencari nilai variabel yang lain. Misalnya untuk kendala pertama jika X1 = 0, maka 2X2 = 10 atau X2 = 5, kemudian bila X2 = 0, maka X1 = 10. kedua titik ini {(0,5) dan (10,0)} kemudian dihubungkan dengan suatu garis lurus. Dengan cara yang sama untuk kendala kedua kita peroleh titik {(0,6) dan (6,0)}.

Suatu daerah yang secara bersamaan memenuhi ketiga kendala ditunjukkan oleh area yang diarsir, yaitu area ABCDE pada grafik 2.1. Wilayah ini dinamakan ruang solusi atau solusi layak (solution space). Sementara itu pasangan nilai-nilai (X1,X2) diluar daerah ini bukan merupakan solusi layak, karena menyimpang dari satu atau lebih kendala. Contohnya, titik R dan S adalah solusi layak, sementara P dan Q bukan solusi layak.

Dari contoh diatas ada beberap hal yang dapat disimpulkan :

• Pertama, solusi optimal akan selalu terletak pada batas ruang solusi. Ruang solusi membentuk suatu convex set.
• Kedua, solusi optimum tidak hanya pada batas ruang solusi, tetapi lebih tepatnya adalah pada suatu titik pojok yang dibentuk melalui perpotongan dua kendala. Suatu perkecualian jika fungsi tujuan sejajar dengan sebuah kendala karena memiliki kemiringan yang sama.

Penyelesaian grafis untuk masalah minimasi dapat dicari dengan cara yang sama dengan masalah maksimasi. Pada umumnya solusi masalah minimasi adalah pada titik dalam batas ruang solusi yang paling dekat dengan titik asal yang disentuh oleh fungsi tujuan. Ini berarti berlawanan dengan masalah maksimasi dimana solusi optimal biasanya berada paling jauh dari titik asal yang disentuh oleh fungsi tujuan.

Pengertian Linear Programming 2017-03-03T03:32:00-08:00 Rating: 4.5 Diposkan Oleh: frf