analisis beberapa metode transportasi dalam …

ANALISIS BEBERAPA METODE TRANSPORTASI DALAM

OPTIMALISASI BIAYA DISTRIBUSI

SKRIPSI

SUSTRI ELIANY PURBA

140803078

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA

MEDAN

2018




SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar

Sarjana Sains

SUSTRI ELIANY PURBA

140803078

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM


MEDAN

2018


ii

PERNYATAAN



SKRIPSI

Saya mengaku bahwa skripsi ini adalah hasil karya sendiri, kecuali beberapa kutipan

dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, Agustus 2018

Sustri Eliany Purba

140803078


iii

PENGESAHAN SKRIPSI

Judul : Analisis Beberapa Metode Transportasi Dalam

Optimalisasi Biaya Distribusi

Kategori : Skripsi

Nama : Sustri Eliany Purba

Nomor Induk Mahasiswa : 140803078

Program Studi : Sarjana (S1) Matematika

Departemen : Matematika

Fakultas : MIPA-Universitas Sumatera Utara

Disetujui di

Medan, Agustus 2018

Ketua Program Studi Pembimbing,

Dr. Suyanto, M.Kom Dr. Mardiningsih, M.Si

NIP. 19590813 198601 1 002 NIP. 19630405 198811 2 001


iv



ABSTRAK

Masalah transportasi sebagai bentuk khusus program linier membutuhkan metode

penyelesaian yang lebih efektiv dari metode simpleks. Sehingga diciptakan sebuah

metode khusus untuk menyelesaikan masalah transportasi dikenal dengan metode

transportasi. Metode ini bertujuan untuk mengoptimalkan biaya distribusi produk

tunggal dari beberapa sumber (source) ke beberapa tujuan (destination). Dalam

tulisan ini, penulis melakukan analisis terhadap beberapa metode transportasi yaitu,

metode penyelesaian solusi awal North west corner method (NWCM), Least cost

method (LCM), approximation method (VAM) dan metode uji optimalitas Modified

Distribution (MODI). Tujuan dari penelitian ini adalah mengkaji setiap metode untuk

memperlihatkan karakteristik, kelebihan dan kelemahan yang dimiliki setiap metode.

Metodologi penelitian yang digunakan adalah studi literatur terhadap beberapa

tinjauan pustaka berupa buku, artikel dan jurnal ilmiah yang berkaitan. Hasil

penelitian menunjukkan bahwa jika dilihat dari alur kerja setiap metode maka

metode yang paling sederhana adalah NWCM, selanjutnya metode LCM dan yang

paling kompleks adalah metode VAM. Namun jika dilihat dari solusi yang diperoleh

metode VAM menghasilkan total biaya distribusi paling minimum. Uji optimalitas

dengan metode MODI juga memperlihatkan bahwa solusi awal yang paling

mendekati solusi optimal dihasilkan oleh metode VAM, dilanjutkan oleh metode

LCM dan solusi awal terbesar dihasilkan metode NWCM.

Kata kunci: LCM, masalah transportasi, metode transportasi, MODI, NWCM, solusi

awal, solusi optimal, VAM


v

Analysis of Some Transportation Methods

in The Optimization of Distribution Cost

Abstract

Transportation problem as a special form of linear program requires a more

effective method of completion of the simplex method. Hence, a special method was

created to solve the problem of transportation known as transportation method. This

method aims to optimize the cost of single product distribution from multiple sources

to multiple destinations. In this paper, the author analyzes several methods of

transportation namely, the method of solution completion of North west corner

method (NWCM), Least cost method (LCM), approximation method (VAM) and

Modified Distribution (MODI) optimality test method. The purpose of this study is to

examine each method to show the characteristics, advantages and disadvantages of

each method. The research methodology used in this paper is literature study on

several literature reviews in the form of books, articles and related scientific

journals. The results shows that when it is viewed from the workflow of each method,

the simplest method is NWCM, then the LCM method and the most complex one is

the VAM method. However, when it is viewed from the solution obtained, VAM

method produces the minimum total cost of distribution. The optimality test with the

MODI method also shows that the nearest solution closest to the optimal solution is

generated by the VAM method, followed by the LCM method and the largest initial

solution produced by the NWCM method.

Keywords: destination, demand, initial solution, LCM, MOD, NWCM, optimal

solution, supply, source, transportation problems, transportation method,

VAM


vi

PENGHARGAAN

Puji dan syukur Penulis ucapkan kepada Tuhan Yesus atas segala kebaikan dan

kemurahan-Nya yang senantiasa menyertai, menguatkan, dan memberkati kehidupan

Penulis dalam setiap proses yang Penulis lalui. Hanya oleh karena kebaikan dan

penyertaan-Nya sajalah maka Penulis dapat menyelesaikan skripsi yang berjudul,

“Analisis Beberapa Metode Transportasi Dalam Optimalisasi Biaya Distribusi”

sebagai salah satu syarat untuk mendapatkan gelar Sarjana Matematika pada

Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam,

Universitas Sumatera Utara.

Terima kasih Penulis sampaikan kepada Ibu Dr. Mardiningsih, M.Si selaku

dosen pembimbing yang senantiasa meluangkan waktunya untuk membimbing,

memberikan arahan, dukungan dalam penulisan skripsi ini dan motivasi kepada

Penulis untuk lebih baik kedepannya. Semoga Tuhan senantiasa memberkati

kehidupan beliau dalam kesehatan dan sukacita. Terima kasih kepada Bapak Drs.

Agus Salim Harahap, M.Si dan Ibu Dra. Normalina Napitupulu, M.Sc selaku Dosen

Penguji yang telah memberi saran dan kritik yang membangun dalam

penyempurnaan skripsi ini. Dan semoga Tuhan senantiasa memberkati kehidupan

Bapak dan Ibu dalam kesehatan dan sukacita.

Terima kasih kepada Bapak Dr. Suyanto, M.Kom dan Bapak Drs. Rosman

Siregar, M.Si selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU,

seluruh Dosen Matematika FMIPA USU yang telah memberikan ilmu yang

bermanfaat kepada Penulis dari sejak awal perkuliahan, dan kepada para Pegawai

FMIPA USU yang senantiasa tulus melayani keperluan mahasiswa.

Selanjutnya, terima kasih Penulis ucapkan kepada Ibunda Roslina Saragih

dan Ayahanda Jolen Purba yang selalu mendoakan, mendukung, dan menasihati

sehingga Penulis dapat menyelesaikan skripsi ini. Biarlah kiranya berkat dan

penyertaan Tuhan Yesus yang membawa sukacita bagi kehidupan mereka.


vii

Kemudian, terima kasih kepada kelima abang dan kakak Penulis yaitu Rosida Purba,

Jan Linson Purba, Jonswarman Purba, Janiapoh Purba, Enida Purba, dan juga kakak/

abang ipar yang selalu mendukung dan menopang kebutuhan Penulis khususnya dari

segi materi dan finansial yang Penulis butuhkan selama perkuliahan sehingga dapat

menyelesaikan skripsi ini.

Dan tak lupa Penulis sampaikan terimakasih kepada semua teman dan

sahabat yang selalu setia mendoakan, menguatkan, dan memberikan semangat dalam

masa sukar dan mudah, sedih dan senang, jatuh dan bangun yang Penulis lalui dari

awal perkuliahan sampai saat ini. Untuk beberapa orang yang Penulis sebutkan

mereka yang sungguh dekat dengan keseharian penulis selama menyelesaikan

perkuliahan yaitu, untuk keluarga baru yang Penulis miliki di Medan dari awal

memasuki perkuliahan sampai saat ini, Nanggi Grace dan Panggi Kaban, terimakasih

sudah menerima Penulis sebagai anak, semoga Tuhan Yesus senantiasa memberkati

dan menambahkan sukacita buat semua keluarga. Dan untuk Ruth Situmorang,

terimakasih telah menjadi seorang sahabat yang baik, semoga Tuhan Yesus

senantiasa menyertaimu. Dan juga terimakasih kepada teman-teman seperjuangan

angkatan 2014, seluruh adik-adik Matematika stambuk 2015, 2016 dan 2017 yang

telah menjadi keluarga baru bagi Penulis, semoga Tuhan senantiasa memberkati.

Penulis menyadari bahwa skripsi ini jauh dari kesempurnaan. Untuk itu,

Penulis meminta maaf apabila ada kesalahan baik dalam penulisan dan penyajian

dalam skripsi ini. Akhir kata, Penulis berharap skripsi ini bermanfaat bagi diri

Penulis pribadi dan orang lain.

Medan, Agustus 2018

Penulis

Sustri Eliany Purba


viii

DAFTAR ISI

Halaman

PERNYATAAN ii

PENGESAHAN SKRIPSI iii

ABSTRAK iv

ABSTRACT v

PENGHARGAAN vi

DAFTAR ISI viii

DAFTAR TABEL x

DAFTAR GAMBAR xii

DAFTAR SIMBOL xiii

BAB 1 PENDAHULUAN

1.1 LatarBelakang 1

1.2 RumusanMasalah 2

1.3 BatasanMasalah 3

1.4 TujuanPenelitian 3

1.5 Manfaat Penelitian 3

BAB 2 TINJAUAN PUSTAKA

2.1 Riset Operasi 5

2.2 Program Linier 6

2.3 Masalah Transportasi 7

2.3.1 Sejarah Permasalahan Transportasi 7

2.3.2 Defenisi dan Tujuan Masalah Transportasi 8

2.3.3 Ciri-ciri Masalah Transportasi 8

2.3.4 Model Umum Masalah Transportasi 9

2.3.4.1 Asumsi Dasar 9

2.3.4.2 Pengertian Metode Transportasi 9

2.3.4.3 Model Masalah Transportasi 10

2.3.4.4 Keseimbangan Transportasi 14

2.3.4.5 Metode Penyelesaian 17

2.4 Sistem Distribusi 19

2.5 Degenarasi dan Redudansi 14

BAB 3 METODE PENELITIAN

3.1 KerangkaPenelitian 22

BAB 4 PEMBAHASAN

4.1 Masalah Transportasi 23

4.2 Model Matematika Masalah Transportasi 25

4.3 Penyelesaian Masalah Transportasi 29

4.3.1 Menentukan Solusi Layak Awal 29

4.3.2 Menentukan Solusi Optimum 30


ix

4.3.3 Ciri-ciri Solusi Layak Awal 30

4.4 Metode Transportasi 31

4.4.1 Metode Untuk Menentukan Solusi Layak Awal 31

4.4.1.1North – West corner Method (NWCM) 31

4.4.1.2 Least – Cost Method (LCM) 34

4.4.1.3 Vogel’s Approximation Method (VAM) 36

4.4.2 Metode Uji Optimalitas 39

4.4.2.1 Stepping Stone Method 39

4.4.2.2 Modified Distribution (MODI) 50

4.5 Aplikasi Metode Pada Contoh Kasus 58

4.5.1 Menentukan Solusi Layak Awal 59

4.5.1.1Solusi Layak Awal denganNWC 59

4.5.1.2Solusi Awal Dengan Metode LCM 60

4.5.1.3 Solusi Awal dengan Metode VAM 63

4.5.2 Uji optimalitas pada solusi awal 69

4.5.2.1 Uji Optimalitas dengan MODI 70

4.5.3 Penyelesaian Masalah Transportasi

dengan Software 75

4.5.3.1 Program Lindo 75

4.5.3.2 Program Lingo 81

BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan 84

5.2 Saran 85

DAFTAR PUSTAKA 86


x

DAFTAR TABEL

Nomor Judul Halaman

2.1 Gambaran umum Masalah Transportasi 12

2.2 Tabel Persoalan Transportasi Seimbang ∑ai = ∑bj 15

2.3 Tabel Persoalan Transportasi Tidak Seimbang ∑ai> ∑bj 16

2.4 Tabel Persoalan Transportasi Tidak Seimbang ∑ai< ∑bj 16

4.1 Tabel Masalah Transportasi 25

4.2 Tabel Transportasi secara umum 26

4.3 Contoh Tabel Transportasi Gula 28

4.4 Tabel distribusi dari 3 pabrik ke 3 pasar 32

4.5 Hasilalokasibarangdengan NWCM dari 3 pabrikke 3 pasar 33

4.6 Hasil alokasi NWCM 33

4.7 Tabel Transportasi 34

4.8 Hasil menentukan solusi layak awal dengan LCM 35

4.9 Hasil Alokasi LCM 26

4.10 Tabel Transportasi contoh soal VAM 36

4.11 Hasil alokasi dengan metode VAM 37

4.12 Hasil alokasi VAM 37

4.13 Perbandingan proses alokasi menentukan solusi layak awal 38

4.14 Tes optimalitas solusi layak awal dengan metode stepping stone 41

4.15 Alokasi 1 ton ke sel 1A 42

4.16 Pegurangan satu ton dari sel 1B 43

4.17 Jalur tertutup metode stepping stone sel 2A 43

4.18 Jalur tertutup stepping stone sel 2A 44

4.19 Jalur stepping stone sel 2B 45

4.20 Jalur stepping stone pada sel 3C 45

4.21 Jalur alokasi sel 1A 46

4.22 Iterasi kedua dari metode stepping stone 47

4.23 Jalur Stepping-Stone untuk Cell 2A 47

4.24 Jalur Stepping-Stone untuk Cell 1B 48

4.25 Jalur Stepping-Stone untuk Cell 2B 48

4.26 Jalur Stepping-Stone untuk Cell 3C 49

4.27 Solusi optimal alternatif dengan metode stepping stone 49

4.28 Solusi layak awal dengan least-cost method 52

4.29 Solusi awal dengan semua nilai uidan vj 54

4.30 Iterasi kedua menentukan solusi optimal dengan MODI 55

4.31 Nilai baru ui dan vjuntuk iterasi 56

4.32 Contoh masalah transportasi 58

4.33 Matriks biaya transportasi hasil alokasi dengan metode NWC 59

4.34 Hasil alokasi dengan LCMsel biaya terendah pertama 61

4.35 Lanjutan proses alokasi LCM biaya terendah kedua 61

4.36 Lanjutan hasil alokasi dari metode LCM biaya terendah ketiga 62

4.37 Solusi awal dengan metode LCM 63

4.38 Tabel Masalah Transportasi 64


xi

4.39 Beda baris dan beda kolom iterasi ke-1 64

4.40 Hasil perhitungan pada kolom penalty terbesar pertama 65


4.42 Hasil perhitungan pada kolom penalty terbesar kedua 66


4.44 Hasil perhitungan pada kolom penalty terbesar ketiga 67


4.46 Hasil perhitungan pada kolom penalty terbesar keempat 68


4.48 Hasil perhitungan pada kolom penalty terbesar kelima 69

4.49 Solusi layak awal dengan Least-cost method (LCM) 70

4.50 Nilai vi danuj dalam tabel solusi awal 72

4.51 Nilai opportunity cost dari hasil evaluasi sel-sel kosong 72

4.52 Hasil realokasi solusi dengan metode MODI iterasi ke-1 73

4.53 Nilai opportunity cost sel-sel kosong metode MODI iterasi ke-2 73

4.54 Hasil Penyelesaian contoh Kasus Transportasi subbab 4.5 75

4.55 Tabel masalah Transportasi dengan Lindo 75

4.56 Tabel masalah Transportasi dengan Lingo 65


xii

DAFTAR GAMBAR

Nomor Judul Halaman

2.1 Deskripsi jaringan transportasi 11

2.2 Representasi Model Persoalan Transportasi 13

4.1 Representasi Jaringan sederhana Masalah Transportasi 23

4.2 Jaringan Transportasi 24

4.3 Model Jaringan Transportasi 25


xiii

DAFTAR SIMBOL

Z = fungsi tujuan; total yang akan diminimumkan

𝐶ij = biaya transportasi per unit barang dari sumber i ke tujuan j

𝑋ij = jumlah barang yang didistribusikan dari sumber i ke tujuan j

𝑎i = jumlah barang yang ditawarkan atau kapasitas dari sumber i

𝑏j = jumlah barang yang diminta atau dipesan oleh tujuan j

𝑚 = banyaknya daerah penghasil/ sumber

𝑛 = banyaknya daerah tujuan

Pi = dummy untuk baris

Pj = dummy untuk kolom

cij = biaya transportasi per unit

ui = nilai variabel dual setiap baris

vj = nilai setiap sel kolom


BAB 1

PENDAHULUAN

1.1 Latar Belakang

Salah satu permasalahan khusus dalam linear programming adalah masalah

transportasi, untuk menyelesaikan permasalahan ini digunakan metode transportasi.

Dikatakan khusus, karena terletak pada karakteristik utama, yaitu bahwa masalah-

masalah tersebut cenderung membutuhkan sejumlah pembatas dan variabel yang

sangat banyak sehingga dalam penggunaan komputer dalam menyelesaikan metode

simpleks akan sangat mahal dibandingkan secara manual (Zulfikarijah, 2004).

Metode transportasi adalah metode yang paling efisien dibandingkan dengan

metode simpleks. Penggunaan metode transportasi ini dipelopori oleh FL. Hitchcock

(1941), TC. Koopmas (1949) dan GB.Dantzig (1951). Beberapa permasalahan yang

dapat diselesaikan dengan metode transportasi adalah mengalokasikan barang atau

jasa dari suatu tempat (sumber/supply) ke tempat lainnya (demand/destination)

secara optimal dengan mempertimbangkan biaya minimal, pengalokasian periklanan

yang efektif, pembelanjaan modal dan alokasi dana untuk investasi, analisis

pemilihan lokasi usaha yang tepat, keseimbangan lini perakitan, dan penjadwalan

produksi (Sri Rahmawati, 2016).

Opltimalisasi dalam ilmu matematika, komputer dan ekonomi adalah suatu

proses menyelesaikan permasalahan matematis secara efektif dengan memilih solusi

terbaik dari beberapa solusi alternatif yang tersedia. Dengan kata lain optimalisasi

