Linear Programming

Pengertian Linear Programming

Menurut Wikipedia (2009), Linear Programming merupakan suatu model umum yang dapat digunakan dalam pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukan, dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas.

Sedangkan Menurut Siringoringo (2005), linear programming merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Linear programming banyak diterapkan dalam masalah ekonomi, industri, militer, sosial dan lain-lain. Linear programming berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.

            Langkah  pertama dalam model linear programming adalah formulasi masalah, yang meliputi proses pengidentifikasi dan penentuan batasan serta fungsi tujuan. Langkah kedua adalah memecahkan masalah yang dialami. Jika terdapat hanya dua variabel keputusan, maka masalah tersebut dapat diselesaikan dengan menggunakan metode grafik. Semua permasalahan linear programming juga dapat dipecahkan dengan metode simpleks apabila terdapat tiga variabel keputusan atau lebih. Metode tersebut menghasilkan informasi yang berharga seperti harga bayangan atau harga berganda dan menyediakan analisis sensitivitas lengkap pada input lain dari permasalahan yang dipakai (Heizer, 2005).

Karakteristik yang biasa digunakan dalam persoalan linear programming adalah sebagai berikut (Siringoringo, 2005):

1.  Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, kita dapat memeriksa kelinearan menggunakan grafik (diagram pencar) ataupun menggunakan uji hipotesa. Secara teknis, linearitas ditunjukkan oleh adanya sifat proporsionalitas, additivitas, divisibilitas dan kepastian fungsi tujuan dan pembatas.

2.  Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel. Jika harga per unit produk misalnya adalah sama berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak dipenuhi.

3.  Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan. Untuk fungsi kendala, sifat additivitas dipenuhi jika nilai kanan merupakan total penggunaaan masing-masing variabel keputusan. Jika dua variabel keputusan misalnya merepresentasikan dua produk substitusi, dimana peningkatan volume penjualan salah satu produk akan mengurangi volume penjualan produk lainnya dalam pasar yang sama, maka sifat additivitas tidak terpenuhi.

4.    Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.

5.    Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.

Pembentukan Model Matematik

Tahap berikutnya yang harus dilakukan setelah memahami permasalahan optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan konvensional riset operasional untuk pemodelan adalah membangun model matematik yang menggambarkan inti permasalahan. Kasus dari bentuk cerita diterjemahkan ke model matematik. Model matematik merupakan representasi kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel keputusan. Model matematika permasalahan optimal terdiri dari dua bagian. Bagian pertama memodelkan tujuan optimasi. Model matematik tujuan selalu menggunakan bentuk persamaan. Bentuk persamaan digunakan karena kita ingin mendapatkan solusi optimum pada satu titik. Fungsi tujuan yang akan dioptimalkan hanya satu. Bukan berarti bahwa permasalahan optimasi hanya dihadapkan pada satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada bagian ini kita hanya akan tertarik dengan permasalahan optimal dengan satu tujuan.

