Manajemen Sains. Model Transportasi. Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Manajemen Sains Model Transportasi

Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Pengertian Model transportasi adalah kelompok khusus program

linear yang menyelesaikan masalah pengiriman komoditas dari sumber (misalnya pabrik) ke tujuan (misalnya gudang). Tujuannya adalah untuk menentukan jadwal pengiriman dengan meminimalkan total biaya pengiriman dengan memenuhi batas pasokan dan kebutuhan. Aplikasi transportasi dapat dikembangkan didaerah operasi yang lain, misalnya inventory control, penjadwalan pekerja (employment scheduling), dan penilaian personal (personnel assignment).

2

Teknik Informatika UMG 2011

Pengertian

3


Contoh kasus MG Auto MG Auto mempunyai tiga area produksi (plant) di Los

Angeles. Detroit, dan New Orleans, dan dua pusat distribusi utama di Denver dan Miami. Kapasitas tiga plant pada kuartalan adalah 1000, 1500, dan 1200 mobil. Kebutuhan kuartalan pada dua pusat distribusi adalah 2300 dan 1400 mobil. Tabel jarak antara plant dan pusat distribusi di Tabel 1. Trucking Company meminta biaya transportasi mobil sebesar 8 sen per mil per mobil. Biaya transportasi per mobil pada rute yang berbeda, disesuaikan pada nilai dolar terdekat, ditampilkan dalam Tabel 2. Model pemrograman linier masalah sebagai berikut : Minimalkan Z = 80x11 + 215x12 + 100x21 + 108x22 +

102x31 + 68x32

4


Contoh kasus MG Auto Tabel 1 Jarak (mil)

Biaya transportasi

per mobil ($)

Los Angeles

1000

2690

Los Angeles (1)

Denver (1) 80

Detroit

1250

1350

Detroit (2)

100

850

New Orleans (3) 102

Denver Miami

New Orleans 1275

5


Miami (2) 215 108 68

Model Transportasi MG Auto Denver

Miami

Supply

80

215

Los Angeles

1000 x11

x12 100

108

Detroit

1500 x21

x22 102

68

New Orleans

1200 x31

Kebutuhan 6

2300


x32 1400

3700

Solusi MG Auto

Solusi optimal yang didapatkan seperti pada Gambar

menyatakan bahwa untuk pengiriman 1000 mobil dari Los Angeles ke Denver, 1300 dari Detroit ke Denver, 200 dari Detroit ke Miami, dan 1200 dari New Orleans ke Miami. Biaya transportasi minimal dihitung dengan Z = 1000 * 80 + 1300 * 100 + 200 * 108 + 1200 * 68 = $313200 7


Menyeimbangkan model transportasi Algoritma transportasi didasarkan pada asumsi bahwa model

8

dalam keadaan seimbang, artinya total kebutuhan sama dengan total pasokan (supply). Jika model tidak seimbang, maka dapat ditambahkan sumber dummy atau tujuan dummy untuk memberikan keseimbangan Dalam model MG, andaikan kapsitas plant Detroit adalah 1300 mobil (bukan 1500). Total supply (=3500 mobil) lebih kecil dari total kebutuhan (=3700 mobil), artinya ada sebagian dari Denver atau Miami yang yang tidak akan dicapai kapasitasnya. Karena kebutuhan melebihi pasokan, sebuah sumber dummy (plant) dengan kapasitas 200 mobil (=3700 – 3500) ditambahkan untuk menyeimbangkan model transportasi. Biaya unit transportasi dari plant dummy ke dua tujuan adalah nol karena sebenarnya plant tidak ada


Kasus model MG dengan sumber dummy Denver

Miami

Supply

80 Los Angeles

215 1000

1000 100

Detroit

108 1300

1300 102

68

New Orleans 0 Plant dummy Kebutuhan 9


1200

1200 0 200 2300

1400

200 3700

Menyeimbangkan model transportasi Untuk kasus dimana pasokan melebihi kebutuhan

misalnya dalam kasus model MG kebutuhan di Denver adalah 1900 mobil. Dalam kasus ini, kita perlu menambahkan tujuan dummy untuk menerima pasokan kelebihan (surplus). Biaya unit transportasi pada tujuan dummy adalah nol

