51
Sifat 1.a
:
Jika hanya ada satu solusi optimum,
maka pasti ada satu titik ekstrim.
Sifat
1.b
:
Jika
solusi
optimumnya
banyak,
maka
paling
sedikit
ada
dua
titik
ekstrim
yang
berdekatan.
(Dua
buah
titik
ekstrim
dikatakan
berdekatan
jika
segmen
garis yang
menghubungkan
keduanya
itu
terletak
pada
sudut
dari
batas daerah fisibel).
Sifat 2
:
Hanya ada sejumlah terbatas titik ekstrim pada setiap persoalan.
Sifat 3
:
Jika
suatu
titik
ekstrim
memberikan
harga
Z
yang
lebih
baik
dari
yang
lainnya, maka pasti solusi itu merupakan solusi optimum.
Sifat
3
ini
menjadi dasar
dari
metode
simpleks yang
prosedurnya meliputi 3
langkah berikut :
1. Langkah
inisialisasi
:
mulai dari suatu titik ekstrim.
2. Langkah
iteratif
:
bergerak
menuju
titik
ekstrim
berdekatan
yang
lebih
baik.
Langkah
ini diulangi sebanyak diperlukan.
3. Aturan penghentian
:
memberhentikan
langkah
ke-2 apabila telah sampai pada
titik ekstrim yang terbaik (titik optimum).
2.6.4
Algoritma Simpleks Untuk Persoalan Maksimasi
Untuk
menyelesaikan
persoalan
programa
linier
dengan
menggunakan
metode
simpleks, lakukan langkah-langkah
berikut
:
1. Konversikan formulasi
persoalan ke dalam bentuk standar
2. Cari solusi basis fisibel (BFS)
3.
Jika
seluruh
NBV
mempunyai
koefisien
non-negatif
(artinya
berharga
positif
atau
nol)
pada
basis
fungsi
tujuan
(basis
persamaan
z
yang
biasa
juga
disebut
baris
0),
maka BFS sudah optimal.
 |