## METODE RELAKSASI LAGRANGE UNTUK MENENTUKAN SOLUSI PROGRAM BILANGAN CACAH

## Susi Setiawani
Program Studi Pendidikan Matematika FKIP Universitas Jember
Abstract. When  the  Integer  Programming  (IP)  has  several  constraints,  we  need  to reduce the constraints for getting feasible solution in a relative short time. One of the available  methods  is  the  Lagrange  relaxation  method,  that  reduces  constraints  by including  complicated  constraints  set  into  the  objective  function  as  penalty  with respect to the set of nice constraints. If the constraints and  values are chosen well, it tends  to  be  a  reasonably  tightest  bound  in  finding  optimal  solution  and  solving  IP quickly.  The purpose of this paper is to discuss how to solve IP by using Lagrange relaxation approach, find out relation among optimal solution of Linear programming, IP  and  relaxation  Lagrange  (dual  Lagrange),  and  understanding  this  method  via  an example.
Keywords: Lagrange Relaxation , Integer Programming
MSC 2020 ( https://zbmath.org/classification )

## 1. Pendahuluan
Program    (linier) bilangan cacah ( Integer  Programming /  IP) merupakan salah satu  kasus dari  program  linier  ( Linier  Programming /LP)  yang  semua  variabelnya  bilangan  cacah. Berdasarkan  pembatasan  variabel,  IP  terbagi  3  yaitu  IP  murni  (semua  variable  bilangan cacah),  IP  campuran  (hanya  sebagian  variabel  yang  bilangan  cacah)  dan  IP  nol-satu (variabel  hanya  bernilai  nol  dan  satu)  [6].  Perumusan  Problem  Bilangan  Cacah  adalah sebagai berikut :
Z IP = max ( C T x ) sebagai fungsi tujuan dengan himpunan fungsi kendala :
A x  b dimana x  R + n ,  x bilangan  cacah, C T ,  A,  b adalah  matriks  koefisien  bilangan  cacah berukuran (1 x n ), m x n, m x 1.[4]
Penyelesaian IP sama dengan mengendorkan IP menjadi LP atau disebut juga dengan LP relaksasi,  dimulai  dengan  mencari  ruang  penyelesaian  layak  ( feasible ),  tetapi  karena adanya  persyaratan  bilangan  cacah  maka  akan  muncul  batasan  tambahan  yang  akan menyebabkan suatu pengurangan dari ruang penyelesaian layak [6]. Penyelesaian LP dapat dilakukan  dengan  metode  grafik  (jika  variabel  hanya  2),  jika  lebih  dari  2  variabel
diselesaikan  dengan  metode  simplex  atau  dapat  menggunakan  bantuan  komputer  untuk mencari  penyelesaian  optimal.  Ada  banyak  software  komputer  untuk  menyelesaikan program linier diantaranya TORA, LINDO dan LINGO, tetapi hanya untuk variabel yang terbatas.
Ada  beberapa  metode  penyelesaian  IP  yaitu  metode  Irisan  (contohnya  Gomory),  search (contohnya Branch  and  Bound (BB))  dan  Heuristik  [2].  Penyelesaian  dengan  relaksasi Lagrange  dikembangkan  diawal  tahun  70an,  merupakan  dasar  pengembangan  metode heuristik. Metode ini diterapkan untuk mencari batas yang ketat pada metode Branch and Bound [7].
Ada  kalanya  suatu  himpunan  fungsi  kendala  terlalu  kompleks  sehingga  sulit  untuk diselesaikan  sehingga  problem  harus  dikendorkan  atau  di  relaksasi.  Metode  Lagrange relaksasi  akan  membagi  2  bagian  besar  himpunan  fungsi  kendala  yaitu  kompleks  dan mudah  ( nice )  [1].  Tidak  seperti  metode  lain  yang  menambah  fungsi  kendala  untuk mendapat  solusi  optimal,  metode  ini  justru  mereduksi  fungsi  kendala  dengan  memilih himpunan  fungsi  kendala  kompleks  menjadi  bagian  fungsi  tujuan.  Dengan  berkurangnya fungsi  kendala,  tentu  akan  mereduksi slack  variable dan surplus  variable (pada  metode simpleks),  dan  mereduksi  garis  (pada  metode  grafik)  sehingga  solusi  optimal  akan  lebih cepat di peroleh.
Artikel ini mencoba melihat 1) relaksasi Lagrange sebagai pendekatan pemecahan masalah IP  dengan  membuktikan  sebuah  teorema,  2)  bagaimana  hubungan  antara  penyelesaian optimal dari program linier, program bilangan cacah dan relaksasi Lagrange dalam hal ini bentuk  dual  Lagrange  dan  3)  aplikasi  pada  sebuah  contoh  dengan  metode  grafik  untuk lebih memahami metode relaksasi Lagrange.

