Praktikum Ii. Transportasi

Laboratorium Komputer V Jurusan Teknik Industri ISTA

PRAKTIKUM II

Transportasi A. Tujuan Praktikum Transportasi 1. Memahami bagaimana memformulasikan permasalahan transportasi. 2. Memahami prosedur pemecahan masalah dengan teknik transportasi 3. Memahami dan dapat mencari solusi/menyelesaikan permasalahan menggunakan beberapa teknik transportasi. B. Alat Yang Digunakan 1. Lembar Pengamatan. 2. Komputer Lengkap dengan Monitor dan Printer. 3. Software WinQSB 4. Kalkulator & Alat Tulis C. Format Praktikum 1. Pre-Test 2. Diskusi 3. Menyelesaikan kasus transportasi menggunakan Software WinQSB D. Landasan Teori Bagian ini akan membahas model transportasi dan berbagai variasinya. Permasalahan dalam transportasi, berhubungan dengan penentuan rencana berbiaya terendah untuk mengirimkan satu barang dari sejumlah sumber (misalnya, pabrik) ke sejumlah tujuan (misalnya, gudang). Model transportasi pada dasarnya merupakan sebuah program linier yang dapat dipecahkan oleh metode simpleks biasa. Tetapi, strukturnya yang khusus memungkinkan pengembangan sebuah prosedur pemecahan, yang disebut teknik transportasi, yang lebih efisien dalam hal perhitungan. Teknik transportasi ini pada dasarnya mengikuti langkah-langkah metode simpleks. Persoalan transportasi membahas masalah pendistribusian suatu produk atau komoditas dari sejumlah sumber (supply) kepada sejumlah pemakai (demand) sebagai tujuannya. Pendistribusian ini mempunyai tujuan meminimumkan ongkos pengangkutan yang terjadi. Ciri-ciri khusus persoalan transportasi adalah: 1. Terdapat sejumlah sumber (pemasok) dan sejumlah permintaan (demand) atau tujuan tertentu. 2. Jumlah barang yang didistribusikan dari setiap sumber dan barang yang diminta oleh pemakai besarnya tertentu. 3. Jumlah barang yang dikirim dari suatu sumber ke pemakai/tujuan besarnya sesuai dengan permintaan dan sesuai dengan kapasitas sumber. 4. Biaya pengangkutan barang dari suatu sumber ke suatu tujuan besarnya tertentu.

Modul Praktikum Penelitian Operasional –Transportasi

9

Laboratorium Komputer V Jurusan Teknik Industri ISTA

D.1 Model Transportasi Formulasi program linier untuk model transportasi bentuk umumnya dapat ditulis sebagai berikut: m

n

z = ∑∑ cij xij

Minimumkan:

i =1 j =1 n

∑x

Berdasarkan pembatas :

ij

≤ ai , i = 1, 2,......, m

ij

≤ b j , i = 1, 2,......, n

j =1 n

∑x j =1

xij > 0 untuk seluruh i dan j Sebagai ilustrasi, jika ada 2 buah sumber dan 3 tujuan (m=2,n=3) c11; x11

Denver c13; x13

LA

c12; x12 Detroit

c21;x21 c22;x22 Miami

N. Orland

c23;x23

Adapun datanya adalah sebagai berikut: Sumber

Denver

Miami

Los Angeles

80

215

Detroit

100

108

New Orland

102

68

Tujuan

Permasalahannya adalah bagaimana mengalokasi sumber ketujuan dengan ongkos transportasi yang seminim mungkin. Langkah pertama yang harus dilakukan adalah melakukan pengecekan apakah total supply = total demand, kalau ya berarti model taransportasi ini merupakan model transportasi yang balance (seimbang). Permasalahan ini dapat kita selesaikan dengan LP dengan model matematis berikut: Minimize z = 80x11 + 215x12 + 100x21 + 108x22 + 102x31 + 68x32 Dengan constraint: x11 + x12

= 1000 + x21 + x22 + x21

x11 + x12

+ x22

= 1500 + x31 + x32

= 1200

+ x31

=2300 + x32

=1400

xij ≥ 0, for all i and j

Modul Praktikum Penelitian Operasional –Transportasi

10

Laboratorium Komputer V Jurusan Teknik Industri ISTA

Model matematis persamaan transportasi di atas dapat di tampilkan dengan lebih sederhana dalam bentuk tabel trasnportasi yang dapat dilihat pada Tabel 5 berikut: Tabel 5. Model transportasi seimbang Denver (1)

Miami (2)

80

215

Los Angeles (1) x12

x11 100 Detroit

108

(2) x21

x22 102

68

New Orleans (3) x31

x32