Bagian kedua merupakan model matematik yang merepresentasikan sumber daya yang membatasi. Fungsi pembatas bisa berbentuk persamaan (=) atau pertidaksamaan (≤ atau ≥). Fungsi pembatas disebut juga sebagai konstrain. Konstanta (baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas maupun pada tujuan dikatakan sebagai parameter model. Model matematika mempunyai beberapa keuntungan dibandingakan pendeskripsian permasalahan secara verbal. Salah satu keuntungan yang paling jelas adala model matematik menggambarkan permasalahan secara lebih ringkas. Hal ini cenderung membuat struktur keseluruhan permasalahan lebih mudah dipahami, dan membantu mengungkapkan relasi sebab akibat penting. Model matematik juga memfasilitasi yang berhubungan dengan permasalahan dan keseluruhannya dan mempertimbangkan semua keterhubungannya secara simultan. Terakhir, model matematik membentuk jembatan ke penggunaan teknik matematik dan komputer kemampuan tinggi untuk menganalisis permasalahan.

Model matematik mempunyai kelemahan. Tidak semua karakteristik sistem dapat dengan mudah dimodelkan menggunakan fungsi matematik. Meskipun dapat dimodelkan dengan fungsi matematik, kadang-kadang penyelesaiannya sulit diperoleh karena kompleksitas fungsi dan teknik yang dibutuhkan. Bentuk umum linear programming adalah sebagai berikut:

Fungsi tujuan :

Maksimumkan atau minimumkan z = c₁x₁ + c₂x₂ + ... + c_nx_n

Sumber daya yang membatasi :

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = /≤ / ≥ b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = /≤ / ≥ b₂

…

a_m1x₁ + a_m2x₂ + … + a_mnx_n = /≤ / ≥ b_m

x₁, x₂, …, x_n ≥ 0

Simbol x₁, x₂, ..., x_n  (x_i) menunjukkan variabel keputusan. Jumlah variabel keputusan (x_i) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan. Simbol c₁,c₂,...,c_n merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya.Simbol a₁₁, ...,a_1n,...,a_mn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya. Simbol b₁,b₂,...,b_m menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas.

Pertidaksamaan terakhir  (x₁, x₂, …, x_n ≥ 0) menunjukkan batasan non negatif. Membuat model matematik dari suatu permasalahan bukan hanya menuntut kemampuan matematik tapi juga menuntut seni permodelan. Menggunakan seni akan membuat permodelan lebih mudah dan menarik.

Kasus linear programming sangat beragam. Dalam setiap kasus, hal yang penting adalah memahami setiap kasus dan memahami konsep permodelannya. Meskipun fungsi tujuan misalnya hanya mempunyai kemungkinan bentuk maksimisasi atau minimisasi, keputusan untuk memilih salah satunya bukan pekerjaan mudah. Tujuan pada suatu kasus bisa menjadi batasan pada kasus yang lain. Harus hati-hati dalam menentukan tujuan, koefisien fungsi tujuan, batasan dan koefisien pada fungsi pembatas.

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 (Heizer, 2005).

Asumsi  Linear programming

            Model linear programming mengandung asumsi-asumsi tertentu yang harus dipenuhi agar definisinya sebagai suatu masalah linear programming menjadi absah (Ayu, 1996). Membentuk suatu model linear programming perlu diterapkan asumsi-asumsi sebagai berikut.

1.    Liniearity

Fungsi obyektif dan kendala haruslah merupakan fungsi linier dan variabel keputusan. Tingkat peubah atau kemiringan hubungan fungsional adalah konstan.

2.    Divisibility

Solusi tidak harus bilangan bulat atau bilangan pecahan dengan demikian variabel keputusan merupakan variabel kontinu sebagai lawan dari variabel diskrit atau bilangan bulat

3.    Deterministik

Mencerminkan kondisi masa depan maupun sekarang dan keadaan masa depan sangat sulit untuk diketahui.

4.    Homogeneity

Memiliki arti yaitu sumber daya yang digunakan dalam proses harus sama

5.    Non negativity

Nilai variabel keputusan harus > 0.

6.    Semua konstanta C_j A_j B_j diasumsikan memiliki nilai yang pasti.

Syarat  Linear Programming

            Menurut Ayu (1996), linear programming dilakukan dengan syarat yang berlaku. Syarat tersebut ditentukan agar dalam penyelesaian persoalan dapat ditempuh dengan linear programming, berikut syarat linear programming.

1.    Tujuan harus jelas

2.    Ada benda alternatif yang akan dibandingkan

3.      Sumber daya terbatas

4.     Bisa dirumuskan secara kuantitatif

5.     Adanya keterkaitan peubah (kendala harus sama, bahan baku harus sama atau keterkaitan)

Metode-Metode Linear Programming

            Linear programming dapat dilakukan dengan menggunakan beberapa macam metode sesuai dengan tingkat persoalannya (Siringoringo, 2005). Metode-metode tersebut sama-sama dapat memecahkan persoalan yang mengandung beberapa permasalahan. Berikut ini metode yang dapat dilakukan dalam memecahkan persoalan linear programming.

1.      Metode aljabar yaitu mempunyai bentuk perhitungan formulasi standard dengan  mengkombinasi dua variabel yang nilainya dianggap nol hingga diperoleh nilai z terbesar.

2.     Metode grafik yaitu metode yang digunakan untuk memecahkan persoalan yang mengandung dua permasalahan.

3.        Metode simpleks dapat digunakan untuk memecahkan persoalan yang mengandung tiga atau lebih permasalahan dan didasarkan pada proses perhitungan ulang supaya mendapat hasil yang optimal.

4.   Metode big-m biasanya dipakai untuk memecahkan persoalan yang memiliki pembatas “=” atau “>”

Pengolahan data yang dibuat hanya menggunakan dua metode yaitu menggunakan metode grafik dan simpleks. Berikut ini penjelasan untuk metode grafik dan metode simpleks.

Metode Grafik

            Metode grafik adalah suatu metode yang ada dalam linear programming yang digunakan untuk memecahkan persoalan yang mengandung dua permasalahan. Prosedur umumnya adalah untuk mengubah suatu deskriptif kedalam bentuk masalah linear programming dengan menentukan variabel, konstanta, fungsi objektif dan batasan kendala.  Pada metode grafik dilakukan beberapa tahapan, yaitu (Ayu, 1996):

1.    Indetifikasi variabel keputusan.

2.     Identifikasi fungsi objektif.

3.     Identifikasi kendala-kendala.

4.     Menggambarkan bentuk grafik dari semua kendala.

5.     Indentifikasi daerah solusi yang layak pada grafik.

6.     Menggambarkan bentuk grafik dari fungsi objektif dan menentukan titik yang memberikan nilai objektif optimal pada daerah solusi yang layak.

7.     Mengartikan solusi yang diperoleh.

Metode Simpleks

            Metode simpleks adalah salah satu metode yang ada dalam linear programming yang digunakan untuk memecahkan persoalan yang mengandung tiga permasalahan atau lebih dan didasarkan pada proses perhitungan ulang supaya mendapat hasil yang optimal. Tahap paling awal yang diperhatikan dalam metode simpleks ini adalah tiga tahap yang dilakukan pada linear programming yaitu: 

1.    Masalah harus dapat diidentifikasi sebagai sesuatu yang dapat diselesaikan dengan linear programming. 

2.    Masalah yang tidak terstruktur harua dapat dirumuskan dalam model matematika, sehingga menjadi terstruktur.

3.    Model harus diselesaikan dengan teknik matematika yang dibuat

Tahap selanjutnya merupakan tahap teknis yang secara umum ada dalam linear programming (Ayu, 1996). Tahap tersebut akan dijelaskan sebagai berikut:

1.    Menentukan variabel keputusan, dimana maksud dari variabel keputusan ini merupakan simbol matematika yang menggambarkan tingkatan aktivitas perusahaan. Tahap ini sebenarnya untuk mempermudah dalam menggunakan metode matematik, dengan memutuskan memakai simbol matematik untuk hal yang ingin dihitung.

2.  Membuat fungsi tujuan, yang dimaksudkan dari fungsi tujuan ini adalah hubungan matematika linier yang menjelaskan tujuan perusahaan dalam terminologi variabel keputusan. Setelah ditentukan variabel keputusan, kemudian digunakan dalam membuat fungsi (persamaan matematika) dari tujuan yang ingin dicapai perusahaan.

3.     Membuat batasan (kendala) model, maksud dari fungsi batasan adalah hubungan linier dari variabel keputusan yang menunjukkan keterbatasan perusahaan dalam lingungan operasi perusahaan.

Pemodelan Persoalan Linear Programming

Model LP terdiri dari beberapa Decision Variables, sebuah objective function dan beberapa constraints.  Sebagai langkah awal dalam membuat model LP harus ditentukan Deecision Variables.  Yang dimaksud dengan decision variables disini adalah simbol-simbol matematik yang mewakili banyaknya kegiatan dalam suatu proses operasi.

Sebagai contoh, suatu perusahaan pembuat barang elektronik memproduksi Radio, TV dan VCD-Player.  Jumlah tiap-tiap barang yang diproduksi diberi simbol-simbol X₁, X₂, dan X₃.  Simbol-simbol matematik tersebut mewakili produknya.

X₁ = jumlah radio yang diproduksi,

X₂ = jumlah TV yang diproduksi, dan

X₃ = jumlah VCD-Player yang dihasilkan.

Berdasarkan perubah (decision variables) yang sudah dipilih, semua constraints dan objective function kemudian diekspresikan menggunakan perubah-perubah tersebut.

Untuk objective function, selalu ditulis dalam bentuk maximise atau minimise dari fungsi yang akan di maksimalkan atau dimimalkan.  Sebagai contoh, apabila keuntungan yang diperoleh dari penjualan satu Radio Rp6000, satu TV Rp4000, dan satu VCD-Player Rp2000, maka objective function untuk mencari keuntungan terbesar ditulis

Maximise  6000 X₁ + 4000 X₂ + 2000 X₃ .

Perubah yang sama juga digunakan untuk penulisan constraints.  Constraints dapat berupa pernyataan keterbatasan sumber daya, bisa juga berupa panduan.  Sebagai illustrasi misalnya setiap Radio memerlukan waktu pengerjaan 2 jam sementara untuk TV hanya 1 jam, sedangkan untuk VCD-Player 1.5 jam.  Adapun sumber daya waktu yang tersedia hanya 40 jam kerja.  Dengan demikian constraint nya dituliskan dalam bentuk

2 X₁ + 1 X₂ + 1.5 X₃ £ 40

Selain itu harus pula dipenuhi bahwa X₁, X₂, dan X₃ harus merupakan bilangan bulat (integer) karena produk Radio, TV dan VCD-Player tidak bisa dalam bentuk angka pecahan (real).  Ditulis dengan simbol: X₁, X₂, X₃ bilangan bulat

Dari illustrasi diatas, maka bentuk umum model LP sebagai berikut:

Maximise (or Minimise)

c₁ x₁ + c₂ x_{2 + … +} c_n x_n

Subject to:

a₁₁ x₁ + a₁₂ x_{2 + … +} a_1n x_n ( £ or = or ³) b₁

a₂₁ x₁ + a₂₂ x_{2 + … +} a_2n x_n ( £ or = or ³) b₂

a_n1 x₁ + a_n2 x_{2 + … +} a_nn x_n ( £ or = or ³) b_n

x_i : decision variables,

b_i : constraint levels,

c_i : objective function coefficients,

a_ij : constraint coefficients.

Teori Penyelesaian Linear Programming

Untuk memudahkan pemahaman LP, diberikan contoh kasus sederhana yang bisa digambarkan secara grafik dan secara komputasi tidak rumit.

Studi Kasus 5-1:

Sebuah perusahaan garmen di Klaten, PT Sarjono, memproduksi baju lengan pendek dan baju lengan panjang.  Perusahan tersebut mempunyai sumber daya utama yaitu penjahitan (bagian jahit) dan pemotongan (bagian pola).  Untuk usaha di bulan depan PT Sarjono mengalokasikan waktu yang disediakan di bagian jahit 240 jam kerja dan di bagian potong 100 jam kerja.

Berdasarkan catatan pekerjaan sebelumnya sudah diperoleh data untuk pembuatan satu pakaian lengan panjang menghabiskan waktu 2 jam pemotongan dan 4 jam penjahitan.  Pembuatan baju lengan pendek memerlukan 1 jam pemotongan dan 3 jam penjahitan.

Data keuntungan setiap baju lengan panjang Rp700 dan lengan pendek Rp500.

PT Sarjono ingin mengetahui jumlah produksi baju (lengan panjang dan lengan pendek) di bulan depan yang menghasilkan keuntungan sebesar-besarnya dengan keterbatasan sumber daya yang tersedia.

Penyelesaian Studi Kasus 5-1:

Untuk penyelesaian diatas, terlebih dahulu persoalan dibuat model matematik kemudian diselesaikan persamaan simultannya.  Adapun langkah penyelesaiaannya sebagai berikut:

·         Produk yang dicari harga optimalnya (decision variables) dituliskan dalam simbol matematik terlebih dahulu

X : Jumlah baju lengan panjang yang akan diproduksi,

Y : Jumlah baju lengan pendek yang akan diproduksi.

·         Menuliskan objective function dengan cara memformulasikan yang akan dimaksimalkan atau diminimalkan:

Keuntungan total yang diperoleh PT Sarjono sebesar

700 x baju lengan panjang + 500 x baju lengan pendek

Objective funtion :              Maximise 700 X + 500 Y

·         Menuliskan constraints:

PT Sarjono mempunyai dua keterbatasan sumber daya:

Penjahitan:               4 X + 3 Y £ 240

Pemotongan:           2 X + 1 Y £ 100

Persyaratan lain : Hasil perhitungan harus positif dan angkanya bukan pecahan:

X, Y ³ 0          dan X,Y integer (bilangan bulat)

Daerah feasible 4 X + 3 Y £ 240; 2 X + 1 Y £ 100; X, Y ³ 0

·         Mencari harga optimal objective function di dareah feasible

Salah satu cara termudah untuk mencari harga maksimal dari objective function di daerah feasible adalah dengan melakukan analisis di titik-titik sudut, yang diwakili pada titik A, B,C dan D.

Titik A (X=0, Y=0)             : 700 .0 + 500 . 0 = 0

Titik B (X=50, Y=0)           : 700 . 50 + 500 . 0 = 35000

Titik D (X=0, Y=80)           : 700.0 + 500 . 80 = 40000

Untuk menentukan titik C diperoleh dengan cara menyelesaikan dua persamaan simultan

4 X + 3 Y = 240          (i)

2 X + 1 Y = 100          (ii)

Terlebih dahulu kalikan persamaan (ii) dengan –2, menjadi

4 X + 3 Y = 240

-4 X -2 Y = -200

1 Y = 40

Dengan menggunakan Y =40 akan diperoleh X =30

Titik C (X=30, Y=40)         : 700 . 30 + 500 . 40 = 41000

Dari perbandingan di keempat titik dapat disimpulkan bahwa harga keuntungan terbesar akan diperoleh apabila diproduksi sebanyak 30 pakaian lengan panjang dan 40 pakaian lengan pendek.  Adapun keuntungan maksimal yang diperoleh sebesar Rp 41000,-.

http://f-blue.blogspot.com/2011/06/linier-programming.html

http://lagaknya.blogspot.com/2010/09/linear-programming.html

http://chedjam.wordpress.com/2011/03/26/program-linier/