## Program Bilangan Cacah
Himpunan  fungsi  kendala  dibagi  menjadi  himpunan  fungsi  kendala  yang  kompleks  dan mudah, sehingga menurut Achuthan [1] Problem Bilangan Cacah dapat dirumuskan ulang sebagai berikut :
(IP)
Z IP = max ( C T x )
dengan kendala :
A 1 x  b 1 ( m 1 himpunan kendala yang kompleks)
A 2 x  b 2 ( m 2 himpunan kendala yang mudah)
dimana x  R + n ,  x bilangan  cacah, C T ,  A,  b adalah  matriks  koefisien  bilangan  cacah berukuran (1 x n ), m x n, m x 1  dan m jumlah anggota himpunan kendala.

## Fungsi Lagrange
Misalkan masalah dengan fungsi tujuan Max z = f ( X ) dan fungsi kendala g ( X )  k, dimana k adalah konstanta dan X merupakan himpunan variabel bebas ( x 1 , x 2,  , x n ). Budnick, dkk mendefinisikan Fungsi Lagrange dari masalah tersebut adalah :
L( X ,  ) = f ( X ) –  [ g ( X ) - k ]
Variabel  disebut pengali  Lagrange  ( Lagrange  multipliers ) .  Fungsi  kendala  [ g ( X )  - k ] diperlukan  sama  dengan  nol,  berupa  suatu  nilai  sehingga  ruas  [ g ( X )  - k ]  =  0  . Konsekwensinya  nilai  fungsi  Lagrange  yang  baru  sama  dengan  nilai  fungsi  tujuan.  * merupakan tingkat perubahan dalam nilai optimal dari fungsi tujuan dengan fungsi kendala ketika  variabel  yang  lain  tetap,  yang  diperoleh  dari k L   ) , (
* *  X .  Interpretasi  harga  * dimana  L( X ,  ) = f ( X )  –  [ g ( X ) - k ] dapat  dilihat pada Table 1. Jika f ( X ) optimal maka L( X ,  )  akan  optimal.  Tentunya  penurunan  nilai  optimal  L  tidak  dikehendaki,  sehingga kita harus menghindari penurunan k , sehingga diperlukan relaksasi kendala.
Tabel 1. Interpretasi nilai  * A RAH  * Kenaikan konstanta k Penurunan konstanta k Positif Kenaikan f ( X ) optimal Penurunan f ( X ) optimal Negatif Penurunan f ( X ) optimal Kenaikan f ( X ) optimal

## Metode Relaksasi Lagrange
Metode  relaksasi  Lagrange  merupakan  salah  satu  metode  penyelesaian  heuristik  untuk menyelesaikan  masalah  optimasi  combinatorial  kompleks  ( complex  combinatorial optimization )  dan  IP.  Metode  ini  merupakan  strategi  penyelesaian  umum  untuk menyelesaikan  program  matematika  dengan  menyederhanakan  masalah  dengan menggunakan struktur khusus. Penyederhanaan masalah dapat dilakukan dengan beberapa cara  sehingga  pendekatan  solusi  sangat  fleksibel  [5].  Relaksasi  Lagrange  menyelesaikan sub  masalah  dalam  metode Branch  and  Bound sebagai  model  yang  terpisah.  Dan  dapat mengembangkan  batasan  dengan  batas  yang  ketat  pada  nilai  optimal  fungsi  tujuan  [3]. Untuk mendapatkan bentuk relaksasi Lagrange terlebih dahulu dibuat bentuk umum dari IP yaitu IP(Q) agar dapat mengendorkan/ merelaksasi program bilangan cacah di atas, yaitu :
(IP(Q))
Z IP = max ( C T x )
dengan kendala :
A 1 x  b 1 ( m 1 kendala yang kompleks) dan x  Q
dimana Q = { x  R + n : A 2 x  b 2 dan x bilangan bulat}   , [1]

## Primal Relaksasi Lagrange
Dengan  menggunakan  fungsi  Lagrange  dan  mengganti  L(X,  )  dengan Z RL (  )    maka pengendoran  IP(Q)  atau  disebut  juga Relaksasi  Lagrange (RL(  ))  atau  bentuk  primal relaksasi Lagrange (RL(  )) dari IP(Q) ) terhadap A 1 x  b 1 dalam Achuthan adalah :
RL(  ) :
Z RL (  ) = max { Z(  , x ) : x  Q}
dimana Z(  , x ) = C T x+  ( b 1 – A 1 x ), dan untuk sebarang   R m 1  dan   0.
Atau dapat juga dituliskan sebagai :
Z RL (  )   = ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )} = Max { ( C T -  A 1 ) x +  b 1 : x  Q}     (1) dimana  Conv(Q)  adalah Convexhull (Q)  atau  himpunan  semua  titik  layak  ( feasible )  atau daerah layak.
Fungsi  kendala  kompleks A 1 x  b 1 dari  IP  bukan  sebagai  fungsi  kendala  dalam  RL(  ) tetapi    termasuk  dalam  fungsi  tujuan  dengan  penalty  ( b 1 –  A 1 x ).  Penalty  adalah  fungsi yang dimasukkan ke fungsi tujuan. Karena   0, jika  cukup besar maka A 1 x  b 1 akan memenuhi  untuk  ( b 1 –  A 1 x )  lainnya  mempunyai  bentuk  negatif  dan  fungsi  tujuan mempunyai bentuk penalty negatif.

