Linier Programming

BAB II

LANDASAN TEORI

Linier Programming

2.1.        Pengertian Linear Programming

            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).

2.2.1     Formulasi Permasalahan

Urutan pertama dalam penyelesaian adalah mempelajari sistem relevan dan mengembangkan pernyataan permasalahan yang dipertimbangakan dengan jelas. Penggambaran sistem dalam pernyataan ini termasuk pernyataan tujuan, sumber daya yang membatasi, alternatif keputusan yang mungkin (kegiatan atau aktivitas), batasan waktu pengambilan keputusan, hubungan antara bagian yang dipelajari dan bagian lain  dalam perusahaan, dan lain-lain.

Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam formulasi masalah. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai.

2.2.2     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).

2.2.3     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.

2.2.4     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)

2.2.5     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.

2.2.6     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.

2.2.7     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.