III RELAKSASI LAGRANGE Relaksasi Lagrange merupakan salah satu metode yang terus dikembangkan dalam aplikasi pemrograman matematik. Sebagian besar konsep teoretis dari banyak aplikasi menggunakan metode ini, salah satunya adalah integer programming dengan melibatkan kendala yang ada. Ide dari permasalahan relaksasi Lagrange berawal dari metode penalti. Metode penalti ini merupakan suatu metode yang digunakan untuk mencari solusi hampiran dari masalah pemrograman berkendala. Pada permasalahan relaksasi Lagrange, kendala yang direlaksasi digantikan dengan suku penalti pada fungsi objektifnya dengan melibatkan kendala yang direlaksasi dan variabel masalah dual. Berikut ini akan disampaikan rumusan secara umum konsep dari relaksasi Lagrange, kemudian aplikasinya pada suatu contoh kuantitatif (numerik) masalah integer programming. Misalkan diberikan masalah maksimisasi integer programming sebagai berikut: max (* (P) terhadap +* " , ©* " ª * # - dan integer,
dengan * adalah vektor berukuran / , , adalah vektor berukuran . / , ª adalah vektor berukuran « / , + merupakan matriks berukuran . / , dan © merupakan matriks berukuran « / . Matriks + dan matriks © merupakan matriks kendala, dengan . " dan « " @ Untuk memformulasikan masalah relaksasi Lagrange, misalkan kendala yang akan direlaksasi (dilonggarkan) adalah +* " ,, dan didefinisikan ¬ sebagai pengali Lagrange yang merupakan vektor taknegatif berukuran . / . Dengan memasukkan ¬ , 2 +* ke dalam fungsi objektif (P) dan kendala +* " , dihilangkan, maka diperoleh permasalahan relaksasi Lagrange dari masalah (P) yaitu: ¬ max terhadap
(* ¬ , 2 +* -”® ©* " ª * # - dan integer,
dengan ¬ # -. Karena +* " , dan ¬ # -, maka ¬ , 2 +* # -, sehingga jika kendala +* " , dilanggar (berarti +* Q ,) maka
¬ , 2 +* " - yang akan mengurangi nilai . Suku ¬ , 2 +* merupakan suku penalti. Selain itu, karena ¬ , 2 +* # - maka solusi optimum dari masalah ini untuk suatu nilai ¬ # -, misalkan *— , merupakan batas atas dari atau ¬ # (*—
¬ , 2 +*— # (Fisher 1985). ¬ merupakan batas
Dengan demikian, atas dari .
Ada beberapa metode yang telah dikembangkan untuk mencari solusi pengali Lagrange dari permasalahan relaksasi Lagrange pada model integer programming, di antaranya metode subgradien dan metode branch and bound (Fisher 1985). Masalah relaksasi Lagrange memiliki keterkaitan dengan variabel masalah dual. Jika kendala +* " , pada masalah (P) direlaksasi, maka terdapat suatu variabel dual ¬ yang berpadanan dengan kendala tersebut. Karena ¬ , 2 +* # -, maka nilai ¬ yang baik untuk menentukan solusi optimum dari (P) adalah ¬ yang meminimumkan ¬ . Jadi, ¬ merupakan solusi dari masalah min ¬ terhadap ¬ # -. Berikut ini diberikan contoh numerik untuk memahami konsep relaksasi Lagrange. Contoh 16 Misalkan diberikan sebagai berikut: &
…
max terhadap „
&" ¯
• ¯ " integer, •
:
permasalahan :
" & " " : :
IP
(1) (2) (3) (4) (3.1) (5) (6)
Jika kendala (2) direlaksasi, maka formulasi masalah relaksasi Lagrangenya menjadi max
terhadap
… & C &2 „ …2„ &2 " "
:
&2 :2:
: (3) (4)
&
D
12
&" ¯" , • ¯ integer, • dengan # &.
: :
(5) (6)
Sebelum menyelesaikan masalah IP (3.1) dengan menggunakan relaksasi Lagrange, maka berikut ini diberikan ilustrasi beberapa nilai pengali Lagrange yang meminimumkan fungsi objektif yang diperoleh dari hasil coba-coba, dengan solusi optimum ¯ pada Tabel 2 diperoleh dengan menggunakan software LINDO 6.1 (lihat Lampiran 2). Tabel 2 Solusi Lagrange yang mungkin dan nilai variabel dualnya Solusi Lagrange LRu u 0 6 5 8 3 2 1
½ ¾
1 0 0 0 0 0 0 0 1 1 0 1 1
0 0 0 1 0 1 1 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 1 1 1
20 60 50 50 80 34 26 18 18 18 18 19 18.5
Nilai fungsi objektif solusi fisibel masalah (P) (=Z) 0 0 10 0 10 10 10 16 14
Nilai pada Tabel 2 diperoleh dari hasil substitusi nilai ¯ pada fungsi objektif (persamaan (1)). Jika &, diperoleh solusi optimum yaitu &, dengan nilai fungsi objektif & &. Solusi & bukan merupakan solusi fisibel dari masalah IP (3.1), karena nilai-nilai ¯ tersebut tidak memenuhi kendala IP (3.1) yaitu kendala (2). Begitupun untuk
, dan
, solusi relaksasi Lagrange bukan solusi fisibel untuk IP (3.1). Jika …, diperoleh solusi optimum relaksasi Lagrange yaitu &, dengan nilai fungsi objektif … …&, dan nilai fungsi objektif solusi fisibel &. Hal yang sama jika „, diperoleh solusi optimum relaksasi Lagrange yaitu &. Dengan demikian, . dipilih yang meminimimumkan
Dengan cara yang serupa, diperoleh nilai-nilai dan solusi fisibel untuk yang lain dengan hasilnya pada Tabel 2. Pada Tabel 2, jika pengali Lagrange < maka terdapat dua solusi Lagrange alternatif dengan nilai fungsi objektif < <&. Solusi Lagrange pertama diperoleh dari output software LINDO 6.1 (lihat Lampiran 2), dengan solusi optimum relaksasi Lagrange yaitu & sehingga nilai fungsi objektif solusi fisibel &. Untuk solusi Lagrange alternatif kedua diperoleh dari hasil coba-coba yaitu dengan menyubstitusikan semua kemungkinan nilai ¯ yang memenuhi pada fungsi objektif semua kendala. Solusi Lagrange alternatif kedua diperoleh , & sehingga nilai fungsi objektif solusi fisibel &. Pada Tabel 2, jika pengali Lagrange maka terdapat empat solusi Lagrange alternatif dengan nilai fungsi objektif „. Solusi Lagrange pertama diperoleh dari output software LINDO 6.1 (lihat Lampiran 2), dengan solusi optimum relaksasi Lagrange yaitu , & sehingga nilai fungsi objektif solusi fisibel &. Solusi Lagrange alternatif lainnya diperoleh dari proses coba-coba juga yaitu dengan menyubstitusikan semua kemungkinan nilai ¯ pada fungsi objektif yang memenuhi semua kendala (lihat Tabel 2) dengan nilai „. Solusi Lagrange alternatif ketiga (lihat Tabel 2) bukan solusi fisibel untuk IP (3.1) karena nilai-nilai ¯ tersebut tidak memenuhi kendala IP (3.1). Dari hasil coba-coba tersebut diperoleh batas nilai 18 yang merupakan nilai minimum yang diperoleh dengan fungsi objektif . Untuk meyakinkan hal tersebut, maka perlu ditunjukkan bahwa 18 adalah nilai dengan optimum fungsi objektif mengamati grafik fungsi nya. Jika semua kemungkinan solusi ¯ pada Tabel 2 disubstitusikan pada fungsi objektif masalah relaksasi Lagrange, maka diperoleh beberapa fungsi linear dari yang diberikan pada Tabel 3.
13
Tabel 3 Fungsi linear dari Solusi masalah relaksasi Lagrange LRu x1 = x2 = x3 = x4 = 0 x2 = 1, x1 = x3 = x4= 0 x2 = x4 = 1, x1 = x3 = 0 x1 = 1, x2 = x3 = x4 = 0 x1 = x4 = 1, x2 = x3 = 0
ZD(u) 10u 10+8u 14+4u 16+2u 20-2u
Karena permasalahan ini adalah memaksimumkan fungsi objektif masalah relaksasi Lagrange, maka fungsi merupakan maksimum dari sekumpulan fungsi linear tersebut, atau maxy &
Grafik fungsi berikut ini.
& „ : & 2 |@
:
…
diberikan pada gambar &
60 50 40 30
&
„
:
:
…
20
&2
10
1
2
3
4
Gambar 11 Fungsi konveks linear . sesepenggal
5
6
ditandai Pada Gambar 11, Fungsi dengan garis tebal. Menurut Teorema 6, merupakan fungsi konveks. Fungsi juga terdiri atas sepenggal-sepenggal beberapa fungsi linear, sehingga fungsi merupakan fungsi linear sesepenggal. Jadi, fungsi adalah fungsi konveks linear sesepenggal dengan &2 m & „ &
n &" P n " "
Dari Gambar 11 dapat dengan mudah terlihat bahwa fungsi minimum saat , sehingga benar bahwa nilai 18 adalah nilai minimum fungsi objektif . Dapat ditunjukkan bahwa fungsi terturunkan pada setiap titik I G ° y <| O untuk (lihat Lampiran 3). Nilai
I G ° y <| dapat diperoleh dari & 2 „ : , dengan ¯ merupakan solusi optimum masalah relaksasi Lagrange (-”± . Sebagai catatan, &2 : diperoleh dari „ kendala (2) yang direlaksasi. O Jika & P P , maka &2 C„ & & : D 2 . Jika O P P <, maka &2 C„ & & : & D „, dan jika Q < maka O & 2 C„ & & & : & D &. Sebagai catatan, solusi nilai-nilai ¯ tersebut dapat dilihat pada Tabel 2. Secara umum, gradien fungsi pada titik-titik terturunkan diberikan oleh +* 2 , (Fisher 1985). Pengamatan ini menyarankan untuk mengaplikasikan metode gradien untuk meminimumkan fungsi dengan beberapa penyesuaian di titik-titik tempat fungsi takterturunkan. Di titik-titik tersebut digunakan subgradien sebagai pengganti gradien. Konsep dari metode subgradien disampaikan berikut ini. 3.1 Metode Subgradien Metode subgradien pada permasalahan ini digunakan untuk mencari nilai pengali Lagrange. Pada metode subgradien digunakan vektor +* 2 , yang merupakan gradien dari fungsi , dengan * adalah solusi optimum masalah relaksasi Lagrange LRu. Prosedur untuk menentukan nilai pengali Lagrange dimulai dengan inisialisasi titik awal š & dan digunakan rumus sebagai berikut: ¬
™
s ƒ6 y& ¬ 2
, 2 +* |, (3.2)
dengan adalah step size bernilai skalar positif dan * adalah solusi optimum masalah relaksasi Lagrange (L”± pada iterasi ke- . Berikut ini adalah langkah-langkah penyelesaian masalah maksimisasi relaksasi Lagrange dengan metode subgradien (Freund, 2004) • Langkah 0 (Inisialisasi) Diawali dengan š &, dan dipilih step size positif y |²wš . • Langkah 1 (Penentuan subgradien) Gradien +* 2 , ditentukan untuk setiap iterasinya, dengan mencari solusi ¯ terlebih dahulu dari masalah relaksasi Lagrange. Jika +* 2 , &, maka iterasi dihentikan.
14
• Langkah 2 (Penentuan nilai ) Di setiap iterasi, digunakan persamaan (3.2) untuk memperoleh nilai . Kembali ke Langkah 1.
&
60
&
50
:
40
Pada bagian ini akan dibahas penentuan solusi nilai pengali Lagrange untuk masalah maksimisasi relaksasi Lagrange dari masalah IP (3.1) dengan menggunakan metode subgradien. Nilai-nilai tersebut ditentukan dari beberapa kasus barisan nilai . Berikut ini diberikan nilai-nilai yang diperoleh dari beberapa variasi nilai . Nilainilai untuk , diperlihatkan pada Tabel 4, dan rinciannya dapat dilihat di Lampiran 4 bagian 1. Misalkan , dan misalkan š maka dengan menggunakan persamaan s ƒ6 y& ¬ 2 , 2 +* | ¬ ™ diperoleh s ƒ6y& š 2 š , 2 +*š | s ƒ6y& & 2 & 2 J„ & & : K | s ƒ6y& |
&,
Catatan: , 2 +*š diberikan dari kendala yang direlaksasi (kendala (2)) yaitu &2 „ : , dengan solusi * merupakan solusi optimum masalah relaksasi Lagrange yang diperoleh saat & (lihat Lampiran 2 atau Tabel 2). Tabel 4 Metode subgradien dengan nilai untuk semua k
uk
tk x1 x2 x3 x4
0
0
1 1
0
0 1
20
Titik (uk,ZD(uk)) C
1
2
1 0
1
0 0
26
D
ZD(uk)
2
0
1 1
0
0 1
20
C
3
2
1
0
1
0 0
26
D
4
0
1
1
0
0 1
20
C
5
2
1
0
1
0 0
26
D
6
0
1
0
0 1
20
C
Untuk kasus pertama ini, metode subgradien menghasilkan & dan . Berikut ini diberikan ilustrasi dari hasil iterasi , . pada metode subgradien dengan
30 20
´
g
…
„µ
µ µ
:µ µ
µ &2 µ
10
1
2
3
4
5
6
Gambar 12 Ilustrasi hasil iterasi pada metode subgradien dengan , . Karena iterasi tersebut menghasilkan nilai pengali Lagrange yang berulang-ulang, maka nilai step sizenya perlu diperbaiki. Misalkan nilai step size yang digunakan Dengan cara serupa, dihasilkan nilai yang ditunjukkan pada Tabel 5. Rinciannya dapat dilihat pada Lampiran 4 bagian 2. Tabel 5 Metode subgradien dengan nilai
x1 x2 x3 x4 ZD(uk) kTitik k (u , ZD(u ))
k
uk
tk
0
0
1
1 0
0
1
20
E
1
2
0
0
26
F
0
³:
0 1
2
1 0
0
1
20
E
1 0
0
1
19
G
0
1
3 4 5 6
³
³:
ˆ³„
<³ …
³
³„
³ … 1 0 ³
18.5 1 18.25
H
1 0 0
1 0 0
1 18.125
J
I
Solusi ¯ pada Tabel 5 dapat dilihat pada Lampiran 2 & 5. Untuk kasus kedua ini, nilai konvergen ke 0 (lihat Lampiran 6 bagian 1) dengan nilai berurutan setengah dari nilai sebelumnya. Pada iterasi ini, iterasi pada metode subgradien cukup bagus karena nilai pengali Lagrangenya konvergen ke nilai optimum (lihat Lampiran 6 bagian 2). Berikut ini diberikan ilustrasi dari hasil iterasi pada metode subgradien dengan yang digunakan setengah dari nilai sebelumnya.
15
&
60 50 40 30 20
¹
•
h\ N º
&
„
:
:
… &2
10
1
2
3
4
5
6
Gambar 13 Ilustrasi hasil iterasi pada metode subgradien dengan setengah dari nilai sebelumnya. Sekarang, akan dibahas kasus lain dari barisan nilai , yaitu sepertiga dari nilai sebelumnya, atau . Dengan cara serupa dihasilkan nilai-nilai yang ditunjukkan pada Tabel 6 berikut ini. Rinciannya dapat dilihat pada Lampiran 4 bagian 3. Tabel 6 Metode subgradien dengan nilai
k
k
u
0
0
1
2
2
0
3
2/9
4
8/27
5
26/81
6 80/243 7 242/729
x1 x2 x3
x4 ZD(u ) k Titikk
1
³
1
0
0
1
20
³¶
0
1
0
0
26
L
1
0
0
1
20
K
³„
1
0
0
1 19.55
M
³ :
1
0
0
1 19.41
N
1
0
0
1 19.35
O
1
0
0
1 19.34
P
1
0
0
1 19.33
Q
tk
³ ˆ
³ˆ ¶
k
(u , ZD(u ) )
K
Solusi ¯ pada Tabel 6 dapat dilihat pada Lampiran 2 & 5. Untuk kasus ketiga ini, nilai konvergen ke 0 (lihat Lampiran 6 bagian 3), akan tetapi laju kekonvergen lebih cepat dibandingkan dengan kasus kedua, karena nilai yang digunakan adalah sepertiga dari nilai sebelumnya. Pada iterasi ini, nilai pengali Lagrangenya konvergen ke (lihat Lampiran 6 bagian 4). Akan tetapi, jika maka diperoleh solusi optimum relaksasi Lagrange yaitu , & (lihat Lampiran 5) yang bukan merupakan solusi fisibel dari masalah IP (3.1), karena solusi tersebut tidak memenuhi
kendala (2) pada IP (3.1). Dengan demikian, untuk kasus ketiga ini nilai pengali Lagrange konvergen ke titik yang bukan solusi optimumnya. Berikut ini diberikan ilustrasi dari hasil iterasi pada metode subgradien dengan yang digunakan sepertiga dari nilai sebelumnya. &
60 50 40 30 20 10
-
»¼¾½ qr
&
„
:
:
… &2
1
2
3
4
5
6
Gambar 14 Ilustrasi hasil iterasi pada metode subgradien dengan dengan sepertiga dari nilai sebelumnya. Dengan demikian, pengali Lagrange yang diperoleh dengan menggunakan metode subgradien adalah yang diperoleh bila menggunakan kasus kedua. Menurut Held, Wolfe, dan Crowder (1974), untuk M dan jika kedua kondisi berikut ini dipenuhi, yaitu M & dan (i) (ii) ·%wš % M ¸, maka konvergen ke nilai optimal . Dengan uji deret kekonvergenan pada Tabel 5, diperoleh · % M (lihat Lampiran 6 bagian 5) yang sebenarnya melanggar kondisi kedua. Ini memperlihatkan bahwa kondisi kedua yaitu ·%wš % M ¸ merupakan syarat cukup bagi konvergen ke nilai optimal (Fisher 1985). Terbukti dengan tidak terpenuhi kondisi kedua, iterasi pada metode subgradien diperoleh nilai pengali Lagrange yang konvergen ke nilai optimum . Nilai pada Tabel 4, 5, dan 6 diperoleh dari hasil coba-coba. Pada bagian ini diberikan rumus (Fisher 1985) yang dapat digunakan yaitu: ·x %
¬ 2 — ,% 2 ·¯w z%¯ *¯
@
dengan — adalah nilai fungsi objektif dari ¬ adalah nilai solusi fisibel (P) dan fungsi objektif masalah relaksasi Lagrange dengan nilai ¬ pada iterasi ke- .
16
Untuk menggunakan persamaan (3.3), nilai diperbarui pada setiap iterasinya yaitu dengan menyubstitusikan solusi ¯ yang diperoleh dari masalah relaksasi Lagrange pada fungsi objektif masalah asli (P), sehingga diperoleh nilai — yang baru. Nilai skalar yang dapat digunakan adalah & P " (Fisher 1985). Sering kali, ditentukan dengan permulaan š . Jika tidak ada peningkatan nilai pada dari iterasi ke- , maka dilakukan reduksi terhadap menjadi ¿À @ Aturan dipilih & P " telah dibuat secara empiris dengan baik, meskipun hal ini tidak menjamin bahwa persamaan (3.3) dapat memberikan kekonvergenan nilai pengali Lagrange yang optimum (Fisher 2004). Jika — nilai , maka metode yang biasa ¬ dilakukan untuk memecahkan masalah ini adalah dengan membatasi jangkauan iterasi yang berulang-ulang (Fisher 1985). Sebagai contoh dapat dilihat pada Contoh 18. —
3.2
Perbandingan Masalah Relaksasi Lagrange dengan Pemrograman Linear Relaksasi Berdasarkan Nilai Batasnya
Pada bagian ini akan dibandingkan antara solusi penyelesaian IP dengan relaksasi Lagrange dan solusi penyelesaian IP dengan PL-relaksasi dari permasalahan IP (3.1) berdasarkan nilai batasnya. Contoh 17 Misalkan ÁÂ dinotasikan sebagai nilai optimum dari (P) dengan merelaksasi kendala integernya atau disebut PL-relaksasi. Berikut ini diberikan PL-relaksasi yang diperoleh dari masalah IP (3.1) dengan merelaksasi kendala integernya yaitu: max ÁÂ terhadap „
&"
…
¯
&
" , •
:
:
" & " " :
(1) (2) (3) (3.4) (4) (5)
Solusi optimum PL-relaksasi (3.4) adalah & & &@<, dengan nilai fungsi objektif Á „ yang diperoleh dengan menggunakan software LINDO 6.1 (lihat Lampiran 7). Untuk melakukan perbandingan, tuliskan terlebih dahulu bentuk standar PL dual dari masalah PL-relaksasi (3.4) tersebut. Misalkan à •ƒu à dinotasikan sebagai variabel dual yang berpadanan dengan
kendala (2), (3) dan (4) dan †¯ merupakan variabel dual dari kendala ¯ " , sehingga bentuk PL dual dari masalah PL-relaksasi (3.4) adalah min & terhadap „
Ã
Ã
à † † à à † : à † à à †
†
†
†
# … # & #& #: † † † # &.
†
(3.5)
Solusi optimum PL dual (3.5) adalah à „à † † † † &, dengan nilai fungsi objektif 18 yang diperoleh dengan menggunakan software LINDO 6.1 (lihat Lampiran 7). Pada permasalahan ini terdapat dua fakta. „ sama dengan nilai Pertama, nilai Á batas atas yang diperoleh dari masalah relaksasi Lagrange (maksimisasi IP (3.1) dengan kendala (2) direlaksasi) yaitu „@ Kedua, nilai variabel PL dual dengan pada kendala (2) yaitu † & sama dengan nilai variabel yang meminimumkan batas atas 18 pada masalah relaksasi Lagrange yaitu &. Berikut ini diperlihatkan hubungan dengan Á untuk masalah maksimisasi relaksasi Lagrange. s tu›s ƒ6C(* ¬ , 2 +* Dœ, ¬ # terhadap ©* " ª * # - dan integer; " s tu›s ƒ6C(* ¬ , 2 +* Dœ, ¬ # terhadap ©* " ª * # -;
(PL dual)
(PL dual)
s tuys tu¬, Ī|, ¬ Ä # terhadap Ä© # ( 2 ¬+; s tu¬, Ī, ¬ Ä # terhadap ¬+ Ä© # (. s ƒ6 (* terhadap +* " , ©* " ª * # -. . ÁÂ
Dari uraian di atas, bahwa " ÁÂ . Dengan demikian, ketaksamaan tersebut merupakan relasi antara masalah relaksasi Lagrange dan PL-relaksasi dengan merelaksasi kendala integer. Secara logik, P ÁÂ kondisi bisa saja ÁÂ atau
17
Contoh 18 Dari permasalahan IP (3.1), jika kendala (3) dan (4) direlaksasi maka formulasi masalah relaksasi Lagrangenya menjadi:
(Fisher 1985). Apabila nilai lebih kecil dari nilai ÁÂ maka disebut strictly. akan sama dengan ÁÂ jika solusi Nilai masalah relaksasi Lagrange tersebut nilainya tidak berubah meskipun dihilangkan kendala integernya (Fisher, 1985). Terbukti pada Contoh 17, nilai optimum ÁÂ „ sama dengan batas atas masalah relaksasi Lagrange dengan nilai optimum „ sehingga . ÁÂ
…
C 2 …2 &2 terhadap „ &" ¯ " ,• ¯ integer, • # &, max
Relaksasi Lagrange yang baik adalah relaksasi yang dapat menyelesaikan masalah awal (P), dalam hal ini masalah IP (3.1) (Fisher 1985). Ini berarti, bahwa relaksasi Lagrange yang baik adalah relaksasi yang memberikan solusi batas atas masalah relaksasi Lagrange sama dengan batas nilai fungsi objektif masalah awal (P). Pada pembahasan sebelumnya telah ditunjukkan bahwa batas atas masalah relaksasi Lagrange yang diperoleh dari merelaksasi kendala (2) dari masalah IP (3.1) „. Batas atas masalah relaksasi adalah Lagrange tersebut dapat diperbaiki dengan menggunakan relaksasi Lagrange yang variabel-variabelnya bernilai integer.
& : C 2 D &2 :2
:
:
:
" &
Tabel 7 Aplikasi metode subgradien untuk perbaikan relaksasi u1
u2
0
0
0
1
13
0
Åk
x1
x2
x3
x4
ZD(u1,u2)
Z*
1
1
1
0
0
26
0
1
0
0
0
1
17
4
ZD(u1,u2)
Z*
(fisibel untuk k
u1
u2
2
0
0
3
11
0
(3.6)
dengan merupakan pengali Lagrange taknegatif. Solusi dari masalah relaksasi Lagrange (3.6) mensyaratkan bahwa semua variabel bernilai bilangan bulat nol atau satu. Sebagai catatan, jika digunakan maka akan diperoleh hasil yang berulangulang ke nilai &, & dan tidak diperoleh peningkatan nilai pada dari iterasi ke- (lihat Lampiran 8), maka langkah selanjutnya adalah dilakukan reduksi terhadap menjadi . Secara empirik pada Tabel 7 ditunjukkan aplikasi metode subgradien untuk mencari nilai pengali Lagrange dengan menggunakan persamaan (3.2) dan nilai . Rincian iterasinya dapat dilihat pada Lampiran 9. Sebagai catatan, solusi optimum relaksasi Lagrange yaitu ¯ diperoleh dengan menggunakan software LINDO 6.1 (lihat Lampiran 10).
3.3 Perbaikan Relaksasi Kelebihan merelaksasi lebih dari satu kendala yaitu batas atas masalah relaksasi Lagrange yang diperoleh akan lebih mendekati atau sama dengan nilai batas solusi masalah awal (P). Berikut ini diberikan alternatif relaksasi dari masalah IP (3.1) dengan kendala yang direlaksasi lebih dari satu kendala. Sebagai ilustrasi, berikut ini diberikan contohnya.
k
(2) (5) (6)
D
:
Åk
x1
x2
x3
x4
1
1
1
0
0
26
4
1
1
0
1
0
16
16
(fisibel untuk
…
18
Pada Tabel 7, saat iterasi ke-3 diperoleh dan &, dengan solusi optimum relaksasi Lagrange yaitu &, sehingga nilai fungsi objektif masalah relaksasi Lagrange diperoleh & … dan nilai fungsi objektif solusi fisibel — …. Karena pada iterasi ke-3 diperoleh — & …, maka untuk iterasi nilai ke-4 dan ke-5 serta seterusnya akan diperoleh nilai-nilai pengali Lagrange yang sama nilainya yaitu dan & sehingga untuk memecahkan masalah ini adalah dengan membatasi jangkauan iterasi sampai batas
iterasi ke-3. Dengan demikian, solusi pengali Lagrange yang diperoleh dengan menggunakan metode subgradien adalah dan &, dengan batas atas & … yang nilainya sama dengan nilai fungsi objektif dari solusi fisibel masalah (P) ketika menyelesaikan masalah relaksasi Lagrange tersebut. Dengan demikian, metode relaksasi Lagrange dapat menyelesaikan masalah IP (3.1). Ini berarti, relaksasi Lagrange dapat menyelesaikan masalah awal (P) yaitu masalah integer programming.
IV SIMPULAN DAN SARAN 4.1 Simpulan Masalah integer programming (IP) dapat diselesaikan dengan menggunakan metode relaksasi Lagrange. Ide dari permasalahan relaksasi Lagrange berawal dari metode penalti yang merupakan suatu metode yang digunakan untuk mencari solusi hampiran dari masalah pemrograman berkendala. Pada permasalahan relaksasi Lagrange, kendala yang direlaksasi digantikan dengan suku penalti pada fungsi objektifnya dengan melibatkan kendala yang direlaksasi dan variabel masalah dual. Nilai pengali Lagrange dari masalah relaksasi Lagrange pada model integer programming dapat ditentukan dengan menggunakan metode subgradien. Dengan nilai pengali Lagrange tersebut dapat diperoleh suatu batas atas dari masalah awal (P) sebagai solusi optimum masalah maksimisasi relaksasi Lagrange. Pada permasalahan ini (maksimisasi relaksasi Lagrange), solusi relaksasi Lagrange bisa jadi tidak diperoleh solusi yang optimum. Hal tersebut dikarenakan nilai pengali Lagrange yang diperoleh dengan metode subgradien dimungkinkan merupakan solusi di minimum lokal. Dengan demikian, haruslah
dipastikan bahwa nilai pengali Lagrangenya merupakan solusi di minimum global. Untuk masalah maksimisasi relaksasi Lagrange, nilai optimum fungsi objektif relaksasi Lagrange lebih besar atau sama dengan nilai objektif IP dan nilai optimum fungsi objektif relaksasi Lagrange lebih kecil atau sama dengan nilai objektif PL-relaksasi. Dengan demikian, relaksasi Lagrange merupakan metode yang terbaik untuk menyelesaikan masalah integer programming dibandingkan dengan PL-relaksasi, karena solusi optimum relaksasi Lagrange mendekati solusi optimum masalah IP. 4.2 Saran Pada karya ilmiah ini telah dibahas penyelesaian masalah integer programming dengan metode relaksasi Lagrange. Solusi dari pengali Lagrange diperoleh dengan menggunakan metode subgradien. Penulis menyarankan untuk selanjutnya dilakukan pembahasan mengenai masalah ini dengan solusi pengali Lagrangenya menggunakan metode branch and bound.