## Dual Lagrange
Batas  atas  terkecil  Z RL (  *)  dari  Z IP diberikan  oleh  solusi  optimal  *  pada  problem  Dual Lagrange. Sehingga dengan  * didapat pendekatan solusi untuk IP. Dual Lagrange (DL) dari IP(Q) atau primal relaksasi Lagrange terhadap fungsi kendala A 1 x  b 1 didefinisikan sebagai berikut [5]:
(DL) : Z DL = 0   Min {Z RL (  )}
Atau dual Lagrange dari persamaan (2.1) dapat ditulis sebagai [7]
Z DL = 0   Min {Z RL (  )} = 0   Min ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )} (2)
Teorema:
Z DL =Max { C T x : A 1 x  b 1 , x  Conv(Q)} Pembuktian teorema ini pada pembahasan.

## 2. Hasil dan Pembahasan

## Penggunaan Program Bilangan Cacah
Untuk  lebih  memahami  pemakaian  metode  relaksasi  Lagrange  akan  digunakan contoh berikut ini.
(IP) : Z IP = Max 2 x 1 + 5 x 2
dengan kendala
4 x 1 + x 2  28 (3)
x 1 + 4 x 2  28 (4)
x 1 - x 2  1 (5)
x 1 dan x 2 bilangan bulat x 1  0, x 2  0 (6)
Untuk  menyelesaikan  problem  bilangan  cacah  di  atas,  terlebih  dahulu    dikendorkan menjadi program linier, yaitu : Z LP = Max 2 x 1 + 5 x 2 dengan kendala (3), (4), (5) dan
x 1 dan x 2 bilangan  Real, x 1  0, x 2  0 (6)
Karena hanya terdiri dari 2 variabel maka dapat diselesaikan dengan metode grafik (lihat grafik1).  Garis  menunjukkan  fungsi  kendala  dan  garis  titik-titik  adalah  fungsi  tujuan. Daerah poligon ABCEF yang diarsir adalah convex hull Q atau daerah penyelesaian layak yang  konveks  untuk  relaksasi  LP.  Sedangkan  titik  –  titik  bilangan  bulat  di  daerah  layak merupakan  titik  –  titik  bilangan  cacah  yang  mungkin  sebagai  penyelesaian  IP.  Nilai optimal fungsi tujuan dari relaksasi LP berada pada ( x 1 , x 2 ) = (5.6, 5.6) is Z LP = 39.2 di titik E.
Pembulatan titik optimal yaitu (6,6) tidak berada di daerah layak dan (5,5) memberikan Z IP =  37,  bandingkan  dengan  Z IP pada  titik  (4,6)  yaitu  38.  Ini  berarti  penyelesaian  Program bilangan  cacah  tidak  dapat  dilakukan  dengan  pembulatan  titik  optimal.  Untuk  mencari penyelesaian  optimal  IP  dilakukan  dengan  menginvestigasi  titik  –titik  bilangan  cacah ekstrim  yang  terdapat  pada  grafik  1.  Dari  grafik  tersebut  diperoleh  titik  ekstrim (0,0),(1,0),(4,6),(5,5)  dan  (7,0).  Nilai  fungsi  tujuan  pada  setiap  titik  ekstrim  adalah  : Z IP (0,0) =  2 x 1 + 5 x 2 = 2(0) + 5(0) = 0; Z IP (1,0) =   2(1) + 5(0) = 2 ; Z IP (4,6) =  2(4) + 5(6) = 38 ; Z IP (5,5) =  2(5) + 5(5) = 35 dan Z IP (7,0) =  2(7) + 5(0) = 14. Oleh karena itu penyelesaian optimal IP adalah : Z IP (4,6) = 38.

