## STUDI MASALAH PEMROGRAMAN GEOMETRIK DENGAN METODE DUAL
(Study on Geometric Programming using Dual Method)

## Fitriya dan Agustina Pradjaningsih
Jurusan Matematika FMIPA Universitas Jember Jl. Kalimantan 37, Jember 68121, Indonesia Email:agustina.fmipa@unej.ac.id
Abstract. Geometric programming is an optimization  technique developed for solving a class of non-linear programming problems. It is used to minimize function which are in the form of posynomial subject to constraints of the same type. To find the solution, this technique consider dual problem that related to primal problem. In this paper, we discuss about minimize solution with constrained of geometric programming problems on the basis of Lagrangian function and Kuhn-Tucker Conditions.
Keywords: geometric programming, posynomial MSC 2020: 90C46

## 1. Pendahuluan
Pemrograman non linier merupakan masalah optimisasi dengan fungsi tujuannya non linier. Pemrograman  geometrik  merupakan  metode    untuk  menyelesaikan  salah  satu  kelas  dari masalah pemrograman non linier yang diperkenalkan pertama kali oleh Clarence Zener dan Richard  Duffin  pada  tahun  1961[2].  Pemrograman  geometrik  digunakan  untuk meminimumkan suatu fungsi tujuan berbentuk khusus yang disebut posinomial. Jika ada kendala maka kendala  juga berbentuk posinomial. Sebuah posinomial mempunyai bentuk
     N j n i a i j ij x c f 1 1 ) ( X
dengan .
1 , 1 , 0 , , 0 N j n i x R a c i ij j        Masalah  minimisasi  ini  selanjutnya disebut masalah primal. Teknik ini menentukan solusi dengan mempertimbangkan masalah dual yang berkaitan dengan masalah primal, yang penyelesaiannya lebih sederhana.
Sebuah fungsi ) ( X f dengan T n x x x ) , , , ( 2 1   X dikatakan mempunyai minimum relatif atau  lokal  di T n x x x ) ,
, , ( 2 1       X jika ) ( )
( h X X     f f untuk  semua
T n j h h h ) , , , , ( 1    h sehingga j h cukup kecil untuk semua j [1]. Titik  X adalah titik maksimum lokal atau relatif jika
) ( ) ( h X X     f f . Fungsi ) ( X f mempunyai minimum
global atau absolut di titik  X jika ) ( ) ( X X f f   untuk setiap X pada daerah asal tempat ) ( X f didefinisikan. Titik  X akan menjadi  titik maksimum global atau absolut dari ) ( X f
jika ) ( ) ( X X f f   .
Misalkan titik n R  2 1 , X X dan S menunjukkan himpunan konveks, secara matematis dapat didefinisikan sebagai berikut:[3]
Jika titik S  2 1 , X X , maka titik S  X 1 0 , ) 1 ( 2 1         X X X
Fungsi ) ( X f dikatakan konveks atau cembung ( convex ) jika setiap dua titik n R  2 1 , X X
dan untuk semua 1 0    , ) ( ) 1 ( ) ( ) ) 1 ( ( 1 2 1 2 X X X X f f f          Fungsi ) ( X f dikatakan konkaf atau cekung ( concave ) jika merupakan negatif dari fungsi konveks.
Teorema  1. Suatu  fungsi ) ( X f adalah  konveks  jika  matrik  Hessian ] / ) ( [ ) ( 2 j i x x f     X X
H adalah semi definit positif.
Teorema 2. Suatu minimum lokal dari fungsi konveks ) ( X f adalah minimum global.
Metode pengali Lagrange merupakan suatu metode yang dipergunakan untuk pencarian titik optimum  dari  suatu  fungsi  dengan  kendala  yang  berbentuk  persamaan.  Permasalahan minimisasi dari fungsi yang kontinu dengan kendala persamaan berbentuk:
minimumkan   X f f  , T n x x x ) , , , ( 2 1   X
dengan kendala   m j g j , , 2 , 1 , 0    X , dengan n m  .
Untuk memecahkan masalah tersebut, kita menyusun fungsi Lagrange sebagai berikut:
      X X     m j j j m n g f x x x L 1 2 1 2 1 , , , , , , ,      
dengan m j j , , 2 , 1 ,
   disebut pengali Lagrange dan m adalah banyaknya kendala. Titik minimum relatif dapat diperoleh dengan menggunakan teorema berikut ini.
Teorema  3. Kondisi  perlu  untuk  fungsi ) ( X f dengan  kendala   , 0  X j g m
j ,
, 2 , 1  
mempunyai  minimum  relatif  di  X adalah  bahwa  turunan  parsial  pertama  dari  fungsi Lagrange  yang  didefinisikan  oleh   m n x x x L L    , , , , , , , 2 1 2 1
   yang  terkait  dengan
masing-masing argumennya harus sama dengan nol.
Teorema 4. Kondisi cukup untuk ) ( X f mempunyai minimum relatif di  X adalah  bentuk kuadratik Q , yang didefinisikan
j i n i n j j i dx dx x x L Q        1 1 2
yang dievaluasi di   X X , definit positif untuk semua nilai d X yang memenuhi kendala.
Jika j i n i n j j i dx dx x x L Q        1 1 2 negatif untuk semua nilai d X maka  X adalah titik maksimum relatif dari ) ( X f . Bentuk kuadratik Q akan definit positif (atau negatif) untuk semua d X bila  setiap  akar  polinomial i z didefinisikan    pada  persamaan  determinan  berikut  adalah positif (atau negatif):[3]
      0 0 0 0 0 0 0 0 0 0 2 1 2 22 21 1 12 11 2 1 2 1 2 22 12 2 22 21 1 21 11 1 12 11        


   
    mn m m n n mn n n nn n n m n m n g g g g g g g g g g g g z L L L g g g L z L L g g g L L z L dengan              X λ , X j i ij j i ij x g g x x L L dan , 2
Kondisi Kuhn-Tucker digunakan untuk optimisasi fungsi dengan kendala pertidaksamaan sebagai berikut:
minimumkan ) ( X f dengan kendala   m j g j , , 2 , 1 , 0    X
Masalah  di  atas  merupakan  masalah  minimisasi  tetapi  kondisi  Kuhn-Tucker  juga  dapat diterapkan  untuk  masalah  maksimisasi.  Kondisi Kuhn-Tucker  merupakan  pengembangan dari  metode  Lagrange.  Kondisi  Kuhn-Tucker  untuk  masalah  minimisasi  di  atas,  dapat dinyatakan sebagai berikut:
                        m j m j g m j g n i x g x f j j j j m
j i j j i , , 2 , 1 , 0 dan , , 2 , 1 , 0 , , 2 , 1 , 0 , , 2 , 1 , 0 1       
Kondisi di atas tidak cukup untuk menjamin suatu minimum relatif di  X . Pada masalah pemrograman konveks yaitu masalah minimisasi dengan fungsi tujuan dan kendala adalah konveks maka kondisi Kuhn-Tucker merupakan kondisi perlu sekaligus kondisi cukup yang menjamin hanya ada satu titik yaitu minimum global [3].

## Bentuk Umum Posinomial
Sebuah posinomial didefinisikan [3]:
          X X X X X N N j j U U U U f         2 1 1 dengan       n i a n a a j a i j j nj j j ij x x x c x c U 1 2 1 2 1  X 1 , 1 , 0 , , 0 N j n i x R a c i ij j       

## Bentuk Umum Pemrograman Geometrik
Terdapat dua macam masalah dalam pemrograman geometrik yaitu:
1. masalah minimisasi tanpa kendala yang dapat dirumuskan sebagai berikut:
tentukan T n x x x ) , , , ( 2 1   X yang meminimumkan fungsi tujuan             N j N j n i a i j j ij x c U f 1 1 1 X X      N j a n a a j nj j j x x x c 1 2 1 2 1 
dengan
R c i j    ij a dan , 0 x , 0 .
2. masalah minimisasi dengan kendala dapat dinyatakan sebagai berikut:
tentukan T n x x x ) , , , ( 2 1   X yang meminimumkan fungsi tujuan
     0 0 1 1 0 ) ( N j n i a i j ij x c f X
dan memenuhi kendala
m k x c g n i a i N j kj k kij k , , 2 , 1 , 1 ) , ( ) ( 1 1          X dengan 0 , , , 0 , 0 0 0      i kij ij kj j x R a R a c c .  Kedua  Masalah  minimisasi  ini  kemudian disebut masalah primal.

## 2. Hasil dan Pembahasan
Pertama-tama fungsi tujuan ) ( X f dimisalkan dengan
  ) ( 0 0 X g x      0 0 1 1 0 ) ( N j n i a i j ij x c f X (1)
Sedangkan fungsi kendala dapat dituliskan dalam bentuk berikut
  m k g f k k k , , 2 , 1 , 0 ) ( 1      X  (2)
k  disebut fungsi tanda dan bernilai +1 atau –1 tergantung apakah 1 atau 1   k g .
Didefinisikan bobot untuk masing-masing suku dalam fungsi tujuan
0 0 1 0 , , 2 , 1 , 0 0 N j x x c n i a i oj j ij        dan 1 0 1 0     N j j (3)
sedang bobot untuk masing-masing suku dalam kendala didefinisikan
       n i k a i kj kj N j m k x c kij 1
, , 2 , 1 ; , , 2 , 1 , 0   (4)
Masalah asal meminimumkan ) ( X f dengan kendala
, 1 atau 1
  k g m k , , 2 , 1   akan berubah  menjadi  meminimumkan 0 x dengan  kendala  (2),  (3)  dan  (4).  Didefinisikan
transformasi eksponensial , i w i e x  n i , , 2 , 1 , 0   . masalah di atas dapat ditulis kembali menjadi Minimumkan 0 w e
dengan kendala
0 1 0 , , 2 , 1 ; exp 0 N j w a c e n i i ij oj oj w                    m k f k N j kj k k , , 2 , 1 , 0 1 1                k n i i kij kj kj N j m k w a c , , 2 , 1 ; , , 2 , 1 ; exp 1               0 1 0 1 0      N j j
Dengan mengambil logaritma, diperoleh
Minimumkan 0 w
dengan kendala 1
0 1 0     N j j 0 1 0 0 0 0 , , 2 , 1 ; ln N j c w w a n i j j i ij               
k n i kj kj i kij N j m k c w a , , 2 , 1 ; , , 2 , 1 ; ln 1
                m k f k N j kj k k , , 2 , 1 , 0 1 1               
Semua  bobot  harus  bernilai  positif  dan
n w w w , , , 1 0  tidak  terbatas  dalam  tanda.  Untuk memecahkan  masalah  dengan  kendala  ini,  disusun  fungsi  Lagrange  dengan
k kj j     dan , , 0 0 adalah pengali Lagrange. Karena m kendala adalah pertidaksamaan agar memenuhi kondisi Kuhn-Tucker, kendala diubah dalam bentuk 0  k f sehingga k  terbatas bernilai  nonnegatif ) , , 2 , 1 , 0 ( m k k     .  Kemudian k k f  ditambahkan  pada  fungsi Lagrange tanpa mengubah nilainya. Fungsi Lagrange untuk masalah tersebut adalah sebagai berikut:
                         m k N j kj k k N j j k w L 1 1 1 0 0 0 1 1 ) ( 0    λ Δ, w,                                                 m k N j n i kj kj i kij k kj N j n i j j i ij j k c w a c w w a 1 1 1 1 1 0 0 0 0 0 ln ln 0    (5)
Pada titik stasioner dari L , didapat
0 w L   =     0 1 0 1 N j oj  (6)
   i w L         0 1 1 1 0 0 , , 2 , 1 , 0 N j m k N j kij k kj ij j k n i a a     (7)
    j L 0 0 0 0 , , 2 , 1 , 0 N j oj j        (8)
    kj L m k N j k kj k kj k k , , 2 , 1 ; , , 2 , 1 , 0            (9)
   0  L      0 1 0 1 N j oj (10)
   k L  m k k N j kj k , , 2 , 1 , 0 1 1              
(11)
   oj L  0 1 0 0 0 0 , , 2 , 1 , 0 ln N j c w w a n i j j i ij                 (12)
Majalah Ilmiah Matematika dan Statistika Volume 15 Nomor 2  2015, 87 – 96 https://jurnal.unej.ac.id/index.php/MIMS/index ISSN 1411-6669
   kj L  m k N j c w a k n i kj kj i kij k , , 2 , 1 ; , , 2 , 1 , 0 ln 1                           (13)
dikenalkan 0  dengan nilai satu dan persamaan (7) dapat ditulis kembali menjadi
     m k N j kij kj k k n i a 0 1 , , 2 , 1 , 0    (14)
Dari persamaan (6), (8) dan (10) diperoleh
             0 0 0 1 1 0 0 0 1 1 1 N j N j oj j o N j oj     (15)
Dari persamaan (8) dan (15), didapatkan bahwa
0 0 0 0 0 , , 2 , 1 , N j j j j         (16)
Dengan cara yang sama, persamaan (9) dan (11) mengarah pada
kj k kj     dan (17)
        k k N j k kj k N j kj m k 1 1 , , 2 , 1 ,     (18)
Dengan demikian kj  dapat dinyatakan sebagai berikut (dari persamaan (17)):
m k N j k N j kj kj k kj kj k , , 2 , 1 ; , , 2 , 1 , 1              dengan 0   k (19)
Karena persamaan (16) dan (19) menyatakan j 0  dan kj  dalam suku-suku dari j 0  dan kj  ,  pengali  Lagrange  dapat  diperlakukan  sebagai  variabel  yang  tidak  diketahui  dalam masalah, sehingga fungsi Lagrange dari persamaan (5) dapat dinyatakan
        m k k k N j j f w L 1 1 0 0 0 0 0 ) (     f Δ, w, +                                                
     m k N j n i N j kj kj kj i kij k kj N j n i j j i ij j k k c w a c w w a 1 1 1 1 1 1 0 0 0 0 0 ln ln 0       (20)
dengan   T N j mj m N j j T m m f f
                              1 1 1 1 1 1 , , 1 ,
, 1     f .
Mengingat bahwa  
  0 1 0 0 1 N j j   dan 1
0   , persamaan (20) menjadi
                             0 1 0 0 0 1 1 1 ) 1 ( ln ) ( N j j m k N j kj N j kj kj kj k w c L k k      f λ, w, + …
         n i m k N j m k k k kj kij k i k f a w 1 0 1 1    (21)
Fungsi ini ) ( f λ, w, L dapat  dipandang sebagai fungsi Lagrange dari masalah optimisasi lain dengan fungsi tujuannya adalah
              m k N j N j kj kj kj kj k k k c v 0 1 1 ln ) ( ~     λ (22)
dan  kendala
0 1 0 1 0     N j j  (23)
     m k N j kj kij k k n i a 0 1 , , 2 , 1 , 0    (24)
dan  
   k N j kj k m k 1 , , 2 , 1 , 0   
(25)
m n f f f w w w w , , , dan , , , ), 1 ( 2 1 2 1 0    berperan  sebagai  pengali  Lagrange  dalam persamaan  (21).  Variabel m
k N j k kj , , 2 , 1 , 0 ; , , 2 , 1 ,  
   dapat  dicari  dengan menyelesaikan pers. (23) dan (24)  yang masing-masing mewakili  kondisi  normalitas dan ortogonalitas. Dapat dilihat bahwa terdapat 1  n persamaan linier dalam N variabel dengan    m k k N N 0 . Jadi derajat kesulitannya adalah
1   n N .
Fungsi dual ) ( λ v merupakan  eksponensial  dari )
( ~ λ v kj k m k N j N j kj kj kj v k k c e v                    0 1 1 ) ( ~ ) ( λ λ (26)
yang  juga  dibatasi  kendala  normalitas  (23),  kendala  ortogonalitas  (24)  dan  kendala  tak negatif (25).

## Prosedur Perhitungan
Masalah  Minimisasi  dengan  kendala  dapat  diselesaikan  dengan  memaksimumkan ) ( λ v dengan kendala normalitas dan ortogonalitas. Jika masalah  mempunyai derajat kesulitan nol, maka dihasilkan solusi tunggal untuk  λ . Nilai stasioner fungsi tujuan dapat diperoleh dengan mensubstitusi  λ pada persamaan (26).
Majalah Ilmiah Matematika dan Statistika Volume 15 Nomor 2  2015, 87 – 96 https://jurnal.unej.ac.id/index.php/MIMS/index ISSN 1411-6669
Jika masalah mempunyai derajat kesulitan positif D (yaitu ) 1    n N D , persamaan linier (23) dan (24)  dapat dipakai untuk menyatakan ( 1  n ) kj  variabel dalam suku-suku dari sisa kj D  variabel dari . Fungsi dual v dapat dinyatakan sebagai fungsi dari D variabel kj  yang independen. Titik stasioner dari v dapat dicari dengan menggunakan sebarang teknik optimisasi tanpa kendala atau dengan teknik kalkulus dipakai yaitu turunan pertama fungsi v adalah sama dengan nol yang memberikan pendekatan solusi yang bagus.
Setelah solusi  λ diperoleh, maka maksimum fungsi dual  v diperoleh dari persamaan (26) yang juga merupakan minimum fungsi primal  f . Untuk menentukan nilai optimal variabel
) , , 2 , 1 ( n i x i    dapat digunakan hubungan
0 0 1 0 0 , , 2 , 1 , 0 ) ( 0 N j x x c n i a i oj j j ij             
(27)
m k N j x c n i k a i kj N j kj kj kj kij k , , 2 , 1 ; , , 2 , 1 , ) ( 1 1                 
(28)
Jika masalah seluruh kendalanya berbentuk 1 ) (  X k g , maka fungsi tujuan ) ( 0 X g menjadi fungsi  konveks  ketat    dari  variabel  transformasi n w w w , , , 2 1  dan  kendala  juga  akan konveks  sehingga mempunyai satu minimum lokal yang juga minimum global. Fungsi dual transformasi adalah fungsi konkaf yang memiliki satu titik stasioner yaitu maksimum global. Dengan  demikian  minimum 0 w dapat  dicari  dengan  memaksimumkan  fungsi ) ( ~ λ v atau eksponensialnya ) ( λ v .
Jika masalah pemrograman geometrik berisi kendala campuran m k g k , , 2 , 1 , 1 ) , )( (     X ,  tidak  ada  pernyataan  umum  yang  dapat  dibuat  tentang kekonveksan  atau  kekonkafan  dari  himpunan  kendala.  Akan  tetapi,  karena  fungsi  tujuan kontinu  dan  terbatas  di  bawah  oleh  nol,  kasus  ini  harus  mempunyai  minimum  yang dilengkapi bahwa ada titik yang memenuhi kendala.

## 3. Kesimpulan
Berdasarkan uraian pada pembahasan dapat ditarik kesimpulan bahwa untuk menentukan solusi masalah minimisasi dengan kendala dalam pemrograman geometrik adalah dengan menyelesaikan bentuk dualnya, yaitu
tentukan T mN m N N m ) , , , , , , , , , ( 1 1 11 0 01 1 0            λ
yang memaksimumkan
kj m k N j N j kj kj kj k k k c v                   0 1 1 ) ( λ dengan kendala
1 0 1 0    N j j  (kondisi normalitas)
     m k N j kj kij k k n i a 0 1 , , 2 , 1 , 0   
(kondisi ortogonalitas)
     k N j kj k m k 1 , , 2 , 1 , 0   
(kendala tak negatif) Untuk 1 sedangkan ; 1 ) ( jika 1 1 ) ( jika 1 , , 2 , 1 0              X X k k k k g g m k  .

## Daftar Pustaka
[1] Hamdy  A Taha, 1997, Riset Operasi Suatu Pengantar Jilid 2 (alih bahasa oleh Daniel Wirajaya), Binarupa Aksara, Jakarta.
[2] K.V. Mital, 1976, Optimization Methods in Operations Research and System Analysis, Wiley Eastern Limited, New Delhi.
[3] S.S.  Rao,  1984,  Optimization  Theory  and  Applications,  Wiley  Eastern  Limited,  San Diego.