BAB V PROGRAMA LINIER : MODEL TRANSPORTASI

Programa Linier : Model Transportasi

BAB V PROGRAMA LINIER : MODEL TRANSPORTASI

Model transportasi berkaitan dengan penentuan rencana berbiaya rendah untuk mengirimkan satu barang dari sejumlah sumber (misalnya, pabrik) ke sejumlah tujuan (misalnya, gudang). Model ini dapat diperluas secara langsung untuk mencakup situasi-situasi praktis dalam bidang pengendalian mutu, penjadwalan dan penugasan kerja, di antara bidangbidang lainnya. Model transportasi pada dasarnya merupakan sebuah programa linier yang dipecahkan oleh metode simpleks biasa. Tetapi, strukturnya yang khusus memungkinkan pengembangan sebuah prosedur pemecahan, yang disebut teknik trasportasi, yang lebih efisien dalam hal perhitungan. Ciri-ciri khusus persoalan 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 sumber ke suatu tujuan, besarnya tertentu.

5.1 Definisi dan Aplikasi Model Transportasi Dalam arti sederhana, model transportasi berusaha menentukan sebuah rencana transportasi sebuah barang dari sejumlah sumber ke sejumlah tujuan. Data dalam model ini mencakup : 1. Tingkat penawaran di setiap sumber dan sejumlah permintaan di setiap tujuan. 2. Biaya transportasi per unit barang dari setiap sumber ke setiap tujuan.

1


Tujuan dari model ini adalah menentukan jumlah yang harus dikirimkan dari setiap sumber ke setiap tujuan sedemikian rupa sehingga biaya transportasi total diminimumkan. Asumsi dasar dari model ini ialah bahwa biaya transportasi di sebuah rute tertentu adalah proporsional secara langsung dengan jumlah unit yang dikirimkan. Gambar 5.1 memperlihatkan sebuah model transportasi dari sebuah jaringan dengan m sumber dan n tujuan. Sebuah sumber atau tujuan diwakili dengan sebuh node. Busur yang menghubungkan sebuah sumber dan sebuah tujuan mewakili rute pengiriman barang tersebut. Jumlah penawaran di sumber i adalah ai dan permintaan di tujuan j adalah bi. Biaya unit transportasi antara sumber i dan tujuan j adalah cij.

Sumber

Tujuan c11 : x11

Unit penawaran

a1

1

1

b1

a2

2

2

b2

.

.

. . m

. . n

a1

cmn : xmn

Unit permintaan

bn

Gambar 5.1 Model Transportasi dari Sebuah Jaringan

Anggaplah xij mewakili jumlah barang yang dikirimkan dari sumber i ke tujuan j ; maka model programa linier yang mewakili masalah transportasi adalah sebagai berikut :

m

n

Me min imumkan z   cij xij i 1 j 1

2


Dengan batasan : n

x j 1

ij

m

x i 1

ij

 ai ,

i 1, 2, ...., m

 bj ,

j 1, 2, ...., n

xij  0,

untuk semua i dan j

Kelompok batasan pertama menetapkan bahwa jumlah pengiriman dari sebuah sumber tidak dapat melebihi penawarannya ; demikian pula, kelompok batasan kedua mengharuskan bahwa jumlah pengiriman ke sebuah tujuan harus memenuhi permintaannya. Model diatas menyiratkan bahwa penawaran total setidaknya sama dengan permintaan total sama dengan permintaan total

(



m

i



n j



m

i

1 ai harus

 1 b j . Ketika penawaran total

1 ai =



n j

 1 b j ), formulasi yang

dihasilkan disebut model transportasi berimbang (balanced transportation model). Model ini berbeda dengan model diatas hanya dengan fakta bahwa semua batasan adalah persamaan yaitu : n

x j 1

ij

m

x i 1

Dalam

ij

kehidupan

 ai ,

i 1, 2, ...., m

 bj

j 1, 2, ...., n

nyata

tidak

selalu

dapat

dipastikan

bahwa

penawaran sama dengan permintaan atau melebihinya. Tetapi, sebuah model transportasi

dapat

selalu

berimbang.

Pengimbangan

ini,

disamping

kegunaannya dalam pemodelan situasi praktis tertentu, adalah penting untuk pengembangan sebuah metode pemecahan yang sepenuhnya memanfaatkan struktur khusus dari model tranportasi ini .

3


5.2 Pemecahan Masalah Transportasi Untuk menyelesaikan persoalan transportasi, harus dilakukan langkahlangkah sebagai berikut : 1. Tentukan pemecahan awal yang layak. 2. Tentukan variabel masuk (entering variabel) dari variabel-variabel nonbasis. Bila semua variabel sudah memenuhi kondisi optimum, STOP. Bila belum, lanjutkan langkah 3. 3. Tentukan variabel keluar (leaving variabel) di antara variabel-variabe basis yang ada, kemudian hitung solusi yang baru. Kembali ke langkah 2.

Langkah 1 : Menentukan solusi fisibel basis awal Ada tiga metode yang biasa digunakan untuk menentukan solusi fisibel basis awal yaitu :

5.2.1 Metode pojok kiri atas-pojok kanan bawah (northwest corner rule / NCR) Prosedur yang digunakan dalam menyelesaikan persoalan transportasi dengan metode NCR adalah sebagai berikut : Mulai dari pojok kiri atas, alokasikan sebesar x 11 = min (a1 , b1 ). Artinya : jika b1  a1 maka x11 = b1 ; jika b1  a1, maka x11 = a1 . Kalau x11 = b1, maka selanjutnya yang mendapat giliran untuk dialokasikan adalah x12 sebesar min (a1 - b1, b2) ; kalau x11 = a1 (atau b1  a1), maka selanjutnya yang mendapat giliran untuk dialokasikan adalah x21 sebesar min (b1 - a1, a2). Demikian seterusnya. Contoh :