bertujuan untuk memaksimumkan atau meminimumkan sebuah fungsi tujuan dengan

memilih beberapa nilai integer atau variabel real dari sebuah himpunan nilai yang

ditetapkan. Demikian halnya masalah transportasi, disadari penting untuk

menemukan sebuah rencana pendistribusian yang optimal terhadap sejumlah barang

yang sejenis. Ketika penawaran barang (supply) tersedia pada sejumlah sumber yang

berbeda, jumlah permintaan barang (demand) ditentukan pada setiap tujuan, dengan

biaya transportasi dari sumber ke tujuan didefenisikan dengan jelas, masalah yang

harus diselesaikan adalah menemukan model / rencana pendistribusian yang optimal


2

yang dapat meminimalkan seluruh biaya transportasi pengangkutan barang dari

seluruh sumber ke seluruh tujuan (Rekha Vivek, 2013).

Beberapa metode yang dapat digunakan untuk menyelesaikan kasus

transportasi antara lain North west corner method (NWCM), Least cost method

(LCM), Integer programming, Dyinamic programming, Vogel approximation

method (VAM), dan algoritma simpleks. Di antara metode-metode tersebut, metode

integer programming dan dynamik programming tidak seefesien metode algoritma

simpleks karena kedua metode ini membutuhkan jumlah perhitungan yang lebih

banyak (Dwi dan Yus Endra, 2004).

Jika telah dilakukan pengalokasian dengan salah satu metode tersebut akan

diperoleh suatu nilai solusi layak awal (feasible solution). Langkah berikutnya adalah

melihat apakah alokasi tersebut sudah optimal atau belum yang dikenal dengan uji

optimalisasi. Ada dua metode uji optimalisasi yang umum digunaka, yaitu metode

Stepping-stone dan MODI (Modified Distribution). Jika hasil uji menunjukkan

bahwa solusi layak awal adalah solusi optimal maka alokasi telah optimal dan dapat

dikatakan telah mencapai nilai yang paling menguntungkan (Sri Mulyono, 2004).

Pada penelitian ini, penulis ingin menganalisis beberapa metode transportasi

yang umum digunakan oleh para peneliti sebelumnya yang berkaitan dengan masalah

transportasi yakni tiga metode untuk menentukan solusi awal yaitu North west corner

method (NWCM), Least cost method, approximation method (VAM) dan metode uji

optimalitas yaitu MODI (Modified Distribution) untuk menentukan solusi optimum.

Dan semua metode yang dianalisis tersebut akan diaplikasikan pada sebuah contoh

kasus transportasi pendistribusian barang. Sehingga penulis memberi judul penelitian

ini dengan “Analisis Beberapa Metode Transportasi Dalam Optimalisasi Biaya

Distribusi”.

1.2 Rumusan Masalah

Sesuai dengan uraian pada latar belakang penelitian ini, maka yang menjadi pokok

permasalahan pada penelitian ini adalah:

1. Mengkaji dan menganalisis karakteristik metode North west corner method

(NWCM), Least cost method, approximation method (VAM), yakni

bagaimana kelebihan dan kelemahan setiap metode sehingga suatu metode


3

dapat disimpulkan sebagai metode optimal untuk meyelesaikan suatu kasus

transportasi

2. Menguji keoptimalan setiap metode dengan mengaplikasikan pada contoh

kasus, dan melakukan uji optimalitas dengan metode MODI (Modified

Distribution) untuk menentukan apakah solusi awal yang diperoh sudah

merupakan solusi optimum atau tidak.

1.3 Batasan Masalah

Dalam tulisan ini penulis membatasi permasalahan pada:

1. Fokus penelitian ini adalah menganalisis bagaimana karakteristik dan alur

pengaplikasian setiap metode dapat menyelesaikan kasus transportasi

2. Ada 3 metode yang dianalisis dalam tulisan ini yaitu North west corner

method (NWCM), Least cost method, approximation method (VAM) untuk

menentukan solusi awal dan digunakan metode MODI (Modified

Distribution) untuk menguji keoptimalan solusi awal

3. Penelitian ini menggunakan contoh kasus

1.4 Tujuan Penelitian

Sesuai dengan perumusan masalah, maka tujuan dari penelitian ini adalah untuk

memperlihatkan dan menentukan metode apa yang tepat dan optimal dari ketiga

metode yang dianalisis yaitu North west corner method (NWCM), Least cost method,

approximation method (VAM) untuk menyelesaikan kasus-kasus trasportasi dalam

mengoptimalkan biaya distribusi.

1.5 Manfaat Penelitian

Manfaat dari penelitian ini adalah:

1. Sebagai referensi bagi mahasiswa/i agar lebih selektif dalam memilih metode

transportasi yang sesuai dengan kasus yang diteliti.

2. Memberikan informasi dan menambah pengetahuan pembaca mengenai

model transportasi yang dapat diaplikasikan dalam kehidupan sehari-hari.

3. Menambah studi pustaka bagi peneliti selanjutnya yang berkaitan dengan

tulisan ini.


4

4. Sebagai rujukan bagi perusahaan-perusahaan yang bergerak di bidang

distribusi agar dapat memilih metode yang sesuai untuk mengoptimalkan

biaya transportasi sehingga diperoleh keuntungan yang maksimum.


BAB 2

TINJAUAN PUSTAKA

2.1 Riset Operasi

Masalah Riset Operasi (Operation Research) pertama kali muncul tahun 1939 di

Inggris selama Perang Dunia II. Inggris mula-mula tertarik menggunakan metode

kuantitatif dalam pemakaian radar selama perang. Mereka menamakan pendekatan

itu sebagai Operation Research karena mereka menggunakan ilmuwan (scientist)

untuk meneliti (research) masalah-masalah operasional selama perang. Ternyata

pendekatan tersebut berhasil dalam memecahkan masalah operasi konvoi, operasi

anti kapal selam, strategi pengeboman, dan operasi pertambangan (Jong Jek Siang,

2014). Setelah Perang Dunia II berakhir, Riset Operasi yang lahir di Inggris ini

kemudian berkembang pesat di Amerika karena keberhasilan tim Riset Operasi

dalam bidang militer ini telah menarik perhatian orang-orang industri. Sedemikian

pesat perkembangannya sehingga kini Riset Operasi telah digunakan dalam hampir

seluruh bidang. (Dimyati, 2004)

Secara harfiah kata operation dapat didefinisikan sebagai tindakan-tindakan

yang diterapkan pada beberapa masalah atau hipotesa. Sementara kata research

adalah suatu proses yang terorganisasi dalam mencari kebenaran akan masalah atau

hipotesa. Kenyatannya, sangat sulit mendefinisikan operation research, terutama

karena batas-batasnya tidak jelas (Mulyono, 2004). Definisi lain menurut

Operational Research Society of America (ORSA), operation research berkaitan

dengan pengambilan keputusan secara ilmiah dan bagaimana membuat suatu model

yang baik dalam merancang dan menjalankan sistem yang melalui alokasi sumber

daya yang terbatas. Dapat disimpulkan operation research adalah bagaimana proses

pengambilan keputusan yang optimal dengan menggunakan alat analisis yang ada

dan adanya keterbatasan sumber daya. (Andi Wijaya, 2013)

Dalam operation research atau Riset Operasi, masalah optimalisasi dalam

pengambilan keputusan diperoleh dengan menerapkan teknik matematika dan

statistika. Model matematika yang digunakan dalam metode riset operasi bersifat


6

menyederhanakan masalah dan membatasi faktor-faktor yang mungkin berpengaruh

terhadap suatu masalah. Jika riset operasi akan digunakan untuk memecahkan suatu

permasalahan, maka harus dilakukan lima langkah sebagai berikut:

1. Memformulasikan persoalan.

2. Mengobservasi sistem.

3. Memformulasikan model matematis dari persoalan yang dihadapi.

4. Mengevaluasi model dan menggunakannya untuk prediksi.

5. Mengimplementasikan hasil studi. (Putri Winda S.B., 2016)

2.2 Program Linier

Program linier (Linear Programming) yang disingkat LP merupakan salah satu

teknik Riset Operasi yang digunakan paling luas dan diketahui dengan baik. LP

merupakan metode matematik dalam mengalokasikan sumber daya yang langka

untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau

meminimumkan biaya. LP banyak diterapkan dalam membantu menyelesaikan

masalah ekonomi, industri, militer, sosial dan lain-lain. LP berkaitan dengan

penjelasan suatu dunia nyata sebagai suatu model matematik yang terdiri atas sebuah

fungsi tujuan linier dan sistem kendala linier. (Mulyono, 2004: 13)

Menurut Frederick S. Hiller dan Gerald J. Lieberman, linear programming

merupakan suatu model matematis untuk menggambarkan masalah yang dihadapi.

Linier berarti bahwa semua fungsi matematis dalam model ini merupakan fungsi-

fungsi linier. Pemrograman merupakan sinonim untuk kata perencanaan. Dengan

demikian membuat rencana kegiatan-kegiatan untuk memperoleh hasil yang optimal,

ialah suatu hasil untuk mencapai tujuan yang ditentukan dengan cara yang paling

baik (sesuai dengan model matematis) diantara semua alternatif yang mungkin.

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


7

suatu cara yang lazim digunakan untuk menentukan kombinasi optimal dari tiga

variabel atau lebih. 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.

(Lolyta D., 2015)

2.3 Masalah Transportasi

Masalah Transportasi merupakan salah satu permasalahan khusus dalam linear

programming. Dikatakan khusus, karena terletak pada karakteristik utama, yaitu

bahwa masalah-masalah tersebut cenderung membutuhkan sejumlah pembatas dan

variabel yang sangat banyak sehingga dalam penggunaan komputer untuk

menyelesaikan metode simpleksnya akan sangat sulit dibanding secara manual. (Sari

Diah P, 2014)

2.3.1 Sejarah Permasalahan Transportasi

Masalah transportasi telah lama dipelajari dan dikembangkan sebelum lahir model

program linear. Pada tahun 1939, L.V Kantorovitch mempelajari beberapa

permasalahan yang berhubungan dengan model transportasi. Kemudian F.L.

Hitchcock pada tahun 1941 merumuskan model matematika dari persoalan

transportasi dan kini dianggap sebagai model matematika persoalan transportasi yang

baku, atau sering juga disebut sebagai model Hitchcock. Kemudian pada tahun 1947

T.C. Koopmans menerbitkan buku tentang sistem transportasi yang berjudul

Optimum Utilization of the Transportation System yang kemudian disusul G.B

Dantzig pada tahun 1951 tentang perumusan persoalan linear programming dan cara

pemecahan yang sistematis yang sering disebut sebagai bapak linier programming.

Prosedur pemecahan yang sistematis tersebut disebut metode simpleks.(Siti

Ramadhani, 2015)


8

2.3.2 Definisi dan Tujuan Masalah Transportasi

Secara umum arti transportasi adalah adanya perpindahan barang dari suatu tempat

ke tempat lain dan dari beberapa tempat ke beberapa tempat lain. Tempat atau

tempat-tempat asal barang disebut juga dengan istilah sumber atau sumber-sumber

(resources). Sedangkan tempat atau tempat-tempat tujuan disebut destination. Hal ini

merupakan bagian dari kehidupan nyata manusia untuk memindahkan barang dari

satu tempat ke tempat lain sesuai dengan kebutuhannya. Misalnya, di suatu tempat

asal barang mempunyai jumlah produk yang berlebih sehingga perlu

ditransportasikan ke tempat lain yang memerlukannya (P, Suyadi, 2005).

Dalam arti sederhana, masalah transportasi berusaha menentukan sebuah

rencana transportasi sebuah barang dari sejumlah sumber ke sejumlah tujuan.

Masalah transportasi berkaitan dengan penentuan rencana berbiaya rendah untuk

mengirimkan suatu barang dari sejumlah sumber (misalnya, pabrik) ke sejumlah

tujuan (misalnya, gudang). Dalam arti lain, transportasi adalah aplikasi yang

digunakan untuk mengatur distribusi dari sumber-sumber yang menyediakan produk

yang sama, ke tempat-tempat yang membutuhkan produk tersebut secara optimal.

Masalah transportasi pada dasarnya merupakan sebuah program linier yang

dipecahkan oleh metode simpleks biasa. Tetapi, strukturnya yang khusus

memungkinkan pengembangan sebuah prosedur pemecahan, yang disebut teknik

transportasi, yang lebih efisien dalam hal perhitungan. (Siti Ramadhani, 2016)

2.3.3 Ciri-ciri Masalah Transportasi

Ciri-ciri khusus masalah transportasi adalah:

1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu.

2. Kuantitas komoditas atau barang yang didistribusikan dari setiap sumber dan

yang diminta oleh setiap tujuan, besarnya tertentu.

3. Komoditas yang dikirim atau diangkut dari suatu sumber ke suatu tujuan,

besarnya sesuai dengan permintaan dan atau kapasitas sumber.

4. Ongkos pengangkutan komoditas dari suatu sunber ke suatu tujuan, besarnya

tertentu. (Bu’ulolo ̈, F. 2016)


9

2.3.4 Model Umum Masalah Transportasi

2.3.4.1 Asumsi Dasar

Model transportasi merupakan salah satu bentuk khusus atau variasi dari program

linier yang di kembangkan khusus untuk memecahkan masalah-masalah yang

berhubungan dengan transportasi (pengangkutan) dan disribusi produk atau sumber

daya dari berbagai sumber (pusat pengadaan, atau titik supply) ke berbagai tujuan

(titik permintaan atau pusat pemakaian) yang lebih efisien dalam hal perhitungan.

Asumsi dasar dari model ini adalah bahwa biaya transportasi di sebuah rute

tertentu adalah proposional secara langsung dengan jumlah unit yang dikirimkan.

Defenisi unit transportasi akan bervariasi bergantung pada jenis barang yang di

kirimkan.

Model umum suatu persoalan transportasi dilandasi pada asumsi-asumsi

berikut:

1. Bahwa suatu produk yang ingin diangkut tersedia dalam jumlah yang tetap

dan diketahui.

2. Bahwa produk tersebut akan dikirim melalui jaringan transpotasi yang ada

dengan memakai cara pengakutan tertentu dari pusat-pusat permintaan.

3. Bahwa jumlah permintaan di pusat permintaan pun diketahui dalam jumlah

tertentu dan tetap.

4. Bahwa ongkos angkutan per-unit produk yang diangkut pun diketahui,

sehingga tujuan kita untuk meminimumkan biaya total angkutan dapat

tercapai.

5. Bahwa sumber tidak mungkin mengirim komoditas lebih besar dari

kapasitasnya.

Karena hanya ada satu jenis komoditas, pada dasarnya setiap daerah tujuan

dapat menerima komoditas dari sembarang daerah sumber. (Siti Ramadhani, 2016)

2.3.4.2 Pengertian Metode Transportasi

Pengertian Metode Transportasi menurut Hamdi A. Taha (2003) adalah The

transportation method is a special class of linear programming that deals with

shipping a commodity from sources (e.g. factories) to destinations (e.g.warehouses)

the objective is to determine the total shipping cost while satisfying supply and


10

demand limits.” Maksudnya Metode transportasi adalah bagian khusus dari linear

programming yang membahas pengangkutan komoditi dari sumber ke tempat tujuan

dengan tujuan untuk menemukan pola pengangkutan yang dapat meminimumkan

biaya pengangkutan total da lam pemenuhan batas penawaran dan permintaan.

Sedangkan, Richard B. Chase dkk (2004) menyatakan bahwa “The

transportation method is a simplified special case of simplex method, it gets its name

from its application to problem involving transporting product from several sources

to several destinations, two common objectives of such problem are either: 1.

Minimize the cost of shipping, n units to m destinations 2. Maximize the profit of

shipping, n units to m destinations.” Yang dimaksud dengan Metode Transportasi

menurut defenisi ini adalah suatu bentuk khusus untuk mempermudah metode

simpleks. Nama tersebut diambil dari kegunaan metode tersebut yang meliputi

masalah-masalah angkutan dari beberapa sumber ke beberapa tujuan, dua hal dasar

objek mendasar masalah ini yaitu: 1. Minimisasi ongokos angkut, n unit ke m tujuan

2. Maksimisasi laba angkut, n unit ke m tujuan.

Dan menurut Pangestu Subagyo dkk (2008) mengatakan bahwa Metode

Transportasi merupakan sebuah metode yang digunakan untuk mengatur distribusi

dari sumber-sumber yang menghasilkan produk yang sama ke tempat-tempat yang

membutuhkan secara optimal. (Dika Herli, 2014)

Dari pendapat-pendapat di atas penulis menyimpulkan, bahwa pada dasarnya

Metode Transportasi merupakan metode yang dipakai untuk merencanakan dan

mengendalikan pengalokasian barang dari beberapa sumber ke berbagai tujuan agar

pendistribusian dapat terlaksana sesuai rencana, seoptimal mungkin dan dengan

biaya yang minimum.

2.3.4.3 Model Masalah Transportasi

Model permasalahan transportasi yang paling sederhana diperkenalkan tahun 1941

dan terus dikembangkan pada tahun 1949 dan 1951. Kemudian, beberapa perluasan

dari model dan metode transportasi telah dikembangkan oleh peneliti berikutnya.

Secara umum masalah transportasi diperlihatkan melalui jaringan berikut ini.


11

Gambar 2.1 Jaringan transportasi

Asumsi dasar dari model transportasi adalah besarnya ongkos transportasi pada

rute adalah proposional dengan jumlah barang yang di distribusikan. Deskripsi model

transportasi dalam bentuk jaringan dari m sumber ke n tujuan digambarkan dengan

titik dan busur seperti pada Gambar 2.1. Ada m sumber dan n tujuan masing-

masing digambarkan melalui sebuah titik, dan sebuah busur menghubungkan sumber

