masalah arus dengan biaya minimum
Post on 17-Apr-2015
589 Views
Preview:
DESCRIPTION
TRANSCRIPT
MASALAH ARUS DENGAN BIAYA MINIMUM
Kelompok 5 Riset Operasi
Clara Desi P (1006534)
Puji Astuti (1000048)
Kristin Manullang (1000544)
Elyzabeth (1006638)
Nurul Hanifah (1000057)
Muhammad Furqon (1002520)
Sofihara Al Hazmy (1000690)
Masalah Arus dengan Biaya Minimum
• Perumusan• Kondisi – kondisi agar jaringan kerja baik :
Sifat penyelesaian yang layakSifat penyelesaian bilangan bulat
• Kasus khusus:Masalah transportasiMasalah pemindahanMasalah penugasanMasalah lintasan terpendekMasalah arus maksimumKesimpulan
Masalah Arus dengan Biaya Minimum
PEMBAHASAN
PERUMUSAN
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Clara
Nilai b tergantung pada kondisi simpul i, dengan
bi > 0 , menunjukkan simpul pemasok (sumber)
bi < 0 , menunjukkan simpul penampung (tujuan)
bi = 0 , menunjukkan simpul perantara
Tujuannya :
meminimumkan total biaya pengiriman pasokan yang tersedia melaluijaringan kerja untuk memenuhi permintaan yang ada.
Perjanjiannya adalah penjumlahan dilakukan hanya sepanjang busuryang ada.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Clara
PERUMUSAN PEMROGRAMAN LINEARNYA
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Clara
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Clara
GAMBAR
Masalah Arus dengan Biaya Minimum
A
EB
C
D
A dan B : sumber ; C : perantara ; D dan E : tujuan
Dipresentasikan oleh : Clara
SIFAT PENYELESAIAN YANG LAYAK
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Puji Astuti
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Puji Astuti
Masalah Arus dengan Biaya Minimum
1
52
3
4
2
1
2 3
9
3
4
Dipresentasikan oleh : Puji Astuti
Contoh jaringan dimana barang dari pemasok lebih banyak daripada barang di penampung
Masalah Arus dengan Biaya Minimum
1
2
3
4
5
D
C
B
A
pemasok penampung
Dipresentasikan oleh : Puji Astuti
SIFAT PENYELESAIAN BILANGAN BULAT
Setiap bi dan ui yang memiliki nilai bulat, menyebabkan semuapeubah dasar dalam setiap penyelesaian dasar yang layak jugamemiliki nilai bilangan bulat.
Contoh dari masalah arus dengan biaya minimum ada pada gambar selanjutnya.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Kristin Manullang
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Kristin Manullang
Masalah Arus dengan Biaya Minimum
CARA PENULISAN DARI SUATU JARINGAN KE DALAMMODEL PERSAMAAN LINEAR
meminimumkan :
Z= 2XAB + 4XAC + 9XAD + 3XBC + XCE + 3XDE + 2XED’
Kendala :XAB + XAC + XAD = 50-XAB + XBC = 40
- XAC - XBC + XCE = 0-XAD + XDE - XED =-30
- XCE - XDE +XED =-60Dan XAB ≤ 10 , XCE < 80 , Xij ≥ 0 untuk setiap i ,j .
Dipresentasikan oleh : Kristin Manullang
Sifat penyelesaian bilangan bulat :
-Koefisien untuk setiap peubah dalam kendala-kendalamemiliki tepat dua peubah koefisien tak nol.
Akibat : salah satu (sembarang) dari kendala tersebutberlebihan. Karena dengan menjumlahkan seluruhpersamaan kendala tersebut akan menghasilkan 0 di kedua ruas nya.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Kristin Manullang
KASUS KHUSUS MASALAH TRANSPORTASI
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
TABEL 7-2 DATA PENGIRIMAN UNTUK P&T
Biaya Pengiriman ($) per angkutan TrukPabrik GUDANG Output
1 464 513 654 867 752 352 416 690 791 1253 995 682 388 685 100
Alokasi 80 65 70 85
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
PERUMUSAN MASALAH TRANSPORTASI PERUSAHAAN P&T SEBAGAI MASLAH ARUS BIAYA MINIMUM.
Masalah Arus dengan Biaya Minimum
C1
C2
C3
G3
G4
G2
G1
[75]
[125]
[100]
[-85]
[-70]
[-65]
464513
654867
995682
791
388685
690416
352
[-80]
Dipresentasikan oleh : Elyzabeth
KASUS KHUSUS MASALAH PEMINDAHAN (TRANSSHIPMENT)
Masalah ini merupakan bentuk umum dari masalah transportasidimana satuan-satuan yang akan disebarkan dari sumber menujutujuan dapat melalui suatu titik pertengahan yang bisa merupakan titikpemindahan, sumber atau pun tujuan.
Model Transhipment adalah model transportasi yangmemungkinkan dilakukannya pengiriman barang secara tidak langsung,dimana barang di suatu sumber dapat berada pada sumberlain atautujuan lain sebelum mencapai tujuan akhirnya. Sumber dan tujuandipandang sebagai titik-titik potensial bagi demand maupun supply
Oleh karena itu, perumusan maslaah pemindahan sebagai suatumasalah arus biaya minimum akan sama saja dengan perumusanmasalah transportasi. Bedanya pada masalah pemindahan terdapatsimpul perantara untuk setiap titik perpindahan dan busur ditambahkanuntuk setiap perjalanan pertengahan dari suatu titik menuju titik yanglain.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
TABEL 7-24 DATA PENGANGKUTAN UNTUK P&T
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
Dari tabel 7-24 di atas untuk memperoleh biaya minimum untukpengiriman barang dari suatu pabrik ke gudang dapat dilakukantanpa mengirim langsung dari pabrik ke gudang.
Contoh : biaya pengiriman dari pabrik 1 ke gudang 4 adalah $871,namun pengiriman dapat dilakukan dari pabrik 1 ke persimpangan 2lalu ke gudang 2 barulah ke gudang 4, dan biaya yang dikeluarkan$286 + $207 + $341 = $834. Biaya pengiriman dapat lebih minimumjika tidak dilakukan langsung dari pabrik 1 ke gudang 4.
Pada tabel 7-24, sepanjang diagonal kiri atas ke kanan bawahbernilai nol, karena menunjukan pengiriman ke tempat itu sendiri,dan pengiriman yang tidak mungkin yang ditandai dengan garisdatar diberi biaya per unit yang tinggi sebesar M. Selanjutnya untukmencari biaya minimum menggunakan cara yang sama denganmasalah transportasi.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Elyzabeth
KASUS KHUSUS MASALAH PENUGASAN
Masalah penugasan merupakan jenis khusus program linear dimana sumber-sumber dialokasi pada kegiatan-kegiatan dasarsatu-satu. Jadi setiap sumber/petugas ditugasi secara khususkepada suatau kegiatan/tugas.
Tujuan masalah penugasan adalah untuk menentukanbagaimana semua tugas harus dilakukan untuk meminimumkanbiaya total
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Nurul Hanifah
TABEL 7-26 DATA BIAYA PENANGANAN BAHAN UNTUK JOB SHOP
Lokasi Mesin 1 2 3 4 suplai
1 13 16 12 11 12 15 M 13 20 13 5 7 10 6 1
demande 1 1 1 1
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Nurul Hanifah
Masalah Arus dengan Biaya Minimum
[-1]M1
M2
M3
L3
L4
L2
L1
[1]
[1]
[1]
[-1]
[-1]
[-1]
1316
1211
15M
1320
5 710
6
0 00
0M4
Dipresentasikan oleh : Nurul Hanifah
Masalah Arus dengan Biaya Minimum
KASUS KHUSUS MASALAH LINTASAN TERPENDEK
untuk merumuskan masalah ini sebagai suatu masalah arus biaya minimum,
• satu simpul pemasok dengan nilai pasokan 1 disediakan untuk titik asal
• Satu simpul penampung dengan permintaan sebesar 1 disediakan untuk tujuan,
• Simpul sisanya sebagai simpul perantara
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Muhammad Furqon
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Muhammad Furqon
Masalah Arus dengan Biaya Minimum
C4
4
4
5
5
7
1
1
1 12
3
6
E
TA
O DB[1]
[-1]
Dipresentasikan oleh : Muhammad Furqon
KASUS KHUSUS MASALAH ARUS MAKSIMUM
Dalam kasus ini jaringan kerja telah tersedia dengan satu buahsimpul pemasok, satu buah simpul penampung, beberapa buahsimpul perantara, berbagai busur dan kapasitas busur. Hanyadiperlukan tiga buah perubahan untuk menyesuaikan masalah inidalam format masalah arus biaya minimum.
1. menetapkan Cij = 0 untuk semua busur yang ada untukmenggambarkan ketiadaan faktor biaya dalam masalah arusmaksimum.
2. Memilih suatu besaran yang merupakan suau batas atas dariarus maksimum yang layak yang dapat dilewatkan dalamjaringan kerja dan memberikan penawaran dan permintaansebesar kepada masing – masing simpul pemasok dansimpul penampung.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Sofihara Al Hazmy
3.Menambah busur yang langsung menuju simpul penampungdari simpul pemasok dan menugaskan satuan biaya Cij = M yang cukup besar, serta memberikan kapasitas busur yang tidak terbatas (uij = tak hingga) . Karena biaya yang sangatbesar ini, masalah arus biaya minimum akan mengirimkanarus maksimum yang layak melalui busur lain, yang menjaditujuan masalah arus maksimum.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Sofihara Al Hazmy
Masalah Arus dengan Biaya Minimum
C4
4
4
5
5
7
1
1
1 12
3
6
E
T
A
O DB
Dengan menerapkan perumusan ini terhadap masalah arusmaksimum Taman Seervada yang digambarkan pada gambar10.5 akan menghasilkan jaringan kerja
Dipresentasikan oleh : Sofihara Al Hazmy
KESIMPULANKetika suatu masalah disajikan, kita menjelaskan suatu algoritmadengan tujuan khusus yaitu memecahkannya secara sangatefisien.
untuk itu, tidak perlu merumuskan kembali kasus-kasus khusus inidalam format yang sesuai dengan masalah arus biaya minimum. Namun, jika kode komputer tidak tersedia untuk algoritma dengantujuan khusus ini, maka sangat beralasan untuk menggunakanmetode simpleks jaringan kerja.
Hal ini terutama berlaku untuk masalah pemindahan (tanpakendala kapasitas) dan sampai batas tertentu, beberapa masalahtransportasi.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Sofihara Al Hazmy
Kelima masalah ini merupakan kasus khusus dari masalah arusbiaya minimum merupakan salah satu daya tarik tersendiri. Salah satunya adalah teori yang mendasari masalah arus biayaminimum dan metode simpleks jaringan kerja memberikankesatuan teori untuk seluruh kasus khusus diatas.
Hal lain adalah beberapa dari terapan masalah arus biayaminimum mengandung satu atau beberapa ciri dari kasus-kasuskhusus di atas, sehingga sangat penting untuk mengetahuimelakukan perumusan kembali dari kasus-kasus ini dalamkerangka yang lebih luas pada masalah yang lebih umum.
Masalah Arus dengan Biaya Minimum
Dipresentasikan oleh : Sofihara Al Hazmy
top related