4


Tabel 5.2.1.1 Contoh Pemakaian Metode NCR Tujuan 1 1

2 10

5 Sumber

2

3 0

20

15 7

5 0

9 15

14 15

20 5

16

bj 5

aij 11

10 12

3

4

15

25 18

5 10

5

a1 = 15 ; b1 = 5  x11 = min (15, 5) = 5 a1 - b1 = 10 ; b2 = 15  x12 = min (10, 15) = 10 Langkah selanjutnya ialah mengisi b2 sampai penuh dengan mengalokasikan sebesar 5 pada x22 , yaitu jumlah kekurangan yang terjadi dalam pemenuhan kebutuhan pada b2. Dengan melanjutkan prosedur diatas, maka akan diperoleh berturut-turut : x23 = 15, x24 = 5, dan x34 = 5, yang bersama-sama dengan x11 , x12 , dan x22 membentuk solusi fisibel basis awal. Sehingga biaya trasportasi totalnya adalah : 5 x 10 + 10 x 0 + 5 x 7 + 15 x 9 + 5 x 20 + 5 x 18 = 410

5.2.2 Metode biaya terendah (least cost) Prinsip cara ini adalah pemberian prioritas pengalokasian pada tempat yang mempunyai satuan ongkos terkecil. Dengan mengambil contoh diatas, kita lihat c12 = c31 = 0 adalah ongkos terkecil dari keseluruhan tabel. Maka x 12 dan x31 mendapat prioritas pengalokasian pertama kali. Jumlah unit yang dialokasikan masing-masing adalah x12 = min (a1 , b2) = 15 dan x31 = min (a3 , b1) = 5. Selanjutnya lihat ongkos terkecil berikutnya, yaitu c 22 = 7. Tetapi, karena tujuan kedua (b2) telah terisi penuh, maka lihat ongkos terkecil

5


berikutnya, diperoleh c23 = 9. Alokasikan x23 sebesar min (a2 , b3 ) = min (25, 15) = 15. Dengan menjalankan prosedur diatas, diperoleh x24 = 10. Maka x12 , x31 , x23 dan x24 bersama-sama membentuk solusi fisibel basis awal. Tabel 5.2.1.2 Contoh Pemakaian Metode Least Cost Tujuan 1 1

2 10

0 Sumber

3 0

4 20

15

2

12

7

3

0

14

9 15

5 5

11 0

15 20

10 16

25 18 5

15

15

10

Biaya total = 0 x 10 + 15 x 0 + 0 x 11 + 15 x 9 + 10 x 20 + 5 x 0 = 335. Hasil yang dicapai pada metode least cost ternyata lebih baik (lebih rendah) daripada yang diperoleh dengan metode NCR.

5.2.3 Metode

Pendekatan

Vogel

(Vogel’s

Approximation

Method /VAM) Cara ini merupakan cara terbaik dibandingkan dengan kedua cara diatas. Langkah-langkah pengerjaannya adalah : 1. Hitung penalty untuk tiap kolom dan baris dengan jalan mengurangkan elemen ongkos terkecil dari yang kedua terkecil. 2. Selidiki kolom/baris dengan penalty terbesar. Alokasikan sebanyak mungkin pada variabel dengan ongkos terkecil, sesuaikan supply dengan demand, kemudian tandai kolom atau baris yang sudah terpenuhi. Kalau ada 2 buah baris/kolom yang terpenuhi secara simultan, pilih salah satu untuk ditandai, sehingga supply/demand pada baris/kolom yang tidak terpilih adalah nol. Setiap baris/kolom dengan supply/demand sama dengan nol, tidak akan terbawa lagi pada perhitungan penalty berikutnya. 6


3. a. Bila tinggal 1 kolom/baris yang belum ditandai, STOP. b. Bila tinggal 1 kolom/baris dengan supply/demand positip yang belum ditandai, tentukan variabel basis pada kolom/baris dengan cara ongkos terkecil (least cost). c. Bila semua baris dan kolom yang belum ditandai mempunyai supply dan demand sama dengan nol, tentukan variabel-variabel basis yang berharga nol dengan cara ongkos terkecil. Kemudian STOP. d. Jika 3a, b dan c tidak terjadi, hitung kembali penalty untuk baris/kolom yang belum ditandai. Kembali ke nomor 2.

Contoh :

Penalty Baris 1 1

2 10

3 0

4 20

11

2

12

7

9

20

3

0

14

16

18

15

10

25

2

5 14* Penalty Kolom

5

15

15

10

10

7

7

7

Karena baris ketiga memiliki penalty terbesar (= 14) dan karena c31 = 0 merupakan ongkos terkecil di dalam barisnya, maka alokasikan x31 = 5. Dengan demikian, baris 3 dan kolom 1 sudah terpenuhi secara simultan. Dalam hal ini kita bisa memilih baris 3 atau kolom 1 yang akan ditandai. Misalkan dipilih kolom 1 untuk ditandai, maka sisa supply untuk baris 3 menjadi 0. Tabel baru menjadi :

7


Penalty Baris 1 1

2 10

3 0

4 20

11 15 11*

2

12

7

9

20

3

0

14

16

18

Penalty Kolom

5 0

15

15

10

-

7

11

9

25

2

0

-

