Teori Komplementaritas

Problem komplementaritas adalah suatu problem di bidang optimisasi matematis. Termasuk dalam problem ini adalah masalah minimisasi dan maksimalisasi suatu fungsi yang terdiri atas dua variabel vektor, dengan syarat bahwa internal produk dari kedua variabel tersebut adalah nol, atau dalam bahasa matematisnya, <XY> = 0.[1]

Misalnya, jika dalam suatu ruang vektor riil berdimensi terbatas terdapat dua vektor X dan Y yang memiliki komponen-komponen non-negatif (xi ≥ 0 dan yi ≥ 0 untuk semua : komponen-kompenen tersebut terletak di kuadran pertama untuk ruangan 2-dimensi, atau di oktan pertama untuk ruangan 3-dimensi), maka, untuk setiap pasangan komponen xi dan yi, salah satu komponennya harus bernilai nol. Itulah sebabnya problem ini disebut komplementaritas. Contoh matematisnya X = (1, 0) dan Y = (0, 2) adalah komplementer, tetapi X = (1, 1) dan Y = (2, 0) bukan komplementer. Problem komplementaritas adalah suatu kasus khusus dari problem inequalitas variasional.

Asal Usul sunting

Problem komplementaritas pada awalnya dipelajari karena Kondisi-kondisi Karush-Kuhn-Tucker (di bidang pemrograman linier dan pemrograman kuadratik) memunculkan Problem Komplementaritas Linier (LCP) dan Problem Komplementaritas Campuran (MCP). Pada tahun 1963 Lemke dan Howson membuktikan bahwa penghitungan Keseimbangan Nash untuk game 2 pelaku adalah identik dengan problem LCP. Pada tahun 1968 Cottle dan Dantzig menyatukan masalah pemrograman linier, kuadratik dan bimatriks game. Sejak saat itulah penelitian di bidang komplementaritas dan inequalitas variasional berkembang dengan pesat.

Referensi sunting

  1. ^ Billups, Stephen; Murty, Katta (1999). "Complementarity Problems".  http://www-personal.umich.edu/~murty/LCPart.ps

Referensi Lanjut sunting

Bibliografi sunting

  • Richard Cottle, F. Giannessi, Jacques Louis Lions, ed. (1980). Variational Inequalities and Complementarity Problems: Theory and Applications. John Wiley & Sons. ISBN 978-0471276104. 
  • Michael C. Ferris, Jong-Shi Pang, ed. (1997). Complementarity and Variational Problems: State of the Art. SIAM. ISBN 978-0898713916. 

Pranala luar sunting