LINEAR PROGRAMMING

Oleh : Tb. Ai Munandar

PENDAHULUAN

Linear Programming (LP) merupakan masalah optimasi yang memiliki fungsi dan tujuan untuk menyelesaikan sesuatu yang tidak diketahui dan memiliki batasan kendala dalam bentuk persamaan dan pertidaksamaa. Setiap batasan berbeda antara satu masalah dengan masalahn lainnya. Namun demikian, secara umum LP dapat dituliskan dalam bentuk standar sebagai berikut [1]:

Untuk kasus minimasi : c₁x₁ + c₂x₂+ ... + c_nx_n  ßFungsi Objektifnya

Batasan                       : a₁₁x₁+ a₁₂x₂ + ... + a_1nx_n                    = b₁

                                      a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n                    = b₂

                                      ...............

                                      a_mx₁ + a_m2x₂ + ... + a_mnx_n                   = b_n

dan                              x1 ≥ 0; x2 ≥ 0 ... x3 ≥ 0.

Dimana b_i, c_idan a_ij merupakan nilai konstanta, dan x_i adalah bilangan asli yang akan dicari. Fungsi objektif merupakan formulasi dari permasalahan nyata yang akan dicarikan solusinya, yang sudah diubah ke dalam bentuk matematis. Secara umum, fungsi objektif digunakan untuk menyelesaikan permasalahan minimasi, walaupun tidak menutup kemungkinan digunakan untuk permasalahan maksimasi, tergantung dari sudut pandang model LP yang sedang dibahas, misalnya apakah untuk meminimasi biaya produksi atau untuk memaksimasi jumlah produksi[2].

Setiap fungsi tujuan memiliki batasan baik dalam bentuk persamaan maupun pertidaksamaan linear yang dikombinasikan dengan variabel keputusan, sehingga dapat dituliskan :

Ada dua pendekatan yang bisa digunakan untuk mengubah batasan dari satu bentuk kebentuk lainnya, yaitu :

1.      Slack variabel

Pendekatan ini menambahkan variabel non negatif tertentu untuk mengubah batasan dari bentuk pertidaksamaan linear ke dalam bentuk persamaan linear. Perhatikan contoh di bawah ini :

Diketahui bentuk pertidaksamaan linear sebagai berikut

a₁x₁ + a₂x₂ + · · · + a_nx_n  ≤  b

pertidaksamaan di atas dapat dirubah ke dalam batasan dengan betuk persamaan linear dengan menambahkan variable slack non-negatif w, sehingga menjadi

a₁x₁+ a₂x₂ + … + a_nx_n + w = b,    w ≥ 0

2.      Surplus variabel

Pendekatan ini mengubah batasan dari bentuk persamaan linear ke dalam bentuk pertidaksamaan linear dengan menggunakan dua bentuk matematis pertidaksamaan linear baik ≤ atau ≥. Perhatikan contoh di bawah ini, bentuk dari persamaan linear

a₁x₁+ a₂x₂ + … + a_nx_n = b

Dapat diubah ke dalam bentuk pertidaksamaan linear dengan mengubah operator matematik menjadi ≤ atau ≥, sehingga bentuknya menjadi

a₁x₁+ a₂x₂ + … + a_nx_n ≤ b,  atau

a₁x₁+ a₂x₂ + … + a_nx_n ≥ b,

formulasi linear program harus dibuat ke dalam bentuk standar dengan menggunakan notasi m sebagai jumlah batasan dan notasi n sebagai jumlah variable keputusannya. Nilai spesifik yang dihasilkan untuk setiap variable keputusan disebut dengan solusi,sedangkan solusi dalam bentuk (x₁, x₂, …, xn) disebut sebagai feasible, dengan catatan, bahwa nilai feasible harus memenuhi untuk semua batasan, dan dikatakan optimal jika mencapai nilai maksimum yang diharapkan. Jika suatu permasalahan tidak menghasilkan solusi yang layak, maka permasalahan tersebut dinamakan infeasible [2].

CONTOH PENERAPAN LINEAR PROGRAMMING

1.      Linear programming digunakan untuk pencarian solusi atas permasalahan program diet. LP digunakan unuk menentukan kebutuhan diet yang tepat sehingga memenuhi nilai nutrisi minimum bagi kesehatan.

2.      Pada bidang transportasi, LP digunakan untuk meminimasi total biaya transportasi terutama dalam industry jasa pengiriman barang.

3.      Dibidang manufaktur, LP digunakan untuk meminimalkan biaya produksi sehingga mampu menghasilkan produksi maksimum.

4.      Dan masih banyak lagi penerapan LP.

FORMULASI MODEL LP

Masalah keputusan yang biasa dihadapi para analis adalah alokasi optimum sumber daya yang langka. Sumber daya dapat berupa modal, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi. Tugas analis adalah mencarihasil terbaik yang mungkin dengan adanya keterbatasan sumber daya. Hasil yang diinginkan mungkin ditunjukkan sebagai maksimasi dari beberapa ukuran seperti profit, penjualan dan kesejahteraan, atau minimasi seperti biaya, waktu dan jarak.

Setelah masalah diidentifikasikan, tujuan diterapkan, langkah selanjutnya adalah formulasi model matematikyang meliputi tiga tahap :

1.      Menentukan variabel yang tak diketahui (variabel keputusan) dan menyatakan dalam simbol matematik

2.      Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier (bukan perkalian) dari variabel keputusan

3.       Menentukan semua kendala masalah tersebut dan mengekspresikan dalam persamaan dan pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumberdaya masalah itu

REFERENSI :

[1] .      David G. Luenberger and Yinyu Ye. Linear and Non Linear Programming, 3rd Edition. Springer, 2008.

[2] .      Robert J. Vanderbei. Linear Programming : Foundation and Extention, 3rd Edition. Springer, 2008

[3] .      Lianah. Modul Pembelajaran Matematika Bisnis : Programasi Linier. Universitas Mercu Buana Jakarta. 2008