HIMPUNAN KONVEKS DAN MATRIKS BISTOKASTIK

Abstract

Misal C sebuah himpunan. Himpunan C disebut konveks jika untuk setiap dua titik x_1  dan x_2  di C, ruas garis 〖(1-λ)x〗_1 + λx_2, dengan 0≤λ≤1, menghubungkan dua titik tersebut terletak dalam C, dimana λ adalah sebarang bilangan dalam bilangan real. Misalkan S sebuah himpunan. Galangan konveks atau hull konveks dari S dilambangkan conv (S), yang merupakan himpunan semua kombinasi konveks dari titik-titik di S. Jika S adalah himpunan finit dari titik-titik, maka conv (S)  dinamakan sebuah politop. Sebuah politop sering didefinisikan sebagai sebuah polihedron terbatas dan sangat penting dalam permasalahan program linear, karena himpunan fisibel dari kebanyakan program linear adalah politop. Jika ada sebuah titik x∈C sedemikian hingga titik x tidak dapat ditulis sebagai titik tengah dari dua titik x_1  dan x_2  di C, sedemikian hingga x=1/2 x_1+1/2 x_2  tidak ada. Maka dikatakan x sebuah titik ekstrim dalam himpunan C, titik ekstrim tersebut sebagai titik dalam suatu politop. Galangan konveks dari himpunan independen disebut sebuah simpleks dengan himpunan titik {x_1,x_2,…,x_t}. Himpunan semua matriks bistokastik ordo n x n dilambangkan Ω_n, disebut politop Birkhoff. Himpunan Ω_n  adalah konveks. Matriks A berordo n x n disebut matriks permutasi ordo n jika A diperoleh dari matriks identitas ordo n (I_n) dengan  mempermutasikan kolom-kolom atau baris-barisnya. Himpunan semua matriks permutasi ordo n, dilambangkan P_n. Terdapat sebanyak n! matriks permutasi ordo n.

Kata Kunci: Himpunan Konveks, Galangan Konveks (Hull Konveks), Matriks Bistokastik, Politop Birkhoff