10


Kasus model MG dengan tujuan dummy Denver

Miami

Dummy

80 Los Angeles

215

1000

900

108 200

102 New Orleans Kebutuhan

11

0 1000

100 Detroit

0


1500

400 68

0 1200

1200 1900

Supply

1400

400

3700

Varian model transportasi

Penerapan model transportasi tidak dibatasi hanya pada pengiriman komoditas antara sumber dan tujuan secara geografis. Bidang lain yang dapat menerapkan model transportasi diantaranya adalah productioninventory control dan sharpening service. Boralis memproduksi tas ransel untuk para pendaki. Kebutuhan produk terjadi selama blan Maret sampai Juni setiap tahun. Perusahaan menggunakan tenaga kerja paruh waktu untuk memproduksi tas ransel, dan ternyata kapasitas produksi bervariasi setiap bulannya. Diperkirakan bahwa Boralis akan memproduksi 50, 180, 280, dan 270 unit di bulan Maret sampai Juni. Karena kapasitas produksi dan kebutuhan ternyata berbeda pada tiap bulannya, kebutuhan bulan saat ini dapat dipenuhi dengan tiga cara :

12

Produksi pada bulan ini Kelebihan (surplus) produksi pada bulan sebelumnya Kelebihan (surplus) produksi pada bulan berikutnya (backordering)

Dalam kasus yang pertama, biaya produksi per tas ransel adalah $40. Pada kasus kedua terjadi biaya tambahan untuk pengelolaan (inventory) sebesar $0.5 per tas ransel per bulan. Pada kasus ketiga, biaya tambahan pelanggaran (penalty) sebesar $2 per tas ransel pada delay setiap bulannya. Boralis menginginkan untuk menentukan jadwal produksi yang optimal untuk empat bulan tersebut.


Paralelisme antara masalah productioninventory dan model transportasi Transportasi

Production-inventory

Sumber i

Periode produksi i

Tujuan j

Kebutuhan periode j

Jumlah pasokan di sumber i

Kapasitas produksi periode i

Kebutuhan tujuan j

Kebutuhan periode j

Biaya transportasi unit dari sumber i Biaya unit (produksi + inventory + ke tujuan j penalty) dalam periode i untuk periode j

13


Model transportasi kasus Boralis Biaya kapasitas produksi ($) 1

Bulan produksi

2

3

4

Supply

1

40

40.5

41

41.5

50

2

42

40

40.5

41

180

3

44

42

40

40.5

280

4

46

44

42

40

270

100

200

180

300

Kebutuhan

Biaya unit “transportasi” dari periode i ke periode j dihitung sebagai : Misalnya : c11 = $40 c24 = $40 + ($0.5 + $0.5) = $41 c41 = $40 + ($2 + $2) = $46

14


Biaya produksi dalam i, i = j  cij = Biaya produksi dalam i +biaya pegelolaan dari i ke j, i < j Biaya produksi dalam i + biaya pelanggaran dari i ke j, i > j 

Solusi optimal model productioninventory Garis putus-putus

menunjukkan backordering Garis titik-titik menunjukkan produksi untuk bulan berikutnya, dan garis solid menunjukkan produksi pada periode saat itu. Total biaya Z adalah 50 * 40 + 50 * 42 + 130 * 40 + 70 * 42 + 180 * 40 + 30 * 40.5 + 270 * 40 = 2000 + 2100 + 5200 + 2940 + 7200 + 1215 + 10800 = $31455

15


Solusi awal Model Transportasi Ada tiga metode yang bisa diplih untuk mendapatkan

solusi layak awal model transportasi : Metode northwest-corner Metode least-cost Metode Vogel approximation

Tiga metode diatas berbeda dalam kualitas basis

solusi awal yang dihasilkan, dalam kaitan bahwa solusi awal nilainya lebih kecil. Metode Vogel memberikan basis solusi awal yang paling baik, dan metode northwest-corner yang paling jelek. Tradeoffnya adalah metode northwest-corner menggunakan usaha yang paling sedikit dalam komputasi

