operation research - transportation...

Metode Kuantitatif Manajemen, Kelompok 5, MB IPB E49, 2014

0

OPERATION RESEARCH -

TRANSPORTATION MODELS

Presented by Group 5 E49


SOAL-JAWAB PEMODELAN TRANSPORTASI DENGAN

STUDI KASUS DISTRIBUSI KOMODITI GANDUM, BARLEY

DAN OAT DI NEGARA EROPA MENGGUNAKAN METODE

NORTH-WEST CORNER DAN MODIFIED DISTRIBUTION

TUGAS MATA KULIAH METODE KUANTITATIF MANAJEMEN

DOSEN : Prof. Dr. Ir. BONAR M. SINAGA, MA

DISUSUN OLEH :

[KELOMPOK 5 – E49]

A.M. HERI SAKTIYANTO P056132632.49E

FEBRIANTO ARIF WIBOWO P056132742.49E

FITRIANA PURNAMASARI P056132762.49E

HARYA BUNTALA KOOSTANTO P056132772.49E

HUSNUL INSAN P056132782.49E

SAFITRI LARASATI P056132922.49E

YOGI SYAMRIADI P056132972.49E

PROGRAM PASCASARJANA MANAJEMEN DAN BISNIS

INSTITUT PERTANIAN BOGOR

JANUARI 2014


MODEL TRANSPORTASI

Model Transportasi merupakan perluasan dari persoalan Linear Programming yaitu suatu

model jaringan yang mengatur distribusi produk secara optimal dan digunakan untuk

penentuan rencana biaya minimum (minimum cost) untuk transportasi (pengangkutan)

single commodity dari sejumlah lokasi sumber (sources) seperti pabrik, lokasi

penambangan, pelabuhan, dan sebagainya ke sejumlah lokasi tujuan (destinations) seperti

gudang, pusat distribusi, wilayah pemasaran, dan sebagainya.

Model Transportasi dapat juga digunakan untuk persoalan inventory controll, employment

schedulling, personal assignment, dan sebagainya.

Agar suatu masalah transportasi dapat dibuat model transportasi dan tabel transportasinya,

maka masalah transportasi tersebut harus memiliki data mengenai tingkat supply atau

kapasitas setiap lokasi sumber, tingkat demand setiap lokasi tujuan, dan biaya transportasi

per unit komoditas dari setiap lokasi sumber ke lokasi tujuan.

Karena hanya terdiri dari satu komoditi (single commodity), maka suatu lokasi tujuan

dapat memenuhi permintaannya dari satu lokasi sumber. Tujuan dari model transportasi

adalah menentukan jumlah yang dapat dikirim dari setiap lokasi sumber ke setiap lokasi

tujuan yang memberikan total biaya transportasi minimum.

TIPE-TIPE MODEL TRANSPORTASI

Terdapat 3 tipe kasus model transportasi dimana untuk menyelesaikan pemodelan

tersebut, diperlukan adanya tambahan variabel dummy sebagai berikut :

Jumlah Supply (Qs) = Jumlah Demand (Qd)

Bila :

m

i

ia1

=

n

j

jb1

Maka buatlah tabel/matriks model transportasi dengan mencantumkan beberapa data

berikut :

- Daerah asal & kapasitas produksi/supply masing-masing daerah

- Daerah tujuan & kapasitas daya serap/demand masing-masing daerah

- Biaya transportasi per unit untuk masing-masing rute

MATERI PENGANTAR


Ke

Dari M1 M2 M3

SUPPLY

(ai)

P1 6

X11

8

X12

10

X13 150

P2 7

X21

11

X22

11

X23 175

P3 4

X31

5

X32

12

X33 275

DEMAND

(bj) 200 100 300

ai = bj

600 = 600

Jumlah Supply (Qs) > Jumlah Demand (Qd)

Bila :

m

i

ia1

n

j

jb1


berikut :

- Ciptakan variable dummy daerah tujuan, sebagai interpretasi untuk jumlah supply yg

tidak ditransportasikan pada masing-masing daerah asal.

- Biaya transportasi per unit menuju rute dummy ini diganti dengan biaya penyimpanan