dengan tujuan menggambarkan jalur-jalur antara sumber dan tujuan. Busur-busur (i,

j) menghubungkan sumber i menuju tujuan j membawa dua informasi : (1) biaya

transportasi per unit- cij, dan (2) jumlah barang yang dikirim- xij . Jumlah supply

(penawaran) pada sumber i adalah ai dan jumlah demand (permintaan) pada tujuan j

adalah bj . Tujuan dari model tersebut adalah untuk menentukan besar nilai xij yang

meminimalkan total biaya transportasi saat memenuhi semua batasan supply dan

demand.

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:

Meminimalkan

(2.1)


12

Dengan kendala:

(2.2)

(2.3)

(2.4)

Keterangan:

Z = fungsi tujuan; total yang akan diminimumkan

𝐶ij = biaya transportasi per unit barang dari sumber i ke tujuan j

𝑋ij = jumlah barang yang didistribusikan dari sumber i ke tujuan j



𝑚 = banyaknya daerah penghasil/ sumber

𝑛 = banyaknya daerah tujuan

Bentuk umum dari tabel transportasi dapat dilihat pada tabel berikut.

Tabel 2.1 Gambaran Umum Masalah Transportasi

Sebagai ilustrasi, Gambar 2.2 akan memodelkan persoalan transportasi

dengan 3 sumber dan 4 tujuan (m= 3, n= 4).


13

Gambar 2.2 Representasi Model Persoalan Transportasi

Fungsi Tujuan:

Meminimumkan

Z = C11X11 + C12X12 + C13X13 + C14X14 + C21X21 + C22X22 + C23X23 +

C24X24 + C31X31 + C32X32 + C33X33 + C34X34

Dengan kendala:

X11 + X12 + X13 + X14 ≤ a1

X21 + X22 + X23 + X24 ≤ a1

X31 + X32 + X33 + X34 ≤ a1

X11 + X21+ X31 ≥ b1

X12 + X22 + X32 ≥ b2

(Ariz Kurnia, 2017)

2.3.4.4 Keseimbangan Transportasi

Permasalahan transportasi seimbang adalah permasalahan biaya angkutan barang di

mana jumlah barang yang dipasok dari tempat asal sama dengan jumlah barang yang

diminta di tempat tujuan. (Sitorus, 1997)

Dalam kehidupan nyata, tidak selalu dapat dipastikan bahwa penawaran sama

dengan permintaan atau melebihinya. Tetapi, sebuah model transportasi dapat selalu

berimbang. Pengimbangan ini, di samping kegunaannya dalam pemodelan situasi


14

praktis tertentu, adalah penting untuk pengembangan sebuah metode pemecahan

yang sepenuhnya memanfaatkan struktur khusus dari model transportasi ini (Taha,

1996).

Model Gambar 2.3 pada subbab 2.3.4.3 menyiratkan bahwa penawaran total

harus setidaknya sama dengan permintaan total. Ketika penawaran total sama dengan

permintaan total formulasi yang dihasilkan disebut model transportasi

berimbang (balanced transportation model). Formulasi ini berbeda dengan formulasi

sebelumnya hanya terletak pada batasannya yaitu bahwa semua batasan adalah

persamaan, dituliskan sebagai berikut:

(2.5)

(2.6)

Dalam persoalan transportasi yang sebenarnya, jumlah supply yang tersedia

tidak selalu sama dengan jumlah demand atau dengan kata lain jumlah supply yang

tersedia mungkin lebih besar atau lebih kecil daripada jumlah demand. Jika hal ini

terjadi, maka model persoalan disebut sebagai model transportasi tidak seimbang

(unbalanced transportation model). Setiap persoalan transportasi dapat dibuat

seimbang dengan memasukkan kolom dummy atau baris dummy. Ada 2

kemungkinan yang terjadi pada persoalan transportasi tidak seimbang yaitu:

1. Bila supply lebih besar daripada demand ai > bj, persoalan ini diselesaikan

dengan cara menetapkan dummy pada tujuan (kolom) untuk menyerap

kelebihan demand sebesar:

(2.7)

2. Bila supply lebih kecil daripada demand ai < bj , persoalan ini diselesaikan

dengan cara menetapkan dummy pada sumber (baris) untuk men-supply

kekurangan demand sebesar:

(2.8)


15

Dummy tujuan pada kolom maupun dummy sumber pada baris tabel

transportasi pada dasarnya adalah buatan (tidak riil). Dengan demikian, biaya

distribusi pada kolom dummy dan baris dummy adalah nol. Hal ini dapat dipahami

karena pada kenyataan tidak terjadi pengiriman dari sumber dummy dan tidak terjadi

pengiriman ke tujuan dummy.

Tabel 2.1 Tabel Persoalan Transportasi Seimbang ∑ai = ∑bj

Tabel 2.1 Tabel Persoalan Transportasi Tidak Seimbang ∑ai > ∑bj


16

Tabel 2.1 Tabel Persoalan Transportasi Tidak Seimbang ∑ai < ∑bj

(Jelly Luis, 2014)

2.3.4.5 Metode Penyelesaian Masalah Transportasi

Untuk menyelesaikan persoalan transportasi, harus dilakukan dengan langkah-

langkah sebagai berikut:

1. Menentukan Solusi Fisibel Basis Awal.

2. Manentukan entering variabel dari variabel-variabel nonbasis. Bila semua

variabel sudah memenuhi kondisi optimal, STOP. Bila belum lanjutkan ke

langkah 3.

3. Tentukan leaving variabel diantara variabel-variabel basis yang ada,

kemudian hitung solusi yang ada. Kembali ke langkah 2.

Ada beberapa metode untuk menentukan solusi awal. Tiga dari metode yang

dikenal adalah North West Corner, Least Cost, dan Aproksimasi Vogel.

Metode Northwest Corner

Alur kerja metode Northwest Corner

a. Pendistribusian dimulai dari pojok kiri atas dan diakhiri pada pojok kanan

bawah.

b. Setiap pendistribusian dipilih nilai sebanyak mungkin tanpa menyimpang dari

sumber atau tujuan


17

c. Apabila variabel dasar sudah terisi semua, maka dihitung jumlah biaya yang

akan dikeluarkan oleh perusahaan.

Metode Least Cost

Alur kerja metode Least Cost

a. Pendistribusian dimulai dari biaya terkecil dan apabila terdapat biaya terkecil

lebih dari satu, maka dipilih salah satu.

b. Setiap pendistribusian dipilih nilai sebanyak mungkin tanpa mengabaikan

jumlah sumber atau tujuan

c. Lanjutkan dengan cara yang sama sampai semua penawaran telah dihabiskan

dan keperluan permintaan telah dipenuhi.

Vogel.’s Approximation

Alur kerja Vogel’s Approximation

a. Menghitung oppurtunity cost yang didasarkan pada dua biaya terkecil pada

setiap baris dan kolom dan mengurangkan kedunya, hasil perhitungannya

disebut dengan penalty cost.

b. Memilih nilai penalty cost terbesar di antara baris dan kolom.

c. Memilih biaya terkecil dari nilai penalty cost terbesar dan mendistribusikan

sejumlah nilai. Baris atau kolom penalty yang sudah terpilih diabaikan untuk

langkah selanjutnya.

d. Menyesuaikan jumlah permintaan dan penawaran untuk menunjukkan alokasi

yang sudah dilakukan. Menghilangkan semua baris dan kolom di mana

penawaran dan permintaan telah dihabiskan.

e. Apabila jumlah penawaran dan permintaan belum sesuai, maka ulangi

langkah pertama sampai terisi semua.

Metode MODI (Modified Distribution)

Metode MODI merupakan variasi dari metode stepping stone yang didasarkan

pada rumusan dual. Perbedaannya dengan metode stepping stone adalah metode ini

tidak harus menentukan semua jalur tertutup variabel nonbasis, kecuali pada saat

akan melakukan perpindahan pengisian tabel. Dengan demikian metode MODI


18

merupakan cara yang efisien untuk menghitung variabel non basis. Dalam metode

MODI terdapat persamaan sebagai berikut.

cij = ui + vj (2.9)

Dengan,

cij = biaya transportasi per unit

ui = nilai variabel dual setiap baris

vj = nilai setiap sel kolom

Adapun langkah-langkah dalam metode MODI adalah :

a. Menentukan nilai uiuntuk setiap baris dan nilai-nilai vi untuk setiap kolom

dengan menggunakan hubungan cij = ui + vi untuk semua variabel basis

dan menentukan nilai u1= 0

b. Menghitung perubahan biaya dij untuk setiap variabel non basis dengan

menggunakan rumus dij = cij - mi + ni

c. Apabila hasil perhitungan terdapat nilai dij negatif, maka solusi belum

optimal. Oleh karena itu dipilih Xij dengan nilai dij negatif terbesar sebagai

entering variabel.

d. Mengalokasikan sejumlah nilai ke entering variabel Xij sesuai dengan

proses stepping stone dan mengulangi langkah pertama.

(Sri Rahmawati, 2016)

2.4 Sistem Distribusi

Distribusi merupakan proses pemindahan barang-barang dari tempat produksi ke

berbagai tempat atau daerah yang membutuhkan. Kotler (2005) mendefinisikan

bahwa distribusi akan mencakup perencanaan, pelaksanaan dan pengawasan arus

bahan dengan memperoleh produk akhir dari tempat produksi dengan memperoleh

keuntungan. Sebagian besar perusahaan menyatakan bahwa tujuan distribusi adalah

membawa barang dalam jumlah tepat, pada waktu yang tepat, dan dengan biaya

serendah mungkin.

Aspek terpenting dari distribusi suatu produk adalah biaya pengangkutan

sedangkan biaya pengangkutan sangat dipengaruhi oleh tarif angkut. Dengan

demikian, tingginya biaya pengangkutan akan mempersempit wilayah pemasaran


19

suatu produk. Panjang pendeknya distribusi pemasaran tergantung beberapa faktor

antara lain :

1. Jarak antara produsen dan konsumen, artinya semakin jauh jarak antara

produsen dan konsumen maka biasanya semakin panjang saluran yang akan

ditempuh oleh produk.

2. Cepat tidaknya produk rusak, artinya produk yang cepat atau mudah rusak

harus segera diterima konsumen, dengan demikian menghendaki saluran yang

pendek dan cepat.

3. Skala produksi, artinya bila produksi berlangsung dalam ukuran kecil maka

jumlah produk yang dihasilkan dalam ukuran kecil pula, sehingga tidak akan

menguntungkan jika produsen menjualnya langsung ke pasar. Dalam kondisi

demikian kehadiran pedagang perantara diharapkan, agar saluran yang dilalui

produk cenderung panjang.

4. Posisi keuangan perusahaan. Produsen yang kondisi keuangannya kuat

cenderung untuk memperpendek saluran tataniaga. Agar efektif,

pengoperasian aset sehari-hari harus mengimplementasikan strategi-strategi

yang telah dikembangkan berdasarkan struktur dan otomatisasi rantai

pasokan. Proses yang dijalankan adalah bagaimana membawa produk yang

benar ke outlet yang benar dan pelanggan yang tepat pada waktu yang tepat

pula.

Ada kemungkinan kesalahan apabila sasarannya tidak memenuhi tuntutan

pelanggan 100 persen. Persediaan harus tersedia di tempat yang tepat pada waktu

yang tepat setiap hari tanpa ada yang gagal. Tanpa adanya persediaan yang tepat,

proses distribusi lainnya tidak akan dapat beroperasi. Pengiriman kilat merupakan

pengecualian yang jarang dilakukan. Pada prinsipnya, agar dapat beroperasi setiap

hari, persediaan harus ada di tempat yang benar pada waktu yang tepat. (Diah

Purnama Sari, 2014)

2.5 Degenerasi dan Redundansi

Sebelum menguji optimalitas tabel, terlebih dahulu menghitung jumlah variabel basis

yang ada pada tabel penyelesaian awal yakni harus memenuhi 𝑚+𝑛−1 (𝑚 = jumlah

baris dan 𝑛 = jumlah kolom buah variabel basis (sel yang terisi)) agar proses


20

pengujian keoptimalan dan iterasi capat dilakukan. Akan tetapi dalam menghitung

variabel basis ada kondisi dimana variabel basis yang ada tidak dapat memenuhi

𝑚+𝑛−1 buah variabel basis. Hal ini terjadi karena adanya degenerasi dan redundansi.

Pada degenarasi sel yang terisi kurang dari 𝑚+𝑛−1 buah variabel basis, sedangkan

pada redundansi sel yang terisi melebihi dari 𝑚+𝑛−1 buah variabel basis. Untuk

mengatasi degenerasi, dapat dilakukan penambahan sel terisi dengan cara

memasukkan nilai 0 (sebanyak yang dibutuhkan) ke dalam sel sehingga jumlah sel

terisi sama dengan 𝑚+𝑛−1, sementara kasus redundasi dapat diatasi dengan

megurangi sel alokasi yaitu menggabungkan dua sel ke dalam satu sel degan

memperhatikan harga sel. (Putri Winda Sari, 2016)


BAB 3

METODOLOGI PENELITIAN

Pada bab ini disampaikan metodologi yang digunakan penulis dalam

melakukan penelitian ini. Selain itu, diberikan langkah-langkah sistematis dan

diagram alur sebagai penjelasan tentang proses yang akan dilakukan penulis

dalam melakukan penelitian.

Metodologi yang digunakan dalam penelitian ini adalah menggunakan

metode kepustakaan, yaitu dengan mengumpulkan, membaca, dan mempelajari

referensi-referensi, jurnal, buku-buku yang berkaitan, maupun informasi-

informasi yang didapat dari internet. Berikut ini langkah-langkah yang dilakukan

penulis dalam melakukan penelitian, yaitu:

1. Studi pustaka

Tahap ini dimulai dengan studi kepustakaan yaitu mengumpulkan bahan

referensi, mempelajari serta menggali informasi baik dari buku, artikel,

paper, jurnal, makalah, maupun situs internet mengenai metode North west

corner method (NWCM), Least cost method, approximation method (VAM)

dan MODI (Modified Distribution)

2. Menjelaskan secara rinci setiap metode transportasi North west corner

method (NWCM), Least cost method, approximation method (VAM)

sebagai metode penentuan feasible solution dan Modified Distribution

(MODI) sebagai metode uji optimalitas

3. Menganalisis karakteristik tiap metode dan penggunaan masing-masing

metode

4. Penerapan dalam penyelesaikan contoh kasus dengan metode yang sudah

dianalisis

5. Membuat kesimpulan dan saran.


22

3.1 Kerangka Penelitian

Berikut ini adalah susunan kerangka teoritis yang disajikan dalam bentuk

diagram alur.

LATAR BELAKANG

Menentukan metode optimal untuk

menyelesaikan kasus transportasi

dalam pendistribusian barang

STUDI LITERATUR

Mempelajari teori yang berkaitan dengan masalah

penelitian yakni : program linear, metode transportasi,

jurnal-jurnal terkait masalah optimalisasi biaya distribusi

MENENTUKAN FOKUS PENELITIAN

Menentukan judul dan batasan masalah yang akan dianalisis,

yakni metode transportasi menentukan solusi awal NWCM,

LCM, VAM, dan metode uji optimalitas MODI

PEMBAHASAN

Mengkaji dan menganalisis secara rinci karakteristik dan

alur kerja setiap metode dalam menyelesaikan kasus

transportasi untuk menentukan solusi awal

NWCM LCM VAM

UJI OPTIMALITAS

Solusi awal dari setiap metode

dengan MODI

PENERAPAN

SEMUA METODE

PADA CONTOH

SOAL METODE OPTIMAL

KESIMPULAN DAN

SARAN


BAB 4

PEMBAHASAN

4.1 Masalah Transportasi

Pada umumnya, masalah transportasi berhubungan dengan distribusi suatu produk

tunggal dari beberapa sumber, dengan penawaran terbatas, menuju beberapa tujuan,

dengan permintaan tertentu, pada biaya transport minimum. Secara khusus masalah

transportasi merupakan hal yang berkaitan dengan persediaan (supply), permintaan

(demand), dan biaya pengiriman (shipping cost) barang atau produk tunggal tertentu

yang bertujuan untuk megoptimalkan biaya pendistribusian.

Dalam hal ini produk yang didistribusikan adalah produk tunggal, maka suatu

tujuan (destination) dapat memenuhi jumlah permintaan yang dibutuhkan dari

beberapa sumber (source) yang berbeda, demikian halnya satu sumber dapat

mengirimkan sejumlah barang ke beberapa tujuan sesuai dengan jumlah barang yang

tersedia. Untuk lebih memahami pernyataan tersebut, penulis memperlihatkan

dengan gambar jaringan transportasi berikut ini.

Gambar 4.1 Representasi Jaringan Sederhana Masalah Transportasi


24

Gambaran umum dari sebuah masalah transportasi berdasarkan representasi

jaringan Gambar 4.1 dapat di uraikan dalam 3 hal berikut.

1. Sejumlah m titik sumber dapat mengirimkan sejumlah produk tunggal. Titik

sumber i dapat menyediakan maksimal si unit produk.

2. Sejumlah n titik tujuan tempat produk dikirimkan, dengan setiap titik j harus

menerima minimal dj unit produk.

3. Setiap unit produk yang dihasilkan pada sumber i dan dikirimkan ke tujuan j

dihubungkan sebuah variabel biaya cij, dan variabel jumlah barang yang

dikirimkan dari titik sumber i ke titik tujuan j adalah xij

Masalah transportasi ini dapat diperlihatkan dalam contoh sebuah perusahaan

pembuatan barang atau pabrik yang mendistribusikan hasil produksi ke beberapa

gudang. Sebuah perusahaan memiliki tiga buah pabrik yakni P1, P2, P3 yang

memproduksi produk yang sama. Dari ketiga pabrik, produk tersebut di angkut ke

tiga buah gudang yakni W1 , W2 , W3. Setiap pabrik memiliki kapasitas produksi

