Dalam ilmu matematika dikrit sendiri Kombinatorial adalah salah satu cabang dari matematika yang bertujuan untuk menghitung jumlah penyusunan objek-objek tanpa mengenumerasi semua kemungkinan susunannya.
Jadi, dapat disimpulkan Combinatorial
Problem adalah suatu permasalahan matematis dalam menyusun, mengelompokan,
mensorting, atau memilih sejumlah objek diskrit tertentu. Dan sampai saat ini
Combinatorial Problem masih menjadi salah satu masalah yang paling sulit dalam
komputasi, baik itu dari teori dan prakteknya.
Kesulitan dari Combinatorial Problem antara lain adalah :
- Sejumlah objek Kombinatorik tertentu tumbuh dengan cepat seiring peningkatan ukuran masalah.
- Tidak diketahui algoritma pasti yang dapat menyelesaikan masalah Combinatorial Problem.
Beberapa Combinatorial Problem memang
dapat diselesaikan dengan algoritma yang efisien, Tapi itu harus mengikuti
aturan-aturannya. Berikut ini adalah Contoh kasus dari Combinatorial Problem :
VRP atau
Vehicle Routing merupakan permasalahan optimasi penentuan rute dengan
keterbatasan kapasitas kendaraan. Contoh dari permasalahan ini adalah ketika
terdapat salesman yang berangkat dari suatu kota kemudian melakukan kunjungan
ke sejumlah kota. Setiap kotanya hanya dapat
dikunjungi oleh satu salesman saja. Tujuan utamanya adalah meminimalkan total
jarak atau total biaya perjalanan. VRP merupakan permasalahan klasik yang
sangat dekat dengan kehidupan manusia. Contoh permasalahan yang dapat
diselesaian dengan pendekatan VRP antara lain penentuan rute pengiriman surat,
paket, laundry dan koran. Algoritma yang dapat menyelesaikan masalah
Combinatorial Problem diantaranya adalah Genetic Algoritm, Tabu Search,
Simulated Annealing, Nearest Neighbor dan CODEQ.
Dan ini adalah salah satu step by
step dalam memecahkan Vehicle Routing Problem dengan menngunakan Algoritma Nearest
neighbor :
a.
Titik awal rute dimulai dari depot atau gudang.
b.
Mencari lokasi pelanggan terdekat dari depot
yang belum dikunjungi. Lokasi terdekat inilah yang menjadi lokasi pertama yang
akan dikunjungi.
c.
Mencari lokasi lain yang terdekat dari lokasi
terpilih sebelumnya. Dalam mencari lokasi lain ini terdapat beberapa
pertimbangan yaitu:
o
Total jumlah pengiriman tidak melebihi kapasitas
kendaraan yang digunakan.
o
Jika terdapat lokasi terpilih berikutnya dan
masih terdapat sisa kapasitas kendaraan maka ulangi langkah (b).
d.
Apabila kendaraan tidak memiliki sisa kapasitas,
maka kembali ke langkah (1).
e.
Algoritma berhenti jika semua pelanggan telah
dikunjungi tepat satu kali
TSP atau
Travelling Salesman Problem merupakan masalah kombinasi optimasi dalam
menemukan tour yang paling terpendek. TSP adalah problem untuk menentukan
urutan dari sejumlah kota yang harus dilalui oleh salesman, setiap kota hanya
boleh dilalui satu kali dalam perjalanannya, dengan jarak anatara setiap kota
satu dengan setiap kota lainnya sudah diketahui. Salesman tersebut harus
meminimalkan biaya dan jarak yang harus ditempuh dalam perjalanan tersebut.
Berikut adalah step by step dalam meyelesaikan Travelling Salesman Problem :
a.
Siapakan Matriks biaya untuk menghitung bobot.
Jika biaya matriks yang dimaukkan tidak matriks persegi kemuadian menambahkan
kolom baru dengan nol elemen biaya.
b.
Tentukan elemen minimum di setiap baris dan
mengurangi elemen minimum disetiap baris dari semua elemen dari baris
masing-masing.
c.
Sekarang kita mempunyai matriks yang dihasilkan.
Sekarang ulangi proses yang sama dari langkah 2 untuk semua kolom yaitu
menentukan elemen minimum di setiap kolom dan kurangi yang nilai minimum dari semua
kolom masing-masing untuk mendapatkan matriks yang baru dihasilkan.
d.
Sekarang setelah baris dan kolom operasi,
menarik sejumlah minimum garis horizontal dan vertikal untuk menutupi semua nol
dalam menghasilkan matriks. Membiarkan menjadi jumlah minimum bariis dan N
urutan Matriks. Kemudian akan terjadi 2 kemungkinan yang mungki terjadi
o
Jika a = n, maka tugas optimasi jalur bisa
dilakukan
o
Jika N<n, kemudian lanjutkan.
e.
Sekarang menemukan unsur erungkap terkecil dalam
matriks dengan garis “a”.
f.
Kurangi minimum elemen yang dapat diperoleh pada
langkah 5 dari semua elemen ditemukan dan menambahkan elemen yang sama di
persimpangan garis horizontal dana vertical untuk mendapatkan matriks menengah.
g.
Ulangi langkah (b) ke langkah (d) sampai kita
endapatkan kasus a = n.
h.
Periksa berturut-turut baris demi baris sampai
nol tunggal ditemukan. Lingkaran nol ini untuk membuat tugas dan kemudian
tandai silang(X) di semua nol jika berbaring dikolom yang lingkari nol. Ini
menunjukan bahwa mereka tidak dapat dipertimbangkan untuk tugas di masa
mendatang. Lanjutkan dengan cara ini sampai semua nol telah diperiksa. Ulangi
prosedur yang sama untuk kolom juga.
i.
Ulangi langkah (g) berturut-turut sampai salah
satu kondisi dibawah ini muncul :
o
Jika tidak ada angka nol tanpa tanda terisis,
maka akhiri proses.
o
Jika ada terdapat lebih dari satu nol dalam
kolom. Lingkari dan tandai di kolom yang tersisa nol dan ulangi proses samapai
tidak ada nol yang tidak ditandai dalam matriks.
j. Jadi tandai nol di setiap baris dan setiap kolom
dari matriks yang diperoleh dan nol yang ditandai akan memberika penugasan yang
optimal
Contoh Source Code dalam bahasa C
------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<conio.h>
int main ()
{
Int
cost[20],min,l,m,sr[20],sc[20],flag[20],i,j,k,rf[20],cf[20],n;
Int nrz[20],ncz[20,cn,a,noz,nrz1[20],ncz[20],count
er=0;
Printf(“\n\masukan
jumlah tugas : “);
Scanf (“%d”,
&n);
//Masukan
Cost Matriks
Printf
(“\nMasukan cost matriks\n”);
For (i=0;
i<n; i++)
{
Printf(“\n”);
For
(j=0; j<n; j++)
{
Printf(“const[%d][%d]
= “,i,j);
Scanf
(“%d”, &cost[i][j]);
}
}
Printf
(“\n\n”);
//Menampilkan
cost matriz yang dimasukan
Printf (“cost
matriks : \n”);
For (i=0;
i<n; i++)
{
For
(j=0; j<n; j++)
Printf(“\t%d\t”,
costi[i][j]);
Printf(“\n”);
}
//operasi
kolom
For (i=0;
i<n; i++)
{
Min=cost[i][j];
//Menemukan
elemen minimum disetiap baris
For
(j=;j<n;j++)
{
If
(min>cost[i][j])
Min=cost[i][j];
}
//kurangi
unsur dari minimum dari setiap elemen baris
For
(j=0;j<n;j++)
Const[i][j]-min;
}
//operasi
dalam kolom
For
(i=0;i<n;i++)
{
Min=cost[0][i];
//menemukan
elemen disetiap kolom
For(j=0;j<n;j++)
{
If
(min>cost[j][i])
Min=cost[j][i];
}
//kurangi
unsur minimum dari setiap elemen kolom
For
(j=0;j<n; j++)
Costj[j][i]=cost[j][i]-min;
}
Printf(“\n\n”);
Printf{“Cost
matriks setelah operasi baris dan kolom : \n”);
For (i=0;
i<n; i++)
{
For
(j=0; j<n; j++)
Printf(“\t%d\t”,
cost[i][j]);
Print
(“\n”);
}
Repatx:;
//Menarik
jumlah minimum garis horizontal dan vertical
A=0; noz=0,
min=1000;
For (i=0;
i<n; i++)
{
For
(j=0; j<n; j++)
Flag[i][j]=0;
}
For
(i=0;i<n; i++)
{
Cn=0;
For
(j=0; j<n; j++)
{
If
(cost[i][j]==0)
{
Cn++;
Flag[i][j]=1;
}
}
Nrz[i]=cn;
Noz=noz+cn;
}
For (i=0;i<n; i++)
{
Cn=0;
For (j=0;
j<n; j++)
{
If(cost[j][i]==0)
{
Cn++;
Flag[j][i]=1;
}
}
Ncz[i]=cn;
Noz=noz+cn;
}
For (i=0; i<n; i++)
{
Nrz1[i]=nrz[i];
Ncz1[i]=ncz[i];
}
K=0;
While (nrz[k] !=0 || ncz[k] !=0)
{
For (i=0;
i<n; i++)
{
Cn=0;
For(j=0;
j<n; j++)
{
If
(flag[i][j]==1)
Cn++;
Nrz[i]=cn;
}
If
(nrz[i]==1)
{
For
(j=0; j<n; j++)
{
If
(flag[i][j]==1)
{
Flag[i][j]=2;
For(k=0;
k<n; k++)
{
If(flag[k][j]==1)
Flag[k][j]=0;
}
}
}
}
For
(i=0; i<n; i++)
{
Cn=0;
For(j=0;
j<n; j++)
{
If(flag[j][i]==1)
Cn++;
Ncz[i]=cn;
}
If(ncz[i]==1)
{
For
(j=0; j<n; j++)
{
If(flag[j][i]==1)
{
Flag[j][k]=0;
}
}
}
}
}
K++;
}
For (i=0;
i<n; I++)
{
For(j=0l
j<n; j++)
{
If
(flag[i][j]==2)
A++
}
}
//Jika jumlah
minuman baris, adl sama dengan urutan dari matriks n maka dapat diselesaikan
secara optimal//
If(a==n)
{
Printf(“\nTugas\n”);
//Menampilkan
urutan tugas//
For (i=0;
i<n; i++)
{
For(j=0;
j<n; j++)
{
If(flag[i][j]==2)
Printf(“%d->%d”,i+1,j+1);
}
Printf(“\n”);
}
Getch();
Exit(0);
}
//Menentukan
unsur terkecil yang tidak mencakup oleh garis kemudian mengurangi elemen
minimum ini dari semua elemen ditemukan & menambahkan elemen yang sama
dipersimpangan garis horizontal ataupun vertical//
Else
{
For(i=0; i<n;
i++)
{
Rf[i]=0,
sr[i]=0;
Cf[i]=0,
sc[i]=0;
}
For (k=n;
(k>0&&noz!=0); k--)
{
For(i=0;
i<n; i++)
{
M=0;
For(j=0;j<n;
j++)
{
If((flag[i][j]==4&&(cost[i][j]==0))
M++;
}
Sr[i]=m;
}
For(i=0;
i<n; i++)
{
If
(nrz1[i]==k&&nrz1[i]!=sr[i])
{
Rf[i]=1;
For(j==0;
j<n; j++)
{
If(cost[i][j]==0)
Flag[i][j]=4;
}
Noz=noz-k;
}
}
For (i=0;
i<n; i++)
{
1=0;
For(j=0;
j<n; j++)
{
If((flag[j][i]==4)&&(cost[j][i]==0))
l++;
}
Sc[i]=l;
}
For(i=0;
i<n; i++)
{
If(ncz1[i]==k&&ncz1[i]!=sc[i])
{
Cf[i]=1;
For(j=0;
j<n; j++)
{
If(cost[j][i]==0)
Flag[j][i]=4;
}
Noz=noz-k;
}
}
For(i=0;
i<n; i++)
{
For(j=0;
j<n; j++)
{
If(flag{i][j]!=3)
{
If(rf[i]==1
&& cf[j]==1)
{
Flag[i][j]=3;
If(cost[i][j]==0)
Noz=noz+1;
}
}
}
}
}
For(i=0; i<n; i++)
{
For(j=0;
j<n; j++)
{
If(rf[i]!=1&&cf[j]!=1)
{
If(min>cost[i][j])
Min=cost[i][j];
}
}
}
For(i=0; i<n; i++)
{
For(j=0;
j<n; j++)
{
If(rf[i]!=1&&cf[j]!=1)
Cost[i][j]=cost[i][j]-min;
}
}
For(i=0; i<n; i++)
{
For(j=0;
j<n; j++)
{
If(flag[i][j]==3)
Cost[i][j]=cost[i][j]+min;
}
}
}
Printf(“\n\n”);
If(counter < 10)
{
Counter =
counter+1;
Printf(“\n\matriks tengah : \n”);
For (i=0; i<n; i++)
{
For(j=0;
j<n j++)
Printf(“\t%d\t”,
cost[i][j]);
Printf(“\n”);
}
}
Else
{
Printf(“\n\nSolusi
optimal”);
Getch();
Return 0;
}
Goto repatx;
}
-----------------------------------------------------------------------
Knapsack Problem merupakan
masalah dimana orang dihadapkan pada persoalan optimasi pada pemilihan benda
yang dapat dimasukan kedalam sebuah wadah yang memiliki keterbatasan ruang atau
daya tampung. Dengan adanya optimasi dalam pemilihan benda yang akan
dimasukkkan ke dalam wadah tersebut diharapkan dapat menghasilkan keuntungan
yang maksimal. Contoh dari Knapsack Problem adalah Jasa pengangkutan barang
dalam kontainer dengan media kapal. Knapsack Problem bisa ditasi dengan
algoritma Brute Force, Algoritma Greedy dan Algoritma Genetika.
Jenis-Jenis Knapsack Problem
a. 0/1 Knapsack Problem
Setiap barang hanya tersedia 1 unit, take
it or leave it.
b. Fractional Knapsack Problem
Barang boleh dibawa sebagian saja (dalam
unit pecahan). Versi problem ini menjadi
masuk akal apabila barang-barang dibagi misalnya gula, tepung, dan sebaginya.
masuk akal apabila barang-barang dibagi misalnya gula, tepung, dan sebaginya.
· c. Bounded Knapsak Problem
Setiap barang tersedia sebanyak N unit
(jumlahnya terbatas).
· d. Unbounded Knapsak Problem
Setiap barang tersedia lebih dari 1 unit,
jumlah nya tidak terbatas.
Salah satu cara untuk menyelesaikan Knapsack Problem adalah dengan
menggunakan algoritma Greedy. Yang cara kerjanya adalah dengan menyelesaikan
suatu masalah dengan beberapa fungsi pembatas untuk mencapai satu fungsi
tujuan. Berikut Step by step untuk menyelesaikan masalah knapsack :
a.
Tentukan fungsi tujuan , yaitu mencari nilai
maximum dari jumlah hasil perkalian anatara nilai profit (Pi) dengan nilai
Probabilitas (Xi) Maximum ∑ Pi.Xi
b.
Tentukan fungsi pembatas, yang merupakan hasil
penjumlahan dari perkalian anatara bobot (Wi) dngan nilai probabilitas (Xi)
yang tidak boleh melebihi dari kapasitas media penyimpanan (M)
Sebelum mengerjakan ke-2 cara
diatas berarti kita harus mengetahui
Jumlah objek (n), Bobot setiap Objek (Wi), Profit setiap objek (Pi),
Probabilitas setiap objek (Xi) dan
kapasitas media penyimpanan (M).
Algoritma
----------------------------------------------------------------------------------------------
PROCEDURE GREEDY KNAPSACK (P, W,
X, n)
REAL P(1:n), W(1:n), X(1:n), M, isi
INTEGER i, n
X(1:n) = 0
isi = M
FOR i = 1 TO n DO
IF W(i) > isi THEN EXIT ENDIF
X(i) = 1
isi = isi – W(i)
REPEAT
IF i ≤ n THEN X(i) = isi/W(i) ENDIF
END GREEDY KNAPSACK
REAL P(1:n), W(1:n), X(1:n), M, isi
INTEGER i, n
X(1:n) = 0
isi = M
FOR i = 1 TO n DO
IF W(i) > isi THEN EXIT ENDIF
X(i) = 1
isi = isi – W(i)
REPEAT
IF i ≤ n THEN X(i) = isi/W(i) ENDIF
END GREEDY KNAPSACK
-----------------------------------------------------------------------------------------------
Tapi, contoh teknik diatas hanya
akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan
nilai (Pi/Wi).
Mungkin hanya itu saja yang bisa
saya sampaikan, semoga bisa bermanfaat dan mohon maaf bila ada kekurangan. Dan
sseiiring semakin berkembangnya ilmu pengetahuan diharapkan akan ditemukan
metode-metode maupun pendekatan-pendekatan baru yang bisa menjadi sebuah cara
penyelesaian terbaik untuk permasalahan Combinatorial Problem ini. Sekian Semoga kita
bisa bertemu lagi dilain waktu. Terimakasih.
- [Anany Levitin]-Intro_2_Design&Analysis_Algorithms
- Performansi Algoritma CODEQ dalam Penyelesaian Vehicle Routing Problem oleh Annisa Kesy Garside
- Aplikasi Kombinatorial pada Vehicle Routing Problem oleh Raden Prana A
EmoticonEmoticon