Selanjutnya kita ulangi menghitung penalty. Kita lihat bahwa baris 1 dan kolom 3 mempunyai penalty yang sama (= 11) sehingga kembali kita dapat memilih salah satu untuk ditandai. Misalkan dipilih kolom 3 untuk ditandai, maka alokasikan x23 = 15. Supply untuk baris 2 sekarang menjadi 10.

Penalty Baris 1 1

2 10

3 0

4 20

11 15

2

12

7

9

20

16

18

15 3

Penalty Kolom

0

14

11

10 13*

5 0

0 15

0

10

-

7

0

9

-

Dengan menghitung penalty yang baru, diperoleh penalty terbesar untuk baris 2 (= 13) sehingga alokasikan x22 = 10. Kemudian tandai baris 2.

1

2

3

4

1

10

0

20

11

2

12

7

9

20

3

0

16

18

15 10 5 0

15 14

0 0

5

0

10

8


Supply yang masih tersedia adalah 15 (baris 1), sedangkan demand yang belum terpenuhi adalah kolom 2 sebanyak 5 dan kolom 4 sebanyak 10. Karena tidak ada pilihan lain, maka alokasikan x12 = 5 dan x14 = 10. Pengisian tabel selesai dengan solusi fisibel basis awal : x12 = 5, x14 = 10, x22 = 10, x23 = 15 dan x31 = 5. Dari hasil perhitungan diatas, maka tabel optimumnya adalah :

1 1

2 10

3 0

4 20

5 2

12

3

0

7 10

5 5

11 10

15

9

20

16

18

15 14

25 5

15

15

10

Biaya total = 5 x 0 + 10 x 11 + 10 x 7 + 15 x 9 + 5 x 0 = 315 Langkah 2 dan 3 : Menentukan entering variabel dan leaving variabel Menentukan entering dan leaving variabel adalah tahap berikutnya dari teknik pemecahan persoalan transportasi, setelah solusi fisibel basis awal diperoleh. Ada dua cara yang bisa digunakan dalam menentukan entering dan leaving variable ini, yaitu dengan menggunakan metode stepping stone atau metode multipliers.

5.2.4 Metode Stepping Stone Untuk menentukan entering dan leaving variable ini, terlebih dahulu haris dibuat suatu loop tertutup bagi setiap variabel nonbasis. Loop tersebut berawal dan berakhir pada variabel nonbasis tadi, di mana tiap sudut loop haruslah merupakan titik-titik yang ditempati oleh variabel-variabel basis dalam tabel trasportasi. Sebagai contoh, kita lihat kembali tabel terakhir yang diperoleh dari cara NCR, Tabel 5.2.4.1 berikut ini :

9


Tabel 5.2.4.1 Solusi fisibel Basis Awal dengan Metode NCR 1

2

1

3

10 5

20

11

7

9

20

10

2

12

3

0

15

5

5

4

0

15

5

14 15

16

25 18

5 10

15

5

Dari tabel diatas diperoleh variabel basis awal x11 , x12 , x22 , x23 , x24 , dan x34 , masing-masing dengan harga 5, 10, 5, 15, 5, dan 5. Sampai disini diperoleh solusi awal z = (5) (10) + (10) (0) + (5) (7) + (15) (9) + (5) (20) + (5) (18) = 410 Dalam hal ini loop digunakan untuk memeriksa apakah bisa diperoleh penurunan ongkos (z) jika variabel nonbasis dimasukkan menjadi variabel basis. Dengan cara memeriksa semua variabel nonbasis yang terdapat dalam suatu iterasi itulah kita dapat menentukan entering variabel. Sebagai contoh, kita kembali pada Tabel 5.2.4.1. Misalkan kita akan memeriksa apakah variabel nonbasis x21 dapat dimasukkan menjadi variabel basis sehingga ongkos totalnya berkurang. Untuk itu alokasikan sebanyak 1 satuan barang kepada x21 (atau x21 = 1). Mengingat bahwa kuantitas barang pada masing-masing baris atau kolom harus tetap, maka perubahan harga x21 dari 0 menjadi 1 mengakibatkan perubahan pada harga variabel basis x 11 (yang berada pada kolom 1) sebesar 1 sehingga x 11 menjadi = 4. Demikian pula halnya dengan variabel yang berada pada baris 2 sehingga x22 berubah menjadi 4. Perubahan yang terjadi pada z adalah : z = (4) (10) + (11) (0) + (1) (12) + (4) (7) + (15) (9) + (5) (20) + (5) (18) = 405 Dibandingkan dengan solusi sebelumnya (z = 410), maka jelaslah bahwa

x21

dapat

dimasukkan

sebagai

entering

variabel,

dimana

pengalokasian 1 unit barang kepada x21 akan mengakibatkan penurunan ongkos sebesar 5 (lihat Tabel 5.2.4.2).

10


Tabel 5.2.4.2 Pemasukan Variabel Nonbasis x21 Menjadi Variabel Basis 1

2

1

3

10 4

4

0

20

11

7

9

20

11

2

15

12 1

4

3

15

0 5

14 15

5 16

25 18

5 10

15

5

