riset operasional pertemuan 8

7/23/2019 Riset Operasional Pertemuan 8

1/10

BAB VIMODEL TRANSPORTASI

MASALAH TRANSPORTASI

Merupakan masalah pendistribusian suatu produk/barang dari sejumlah sumber (supply)

ke sejumlah tujuan (demand), untuk meminimumkan biaya transportasi.

Merupakan bentuk khusus dari masalah linier programming, dengan kekhususan :

o Jumlah kendala dan variabel sangat banyak

o Kebanyakan koefisien a ijbernilai nol

iri!"iri khusus masalah transportasi :

#. $erdapat sejumlah sumber (%i) dan sejumlah tujuan (&j)

'. Jumlah produk/barang yang didistribusikan dari sumber ke!i sesuai dengan

kebutuhan tujuan ke!j adalah sebanyak ( ij)

. *roduk/barang yang diangkut dari suatu sumber ke suatu tujuan sesuai dengan

permintaan tujuan (b j) dan sesuai dengan kapasitas sumber (a i)

+. iaya transportasi produk dari suatu sumber!i ke suatu tujuan!j sebesar dapat dihitung

( ij)

Gambaran Umum Model Transportas

%umber (%upply- %i) $ujuan (&emand- D!)

## : ## b#a#

b'

a'

b

RISET OPERASIONAL

Nof Erni


2/10

%e"ara matematis , formulasi program liniernya dapat dinyatakan sebagai berikut :

m n

Minimumkan ijij,i# j #

m

&engan pembatas : ij a i i #,',,0m (supply sumber ke!i)i#

n

ij bj, j #,',,0n (permintaan tujuan ke!j)

j#

ij 1 2 untuk seluruh i dan j

&imana :

a i, : (i #,',,0m ) : menunjukkan supply pada sumber ke!ibj , : (j #,',,0n ) : menunjukkan permintaan pada tujuan ke!j

ij, : menunjukkan biaya angkut per unit dari sumber ke!i menuju tujuan ke!jij : menunjukkan jumlah yang diangkut dari sumber ke!i menuju tujuan ke!j

A" Pen#elesaan den$an metode smple%

3ormulasi program linier dari gambaran umum diatas adalah :

Minimumkan : ####4 #'#'4 ##4 '#'#4 '''' 4 ''

&engan pembatas :

##4 #'4# a# pembatas sumber

'#4 '' 4 ' a'

##4 '# b#

#'4 '' b' pembatas tujuan

#4 ' b

##, #', ....' 1 2

RISET OPERASIONAL

Nof Erni


3/10

&onto' (

*erusahaan M5 6uto ompany memiliki pabrik mobil di 7os 6ngeles, &etroit dan 8e9rleans. *usat distribusi berlokasi di &enver dan Miami. Kapasitas ke tiga pabrik se"ara

berturut!turut #222, #;22 dan #'22 mobil, sedang permintaan pada pusat distribusi sebesar '22

dan #+22 mobil. iaya transportasi dari pabrik ke pusat distribusi disajikan pada $abel berikut :

&enver Miami

7os 6ngeles


4/10

B" Pen#elesaan den$an al$ortma transportas

Masalah transportasi disusun dalam $abel $ransportasi

$abel. 6lgoritma $ransportasi

$ujuan ( j )

%umber (i )

Kota#

Kota'

Kota

%upply

5udang # a#

5udang ' a'

&emand b# b' b

entuk permasalahan transportasi :

#. alan"ed : terdapat keseimbangan total supply dengan total demand

&engan formulasi matematika sbb:

m n

ai bji # j #

$abel $ransportasi >alan"ed?

Tujuan Supply

Sumber Denver Miami

80 215

Los Angeles X11 X12 1000 100 108

Detroit X21 X22 1500 102 68

New Orleans X31 X32 1200

Demand 2300 1400 3700

'. @nbalan"ed : jka total supply tidak sama dengan total demand

o Jika jumlah supply melebihi jumlah demand maka dibuat suatu tujuan

dummy (kolom dummy) untuk menyerap kelebihan supply

RISET OPERASIONAL

Nof Erni


5/10

o Jika jumlah demand melebihi jumlah supply maka dibuat suatu sumber

dummy (baris dummy) untuk memasok kekurangan demand

o iaya transportasi per unit dari sumber dummy ke seluruh tujuan adalah nol)

demikian juga biaya transportasi dari semua sumber ke tujuan dummy adalah

nol karena pada kenyataannya tidak terjadi pengiriman

$abel $ransportasi >@nbalan"ed?

Tujuan Supply

Sumber Denver Miami Dummy

80 215 0

Los Angeles 1000 100 108 0

Detroit 1500

102 68 0 New Orleans 1200

Demand 1900 1400 400 3700

%upply 1 demand : A22!22 +22 ditempatkan pada kolom dummy.

6tau sebaliknya jika suuply lebih ke"il dari demand ditambahkan baris dummy

Jika pada suatu masalah transportasi dinyatakan bah9a pada sumber ke! i tidak boleh ada

pengiriman ke tujuan ke!j maka biaya transportasi dinyatakan dengan suatu harga positif

yang besarnya tidak terhingga ( M)

Tujuan Supply

Sumber Denver Miami

M 215

Los Angeles X11 X12 1000 100 108

Detroit X21 X22 1500 102 M

New Orleans X31 X32 1200Demand 2300 1400

RISET OPERASIONAL

Nof Erni


6/10

%e"ara umum metode penyelesaian masalah transportasi mengikuti langkah :

#. $entukan solusi layak a9al

'. $entukan entering variable dari variable non basis (sel kosong), jika semua variable

sudah optimum, %$*, jika belum lanjutkan langkah

