makalah metode danzing (modi)
TRANSCRIPT
BAB I
PENDAHULUAN
Persoalan Transportasi membahas masalah pendistribusian, suatu komoditas atau produk dari sejumlah sumber (supply) kepada sejumlah tujuan (demand), dengan tujuan meminimumkan biaya transportasi, di mana masalah transportasi selalu ditunjukkan dengan m dan n tujuan, ai adalah suatu bilangan dari supply unit pada sumber i yang berjalan dari 1,2,3,,m dan bj merupakan suatu unit permintaan pada sumber j dan berjalan dari 1,2,3,,n.
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 jumlah permintaan di setiap tujuan.
2. Biaya transportasi per unit barang dari setiap sumber ke setiap tujuan.
Karena hanya terdapat satu barang, sebuah tujuan dapat menerima permintaannya dari sumber atau lebih. 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 adalah bahwa biaya transportasi di sebuah rute tertentu adalah proporsional secara langsung dengan jumlah unit yang dikirimkan (Hamdy A. Taha, 1996)Ciri-ciri khusus persoalan transportasi ini adalah:
1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu;
2. Kuantitas komoditas atau barang yang didistribusikan dari setiap sumber yang diminta oleh setiap tujuan, besarnya tertentu;
3. Komoditas yang dikirim atau yang diangkut dari suatu sumber ke suatu tujan, besarnya sesuai dengan permintaan atau kapasitas sumber;
4. Ongkos pengangkutan komoditas dari suatu sumber ke suatu tujuan, besarnya tertentu.
Metode Danzing dapat dilakukan dengan bantuan metode sudut barat laut yaitu suatu metode awal atau langkah awal dalam menyelesaikan persoalan transportasi dengan melihat bahwa jumlah supply harus sama dengan jumlah demand.
BAB IIDASAR TEORIA. Metode Danzing (Multipler)
Metode Danzing dikenal juga sebagai Metode MODI (Modified Distribution) /Faktor Pengali (Multiplier). Cara ini dikembangkan berdasarkan teori dualitas. Untuk setiap baris ke-i dari tabel transportasi dikenal suatu bilangan baris (multiplier Ui) dan untuk setiap kolom ke-j disebut bilangan kolom (multiplier Vj) sehingga untuk tiap variabel basis Xij diperoleh persamaan :
Ui + Vj = CijPenyelesaian awal dari metode ini adalah dengan metode sudut barat laut yaitu setiap baris i dari tabel 2 dikenal suatu multipler Ui dan untuk kolom j disebut multipler Vj, untuk setiap penyelesaian fisibel basis Xij berada dalam penyelesaian fisibel basis, maka dapat dicari Ui dan Vj (Hamdy A. Taha,1996)
Dengan demikian diperoleh nilai cost mula-mula dengan persamaan:. Untuk variable X yang tidak berada dalam basis maka dipakai hubungan dengan syarat , di mana merupakan cost yang baru dan akan dicari.Penyelesaian dari hubungan di atas akan menghasilkan suatu penyelesaian fisibel basis yang minimum. Jika kondisi optimal ini belum terpenuhi maka dilakukan penyelesaian fisibel basis yang baru di mana harga fungsi objektifnya akan lebih kecil dari harga fungsi objektif sebelumnya. Misalnya jika diperoleh Z1=40 maka Z240. Jadi dengan cara ini tidak perlu lagi membuat table simplek biasa yang menguji optimalnya yaitu Zij=Cij, tanpa penyajian vector-vektor yang tidak berada dalam basis.
Apabila penyelesaian pertama Z1 dengan masih ada yang lebih besar dari nol maka proses penyelesaian harus dilanjutkan karena belum ditemukan penyelesaian fisible minimum, yaitu dengan cara memilih Xij yang berkoresponden dengan yang lebih besar dari nol, kemudian Xij tersebut diintroduksir ke dalam matrik baru sehingga diperoleh 1.BAB II
PEMBAHASAN
Diketahui tiga asal persediaan yaitu 4, 6 dan 10. Serta tiga tujuan permintaan yang dimulai dengan 3, 5 dan 12. Tentukan penyelesaian basis minimum jika diketahui matriks ongkosnya adalah suatu matriks demand dan supply.
Tabel 1. Matriks Ongkos mula-mula ()102
354
123
Tabel 2. Matriks Demand dan Supply Mula-mula
***4
***6
***10
3512
Penyelesaian:Langkah 1 :
Pertama Tabel 2 di atas diselesaikan dengan menggunakan metode sudut barat laut, maka diperoleh hasil sebagai berikut:Tabel 3. Matriks Ongkos, Demand dan Supply yang Baru3104
0426
001010
3512
Z1= 3(1) + 1(0) + 4(5) + 2(4) + 3(10)
= 3 + 0 + 20 + 8 + 30
= $ 61
Dari hasil penyelesaian di atas ada lima nilai Xij yang telah diperoleh yaitu X11, X12, X22,X23, dan X33 dan memenuhi syarat m + n 1=3+3-1=5 (degenerate)
Langkah 2:
Selanjutnya digunakan Tabel 1 untuk mencari matriks ongkos yang baru ().
Star awal dimisalkan U1=C11=1
C11=U1+V1=1
C23=U2+V3=4
C12=U1+V2=0
C33=U3+V3=3
C22=U2+V2=5
C11=U1+V1 1 =1 +V1 V1= 0C12=U1+V2 0 =1 +V2 V2= -1
C22=U2+V2 5 =U2-1 U2= 6
C23=U2+V3 4 =6+V3 V3= -2
C33=U3+V3 3 =U3-2 U3= 5
Maka diperoleh U1=1, V1=0, U2=6, V2=-1, U3=5, dan V3=-2
Langkah 3:
Mencari variable X yang tidak berada dalam basis (variable non basis ) yaituX13, X21, X31, dan X32 dengan menggunakan hubungan dengan syarat .Tabel 4. Matriks Ongkos yang BaruV1=0V2=-1V3=-2
U1=110-1
U2=6654
U3=5543
Maka diperoleh :
Langkah 4:Karena nilai masih ada yang lebih besar nol, maka proses ini harus dilanjutkan karena belum ditemukan penyelesaian feasible minimumnya. Untuk sel 31, diperoleh nilai terbesar, maka X31 harus diintrodusir ke dalam penyelesaian oleh bilangan 10 yang sangat kecil.
Sehingga diperoleh:
Tebel 5. Matriks Demand dan supply yang baru (kedua)
3-11+14
4- 12+ 16
110- 110
3512
Untuk menjaga fleksibilitas Xij maka harga 1 terletak di 0 1 4. Jika mengambil harga 1=4, maka tabel 5 menjadi :
Tabel 6. Matriks demand dan supply yang baru (kedua)
-154
066
4610
3512
Langkah 5:
Karena variabel basisnya 6 tidak memenuhi syarat m+n-1, maka satu sel harus dibuang. Sel yang dibuang adalah sel yang tidak memenuhi nilai ai maupun bj yang terdapat pada kolom atau baris tersebut. -154
066
4610
3512
Karena hanya ada satu nilai Xij yang tidak merubah nilai jika dibuang yaitu X22 sehingga diperoleh:
Z2 = Z1 maks 1
= 61- 4(4)
= $45
Dari penyelesaian di atas maka diperoleh nilai Xij lima buah, yakni:
X11, X12, X23, X31, dan X33 yang telah memenuhi syarat m + n 1=3+3-1=5 (degenerate).
Langkah 6:
Selanjutnya karena matriks ongkos yang baru (tabel 4) belum lebih besar sama dengan nol maka proses dilanjutkan kembali seperti di atas, yaitu mencari matriks ongkos yang berikutnya.
Untuk start awal dimisalkan U1 = C11 = 1
C11 = U1 + V1 = 1
C12 = U1 + V2 = 0
C23 = U2 + V3 = 4
C31 = U3 + V1 = 1
C33 = U3 + V3 = 3
C11=U1+V1 1 =1 +V1 V1= 0
C12=U1+V2 0 =1+V2 V2= -1C31=U3+V1 1 =U3+0 U3= 1C33=U3+V3 3 =1+V3 V3= 2C23=U2+V3 4 =U2+2 U2= 2Maka diperoleh U1=1, U2=2, U3=1, V1=0, V2=-1, V3=2Langkah 7:
Nilai Ui dan Vj dapat dinyatakan kembali ke tabel 7 berikut dan mencari variable X yang tidak berada dalam basis (variable non basis ) yaitu X13, X21, X22, dan X32 dengan menggunakan hubungan dengan syarat .
Untuk variable non-basis Tabel 7. Matriks ongkos yang baru (lihat nilai diluar kotak)
V1=0V2=-1V3=2
U1=1
103
U2=2
214
U3=1
103
Maka diperoleh :
Langkah 8:Karena nilai masih ada yang lebih besar dari nol, maka proses ini harus dilanjutkan. Untuk sel 13, diperoleh nilai terbesar, maka X13 harus diintrodusir ke dalam penyelesaian oleh bilangan 2 0. Selanjutnya Tabel 6 berubah dengan penambahan nilai 2 seperti pada Tabel 8 berikut.
Tabel 8. Matriks demand dan Supply yang Baru (ketiga)
-1-2524
66
4+26-210
3512
Untuk menjaga fleksibilitas harga 2 terletak di 0 2 . Jika mengambil 2 = 1Maka Tabelnya menjadi :
Tabel 9. Matriks Demand dan Supply (ketiga)
-2514
66
5510
3512
Langkah 9:
Oleh karena variabel basisnya 6 tidak memenuhi syarat m + n 1, maka satu sel harus dibuang. Sel yang dibuang adalah sel yang tidak merubah nilai ai maupun bj yang terdapat pada kolom atau baris tersebut.-2514
66
5510
3512
Karena hanya ada satu nilai Xij yang tidak merubah nilai jika dibuang yaitu X33, maka X33 harus dibuang. Sehingga diperoleh :
Z3 = Z2 maks2 = 45 1(1)
= $ 44
Dari penyelesaian di atas maka diperoleh nilai Xij yaitu lima buah, yakni:
X11, X12, X13, X23, X31Langkah 10:
Selanjutnya kembali dicari nilai matriks ongkos yang baru (ketiga) dengan mencari nilai Ui dan VjUntuk start awal dimisalkan U1 = C11 = 1
C11 = U1 + V1 = 1
C12 = U1 + V2 = 0
C13 = U1 + V3 = 2C23 = U2 + V3 = 4
C31 = U3 + V1 = 1C11=U1+V1 1 = 1 + V1 V1 = 0
C12=U1+V2 0 = 1 + V2 V2 = -1C13=U1+V3 2 = 1 + V3 V3 = 1C23=U2+V3 4 = U2 + 1 U2 = 3C31=U3+V1 1 = U3 + 1 U3 = 0Maka diperoleh U1 = 1, U2 = 3,U3 = 1, V1 = 0, V2 = -1, dan V3 = 1
Tabel 10. Matriks Ongkos yang Baru (lihat nilai di luar kotak)
V1 = 0V2 = -1V3 = 1
U1 = 1102
U2 = 3324
U3 = 1102
Maka diperoleh:
Karena sudah terpeuhi syarat - Cij 0 maka telah tercapai penyelesaian fleksibel minimum yaitu Z3 = 44 dengan
X11 = -2
X12 = 5
X13 = 1X23 = 6
X31 = 5
Contoh Soal:
Diketahui tiga asal persediaan yaitu 150, 210 dan 90. Serta tiga tujuan permintaan yang dimulai dengan 120, 170 dan 160. Tentukan penyelesaian basis minimum jika diketahui matriks ongkosnya adalah suatu matriks demand dan supply.
Tabel 1. Matriks Ongkos mula-mula ()
50100100
200300200
100200300
Tabel 2. Matriks Demand dan Supply Mula-mula
***150
***210
***90
120170160
Penyelesaian:Langkah 1 :
Pertama Tabel 2 di atas diselesaikan dengan menggunakan metode sudut barat laut, maka diperoleh hasil sebagai berikut:Tabel 3. Matriks Ongkos, Demand dan Supply yang Baru120300150
014070210
009090
120170160
Z1= 120(50) + 30(100) + 140(300) + 70(200) + 90(300)
= 6000+3000 + 42000 + 14000 + 27000
= $ 92000Dari hasil penyelesaian di atas ada lima nilai Xij yang telah diperoleh yaitu X11, X12, X22,X23, dan X33 dan memenuhi syarat m + n 1=3+3-1=5 (degenerate)
Langkah 2:
Selanjutnya digunakan Tabel 1 untuk mencari matriks ongkos yang baru ().
Star awal dimisalkan U1=C11=50C11=U1+V1=50
C23=U2+V3=200C12=U1+V2=100
C33=U3+V3=300C22=U2+V2=300C11=U1+V1 50=50+V1 V1= 0C12=U1+V2 100=50 +V2 V2= 50C22=U2+V2 300 =U2+50 U2= 250C23=U2+V3 200 =250+V3 V3= -50C33=U3+V3 300 =U3-50 U3= 350Maka diperoleh U1=50, V1=0, U2=250, V2=50, U3=-50, dan V3=350
Langkah 3:
Mencari variable X yang tidak berada dalam basis (variable non basis ) yaitu
X13, X21, X31, dan X32 dengan menggunakan hubungan dengan syarat .
Tabel 4. Matriks Ongkos yang BaruV1=0V2=50V3=-50
U1=50501000
U2=250250300
200
U3=350350400300
Maka diperoleh :
50- 50= 0 100-100= 0 0-100 = -100250-200 = 50300-300 = 0200-200 = 0350-100 = 250400-200 = 200300-300 = 0Langkah 4:
Karena nilai masih ada yang lebih besar nol, maka proses ini harus dilanjutkan karena belum ditemukan penyelesaian feasible minimumnya. Untuk sel 31, diperoleh nilai terbesar, maka X31 harus diintrodusir ke dalam penyelesaian oleh bilangan 10 yang sangat kecil.
Sehingga diperoleh:
Tebel 5. Matriks Demand dan supply yang baru (kedua)
120-130+1150
140- 170+ 1210
190- 190
120170160
Untuk menjaga fleksibilitas Xij maka harga 1 terletak di 0 1 250. Jika mengambil harga 1=250, maka tabel 5 menjadi :
Tabel 6. Matriks demand dan supply yang baru (kedua)
-130280150
-110320210
250-16090
120170160
Langkah 5:
Karena variabel basisnya 6 tidak memenuhi syarat m+n-1, maka satu sel harus dibuang. Sel yang dibuang adalah sel yang tidak memenuhi nilai ai maupun bj yang terdapat pada kolom atau baris tersebut.
-130280150
-110320210
250-16090
120170160
Karena hanya ada satu nilai Xij yang tidak merubah nilai jika dibuang yaitu X22 sehingga diperoleh:
Z2 = Z1 maks 1
= 92000- 250(250)
= $29500Dari penyelesaian di atas maka diperoleh nilai Xij lima buah, yakni:
X11, X12, X23, X31, dan X33 yang telah memenuhi syarat m + n 1=3+3-1=5 (degenerate).
Langkah 6:
Selanjutnya karena matriks ongkos yang baru (tabel 4) belum lebih besar sama dengan nol maka proses dilanjutkan kembali seperti di atas, yaitu mencari matriks ongkos yang berikutnya.
Untuk start awal dimisalkan U1 = C11 = 50C11=U1+V1=50
C23=U2+V3=200C12=U1+V2=100
C33=U3+V3=300C31=U3+V1=100C11=U1+V1 50=50+V1 V1= 0C12=U1+V2 100=50 +V2 V2= 50C23=U2+V3 200 =U2+200 U2= 0C31=U3+V2 100 =U2+50 U3= 100C33=U3+V3 300 =100+V3 V3= 200Maka diperoleh U1=50, V1=0, U2=0, V2=50, U3=100, dan V3=200
Langkah 7:
Nilai Ui dan Vj dapat dinyatakan kembali ke tabel 7 berikut dan mencari variable X yang tidak berada dalam basis (variable non basis ) yaitu X13, X21, X22, dan X32 dengan menggunakan hubungan dengan syarat .
Untuk variable non-basis Tabel 7. Matriks ongkos yang baru (lihat nilai diluar kotak)
V1=0V2=50V3=200
U1=50
50100250
U2=0
050200
U3=100
100150300
Maka diperoleh :
Langkah 8:Karena nilai masih ada yang lebih besar dari nol, maka proses ini harus dilanjutkan. Untuk sel 13, diperoleh nilai terbesar, maka X13 harus diintrodusir ke dalam penyelesaian oleh bilangan 2 0. Selanjutnya Tabel 6 berubah dengan penambahan nilai 2 seperti pada Tabel 8 berikut.
Tabel 8. Matriks demand dan Supply yang Baru (ketiga)
-20-21702150
210210
140+2-50- 290
120170160
Untuk menjaga fleksibilitas harga 2 terletak di 0 2 . Jika mengambil 2 = 150Maka Tabelnya menjadi :
Tabel 9. Matriks Demand dan Supply (ketiga)
-170170150150
210210
290-20090
120170160
Langkah 9:
Oleh karena variabel basisnya 6 tidak memenuhi syarat m + n 1, maka satu sel harus dibuang. Sel yang dibuang adalah sel yang tidak merubah nilai ai maupun bj yang terdapat pada kolom atau baris tersebut.-170170150150
210210
290-20090
120170160
Karena hanya ada satu nilai Xij yang tidak merubah nilai jika dibuang yaitu X33, maka X33 harus dibuang. Sehingga diperoleh :
Z3 = Z2 maks2 = 29500 150(150)
= $ 7000Dari penyelesaian di atas maka diperoleh nilai Xij yaitu lima buah, yakni:
X11, X12, X13, X23, X31
Langkah 10:
Selanjutnya kembali dicari nilai matriks ongkos yang baru (ketiga) dengan mencari nilai Ui dan Vj
Untuk start awal dimisalkan U1 = C11 = 50C11 = U1 + V1 = 50
C12 = U1 + V2 = 100
C13 = U1 + V3 = 100C23 = U2 + V3 = 200
C31 = U3 + V1 = 100C11=U1+V1 50=50+V1 V1= 0C12=U1+V2 100=50 +V2 V2= 50C13=U1+V3 100 =50+V3 V3= 50C23=U2+V3 200 =U2+50 U2= 150C31=U3+V1 100 =U3+0 U3= 100Maka diperoleh U1=50, V1=0, U2=150, V2=50, U3=100, dan V3=50
Tabel 10. Matriks Ongkos yang Baru (lihat nilai di luar kotak)
V1=0V2=50V3=50
U1=50
50100100
U2=150
150200200
U3=100
100150150
Maka diperoleh:
Karena sudah terpeuhi syarat maka telah tercapai penyelesaian fleksibel minimum yaitu Z3 = 7000 dengan
X11 = -20X12 = 170X13 = 150X23 = 210X31 = 290BAB IV
KESIMPULANMetode Danzing (penggandaan) merupakan metode transportasi yang digunakan untuk menghasilkan suatu penyelesaian feasibel basis yang minimum, dimana penyelesaian ini telah dicapai jika telah memenuhi syarat . Jika kondisi optimalisasi belum terpenuhi maka dilakukan penyelesaian feasibel yang baru, yang mana harga fungsi objektifnya akan lebih kecil dari harga fungsi objektif sebelumnya.
DAFTAR PUSTAKA
Hamdy A. Taha. 1996. Riset Operasi Suatu Pengantar. Edisi kelima. Jilid 1.
Binarupa. Jakarta.
Liebermen, Gerald J, dan Hiller, Frederick S. 1994. Pengantar Riset Operasi.
Edisi kelima. Erlangga. Jakarta.
1
0
2
3
5
4
1
2
3
1
0
2
3
5
4
1
2
3
1
0
2
3
5
4
1
2
3
50
100
100
200
300
200
100
200
300
50
100
100
200
300
200
100
200
300
50
100
100
200
300
200
100
200
300