Pengecekan keoptimalan solusi

  • Published on
    22-Jul-2015

  • View
    59

  • Download
    0

Embed Size (px)

Transcript

<p>PowerPoint Presentation</p> <p>Pengecekan Keoptimalan Solusi Oleh:Nur Asyifa (1113017000032)Hanna Ramadhana (1113017000040)Ana Matofani (1113017000045)Jafar Ashodiq Al Jufri (1113017000053)Andina Aulia Rachma (1113017000054)</p> <p>Model TransportasiModel transportasi adalah sebuah usaha untuk menentukan rencana transportasi barang dari sejumlah sumber ke sejumlah tujuan.Langkah-Langkah penyelesaian model transportasi adalah :Menentukan Solusi AwalMengecek Keoptimalan solusiModel TransportasiUntuk menentukan solusi awal dalam Model transportasi dapat digunakan 3 metode yaitu metode NWC, Least Cost, dan VAMSetelah solusi awal ditentukan, langkah selanjutnya adalah mengecek apakah solusi tersebut sudah optimal. Pengecekan solusi itu dapat dilakukan dengan 2 Metode, yaitu:Metode Stepping StoneMetode MODI (Modified Distribution)</p> <p>Karakteristik Model TransportasiSuatu barang dipindahkan (transported) dari sejumlah sumber ke tempat tujuan dengan biaya seminimum mungkin Tiap sumber dapat memasok suatu jumlah yang tetap dan tiap tempat tujuan mempunyai jumlah permintaan yang tetap.</p> <p>Contoh SoalGandum dipanen di Midwest dan disimpan dalam cerobong butir gandum di tiga kota, yaitu Kansas City, Omaha, dan Des Moines. Ketiga cerobong butir gandum ini memasok tiga penggilingan tepung yang berlokasi di Chicago, St. Louis, dan Cincinnati. Setiap bulannya, tiap cerobong butir gandum dapat memasok penggilingan sejumlah ton gandum berikut ini.</p> <p>SupplyKansas City 150Omaha 175 Des Moines 275 600 ton </p> <p>Jumlah ton gandum yang diminta per bulan dari tiap penggilingan adalah sebagai berikut : Penggilingan Jumlah yang diminta A.Chicago 200 B.St. Louis 100 C.Cincinnati 300 600 ton</p> <p>Biaya Pengiriman ($)Cerobong Butir GandumPenggilinganChicago(A)St. Louis(B)Cincinnati(C) (1) Kansas City6810(2) Omaha71111(3) Des Moines4512Metode Stepping StoneSolusi Awal di peroleh dari Metode Biaya Cell Minimum</p> <p>ABCPasokan1 6 8</p> <p> 10</p> <p>1502 7 11 111753</p> <p> 4 </p> <p> 5</p> <p> 12275Permintaan200100300600DariKeSolusi Awal di peroleh dari Metode Biaya Cell Minimum</p> <p>ABCPasokan1 6 825 101251502 7 11 111751753</p> <p> 4 200 575 12275Permintaan200100300600DariKeZmin = (200*4) + (25*8) + (75*5) + (125*10) + (175*11) = 4550Persyaratan RIMSebelum mengecek apakah solusi awal yang kita dapat telah optimal , solusi awal tersebut harus memenuhi persyaratan RIM. Yaitu dengan mengecek jumlah sel terisi dengan rumus :( m + n 1 )Jika jumlah sel terisi telah sesuai dengan rumus diatas, maka langkah selanjutnya dapat dilakukan m : jumlah barisn : jumlah kolom</p> <p>1.Menentukan Opportunity cost dari sel kosong dengan membuat loop tertutup. 2.Alokasikan sebanyak mungkin ke sel kosong yang menghasilkan penurunan biaya terbesar. Dengan melihat sel kosong yang memiliki OC paling positif 3.Ulangi langkah 1 dan 2 semua sel kosong memiliki perubahan biaya positif yang mengidentifikasikan tercapainya solusi optimal.</p> <p>LANGKAH-LANGKAH STEPPING STONE :Menentukan Opportunity cost dari sel kosong dengan membuat loop tertutup. Loop tertutup adalah sebuah jalur yang di buat dari sel kosong hingga kembali ke sel kosong tersebut melalui sel-sel terisi.Opportunity cost di dapat dari perubahan biaya dikali negatif satu LANGKAH PERTAMA : Alokasi Satu Ton Ke Sel 1AABCPasokan1 + 6 - 825 101251502 7 11 111751753</p> <p> - 4 </p> <p> 5 + 75 12275Permintaan200100300600DariKeSel 1A : +6-8+5-4 = -1OC : +1200Alokasi Satu Ton Ke Sel 2AABCPasokan1 6 - 825 + 101251502 + 7 11 _ 111751753</p> <p> - 4 200 5 + 75 12275Permintaan200100300600DariKeSel 2A : +7-11+10-8+5-4 = -1OC : +1Alokasi Satu Ton Ke Sel 2BABCPasokan1 6 - 825 + 101251502 7 11 + - 111751753</p> <p> 4 200 5 75 12275Permintaan200100300600DariKeSel 2B : +11-11+10-8 = +2OC : -2 Alokasi Satu Ton Ke Sel 3CABCPasokan1 6 + 825 - 101251502 7 11 111751753</p> <p> 4 200 5 - 75 12 +275Permintaan200100300600DariKeSel 3C : +12-10+8-5 = +5OC : -5Alokasikan sebanyak mungkin ke sel kosong yang menghasilkan penurunan biaya terbesar. Dengan melihat sel kosong yang memiliki OC paling positif </p> <p>LANGKAH 2 :Sel KosongOCA1+1A2+1B2-2C3-5 SEL A1 dan A2 memiliki nilai positif yang sama, Maka kita dapat memilih salah satu untuk masuk ke dalam sel perbaikan, misal kita memilih sel A1</p> <p>Maka didapatkan hasil :Lintasan Stepping Stone untuk Sel 1AABCPasokan1 + 6 - 825 101251502 7 11 111751753</p> <p> - 4 200 5 + 75 12275Permintaan200100300600DariKe20Hasilnya.ABCPasokan1 625 8</p> <p> 101251502 7 11 111751753</p> <p> 4 175 5 100 12275Permintaan200100300600DariKeZmin = (125*10) + (175*11) + (175*4) + (100*5) = 4.52521Apakah masih bisa didapatkan biaya yang lebih murah ? Lakukan cek terhadap sel sel kosong Cari Rute, Hitung Biaya. </p> <p>Namun sebelum itu, jangan lupa cek persyaratan RIM terlebih dahulu.Lintasan Stepping Stone untuk Sel 1BABCPasokan1 - 6 25 + 8</p> <p> 101251502 7 11 111751753</p> <p> 4 + 5 - 100 12275Permintaan200100300600DariKeSel 1B: +8-5+4-6 = +1175Lintasan Stepping Stone untuk Sel 2AABCPasokan1 - 6 25 8</p> <p> + 101251502 + 7 11 - 111751753</p> <p> 4 175 5 100 12275Permintaan200100300600DariKeSel 2A : +7-6+10-11 = 0Lintasan Stepping Stone untuk Sel 2BABCPasokan1 6 - 25 8</p> <p> 10 + 1251502 7 11 + 11 - 1751753</p> <p> 4 + 175 5 - 100 12275Permintaan200100300600DariKeSel 2B = +11-5+4-6+10-11 = +3Lintasan Stepping Stone untuk Sel 3CABCPasokan1 6 + 25 8</p> <p> 10 - 1251502 7 11 111751753</p> <p> 4 - 175 5 100 12 +275Permintaan200100300600DariKeSel 3C: +12-4+6-10 = +4Ternyata opportunity cost dari semua sel kosong mempunyai nilai biaya 0 , maka Iterasi berhenti dan Z sudah minimum. Akan tetapi, untuk sel 2A, nilai biaya = 0 ,berarti soal ini memiliki solusi lebih dari satu (solusi Alternatif) yang menghasilkan biaya minimum. Solusi Alternatif dari Sel 2AABCPasokan1 6 </p> <p> 8</p> <p> 101501502 725 11 111501753</p> <p> 4 175 5 100 12275Permintaan200100300600DariKeZmin = (25*7) + (175*4) + (100*5) + (150*10) + (150*11) = 4525Metode MODI(Modified Distribution)METODE MODILangkah-langkah :Tentukan solusi awal menggunakan satu dari ketiga metode yang tersedia. Hitung nilai bilangan baris dan bilangan kolom dengan menerapkan formula ui + vj = cijHitung opportunity cost, untuk setiap sel kosong menggunakan formula Implised cost actual cost Alokasikan sebanyak mungkin ke sel kosong yang menghasilkan opportunity cost positifUlangi langkah di atas sampai solusi optimal</p> <p>Solusi Awal Biaya Sel MinimumVjVA=VB=VC=UiABCPasokanU1=125125150U2=2</p> <p>175175U3=3</p> <p>20075275Permintaan200100300600KeDari4512681071111Langkah berikutnya : Menghitung nilai bilangan baris dan bilangan kolom Misal u1 = 0x1B : u1 + vB = 8 0 + vB = 8 vB = 8 x1C : u1 + vC = 10 0 + vC = 10 vC = 10 x2C : u2 + vC = 11 u2 + 10 = 11 u2 = 1</p> <p>x3B : u3 + vB = 5 u3 + 8 = 5 u3 = -3 x3A : u3 + vA = 4 -3 + vA = 4 vA = 7</p> <p>Solusi Awal Untuk Semua Nilai Ui dan VjVjVA=7VB=8VC=10UiABCPasokanU1=0125125150U2=12</p> <p>175175U3=-33</p> <p>20075275Permintaan200100300600KeDari4512681071111Langkah berikutnya : Hitung opportunity cost, untuk setiap sel kosong menggunakan formula Implised cost actual costFormula : Implised cost actual cost : (Ui + Vj) biaya angkutDari tabel sebelumnya didapatkan : x1A : (0+7) 6 = +1x2A : (1+7) 7 = +1x2B : (1+8) 11 = -2x3C : (-3+10) 12 = -5</p> <p>Dari hasil tersebut ternyata nilainya = nilai biaya di stepping stone. Maka langkah berikutnya pasti = langkah stepping stone sehingga didapatkan tabel berikut : </p> <p>ABCPasokan1 + 6 - 825 101251502 7 11 111751753</p> <p> - 4 200 5 + 75 12275Permintaan200100300600DariKe36Hasilnya.VjVA=VB=VC=UiABCPasokanU1=1250125150U2=2</p> <p>175175U3=3</p> <p>175100275Permintaan200100300600KeDari4512681071111Zmin = (125*10) + (175*11) + (175*4) + (100*5) = 4.525Apakah masih bisa didapatkan biaya yang lebih murah ?Lakukan langkah untuk mencari bilangan baris dan bilangan kolom dari tabel optimal 1A</p> <p>Namun sebelum itu, jangan lupa cek persyaratan RIM terlebih dahulu. </p> <p>Nilai bilangan baris dan bilangan kolom dihitung sebagai berikut :x1A : u1 + vA = 6 0 + vA = 6 vA = 6 x1C : u1 + vc = 10 0 + vC = 10 vC = 10 x2C : u2 + vC = 11 u2 + 10 = 11 u2 = 1</p> <p>x3A : u3 + vA = 4 u3 + 6 = 4 u3 = -2 x3B : u3 + vB = 5 2 + vB = 5 vB = 7</p> <p>Didapat tabel :VjVA= 6VB= 7VC= 10UiABCPasokanU1= 01250125150U2= 12</p> <p>175175U3= -23</p> <p>175100275Permintaan200100300600KeDari4512681071111Langkah berikutnya : Hitung opportunity cost, untuk setiap sel kosong menggunakan formula Implised cost actual costFormula : Implised cost actual cost : (Ui + Vj) biaya angkutDari tabel sebelumnya didapatkan : x1B : (0+7) 8 = -1x2A : (1+6) 7 = 0x2B : (1+7) 11 = -3x3C : (-2+10) 12 = -4</p> <p>Ternyata opportunity cost dari semua sel kosong mempunyai nilai biaya 0 , maka Iterasi berhenti dan Z sudah minimum. Akan tetapi, untuk sel 2A, nilai biaya = 0 ,berarti soal ini memiliki solusi lebih dari satu (solusi Alternatif) yang menghasilkan biaya minimum. </p> <p>Tabel Solusi AlternatifVjVA= 6VB= 7VC= 10UiABCPasokanU1= 01 - 250 + 125150U2= 12</p> <p> + - 175175U3= -23</p> <p>175100275Permintaan200100300600KeDari4512681071111HasilnyaVjVA= 6VB= 7VC= 10UiABCPasokanU1= 01 150150U2= 12</p> <p> 25 150 175U3= -23</p> <p> 175 100275Permintaan200100300600KeDari4512681071111</p> <p>Terima Kasih Atas PerhatiannyaLatihan Soal</p> <p>D1D2D3PasokanO1 4 8</p> <p> 8</p> <p>56O2 16 24 1682O3</p> <p> 8 </p> <p> 16</p> <p> 2477Permintaan7210241DariKe</p>