Operations Research

Operations Research


Operations Research yang berasal dari Inggris merupakan suatu hasil studi operasi – operasi militer selama perang dunia II. Setelah perangs selesai, potensi komersialnya segera disadari dan pengembangannya telah menyebar dengan cepat di Amerika Serikat. Kini, OR banyak diterapkan untuk menyelesaikan masalah-masalah manajemen, namun tidak jarang perusahaan – perusahaan yang melaporkan kegagalan dalam penerapan OR karena bermacam-macam alasan.


Programma Linier
Levin et. al (1995) menyatakan bahwa programma linier merupakan teknik matematika untuk mendapatkan alternatif penggunaan terbaik (optimum) atas sumber – sumber organisasi.
Dunn (1981) menyatakan bahwa programma linier merupakan penyajian teoritis secara sederhana mengenai hubungan antara dua atau lebih variabel bebas (dinamakan tujuan), dengan menggunakan kendala (batas atas dan batas bawah) nilai – nilai dari variabel tersebut.
Welch dan Commer (1983) menyatakan programma linier merupakan teknik untuk menghitung kombinasi optimum dari sumber – sumber tertentu agar dapat tercapai tujuan yang semaksimal mungkin sebagaimana yang telah ditetapkan sebelumnya.
Levin et. al (1995), menyatakan penggunaan programma linier sebagai teknik pengambilan keputusan menggunakan tiga tahap proses, yaitu :
1. Perumusan masalah; mengumpulkan informasi yang sesuai, mempelajari pertanyaan apa yang harus dijawab, dan membuat permasalahan ke dalam bentuk programma linier
2. Pemecahan masalah; mencari pemecahan optimal programma linier
3. Interpretasi dan penerapan solusi; pemeriksaan bahwa solusi dari programma linier sudah benar (dan bila tidak, harus kembali ke tahap 1 dan memperbaiki rumusannya), mengerjakan analisa sensitivitas yang cocok dan menerapkan ke dalam praktek.

Levin et. al (1995) menyatakan bahwa persyaratan utama dalam pemecahan masalah programma linier adalah :
1. Memiliki tujuan. Umumnya tujuan utama dari sebuah programma linier berupa bentuk memaksimasi keuntungan (laba) dan atau meminimasi biaya. Disadari bahwa bentuk trend (kecenderungan) keuntungan dan biaya tidak selalu berhubungan secara linier dengan volume penjualan atau jumlah produksi.
2. Harus ada alternatif tindakan yang salah satu darinya akan mencapai tujuan. Sebagai contoh, suatu perusahaan harus mengalokasikan kapasitasnyadalam suatu bentuk perbandingan, misalnya 50:50, 25:75, to:30 atau dalam angka perbandingan lainnya.
3. Sumber yang diperhitungkan dalam model merupakan persediaan terbatas. Misalnya sebuah perusahaan mempunyai jumlah mesin, sumber daya manusia, waktu, dan sumber daya – sumberdaya lainnya yang terbatas; dalam perusahaan konveksi fenomena ini dapat diamati melalui sebuah fungsi sebab-akibat, untuk perusahaan yang membuat dua produk, celana dan baju; semakin banyak waktu digunakan untuk membuat celana semakin sedikit baju yang dapat dibuat.
4. Tujuan dan segenap keterbatasannya dinyatakan dalam bentuk persamaan atau pertidaksamaan matematika (formulasi matematika), dan harus ada persamaan atau pertidaksamaan linier.


ASUMSI PROGRAMMA LINIER
Untuk dapat menyelesaikan pemecahan masalah programma linier terdapat beberapa asumsi /persyaratan utama yang harus dipenuhi seperti yang dikemukakan Priyarsono (1999), Levin et. al. (1992) dan Supranto (1991) yaitu :
1. Fungsi objektif harus didefinisikan secara jelas dan dinyatakan sebagai fungsi objektif yang linear.
2. Harus ada alternatif tindakan/pemecahan untuk dipilih menjadi yang terbaik.
3. Sumber dan aktivitas yang diperhitungkan dalam model mempunyai jumlah terbatas (finiteness).
4. Tujuan dan segenap keterbatasannya dinyatakan dalam bentuk persamaan atau pertidaksamaan matematika (formulasi matematika), dan harus ada persamaan atau pertidaksamaan linier.
5. Sumbangan tiap kegiatan terhadap nilai fungsi tujuan Z diassumsikan sebanding (proporsional) dengan taraf kegiatan xj, sebagaimana terungkap pada suku cjxj dalam fungsi tujuan. Demikian pula suku aijxj dalam kendala, sumbangan tiap kegiatan terhadap kendala proporsional dengan taraf kegiatan tersebut.
6. Sumber-sumber dan aktivitas mempunyai sifat dapat dibagi (divisibilitas).
7. Sumber-sumber dan aktivitas mempunyai sifat dapat ditambahkan (aditivitas)
8. Variabel keputusan harus positif, tidak boleh negatif (Xj > 0, untuk semua j).
9. Model programming deterministic, artinya sumber dan aktivitas diketahui secara pasti (single-valued expectations).