barang yang terbatas, dan masing-masing gudang memiliki kapasitas permintaan

tertentu. Setiap pabrik mendistribusikan hasil produksi ke setiap gudang, dengan

biaya transportasi berbeda-beda untuk setiap rute pengiriman. Permasalahan yang

perlu diselesaikan dalam hal ini adalah menentukan banyaknya jumlah barang yang

dikirimkan ke setiap gudang dengan tujuan meminimalkan total biaya transportasi.

Uraian ini dapat diperlihatkan dalam Gambar 4.2 jaringan transportasi

berikut.

Gambar 4.2 Jaringan transportasi


25

Data dari suatu masalah transportasi yang bersangkutan dapat dapat diringkas

dalam sebuah tabel transportasi. Tabel transportasi secara implisit memperlihatkan

batasan jumlah persediaan dan permintaan serta biaya pengiriman antara setiap

sumber dan tujuan seperti yang diperlihatkan pada Tabel 4.1 berikut.

Tabel 4.1 Tabel Masalah Transportasi

4.2 Model Matematika Masalah Transportasi

Sebelum dilanjutkan menentukan solusi masalah transportasi menggunakan metode

yang sudah dikembangkan khusus untuk masalah tersebut, maka terlebih dahulu

diformulasikan dalam sebuah model matematika seperti masalah program linier

umumnya. Model program linier dari masalah transportasi yang dibentuk dikenal

dengan istilah model transportasi.

Data yang dimuat dalam sebuah model transportasi meliputi

1. Level supply dari setiap sumber dan jumlah demand dari setiap tujuan

2. Biaya transportasi setiap unit produk dari setiap sumber ke setiap tujuan

Gambar 4.3 Model jaringan transportasi


26

Gambar 4.3 mempresentasikan sebuah model transportasi dengan m sumber

(sources) S1, S2, ….Sm yang memiliki ai (i = 1,2,3,...m) unit supply secara berurutan

dan n tujuan (destination) D1, D2, …, Dn dengan bj (j = 1,2,3,..., n) unit permintaan

secara berurutan. Setiap sumber atau tujuan digambarkan melalui sebuah titik. Rute

atau alur pendistribusian antara sumber dan tujuan direpresentasikan dengan sebuah

busur yang menghubungkan dua titik. Biaya transportasi setiap unit antara sumber i

dan tujuan j adalah cij dan jumlah unit yang dikirim setiap rute dari sumber i ke

tujuan j disimbolkan xij.

Tabel 4.2 Tabel Transportasi secara umum

Misalkan xij merupakan banyaknya jumlah produk yang diangkut dari sumber

i ke tujuan j. Biaya yang diasosiasikan dengan perpindahan ini adalah hasil kali biaya

perunit dengan banyak unit.

Biaya alokasi = cost x quantity = cij xij

Biaya transportasi sejumlah barang dari sejumlah sumber i menuju seluruh

tujuan j dinyatakan dalam persamaan berikut.

(4.1)


27

Maka, total biaya transportasi produk dari seluruh sumber ke seluruh tujuan

adalah:

Total biaya:

(4.2)

Karena tujuan dari masalah transportasi adalah meminimumkan total biaya

maka model transportasi nya adalah sebagai berikut:

Meminimalkan:

(4.3)

Dengan kendala:

(4.5)

(4.5)

(4.6)

Keterangan:

Z = fungsi tujuan; total biaya transportasi

cij = biaya transportasi per unit barang dari sumber i ke tujuan j

xij = jumlah barang yang didistribusikan dari sumber i ke tujuan j



𝑚 = banyaknya sumber

𝑛 = banyaknya tujuan

(Akpan, Stephen dkk. 2015)


28

Untuk lebih memahami dalam memodelkan sebuah masalah transportasi,

penulis mengambil sebuah contoh sederhana kasus transportasi berikut ini. Tiga buah

pabrik A, B dan C memproduksi gula yang berlokasi di wilayah yang berbeda-beda.

Pabrik A memproduksi b1 ton gula pertahun dan pabrik B memproduksi b2 ton

pertahun dan pabrik C memproduksi c3 ton gula pertahun. Gula tersebut di butuhkan

oleh 4 pasar W, X, Y dan Z dengan masing-masing kebutuhan berturut-turut adalah

d1, d2, d3 dan d4 ton. Biaya transportasi setiap ton gula dari setiap pabrik ke setiap

pasar diberikan pada matriks transportasi Tabel 4.3 berikut. Tujuan dari masalah ini

adalah untuk mengangkut gula dari pabrik menuju pasar dengan total biaya

transportasi minimum.

Tabel 4.3 Contoh Tabel Transportasi Gula

Model transportasi:

Minimumkan total biaya:

Z = c11 x11 + c12 x12 + c13 x13 + c14 x14 + c21 x21 + c22 x22 + c23 x23 + c24x24+

c3x31 + c32 x32 + c33 x33 + c34 x34

Dengan kendala:

a11 x11 +a12 x12 + a13 x13 + a14 x14 ≤ b1

a21 x21 + a22 x22 + a23 x23 + a24 x24 ≤ b2

a31 x31 + a32 x32 + a33 x33 + a34 x34 ≤ b3

a11 x11 + a21 x21 + a31 x31 ≥ d1

a12 x12 + a22 x22 + a32 x32 ≥ d2

a13 x13 + a23 x23 + a33 x33 ≥ d3

a14 x14 + a24 x24+ a34 x34 ≥ d4

dan semua xij and xji lebih dari 0 untuk i = 1,2,3 and j = 1,2,3,4. (supply ≥ 0)


29

Contoh soal tersebut memiliki ciri-ciri

1. Memiliki fungsi tujuan

2. Memiliki persamaan kendala yang saling berkaitan

3. Persamaan kendala bernilai tidak negatif

4. Hubungan atara variabel dan kendala linier

Ciri-ciri ini juga adalah ciri-ciri dari persoalan program linier sehingga benar bahwa

masalah transportasi adalah bentuk khusus masalah program linier.

4.3 Penyelesaian Masalah Transportasi

Masalah transportasi sebagai bentuk khusus dari masalah program linier dapat

diselesaikan dengan metode simpleks. Tetapi karena struktur persamaan kendala

yang lebih kompleks yakni adanya kombinasi tanda ≤ dan ≥ pada kendala, ketika

diselesaikan dengan metode simpleks, diperlukan waktu yang lebih banyak atau lama

dan mengalami kesulitan menentukan solusi akhir. Karena itu digunakan sebuah

metode khusus yang disebut dengan algoritma transportasi atau metode transportasi.

Sebuah pendekatan untuk menentukan solusi dari sebuah persoalan

transportasi dengan algoritma transportasi adalah sebagai berikut.

4.3.1 Menentukan Solusi Layak Awal (initial basic feasible solution )

Solusi layak awal merupakan solusi yang diperoleh dengan mengalokasikan seluruh

produk ke tujuan dengan memenuhi seluruh ketentuan kendala dan fungsi tujuan

yang mana nilai solusi yang diperoleh belum tentu optimal.

Langkah-langkah menentukan solusi layak awal:

1. Membuat model transportasi.

Menyajikan seluruh informasi dari suatu masalah transportasi yaitu supply

dari seluruh sumber dan permitaan dari seluruh tujuan serta biaya pengiriman

kedalam tabel berbentuk matriks yang terdiri dari sel-sel tempat alokasi yang

terbentuk dari baris dan kolom.

2. Menyeimbangkan masalah transportasi yang akan diselesaikan.

Artinya melihat apakah jumlah supply (Σai) sama dengan jumlah demand

(Σbj) (Σai = Σbj). Jika sama dapat dilanjutkan ke langkah kedua. Jika tidak

maka harus diseimbangkan terlebih dahulu dengan menambahkan sebuah


30

kolom dummy atau baris dummy. Biaya dari sel dummy adalah nol. Jika Σai

lebih besar dari Σbj maka yang ditambah adalah sebuah kolom dummy,

dengan maksimal unit yang ditampung adalah sebanyak Σai - Σbj dan nilai

biaya dari sel-sel tersebut adalah nol. Demikian juga jika Σbj lebih besar dari

Σai maka ditambahkan sebuah baris dummy, dengan maksimal unit yang

ditampung adalah sebayak Σbi - Σaj dan nilai biaya dari sel-sel tersebut adalah

nol. Ketika proses penyeimbangkan sudah selesai maka dilanjutkan ke

langkah kedua. Dan sama hal nya dengan masalah program linier, maka

pertidaksamaan harus diubah ke bentuk persamaan dengan menambahkan

slack variable yaitu variabel dummy.

3. Sebuah solusi layak awal dapat ditentukan menggunakan 3 metode, yaitu

a) North-west corner method (NWCM)

b) Leas-cost cell method

c) Vogel’s Approximation method (VAM)

(Gupta, PK dan Hira, DS. 2007)

4.3.2 Menetukan Solusi Optimum (optimum solution)

Setelah solusi layak awal diperoleh, selanjutnya dilakukan evaluasi terhadap hasil

alokasi solusi tersebut untuk mecapai solusi optimum. Ada dua metode yang dapat

digunakan untuk menguji keoptimalan solusi layak awal yaitu:

a) Stepping Stone Method

b) Modified Distribution Method (MODI)

4.3.3 Ciri-ciri Solusi Layak Awal

Solusi layak awal yang diperoleh dinyatakan layak apabila memenuhi beberapa ciri

berikut.

1. Alokasi yang dibuat harus memenuhi keseluruhan syarat, yakni

menghabiskan seluruh ketersediaan supply dan memenuhi kapasitas demand

2. Memenuhi ketidaknegatifan persamaan kendala

3. Total jumlah sel alokasi atau variabel basis harus sama dengan m+n-1,

dengan m adalah banyak baris dan n banyak kolom. Dalam suatu masalah LP

banyaknya variabel basis dalam tabel simpleks sama dengan banyaknya


31

kendala. Namun, pada masalah transportasi, terdapat sebuah kendala yang

berlebihan (redundant). Kondisi keseimbangan Σai = Σbj, memberikan

kenyataan bahwa jika m+n-1 kendala terpenuhi kemudian m+n persamaan

juga akan terpenuhi. Hanya terdapat m+n-1 persamaan independent.

Sehingga, solusi awal hanya memiliki m+n-1 variabel basis. (Murthy, P R.

2007)

4.4 Metode Transportasi

Setelah menjelaskan alur penyelesaian sebuah masalah transportasi berdasarkan

algoritma transportasi yang ada, maka penulis melanjutkan dengan mengkaji lebih

spesifik bagaimana alur kerja dan karakteristik setiap metode dalam menentukan

solusi awal maupun solusi optimal. Tujuannya adalah untuk memperlihatkan

perbedaan setiap metode dan melihat keoptimalan masing-masing metode dalam

menyelesaikan masalah transportasi. Dalam hal ini dianggap masalah transportasi

yang akan diselesaikan seimbang atau sudah diseimbangkan dengan variabel dummy.

4.4.1 Metode Untuk Menentukan Solusi Layak Awal

4.4.1.1 North-West Corner Method (NWCM)

Sesuai dengan nama metode ini, maka alokasi pertama dilakukan di sel paling kiri

atas (northwest) matriks transportasi kemudian bergerak ke kanan atau ke bawah

sesuai permintaan dan kapasitas produksi yang sesuai.

Langkah-langkahnya dapat diringkas seperti berikut ini.

1. Mulai pada pojok barat laut, sel paling kiri atas tabel matriks transportasi.

Bandingkan jumlah supply pada sumber 1 (S1) dengan jumlah demand pada

tujuan 1 (D1).

a) Jika D1 < S1, jika banyak jumlah permintaan yang dibutuhkan pada D1

kurang dari banyaknya unit yang tersedia pada S1, maka alokasikan pada

sel x11 sama dengan jumlah permintaan pada D1, sehingga jumlah supply

seimbang dengan jumlah demand, dan sisa supply yang masih tersedia di

S1 adalah S1 - D1 akan dialokasikan ke sel selanjutnya dilanjutkan secara

horizontal (x12) memenuhi permintaan tujuan kedua D2.

b) Jika D1 = S1, alokasikan ke dalam sel x11 sabanyak demand pada D1,

hitung keseimbangan antara supply dan demand, tidak ada sisa pada S1


32

dan alokasi dilanjutkan ke sel selanjutnya secara diagonal dari sumber S2

ke tujuan D2 (x22) karena semua supply sumber 1 sudah habis

dialokasikan.

c) Jika D1 > S1, alokasikan ke dalam sel x11 sebanyak jumlah supply dari S1,

hitung keseimbangan supply dan demand dan lanjutkan alokasi secara

vertikal ke sel x21 dari sumber S2 untuk memenuhi sisa permintaan dari

tujuan D1 karena jumlah supply dari S1 masih kurang. Jika sudah selesai

memenuhi seluruh permintaan D1 dilanjutkan alokasi ke tujuan D2 dengan

supply yang masih tersedia di S2.

2. Lanjutkan dengan cara yang sama sampai semua penawaran telah dihabiskan

dan keperluan permintaan telah dipenuhi.

(Gupta, PK dan Hira, DS. 2007)

Contoh berikut ini memperlihatkan proses metode NWCM menentukan

solusi layak awal dari suatu masalah transportasi. Contoh ini menggambarkan tiga

buah pabrik yang memproduksi barang dan tiga pasar sebagai tujuan distribusi. Tabel

4.4 memperlihatkan kapasitas supply setiap pabrik, dan demand setiap pasar dan juga

biaya pengiriman tiap unit dari pabrik ketiap pasar.

Tabel 4.4 Tabel distribusi dari 3 pabrik ke 3 pasar

Maka penentuan solusi awal dengan metode NWCM ada sebagai berikut.

1. Sesuai dengan aturan ini, alokasi pertama dimulai pada sel kolom dan baris

pertama misalkan xP1W1, yaitu irisan dari P1 dan W1 dengan biaya 3. Total

demand yang dibutuhkan W1 adalah 20 dan supply P1 sebanyak 30. Maka

dialokasikan sebanyak 20 (min 20 ; 30) ke sel x11, semua demand W1 sudah

terpenuhi dan sisa pada sumber P1 sebanyak 10 unit (30-20) akan


33

dialokasikan pada sel xP1W2 selanjutnya secara horizontal utuk memenuhi

demand W2.

2. Total demand pasar pada kolom W2 sebanyak 20 dan total supply pada P2

adalah 10 unit, maka 10 unit tersebut dialokasikan ke sel xP1W2 dan supply

pada baris pertama sudah habis.

3. Sekarang, berpindah secara vertikal ke sel xP2W2. Pada sel ini, demand pasar

yang masih tersisa adalah 10 unit dan kapasitas supply sebannyak 25,

alokasikan 10 unit ke sel ini dan habiskan semua demand pasar W2.

Kemudian, pindah ke sel xP2W3 dan alokasikan 15 unit supply yang masih

tersedia dari pabrik P2 ke sel ini, menghabiskan kapasitas supply pabrik P2

menyisakan 20 unit kebutuhan pasar W3.

4. Sekarang kapasitas pabrik P3 adalah 20 unit yang akan memenuhi kebutuhan

pasar W3 jadi dialokasikan 20 unit ke sel xP3W3 habiskan seluruh kapasitas

pabrik dan kebutuhan pasar.

Pegalokasian ini diperlihatkan pada tabel 4.5 di bawah ini:

Tabel 4.5 Hasil alokasi barang dengan NWCM dari 3 pabrik ke 3 pasar

Tabel 4.6 Hasil alokasi NWCM

Sumber /Pabrik Tujuan / Pasar Unit barang Harga (satuan)

P1 W1 20 20 x 3 = 60

P1 W2 10 10 x 4 = 40

P2 W2 10 10 x 1 = 10

P2 W3 15 15 x 5 = 75

P3 W3 20 20 x 3 = 60

Total 75 245 satuan harga


34

4.4.1.2 Least-Cost Method (LCM)

Metode ini berusaha mencapai tujuan minimisasi biaya dengan mengalokasikan

sebanyak mungkin pada sel dengan biaya terendah dan proses alokasi akan berlanjut

pada sel biaya terendah kedua demikian seterusnya sampai seluruh kendala

terpenuhi.

Berikut ini akan diuraikan prosedur metode Least-Cost Method dalam

menentuka solusi layak awal.

1. Identifikasi sel dengan biaya cij terendah pada tabel matriks transportasi yang

diberikan. Sebagai contoh khusus adalah 0 untuk masalah yang memuat

variabel dummy. Jika ada lebih dari satu sel yang memiliki jumlah biaya yang

sama, pilih secara sembarang untuk memenuhi syarat kendala dan

mengalokasikan sebanyak untuk memperoleh biaya lebih murah.

2. Alokasikan xij pada sel yang telah dipilih sebanyak mungkin (min si, dj)

sesuai dengan ketersediaan supply dan keperluan demand.

3. Coret atau silang kolom atau baris yang telah memenuhi kendala supply atau

demand. Jika sebuah baris dan kolom keduaya sudah terpenuhi maka coret

hanya satu saja.

4. Sesuaikan supply dan demand untuk baris dan kolom yang tidak dicoret, dan

lakukan proses yang sama untuk memenuhi kendala.

5. Ketika tepat satu baris atau kolom yang tersisa, semua variabel sisa

merupakan basic dan ditetapkan sebagai alokasi layak.

(Mulyono, Sri. 2004)

Untuk memberi ilustrasi dari metode Least-Cost Method, penulis

memperlihatkan contoh masalah yang sama pada NWCM sebelumnya menentukan

solusi layak awal dengan metode LCM sebagai berikut.

Tabel 4.7 Tabel transportasi


35

Proses menentukan solusi layak awalnya adalah sebagai berikut.

1. Mulai dengan membuat alokasi pertama pada sel dengan biaya perunit

terendah. Pada contoh ini adalah sel xP2W2 dan dialokasikan sebanyak 20 unit