Untuk memudahkan perhitungan, buatlah sebuah loop tertutup untuk masingmasing pengecekan. Misalnya untuk variabel x21 tadi (lihat Tabel 5.2.4.3). Kalau kita pandang 1 unit pengalokasian kepada x21 berasal dari pemindahan 1 unit pada kolom 2 ke kolom 1, maka untuk menjaga agar kuantitasl total pada kolom ke 2 tidak berubah dan kuantitas pada kolom 1 tidak berlebih, haruslah dari kolom 1 dipindahkan ke kolom 2 sebesar 1 unit pula. Misalkan yang berubah itu adalah x11 menjadi 4, dan 1 unit dipindahkan dari x11 kepada x12 sehingga x12 menjadi 11. Dengan cara yang sama x 21 menjadi 1 dan x22 menjadi 4 sebagai perimbangannya (lihat Tabel 5.2.4.2). Tabel 5.2. 4.3 Loop tertutup untuk Variabel Nonbasis x 21 1

2

1

5

10

2

x21

5

3

3

4

15

5

5

Akibat “perpindahan antar kolom” ini terhadap ongkos total hanyalah berkisar pada elemen-elemen ongkos tempat dilakukannya perpindahan tersebut, yaitu c11 , c12 , c21 , dan c22. Dalam hal ini, akibat perpindahan dari

11


x11 kepada x12 sebesar 1 unit, maka terjadi penurunan ongkos sebesar c11 – c12. Begitu pula yang terjadi pada perpindahan dari x22 kepada x21 , penurunan ongkosnya adalah sebesar c22 – c21. Kalau penurunan ongkos ini diberi tanda minus (-) dan pertambahan ongkos diberi tanda plus (+), maka perubahan total ongkos yang terjadi, bila dialokasikan sebanyak 1 unit terhadap variabel nonbasis x21 , adalah : [(c11 – c12) + (c22 – c21)] = - [(10 – 0) + (7 – 12)] =-5 Perubahan harga variabel-variabel basis dan nonbasis ini tentu saja dapat pula dipandang sebagai “perpindahan antarbasis” dan tidak akan mempengaruhi

hasil

perhitungan.

Bahkan

ada

kalanya

dibutuhkan

“perpindahan antarkolom” sekaligus “perpindahan antar baris”, misalnya untuk memeriksa x31. Jika cij = perubahan ongkos akibat pengalokasian 1 unit produk ke variabel nonbasis xij , maka dengan cara yang sama akan diperoleh berturut-turut : c13 = 18, c14 = - 2, c31 = - 15, c32 = 9, dan c33 = 9, sehingga diperoleh Tabel 5.2.4.4. Tabel 5.2.4.4 Penambahan dan Penurunan Ongkos Transportasi per unit untuk masing-masing Variabel Nonbasis 1

2

1

3

10 5

0

4 20

(18) 2

11

10 12

7 5

(-2) 9

15

20 5

(-5) 3

0

14

16

18 5

(-15)

(9)

(9)

Selanjutnya dipilih variabel nonbasis yang akan menyebabkan penurunan ongkos terbesar sebagai entering variabel. Dari iterasi diatas dipilih x 31 sebagai entering variable karena memberikan penurunan ongkos yang terbesar yaitu sebanyak 15 satuan ongkos per unit. Dengan demikian, kita

12


dapat membuat sebuah loop yang berawal dan berakhir pada variabel x 31 (lihat Tabel 5.2.4.5) Tabel 5.2.4.5 Loop dari Variabel x31 1

2

1

3

10 5

0 (+) 7

12 5

3

11

10

(-) 2

4 20

0

9 15

(-) 14

20 5 (+) 18

16

x31 (+)

5 (-)

Tanda (-) dan (-) menyatakan bahwa variabel yang bersangkutan (pada masing-masing kotak) akan bertambah atau berkurang besarnya sebagai akibat perpindahan kolom dan perpindahan baris. Leaving variable dipilih dari variabel-variabel sudut loop yang bertanda (-). Pada contoh diatas, dimana x telah terpilih sebagai entering variable, calon-calon leaving variable-nya adalah x11 , x22 , dan x34. Dari calon-calon ini, pilihlah salah satu yang nilainya paling kecil. Pada contoh di atas kebetulan ketiganya bernilai sama (= 5) sehingga kita bisa memilih salah satu untuk dijadikan leaving variable. Misalkan x34 dipilih sebagai leaving variable, maka nilai x31 naik 5 dan nilai-nilai variabel basis yang di sudut loop juga berubah (bertambah atau berkurang 5 sesuai dengan tanda (+) atau (-) ). Tabel solusi baru ini adalah seperti pada Tabel 5.2.4.6 dengan ongkos transportasi sebesar : (0 x 10) + (15 x 0) + (0 x 7) + (15 x 9) + (10 x 20) + (5 x 0) = 335

13


Tabel 5.2.4.6 Tabel solusi baru setelah x31 terpilih sebagai entering variable dan x34 menjadi leaving variable 1

2

1

3

10 0

2

20

11

15 12

7

9

0 3

4

0

15

0

14

20 10

16

18

5

Bandingkan

dengan

solusi

awal

pada

Tabel

5.2.4.1

yang

ongkos

transportasinya = 410. Selisih ongkos transportasi (410 – 335 = 75) sama dengan hasil perkalian antara :

Jumlah unit yang ditambahkan pada x 31 (5)

X X

penurunan ongkos per unit (15)

Perhatikan : Angka 0 pada x11 dan x22 adalah variabel basis yang berharga 0. Jadi, tidak boleh dihilangkan karena ia tidak sama dengan kotak-kotak lain yang tidak ada angkanya (variabel nonbasis). Sampai disini kita masih harus memeriksa, barangkali nilai fungsi tujuan masih bisa diperbaiki. Untuk itu lakukanlah kembali langkah-langkah yang sudah kita kerjakan, dengan menggunakan Tabel 5.2.4.6 sebagai solusi awal (pengganti Tabel 5.2.4.1). Kita dapatkan :

