Minimum-Cost Capacitated Flow Problem
Minimum-Cost capacitated flow atau arus berkapasitas biaya minimum didasari pada 3 asumsi Tiap arc melambangkan cost.
Arc boleh mempunyai batas kapasitas positif.
Setiap node pada network bisa berperan sebagai source atau tujuan.
Network Representation
Mengingat jaringan berkapasitas G = (N,A) dimana N adalah jumlah node dan A adalah jumlah arc, maka didefinisikan:
xij= jumlah arus dari node i ke node j
uij(lij) = batas atas (batas bawah) kapasitas arc(i,j)
cij = biaya arus per unit dari node i ke node j.
fi = arus bersih pada node i.
Disini sebagaimana sudah dijelaskan pada bab sebelumnya bahwa tanda positif untuk supply dan negatif untuk demand.
Linear Programming Formulation
Formulasi pada model jaringan berkapasitas adalah program linear yang akan menghasilkan dasar untuk pengembangan algoritma simplex berkapasitas. Dengan menggunakan notasi pada 6.5.1, program linear untuk jaringan berkapasitas ditulis sebagai berikut :
minimize
Linear Programming Formulation [cont]
Rumus diatas adalah pokok dari :
Linear Programming Formulation [cont]
Persamaan untuk node j ini menghitung arus bersih fi pada node j sebagai berikut:
(arus keluar dari node j) – (arus masuk ke node j) = fi
Capacitated Network Simplex Algorithm
Capacitated Network Simplex Algorithm [cont]
Langkah-langkah untuk menyelesaikan kasus jaringan berkapasitas minimum adalah sebagai berikut:
Step 0 : Tentukan solusi awal yang fisible dari jaringan. Lanjut ke step 1.
Step 1 : Tentukan entering variabel dengan menggunakan metode simplex kondisi optimal. Jika seluruh solusi sudah optimal, stop. Jika belum lanjut ke step 2.
Step 2 : Tentukan leaving variabel dengan menggunakan metode simplex kondisi feasible. Tentukan solusi baru, dan kembali ke step 2.
Capacitated Network Simplex Algorithm [cont]
Entering variabel ditentukan dari perhitungan zij – cij, sebuah koefisien objektif untuk seluruh non basis variabel.
Jika zij – cij ≤ 0, berarti sudah optimum. Jika tidak, maka kita harus memilih basis yang paling positif untuk penghitungan selanjutnya menjadi entering variabel.
Contoh Kasus
Sebuah jaringan pipa menghubungkan dua sumber air dengan dua kota. Supply harian dari sumber adalah 40 dan 50 juta galon. Sementara permintaan dari 2 kota masing-masing 30 dan 60 juta galon. Node 1 dan 2 menggambarkan sumber, node 4 dan 5 menggambarkan kota. Node 3 adalah stasiun transit. Tentukan optimal solusi dari model di atas.
Penyelesaian:
Iterasi 0
Step 0
Menentukan solusi fisible awal dari basis.
Didapatkan sebagai berikut:
z12 – c12 = 0 – (-5) – 3 = 2
z25 – c25 = 5 – (-15) – 1 = 9
z45 – c45 = 5 – (-15) – 4 = 6
Arc (2,5) batas atasnya : 30.
Substitusikan x25 = 30 – x52
Kurangkan masing-masing x23 dan x35 dengan 30.
Pengertian
CPM (Critical Path Method) dan PERT (Program Evaluation & Review Technique) adalah metode berbasis jaringan yang didesain untuk membantu perencanaan, penjadwalan & kontrol proyek
Proyek adalah sekumpulan aktivitas yang berhubungan, dimana masing-masing membutuhkan waktu & sumber daya
Tujuannya adalah untuk menganalisa aktivitas penjadwalan
Langkah-langkah-1
Langkah-langkah-2
Tentukan aktivitas proyek, hubungan yg mendahului, & waktu yang dibutuhkan
Proyek diterjemahkan dalam sebuah jaringan yg menunjukkan relasi antar aktivitas
Libatkan perhitungan jaringan spesifik, yang membentuk basis pembangunan time schedule untuk proyek
Langkah-langkah-3
Selama pelaksanaan, jadwal mungkin tidak terealisasikan sesuai dengan yang direncanakan, menyebabkan beberapa aktivitas tertunda / dipercepat. Untuk inilah ada loop ke belakang pada gambar
CPM mengasumsikan durasi aktivitas tertentu
PERT mengasumsikan probabilitas durasi
Tidak ada komentar:
Posting Komentar