16


Contoh kasus SunRay SunRay Transport Company mengirimkan

muatan truk berupa tepung dari tiga silo ke empat mill. Pasokan (muatan truk) dan kebutuhan (muatan truk) bergabung dengan biaya transportasi unit per muatan truk pada rute yang berbeda ditunjukkan pada tabel x. Biaya transportasi unit, cij (pojok kanan atas kotak) dalam ratusan dollar. Model mencari jadwal pengiriman xij antara silo i dan mill j (i = 1,2,3; j = 1,2,3,4) 17


Tabel transportasi kasus SunRay Mill 1

Mill 2 10

Mill 3 2

Mill 4 20

11

Silo 1

15 x11

x12 12

x13 7

x14 9

20

Silo 2

25 x21

x22 4

x23 14

x24 16

18

Silo 3

10 x31

Kebutuhan 18

Supply

x32 5


15

x33 15

x34 15

50

Menggunakan metode NorthwestCorner Alokasikan sebanyak mungkin pada sel yang dipilih, dan sesuaikan jumlah supply dan kebutuhan dengan mengurangi alokasi yang dibutuhkan. 2. Pindah ke garis atau kolom dengan nilai alokasi supply atau kebutuhan nol (belum dialokasikan). Jika baris dan kolom sel tadi belum ada alokasi maka alokasikan sisa tadi ke sel ini. Jika masih kurang, maka pindah ke baris atau kolom lainnya untuk menambah alokasi. 3. Jika masih ada baris atau kolom yang jumlah alokasi supply dan kebutuhan belum mencapai maksimal, kembali ke langkah 1. Jika tidak, maka berhenti. 1.

19


Solusi awal dengan metode NWC Mill 1

Dari tabel diatas,

basis solusi adalah : x11 = 5, x12 = 10 x22 = 5, x23 = 15,

x24 = 5 x34 = 10

Biaya jadwal

Mill 2

10

Mill 3 2

Silo 1 5

20


2 0

11

9

20

Supply

15

10 12

Silo 2

7 5

15

4

14

25

5 1 6

Silo 3

menjadi :

Z = 5 * 10 + 10 * 2 + 5 * 7 + 15 * 9 + 5 * 20 + 10 * 18 = $520

Mill 4

18 10 10

Kebut uhan

5

15

15

15

50

Menggunakan metode Least-Cost Sel (1,2) mempunyai biaya unit terkecil dalam tabel (=$2). Jumlah terbanyak yang dapat dikirimkan pada jalur (1,2) adalah x12 = 15. 2. Sel (3.1) mempunyai biaya unit terkecil berikutnya (=$4). Berikan x31 = 5 karena kapasitas maksimal di kolom 1 adalah 5, alokasi supply yang dibutuhkan tinggal 10 – 5 = 5. 3. Lanjutkan cara yang sama, sehingga sel (2.3) dialokasikan 15, sel (3.4) dialokasikan 5, dan sel (2.4) dialokasikan 10. 1.

21


Solusi awal dengan metode LeastCost Dari tabel diatas,

22

basis solusi adalah : x12 = 15 x23 = 15, x24 = 10 x31 = 5, x34 = 5 Biaya jadwal menjadi : Z = 15 * 2 + 15 * 9 + 10 * 20 + 5 * 4 + 5 * 18 = 30 + 135 + 200 + 20 + 90 = $475 Teknik Informatika UMG 2011

Mill 1

Mill 2

10 Silo 1

(start)

Mill 3 2

7

9 15

4

11

(end) 20 25

10

14

16

5

18 10

5 5

Supply 15

Silo 2

Kebutuh an

20

15 12

Silo 3

Mill 4

15

15

15

50

Menggunakan VAM 1.

2.

3.