menghabiskan semua syarat dar pasar W2.

2. Selanjutnya pindah ke sel dengan biaya terendah kedua dan membuat alokasi

untuk kapasitas yang tersisa dan ketentuan dari baris dan kolomnya. Pada

contoh ini, terdapat sel dengan harga yang sama antara sel xP1W3 dansel

xP2W1, maka dipilih sel xP1W3 karena akan menghabiskan kapasitas maksimum

yaitu 30

3. Proses yang sama diulang sampai seluruh ketentuan kendala terpenuhi.

Solusi awal yang diperoleh diperlihatkan pada Tabel 4.8 berikut ini.

Tabel 4.8 Hasil menentukan solusi layak awal dengan LCM

Tabel 4.9 Hasil alokasi LCM

Sumber /Pabrik Tujuan / Pasar Unit barang Harga (satuan)

P1 W3 30 30 x 2 = 60

P2 W1 5 5 x 2 = 10

P2 W2 20 20 x 1 = 20

P3 W1 15 15 x 4 = 60

P3 W3 5 5 x 3 = 15

Total 75 165 satuan harga


36

4.4.1.3 Vogel’s Approximation Method (VAM)

VAM adalah sebuah metode perbaikan dari metode Least-cost yang secara umum

menentuka solusi awal yang lebih baik. VAM melakukan alokasi dalam suatu cara

yang akan meminimumkan penalty (opportunity cost) dalam memilih kotak yang

salah untuk suatu alokasi.

Langkah-langkah dari metode VAM dalam menentukan solusi layak awal

adalah sebagai berikut.

1. Hitung opportunity cost untuk setiap baris dan kolom. Opportunity cost

untuk setiap baris i dihitung dengan mengurangkan nilai cij terkecil pada baris

tersebut dari nilai cij 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 minimun.

2. Pilih baris atau kolom dengan opportunity cost terbesar (jika terdapat nilai

kembar, pilih secara sembarang). Alokasikan sebanyak mungkin ke kotak

dengan nilai cij minimum pada baris atau kolom yang dipilih. Untuk cij

terkecil, xij = minimum ( si, dj ). Artinya penalty terbesar dihindari.

3. Sesuaikan penawaran dan permintaan untuk menunjukkan alokasi yang sudah

dilakukan. Hilangkan semua baris dan kolom di mana penawaran dan

permintaan sudah dihabiskan.

4. Jika semua penawaran dan permintaan belum dipenuhi, kembali ke langkah 1

dan hitung lagi opportunity cost yang baru. Jika semua kendala penawaran

dan permintaan telah habis terpenuhi, solusi awal telah dipenuhi.

(Agustini, Dwi Hayu dan Rahmadi, Endra. 2004)

Dengan contoh soal masalah yang sama diperlihatkan bagaimana menentukan

solusi layak awal dengan metode VAM sebagai berikut

Tabel 4.10 Tabel Transportasi contoh soal VAM


37

Langkah-langkah untuk menentukan sebuah solusi layak awal dari tabel di

atas adalah sebagai berikut.

1. Identifikasi baris dan kolom yang memiliki biaya terendah untuk dicari

opportunity cost terbesar. Pada contoh ini, opportunity cost terbesar adalah 2

pada kolom W2, maka kolom yang dipilih untuk alokasi adalah kolom W2.

2. Alokasikan jumlah maksimum yang mungkin pada sel yang bersangkutan

dengan biaya terendah, pada kolom W2 adalah 1, karena itu sel xP2W2 dipilih

untuk alokasi, 20 unit dialokasikan ke dalam sel tersebut dan colom W2

dihapus karena syarat kebutuhan pasar W2 sudah dipenuhi.

3. Hitung ulang nilai opportunity cost baris dan kolom untuk tabel transportasi

yang sudah dikurangi. Cara yang sama diulangi sampai semua keseluruhan

persyaratan dipenuhi.

Hasil alokasi dari contoh soal dengan metode VAM diperlihatkan pada

Tabel 4.11 berikut.

Tabel 4.11 Hasil alokasi dengan metode VAM

Tabel 4.12 Hasil alokasi


38

Sekarang akan diperlihatkan perbandingan dari ketiga metode yang sudah

diuraikan sebelumnya yaitu NWCM, LCM dan VAM dalam menentukan solusi

layak awal (basic feasible solution) suatu masalah transportasi pada Tabel 4.13 di

berikut.

Tabel 4.13 Perbandingan proses alokasi menentukan solusi layak awal

dari 3 metode transportasi

No North-West Corner

(NWCM)

Least-Cost Method

(LCM)

Vogel’s Approximation

Method (VAM)

1. Alokasi yang dilakukan

dimulai dari sel sudut

atas sisi kiri tanpa

mempertimbangkan

biaya sel tersebut.

Alokasi dilakukan

bergantung pada biaya

sel. Biaya terendah dipilih

pertama kali sampai

akhirnya biaya tertinggi.

Alokasi bergantung

pada nilai opportunity

cost dari sel yaitu selisih

dua biaya sel terendah.

2. Karena tidak adanya

pertimbangan pada nilai

biaya sel, secara

langsung total biaya

transportasi akan lebih

tinggi dari pada metode

yang lain.

Karena sel yang dipilih

dipertimbangkan ketika

melakukan alokasi, maka

total biaya transportasi

akan secara komparatif

berkurang dari metode

NWCM.

Karena alokasi yang

dibuat bergatung pada

nilai opportunity cost

sel, maka solusi layak

awal yang diperoleh

akan menjadi sangat

lebih mendekati solusi

optimal.

3. Memerlukan waktu

yang relatif singkat

karena proses alokasi

tanpa ada iterasi.

Metode ini cocok untuk

memperoleh solusi

layak awal dengan

cepat.

Metode ini memerlukan

waktu yang lebih lama

dari NWCM karena

penentuan solusi

diurutkan dari biaya

terendah sehingga iterasi

sebanyak urutan biaya

terendah. Solusi layak

awal yang diperoleh akan

sangat lebih mendekati

solusi optimal.

Metode ini memerlukan

waktu yang lebih lama

untuk memperoleh

solusi layak awal karena

proses menyeleksi sel

alokasi lebih kompleks

jumlah iterasi yang lebih

banyak dari metode

NWCM dan LCM. Tapi

solusi yang diperoleh

akan sangat lebih

mendekati solusi

optimal.

4. Ketika yang dibutuhkan

hanya solusi layak awal

tanpa melihat besar total

biaya, lebih baik untuk

menggunakan NWCM.

Ketika yang dibutuhkan

adalah solusi optimal,

maka lebih baik

menggunakan metode

least-cost untuk

menentukan solusi layak

awal dan MODI untuk

solusi optimal.

VAM dan MODI adalah

pilihan terbaik untuk

memperoleh solusi

optimal.

(Murthy, P R. 2007)


39

Pada contoh soal yang penulis berikan pada uraian sebelumnya, total biaya

transportasi yang diperoleh dari alokasi menggunakan metode NWCM adalah 245

satuan harga, dengan LCM 165 satuan harga, dan dengan VAM 165 satuan harga.

Total biaya tertinggi diperoleh dari metode NWCM, sedangkan metode NWCM dan

LCM menghasilkan total biaya yang sama yaitu 165 satuan harga. Perbedaan harga

yang cukup besar dari hasil alokasi menggunakan tiga metode tersebut yaitu 80

(selisih 245 dan 165) satuan harga menunjukkan bahwa NWCM dapat dikategorikan

metode yang paling tidak efesien, dapat dilihat dari solusi layak awal yang diperoleh

cukup tinggi. Hal ini diakibatkan karena tidak mempertimbangkan biaya transportasi

per unit dalam membuat alokasi sehingga.

Sekarang penulis akan melanjutkan mengkaji metode yang digunakan untuk

menguji solusi layak awal yang sudah diperoleh untuk melihat apakah solusi tersebut

merupakan solusi optimal atau tidak.

4.4.2 Metode Uji Optimalitas

Ketika solusi layak awal untuk sebuah masalah transportasi sudah ditemukan,

langkah selanjutnya yang harus dilakukan adalah menguji apakah solusi yang

diperoleh optimal atau tidak. Masalah ini dapat diselesaikan dengan dua metode,

yaitu:

a) Stepping Stone Method

b) Modified Distribution Method

4.4.2.1 Stepping Stone Method

Setelah solusi layak awal diperoleh dari sebuah masalah transportasi dengan metode

yang tersedia, langkah berikutnya adalah mengevaluasi sel kosong lain untuk

meminimalkan biaya transport dengan memasukkan variabel nonbasis (yaitu alokasi

barang ke kotak kosong) ke dalam solusi. Proses evaluasi variabel nonbasis yang

memungkinkan terjadinya perbaikan solusi dan kemudian mengalokasikan kembali

dinamakan metode stepping stone.

Untuk memberi sebuah tes optimalitas pada solusi layak awal, harus

ditentukan opportunity cost dari sel-sel kosong (variabel nobasis) dalam tabel

transportasi yang tersedia. Sebuah masalah transportasi memiliki ketentuan dalam


40

mengambil keputusan suatu solusi dikatakan optimal jika dan hanya jika semua

opportunity cost bernilai positif (tidak ada satupun opportunity cost dari sel kosong

yang bernilai negatif) yang artinya tidak perlu dilakukan evaluasi iterasi selanjutnya

dan proses tes optimalitas berhenti. Jika ada satu saja opportunity cost yang bernilai

negatif maka masih ada kemungkinan terjadi penurunan biaya jika diadakan

realokasi. Karena itulah dilakukan proses evaluasi untuk seluruh sel-sel kosong.

Metode stepping stone digunakan untuk menentukan opportunity cost dari

sel-sel kosong dan akan dievaluasi dengan metodologi sebagai berikut.

1. Berikan tanda ‘+’ pada sel kosong yang akan dievaluasi

2. Mulai dari sel tersebut gambar sebuah loop (jalur tertutup) yang berpindah

secara horizontal atau vertikal dari sel variabel basis ke sel variabel basis

yang lain. Harus diperhatikan bahwa, tidak boleh ada perpindahan yang

diagonal/ menyilang. Ketika sampai pada sel variabel basis/ alokasi, terjadi

perubahan arah dan berpindah secara vertikal ke bawah atau ke atas ataupun

secara horizontal untuk mencapai sel variabel basis yang lain. Jika ditemukan

sel alokasi yang tidak memungkinkan berubah arah, abaikan dan lanjutkan

proses pada sel alokasi selanjutnya pada baris atau colom tersebut.

3. Setelah melengkapi loop tersebut, berikan tanda negativ ‘-’ dan positiv ‘+’

secara alternatif (bergantian).

4. Identifikasi jumlah unit terendah pada sel-sel yang diberi tanda negatif.

5. Jumlah muatan tersebut akan ditambahkan pada sel yang bertanda positif dan

mengurangi muatan dari sel yang diberi tanda negatif (proses realokasi).

6. Tidak diijinkan merubah sel alokasi yang tidak berada di dalam loop.

7. Proses penambahan dan pengurangan pada setiap perubahan arah loop harus

memperhatikan keseimbangan persyaratan kendala (jumlah permintaan dan

penawaran).

8. Bentuk sebuah tabel dari sel-sel kosong dan daftarkan perubahan biaya utuk

setiap perubahan muatan dari sel alokasi ke sel alokasi.

9. Jika perubahan biaya positif, artinya jika diterapkan hasil evaluasi tersebut

pada solusi yang dipilih maka biaya total akan meningkat demikan sebalikya

perubahan biaya negatif, total biaya akan berkurang jika hasil evaluasi

tersebutkan diterapkan pada solusi. Perubahan biaya disebut juga dengan


41

opportunity cost (biaya untung) namun tandanya berkebalikan dengan nilai

perubahan biaya, karena jika biaya naik keuntungan berkurang (opportunity

cost negatif) dan bila biaya menurun keuntungan meningkat (opportunity cost

positif). Maka, dalam solusi optimal dari sebuah masalah transportasi, sel-sel

kosong seharusnya tidak memiliki opportunity cost positif.

10. Ketika semua sel kosong memiliki opportunity cost negatif, solusi tersebut

dikatakan optimal. Dan sebaliknya jika masih ada opportunity cost positf

masih perlu evaluasi iterasi berikutnya dan berhenti jika semua opportunity

cost bernilai negatif atau 0 (sama artinya dengan perubahan biaya pada setiap

sel kosong positif atau 0).

(Murthy, P R. 2007)

Berikut ini diperlihatkan sebuah tabel masalah transportasi yang sudah

ditentukan solusi layak awalnya dengan metode least-cost dan akan diberikan tes

optimalitas dengan metode stepping stone.

Tabel 4.14 Tes optimalitas solusi layak awal dengan metode stepping stone

Prinsip dasar dari sebuah masalah transportasi adalah menentukan apakah

sebuah rute transportasi yang tidak digunakan dalam hal ini sel-sel kosong

memberikan total biaya yang lebih rendah jika rute tersebut digunakan. Tabel 4.14 di

atas memperlihatkan 4 sel kosong (1A, 2A, 2B, 3C) merepresentasikan rute yang

tidak digunakan. Sel 1A artinya sel yang menunjukkan tempat alokasi dari baris 1

kolom A pada tabel transportasi, demikian berlaku untuk semua sel pada tabel


42

transportasi dalam tulisan ini. Langkah pertama dalam metode stepping stone adalah

untuk mengevaluai sel-sel kosong ini untuk melihat apakah dengan meggunakan sel-

sel tersebut akan mengurangi total biaya. Jika diperoleh sebuah rute baru yang

mungkin untuk menurunkkan total biaya maka akan dialokasikan sebanyak mungkin

ke dalam sel tersebut.

Dari tabel 4.14 di atas, pertama sel kosong yang akan diberi tanda positi (+)

adalah 1A. Jika satu ton dialokasikan ke sel 1A, biaya akan bertambah $1 yakni

biaya transportasi dari sel 1A. Dengan menambah alokasi satu ton ke sel 1A, terjadi

peningkatan supply pada baris 1 menjadi 151 ton seperti diperlihatkan pada Tabel

4.15 berikut.

Tabel 4.15 Alokasi 1 ton ke sel 1A

Persyaratan kendala dari permasalahan transportasi tidak dapat diubah harus

tetap diperhatikan keseimbangan antara jumlah penawaran dan permintaan. Jika

dengan menambahkan satu ton ke dalam sel 1A, maka harus dikurangi satu ton dari

sel alokasi yang lain pada baris yang sama dengan sel 1A. Maka sel 1B adalah calon

yang logis karena memiliki 25 ton yang tersimpan pada sel tersebut. Dengan

mengurangi satu ton dari sel 1B, akibatnya total supply pada baris 1 adalah 150 ton,

yang artinya sudah memenuhi kembali batasan supply awal. Pada saat yang sama

pengurangan satu ton dari sel 1B telah mengurangi total biaya sebesar $8. Dan juga

pengurangan satu ton dari 1B mengakibatkan hanya 99 tob alokasi yang dipenuhi

pada kolom 2 sementara yang dibutuhkan adalah 100 ton, hal ini mengharuskan

penambahan 1 ton yag diperoleh dari sel alokasi yang lain. Dan yang diplih adalah


43

sel 3B yang memiliki alokasi 75 ton, sehingga kendala permintaan awal 100 ton

terpenuhi.

Tabel 4.16 Pegurangan satu ton dari sel 1B

Persyaratan dari metode stepping stone ini adalah bahwa unit dapat ditambah

dan dikurangi hanya dari sel-sel yag telah memiliki alokasi. Itulah sebabnya satu ton

ditambahkan ke sel 3B dan bukan sel 2B. Hal ini berdasarkan ketentuan dari metode

ini, sesuai dengan namanya, proses penambahan dan pengurangan unit dari sel-sel

alokasi adalah analogi menyebrangi sebuah kolam dengan melangkah pada batu-

batu. Pengalokasian satu ton tambahan pada sel 3B telah meningkatkan biaya sebesar

$5 dan juga menambahan supply pada baris ke 3 menjadi 276 ton, yang telah

melanggar batas kendala pada sumber ini. Hal ini dapat diperbaiki kembali dengan

mengurangi satu ton dari sel 3A yang memiliki 200 ton unit alokasi, dan memenuhi

batasan kendala awal pada baris 3 yang mengakibatkan pengurangan total biaya $4

biaya transportasi sel 3A. Alokasi ini diperlihatkan pada Tabel 4.16 berikut.

Tabel 4.17 Jalur tertutup metode stepping stone sel 2A


44

Dari Tabel 4.16 memperlihatkan bahwa penambahan satu ton dari sel 3A,

tidak mengganggu kendala permitaan pada kolom A, karena sebelumnya telah

ditambah satu to ke sel 1A yaitu saat pertama evaluasi alokasi sel kosong.

Sekarang, ditinjau kembali pertambahan dan pengurangan dalam biaya

sebagai hasil dari proses evaluasi metode ini. Diawali dengan penambahan biaya $6

pada sel 1A, dan pengurangan biaya $8 pada sel 1B, dan penambahan biaya $5 pada

sel 3B, dan terakhir pengurangan biaya $4 pada sel 3A, dapat dituliskan alur panah

berikut:

1A →1B → 3B→ 3A

+ $6 - $8 + $5 - $4 = -$1

Dengan kata lain, utuk setiap ton unit alokasi ke sel 1A (rute yang tidak

digunakan pada solusi layak awal), akan megurangi total biaya sebesar $1. Hal ini

menunjukkan bahwa solusi layak awal tidak optimal karena sebuah biaya yang lebih

rendah dapat dicapai dengan mengalokasikan beberapa ton unit ke sel 1A. Tujuan

dari evaluasi sel ini adalah untuk menentukan entering variable yang akan

mengurangi biaya paling besar. Variabel lain (sel kosong) yang lain bahkan mungkin

menghasilkan pengurangan biaya yang lebih besar dari sel 1A. Jika ada sel lain yang