## Pendekatan Relaksasi Lagrange
Ada  sebanyak m = m 1 + m 2 anggota  himpunan  fungsi  kendala.  Semuanya  mempunyai peluang yang sama untuk dikelompokkan sebagai m 1 (fungsi kendala kompleks). Sehingga ada  sebanyak  (2 m –  2)  kemungkinan  relaksasi  Lagrange,  yaitu  semua  anggota  himpunan bagian dari himpunan fungsi kendala kecuali  dan himpunan semesta. Untuk illustrasi di atas  ada  3  fungsi  kendala  sehingga  ada  2 3 -2  =  6  kemungkinan  relaksasi  Lagrange  yang dapat  dibentuk.  Artikel  ini  akan  membahas  2  kasus  dari  6  kasus  yang  mungkin  yaitu pengambilan fungsi kendala 1&2, dan kendala 1 sebagai fungsi kendala kompleks.

## Primal Relaksasi Lagrange
Setelah  memilih  himpunan  fungsi  kendala  kompleks,  pendekatan  relaksasi  Lagrange dilakukan dengan cara:
 membentuk IP(Q) dan RL(  ).
 Mencari harga   0 dengan cara koefisien tiap variable pada fungsi tujuan sama dengan nol .
 Substitusi  pada  Z RL (  )  kemudian  cari  pasangan  variabel  bilangan  bulat  yang bersesuaian yang memberikan harga Z maksimum.
Perhatikan persamaan (2.1), ada 2 kemungkinan nilai Q pada Z RL (  ). Pertama jika Q =  , maka Z RL (  ) = -  untuk semua  sehingga Z DL = -  . Dan kedua jika  Q   , andaikan dinotasikan
 Himpunan titik ekstrim dari Conv(Q) = { x k  R + n : k  K }, dimana K indeks himpunan.
 Himpunan sinar ektrim dari Conv(Q) = { r j  R + n : j  J }, J indeks himpunan. Z RL (  )   = ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )} dapat mempunyai kemungkinan 2 solusi sebagai berikut :