pada masing-masing daerah asal (≥ 0)

Ke

Dari M1 M2 M3

SUPPLY

(ai)

P1 6

X11

8

X12

10

X13 200

P2 7

X21

11

X22

11

X23 175

P3 4

X31

5

X32

12

X33 275

DEMAND

(bj) 200 100 300

ai > bj

650 > 600


Ke

Dari M1 M2 M3 DUMMY

SUPPLY

(ai)

P1 6

X11

8

X12

10

X13

C14

X14 200

P2 7

X21

11

X22

11

X23

C24

X24 175

P3 4

X31

5

X32

12

X33

C34

X34 275

DEMAND

(bj) 200 100 300 50

ai = bj

650 = 650

Jumlah Supply (Qs) < Jumlah Demand (Qd)

Bila :

m

i

ia1

<

n

j

jb1


berikut :

- Ciptakan variable dummy daerah asal, sebagai interpretasi untuk jumlah demand yg

tidak dapat dipenuhi pada masing-masing daerah tujuan.

- Biaya transportasi per unit dari rute dummy ini diganti dengan biaya pinalti/denda

akibat tidak dipenuhinya demand pada masing-masing daerah tujuan (≥ 0)

Ke

Dari M1 M2 M3

SUPPLY

(ai)

P1 6

X11

8

X12

10

X13 150

P2 7

X21

11

X22

11

X23 175

P3 4

X31

5

X32

12

X33 275

DEMAND

(bj) 200 180 300

ai < bj

600 > 680


Ke

Dari M1 M2 M3

SUPPLY

(ai)

P1 6

X11

8

X12

10

X13 150

P2 7

X21

11

X22

11

X23 175

P3 4

X31

5

X32

12

X33 275

DUMMY C41

X41

C42

X42

C43

X43 80

DEMAND

(bj) 200 180 300

ai = bj

680 = 680

SOLUSI MODEL TRANSPORTASI

Terdapat 3 metode penentuan solusi awal yang layak (Initial Basic Feasible Solution)

untuk model transportasi yang sudah berada dalam kondisi seimbang, dimana jumlah supply

sama dengan jumlah demand, yaitu :

1. North-West Corner Method

2. Minimum Cell Cost Method

3. Vogel’s Aproximation Method

CEK OPTIMALITAS

Solusi yang di dapat dari ketiga metode di atas merupakan solusi yang layak tapi belum

tentu merupakan solusi yang optimal. Untuk menentukan solusi optimal pada pemodelan

transportasi, maka perlu dilakukan perhitungan lebih lanjut melalui cek optimalitas.

Syarat

Jumlah sel yang terisi = (m + n) – 1

Dimana

m = Jumlah baris tabel transportasi

n = Jumlah kolom tabel transportasi


Cek optimalitas dapat dilakukan dengan 2 metode berikut :

1. Stepping-Stone Solution Method

2. Modified Distribution Method (MODI)

Pada makalah kali ini, metode yg akan digunakan adalah North-West Corner Method

dengan penyempurnaan tahap demi tahap untuk memperoleh solusi optimal menggunakan

metode MODI (Modified Distribution).

METODE NORTH-WEST CORNER

Metode North-West Corner menggunakan algoritma sebagai berikut :

(1) Pengisian sel dimulai dari sudut kiri atas tabel (X11)

(2) Tentukan nilai paling minimum antara a1 & b1 pada X11, kemudian isi sebagai nilai X11

(3) Lakukan pengecekan jumlah supply & demand untuk X11, jika jumlah supply belum

terpenuhi sesuai jumlah maksimal maka pengisian sel berlanjut ke sel sebaris berikutnya

(X12), namun jika jumlah demand yg belum terpenuhi maka pengisian sel berlanjut ke

sel sekolom berikutnya (X21).

(4) Ulangi langkah (2) dan (3) hingga seluruh jumlah supply dan demand terpenuhi dengan

kondisi seimbang (ai = bj).

Contoh

PABRIK DISTRIBUTOR

SUPPLY (ai) DENVER MIAMI

Los Angeles 40