mennyebabkan penurunan biaya lebih besar maka akan dipilih, dan jika tidak yang

dipilih sebagai entering variable adalah sel 1A. Untuk mengindentifikasi entering

variable yang tepat, sel kosng yang tersisa harus dievaluasi dengan cara yang sama

seperti sel 1A.

Evaluasi untuk sel kosong yang lain dilakukan dengan cara yang sama. Jalur

tertutup metode stepping stone untuk sel 2A diperlihatkan pada Tabel 4.17 berikut.

Tabel 4.18 Jalur tertutup stepping stone sel 2A


45

2A→ 2C →1C → 1B→ 3B → 3A

+ $7- $11 + $10 - $8 + $5 - $4 = -$1

Perlu diperhatikan bahwa jalur cel 2A lebih kompleks dari jalur sel 1A.

Alokasi pada sel 2A akan mengurangi $1, seperti yang diperlihatkan pada tabel 4.17,

yang artinya diperoleh entering variabel lain walaupun tidak lebih baik dari sel 1A.

Jalur stepping stone dan hasil komputasi dari sel kosong sisa yaitu sel 2B dan

3C diperlihatkan pada Tabel 4.18 dan Tabel 4.19 secara berurutan.

Tabel 4.19 Jalur stepping stone sel 2B

2B→ 2C →1C→1B

+ $11 - $11 + $10 -$8 = +$2

Tabel 4.20 Jalur stepping stone pada sel 3C

3C →1C → 1B→3B

+ $12 - $10 + $8 - $5 = +$5


46

Setelah keempat rute yang tidak digunakan dalam solusi layak awal

dievaluasi, terdapat dua sel yang memiliki perubahan biaya sama yaitu sel 1A dan

2A sebesar -$1 yang artinya ada dua sel yang memiliki opportunity cost bernilai

positif dan solusi awal tidak optimal. Maka dapat dipilih sembarang sel untuk

dijadikan entering variable realokasi unit, dan yang dipilih adalah sel 1A. Karena

total biaya dari model transportasi akan berkurang $1 untuk setiap ton alokasi, maka

diusahakan mengalokasikan sebanyak mungkin. Untuk menentukan jumlah berapa

alokasi, perlu untuk melihat kembali jalur sel 1A pada Tabel 4.21 berikut.

Tabel 4.21 Jalur alokasi sel 1A

Jalur stepping stone pada Tabel 4.20 di atas memperlihatkan bahwa sejumlah

ton supply harus dikurangi dari sel 1B dan 3A untuk memenuhi keseluruhan

persyaratan dan memenuhi model kendala. Karena tidak dapat mengurangi lebih dari

yang tersedia dalam sel alokasi, hanya 25 ton di sel 1B. Dengan kata lain jika

dialokasikan 25 ton ke sel 1A, maka harus dikurangi lebih dari 25 ton dari sel 1B,

dan hal itu tidak mu ngkin terjadi karena yang tersedia hanya 25 ton. Oleh karena itu

jumlah supply yang dapat dialokasikan ke sel 1A adalah 25 ton. Sehingga proses

alokasi ulang nya adalah 25 ton ditambah ke sel 1A, dikurangi dari sel 1B, ditambah

ke sel 3B, dan dikurangi dari sel 3A. Alokasi ulang ini diperlihatkan pada tabel 4.22

berikut.


47

Tabel 4.22 Iterasi kedua dari metode stepping stone

Tabel 4.22 memperlihatkan hasil satu iterasi dari metode stepping stone.

Selanjutnya dipilih x1A sebagai entering variable dan diakhiri x1B sebagai leaving

variable karena nilai alokasinya menjadi 0. Selanjutnya dilakukan evaluasi apakah

solusi yang diperlihatkan pada tabel 4.21 sudah optimal atau belum. Caranya dengan

membuat jalur dari rute yang tidak digunakan yang dimulai dari sel kosong 2A, 1B,

2B, dan 3C. Jalur-jalur tersebut diperlihatkan pada tabel 4.23 sampai Tabel 4.26

berikut.

Tabel 4.23 Jalur Stepping-Stone untuk Cell 2A

2A→ 2C→1C → 1A

+ $7 - $11 + $10 - $6 = $0

Besar perubahan biaya dari evaluasi sel 2A dengan jalur stepping stone

adalah 0, yang artinya nilai opportuity cost sel tersebut adalah nol. Tidak ada

pengaruh jika dilakukan realokasi pada sel tersebut.


48

Tabel 4.24 Jalur Stepping-Stone untuk Cell 1B

1B→ 3B → 3A→ 1A

+ $8 - $5 + $4 - $6 = +$1

Besar perubahan biaya dari evaluasi sel 1B dengan jalur stepping stone

adalah +$1, yang artinya nilai opportuity cost sel tersebut adalah -1. Akan terjadi

penambahan +$1 biaya tiap unit jika dilakukan realokasi pada sel tersebut.

Tabel 4.25 Jalur Stepping-Stone untuk Cell 2B

2B →3B → 3A→ 1A→1C→2C

+ $11 - $5 + $4 - $6 + $10 - $11 = +$3



penambahan biaya alokasi +$3 setiap unit jika dilakukan realokasi pada sel tersebut.


49

Tabel 4.26 Jalur Stepping-Stone untuk Cell 3C

3C →3A→ 1A→1C

+ $12 - $4 + $6 - $10 = +$4



penambahan biaya alokasi +$4 setiap unit jika dilakukan realokasi pada sel tersebut.

Proses evaluasi yang telah dilakukan pada empat rute dalam iterasi kedua

metode stepping stone menunjukkan tidak adanya pengurangan biaya maka

opportunity cost dari keempat sel kosong adalah negatif, sehingga solusi yang

diperoleh pada Tabel 4.21 sebelumnya adalah solusi optimal. Dapat disimpulkan

solusi layak awal dengan yang diperoleh menggunakan metode least-cost

memerlukan dua iterasi sampai ditetapkan solusi optimal.

Tabel 4.27 Solusi optimal alternatif dengan metode stepping stone

Total biaya= 25($7) + 150($10) +150($11) + 175($4) +100($5) = $4525


50

Satu kekurangan dari metode stepping stone adalah harus membuat loop

untuk setiap sel kosong. Jika sebuah masalah transportasi yang terdiri dari m baris

dan n kolom, maka total jumlah sel kosong yang harus dievaluasi adalah sebanyak

(m x n) – (m+n-1) = (m-1)(n-1). Jumlah sel tersebut harus dikalkulasi dan jika untuk

masalah yang besar (variabel banyak), metode ini menjadi tidaka efesien dan

menghabiskan banyak waktu. Jadi, utuk tes optimalitas penulis memilih metode

MODI. Metode ini berbeda dari stepping stone karena metode MODI tidak perlu

menentukan semua jalur tertutup dari sel-sel kosong (variabel nonbasis). Sebagai

gantinya, nilai-nilai opportunity cost ditentukan secara serentak dan hanya jalur

tertutup untuk entering variabel yang diidentifikasi. Hal ini menghilangkan tugas

yang melelahkan dari identifikasi semua jalur stepping stone. Untuk lebih jelas

bagaimana cara kerja metode MODI akan penulis uraikan pada subbab berikut.

4.4.2.2 Modified Distribution Method (MODI)

Pada dasarnya metode modified distribution (MODI) adalah sebuah modifikasi dari

metode stepping stone. Dalam metode MODI, perubahan biaya sel ditentukan secara

matematis, tanpa mengidentifikasi semua sel kosong dengan jalur stepping stone.

Jika dengan metode stepping stone, untuk memperoleh opportunity cost dari

setiap sel kosong harus menulis sebuah loop dan mengevaluasi jalur tersebut

sehingga prosesnya lama dan kurang efektif. Dalam MODI, opportunity cost dari

semua sel kosong dihitung secara simultan dengan variabel dual dan hanya satu jalur

tertutup yang benilai positif terbesar (yang memungkinkan terjadinya penurunan

biaya terbesar) yang akan dieveluasi lebih lanjut. Sehingga menguragi penggunaan

waktu operasi daripada metode stepping stone.

Langkah-langkah dalam metode MODI (modified distribution) sebagai

berikut:

1. Tentukan variabel dual yang bersesuaian dengan kendala supply dan demand.

Jika ada m sumber dan n tujuan, maka akan ada m+n variabel dual. Andaikan

ui (i= 1, 2,..., m) dan vj (j= 1, 2,..., n) adalah variabel dual yang bersesuaian

dengan kendala supply dan demand dan cij adalah biaya sel alokasi, untuk

menentukan nilai variabel dual dapat dihitung dengan persamaan ui + vj = cij

; xij > 0 untuk semua sel alokasi (variabel basis).


51

2. Setiap solusi layak awal memiliki m+n-1 variabel basis untuk xij > 0.

Sehingga akan ada m+n-1 persamaan untuk menentukan m+n variabel dual.

Satu dari variabel dual tersebut dapat dipilih secara sembarang biasanya u1=0.

3. Jika xij = 0 (bayak unit pada sel kosong), nilai variabel dual yang dihitung

akan dibandingkan dengan nilai cij pada sel tesebut sebagai cij - ui - vj, hasil

kalkulasi nya disimpan dalam variabel dij merupakan besar perubahan biaya

yang terjadi dari evaluasi sel-sel kosong. Jika cij - ui - vj ≥ 0 artinya perubahan

biaya positif (opportunity cost negatif), melalui theorem of complementary

slackness dapat diperlihatkan bahwa solusi tersebut optimal, sama halnya

dengan stepping stone.

4. Nilai opportunity cost memiliki beberapa arti sebagai berikut:

a) Jika semua dij > 0 opportunity cost negatif maka solusi layak awal

optimal dan tunggal

b) Jika semua dij ≥ 0; minimal satu dij = 0, opportunity cost negatif

solusi optimal dan terdapat solusi (rute) alternatif lain yang optimal

c) Jika minimal ada satu dij < 0 oportunity cost positif maka solusi tidak

optimal

d) Jika satu atau lebih cij - ui - vj < 0 oportunity cost positif, artinya solusi

layak awal tidak optimal dan masih harus dilakukan realokasi. Sel

dengan nilai cij - ui - vj terkecil akan dipilih sebagai entering variabel

dan dialokasikan sebanyak mungkin sesuai dengan kendala supply

dan demand. Realokasi meyebabkan perubahan sel basis menjadi sel

nonbasis demikian sebaliknya. Ketika solusi masih tidak optimal

maka proses yang sama dilakukan pada iterasi berikutnya untuk

menentukan nilai variabel dual dan opportunity cost sel-sel kosong

dan komputasi berhenti jika semua nilai cij - ui - vj ≥ 0.

(Murthy, P R. 2007)

Untuk memperlihatkan bagaimana proses metode MODI mengevaluasi solusi

layak awal, penulis akan menggunakan kembali solusi layak awal yang ditentukan

dengan metode least-cost. Tabel berikut ini memperlihatkan solusi layak awal yang

akan dievaluasi dengan metode MODI.


52

Tabel 4.28 Solusi layak awal dengan least-cost method

Kolom tambahan pada sisi kiri tabel dengan variabel ui dan baris tambahan

pada bagian atas dengan variabel vj melambangkan nilai baris dan kolomyang harus

dihitung dalam metode MODI. Nilai tersebut dihitung untuk semua sel alokasi

dengan rumus:

ui + vj = cij.

Nilai cij adalah biaya transportasi untuk setiap sel ij. Sebagai contoh rumus

untuk sel 1B adalah:

u1 + vB = c1B,

dengan besar biaya transportasi c1B = 8, maka

u1 + vB = 8.

Dan rumus untuk sel-sel sisanya yang akan dievaluasi adalah:

x1C : u1 + vC = 10

x2C : u2 + vC = 11

x3A : u3 + vA = 4

x3B : u3+ vB = 5


53

Sekarang terdapat lima persamaan dengan 6 variabel yang nilainya tidak

diketahui. Untuk menyelesaikan persamaan ini perlu menetapkan satu dari semua

variabel persamaan berilai nol. Jika dimisalkan u1 = 0, maka semua nilai variabel ui

dan vj yang lain akan dapat diselesaikan.

x1B : u1 + vB = 8

0 + vB = 8

vB = 8

x1C : u1 + vC = 10

0 + vC = 10

vC = 10

x2C : u2 + vC = 11

u2 + 10 = 11

u2 = 1

x3B : u3 + vB = 5

u3 + 8 = 5

u3 = -3

x3A : u3+ vA = 4

-3 + vA = 4

vA = 7

Perhatikan bahwa persamaan untuk sel 3B harus diselesaikan lebih dahulu

sebelum sel 3A dapat diselesaikan. Dan semua nilai dari ui dan vj dapat

disubstitusikan ke dalam tabel seperti diperlihatkan pada tabel 4.29 berikut.


54

Tabel 4.29 Solusi awal dengan semua nilai ui dan vj

Selanjutnya, digunakan rumus berikut ini untuk mengevaluasi sel-sel kosong

yakni menentukan opportunity cost dari variabel nonbasis.

cij – ui – vj = dij

di mana dij sama dengan peningkatan biaya atau penurunan biaya yang mungkin

terjadi dengan mengalokasikan ke sebuah sel. Untuk semua sel-sel kosong dalam

Tabel 4.29, rumus tersebut menghasilkan nilai-nilai berikut.

x1A : d1A = c1A – u1 - vA = 6 - 0 - 7 = -1

x2A : d2A = c2A – u2 - vA = 7 - 1 - 7 = -1

x2B : d2B = c2B – u2 – vB = 11 - 1 - 8 = +2

x3C : d3C = c3C – u3 – vC = 12 - (-3) - 10 = +5

Dari perhitungan ini menunjukkan bahwa baik sel 1A dan sel 2A akan

menurunkan biaya $1 per alokasi unit. Perhatikan bahwa perubahan biaya dari empat

sel kosong diatas sama dengan perubahan biaya untuk empat sel kosong yang

dihitung dengan metode stepping stone iterasi pertama pada subbab sebelumnya.

Informasi yang sama yaitu nilai opportuity cost ditentukan dengan dua metode


55

yangberbeda yakni evaluasi jalur dalam metode stepping stone dan menggunakan

rumus matematika dari metode MODI.

Karena nilai opportunity cost dari sel 1A dan 2A sama maka dapat dipilih

sembarang sebagai entering nonbasic variabel untuk evaluasi iterasi selanjutnya

sampai ditemukan semua opportunity cost dari sel-sel kosong berilai negatif (dij ≥ 0).

Jika yang dipilih adalah sel 1A sebagai entering nonbasic variabel, maka harus

ditentukan kembali jalur stepping stone dari sel tersebut untuk menentukan berapa

banyak unit yang akan di realokasi. Hasil realokasi dari jalur sel 1A diperlihatkan

pada Tabel 4.30 berikut.

Tabel 4.30 Iterasi kedua menentukan solusi optimal dengan MODI

Nilai dari variabel ui dan vj pada Tabel 4.30 harus dihitung kembali

menggunakan rumus ui + vj = cij untuk sel-sel yang sudah dialokasikan.

x1A : u1 + vA = 6

0 + vA = 6

vA = 6

x1C : u1 + vC = 10

0 + v4 = 10

vC = 10


56

x2C : u2 + vC = 11

u2 + 10 = 11

u2 = 1

x3A : u3 + vA = 4

u3 + 6 = 4

u3= -2

x3B : u3 + vB = 5

-2 + vB = 5

vB = 7

Nilai baru dari ui dan vj diperlihatkan pada Tabel 4.31 berikut.

Tabel 4.31 Nilai baru ui dan vj untuk iterasi

Perubahan biaya dari sel-sel kosong pada di atas dapat dihitung dengan rumus

opportunity cost :

cij – ui – vj = dij

x1B : d1B = c1B – u1 – vB = 8 - 0 - 7 = +1


57

x2A : d2A = c2A – u2 - vA = 7 - 1 - 0 = 0

x2B : d2B = c2B – u2 – vB = 11 - 1 - 7 = +2

x3C : d3C = c3C – u3 – vC = 12 - (-2) - 10 = +4

Karena tidak ada opportunity cost yang bernilai positif, maka solusi yang

diperlihatkan pada Tabel 4.30 optimal.