. $entukan leaving variable diantara variable basis (sel terisi) yang ada, kemudian

hitung solusi baru dan kembali ke langkah '.

B"*" Menentu%an solus la#a% a+al

Metode yang biasa digunakan untuk mementukan solusi layak a9al :

a" Metode Sudut Barat Laut ,nort'+est -orner.- metode pojok kiri atas menuju kanan

ba9ah , dengan "ara :

#. Mulai dari sudut kiri atas sudut barat laut (sel ##) dan aloasikan sebanyak

mungkin untuk ##dengan memenuhi ## min (a# ,b#)

'. 7anjutkan pengalokasian pada sel :

i, j 4# #' : jika sumber B i , mempunyai kapasitas sisa

i4#, j '# : jika sumber B i , tidak mempunyai kapasitas sisa

. &emikian seterusnya sampai seluruh sumber teralokasikan.

+. %olusi layak a9al ter"apai, jika jumlah sel terisi sebanyak m 4 n B #

ontoh kasus :

*erusahaan otomotif memiliki kasus transportasi untuk mengrim sejumlah bahan baku

dari gudang ke pabrik seperti disajikan pada $abel berikut.

$abel. Keseimbangan supply dan demand

Tujuan Supply

Sumber 1 2 3

10 0 20 11

1 X11 X12 X13 X14 15

12 7 9 20

2 X21 X22 X23 X24 25

0 14 16 18

3 X31 X32 X33 X34 5Demand 5 15 15 10 45

RISET OPERASIONAL

Nof Erni


7/10

erapa biaya yang diperoleh jika menggunakan metode %7C

&engan menggunakan algortima %7 :

*ilih sel ## : min (a#- b#)

: min (#; - ;): ;

*ilih sel #' : min (sisa pada a#- b')

: min (#2 - #;): #2

*ilih sel '' : min (a'- sisa padab')

: min ('; - ;): ;

*ilih sel ' : min (sisa pada a'- b)

: min ('2 - #;): #;

*ilih sel '+ : min (sisa pada a'- b+): min (; - #2)

: ;*ilih sel + : min (a- sisa pada b+)

: min (; - ;)

: ;

Tabel " Solus la#a% a+al den$an Sudut Barat Laut

Tujuan Supply

Sumber 1 2 3

10 0 20 11 1 5 10 15

12 7 9 20

2 5 15 5 25 0 14 16 18

3 5 5Demand 5 15 15 10 45

Dariabel basis ## ;, '' ;, ' #;, '+ ;, + ;

Min +#2 , layak, belum tentu optimal

b" Metode Ba#a Ter%e-l ,Least &ost.

Metode pendistribusian berdasarkan biaya terke"il

*rinsip memprioritaskan pengalokasian pada sel dengan biaya terke"il

RISET OPERASIONAL

Nof Erni


8/10

7angkah penyelesaian :

#. *ilih sel dengan biaya terke"il, alokasikan sebanyak mungkin untuk ij min( ai, bj)

'. @langi langkah #, sampai semua kapasitas sumber/supply telah teralokasi dansesuai kebutuhan tujuan/demand.

Tabel " Solus la#a% a+al den$an Least &ost ,alt *.

Tujuan Supply

Sumber 1 2 3

10 0 20 11

1 15 15 12 7 9 20

2 5 15 5 25 0 14 16 18

3 5 5

Demand 5 15 15 10 45


9/10

-. Metode Pende%atan Vo$el ,Vo$el Appro0maton Met'od.

*rinsip : meminimumkan biaya pinalti karena alokasi yang salah

Merupakan metode terbaik dibanding dua metode sebelumnya

7angkah penyelesaian :

#. Eitung penalty untuk tiap kolom dan baris dengan "ara : biaya kedua terke"il

dikurangi dengan biaya terke"il (selisih dua biaya terkecil)pada tiap baris dankolom.

'. *ilih kolom/baris dengan biaya penalty terbesar, alokasikan sebanyak mungkin

dengan memenuhi ij min( ai, bj) pada sel dengan biaya terke"il.

. $andai kolom/baris terpilih,dengan menggangap biaya penalty adalah nol,

sehingga tidak ikut dalam penghitungan biaya penalty berikutnya.

+. @langi langkah # B

;. ila tinggal satu kolom/baris yang belum ditandai, %$* dan alokasikan padasel dengan biaya terke"il

ontoh . perhitungan metode D6M langkah #

#. Eitung *enalty baris dan kolom'. *enalty terbesar pada baris , sebesar #+

. iaya terke"il pada baris pada kolom #, sebesar 2 (sel terpilih #)

+. 6lokasikan pada sel terpilih #(min a- b#)

min( #;, ;) ;

$abel. *enalty baris dan kolom

Tujuan Supply penalty

Sumber 1 2 3

10 0 20 11 10

1 15 12 7 9 20 2

2 25 0 14 16 18 14

3 5 15

Demand 5 15 15 10

penalty 10 7 7 7

RISET OPERASIONAL

Nof Erni


10/10

@langi untuk penalty berikutnya.%etelah dilakukan kali perhitungan penalty diperoleh hasil pada $abel berikut.

$abel. %olusi dengan metode D6M

Tujuan Supply penalty

Sumber 1 2 3 1 2 3

10 0 20 11 10 11 11

1 ! 1" 15 12 7 9 20 2 2 13

2 1" 1! 25 0 14 16 18 1 - -

3 ! 5

Demand 5 15 15 10

penalty 1 10 7 7 7

2 - 7 11 9

3 - 7 - 9

Min #;, belum tentu optimal (mendekati optimal).

RISET OPERASIONAL

Nof Erni

riset operasional pertemuan 8

Documents