100

50

100

Detroit 100

75

70

75 150

New Orleans 60

80

50

50

DEMAND (bj) 175 125 300

Total Biaya = 100(40) + 75(100) + 75(70) + 50(80)

= 4000 + 7500 + 5250 + 4000

= 20750


METODE MODIFIED DISTRIBUTION (MODI)

Metode MODI (Modified Distribution) adalah metode untuk mendapatkan solusi

optimal masalah transportasi (total biaya transportasi minimum). Metode ini bersifat eksak

dan juga disebut sebagai metode multiplier, karena dalam penghitungannya menggunakan

multiplier, yaitu multiplier baris (ui) dan multiplier kolom (vj).

Metode MODI menggunakan algoritma sebagai berikut :

(1) Menentukan ui dan vj dengan memperhatikan basic variable, yaitu sel (kotak) yang ada

isinya dan menggunakan rumus Ui + Vj = Cij

(2) Menentukan indeks perbaikan, yaitu dengan memperhatikan sel (kotak) yang kosong

dan dengan menggunakan rumus Indeks Perbaikan (Kij) = Cij – Ui – Vj

(3) Isilah sel kosong yang mempunyai Indeks Perbaikan negatif yang dimulai dari sel

kosong dengan indeks perbaikan negatif terbesar

(4) Ulangi langkah (1) s/d (3), jika Indeks Perbaikan telah positif semua berarti solusi

optimal telah tercapai dan tidak ada sel kosong yang harus diisi.

Contoh

PABRIK DISTRIBUTOR


Los Angeles 40

100

50

100

Detroit 100

75

70

75 150

New Orleans 60

80

50

50

DEMAND (bj) 175 125 300

Langkah-Langkah Penyelesaian

(1) Hitung nilai setiap Ui dan Vj dengan memisalkan U1 = 0

Dari sel yang terisi diperoleh persamaan dan nilai Ui, Vj sebagai berikut :

Ui + Vj = Cij

C11 = U1 + V1 = 40 U1 = 0 V1 = 40

C21 = U2 + V1 = 100 V1 = 40 U2 = 60

C22 = U2 + V2 = 70 U2 = 60 V2 = 10

C32 = U3 + V2 = 80 V2 = 10 U3 = 70


Dari sel yang kosong diperoleh persamaan dan nilai Ui, Vj sebagai berikut :

Indeks Perbaikan (Kij) = Cij – Ui – Vj

K12 = C12 – U1 – V2 = 50 – 0 – 10 = 40

K31 = C31 – U3 – V1 = 60 – 70 – 40 = -50

(2) Pilih sel kosong dengan indeks perbaikan yang bernilai negatif

Titik tolak perubahan adalah segi empat yang indeksnya :

Bertanda negatif

Angkanya terbesar

Maka yg dipilih adalah sel K31 :

K12 = C12 – U1 – V2 = 50 – 0 – 10 = 40

K31 = C31 – U3 – V1 = 60 – 70 – 40 = -50

(3) Berikan penanda positif/negatif

- Tanda positif (+) pada sel terpilih (X31)

- Tanda negatif (-) pada sel Xij terdekat yang mempunyai isi dan sebaris (X32)

- Tanda negatif (-) pada sel Xij terdekat yang mempunyai isi dan sekolom (X21)

- Tanda positif (+) pada sel Xij terdekat yang mempunyai isi dengan posisi sebaris atau

sekolom dengan 2 Xij yang bertanda negatif sebelumnya (X22)

PABRIK DISTRIBUTOR

SUPPLY (ai) Ui DENVER MIAMI

Los Angeles 40

100

50

100 U1 = 0

Detroit

100

75

(-)

70

75

(+)

150 U2 = 60

New Orleans

60

(+)

80

50

(-)

50 U3 = 70

DEMAND (bj) 175 125 300

Vj V1 = 40 V2 = 10

(4) Pindahkanlah alokasi dari yang bertanda negatif ke yang bertanda positif

(berlawanan dengan arah jarum jam) sebanyak isi terkecil dari yang bertanda

negatif