Total biaya = 25(6) + 125(10) + (175(11) + 175(4) + 100(5) = 4525 (sama

dengan hasil optimal metode stepping stone).

Demikian halnya seperti dalam penyelesaian metode stepping stone, sel 2A memiliki

perubahan biaya 0 (opportunity cost 0) menunjukkan adanya solusi optimal ganda

(ada jalur alokasi optimal lain dengan total biaya yang sama).

Dari kajian yang telah dilakukan untuk dua metode uji optimalitas yaitu

stepping stone method dan modified distribution method (MODI), penulis memilih

MODI sebagai metode optimalitas yang akan diaplikasikan pada penyelesaian contoh

masalah transportasi. Hal ini karena, pada intinya MODI adalah sebuah metode

modifikasi dari stepping stone dengan proses yang lebih efesien. Solusi layak awal

dari masalah transportasi yang akan diselesaikan ditentukan dengan ketiga metode

yang telah dikaji pada subbab sebelumnya yaitu north-west corner method, least-cost

method dan vogel’s approximation method. Tujuan dari penyelesaian contoh masalah

ini adalah untuk memperlihatkan keoptimalan masing-masing metode sehingga pada

akhir tulisan ini dapat disimpulkan metode apa yang tepat dipilih menyelesaikan

persoalan transportasi serupa dalam kehidupan nyata, sesuai dengan tujuan dari

tulisan ini.


58

4.5 Aplikasi Metode Pada Contoh Kasus

Berikut ini penulis menyajikan sebuah tabel transportasi yang memuat seluruh

informasi dari sebuah contoh masalah transportasi.

Tabel 4.32 Contoh Masalah Transportasi

Tabel 4.32 di atas menggambarkan bahwa jumlah kapasitas pabrik pabrik O1,

O2, O3, dan O4 berturut-turut: 100, 90, 70, dan 90, sedangkan permintaan pasar di

lapangan D1, D2, D3, D4, dan D5 berturut-turut 80, 50, 100, 60, dan 70. Biaya satuan

dari pabrik O1 ke permintaan D1 adalah 12, biaya satuan dari pabrik O1 ke permintaan

D2 adalah 4, dan seterusnya, sampai biaya satuan dari pabrik O3 ke permintaan D5

adalah 1. Untuk menyelesaikan permasalahan transportasi ini ada beberapa metode

yang akan digunakan seperti yang sudah dikaji pada subbab sebelumnya antara lain:

Metode North-West Corner (NWC), metode Least-cost (LCM), dan metode

pendekatan Vogel (Vogel Approximation Methods) atau disingkat VAM.


59

4.5.1 Menentukan Solusi Layak Awal (Basic Feasible Solution)

5.5.1.1 Solusi Layak Awal dengan Metode North West Corner (NWC)

Untuk masalah pada Tabel 4.31 di atas, maka apabila diselesaikan dengan metode

NWC akan melakukan langkah-langkah sebagai berikut:

Penggunaan metode NWC mengharuskan sel O1D1, terletak di sudut kiri atas

tabel yang pertama sekali diisi. Alokasi diterapkan X11 = 80 unit untuk memenuhi

permintaan yang ternyata lebih kecil dari kapasitas O1. Ini berarti permintaan tujuan

D1= 80 dapat dipenuhi dari O1. Ternyata produksi O1 masih mempunyai (100 - 80) =

20 unit kapasitas yang belum disalurkan. Sisa yang 20 unit ini di alokasikan kepada

permintaan D2 yang permintaannya 50 unit. Untuk memenuhi kekurangan kebutuhan

D2, yaitu kurang 30 unit maka diambil dari D2 dengan demikian maka sel O1D2 atau

X12 = 20 dan sel O2D2 atau X22 = 30. Sisa produksi D2 setelah dikurangi 30 unit

adalah 60 unit, sisa ini dialokasikan ke sel O2D3 atau X23 secara keseluruhan.

Permintaan D3 adalah 90 unit dan telah tersedia 60 unit dari O2. Kekurangan 30 unit

permintaan diambil dari produksi O3 sehingga X23 = 70 dan X33 = 30. Sisa produksi

O3 sebanyak 40 unit yaitu (70-30) dialokasikan ke permintaan D4. Jumlah permintaan

D4 sebanyak 60 unit dilengkapi dengan mengambil 20 unit dari produksi O4. Dengan

demikian produksi O4 tersisa 70 unit dialokasikan ke permintaan D5.

Hasil alokasi dari metode north-west corner ini diperlihatkan pada Tabel 4.33

berikut.

Tabel 4.33 Matriks biaya transportasi hasil alokasi dengan metode NWC


60

Berdasarkan Tabel 4.32 di atas diperoleh hasil alokasi sebagai berikut: Sel

O1D1 atau X11 = 80, sel O1D2 atau X12 = 20, sel O2D2 atau X22 = 30, sel O2D3 atau X23

= 60, sel O3D3 atau X33 = 30, sel O3D4 atau X34 = 40, sel O4D4 atau X44 = 20, dan sel

O4D5 atau X45 = 70.

Besarnya biaya transportasi dengan metode NWC adalah:

Total biaya = 80 (12) + 20 (4) + 30 (1) + 60 (6) + 30 (4) + 40 (7) + 20 (9) +

70 (1) = 2.080

4.5.1.2 Solusi Awal dengan Metode Least-cost (LCM)

Sesuai dengan yang telah dikaji pada bagian metode LCM sebelumya, alokasi

menggunakan metode ini didasarkan pada pemilihan sel dengan biaya terendah.

Untuk persoalan transportasi berdimensi kecil, hal ini akan memberikan pengurangan

waktu. Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya

pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin

dengan mengingat persyaratan kapasitas produksi (origin) maupun permintaan

tempat tujuan. Kemudian beralih ke sel termurah berikutnya dan mengadakan alokasi

dengan memperhatikan kapasitas yang tersisa dari permintaan baris dan kolom.

Untuk permasalahan transportasi di atas langkah-langkah penyelesaian dengan

metode Least-cost adalah sebagai berikut.

Biaya sel terkecil adalah 1 yaitu pada sel O2D2, O3D1, dan O4D5. Sel-sel ini

diisi dengan memperhatikan kapasitas dan permintaan, yaitu dengan mencari nilai

minimum dari keduanya. Sel O2D2 diisi 50 unit, sehingga kapasitas O2 menjadi 40

dan permintaan D2 menjadi 0, kemudian kolom D2 diberi tanda bahwa alokasi pada

kolom tersebut telah selesai. Kemudian sel O3D1 diisi 70 unit, sehingga kapasitas O3

menjadi 0 dan permintaan D2 menjadi 10 unit, kemudian baris O3 diberi tanda juga.

Sel O4D5 diisi 70 unit, sehingga kapasitas O4 menjadi 20 dan permintaan D5 menjadi

0, kemudian kolom D5 juga diberi tanda bahwa alokasi pada kolom tersebut telah

lengkap. Hasil perhitungan di atas ini dapat dilihat pada Tabel 4.34 berikut.


61

Tabel 4.34 Hasil alokasi dengan LCM sel biaya terendah pertama

Biaya terkecil selanjutnya adalah 5 yang terletak pada sel O1D4. Sel O1D4

diisi sebesar minimum dari kapasitas O1dan permintaan D4, sehingga diisi dengan 60

unit. Dengan pengisian 60 unit pada sel O1D4 maka kapasitas O1 menjadi 40 dan

permintaan D4 menjadi 0, kemudian kolom D4 diberi tanda dan tidak diolah pada

program selanjutnya. Hasil perhitungan ini dapat dilihat pada Tabel 4.35 berikut.

Tabel 4.35 Lanjutan proses alokasi LCM biaya terendah kedua


62

Biaya terkecil selanjutnya adalah 6 yang terletak pada sel O2D3 dan sel O4D3.

Sel O2D3 diisi minimum dari sisa kapasitas O2 dan permintaan D3, sehingga diisi

dengan 40 unit. Dengan pengisian 40 unit pada sel O2D3 maka kapasitas O2 menjadi 0

dan permintaan D3 menjadi 50 unit, kemudian baris O2 diberi tanda dan tidak diolah

pada program\ selanjutnya. Sel O4D3 diisi minimum dari sisa kapasitas O4 dan sisa

permintaan D3, sehingga diisi dengan 20 unit. Dengan pengisian 20 unit pada sel

O4D3 maka kapasitas O4 menjadi 0 dan permintaan D3 menjadi 30, kemudian baris 42

ditandai dan tidak diolah pada program selanjutnya. Hasil perhitungan ini dapat kita

hihat pada Tabel 4.36 berikut.

Tabel 4.36 Lanjutan hasil alokasi dari metode LCM biaya terendah ketiga

Selanjutnya kekurangan dari permintaan D1 sebanyak 10 unit, dan

kekurangan permintaan D2 sebanyak 30 unit di alokasikan dari sisa produksi D1 yang

besarnya 40 unit. Dengan demikian maka semua permintaan maupun pemawaran

telah selesai dan diperoleh Tabel 4.37 berikut.


63

Tabel 4.37 Solusi awal dengan metode LCM

Berdasarkan Tabel 4.37 di atas diperoleh sistem hasil alokasi dari masalah

transportasi sebagai berikut:

X11 = 10, X13 = 30, X14 = 60, X22 = 50, X23 = 40, X31 = 70, X43 = 20, dan X45 = 70.

Besarnya biaya transportasi dengan metode Least-cost adalah:

Total biaya = 10 (12) + 30 (9) + 60 (5) + 50 (1) + 40 (6) + 70 (1) + 20 (6) +

70 (1) = 1240.

4.5.1.3 Solusi Awal dengan Metode VAM ( Vogel Approximation Method)

Sesuai dengan pembahasan pada subbab sebelumya bahwa metode VAM didasarkan

atas ‘beda kolom’ dan ‘beda baris’ yang menentukan perbedaan antara dua biaya

alokasi terendah dalam satu kolom atau satu baris.


64

Tabel 4.38 Tabel Masalah transportasi

Besarnya beda baris dan beda kolom adalah sebagai berikut.

Tabel 4.39 Beda baris dan beda kolom iterasi ke-1

Beda baris atau beda kolom terbesar pertama adalah 7 yaitu pada kolom D1,

biaya termurah kolom D1 adalah 1 yaitu pada sel O3D1. Oleh karena itu sel O3D1 ini

diisi terlebih dahulu, yang besarnya adalam minimum kapasitas O3 dan permintaan

D1 yaitu 70. Dengan mengisi sel O3D1 sebesar 70, maka kapasitas O3 menjadi 0 dan

permintaan D1 menjadi 10. Dengan demikian baris O3 ditandai dan tidak dimasukkan

dalam program selanjutnya.


65

Tabel 4.40 Hasil perhitungan pada kolom penalty terbesar pertama

Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut.


Beda baris atau beda kolom terbesar kedua adalah 6 yaitu pada kolom D5,

biaya terendah kolom D5 adalah 1 yaitu pada sel O4D5. Oleh karena itu sel O4D5 ini



permintaan D5 menjadi 0. Dengan demikian kolom D5 ditandai dan tidak dimasukkan



66

Tabel 4.42 Hasil perhitungan pada kolom penalty terbesar kedua



Beda baris atau beda kolom terbesar ketiga adalah 5 yaitu pada baris O2,

biaya termurah kolom O2 adalah 1 yaitu pada sel O2D2. Oleh karena itu sel O2D2 ini



permintaan D2 menjadi 0. Dengan demikian kolom D2 ditandai dan tidak dimasukkan



67

Tabel 4.44 Hasil perhitungan pada kolom penalty terbesar ketiga


Tabel 4.45. Beda baris dan beda kolom iterasi ke-4

Beda baris atau beda kolom terbesar adalah 4 yaitu pada baris O1, biaya

termurah baris O1 adalah 5 yaitu pada sel O1D4. Oleh karena itu sel O1D4 ini diisi

terlebih dahulu, yang besarnya adalam minimum sisa kapasitas O1 dan permintaan D4

yaitu 60. Dengan mengisi sel O1D4 sebesar 60, maka kapasitas O1 menjadi 40 dan

permintaan D4 menjadi 0. Dengan demikian baris O4 ditandai dan tidak dimasukkan



68

Tabel 4.46 Hasil perhitungan pada kolom penalty terbesar keempat



Beda baris atau beda kolom terbesar kelima adalah 4 yaitu pada baris O4,

biaya termurah baris O4 adalah 6 yaitu pada sel O4D3. Oleh karena itu sel O4D3 ini

diisi terlebih dahulu, yang besarnya adalam minimum sisa kapasitas O4 dan

permintaan D3 yaitu 20. Dengan mengisi sel O4D3 sebesar 20, maka kapasitas O4

menjadi 0 dan permintaan D2 menjadi 80. Dengan demikian baris O4 ditandai dan

tidak dimasukkan dalam program selanjutnya.


69

Tabel 4.48 Hasil perhitungan pada kolom penalty terbesar kelima

Kemudian kekurangan kebutuhan D3 dicukupi oleh sisa dari O1 sebanyak 40

dan sisa O2 sebanyak 30. Dengan demikian kita peroleh sistem transportasi sebagai

berikut: X13 = 40, X14 = 60, X21 = 10, X22 = 50, X23 = 30, X31 = 70, X43 = 20, dan X45 =

70. Besarnya biaya transportasi dengan metode VAM adalah :

Total biaya = 40 (9) + 60 (5) + 10 (8) + 50 (1) + 30 (6) + 70 (1) + 20

(6) + 70 (1) = 1230.

4.5.2 Uji optimalitas pada solusi awal

Dari penyelesaian ketiga metode tersebut di atas dapat dilihat bahwa metode yang

paling sederhana adalah metode NWC, tetapi hasil dari metode ini umumnya kurang

optimal yakni total biaya masih cukup besar. Sedangkan dengan metode VAM hasil

perhitungan biaya yang diperoleh rendah, tetapi perhitungannya cukup rumit. Metode

Least-cost secara perhitungan sederhana, tetapi hasilnya mendekati dengan hasil

metode VAM.

Berikut ini dilanjutkan pada uji keoptimalan solusi layak awal dengan metode

MODI. Tujuan dari uji optimalitas ini adalah fokus melihat solusi optimal yang akan

dibandingakan dengan solusi layak awal yang diperoleh dari ketiga metode pada

contoh soal yang sama. Karena pada intinya MODI adalah pengembangan dari

metode Stepping stone seperti telah diuraikan pada kajian subbab sebelumnya, maka


70

tetap akan menghasilkan solusi yang sama jika digunakan pada penyelesaian contoh

masalah transportasi ini, sehingga penulis langsung menetapkan satu metode uji saja

yaitu MODI.

4.5.2.1 Uji Optimalitas dengan Modified Distribution (MODI)

Dengan memperhatikan kembali total biaya yang dihasilkan dari masing-masing

metode solusi layak awal yaitu, metode NWC sebesar 2080 satuan biaya, metode

LCM sebesar 1240 satuan biaya dan metode VAM sebesar 1230 satuan biaya, maka

Penulis memilih satu solusi layak awal yang akan dievaluasi untuk menentukan

solusi optimal. Solusi tersebut adalah hasil dari metode Least-cost karena besar biaya

yang dihasilkan berada diantara ketiga metode.

Tabel 4.49 Solusi layak awal dengan Least-cost method (LCM)

Berdasarkan tabel 4.49 di atas, kolom tambahan pada sisi paling kanan tabel

dengan variabel vi dan baris tambahan pada bagian sisi paling bawah tabel dengan

variabel uj melambangkan nilai kolom dan baris yang harus dihitung dalam metode

MODI. Nilai tersebut dihitung untuk semua sel alokasi dengan rumus:

vi + uj = cij.

Dari Tabel 4.48 di atas diperlihatkan bahwa jumlah baris m = 4 dan jumlah

kolom n =5 maka jumlah sel variabel basis dinyatakan layak sebagai solusi awal jika

sel alokasi memenuhi syarat umum m+n -1= 4+5-1= 8. Solusi awal pada tabel 4.48

memperlihatkan alokasi yang sesuai yaitu sebanyak 8 sel variabel basis. Sehingga


71

dapat dilanjutkan untuk dievaluasi dengan metode MODI yaitu mengevaluasi seluruh

sel kosong dengan rumus yang sudah ditetapkan. Banyak sel kosong yang akan

dievaluasi adalah sebanyak (m x n) – (m +n -1) = (4 x 5) - (4 + 5 - 1) = 12 sel. Maka,

rumus untuk sel-sel kosong pada tabel 4.48 di atas adalah sebagai berikut.

xO1D2 : vO1 + uD2 = 4

xO1D5 : vO1 + uD5 = 9

xO2D1 : vO2 + uD1 = 8

xO2D4 : vO2+ uD4 = 6

xO2D5 : vO2 + uD5 = 7

xO3D2 : vO3 + uD2 = 12

xO3D3 : vO3 + uD3 = 7

xO3D4 : vO3+ uD4 = 7

xO3D5 : vO3 + uD5 = 7

xO4D1 : vO4 + uD1 = 10

xO4D2 : vO4 + uD2 = 15

xO4D4 : vO4+ uD4 = 9

Dengan memilih vO1 = 0, maka diperoleh hasil berikut.

xO1D2 : vO1 + uD2 = 4

0 + uD2 = 4

uD2 = 4

dan dengan cara yang sama diperoleh nilai semua vi dan uj sebagai berikut. uD1 = 12,

uD3 = 9, uD4 = 5. Dari u D1= 12, diperoleh vO1 = -11, dari uD3 = 9, diperoleh vO2 = -3,


72

dan vO4 = -3, dari vO2 = -3, diperoleh uD2 = 4, dan dari vO4 = -3, diperoleh uD5 = 4.

Seperti diperlihatkan pada tabel 4.50 berikut.

Tabel 4.50 Nilai vi dan uj dalam tabel solusi awal

Selanjutnya menentuka nilai opportunity cost dengan menghitung perubahan

biaya dij setiap sel kosong dengan rumus:

dij = cij – (vi + uj)

dO1D2 = cO1D2 – (vO1+ uD2)

dO1D2 = 4 – (0 + 4) = 0

Dengan cara yang sama diperoleh nilai opportunity cost dari semua sel kosong pada

Tabel 4.50 berikut.

Tabel 4.51 Nilai opportunity cost dari hasil evaluasi sel-sel kosong

Dari Tabel 4.51 di atas, terlihat bahwa opportunity cost terbesar adalah pada

sel O2D1 yaitu +1 sehingga sel ini harus diisi sebanyak mungkin. Sel ini diisi


73

sebanyak minimun dari sel O1D1 dan O2D2 yaitu sebanyak 10. Sehingga Tabel 4.50

menjadi Tabel 4.52 berikut.

Tabel 4.52 Hasil realokasi solusi dengan metode MODI iterasi ke-1

Untuk memutuskan apakah solusi dari hasil evaluasi iterasi ke-1 sudah

optimal atau tidak dilakukan evaluasi kembali pada setiap sel kosong untuk melihat

nilai opportunity cost dengan metode MODI. Dengan cara yang sama diperoleh nilai

opportunity cost dari sel-sel kosong pada Tabel 4.53 berikut.

Tabel 4.53 Nilai opportunity cost sel-sel kosong metode MODI iterasi ke-2

No. Sel kosong Opportunity cost

1 O1D1 -1

2 O1D2 0

3 O1D5 -5

4 O2D4 -3

5 O2D5 -6

6 O3D2 -18

7 O3D3 -5

8 O3D4 -12

9 O3D5 -13

10 O4D1 -2

11 O4D2 -14

12 O4D4 -7


74

Dari Tabel 4.53 terlihat bahwa tidak ada lagi sel kosong yang mempunyai

opportunity cost positif, ini berarti bahwa solusi pada Tabel 4.50 telah optimal,

dengan biaya transportasi sebesar:

Total biaya =40 (9) + 60 (5) + 10 (8) + 50 (1) + 30 (6) + 70 (1) + 20

(6) + 70(1) = 1.230.

Sebagai catatan bahwa opportunity cost sel O1D2 adalah nol, ini berarti bahwa sel ini

diisi maupun tidak, tidak akan menambah atau mengurangi biaya transportasi.

Dari evaluasi sel-sel kosong dengan metode uji optimal MODI diperoleh total

biaya alokasi optimal sebesar 1230 satuan biaya utuk mengalokasikan seluruh supply

yang tersedia memenuhi seluruh demand. Jika dibandingkan total biaya optimal

dengan biaya alokasi solusi layak awal dari ketiga metode yang sudah dikalkulasi

sebelumnya, dapat dilihat perbedaan selisih biaya alokasi yang paling mendekati

solusi optimal. Besar solusi awal metode NWC sebesar 2080 satuan biaya, metode

LCM sebesar 1240 satuan biaya dan metode VAM sebesar 1230 satuan biaya.

Selisih biaya terbesar terjadi antara metode NWC dan MODI sebesar 850, sementara

selisih biaya yang paling kecil atau bahkan besar solusi awal sama dengan besar

biaya optimal adalah antara VAM dan MODI yaitu 1230 dengan selisih biaya 0, dan

yang berada diantara keduanya adalah metode LCM dengan selisih biaya 10.

Perbedaan selisih biaya antara solusi layak awal dan solusi optimal

menunjukkan seberapa optimal suatu metode solusi awal tersebut jika dilihat dari

besar biaya yang dihasilkan. Hal ini dapat menjadi pertimbangan dalam memilih

suatu metode menyelesaikan sebuah kasus transportasi. Namun, pemilihan metode

juga perlu memperhatikan bagaimana efesiensi setiap metode menyelesaikan

permasalahan transportasi. Efesiensi tersebut mencakup banyaknya iterasi

perhitungan, waktu yang dibutuhkan, proses alokasi variabel basis dan juga

disesuaikan dengan tingkat kesulitan dari masalah transportasi yang akan

diselesaikan. Tidak hanya memperhatikan hasil akhir yang diperoleh, karena solusi

layak awal tetap akan dievaluasi sebelum dinyatakan sebagai solusi optimal.

Hasil dari penyelesaian contoh kasus transportasi di atas akan Penulis

perlhatkan dalam Tabel 4.54 berikut.


75

Tabel 4.54 Hasil Penyelesaian contoh Kasus Transportasi subbab 4.5

No Metode

Solusi

Awal

Total Biaya

yang Diperoleh

(satuan biaya)

Banyak

iterasi

perhitungan

Total Biaya

Optimal dengan

MODI (satuan

biaya)

Selisih terhadap

Solusi optimal

(satuan biaya)

1 NWCM 2080 - 1230 850

2 LCM 1240 3 1230 20

3 VAM 1230 5 1230 0

Berdasarkan Tabel 4.54 dapat diketahui bahwa solusi layak awal yang paling

optimal diperoleh dengan metode VAM, yaitu dilihat dari selisih biaya antara solusi

layak awal dan solusi optimal yang dihasilkan paling rendah yaitu 0 satuan biaya.

4.5.3 Penyelesaian Masalah Transportasi dengan Software

4.5.3.1 Program Lindo

Program Lindo merupakan sebuah software yang biasa digunakan untuk

menyelesaikan masalah program linier. Masalah transportasi sebagai bentuk khusus

dari program linier juga dapat diselesaikan dengan Lindo. Berikut ini akan dibahas

masalah transportasi yang sama dengan contoh kasus pada subbab 4.5 menggunakan

Program Lindo.

Tabel 4.55 Tabel masalah Transportasi dengan Lindo

Misalkan banyaknya barang pada sel Xij yaitu banyaknya barang yang dikirim

dari pabrik Oi ke permintaan Dj, dan cij adalah biaya satuan pengiriman dari pabrik Oi

ke permintaan Dj, maka besarnya biaya pengiriman adalah:


76

Dari ketentuan ini, untuk kasus masalah transportasi ini, maka kita peroleh model.

Minimumkan biaya:

Z= 12X11 + 4X12 +9 X13 + 5X14 + 9X15 + 8X21 + 1X22 + 6X23 + 6X24 +

7X25 + 1X31 + 12X32 + 4X33 + 7X34 + 7X35 + 10X41 + 15 X42 + 6X43 +

9X44 + 1X45

Dengan kendala:

X11 + X21 + X31 + X41 = 80

X12 + X22 + X32 + X42 = 50

X13 + X23 + X33 + X43 = 90

X14 + X24 + X34 + X44 = 60

X15 + X25 + X35 + X45 = 70

X11 + X12 + X13 + X14 + X15 = 100

X21 + X22 + X23 + X24 + X25 = 90

X31 + X32 + X33 + X34 + X35 = 70

X41 + X42 + X43 + X44 + X45 = 90

Dengan Xij ≥ 0, untuk setiap i dan j.

Dalam menyelesaikan program linear maupun masalah transportasi, indeks

ditulis sejajar dengan variabelnya sehingga dalam penulisan pada Lindo sebagai

berikut.

Setelah program Lindo dijalankan, maka akan diperoleh hasil sebagai berikut.


77


78

Tampilan yang muncul pada layar editor di atas merupakan penyelesaian

suatu masalah transportasi yang dapat diartikan sebagai berikut.

1. Biaya minimum yang diperlukan untuk pengangkutan barang adalah 1.230

yang dapat dibaca dari


79

2. Alokasi pengiriman barang dapat diketahui dari nilai value pada hasil berikut.

a. Dari O1 (tempat asal) dikirimkan ke D2 (tempat tujuan) sebanyak 40 unit, dan

ke D4 sebanyak 60 unit.

b. Dari O2 dikirimkan ke D1 sebanyak 10 unit, ke D2 sebanyak 10 dan dikirim ke

D3 sebanyak 70

c. Dari O 3 dikirimkan sebanyak 70 unit ke D1.

d. Dari O 4 dikirimkan sebanyak 20 unit ke D3, dan 80 unit ke D5

Reduced Cost adalah lawan dari opportunity cost, jadi apabila Reduced Cost = 4,

maka opportunity cost nya = -4. Dengan demikian dari hasil di atas, tidak ada

opportunity cost yang positif, jadi program optimal.

Pada masalah transportasi keadaan pasar seimbang artinya jumlah permintaan

akan barang sama dengan jumlah kapasitas produksi, maka dual price tidak memiliki


80

makna khusus. Selanjutnya hasil berikut menunjukkan perubahan yang dibolehkan

agar sistem transportasi tetap, dengan biaya optimal.

Misalnya c11 dapat turun sampai 11 atau naik sampai tak berhingga, c12 dapat turun

sampai 0 dan tidak boleh naik, dan seterusnya.

Hasil terakhir yaitu:

Menunjukkan bahwa jumlah produksi maupun jumlah permintaan adalah tetap

karena memang keadaan pasar seimbang.


81

4.5.3.2 Program Lingo

Lingo adalah salah satu program (software) dibawah Winston satu set bersama-sama

dengan Lindo. Program Lingo lebih luas cakupannya, namun output (hasil keluaran)

nya tidak selengkap program Lindo. Pada program Lingo, dapat mengolah data atau

rumusan non-linear, seperti membuat grafik fungsi sinus, fungsi logarirmis, fungsi

eksponen, dan lain-lain.

Bentuk pemrograman Lingo juga lebih rumit sedikit, tetapi akan lebih efisien

apabila digunakan untuk menyelesaikan masalah transportasi dengan banyak

variabel. Karena pada program Lingo disediakan perintah (command) looping

dengan perintah for ... loop. Sebagai contoh masalah transportasi yang sudak dibahas

di atas akan dikerjakan dengan program Lingo.

Tabel 4.56 Tabel masalah Transportasi dengan Lingo

Dengan program Lingo, maka perintah untuk menyelesaikan masalah

transportasi ini adalah.


82

Dari program di atas menunjukkan bahwa, program Lingo ini sangat baik

untuk masalah transportasi khususnya untuk banyak variable, karena dengan Lingo

tidak perlu mendefinisikan nama variable. Perhatikan bahwa bentuk program Lingo

untuk menyelesaikan masalah transportasi ini bentuk program sudah baku dan tidak

perlu mengganti variabel/ menambah variabel. Perubahan program hanya mengubah

banyaknya Kapasitas, Permintaan, dan perubahan pada data saja.

Setelah program dijalankan, maka akan diperoleh hasil sebagai berikut.


83

Dari hasil program Lingo diperoleh biaya minimum yang diperlukan untuk

pengangkutan barang adalah 1.230 pada iterasi ke-15.

Sedangkan menggunakan program Lindo dengan besar biaya minimum sama 1.230

pada iterasi ke-8

Dari penyelesaian masalah transportasi menggunakan software LINDO dan

LINGO diperoleh biaya minimum yang sama dengan penyelesaian secara analitik

menggunakan metode transportasi solusi optimum MODI. Jadi dapat disimpulkan

bahwa penyelesaian antara proses manual dan menggunakan software menghasilkan

biaya optimum yang sama. Software LINDO dan LINGO dapat digunakan untuk

menyelesaikan kasus transportasi dengan jumlah variabel yang relatif besar dalam

waktu yang lebih singkat.


BAB 5

KESIMPULAN DAN SARAN

5.1 Kesimpulan

Berdasarkan analisis yang telah Penulis lakukan tentang beberapa metode

transportasi dalam optimalisasi biaya distribusi suatu produk yang telah diuraikan

dalam bab pembahasan, maka dapat disimpulkan sebagai berikut.

1. Sebuah masalah transportasi diselesaikan menggunakan sebuah metode

khusus yang disebut metode transportasi. Ada dua tahap penyelesaian yang

harus dilakukan yaitu menentukan solusi layak awal (basic feasible solution)

dan solusi optimal (optimal solution). Solusi layak awal adalah solusi dasar

yang harus ditentukan dengan memenuhi seluruh ketentuan kendala dan

fungsi tujuan, sementara solusi optimal adalah solusi akhir yang telah

dinyatakan optimal melalui uji optimalitas. Untuk memperoleh solusi optimal

terlebih dahulu ditentukan solusi layak awal dengan menggunakan beberapa

metode yaitu North-west corner method (NWCM), Least-cost method (LCM)

dan Vogel’s Approximation method (VAM). Solusi layak awal yang diperoleh

dari salah satu metode solusi awal akan dievalusi menggunakan metode uji

optimalitas yaitu metode Stepping stone method (SSM) dan Modified

distribution (MODI) dan diperoleh solusi optimal.

2. Dari ketiga metode yang telah dikaji dapat dilihat bahwa metode yang paling

sederhana adalah metode NWC, karena proses alokasinya singkat tanpa

adanya iterasi perhitungan, tetapi hasil dari metode ini umumnya kurang

memuaskan karena biaya alokasi yang diperoleh cukup besar, hal ini

diakibatkan proses alokasi yang tidak mempertimbangkan biaya alokasi tiap

produk. Sedangkan dengan metode VAM, alokasi yang dilakukan

menghasilkan total biaya paling rendah, hal ini terjadi karena pemilihan sel

alokasi didasarkan pada nilai penalty cost yang meminimumkan

pengalokasian pada sel berbiaya tinggi, tetapi perhitungannya cukup rumit


85

karena memerlukan beberapa iterasi sampai diperoleh solusi layak awal.

Sementara metode LCM, secara perhitungan masih kategori sederhana karena

alokasi didasarkan pada biaya sel terendah, kemudian besar total biaya

alokasi dari solusi awal yang diperoleh umumnya berada diantara metode

NCM dan VAM.

3. Dari hasil uji optimalitas dengan metode MODI pada solusi awal yang

diperoleh dari pengaplikasian ketiga metode yakni NWC, LCM dan VAM

pada contoh masalah tranasportasi dalam tulisan ini, selisih terbesar antara

solusi awal dan solusi optimal dihasilkan oleh metode NWC, selisih terendah

adalah metode VAM, sementara metode LCM umumya memiliki selisih

biaya diantara keduanya atau ada kalanya sama dengan VAM.

4. Jadi, setiap metode memilki karakteristik tersendiri baik kelemahan dan

kelebihan. Dari hasil analisis masing-masing metode, Penulis menyimpulkan

bahwa pemilihan metode optimal harus disesuaikan dengan kondisi masalah

tranasportasi yang akan diselesaikan, maksudnya adalah tergantung

banyaknya variabel permasalahan mencakup jumlah source (banyaknya

tempat produksi) , dan jumlah destination (tujuan alokasi) serta waktu yang

disediakan untuk menyelesaikan. Bilamana diberi waktu yang cukup, maka

akan digunakan metode VAM, namun jika ingin waktu lebih singkat dengan

metode LCM sudah cukup optimal. Berapapun nilai solusi awal yang

diperoleh masih harus dilakukan uji optimal untuk menentukan solusi optimal

dari sebuah masalah transportasi. Tujuan utama memiliki metode optimal

dalam meneyelesaikan sebuah masalah transportasi agar banyak iterasi uji

optimal yang diperlukan seminimal mungkin.

5.2 SARAN

Dalam penelitian ini penulis menggunakan sumber materi dari jurnal-jurnal ilmiah

dan beberapa buku yang mana semua kasus transportasi yang dibahas dan

diselesaikan tergolong sederhana. Hal ini dikarenakan penulis fokus pada

pembahasan materi dibanding aplikasi langsung atau studi kasus serta penyelesaian

dilakukan contoh kasus dilakukan secara manual sehingga jika menggunakan kasus


86

yang kompleks membutuhkan banyak waktu. Oleh karena itu saran yang dapat

penulis berikan adalah jika peneliti selanjutnya ingin mengkaji topik yang sama

dapat menggunakan kasus yang diambil langsung dari sumber lapangan dengan skala

permasalahan yang lebih besar dan dapat menggunakan bantuan software yang

sesuai. Pada tulisan ini penulis tidak menyertakan penyelesaian dengan batuan

software karena keterbatasan pengetahuan penulis tentang program yang

bersangkutan. Semoga peneliti selanjutnya dapat menyempurnakan kekurangan dari

tulisan ini.


DAFTAR PUSTAKA

Agustini, Dwi Hayu dan Rahmadi, Endra. 2004. Riset Operasional Konsep konsep Dasar.

Cetakan Pertama. Jakarta: PT. Rineka

Akpan, Stephen dkk. 2015. A Modified Vogel Approximation Method for Solving Balanced

Transportation Problems. Department of Computer Science, University of Calabar,

Cross-River State, Nigeria. © Global Society of Scientific Research and Researchers.

http://asrjetsjournal.org/.

(diakses : 15 Februari 2018)

Ary, M dan Syarifuddin, D. 2011. ISSIT. Comparison the transportation problem solution

between north-west corner method and stepping stone method with basic approach.

Universitas BSI Bandung

Fitriatien, Sri Rahmawati. 2016. Metode Transportasi Sebagai Solusi Alternatif Dalam

Pengambilan Keputusan Pada Operasional Riset. Universitas PGRI Adi Buana

Surabaya. https://osf.io/fdg96/.

(diakses: 13 Februari 2018)

Gupta, PK dan Hira, DS. 2007. Operations Research Theory And Aplication. India: S.chand

& Company Ltd

Hernawati, Tri dan Laili, Isnaniah. 2015. Pendistribusian Produk Dengan Vogel‘S

Approximation Method (Vam) Dan Modified Distribution Method (Modi). Universitas

Islam Medan Area. https://osf.io/kc42n/.

(diakses : 13 Februari 2018)

Hyalel, Abdallah A dan Alia A, Mohammad. 2012. Solving Transportation Problems Using

The Best Candidates Method. Al-Zaytoonah Universty of Jordan. http://computer

Science & Engineering: An International Journal (CSEIJ), Vol.2, No.5, October 2012.


Mulyono, Sri. 2004. Riset Operasi. Edisi Revisi. Jakarta: Lembaga Penerbitan Fakultas

Ekonomi UI

Murthy, P R. 2007. Operation Reasearh 2nd edition. New age interational Ltd. New Delhi

Sentosa, Dika Herli. 2014. Management Biaya Distribusi. Binus University.


http://asrjetsjournal.org/

https://osf.io/fdg96/

https://osf.io/kc42n/

87

Sharma, Gaurav dkk. 2012. Solving Transportation Problem With The Various Method Of

Linear Programming Problem. Institute Of Technology And Management, Bhopal

(M.P). http://www.innovativejournal.in/index.php/ajcem. (diakses : 15 Februari 2018)

Supranto, Johannes. 1988. Riset Operasi Untuk Pengambilan Keputusan. Cetakan Pertama.

Jakarta: UI Press

Taha, HA. 1999. Introduction to operations research. PHI limited. New Delhi

Vivek Joshi, Rekha. 2013. Optimization Techniques for Transportation Problems of Three

Variables. Department of Mathematics, Sydenham College of Commerce and

Economics, Mumbai University, India. IOSR Journal of Mathematics (IOSR-JM) e-

ISSN: 2278-5728, p-ISSN:2319-765X. Volume 9, Issue 1 (Nov. – Dec. 2013), PP 46-

50 www.iosrjournals.org.


Winston, WL. 2004. Operation Research application algorithms. Brooks/ Cole Thomson.

Canada

Zulfikarizah, Fien. 2014. Operation Research. Edisi Ketiga. Malang: Bayumedia Publishing


http://www.innovativejournal.in/index.php/ajcem

http://www.iosrjournals.org/

analisis beberapa metode transportasi dalam …

Documents