Z RL (  )  =           K k x A b Cx J j r A C k j suatu untuk ) ( suatu untuk 0 ) ( jika tas) tak terba solusi ( 1 1 1 1  
Kasus 1
Fungsi  kendala  (3)  dan  (4)  diambil  sebagai  himpunan  fungsi  kendala  yang kompleks. Sehingga bentuk umum dari  IP untuk kasus 1 adalah : (IP(Q)) : Z IP = Max 2 x 1 + 5 x 2 dengan kendala x 1 - x 2  1   and x  Q Q = { x 1 , x 2  Z 2 + : 4 x 1 + x 2  28 , x 1 + 4 x 2  28 }  
Bentuk Relaksasi    Lagrange  (RL1) dari  IP(Q)  dengan  pengambilan  dual  dua  fungsi kendala  (3) dan (4) sekaligus  :
RL(  1 ,  2 ) :  Z RL1 (  1 ,  2 )  = Q x Max  {2 x 1 + 5 x 2 +  1 (28- 4 x 1 - x 2 ) +  2 (28 - x 1 - 4 x 2 ) } atau
Z RL1 (  1 ,  2 )  = Q x Max  { (2 - 4  1 -  2 ) x 1 + (5 -  1 -4  2 ) x 2 + 28  1 + 28  2 } dengan kendala
x 1 - x 2  1   , x 1 , x 2  Z 2 + , dimana (  1 ,  2  0)
atau Q = { x : x memenuhi fungsi kendala (5) dan x 1 , x 2  Z 2 + } . Q adalah sebuah sinar ekstrim (lihat grafik2), dan Convex hull Q atau Conv (Q) = { x 1 , x 2  Z 2 + : x 1 - x 2  1 }. Atau relaksasi Lagrange untuk kasus ini dapat ditulis kembali sebagai :
Z RL1 (  1 ,  2 )  = max {Z (  1 ,  2 , x )  : x 1 , x 2  Conv(Q)}
Gambar 2. Penyelesaian Z LR1 dengan dual fungsi kendala 1 dan 2
Berikut  ini  akan  dihitung  harga  dengan  cara  koefisien  tiap  variable  sama  dengan  nol, yaitu  (2 - 4  1 -  2 ) = 0 ,  (5 -  1 -4  2 ) = 0,  28  1 = 0 dan  28  2 = 0, diperoleh :
 2 = 2 - 4  1 kemudian 5 -  1 - 4(2 - 4  1 ) = 0   1 = 1/5 dan  2 = 6/5 dan  1 = 0,  2 = 0. Substitusi pasangan  1 ,  2 pada Z RL1 (  1 ,  2 ) dan akan dicari pada titik pasangan bilangan cacah ( x 1 , x 2 ) mana yang memberikan harga maksimum.
 Z RL1 (0,0) = max{2 x 1 + 5 x 2 : x 1 , x 2  Conv(Q)} =  (tidak terbatas).
 Z RL1 (1/5,6/5) = max{{(2 – 4(1/5) - 6/5) x 1 + (5 –1/5 -4(6/5) ) x 2 + 28(1/5) + 28 (6/5) : x 1 , x 2  Conv(Q)}   =  max {5.6 + 33.6 : x 1 , x 2  Conv(Q)} = 39.2 Selanjutnya hitung harga Z yang pada selang  yang telah di cari di atas.
 Untuk 0   1 < 1/5 dan 0   2 < 6/5 , penyelesaian optimal  tidak terbatas atau: Z RL1 (  1 ,  2 ) = tidak terbatas.
 Untuk  1  1/5  dan  2  6/5 , penyelesaian optimal adalah ( x 1 ,0).  Ini  dapat  saja (0,0) atau (1,0) Untuk titik (0,0) adalah :
Z RL1 (  1 ,  2 ) = (2 – 4  1 -  2 )(0) + (5 –  1 -4  2 )(0) + 28  1 + 28  2 = 28  1 + 28  2 Atau untuk titik (1,0) adalah : Z RL1 (  1 ,  2 ) = (2–4  1 -  2 )(1) +(5–  1 -4  2 )(0)+ 28  1 +28  2 = 2–4  1 -  2 +28  1 + 28  2
Kasus 2.
Jika  fungsi  kendala  (3)  dianggap  sebagai  fungsi  kendala  kompleks  maka  bentuk umum dari IP adalah :
(IP(Q)) : Z IP = Max 2 x 1 + 5 x 2 Subject to x 1 + 4 x 2  28 x 1 - x 2  1   dan x  Q
Q = { x 1 , x 2  Z 2 + : 4 x 1 + x 2  28  }  
Dengan Relaksasi Lagrangian (RL2) dari IP di atas yang mempunyai dual kendala (3)  : RL(  ) :  Z RL2 (  )  = Q x Max  {2 x 1 + 5 x 2 +  (28- 4 x 1 - x 2 ) }
atau
Z RL2 (  )  = Q x Max  { (2 - 4  ) x 1 + (5 -  ) x 2 + 28  }
Dengan kendala x 1 + 4 x 2  28 ; x 1 - x 2  1 , x 1 , x 2  Z 2 + ,  dimana (  1 ,  2  0) Perpotongan antara fungsi kendala  (4) & (5) adalah  (6.4,5.4) = D
Q = { x : x memenuhi fungsi kendala 2) dan (3) dengan x 1 , x 2  Z 2 + }yaitu: = {(0,0),(1,0),(0,1),(1,1),(2,1),(0,2),(1,2),(2,2),(2,3),(0,3),(1,3),(2,3),(3,3),(4,3), (0,4),(1,4),(2,4),(3,4),(4,4),(5,4),(0,5),(1,5),(2,5),(3,5),(4,5),(5,5),(6,5), (0,6), (1,6),(2,6),(3,6),(4,6),(0,7)} (lihat titik-titik pada grafik 3).
Conv (Q) = { x 1 , x 2  Z 2 + : x 1 + 4 x 2  28 dan x 1 - x 2  1 }
atau
Z RL2 (  )  = max {Z (  , x )  : x 1 , x 2  Conv(Q)}
Gambar 3. Penyelesaian Z LR1 dengan dual fungsi kendala 1
1) Mencari harga  dan Z RL2 (  ).
Karena (2 - 4  ) = 0 ,  (5 -  ) = 0,   dan  28  = 0, diperoleh  = 1/2 ,  = 5 dan  = 0.
Z RL2 (0) = max{2 x 1 + 5 x 2 : x 1 , x 2  Conv(Q)} =  Z(0,(4,6)) = 38 Z RL2 (1/2) = max{(2 – 4(1/2)) x 1 + (5 –1/2 ) x 2 + 28(1/2) : x 1 , x 2  Conv(Q)} =  max {9/2 x 2 + 14 : x 1 , x 2  Conv(Q)} = Z(1/2,(0,7)) = 45.5 Ringkasan nilai Z RL2 dengan beragam nilai  pada titik ekstrim disajikan tabel berikut :
 Titik Ekstrim Titik Optimal (0,0) (1,0) (4,6) (6,5) (0,7)  = 0 0 2 38 37 35 (4,6)  = ½ 14 14 41 36.5 45.5 (0,7)  = 5 140 122 68 32 140 (0,0) or (0,7)  Untuk 0   < 1/2 , Penyelesaian optimal adalah (4,6):