Variabel nonbasis x13 x14 X21 X32 X33 x34

Perubahan ongkos per unit c13 = +18 c14 = - 2 c21 = - 5 c32 = +24 c33 = +24 c34 = +15

14


Dengan demikian kita memilih x21 sebagai entering variable. Tabel 5.2.4.7 1

2

1

3

10 0

0 (+) 7

12 0

x21

9 15

(-) 14

(+) 3

11

15

(-) 2

4 20

0

20 10

16

18

5

Tabel 5.2.4.8 1

2

1

10

3 0

4 20

15 (-) 2

12 0

3

x14 7

0 (+) 0

11

15 14

(+) 20

9 10 16

(-) 18

5

Pada loop yang berasal dan berakhir pada x 21 ini, leaving variable-nya ada dua, yaitu x11 dan x22. Karena keduanya berharga 0, kita bisa memilih salah satu untuk dijadikan leaving variablenya. Misalkan x 11 adalah leaving variable, maka x21 = 0 dengan ongkos transportasi tetap 335. Karena itu, kita coba membuat loop dari variabel nonbasis yang lain, yang juga dapat menurunkan ongkos transportasi per unit (yaitu x14). Kita dapatkan : c11 = +5; c32 = +19; c13 = +18; c33 = +19; c34 = +10; c14 = - 2. Dari Tabel 5.2.4.8 terlihat bahwa leaving variable adalah x24 sehingga x14 = 10; x22 = 10; dan x12 = 5. Solusi optimalnya adalah :

15


Tabel 5.2.4.9 Solusi Optimal 1

2

1

10

2

12

3

4

0

20

11

7

9

20

16

18

5 0

10

10

3

0

15 14

5 5

15 25 5

15

15

10

Dengan ongkos transportasi sebesar : (5 x 0) + (10 x 11) + ( 0 x 12) + (10 x 7) + (15 x 9) + (5 x 0) = 315

5.2.5 Metode Multiplier Cara ini iterasinya sama seperti stepping stone. Perbedaan utama terjadi pada cara pengevaluasian variabel nonbasis, atau penentuan penurunan ongkos transpor

per

unit

untuk

tiap variabel.

Cara

ini

dikembangkan berdasarkan teori dualitas. Untuk tiap basis i dari tabel trasformasi dikenal suatu multiplier ui , dan untuk kolom j disebut multiplier vj sehingga untuk tiap variabel basis xij didapat persamaan : ui + vj + cij Dari persamaan di atas kita dapat menghitung berapa penurunan ongkos transportasi per unit untuk tiap variabel nonbasis x ij sebagai berikut : cij = xij – ui - vj Langkah berikutnya adalah seperti iterasi yang dilakukan oleh metode stepping stone. Sebagai contoh kita lihat lagi solusi fisibel basis awal dari Tabel 5.2.4.1 vj v1 ui u1

v2 10

5

0

20

11

7

9

20

15

5 0

u3 5

v4

10 12

u2

v3

15 14

15

5 16

15

25 18

5 10

5

16


Basis awal : 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 Dengan menentukan ui = 0, maka harga-harga multiplier yang lain dapat dicari sebagai berikut : u1 + v1 = 10  v1 = 10 u1 + v2 = 0  v2 = 0 u2 + v2 = 7  u2 = 7 u2 + v3 = 9  v3 = 2 u2 + v4 = 20  v4 = 13 u3 + v4 = 18  u3 = 5 vj v1= 10 ui u1 = 0

v2= 0 10



0 

12

u2 = 7

-15 5

20

7

0

11 -2

9 

14 +9 15

v4= 13

+18



-5 u3 = 5

v3= 2

20 

16 +9 15

15 25 18

 10

5

Untuk menentukan entering variabel : c21 = c21 – v1 – u2 = - 5 c31 = c31 – v3 – v1 = - 15 c13 = c13 – u1 – v3 = 18 c14 = c14 – u1 – v4 = - 2 c32 = c32 – u3 – v2 =

9

c33 = c33 – u3 – v3 =

9

17


Entering variabel adalah x13 (karena memberikan penurunan ongkos per unit yang terbesar). Selanjutnya iterasinya sama dengan metode stepping stone.

5.3 Model Penugasan (Assigment Model)

Model penugasan merupakan kasus khusus dari model transportasi, dimana sejumlah m sumber ditugaskan kepada sejumlah n tujuan (satu sumber untuk satu tujuan) sedemikian sehingga didapat ongkos total yang minimum. Biasanya yang dimaksud dengan sumber ialah pekerjaan (atau pekerja), sedangkan yang dimaksud dengan tujuan ialah mesin-mesin. Jadi, dalam hal ini, ada m pekerjaan yang ditugaskan pada n mesin, di mana apabila pekerjaan i ( i = 1, 2, …., m) ditugaskan kepada mesin j (j = 1, 2, … , n) akan muncul ongkos penugasan ci j. Karena satu pekerjaan ditugaskan hanya pada satu mesin, maka supply yang dapat digunakan pada setiap sumber adalah 1 (atau ai = 1, untuk seluruh i). Demikian pula halnya dengan mesin-mesin ; karena satu mesin hanya dapat menerima satu pekerjaan, maka demand dari setiap tujuan adalah 1 (atau bj = 1, untuk seluruh j). Jika ada suatu pekerjaan yang tidak dapat ditugaskan pada mesin tertentu, maka cij yang berkorespondensi dengannya dinyatakan dengan M, yang merupakan ongkos yang sangat tinggi. Penggambaran umum persoalan penugasan ini adalah sebagai berikut :

