BAB 2
LANDASAN TEORI
2.1 Pengertian Program Linier (Linear Programming)
Menurut Sri Mulyono (1999), Program Linier (LP) merupakan metode matematik dalam mengalokasikan sumber daya yang langka untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan dan meminimumkan biaya. LP berkaitan dengan penjelasan suatu dunia nyata sebagai suatu model matematik yang terdiri atas sebuah fungsi tujuan linier dan sistem kendala linier.
Adapun menurut Pangestu Subagyo (1986), Linear Programming merupakan suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber- sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas.
Tujuan dari penyelesaian masalah program linier adalah untuk mencapai optimasi, yaitu memaksimumkan keuntungan dan meminimumkan biaya. Adapun beberapa cara atau metode pemecahan yang dapat digunakan antara lain penyelesaian dengan metode grafik dan metode simpleks. Metode grafik dapat digunakan pada masalah program linier yang hanya memiliki dua variabel keputusan saja. Bila melibatkan lebih dari dua variabel maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks. Metode simpleks merupakan suatu cara yang lazim digunakan untuk menentukan kombinasi optimal dari tiga variabel atau lebih.
Universitas Sumatera Utara
Akan tetapi, ada sejumlah persoalan program linier yang dapat dipecahkan dengan menggunakan prosedur perhitungan lain yang lebih efisien daripada metode simpleks. Salah satu diantaranya adalah metode transportasi. Metode transportasi lebih efisien dalam memecahkan persoalan transportasi dan persoalan penugasan, yang merupakan bentuk khusus dari persoalan transportasi.
2.2 Metode Transportasi 2.2.1 Definisi Metode Transportasi
DEFINISI 1: Metode transportasi adalah suatu metode yang digunakan untuk mengatur distribusi dari sumber-sumber yang menyediakan produk ke tempat tujuan secara optimal. Distribusi dilakukan sedemikian rupa sehingga permintaan dari beberapa tempat tujuan dapat dipenuhi dari beberapa sumber yang ada. Alokasi ini dilakukan dengan mempertimbangkan biaya pengiriman yang beragam karena jarak dan kondisi antar lokasi yang berbeda, (Herjanto, 1999).
DEFINISI 2: Metode transportasi pertama kali diformulasikan sebagai suatu prosedur khusus untuk mendapatkan biaya minimum. Dalam mendistribusikan unit yang homogen dari pabrik yang memiliki sejumlah penawaran ke beberapa tujuan yang memiliki sejumlah permintaan, setiap sumber memiliki kapasitas tertentu dan setiap tujuan memiliki kebutuhan yang berbeda-beda (Levin, 2002).
DEFINISI 3: Metode transportasi berhubungan dengan distribusi suatu produk tunggal dari beberapa sumber dengan penawaran terbatas, menuju beberapa tujuan, dengan permintaan tertentu, pada biaya transpor minimum. Karena hanya ada satu macam barang, suatu tempat tujuan dapat memenuhi permintaannya dari satu atau lebih sumber (Mulyono, 1991).
Universitas Sumatera Utara
DEFINISI 4: Metode
transportasi
merupakan
salah
satu
teknik
manajemen
dalam
mendistribusikan produk dari gudang ke tempat yang dituju (Sarjono, 2010).
Dari beberapa definisi tersebut dapat disimpulkan bahwa metode transportasi merupakan suatu metode yang dapat digunakan untuk menentukan pengalokasian yang paling efektif dari sumber ke tujuan sehingga biaya yang dikeluarkan minimum.
2.2.2 Persoalan Transportasi
Pada umumnya, persoalan transportasi berkaitan dengan pendistribusian suatu produk dari sumber ke titik-titik tujuan yang membutuhkan secara optimal dengan tujuan mendapatkan biaya ditribusi yang minimum. Untuk mendapat biaya yang minimum, maka alokasi produk harus diatur sedemikian rupa, karena terdapat perbedaan biaya-biaya alokasi, baik dari sumber ke tujuan atau sebaliknya.
Persoalan transportasi memiliki beberapa ciri yang perlu diketahui sebagai berikut: 1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu. 2. Jumlah atau kuantitas barang yang didistribusikan dari setiap sumber dan yang diminta oleh setiap tujuan adalah tertentu. 3. Jumlah atau kuantitas barang yang dikirim dari suatu sumber ke suatu tujuan sesuai dengan permintaan atau kapasitas sumber. 4. Biaya transportasi dari suatu sumber ke suatu tujuan adalah tertentu.
Adapun data yang dibutuhkan dalam metode transportasi mencakup: 1. Tingkat penawaran di tiap sumber dan jumlah permintaan di tiap tujuan. 2. Biaya transportasi per unit barang dari tiap sumber ke tiap tujuan.
Universitas Sumatera Utara
2.2.3 Keseimbangan Transportasi
Suatu masalah transportasi dikatakan seimbang (balanced program) apabila jumlah penawaran sama dengan jumlah permintaan. Dapat dituliskan: π
π
β ππ = β bj π=π
π=π
Kenyataannya, kasus seimbang tidak selalu terjadi. Pada umumnya, masalah yang lebih sering terjadi adalah permasalahan tak seimbang dimana penawaran (supply) lebih besar dari permintaan (demand) atau sebaliknya. Dalam kasus masalah tak seimbang metode solusi transportasi mebutuhkan sedikit modifikasi yaitu
dengan
menambahkan
kolom
dummy
atau
baris
dummy
untuk
menyeimbangkan penawaran dengan permintaan.
Jika permintaan (demand) melebihi penawaran (supply) maka dibuat sumber dummy yang akan memenuhi kekurangan tersebut sebanyak π
π
β ππ β β ππ π=1
π=1
Sebaliknya, jika penawaran (supply) melebihi permintaan (demand) maka dibuat sumber dummy yang akan menyerap kelebihan tersebut sebanyak π
π
β ππ β β ππ π=1
π=1
Biaya transportasi per unit barang dari sumber dummy ke seluruh tujuan adalah nol karena alokasi tersebut tidak mempengaruhi solusi dan pada kenyataanya tidak terjadi pengiriman dari sumber dummy.
2.2.4 Model Permasalahan Transportasi
Dalam perkembangannya, model transportasi telah diterapkan pada berbagai macam organisasi bisnis. Pemecahan kasus-kasus dengan model transportasi telah mengakibatkan penghematan yang cukup signifikan.
Universitas Sumatera Utara
Tujuan dari model transportasi adalah merencanakan pengiriman dari sumbersumber ke tujuan sedemikian rupa untuk meminimumkan total biaya transportasi, dengan kendala-kendala: 1. Setiap permintaan tujuan terpenuhi. 2. Sumber tidak mungkin mengirim komoditas lebih besar dari kapasitasnya.
Dalam menggambarkan masalah transportasi, perlu digunakan istilah-istilah yang tidak khusus karena masalah transportasi adalah masalah yang umum, yaitu pendistribusian berbagai komoditi dari berbagai kelompok pusat penerima yang disebut tujuan, sedemikian rupa hingga meminimalisasi biaya distribusi total. Secara umum, sumber π (π = 1,2, β¦ , π) mempunyai supply yaitu unit barang yang akan didistribusikan ke tujuan-tujuan dan tujuan π (π = 1,2, β¦ , π) mempunyai permintaan yaitu unit barang yang akan dikirim dari sumber-sumber. Asumsi dasar metode transportasi ini adalah biaya mendistribusikan unit-unit dari sumber i ke tujuan j berbanding langsung dengan jumlah yang didistribusikan, dimana πΆππ menyatakan biaya per unit barang yang didistribusikan.
Suatu masalah transportasi dapat dimodelkan secara matematis, yaitu dengan membentuk fungsi tujuan. Fungsi tujuan tersebut menunjukkan biaya transportasi dari sumber i ke tujuan j, maka model program linier untuk permasalahan transportasi dapat diformulasikan sebagai berikut. Fungsi tujuan :
Dengan kendala
π Meminimumkan π = βπ π=1 βπ=1 πΆππ πππ
:
βππ=1 πππ = ππ ; π = 1,2, β¦ , π βπ π=1 πππ = ππ ; π = 1,2, β¦,
Keterangan: πΆππ = biaya transportasi per unit barang dari sumber i ke tujuan j πππ = jumlah barang yang didistribusikan dari sumber i ke tujuan j ππ = jumlah barang yang ditawarkan atau kapasitas dari sumber i ππ = jumlah barang yang diminta atau dipesan oleh tujuan j
Universitas Sumatera Utara
π = banyaknya sumber π = banyaknya tujuan
Gambar berikut menjelaskan bahwa terdapat tiga sumber dalam sebuah perusahaan, yaitu π1 , π2 , dan π3 . Dari ketiga sumber tersebut dapat dikirimkan ke tujuan π1 , π2 , dan π3 . Garis yang menghubungkan sebuah sumber dan sebuah tujuan mewakili rute pengiriman barang tersebut. Jumlah penawaran di sumber i adalah ππ , dan permintaan di tujuan j adalah ππ . Biaya unit transportasi antara sumber i dan tujuan j adalah ππ . Berikut adalah ilustrasi model transportasi. SUMBER
TUJUAN π11
π1
π1
π12 π13 π21
π22
π2
π2
π31 π32 π3
π3 π33
Gambar 2.1 Model Transportasi
Universitas Sumatera Utara
Formulasi program linier dari model diatas adalah: Minimumkan: π = πΆ11 π11 + πΆ12 π12 + πΆ13 π13 + πΆ21 π21 + πΆ22 π22 + πΆ23 π23 + πΆ31 π31 + πΆ32 π32 + πΆ33 π33
Dengan batasan: π11 + π12 + π13 = π1 π21 + π22 + π23 = π2 π31 + π32 + π33 = π3 π11 + π21 + π31 = π1 π12 + π22 + π32 = π2 π13 + π23 + π33 = π3
Dari formula program linier diatas dapat dilihat bahwa tiap variabel berada dalam dua batasan sumber dan tujuan. Selanjutnya, koefisien variabel selalu positif 1. Sifat khusus model ini mengakibatkan penggunaan metode solusi khusus, dalam hal ini metode transportasi, lebih baik dan efisien dibanding metode simpleks.
Karena bentuk masalah transportasi yang khas, maka masalah transportasi dapat ditempatkan dalam suatu tabel khusus yang dinamakan tabel transportasi. Sumber ditulis dalam baris-baris dan tujuan dalam kolom-kolom. Tabel tersebut memiliki m x n kotak. Biaya transportasi per unit barang πΆππ dicatat pada kotak kecil di bagian kanan atas setiap kotak. Permintaan dari setiap tujuan terdapat pada baris paling bawah, sementara penawaran setiap sumber dicatat pada kolom paling kanan. Kotak pojok kiri bawah menunjukkan kenyataan bahwa penawaran sama dengan permintaan (S = D). Variabel πππ pada setiap kotak menunjukkan jumlah barang yang diangkut dari sumber i ke tujuan j. Bentuk umum dari tabel transportasi dapat dilihat pada tabel berikut.
Universitas Sumatera Utara
Tabel 2.1 Persoalan Transportasi Tujuan Dari / Ke
Supply
Demand
β¦
ππ1
π2π
πΆππ
πππ
π·2
β¦
...
β¦
ππ
πππ
πΆππ
πππ
ππ2
π·1
πΆππ
β¦
πΆππ
πΆπ2
π2
π2π
β¦
β¦
ππ2
πΆπ1
πΆ2π
πΆ2π
π·π
β¦
πΆπ2
π1
π1π
β¦
β¦
β¦
π22
ππ1
m
πΆ22
πΆπ1
πΆ1π
π1π
πΆ21
n
πΆ1π
π12
π21
β¦
j
πΆ12
β¦
β¦
π11
i
β¦
Sumber
2
πΆ11
β¦
1
β¦
2
β¦
1
ππ
πππ β¦
π·π
β Si = β Dj
2.3 Metode Pemecahan Masalah Transportasi 2.3.1 Penentuan Solusi Awal
Ada beberapa metode untuk menentukan solusi awal. Tiga dari metode yang dikenal adalah North West Corner, Least Cost, dan Aproksimasi Vogel.
1. Metode Pojok Barat Laut (North West Corner) Metode ini dimulai dengan alokasi pertama dari pojok kiri atas (barat laut) yaitu (1,1). Pengalokasian terhadap sel dapat dirumuskan π11 = πππ (π·1 , π1 ) Jika π·1 < π1 maka pengalokasian diteruskan ke sel (1,2) dimana π12 = min(π1 β π·1 , π·2 ). Jika π·1 > π1 maka pengalokasian diteruskan ke sel (2,1) dimana
Universitas Sumatera Utara
π21 = min(π·1 β π1 , π2 ). Langkah ini diteruskan sampai seluruh permintaan terpenuhi.
2. Metode Ongkos Terkecil (Least Cost) Metode Least Cost berusaha mencapai tujuan minimasi biaya dengan alokasi sistematik pada sel-sel sesuai dengan besarnya biaya transport per unit barang. Prosedur metode ini adalah: 1) Pilih variabel πππ (sel) dengan biaya transpor (πΆππ ) terkecil dan alokasikan sebanyak mungkin pada sel tersebut. Untuk πΆππ terkecil, maka πππ = ππππππ’π(ππ , π·π ). Pengalokasian ini akan menghabiskan baris i atau kolom j. 2) Dari sel-sel sisanya yang layak (yaitu yang tidak terisi atau tidak dihilangkan), pilih nilai πΆππ terkecil dan alokasikan unit barang sebanyak mungkin pada sel tersebut. 3) Lanjutkan proses ini sampai semua penawaran dan permintaan terpenuhi.
3. Metode Aproksimasi Vogel (VAM) VAM selalu memberikan suatu solusi awal yang lebih baik dibandingkan metode North West Corner dan sering kali lebih baik daripada metode Least Cost. Pada beberapa kasus, solusi awal yang diperoleh melalui VAM akan menjadi optimum. VAM melakukan alokasi dalam suatu cara yang akan meminimumkan penalty (opportunity cost) dalam memilih sel yang salah untuk suatu alokasi. Proses VAM sebagai berikut: 1) Hitung opportunity cost untuk setiap baris dan kolom. Opportunity cost untuk setiap baris i dihitung dengan mengurangkan nilai πΆππ terkecil pada baris itu dari nilai πΆππ satu tingkat lebih besar pada baris yang sama. Opportunity cost kolom diperoleh dengan cara yang serupa. Biaya-biaya ini adalah penalty karena tidak memilih kotak dengan biaya minimum. 2) Pilih baris atau kolom dengan opportunity cost terbesar (jika terdapat nilai yang sama, maka pilih secara sembarang). Alokasikan unit barang sebanyak mungkin ke kotak dengan nilai πΆππ minimum pada baris atau kolom yang dipilih. Untuk πΆππ terkecil, πππ = ππππππ’π(ππ , π·π ). Artinya penalty terbesar dihindari.
Universitas Sumatera Utara
3) Sesuaikan penawaran dan permintaan untuk menunjukkan alokasi yang sudah dilakukan. Hilangkan semua baris dan kolom dimana penawaran dan permintaan telah dihabiskan. 4) Jika semua penawaran dan permintaan belum dipenuhi, kembali ke langkah 1 dan hitung lagi opportunity cost yang baru. Jika semua penawaran dan permintaan terpenuhi, maka solusi awal telah diperoleh.
2.3.2 Penentuan Solusi Optimum
Bila solusi awal sudah didapat, maka langkah beriktnya adalah menentukan apakah solusi tersebut sudah merupakan yang terbaik (biaya paling minimum) atau belum. Prosedur ini melibatkan pemeriksaan tiap sel tak terpakai (tidak terisi) dalam tabel untuk menjajagi kemungkinan pemindahan pengiriman ke salah satu dari sel tak terpakai tersebut. Tujuan evaluasi ini adalah menentukan ada tidaknya rencana pengiriman dari sumber ke tujuan yang lebih baik. Ada dua metode untuk menilai sel tak terpakai, yakni metode Stepping Stone dan MODI. Metode Stepping Stone atau batu loncatan merupakan landasan bagi metode MODI.
1. Metode Batu Loncatan (Stepping Stone) Metode batu loncatan adalah suatu metode untuk mengevaluasi variabel non basis yang memungkinkan terjadinya perbaikan solusi dan kemudian mengalokasikan kembali sejumlah unit barang. Setelah solusi layak awal diperoleh dari masalah transportasi, langkah berikutnya adalah menekan biaya transpor dengan memasukkan variabel nonbasis ke dalam solusi. Sel nonbasis adalah sel yang tidak mendapat alokasi pada solusi awal.
Untuk dapat menentukan sel nonbasis yang akan dievaluasi, terlebih dahulu harus ditentukan jalur tertutup atau loop dari sel yang diisi, dimana alokasi dapat ditransfer ke sel nonbasis yang sedang dievaluasi. Adapun beberapa hal penting yang berkaitan dengan penyusunan jalur stepping stone adalah:
Universitas Sumatera Utara
a) Arah yang diambil, baik searah maupun berlawanan arah dengan jarum jam adalah tidak penting dalam membuat jalur tertutup. b) Hanya ada satu jalur tertutup untuk setiap sel kosong. c) Jalur hanya mengikuti sel yang terisi (dimana terjadi perubahan arah), kecuali pada kotak kosong yang sedang dievaluasi. d) Hanya dua sel yang dapat digunakan pada satu baris atau kolom. e) Sel basis terakhir dalam loop harus berada pada satu baris atau kolom dengan sel nonbasis yang akan dievaluasi.
Setelah menentukan loop, maka dilanjutkan dengan langkah penyelesaian stepping stone sebagai berikut: 1) Berikan tanda positif (+) dan negatif (-) secara bergantian pada nilai πΆππ dari selsel yang termasuk dalam loop, dimulai dengan tanda positif pada sel kosong yang dievaluasi. 2) Hitung perubahan biaya πΆππ terhadap setiap sel nonbasis dengan menjumlahkan nilai πΆππ yang terdapat pada masin-masing loop. Jika perubahan biaya yang dihasilkan pada variabel nonbasis bernilai positif, artinya terjadi penambahan biaya jika dilakukan pengalokasian barang ke sel tersebut. Sebaliknya, jika perubahan biaya yang dihasilkan bernilai negatif, artinya biaya transportasi akan berkurang. Pilih sel nonbasis yang memiliki nilai perubahan biaya negatif terbesar. 3) Pindahkan sejumlah unit barang dari sel basis yang mempunyai nilai πΆππ paling besar ke sel nonbasis terpilih yang berada dalam satu baris atau satu kolom pada loop tersebut. 4) Ulangi semua langkah tersebut hingga semua nilai perubahan biaya dari masing-masing sel nonbasis bernilai nol atau positif.
2. Metode MODI (Modified Distribution) Metode Modified Distribution (MODI) adalah suatu variasi metode stepping stone yang didasarkan pada rumusan dual. Metode MODI berbeda dengan metode stepping stone dalam hal bahwa dengan metode MODI tidak perlu menentukan semua jalur tertutup variabel nonbasis, kecuali jalur tertutup untuk entering
Universitas Sumatera Utara
variable. Karena itu, metode MODI merupakan cara yang lebih efisien untuk menghitung variabel non basis.
Adapun langkah-langkah penyelesaian dengan metode MODI adalah sebagai berikut: 1) Menentukan nilai-nilai ππ untuk setiap baris dan nilai-nilai ππ untuk setiap kolom dengan menggunakan hubungan πΆππ = ππ + ππ untuk semua variabel basis dan tetapkan bahwa nilai ππ adalah nol. 2) Hitung perubahan biaya untuk setiap variabel nonbasis dengan menggunakan hubungan πππ = πΆππ β ππ β ππ . 3) Jika terdapat nilai πππ negatif, maka solusi belum optimal. Pilih variabel πππ dengan nilai πππ negatif terbesar sebagai entering variable. 4) Alokasikan barang ke entering variable, πππ , sesuai proses stepping stone. 5) Ulangi langkah diatas hingga semua nilai πππ bernilai nol atau positif.
Universitas Sumatera Utara