Metoda Transportasi
Menurut Budiarto (1993), distribusi adalah kegiatan pemasaran yang berusaha memperlancar serta mempermudah penyampaian produk atau jasa dari produsen kepada konsumen, sehingga penggunaannya sesuai (jenis, jumlah, harga, tempat, dan saat) dengan yang diperlukan. Distribusi yang efektif akan memperlancar arus atau akses barang oleh konsumen sehingga mudah dalam memperolehnya.
Menurut Yamit (1996), metoda transportasi merupakan masalah khusus model linier program yang dapat digunakan untuk menyelesaikan masalah distribusi, masalah lokasi pabrik, masalah penugasan, masalah skedul produksi dan lain sebagainya. Karena sifat khusus tersebut, metoda transportasi berusaha mendapatkan solusi dengan biaya minimum.
Menurut Yamit (1996), persyaratan yang harus dipenuhi untuk menyelesaikan berbagai masalah tersebut adalah:
1. Adanya tempat asal (i) yang dapat berupa pabrik, pekerja, kapasitas produksi dan lain sebagainya sesuai dengan masalah yang dihadapi.
2. Adanya tempat tujuan (j) yang dapat berupa lokasi gudang, lokasi pemasaran, jenis pekerjaan, skedul permintaan dan lain sebagainya.
3. Adanya biaya alokasi per unit (cij) dari tempat asal (i) ke tempat tujuan (j).
4. Adanya jumlah barang (ai) di tempat asal (i).
5. Adanya jumlah permintaan (bj) di tempat tujuan (j).
6. Adanya keseimbangan jumlah barang yang tersedia dengan jumlah permintaan.
Menurut Dimyati (2003), untuk menyelesaikan persoalan transportasi, harus dilakukan langkah-langkah sebagai berikut:
1. Menentukan solusi fisibel basis awal
Ada tiga metoda yang biasa digunakan untuk menentukan solusi fisibel basis awal ini, yaitu:
a. Metoda pojok kiri atas-pojok kanan bawah (northwest corner). Caranya adalah sebagai berikut:
Mulai dari pojok kiri atas, alokasikan sebanyak x11 = min (a1, b1). Artinya: jika b1 < a1 maka x11 = b1 ; jika b1 > a1, maka x11 = a1. jika x11 = b1, maka selanjutnya akan mendapatkan giliran untuk dialokasikan adalah x12 sebesar min (a1 – b1, b2); jika x11 = a1 (atau b1 > a1), maka selanjutnya yang mendapat giliran untuk alokasi adalah x12 sebesar min(b1 – a1, a2). Demikian seterusnya.
b. Metoda ongkos terkecil (least cost)
Prinsip cara ini adalah pemberian prioritas pengalokasian pada tempat yang mempunyai satuan ongkos terkecil.
Langkah-langkah prosedur metoda ongos terkecil atau biaya minimum adalah:
1) Alokasi pertama dimulai dari sel yang memiliki biaya terkecil, pilih salah satu dari daerah asal ke daerah tujuan.
2) Pilih biaya terkecil berikutnya, demikian seterusnya sampai semuanya dapat dialokasikan pada tiap-tiap daerah asal.
3) Jika jumlah sel tidak memenuhi kriteria (m + n – 1), maka diperlukan sel basis semu atau dummy yang dipilih secara bebas dari sel nonbasis dengan jumlah alokasi nol.
c. Metoda pendekatan VAM (Vogel’s Approximation Method)
Metoda ini merupakan sebuah heuristik dari biasanya memberikan pemecahan awal yang lebih baik daripada metoda barat laut atau metoda ongkos terkecil. Pada kenyataanya, VAM umumnya menghasilkan pemecahan awal yang optimum, atau lebih dekat dengan optimum.
Langkah-langkah dari prosedur ini adalah sebagai berikut:
1) Evaluasi penalti untuk setiap baris (kolom) dengan mengurangkan elemen biaya terkecil dalam baris (kolom) dari elemen biaya terkecil berikutnya dalam baris (kolom) yang sama.
2) Identifikasi baris atau kolom dengan penalty terbesar, pilih nilai yang sama secara sembarang. Alokasikan sebanyak mungkin pada variabel dengan biaya terendah dari baris atau kolom yang dipilih. Sesuaikan penawaran dan permintaan dan silang baris atau kolom yang dipenuhi. Jika sebuah baris dan kolom dipenuhi secara bersamaan, hanya satu di antaranya yang disilang dan baris (kolom) sisanya diberikan penawaran (permintaan) nol. Setiap baris atau kolom dengan penawaran atau permintaan nol tidak boleh dipergunakan dalam penalty berikutnya (dalam langkah 3).
3) a) Bila tinggal 1 kolom atau baris yang belum disilang atau ditandai, berhentilah.
b) Bila tinggal 1 kolom atau baris dengan supply atau demand positif yang belum ditandai, tentukan variabel basis pada kolom atau baris dengan cara ongkos terkecil (least cost).
c) Bila semua baris dan kolom yang belum ditandai mempunyai supply dan demand sama dengan nol, tentukan variabel-variabel basis yang berharga nol dengan cara ongkos terkecil. Kemudian berhentilah.
d) Jika 3a, b dan c tidak terjadi, hitung kembali penalty untuk baris atau kolom yang belum ditandai. Kembali ke tahap 2.
2. Menentukan Solusi Optimal [MODI]
Metoda MODI dapat diringkas dalam langkah-langkah berikut :
a. Tentukan nilai-nilai Ui untuk setyiap baris dan nilai – nilai Vj untuk setiap kolom dengan menggunakan hubungan cij = Ui + Vj untuk semua variabel basis dan tetapkan nilai nol untuk U1.
b. Hitung perubahan biaya Cij, untuk setiap variabel non basis dengan menggunakan rumus Cij = cij – Ui – Vj.
c. Jika terdapat nilai Cij negatif, solusi belum optimal. Pilih variabel Xij dengan nilai Cij negatif terbesar sebagai entering variabel.
d. Alokasikan barang ke entering variabel Xij sesuai proses stepping stone. Kembali ke langkah 1.