Yang bertanda negatif memiliki isi 75 (X21) & 50 (X32), maka pilihlah 50 (X32).

PABRIK DISTRIBUTOR


Los Angeles 40

100

50

100

Detroit

100

75 25

(-)

70

75 125

(+)

150

New Orleans

60

50

(+)

80

50

(-)

50

DEMAND (bj) 175 125 300

(5) Ulangi langkah (1), (2), (3) dan (4) hingga pada langkah (2) sudah tidak didapat

lagi indeks perbaikan bernilai negatif

PABRIK DISTRIBUTOR

SUPPLY (ai) Ui DENVER MIAMI

Los Angeles 40

100

50

100 U1 = 0

Detroit 100

25

70

125 150 U2 = 60

New Orleans 60

50

80

50 U3 = 20

DEMAND (bj) 175 125 300

Vj V1 = 40 V2 = 10


C11 = U1 + V1 = 40 U1 = 0 V1 = 40

C21 = U2 + V1 = 100 V1 = 40 U2 = 60

C22 = U2 + V2 = 70 U2 = 60 V2 = 10

C31 = U3 + V1 = 60 V1 = 40 U3 = 20


K12 = C12 – U1 – V2 = 50 – 0 – 10 = 40

K32 = C32 – U3 – V2 = 80 – 20 – 10 = 50

Karena harga Kij sudah tidak ada yang negatif, maka distrusi tersebut sudah optimal.


Maka persamaan linear fungsi tujuan & kendalanya menjadi sebagai berikut :

Fungsi Tujuan

Minimum Z = (C11) X11 + (C21) X21 + (C22) X22 + (C31) X31

Minimum Z = 40X11 + 100X21 + 70X22 + 60X31

Minimum Z = 40 (100) + 100 (25) + 70 (125) + 60 (50)

Minimum Z = 4000 + 2500 + 8750 + 3000

Minimum Z = 18250

Fungsi Kendala Pabrik

(1) X11 + X12 ≤ 100

(2) X21 + X22 ≤ 150

(3) X31 + X32 ≤ 50

Fungsi Kendala Gudang

(1) X11 + X21 ≤ 175

(2) X12 + X22 ≤ 125

Kendala Non-Negatif

X11, X12, X21, X22, X31, X32 ≥ 0


SOAL

Andaikan Inggris, Prancis dan Spanyol memproduksi semua kebutuhan dunia akan gandum,

barley dan oat. Dibutuhkan lahan pertanian 50 juta hektar untuk memproduksi gandum guna

memenuhi permintaan dunia. Sedangkan untuk memproduksi barley dibutuhkan lahan seluas

110 juta hektar, dan untuk memproduksi oat dibutuhkan lahan seluas 40 juta hektar. Luas

lahan pertanian yang dapat digunakan untuk memproduksi ketiga jenis tanaman pangan

tersebut di Inggris, Prancis dan Spanyol berturut-turut 90 juta hektar, 60 juta hektar dan 50

juta hektar.

Jumlah jam kerja untuk mengerjakan 1 hektar lahan gandum di Inggris, Prancis dan Spanyol

berturut-turut adalah 4, 3 dan 5. Sedang untuk mengerjakan 1 hektar lahan barley dibutuhkan

1, 5 dan 2. Dan untuk mengerjakan 1 hektar lahan oat dibutuhkan 2, 5 dan 4 jam kerja

(berturut-turut di Inggris, Prancis dan Spanyol).

Upah kerja perjam dalam mengerjakan lahan gandum di Inggris, Prancis dan Spanyol

berturut-turut adalah $5.00, $5.00 dan $3.00. Sedangkan untuk mengerjakan lahan barley

diberikan upah $5.00, $4.00 dan $5.00 per jam, dan untuk mangerjakan lahan oat adalah

$4.00, $2.00 dan $4.75 per jam.

Masalhnya adalah bagaimana mengalokasikan penggunaan lahan di tiap negara tersebut untuk

memenuhi kebutuhan pangan dunia dan untuk meminimumkan upah kerja total yang harus

dibayarkan.

SOAL - JAWAB


JAWAB

Perhitungan Upah Kerja