Permasalahan ini dapat diselesaikan dengan teknik transportasi. Adapun pemecahannya akan dibahas pada bagian D.2 berikut. D.2 Metode Pemecahan dengan Teknik Transportasi Langkah-langkah dasar dari teknik transportasi adalah: Langkah 1

:

Tentukan pemecahan awal yang layak

Langkah 2

:

Tentukan variabel masuk dari variabel-variabel nondasar. Jika semua variabel masuk memenuhi kondisi optimalitas (dari metode simpleks), berhenti; jika tidak, lanjutkan ke langkah 3

Langkah 3

:

Tentukan variabel keluar (dengan menggunakan kondisi kelayakan) dari variabelvariabel dalam pemecahan dasar saat ini; lalu temukan pemecahan dasar baru. Kembali ke langkah 2.

Perhatikan contoh soal pada Tabel 6 berikut: Tabel 6. Contoh permasalahan transportasi Tujuan Sumber

1

2 10

1 x11

0 x12

12

2

0

3 x31

15

11

15

x14 9

x23 14

x32 5

20

7

Penawaran

4

x13

x22

x21

Permintaan

3

20

25

x24 16

x33 15

18

5

x34 10

A. Penentuan Pemecahan Awal Untuk menentukan pemecahan awal yang layak dapat dilakukan dengan beberapa metode, yaitu: 1. Northwest-corner rule (metode sudut barat laut) 2. Least cost (biaya terendah) 3. Pendekatan Vogel namun untuk menentukan pemecahan awal pada Tabel 6 digunakan Northwest-corner rule (metode sudut barat laut) dan pembahasannya ada pada bagian berikut ini. Modul Praktikum Penelitian Operasional –Transportasi

11

Laboratorium Komputer V Jurusan Teknik Industri ISTA

Metode sudut barat laut memulai dengan mengalokasikan jumlah maksimum yang dapat diijinkan oleh penawaran dan permintaan ke variabel x11 (variabel yang berada di sudut barat laut dari tabel). Kolom (baris) yang sudah dipenuhi lalu disilang, yang menunjukkan bahwa variabel sisanya dalam kolom(baris) yang disilang itu adalah sama dengan nol. Jika sebuah kolom dan sebuah baris dipenuhi secara bersamaan, hanya satu (salah satunya) yang disilang. Kondisi ini menjamin penentuan variabel dasar nol, jika ada, secara otomatis. Untuk lebih jelasnya dapat dilihat pada Tabel 7 berikut: Tabel 7. Pemecahan dasar awal

1

1

2

5

10

2

5

3

4

15

3 5

15

15

15

10

5

25

20

5

5

5

10

5

5

Pemecahan awal dasar yang dihasilkan diberikan dalam Tabel 7 Variabel dasarnya adalah x11=5, x12=10, x22=5, x23=15, x24=5 dan x34=5. Variabel sisa adalah nondasar ditingkat nol. Biaya transportasi dari pemecahan awal dasar ini adalah: 5x10 + 10x0 + 5x7 + 15x9 + 5x20 + 5x18 = $410 Pemecahan awal dalam Tabel 7 mencakup jumlah variabel dasar seperti seharusnya, yaitu, m+n-1=6 B. Penentuan Variabel Masuk (Metode Pengali) Variabel masuk ditentukan dengan menggunakan kondisi optimalitas dari metode simpleks. Dalam metode pengali kita mengaitkan pengali ui dan vj dengan baris i dan kolom j dari tabel transportasi. Untuk setiap variabel dasar xij dalam pemecahan saat ini, pengali ui dan vj harus memenuhi persamaan berikut ini: ui +vj =cij, untuk setiap variabel dasar xij Persamaan ini menghasilkan m+n-1 persamaan (karena hanya terdapat m+n-1 variabel dasar) dengan m+n pengali yang tidak diketahui. Nilai-nilai pengali dapat ditentukan dari persamaan ini dengan memberikan nilai sembarang pada salah satu pengali (biasanya ui ditetapkan sama dengan nol) dan lalu memecahkan m+n-1 persamaan dengan m+n-1 pengali yang tidak diketahui. Setelah hal ini dilakukan, evaluasi terhadap setiap variabel non dasar xpq diketahui: c pq = u p + v q − c pq , untuk setiap variabel nondasar xpq. Variabel dengan c pq yang paling positif lalu dipilih sebagai variabel masuk. Jika kita menerapkan prosedur ini pada variabel-variabel non dasar dalam Tabel 7 (pemecahan awal dasar), persamaan yang berkaitan dengan variabel dasar diketahui: x11: u1 + v1 = c11 = 10 x12: u1 + v2 = c12 = 0 x22: u2 + v2 = c22 = 7 x23: u2 + v3 = c23 = 9 x24: u2 + v4 = c24 = 20 x34: u3 + v4 = c34 = 18 Modul Praktikum Penelitian Operasional –Transportasi