Untuk setiap baris (kolom), tentukan ukuran penalty dengan mengurangkan elemen unit biaya terkecil dalam baris (kolom) dari elemen unit biaya terkecil berikutnya dalam baris (kolom) yang sama. Identifikasi baris (kolom) dengan penalty terbesar. Alokasikan sebanyak mungkin pada variabel dengan biaya unit terkecil dalam baris (kolom) terpilih. Sesuaikan supply dan kebutuhan, dan mencapai batas maksimal supply atau kebutuhan. Jika baris (kolom) tercapai secara simultan, maka sisa alokasi pada baris (kolom) tersebut menjadi nol. (a) Jika tepat satu baris atau kolom dengan sisa nol supply atau kebutuhan, berhenti. (b) Jika satu baris (kolom) dengan supply (kebutuhan) positif belum mencapai maksimal, tentukan variabel basis dalam baris (kolom) dengan metode least-cost, berhenti. (c) Jika semua baris dan kolom yang belum maksimal mempunyai (sisa) supply dan kebutuhan nol, tentukan basis variabel nol dengan metode least-corner, berhenti. (d) Selain tiga pilihan diatas, maka berhenti.

23


Iterasi 1 Baris Penalty Mill 1

Mill 2

10

Mill 3 2

Mill 4

20

11

Silo 1 12

7

9

14

16

24

5

15

15

10 – 4 = 6

7–2=5

16 – 9 = 7


10 – 2 = 8

25

9–7=2

10

14 – 4 = 10

18

Silo 3 Kebutuhan Kolom Penalty

15 20

Silo 2 4

Supply

15 18 – 11 = 7

50

Iterasi 2 Mill 1

Mill 2

10

Mill 3 2

Silo 1

12

7

2 0

1 1

9

2 0

Silo 2

4

14

Silo 3

Mill 4

1 6

1 8

15 16 – 9 = 7

15 18 – 11 = 7

Supply Baris Penalty

15

11 – 2 = 9

25

9–7=2

10

16 – 14 = 2

5 Kebutuhan Kolom Penalty

25


5

15

-

7–2=5

50

Iterasi 3 Mill 1

Mill 2 10

Silo 1

Mill 3 2

Mill 4 20

7

9

Silo 3 Kebutuhan Kolom Penalty

26

14

16

25

20 – 9 = 11

10

18 – 16 =2

18

5 5

15

15

15

-

-

16 – 9 = 7

20 – 18 = 2


-

20

Silo 2 4

15

11

15 12

Supply

Baris Penalty

50

Iterasi 4 Mill 1

Mill 2 10

Silo 1

Mill 3 2

7

Silo 2

Kolom Penalty

27

9

14

15

-

25

20

10

18

20

16

18

5 5

15

15

15

-

-

-

20 – 18 = 2


Supply 11

15 4

Kebutuhan

20

15 12

Silo 3

Mill 4

Baris Penalty

50

Hasil solusi awal dengan VAM Mill 1

Mill 2 10

Silo 1

Mill 3 2

7

9 15

4

16

5

Baris Penalty

15

-

25

-

10

-

20 10

14

Supply 11

0

Silo 2

Kebutuhan Kolom Penalty

20

15 12

Silo 3

Mill 4

18 5

5

15

15

15

-

-

-

-

50

Nilai tujuan pada solusi ini menjadi : Z = 15 * 2 + 0 * 11 + 15 * 9 +

10 * 20 + 5 * 4 + 5 * 18 = $475. Hasil ini sama seperti yang didapatkan pada metode least-cost 28


Metode menuju solusi optimal Stepping Stone ( batu loncatan ) 2. Modified Distribution Method ( MODI ) 1.

29


Stepping Stone ( batu loncatan ) Syarat : Jumlah rute atau sel yang mendapat alokasi harus

sebanyak :

Jumlah Kolom + Jumlah Baris – 1

Langkah – langkahnya : 1. Memilih salah satu sel kosong (yang tidak mendapatkan alokasi). 2. Mulai dari sel ini, kita membuat jalur tertutup melalui sel-sel yang mendapatkan alokasi menuju sel kosong terpilih kembali. Jalur tertutup ini bergerak secara horisontal dan vertikal saja. 3. Mulai dengan tanda (+) pada sel kosong terpilih, kita menempatkan tanda (-) dan (+) secara bergantian pada setiap sudut jalur tertutup. 4. Menghitung indeks perbaikan dengan cara menjumlahkan biaya transportasi pada sel bertanda (+) dan mengurangkan biaya transportasi pada sel bertanda (-). 5. Mengulangi tahap 1 sampai 4 hingga indeks perbaikan untuk semua sel kosong telah terhitung. Jika indeks perbaikan dari sel-sel kosong lebih besar atau sama dengan nol, solusi optimal telah tercapai.