Untuk mengerjakan lahan gandum per hektar

di Inggris : 4 jam x $5.00/jam = $ 20.00

di Prancis : 3 jam x $5.00/jam = $ 15.00

di Spanyol : 5 jam x $3.00/jam = $ 25.00

Untuk mengerjakan lahan barley per hektar

di Inggris : 1 jam x $5.00/jam = $5.00

di Prancis : 5 jam x $4.00/jam = $20.00

di Spanyol : 2 jam x $5.00/jam = $10.00

Untuk mengerjakan lahan oat per hektar

di Inggris : 2 jam x $4.00/jam = $8.00

di Prancis : 5 jam x $2.00/jam = $10.00

di Spanyol : 4 jam x $4.75/jam = $19.00

Berdasarkan hasil-hasil perhitungan diatas, maka diperoleh tabel biaya transportasi seperti

berikut ini :

Komoditi

Negara Gandum Barley Oat

Inggris 20 5 8

Prancis 15 20 10

Spanyol 25 10 19

Langkah selanjutnya :

Periksa dulu apakah Total Demand (Qd) dengan Total Supply (Qs) sama atau tidak

Jika Qd = Qs, maka dikatakan Tabel Transportasi seimbang (equilibrium), jadi tidak

perlu ada kolom dummy (tujuan dummy) maupun baris dummy (sumber dummy)

Jika Qd > Qs, maka perlu diseimbangkan dengan menambahkan baris dummy (sumber

dummy)

Jika Qd < Qs, maka perlu diseimbangkan dengan menambahkan kolom dummy (tujuan

dummy)


Dalam soal ini Qd = 200 dan Qs = 200, artinya tabel transportasi sudah dalam kondisi

seimbang, sehingga tidak perlu ada kolom maupun baris dummy.

Tentukan tabel transportasi awal dengan metode NWC (North-West Corner), sehingga

diperoleh :

Komoditi

Negara GANDUM BARLEY OAT SUPPLY Ui

INGGRIS 50 20

40 5

8

90 U1 = 0

PRANCIS

15 60

20

10 60 U2 = 15

SPANYOL 25

10 10

40 19

50 U3 = 5

DEMAND 50 110 40 200

Vj V1 = 20 V2 = 5 V3 = 14

Total Biaya = X11 (C11) + X12 (C12) + X22 (C22) + X32 (C32) + X33 (C33)

= 50(20) + 40(5) + 60(20) + 10(10) + 40(19)

= 3260 (Solusi layak, belum tentu optimal)

Untuk menentukan solusi optimal, gunakan metode MODI (Modified Distribution).


C11 = U1 + V1 = 20 U1 = 0 V1 = 20

C12 = U1 + V2 = 5 U1 = 0 V2 = 5

C22 = U2 + V2 = 20 V2 = 5 U2 = 15

C32 = U3 + V2 = 10 V2 = 5 U3 = 5

C33 = U3 + V3 = 19 U3 = 5 V3 = 14


K13 = C13 – U1 – V3 = 8 – 0 – 14 = -6

K21 = C21 – U2 – V1 = 15 – 15 – 20 = -20

K23 = C23 – U2 – V3 = 10 – 15 – 14 = -19

K31 = C31 – U3 – V1 = 25 – 5 – 20 = 0


Isilah sel-sel kosong yang mempunyai indeks perbaikan negatif yang dimulai dari sel dengan

negatif terbesar (X21), dan diperoleh tabel transportasi berikut :

Komoditi


INGGRIS 50

(-)

20 40 90

(+)

5

8 90 U1 = 0

PRANCIS 50

(+)

15 60 10

(-)

20

10 60 U2 = 15

SPANYOL 25

10 10

40 19

50 U3 = 14

DEMAND 50 110 40 200

Vj V1 = 0 V2 = 5 V3 = 5



C12 = U1 + V2 = 5 U1 = 0 V2 = 5

C21 = U2 + V1 = 15 U2 = 15 V1 = 0

C22 = U2 + V2 = 20 V2 = 5 U2 = 15

C32 = U3 + V2 = 10 V2 = 5 U3 = 5