Contoh Perhitungan

A. Metoda Solusi Awal

Metode North – West Corner

Ke
Dari 1 2 3 Supply
1 120 8 5 6 120

2 30 15 50 10 12 80

3 3 20 9 60 10 80

Demand 150 70 60 280

Total Biaya : [8 x 120] + [15 x 30] + [ 10 x 50] + [9 x 20] + [10 x 60] = 2690.


Metoda Least Cost

Ke
Dari 1 2 3 Supply
1 8 70 5 50 6 120

2 70 15 10 10 12 80

3 80 3 9 10 80

Demand 150 70 60 280

Total Biaya : [5 x 70] + [6 x 50] + [ 15 x 70] + [12 x 10] + [3 x 80] = 2.060



Metoda VAM

Iterasi 1:
Ke
Dari 1 2 3 Supply Penalty Cost Baris
1 8 5 6 120 1

2 15 10 12 80 2

3 80 3 9 10 80 6

Demand 150 70 60 280
Penalty Cost Kolom 5 4 4

Iterasi 2:
Ke
Dari 1 2 3 Supply Penalty Cost Baris
1 70 8 5 6 120 1

2 - 15 10 12 80 2

3 80 3 - 9 - 10 80 -

Demand 150 70 60 280
Penalty Cost Kolom - 5 6

Iterasi 3:
Ke
Dari 1 2 3 Supply
1 70 8 5 50 6 120

2 - 15 70 10 10 12 80

3 80 3 - 9 - 10 80

Demand 150 70 60 280

Total Biaya : [8 x 70] + [6 x 50] + [ 10 x 70] + [12 x 10] + [3 x 80] = 1.920

B. Metoda Solusi Optimal

1. Solusi awal : VAM

V1 = 8 V2 = 4 V3 = 6
Ke
Dari 1 2 3 Supply
U1 = 0 1 70 8 5 50 6 120

U2 = 6 2 15 70 10 10 12 80

U3 = -5 3 80 3 9 10 80

Demand 150 70 60 280

2. Solusi Optimal : MODI

X11 : U1 + V1 = C11 = 8
X13 : U1 + V3 = C13 = 6
X22 : U2 + V2 = C22 = 10
X23 : U2 + V3 = C23 = 12
X31 : U3 + V1 = C31 = 3

Misalkan : U1 = 0
Maka :
U1 + V1 = 8
0 + V1 = 8
V1 = 8

U3 + V1 = 3
U3 + 8 = 3
U3 = 3 – 8
U3 = -5

U1 + V3 = 6
V3 = 6

U2 + V3 = 12
U2 + 6 = 12
U2 = 6

U2 + V2 = 10
6 + V2 = 10
V2 = 4
Jadi :
U1 = 0
U2 = 6
U3 = -5

V1 = 8
V2 = 4
V3 = 6

Cij = cij – Ui – Vj

C12 = c12 – u1 – v2
C12 = 5 – 0 – 4 = + 1

C21 = c21 – U2 – V1
C21 = 15 – 6 – 8 = + 1

C32 = c32 – U3 – V1
C32 = 9 – (-5) – 4 = + 10

C33 = c33 – U3 – V3
C33 = 10 – (-5) – 6 = + 9

Karena Cij sudah positif semuanya, maka solusi sudah optimal!!!


Ke
Dari 1 2 3 Supply
1 70 8 5 50 6 120

2 - 15 70 10 10 12 80

3 80 3 - 9 - 10 80

Demand 150 70 60 280

Total Biaya : [8 x 70] + [6 x 50] + [ 10 x 70] + [12 x 10] + [3 x 80] = 1.920