30


Modified Distribution Method (MODI) Indeks perbaikan dihitung dengan terlebih dahulu menentukan

nilai baris dan kolom. Notasi dalam metode MODI terdiri dari: Ri = nilai yang ditetapkan untuk baris i Kj = nilai yang ditetapkan untuk kolom j Cij = biaya transportasi dari sumber i ke tujuan j

Ada lima langkah dalam aplikasi metode MODI, yaitu: 1. Menghitung nilai setiap baris dan kolom, dengan menetapkan 2. 3. 4. 5.

31

Ri + Kj = Cij . Formula tersebut berlaku untuk sel yang mendapat alokasi saja. Setelah semua persamaan telah tertulis, tetapkan R1 = 0 Mencari solusi untuk semua R dan K. Menghitung indeks perbaikan dengan menggunakan formula Iij= Cij - Ri - Kj . Mengaplikasikan kriteria optimalitas sebagaimana pada metode stepping stone.


Contoh kasus 3 pabrik Tiga pabrik dalam satu group (W,H,P) dengan kapasitas

produksi masing-masing adalah 90, 60, dan 50. Hasil produksi akan didistribusikan ke tiga gudang (A,B,C) yang kapasitas penyimpanan masing-masing adalah 50, 110, dan 40. Tabel biaya pengiriman produk dari pabrik ke gudang ditampilkan pada tabel dibawah ini. Perusahaan ingin mendistribusikan produk ke masing-masing gudang dengan biaya pengiriman yang minimal.

32


Metode NWC

Biaya yang dikeluarkan Z = (50 . 20) + (40 . 5) + (60 . 20) + (10 . 10) + (40 .

19) = 3260 33


Metode Least-Cost

Biaya yang dikeluarkan : Z = (90 . 5) + (20. 15) + (40 . 10) +(30 .25) + (20. 10) =

2400 34


MENGOPTIMALKAN TABEL (Stepping Stone) - 1

35



Setelah dihitung dengan trial dan error , biaya yang dikeluarkan

adalah: Z = (50 . 15) + (90 . 5) + (10 . 20) + (10 . 10) + (40 . 19) = 2260

36



Setelah dihitung dengan trial dan error , biaya yang dikeluarkan

adalah: Z = (50 . 5) + (40 . 8) + (50 . 15) + (10 . 20) + (50 . 10) = 2020

37



Biaya yang dikeluarkan :

Z = (60 . 5) + (30 . 8) + (50 . 15) + (10 .10) + (50 . 10) = 1890 (paling optimal) Jika hasil belum optimal, lakukan perbaikan terus sampai

mendapatkan hasil yang optimal.

38


MENGOPTIMALKAN TABEL (MODI) -1 Hitung sel yang berisi (nilai tiap kolom dan tiap baris)

Ri + Kj = Ci baris kolom biaya

1. W-A = R1 + K1 = 20 2. W-B = R1 + K2 = 5 3. H-B = R2 + K2 = 20 4. P-B = R3 + K2 = 10 5. P-C = R3 + K3 =19 dari persamaan di atas, hitung K1 dan R1 dengan cara meng-nol-kan

variabel

R1 atau K1, misal R1 = 0 1. R1 + K1 = 20 => 0 + K1 = 20 , K1 =20 2. R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5 3. R2 + K2 = 20 => R2 + 5 = 20 , R2 = 15 4. R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5 5. R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14 letakkan nilai tersebut pada baris / kolom yang bersangkutan 39


MENGOPTIMALKAN TABEL (MODI) -1

40


MENGOPTIMALKAN TABEL (MODI) -1 Hitung nilai/ index perbaikan setiap sel yang kosong