C33 = U3 + V3 = 19 V3 = 5 U3 = 14


K11 = C11 – U1 – V1 = 20 – 0 – 0 = 20

K13 = C13 – U1 – V3 = 8 – 0 – 5 = 3

K23 = C23 – U2 – V3 = 10 – 15 – 5 = -10

K31 = C31 – U3 – V1 = 25 – 14 – 0 = 11




Komoditi


INGGRIS 20

90 5

8

90 U1 = 0

PRANCIS 50 15 10

(-)

20 10

(+)

10 60 U2 = -4

SPANYOL 25 10 20

(+)

10 40 30

(-)

19 50 U3 = 5

DEMAND 50 110 40 200

Vj V1 = 19 V2 = 5 V3 = 14



C12 = U1 + V2 = 5 U1 = 0 V2 = 5

C21 = U2 + V1 = 15 U2 = -4 V1 = 19

C23 = U2 + V3 = 10 V3 = 14 U2 = -4

C32 = U3 + V2 = 10 V2 = 5 U3 = 5

C33 = U3 + V3 = 19 U3 = 5 V3 = 14


K11 = C11 – U1 – V1 = 20 – 0 – 19 = 1

K13 = C13 – U1 – V3 = 8 – 0 – 14 = -6

K22 = C22 – U2 – V2 = 20 – (-4) – 5 = 19

K31 = C31 – U3 – V1 = 25 – 5 – 19 = 1




Komoditi


INGGRIS 20 90 60

(-)

5 30

(+)

8 90 U1 = 0

PRANCIS 50 15

20

10 10

60 U2 = 2

SPANYOL 25 20 50

(+)

10 30

(-)

19 50 U3 = 5

DEMAND 50 110 40 200

Vj V1 = 13 V2 = 5 V3 = 8



C12 = U1 + V2 = 5 U1 = 0 V2 = 5

C13 = U1 + V3 = 8 U1 = 0 V3 = 8

C21 = U2 + V1 = 15 U2 = 2 V1 = 13

C23 = U2 + V3 = 10 V3 = 8 U2 = 2

C32 = U3 + V2 = 10 V2 = 5 U3 = 5


K11 = C11 – U1 – V1 = 20 – 0 – 13 = 7

K22 = C22 – U2 – V2 = 20 – 2 – 5 = 13

K31 = C31 – U3 – V1 = 25 – 5 – 13 = 7

K33 = C33 – U3 – V3 = 19 – 5 – 8 = 6

Dalam tabel tersebut tampak indeks perbaikan untuk semua sel kosong sudah positif semua,

ini berarti bahwa solusi optimal telah tercapai. Jadi total biaya transportasi mínimum sesuai

dengan tabel transportasi berikut :


Komoditi

Negara GANDUM BARLEY OAT SUPPLY

INGGRIS 20

60 5

30 8

90

PRANCIS 50 15

20

10 10

60

SPANYOL 25

50 10

19 50

DEMAND 50 110 40 200

Maka persamaan linear fungsi tujuan, kendala dan total biayanya menjadi sebagai berikut :

Fungsi Tujuan

Minimum Z = (C12) X12 + (C13) X13 + (C21) X21 + (C23) X23 + (C32) X32

Minimum Z = 5X12 + 8X13 + 15X21 + 10X23 + 10X32

Minimum Z = 5 (60) + 8 (30) + 15 (50) + 10 (10) + 10 (50)

Minimum Z = 300 + 240 + 750 + 100 + 500

Minimum Z = 1890

Fungsi Kendala Kapasitas Produksi Negara

(1) X11 + X12 + X13 ≤ 90

(2) X21 + X22 + X23 ≤ 60

(3) X31 + X32 + X33 ≤ 50

Fungsi Kendala Permintaan Komoditi

(1) X11 + X21 + X31 ≤ 50

(2) X12 + X22 + X32 ≤ 110

(3) X13 + X23 + X33 ≤ 40

Kendala Non-Negatif

X11, X12, X13, X21, X22, X23, X31, X32, X33 ≥ 0

operation research - transportation...

Documents