Oktober 25, 2020
Sistem Informasi

Metode Greedy

ICON CREATOR MEDIA MAKET CREATOR

Fungsi dari Metode Greedy yaitu ntuk mendapatkan solu1si optimal dr permasalahan yg mempunyai dua kriteria
yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain). METODE GREEDY

Proses Kerja Metode Greedy :
Untuk menyeselesaikan suatu permasalahan dgn n inputdata yg terdiri dari beberapa fungsi pembatas & 1 fungsi
tujuan yg diselesaikan dgn memilih beberapa solusi yg mungkin (feasible solution/feasible sets), yaitu bila telah
memenuhi fungsi tujuan/obyektif. Metode GREEDY digunakan dlm penyelesaian masalah – masalah :

  1. Optimal On Tape Storage Problem
  2. Knapsack Problem
  3. Minimum Spanning Tree Problem
  4. Shortest Path Problem.

 

1. Optimal Storage On Tapes Problem
Permasalahan Bagamana mengoptimalisasi storage/memory dalam komputer agar data yg disimpan dapat termuat dgn optimal. Misalkan terdapat n program. yg akan disimpan didalam pita (tape).Pita tsb mempunyai panjang
maks. sebesar L, masing2 prg. yg akan disimpan mempunyai panjang L1,L2,L3 …,Ln. Cara penyimpanan adalah penyimpanan secara terurut (sequential).

Persoalan = Bagamana susunan penyimpanan
program2 tersebut sehingga
L1 + L2 + L3 + … + Ln = L ?
L1 L2 L3 . . . Ln
Pemecahannya = jika program.2 tersebut disimpan
dlm Order, dimisalkan adalah Order I, yaitu : j
sama dengan S tik maka akan didapat k=1
n
Mean Retrieval Time (MRT) = S tj /n
j=1
n j
dan Optimal Storage = D(I) = S S lik
j=1 k=1
Contoh,
Misal terdapat 3 buah prg.(n=3) yg masing2
mpy panjang prg. (I1,I2,I3)=(5,10,3). Tentukan
urutan penyimpanannya scr berurutan
(sequential) agar optimal….!

Penyelesaiannya :
Dari 3 program tersebut akan didapat 6 buah kemungkinan order, yg didapat dr nilai faktorial 33! (ingat faktorial n!).

 

2. KNAPSACK Problem

Kasus : Terdapat n obyek (Xi;i=1,2,3,….n) yang masing-masing mempunyai berat (weight)/ Wi & masing-masing memiliki nilai (profit)/Pi yg berbedabeda. Masalah : Bagamana obyek-obyek tersebut dimuat / dimasukan kedalam ransel (knapsack) yg mempunyai kapasitas maks. = M. Sehingga timbul permasalahan sbb:
Bagaimana memilih obyek yg akan dimuat dr nobyek yg ada sehingga nilai obyek termuat jumlahnya sesuai dgn kapasitas(£ M) Jika semua obyek harus dimuat kedalam ransel maka berapa bagian dr setiap obyek yg ada dapat
dimuat kedalam ransel sedemikian shg nilai kum. maks. & sesuai dgn kapasitas ransel ?
Penyelesaian Knapsack Problem :

  1. Dengan Secara Matematika
  2. Dengan Kriteria Greedy.
  3. Dengan Algoritma Pemrograman Greedy.

Penyelesaian Knapsack Dengan Secara Matematika
Fungsi tujuan = fungsi utama/obyektif = fungsi yg mjd penyelesaian permasalahan dgn mendptkan solusi yg optimal. Solusi dimaksud = menemukan nilai/profit yg maks. utk jml obyek yg dimuat dlm ransel shg sesuai kapasitas.
n
Fungsi Tujuan Maksimum : Σ Pi Xi
I=1

Fungsi pembatas = fungsi subyektif = fungsi yg bertujuan untuk memberikan batas maks. dr setiap obyek untuk dapat dimuat dalam ransel sehingga kapasitasnya tdk melebihi dr jumlah maks.daya tampung ransel.
n
Fungsi Pembatas : Σ Wi Xi £ M
i=1
dimana : 0 £ Xi £ 1; Pi >0;Wi>0
Catatan : karena dengan menggunakan
Matematikan sangat sulit dan rumit maka tidak dibahas
lebih mendalam.

Penyelesaian Dengan Kriteria Greedy.
Konsep dr kriteria yg ditawarkan oleh metode Greedy yaitu :

  1. Pilih obyek (barang) dengan nilai Pi maximal atau terbesar
  2. Pilih obyek (barang) dengan beratWi minimal dahulu.
  3. Pilih obyek (barang) dgn perbandingan nilai & berat yaitu Pi/Wi yang terbesar.

 

Penyelesaiannya : Dengan Kriteria
Greedy.
Diketahui bahwa kapasitas M = 20kg ,
Dengan jumlah barang n=3
Berat Wi masing-masing barang
(W , W , W ) = (18, 15, 10)
123Nilai Pi masing-masing barang
(P1, P2, P3) = (25, 24, 15)

Pilih barang dengan Nilai Profit Maksimal
P1 = 25  X1 = 1, dimisalkan sebagai
batas atas nilai
P2 = 24  X2 = 2/15, dihitung dengan
Fungsi Pembatas
P3 = 15  X3 = 0, dimisalkan sebagai
batas bawah nilai

Pilih barang dengan Berat Minimal
W1 = 18  X1 = 0, sebagai batas bawah
W2 = 15  X2 = 2/3,dihitung dgn Fungsi
Pembatas
W3 = 10  X3 = 1, sebagai batas atas

Pilih barang dgn menghitung perbandingan yg terbesar
dr Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik,
yaitu :
P1/W1 = 25/18 karena terkecil maka X1 = 0
P2/W2 = 24/15 karena terbesar maka X2 = 1
P3/W3 = 15/10 dengan Fungsi pembatas
X3 = 1/2.

 

Supported by: Jasa Maket by MaketCreator.com