BAB 2 OPTIMISASI KOMBINATORIAL
2.1 Masalah Model Optimisasi Kombinatorial Masalah optimisasi merupakan suatu proses pencarian varibel bebas yang memenuhi kondisi atau batasan yang disebut kendala dari permasalahan. Proses selanjutnya adalah pencarian ukuran baik yang bergantung pada variabel-variabel permasalahan yang diistilahkan fungsi objektif. Oleh karena penyelesaian optimisasi meupakan himpunan dari nilai-nilai variabel yang memenuhi kendala, sedemikian hingga fungsi objrektif mencapai nilai optimal, maka pada penyelesaian optimisasi kombinatorial, himpunan nilai-nilai variabel yang dimaksud adalah himpunan bilangan bulat atau biner. Untuk memudahkan pengkajian masalah penyelesiannya, masalah optimisasi kombinatorial direpresentasikan sebagai program matematika yang bentuk umumnya adalah sebagai berikut, Cari X = (x1, x2, ..., xn) dengan memaksimumkan fungsi tujuan f (X) dengan kendala
gi (X) 6 0, hi (X) = 0,
Fungsi f , gi dan hi dapat berbentuk fungsi linear atau nonlinear dan X adalah variabel keputusan yang nilainya bilangan bulat atau biner.
14
15 Optimisasi dapat diklasifikasikan dalam beberapa kriteria:
1. Berdasarkan bentuk fungsi tujuan dan fungsi kendala, masalah optimisasi ini diklasifikasikan sebagai masalah program linear dan program non linear. Jika terdapat fungsi nonlinear diantara fungsi objektif atau fungsi-fungsi kendala maka masalah optimisasi tersebut dinamakan masalah program non linear. Masalah program non linear mempunyai beberapa tipe: (a) Program kuadratik Jika fungsi objektif f (x) harus fungsi kuadrat dan kendala adalah fungsi-fungsi linear. (b) Program konveks i. Fungsi objektif f (x) (memaksimumkan) adalah fungsi konkaf. ii. Setiap fungsi kendala gi (x) adalah fungsi konveks . (c) Program separable (terpisah) i. Fungsi objektif f (x) (memaksimumkan) adalah fungsi konkaf. ii. Setiap fungsi kendala gi (x) adalah fungsi konveks . iii. Semua fungsi f (x) dan gi (x) dadalah fungsi separable. (d) Program Nonkonveks. Jika fungsi objektif atau fungsi kendala tidak ada asumsi konveks. 2. Berdasarkan pada nilai variable keputusan (penyelesaian) yang diperbolehkan,
16 masalah optimisasi ini diklasifikasikan sebagai masalah pemrograman integer dan masalah pemrograman riil. Jika beberapa atau semua variable keputusan xj , (j = 1, 2, · · · , n), dibatasi hanya bernilai integer (bilangan bulat) atau diskrit, masalah tersebut dinamakan masalah pemrograman integer. Jika semua variable keputusan bernilai bilangan real, maka masalah tersebut dinamakan masalah pemrograman bilangan real dan jika ada variabel keputusan bernilai bilangan real dan ada yang bilangan bulat maka masalah tersebut dinamakan masalah pemrograman mix integer.
Masalah optimisasi kombinatorial dapat diformulasikan dalam bentuk graph dan dalam bentuk program matematika. Berikut ini beberapa contoh masalah optimisasi kombinatorial.
2.2 Beberapa Masalah Optimisasi Kombinatorial Berikut ini disajikan beberapa masalah optimisasi kombinatorial dari graph yang berbentuk pemrograman non linear integer, khususnya polinomial sehingga model optimisasi kombinatorialnya berbentuk pemrograman polinomial integer. 2.2.1 Himpunan stabil dan bilangan stabil Definisi 2.2.1 : Himpunan Stabil pada suatu graph G = (V, E) adalah himpunan bagian dari vertex-vertex di V , sehingga tidak ada dua vertex di himpunan tersebut yang bertetangga. Ukuran maksimal dari himpunan stabil tersebut disebut bilangan stabil.
17 Untuk membuat model optimisasi kombinatorial dari suatu graph G = (V, E), yang mempunyai bilangan stabil = k, dimisalkan variable xi yang menyatakan vertex i ∈ V (G) dan vertex i hanya diberi nilai 1 atau 0, yaitu jika terpilih diberi nilai 1 dan jika tidak dipilih diberi nilai 0. Oleh karena itu bentuk aljabarnya adalah x2i − xi = 0 untuk setiap i ∈ V (G). Selanjutnya karena setiap vertex yang bertetangga tidak berada dalam satu himpunan, akibatnya jika xi sudah diberi nilai 1, maka xj harus bernilai 0, untuk setiap verteks i dan vertex j yang bertetangga. Jadi untuk setiap edge {i, j} ∈ E(G), bentuk persamaannya xi xj = 0 sehingga diperoleh total maksimum nilai xi dan misalkan total nilainya adalah bilangan bulat k. Sehingga optimisasi kombinatorialnya yang diperoleh adalah: Fungsi tujuan maksimumkan k Kendala x2i − xi = 0, untuk setiap vertex i ∈ V (G) (2.1) xixj = 0, untuk setiap edge {i, j} ∈ E(G) n X
xi = k
i=1
Masalah Cost Multicommodity Flow merupakan masalah network (graph) tak berarah (V, E) dengan himpunan verteks V dan himpunan edge E, misalkan n = |V | dan m = |E| . Misalkan pada sebuah network terdapat K buah flow komoditi, dan setiap komoditi k ∈ K, mempunyai sources dan sinks. Misalkan vektor persediaan dinotasikan dengan bki , i ∈ V.ϕij (0) = 0, untuk {i, j} ∈ E. Untuk sebuah edge {i, j} ∈ E dan xkij menyatakan flow dari comoditi k dari i ke j, dan xkji gi adalah flow dengan arah
18 berlawanan atau menyatakan flow untuk comoditi k dari j ke i. Total cost dari route flow pada edge {i, j} adalah ϕij
K X
! k
xkij + xji
k=1
Route Flow pada setiap komoditi yang memenuhi permintaan pada semua sinks dengan meminimalkan total cost route, sehingga optimisasi kombinatorial dari masalah ini adalah : Fungsi tujuan Minimum
P
ϕij
{i,j}∈E
Kendala
X
xkij −
{i,j}∈E
X
K P
xkij
+
xkji
,
k=1
xkji = bki
i ∈ V dan k ∈ K
{j,i}∈E
xkij , xkji > 0
{i, j} ∈ E dan k ∈ K
2.3 Hubungan Masalah Kombinatorial dengan Optimisasi Kombinatorial Berikut ini disajikan bahwa keberadaan penyelesaian dari suatu masalah kombinatorial suatu graph dapat diketahui berdasarkan keberadaan penyelesaian dari masalah optimisasi kombinatorialnya. Hubungan optimisasi kombinatorial dan masalah kombinatorial bilangan stabil dan bilangan stabil pada suatu disajikan dalam Lemma berikut. Lemma 2.3.1. Suatu graph G(V, E) mempunyai bilangan stabil paling kecil k jika dan hanya jika optimisasi kombinatorial (2.1) mempunyai penyelesaian.
19 Lemma 2.3.2. Suatu graph G(V, E) mempunyai bilangan kromatik paling besar k jika dan hanya jika optimisasi kombinatorial (2.1) mempunyai penyelesaian. Berikut ini adalah syarat perlu dan cukup agar masalah optimisasi kombinatorial bilangan stabil dan bilangan kromatik tidak mempunyai penyelesaian.
2.4 Jaminan Nullstellensatz dan Optimisasi Kombinatorial Loera et al (2008), memperlihatkan bahwa masalah kombinatorial adalah infeasible, yakni jika diperoleh sistem persamaan polinomial J dengan koefisien bilangan kompleks C dengan, J = {f1 (x) = 0, f2 (x) = 0, ..., fr (x) = 0} ⊆ C[x1, ..., xn] tidak punya solusi di C n jika dan hanya jika ada polinomial α1 , α2, ..., αr ∈ C[x1, x2, ..., xn] sedemikian hingga
P
αi fi = 1. Untuk mencari polinomial α1 , α2, ...
, αr ∈ C[x1, x2, ..., xn] digunakan sebuah Algoritma yang disebut Nullstellensatz certificates. Berikut adalah hasil penelitian yang diperoleh Loera, et al.(2008), yang menyatakan bahwa graph komplit dengan vertex lebih besar atau sama dengan empat tidak mempunyai bilangan kromatik sama dengan tiga. Polinomial α1 , α2, ..., αr ∈ C[x1, x2, ..., xn] sedemikian hingga
P
αi fi = 1.
Teorema 2.4.1 : Untuk graph komplitKn dengan n ≥ 4, tidak mempunyai bilangan kromatik sama dengan 3.
20 Bukti: Dari (2.2) diperoleh persamaan polinomial dari graph komplit Kn yang mempunyai bilangan kromatik 3 yaitu, f1 (x) = (x31 − 1) = 0 , f2(x) = x24 + x2 x4 + x22 = 0, . . . , f4 (x) = x23 + x1x3 + x21 = 0 terdapat jaminan Nullstellensatz untuk graph berdegree tepat sama dengan 4 atau 4 4 x 9 4
terdapat g1 (x) = (x31−1), g2 (x) =
− 59 x34x2 − 29 x24 x2x1 + 29 x24 x3x1 , . . . , g4 (x) =
(− 13 x44 − 13 x34x2 ) sedemikian hingga g1 (x)f1(x) + ... + g4 (x)f4(x) = 1 sehingga diperoleh jaminan Nullstellensatz, akibatnya untuk graph komplit Kn dengan n ≥ 4 tidak mempunyai bilangan kromatik sama dengan 3, karena ada polinomial g1 , g2 , g3 ∈ R[x] sedemikian hingga
3 P
gi fi = 1.
i=1
2.5 Definisi dan Notasi Definisi 2.5.1 : Polinomial f dengan variable x1 , . . . , xn dan koefisien atas Z adalah kombinasi linear berhingga dari monomial-monomial, dinotasikan dengan aα ∈ Z, f =
P
aα xα,
α
Definisi 2.5.2 : Misalkan fungsi f : S → R. Matriks turunan ordo dua ( Matriks Hess) dari f (x) pada x∗ adalah
∂ 2f |x = x∗ H|x = x = ∂xi∂xj ∗
Misalkan Rn adalah ruang Eucledian dimensi n. Vector x ∈ Rn dinotasikan sebagai vektor kolom dengan ukuran n × 1, sedangkan vektor baris dinotasikan dengan xT . Akibatnya perkalian vektor baris dengan vektor kolom menghasilkan opersai dot produk biasa. Notasi Subscripts menyatakan koordinat vector, superscripts
21 digunakan untuk barisan. Barisan vector di ditulis sebagai {xk } untuk k = 0, 1, ... atau disederhanakan {xk }. Suatu sub barisan ditulis {xk } untuk k ∈ K, dengan k ∈ {1, 2, 3 . . .}. Suatu barisan {xk } di Rn dikatakan konvergen ke x ditulis xk → x untuk k ∈ K. Suatu vector yang koordinatnya semuanya 1, dinotasikan dengan e. Jika x ∈ Rn dan x ≥ 0 berarti untuk setiap i = 1, 2, . . . , n, dan xi ≥ 0, 0 6= x berarti ada i sehingga xi 6= 0 dan suatu barisan titik-titik {xk } di R1 dikatakan monoton naik jika xk ≤ xk+1 untuk semua k dan dikatakan monoton turun jika xk ≥ xk+1 .