dengan rumus: Cij - Ri - Kj 1. H-A = 15 – 15 – 20 = - 20 2. P-A = 25 – 5 – 20 = 0 3. W-C = 8 – 0 – 14 = - 14 4. H-C = 10 – 15 – 14 = - 19 (optimal jika pada sel yang kosong, indek

perbaikannya ≥ 0, jika belum maka pilih yang negatifnya besar) Memilih titik tolak perubahan Pilih nilai yang negatifnya besar yaitu H-A 41



42


Hitung sel yang berisi W-B = R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5 H-A = R2 + K1 = 15 => R2 + 0 = 15, R2 = 15 H-B = R2 + K2 = 20 => 15 + 5 = 20 , P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5 P-C = R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14 Perbaikan indeks: W-A = 20 – 0 – 0 = 20 W-C = 8 – 0 – 14 = - 6 H-C = 10 – 15 – 14 = - 19 P-A = 25 – 5 – 0 = 20 43



Biaya transportasi : Z = (90 . 5) + (50 . 15) + (10 .

10) + (20 . 10) + (30 . 19) = 2070 44


Hitung sel yang berisi :

W-B = R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5 P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5 P-C = R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14 H-C = R2 + K3 = 10 => R2 + 14 = 10 , R2 = - 4 H-A = R2 + K1 = 15 => - 4 + K1 = 15 , K1 = 19

Perbaikan indeks (sel kosong) : 45

W-A = 20 – 0 – 0 = 20 W-C = 8 – 0 – 14 = - 6 H-B = 20 – 15 – 5 = 0 P-A = 25 – 5 – 0 = 20



Biaya transportasi :

Z = (60 . 5) + (30 . 8) + (50 . 15) + (10 . 10) + (50 .10) = 300 + 240 + 750 + 100 + 500 = 1890 46


Sel berisi:

W-B = R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5 W-C = R1 + K3 = 8 => 0 + K3 = 8 , K3 = 8 H-C = R2 + K3 = 10 => R2 + 8 = 10 , R2 = 2 H-A = R2 + K1 = 15 => 2 + K1 = 15 , K1 = 13 P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5

Indeks perbaikan:

W-A = 20 – 0 – 19 = 1 H-B = 20 – (-4) – 5 = 19 P-A = 25 – 5 – 19 = 1 P-C = 19 – 5 – 14 = 0

Indeks perbaikan sudah positif semua, berarti sudah

optimal.

47


Solusi optimal metode MODI

Biaya transportasi :

Z = (60 . 5) + (30 . 8) + (50 . 15) + (10 . 10) + (50 .10) = 300 + 240 + 750 + 100 + 500 = 1890 48


Latihan Benar atau salah ? Untuk menyeimbangkan model transportasi, perlu menambah sumber dummy dan tujuan dummy. Jumlah yang dikirimkan pada tujuan dummy merepresentasikan kelebihan (surplus) pada sumber pengiriman. Jumlah yang dikirim dari sumber dummy merepresentasikan kekurangan pada tujuan pengiriman. Disetiap kasus dibawah ini, manakah sumber dummy atau

tujuan dummy yang harus ditambahkan untuk menyeimbangkan model :

Supply : a1 = 10, a2 = 5, a3 = 4, a4 = 6. Sedangkan kebutuhan :

b1 = 10, b2 = 5, b3 = 7, b4 = 9. Supply : a1 = 30, a2 = 44. Sedangkan kebutuhan : b1 = 25, b2 = 30, b3 = 10.

49


Tugas Baca Modul 6 Model Penugasan Kerjakan soal Modul 5 :

Kelompok 1 : 5.3 Kelompok 2 : 5.4 Kelompok 3 : 5.5 Kelompok 4 : 5.6 metode Stepping Stone Kelompok 5 : 5.7 metode Stepping Stone Kelompok 6 : 5.6 metode MODI Kelompok 7 : 5.7 metode MODI

Pengerjaan : Satu kelompok berisi maksimal 9 orang Ditulis tangan pada kertas folio bergaris oleh masing-masing

anggota Dikumpulkan pada pertemuan berikutnya

50


Manajemen Sains. Model Transportasi. Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Recommend Documents