Z RL2 (  ) = (2 - 4  )4 + (5 -  )6  + 28  = 38 + 6  i)
 Untuk 1/2   < 5 , Penyelesaian optimal adalah (0,7):
Z RL2 (  ) = (2 - 4  )0 + (5 -  )7  + 28  = 35 + 21  ii)
 Untuk   5 , penyelesaian optimal adalah (0,7):
Z RL2 (  ) = (2 - 4  )0 + (5 -  )7  + 28  = 35 + 21  iii)
Atau
 Untuk   5 , mempunyai penyelesaian optimal (0,0):
Z RL2 (  ) = (2 - 4  )0 + (5 -  )0  + 28  = 28  iv)
Karena  persamaan  ii)  dan  iii)  serupa,  perpotongan  antara  persamaan  i)  dan  ii)  atau  iii) adalah 35+21  =38 +6    = 1/5 . Sehingga Z RL2 ( 1/5 ) = 35 + 21  = 35 + 21(1/5) = 39.2 . Perpotongan antara persamaan i) dan iv) adalah 38 + 6  = 28   22  = 38   = 1.72. Sehingga Z RL2 (1.72) = 28  = 28(1.72) = 48.36. Perpotongan persamaan  ii) atau iii) dan iv) adalah 35 + 21  = 28   7  = 35   = 5. Sehingga Z LR2 (5) = 28  = 28(5) = 140 (Sudah dihitung, lihat tabel). Sehingga ketika  = 0 diperoleh batas yang paling ketat.