12

Laboratorium Komputer V Jurusan Teknik Industri ISTA

Dengan membiarkan u1 = 0, nilai pengali secara berturut-turut ditentukan sebagai v1=10, v2=0, u2=7, v3=2, v4=13, dan u3=5. Jadi evaluasi variabel nondasar diketahui sebagai berikut:

x13 : c13 = u1 + v3 − c13 = 0 + 2 − 20 = −18 x14 : c14 = u1 + v 4 − c14 = 0 + 13 − 11 = 2 x 21 : c 21 = u 2 + v1 − c 21 = 7 + 10 − 12 = 5

x31 : c31 = u 3 + v1 − c31 = 5 + 10 − 0 = 15 ⊕ x32 : c32 = u 3 + v 2 − c32 = 5 + 0 − 14 = −9 x33 : c33 = u 3 + v3 − c33 = 5 + 2 − 16 = −9 Karena x31 memiliki c pq yang paling positif, variabel ini dipilih sebagai variabel masuk. C. Menentukan variabel keluar (konstuksi loop) Untuk menentukan rasio minimum, kita mengembangkan loop tertutup untuk variabel masuk saat ini (x31). Loop berawal dan berakhir di variabel non dasar yang ditunjukkan. Untuk lebih jelasnya dapat dilihat pada Tabel 8 berikut: Tabel 8. Menentukan variabel keluar

⊕

⊕

⊕

Variabel keluar dipilih dari variabel-variabel sudut dari loop ini yang akan menurun ketika variabel x31 meningkat. Ini ditunjukkan dalam Tabel 8 dengan variabel dalam kotak-kotak yang diberi tanda negatif

. Dari Tabel 8, x22 dan x34 adalah variabel yang akan menurun ketika x31 meningkat.

Variabel yang memiliki nilai terkecil kemudian dipilih sebagai variabel keluar, karena variabel itu akan menjadi variabel pertama yang mencapai nilai nol dan setiap penurunan lebih lanjut akan menyebabkan nilainya menjadi negatif. Setelah menentukan variabel yang keluar dari variabel basis, selanjutnya kembali ke langkah 2 menentukan entering variabel. Adapun langkahnya dapat dilihat pada Tabel 9 Tabel 9. Menentukan variabel masuk

⊕

⊕

Modul Praktikum Penelitian Operasional –Transportasi

⊕

13

Laboratorium Komputer V Jurusan Teknik Industri ISTA

Tabel 9 memperlihatkan pemecahan dasar baru dimana x21 masuk dan x11 keluar. Kemudian lakukan langkah berikutnya, nilai ui, vj dan c pq dihitung kembali dan hasilnya dapat dilihat pada Tabel 10 Tabel 10. Konstruksi loop berikutnya

⊕

⊕

Dengan melakukan perubahan pada Tabel 10, kita memperoleh pemecahan baru dalam Tabel 11 Karena semua c pq dalam Tabel 10 tidak positif maka pemecahan optimum telah dicapai. Tabel 11. Solusi optimal

D.3 Pencarian Solusi Menggunakan WinQSB 1. Buka program WinQSB dan pilih menu network modeling. 2. Buka file|new problem sampai muncul kotak dialog pada Gambar 7 berikut:

Gambar 7. Kotak dialog problem specification

3. Kemudian isi data sesuai Gambar 7 dan klik OK 4. Kemudian akan mucul tabel penginputan data seperti pada Gambar 8 dan ketikkan data yang telah didapatkan pada tabel tersebut (lihat Gambar 8)

Modul Praktikum Penelitian Operasional –Transportasi

14

Laboratorium Komputer V Jurusan Teknik Industri ISTA

Gambar 8. Tabel peng-input-an data

5. Setelah penginputan data selesai klik solve and analize|solve the problem sehingga akan muncul solusi yang diperlihatkan oleh Gambar 9

Gambar 9. Solusi optimal

Pada Gambar 9 dapat dilihat bahwa solusi optimal dari permasalahan transportasi di atas adalah: 1. sumber 1 mengirimkan ke tujuan 3 sebanyak 5 unit dengan ongkos kirim 0. 2. sumber 2 mengirimkan ke tujuan 1 dan 2 sebanyak 5 dan 10 unit dengan total ongkos transportasi masing-masing tujuan 0 dan 70. 3. sumber 3 mengirimkan ke tujuan 2 sebanyak 15 unit dengan total ongkos transportasi 135. 4. sumber 4 mengirimkan ke tujuan 1 sebanyak 10 unit dengan total ongkos transportasi 110 5. adapun total ongkos keseluruhan adalah $315

Modul Praktikum Penelitian Operasional –Transportasi

15