HIMPUNAN KONVEKS DAN MATRIKS BISTOKASTIK

CONVEX SET AND DOUBLY STOCHASTIC MATRICES

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.

Let C be a set. The set C is said to be convex if for every two points x_1  dan x_2   in C, the line segment 〖(1-λ)x〗_1 + λx_2, with 0≤λ≤1, connecting the two points lies in C, where λ  is any number in real numbers. Suppose S is a set. The convex hull of S is denoted by conv (S), which is the set of all convex combinations of points in S. If S is a finite set of points, then conv (S) is a polytope. A polytope is often defined as a finite polyhedron and is very important in linear programming problems, because the set of feasible of most linear programming is a polytope. If there is a point x∈C such that the point x cannot be written as the midpoint of the two points x_1  and x_2  in C, such that x=1/2 x_1+1/2 x_2  does not exist. Then we say x is an extreme point in the set C, that extreme point is a point in a polytope. The convex hull of the independent set is called a simplex with the vertex set {x_1,x_2,…,x_t}. The set of all doubly stochastic matrices of the order n x n, denoted Ω_n,  is said to be the Birkhoff polytop. The set Ω_n  is convex. A matrix of order n x n is called a permutation matrix of order n if A is obtained from an identity matrix of order n (I_n)  by permutating its columns or rows. The set of all permutation matrices of order n, denoted P_n. There are as many as n! permutation matrix of order n.

Keywords: Convex Set, The Convex Hull, Doubly Stochastic Matrices, The Birkhoff Polytope.