## Lemma :
LR(  ) adalah relaksasi dari IP(Q) untuk semua   0.
Bukti : Jika x layak di IP(Q) maka x  Q sehingga x layak untuk  LR(  ). Juga Z(  , x ) = C T x+  ( b 1 – A 1 x )  C T x untuk semua x yang layak di IP(Q) karena A 1 x  b 1 dan   0.
3.2.2.  Dual Lagrange Teorema :
Z DL =Max { C T x : A 1 x  b 1 , x  Conv(Q)}
Bukti :
Perhatikan Z RL (  ),  relaksasi  Lagrange  adalah Z RL (  )  =  max  {  Z(  , x )  : x  Q}  atau  dapat dituliskan sebagai : Z RL (  )   = Max { ( C T -  A 1 ) x +  b 1 : x  Q}
= ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )}
Oleh karena itu Z DL = 0   Min {Z RL (  )} = 0   Min ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )} dimana Q = { x  R + n : A 2 x  b 2 dan x bilangan bulat} Jika Q =  , maka Z RL (  ) = -  untuk semua  sehingga Z DL = -  . Jika  Q   , andaikan dinotasikan
 Himpunan titik ekstrim dari Conv(Q) = { x k  R + n : k  K }, dimana K indeks himpunan.
 Himpunan sinar ektrim dari Conv(Q) = { r j  R + n : j  J }, J indeks himpunan.
Z RL (  )   = ) ( Max Q Conv x  { C T x +  ( b 1 -  A 1 x )} dapat mempunyai solusi sebagai berikut :
Z RL (  )  =   
       K k x A b Cx J j r A C k j suatu untuk ) ( suatu untuk 0 ) ( jika tas) tak terba solusi ( 1 1 1 1  
Sehingga Dual Lagrange dapat dituliskan kembali sebagai berikut :
Z DL = 0   Min K k  Max { C T x k +  ( b 1 -  A 1 x k )} dengan kendala ( C -  A 1 x ) r j  0, j  J,   0 Z DL =    , Min dengan kendala  +  ( A 1 x k – b 1 )  C T x k , k  K
( C 1 -  A 1 ) r j  0 , j  J yaitu :
Z DL =    , Min
Dengan kendala  +  ( A 1 x k – b 1 )  C T x k , k  K
 A 1 ) r j  C r j  0 , j  J ;   0 Misalkan  k untuk k  K    dan  j untuk j  J  adalah  variable  dual  yang  berasosiasi (berhubungan) dengan fungsi kendala primal. Dual program linier di atas adalah :
Z DL = Min  = Max C T            K k J j j j k k r x   dengan kendala 1    K k k 
A 1            K k J j j j k k r x 
  b 1         K k k   k ,  j  0, k  K  dan j  J Maka Z DL = Max { C T x : A 1 x  b 1 , x  Conv(Q)}

Dari pembuktian teorema di atas dapat dikatakan bahwa Dual  Lagrange dapat digunakan untuk pendekatan penyelesaian program bilangan cacah.
Dual Lagrange untuk contoh di atas adalah sebagai berikut ini.

## Kasus 1
Z DL1 = 0 , 2 1    Min {Z RL1 (  1 ,  2 )} = 0 , 2 1    Min { Z RL1 (0,0),Z RL1 (1/5 , 6/5)}
= 0 , 2 1    Min {tidak terbatas,  Z RL1 (1/5 , 6/5)}
= 0 , 2 1    Min {  , 2 – 4(1/5) - 6/5 + 28(1/5) + 28(6/5) }
= 0 , 2 1    Min {  ,  39.2} = 39.2
Nilai fungsi optimal  Z DL1 adalah Z DL1 = 39.2