Tabel 5.3.1 Penggambaran Umum Persoalan Penugasan Mesin 1 2 … n 1 c11 c12 … c1n 1 Pekerjaan 2 c21 c22 … c2n 1 . . . . . . . . . . . . . . . m cm1 cm2 cmn 1 1 1 … 1

18


Sebelum model ini dapat dipecahkan dengan teknik trasportasi, terlebih dahulu persoalannya harus diseimbangkan dengan menambahkan pekerjaanpekerjaan atau mesin-mesin khayalan, bergantung pada apakah m  n atau m  n. Dengan demikian, diasumsikan bahwa m = n. Model penugasan dapat diekspresikan secara matematis sebagai berikut :

xij  0, jika pe ker jaan i tidak ditugaskan ke me sin j xij 1, jika pe ker jaan i ditugaskan ke me sin j Jadi model ini diketahui n

Minimumkan z   cij xij i 1 j 1

Dengan batasan n

x j 1

ij

n

x i 1

ij

1,

i 1, 2, ..., n

1,

j 1, 2, ..., n xij  0 atau 1

Suatu ciri khas persoalan penugasan ialah bahwa solusi optimum akan tetap sama bila suatu konstanta ditambahkan atau dikurangkan kepada baris atau kolom yang manapun dari matriks ongkosnya. Hal ini dapat dibuktikan sebagai berikut : Jika pi dan qj merupakan konstanta pengurang terhadap baris i dan kolom j, maka elemen ongkos yang baru adalah :

cij‟ = cij – pi - qj

19


Sehingga fungsi tujuan baru menjadi :

xij   cij  pi  q j  xij

z '   cij ' i

j

i

  cij xij   pi i

j

i

x

ij

j

j

 qj j

x

ij

i

Karena  xij   xij  1, maka z '  z  kons tan ta j

i

Hal ini menunjukkan bahwa meminimumkan z akan menghasilkan solusi yang sama dengan meminimumkan z‟. Suatu hal yang menarik ialah bahwa jika kita melakukan operasi pengurangan pi dan qj terhadap matriks ongkos akan diperoleh zero entries, yaitu elemen-elemen ongkos dalam matriks yang berharga nol, yang juga merupakan variabel-variabel yang menghasilkan solusi optimum bagi z‟ sehingga, berdasarkan pembuktian diatas, merupakan solusi optimal bagi z. Sebagai ilustrasi, perhatikanlah sebuah persoalan penugasan berikut ini:

Tabel 5.3.2 Model Persoalan Penugasan Mesin 1

2

3

5

7

9

14

10

12

15

13

16

1

1

Pekerjaan 2

1

3

1 1

1

1

20


Tabel 5.3.3 Solusi Awal Contoh Persoalan Penugasan Mesin 1 1

2

3

5

7

9

14

10

12

13

16

1

1

Pekerjaan 2

1

1

15 3 1

1 1

1

1

Pada tabel 5.3.3, elemen-elemen nol dibuat dengan mengurangkan elemen terkecil masing-masing baris (kolom) dari baris (kolom) yang bersangkutan. Dengan demikian, matriks cij„ yang baru adalah :

Tabel 5.3.4 Matriks cij„ (Matrisk Ongkos yang Baru) 1

1 0

2 2

3 4

p1 = 5

2

4

0

2

p2 = 10

3

2

0

3

p3 = 13

Matriks terakhir dapat dibuat untuk memperbanyak elemen matriks yang berharga nol dengan cara mengurangkan q3 = 2 dari kolom ketiga. Hasilnya adalah sebagai berikut :

Tabel 5.3.5 Solusi Akhir 1

1 0*

2 2

3 2

2

4

0

0*

3

2

0*

1

Segi empat pada tabel merupakan penugasan yang fisibel yang sekaligus optimum, yaitu (1, 1), (2, 3), dan (3,2 ) dengan ongkos penugasan sebesar 5 + 12 + 13 = 30. Perhatikan bahwa besarnya ongkos ini sama dengan p1 + p2 + p3 + q3 21


Penugasan yang fisibel seperti diatas tidak selalu dapat kita peroleh. Karena itu, diperlukan suatu aturan untuk mencapai solusi optimum yang akan dijelaskan melalui ilustrasi sebagai berikut : Perhatikan suatu persoalan penugasan yang digambarkan sebagai berikut : Tabel 5.3.6 Persoalan Penugasan 1

1 1

2 4

3 6

4 3

2

9

7

10

9

3

4

5

11

7

4

8

7

8

5

Dengan proses pengurangan seperti diatas diperoleh :

Tabel 5.3.7 Proses Pengurangan I 1

1 0

2 3

3 5

4 2

2

2

0

3

2

3

0

1

7

3

4

3

2

3

0

Tabel 5.3.8 Proses Pengurangan II 1

1 0

2 3

3 2

4 2

2

2

0

0

2

3

0

1

4

3

4

3

2

0

0

Dalam kasus ini penugasan yang fisibel terhadap elemen-elemen nol tidak mungkin diperoleh sehingga diperlukan prosedur sebagai berikut : 1. Tariklah garis pada semua baris dan kolom yang mengandung elemen nol dengan jumlah garis minimum, sedemikian sehingga tidak terdapat lagi nol pada matriks yang bersangkutan.

22


