50
Fungsi Pembatas
:
a
11
X1
+
a
12
X2
+a13X3
+
…
+
a1
n
X
n
=
b1
a
21
X1
+
a
22
X2
+a23X3
+
…
+
a2
n
X
n
=
b2
.
.
.
a
m1
X1
+
a
m2
X2
+a
m3
X3
+
…
+
a
mn
X
n
=
b
m
dan X1
=
0, X2
=
0, …, X
n
=
0
Maka
pembatas
dari
model
tersebut
dapat
dituliskan
ke
dalam
bentuk
persamaan
AX
=
b. Perhatikan suatu sistem AX = b dari m persamaan
linier dalam n variabel (n > m).
Definisi
:
1. Solusi basis
Solusi
basis
untuk
AX
= b
adalah
solusi
dimana
terdapat
sebanyak-banyaknya
m
variabel
berharga
bukan
nol.
Untuk
mendapatkan
solusi
basis
dari
AX = b
maka
sebanyak
(n-m) variabel
harus
dinolkan. Variabel-variabel
yang
dinolkan
ini disebut
variabel
non-basis
(NBV).
Selanjutnya,
dapatkan
harga
dari
n –
(n-m)
=
m
variabel
lainnya yang memenuhi AX = b, yang disebut variabel basis (BV).
2. Solusi basis fisibel
Jika seluruh
variabel
pada suatu
solusi
basis
berharga
non-negatif,
maka
solusi
itu
disebut solusi basis fisibel (BFS).
3. Solusi fisibel titik ekstrim
Yang dimaksud
dengan
solusi
fisibel
titik ekstrim
atau titik
sudut
ialah
solusi
fisibel
yang
tidak
terletak
pada
suatu
segmen
garis
yang
menghubungkan
dua solusi
fisibel
lainnya.
Ada tiga sifat pokok titik ekstrim ini, yaitu :
 |