## Kasus 2.
Dual  Lagrange (DL2) yang diperoleh dari (RL2) adalah : Z DL2 = 0   Min {Z RL2 (  )}= 0   Min {Z RL2 (0), Z RL2 (1/5), Z RL2 (1/2), Z RL2 (1.72), Z RL2 (5)}
= 0   Min {38, 39.2, 45.5, 48.36, 140} = 38
Nilai fungsi  optimal  Z DL1 adalah Z DL2 = 38
Hubungan LP, IP dan DL
Z IP = S x  Max C T x = ) ( Max S Conv x  C T x
dan Z DL = Max { C T x : A 1 x  b 1 , x  Conv(Q)} dimana  S = { x  R + n : A 1 x  b 1 , A 2 x  b 2 , x bilangan bulat} Q = { x  R + n : A 2 x  b 2 , x bilangan bulat} Hasil : Z IP = Z DL untuk semua c, jika dan hanya jika Conv(Q  { x  R + n : A 1 x  b 1 }) = Conv(Q)  { x  R + n : A 1 x  b 1 } 
Conv(S) = Conv(Q  x  R + n : A 1 x  b 1 )  Conv(Q)  { x  R + n : A 1 x  b 1 }  { x  R + n : A 1 x  b 1 , A 2 x  b 2 }
Maka dapat dikatakan hubungan antara solusi optimal untuk program bilangan bulat (Z IP ) , dual Lagrange (Z DL ) dan Program Linear(Z LP ) adalah Z IP  Z DL  Z LP
Maka  untuk  kasus  1) Z DL1 = Z LP atau  nilai  fungsi  optimal  dari  dual  Lagrange  1  sama dengan nilai optimal fungsi relaksasi program linear. Sedangkan pada kasus 2) 38  39.2  Z DL2  Z DL1 atau  nilai optimal fungsi dari dual Lagrange terhadap fungsi kendala (3) lebih kecil nilai optimal fungsi dual Lagrange 1 terhadap fungsi kendala  (3) dan (4).
Dari  investigasi  contoh  di  atas,  ketika  =  0  (batas  terketat  untuk  kasus  2)),  diperoleh penyelesaian  optimal  untuk  dual  Lagrange  (DL2)  pada  titik  (4,6)  yaitu: Z DL2 (  )  = 38. Sehingga Z IP =  Z LD2 atau nilai optimal fungsi dual Lagrange 2 terhadap fungsi kendala (3) sama  dengan  nilai  optimal  fungsi  program  bilangan  cacah.  Jadi  secara  keseluruhan hubungan antara solusi dari program linier, program bilangan cacah dan relaksasi Lagrange
pada contoh di atas adalah Z LP = Z DL1  Z DL2 = Z IP .

## 3. Kesimpulan
Relaksasi  Lagrange  sebagai  bentuk  primal  dan  dual  Lagrange  dapat  digunakan  sebagai pendekatan  pemecahan  masalah  IP.  Hubungan  antara  penyelesaian  optimal  dari  program linier, program bilangan cacah dan relaksasi Lagrange dalam hal ini bentuk dual Lagrange adalah Z LP  Z DL  Z IP . Investigasi contoh dengan metode grafik diperoleh Z LP = Z DL1 = 39.2 untuk kasus 1 dan Z DL2 = Z IP = 38 untuk kasus 2. Hubungannya adalah Z LP = Z DL1  Z DL2 = Z IP . Sehingga penyelesaian optimal terdapat pada titik (4,6) dengan  nilai optimal fungsi tujuan program bilangan cacah adalah 38.

## Daftar Pustaka
[1] Achuthan, N.R., (2003), Combinatorial Optimation, Lecture Note . Curtin University of Technolgy, Perth.
[2] Budnick F.S, Mc Leavey D, dan Majena R., (1998), Principles of Operations Research for Management . Second edition . Irwin, RD Illinois, USA.
[3] Hillier F.S and Lieberman G.J., (2001), Introduction to Operation Research. Seventh edition, Mc-Graw Hill Companies, USA.
[4] Nasendi  B.D  dan  Anwar  E.,  (1985), Program  Linier  dan  Variasinya. Gramedia, Jakarta.
[5] Postech  I.E  and  Kangbok,  L.,  (2000), Lagrangian  Relaxation  and  Network Optimization Network Flows chapter 16 .
[6] Siagian, P., (1987), Penelitian Operasional. UI Press, Jakarta.
[7] Slyke  R.V. Lagrangian  Relaxation  and  Duality. Htttp://cis.prog.edu/rvslyke  /ma614 /lagrange.pdf. Diakses tanggal 1 Juli 2005.