2. Tentukan di antara elemen-elemen yang tidak ikut tergaris, satu elemen dengan harga terkecil, kemudian kurangkan sebesar harga elemen ini kepada semua elemen yang tidak tergaris. 3. Tambahkan sebesar harga elemen tersebut (pada point 2) kepada semua elemen yang terletak pada perpotongan dua garis. 4. Aloksikan pekerjaan pada elemen-elemen nol tersebut. 5. Jika solusi optimum belum juga ditemukan, ulangi lagi langkah 1 sampai dengan 4 hingga dicapai penugasan yang fisibel. Kembali pada soal diatas, sebagai kelanjutan dari tabel 5.3.8 adalah :

Tabel 5.3.9 Modifikasi 1

1 0

2 3

3 2

4 2

2

2

0

0

2

3

0

1

4

3

4

3

2

0

0

Tabel 5.3.10 Solusi Optimum 1

1 0*

2 2

3 1

4 1

2

3

0

0*

2

3

0

0*

3

2

4

4

2

0

0*

Tabel memberikan penugasan yang optimum, yaitu (1, 1), (2, 3), (3, 2), dan (4, 4) dengan ongkos total sebesar 1 + 10 + 5 + 5 = 21

5.4

Model “Transshipment” Model transshipment adalah model trasportasi yang memungkinkan

dilakukannya pengiriman barang (komoditas) cara tidak langsung, di mana barang dari suatu sumber dapat berada pada sumber lain atau tujuan lain sebelum mencapai tujuan akhirnya. Jadi, pada model transshipment ini suatu

23


sumber sekaligus dapat berperan sebagai tujuan dan, sebaliknya, suatu tujuan dapat juga berperan sebagai sumber. Dalam model ini, setiap sumber maupun tujuan dipandang sebagai titik-titik potensial bagi demand maupun supply. Oleh karena itu, untuk menjamin bahwa titik potensial tersebut mampu menampung total barang di samping jumlah barang yang telah ada pada titik-titik tersebut, maka perlu ditambahkan kepada titik-titik itu kuantitas suplly dan demand-nya masingmasing sebesar B.

B

m

 ai 

i  1

n

b

j  1

j

Dengan demikian, apabila ada persoalan transportasi sebagai berikut :

T1

T2

T3

10

20

30

S1

100 20

50

40

S2

200 100

100

100

Maka persoalan transshipment-nya adalah : S1

S2

T1

T2

T3

S1

10

20

30

S2

20

50

40

100 + B 100 + B

T1 B

T2 B

T3 B B

B

100 + B

100 + B

100 + B

Model di atas baru lengkap apabila ongkos per unit pengangkut untuk barisbaris dan kolom-kolom yang lainnya telah ditetapkan. Dalam hal ini perlu diingat bahwa ongkos per unit pada elemen-elemen diagonal adalah nol. 24


Asumsikan bahwa seluruh ongkos per unitnya telah ditentukan, maka model transshipment selengkapnya adalah : S1 S1

S2 0

T1 80

T2 10

T3 20

30 400

S2

10

0

20

50

40 500

T1

20

30

0

40

10 300

T2

40

20

10

0

20 300

T3

60

70

80

20

0 300

300

300

400

400

400

Selanjutnya, persoalan di atas diselesaikan dengan menggunakan teknik transportasi seperti biasa, sehingga diperoleh solusi optimal sebagai berikut :

S1

S2

T1

T2

T3

S1 400

S2 500

T1 300

T2 300

T3 300 300

300

400

400

400

