masalah arus dengan biaya minimum

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


PEMBAHASAN

PERUMUSAN


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.



PERUMUSAN PEMROGRAMAN LINEARNYA



GAMBAR


A

EB

C

D

A dan B : sumber ; C : perantara ; D dan E : tujuan


SIFAT PENYELESAIAN YANG LAYAK


Dipresentasikan oleh : Puji Astuti


1

52

3

4

2

1

2 3

9

3

4


Contoh jaringan dimana barang dari pemasok lebih banyak daripada barang di penampung


1

2

3

4

5

D

C

B

A

pemasok penampung


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.


Dipresentasikan oleh : Kristin Manullang


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 .


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.



KASUS KHUSUS MASALAH TRANSPORTASI


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



PERUMUSAN MASALAH TRANSPORTASI PERUSAHAAN P&T SEBAGAI MASLAH ARUS BIAYA MINIMUM.


C1

C2

C3

G3

G4

G2

G1

[75]

[125]

[100]

[-85]

[-70]

[-65]

464513

654867

995682

791

388685

690416

352

[-80]


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.



TABEL 7-24 DATA PENGANGKUTAN UNTUK P&T



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.



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


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




[-1]M1

M2

M3

L3

L4

L2

L1

[1]

[1]

[1]

[-1]

[-1]

[-1]

1316

1211

15M

1320

5 710

6

0 00

0M4


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


Dipresentasikan oleh : Muhammad Furqon


C4

4

4

5

5

7

1

1

1 12

3

6

E

TA

O DB[1]

[-1]


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.


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.




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


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.



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

Documents