Elemen-elemen diagonal dari tabel diatas kita abaikan, karena secara fisik tidak mempunyai arti apa-apa. Solusi optimal diatas menyatakan bahwa : Sumber 2 (S2 mengirimkan seluruh supply-nya pada tujuan pertama (T1), di mana 100 unit disimpan untuk memenuhi demand pada tujuan 1 tersebut, dan sisanya, yaitu sebanyak 100 unit, kemudian dikirimkan

25


kepada tujuan 3 (T3) untuk memenuhi demand pada tujuan 3. Adapun demand pada tujuan 2 (T 2) dipenuhi langsung dari sumber 1 (S1).

LATIHAN SOAL 1. Jawablah setiap model transportasi berikut dengan menggunakan metode NCR, metode LC, dan metode VAM untuk memperoleh pemecahan awal. Bandingkan perhitungan tersebut. (a)

(b)

1

2

6

7

5

1

8

12

0

4

2

12

2

4

0

14

3

1

5

11

3

6

7

4

10

10

10

9

10

11

2. Cari pemecahan awal dalam masalah trasportasi berikut ini berdasarkan metode NCR, metode LC, dan metode VAM. Dapatkan pemecahan optimal dengan menggunakan pemecahan awal terbaik.

10

20

5

7

10

13

9

12

8

20

4

15

7

9

30

14

7

1

0

40

3

12

5

19

50

60

60

20

10

3. Jawablah masalah transportasi tidak seimbang berikut ini dengan menggunakan VAM untuk mencari pemecahan awal ; permintaan pada tujuan 1 harus dikirim dari sumber 4.

26


5

1

0

20

3

2

4

10

7

5

2

15

9

6

0

15

5

10

15

4. Pecahkan model-model penugasan berikut : (a)

(b)

3

8

2

10

3

3

9

2

3

7

8

7

2

9

7

6

1

5

6

6

6

4

2

7

5

9

4

7

10

3

8

4

2

3

5

2

5

4

2

1

9

10

6

9

10

9

6

2

4

6

5. Pertimbangkan masalah menugaskan empat operator ke empat mesin. Biaya penugasan diberikan dalam dollar. Operator 1 tidak dapat ditugaskan ke mesin 3. Demikian juga, operator 3 tidak dapat ditugaskan ke emsin 4. Cari penugasan optimal.

Mesin

Operator

1

2

3

4

1

5

5

-

2

2

7

4

2

3

3

9

3

5

-

4

7

2

6

7

6. Misalkan dalam soal No. 5 tersedia mesin ke lima. Biaya penugasan masing-masing (dalam dollar) kepada keempat operator adalah 2, 1, 2 , dan 8. Mesin yang baru menggantikan mesin yang ada jika penggantian dapat dibenarkan secara ekonomis. Rumuskan kembali masalah sebagai model penugasan dan cara pemecahan optimal. Secara khusus, apakah

27


ekonomis menggantikan salah satu dari mesin-mesin yang ada ? Jika ya, mesin yang mana ? 7. Sebuah perusahaan penerbangan regional dapat membeli bahan bakar jetnya dari tiga penjual. Untuk bulan mendatang perusahaan penerbangan ini membutuhkan pada tiap-tiap bandara dari ketiga bandara yang dilayani sebanyak 100.000 galon di bandara 1, 180.000 galon di bandara 2 dan 350.000 galon di bandara 3. Setiap penjual dapat memasukkan bahan bakar bagi tiap-tiap bandara dengan harga (dalam sen dollar per galon) yang diberikan oleh daftar berikut :

Bandara 1

Bandara 2

Bandara 3

Penjual 1

92

89

90

Penjual 2

91

91

95

Penjual 3

87

90

92

Tetapi tiap-tiap penjual dibatasi oleh jumlah galon total yang dapat ia sediakan. Kapasitas meraka adalah 320.000 galon bagi penjual 1, 270.000 galon bagi penjual 2 dan 190.000 galon bagi penjual 3. Tentukan kebijaksanaan pembelian yang akan mensuplai kebutuhan perusahaan penerbangan ini pada tiap bandara udara dengan biaya total minimum.

8. Sebuah perusahaan roti dapat memproduksi suatu roti istimewa dari kedua pabriknya, sebagai berikut : Pabrik

Kapsitas Produksi

Biaya Produksi,

jumlah roti

/roti

A

2500

23

B

2100

25

Empat restoran ingin membeli roti ini. Permintaan dan harga-harga yang mereka inginkan untuk membelinya adalah sebagai berikut :

28


Restoran

Permintaan Total,

Harga yang ditawarkan,

Jumlah roti

/roti

1

1800

39

2

2300

37

3

550

40

4

1750

36

Biaya (dalam sen) pengiriman dari sebuah pabrik ke sebuah restoran diberikan pada tabel berikut :

Restoran 1

Restoran 2

Restoran 3

Restoran 4

Pabrik A

6

8

11

9

Pabrik B

12

6

8

5

Tentukan suatu skedul penyerahan bagi perusahaan roti ini yang akan memaksimumkan keuntungan totalnya dari roti istimewa ini.

9. Dua buah perusahaan obat-obatan memiliki persediaan 1,1 dan 0,9 juta dosis dari vaksin flu tertentu, dan suatu wabah flu kelihatannya mengancam tiga buah kota. Karena serangan flu ini dapat fatal bagi penduduk yang lebih tua, maka adalah perlu untuk melakukan vaksinasi bagi mereka terlebih dahulu. Yang lainnya akan divaksin pada basis vaksinasi bagi yang pertama kali datang. Jumlah vaksin (dalam juta dosis) yang tiap-tiap kota perkiraan dapat ia tangani adalah sebagai berikut :

Kota 1

Kota 2

Kota 3

Bagi orang tua

0,325

0,260

0,195

Bagi yang lain

0,750

0,800

0,650

Biaya-biaya pengiriman (dalam sen per dosis) antara perusahaan farmasi dan kota-kotanya adalah sebagai berikut :

29


Kota 1

Kota 2

Kota 3

Perusahaan 1

3

3

6

Perusahaan 2

1

4

7

Tentukan suatu skedul biaya pengiriman yang minimum yang akan melengkapi tiap-tiap kota dengan jumlah vaksin yang sekurang-kurangnya cukup untuk melayani penduduk-penduduknya yang lebih tua. (Petunjuk : Bagikan tiap-tiap kota ke dalam dua buah tempat tujuan, yakni penduduk yang lebih tua dan yang lainnya. Ciptakan sebuah toko buatan (dummy). Buatkan agar biaya pengiriman dari sumber buatan ini ke tampat-tempat tujuan penduduk yang lebih tua begitu tingginya sehingga secara efektif menjamin tidak ada pengiriman antara hubungan-hubungan itu).

10. Jaringan dalam Gambar di bawah menunjukkan rute untuk mengirimkan mobil-mobil dari ketiga pabrik (node 1, 2 dan 3) ke lima dealer ( node 6 sampai 10) melalui dua pusat distribusi (node 4 dan 5). Perhatikan bahwa biaya pengiriman per unit dari node i ke node j adalah c ij . Jawablah masalah berikut : a. Susun model transshipment yang berkaitan untuk masalah dalam Gambar di bawah. b. Rumuskan kembali model dengan memperkirakan bahwa pengiriman diijinkan di antara para dealer. c. Rumuskan kembali model itu dengan asumsi bahwa pusat distribusi 4 akan menjual 240 mobil secara langsung kepada para pelanggan.

30


Pabrik

1000

Pusat Distribusi

1

Dealer

6

800

7

500

8

750

4 1500

2

5 9 1000 1200

3 10

650

31

BAB V PROGRAMA LINIER : MODEL TRANSPORTASI

Recommend Documents