19
2.6.2 Metode Simpleks
Metode
simpleks
dirancang oleh
George
Dantzig
pada
tahun
1947
untuk
menyelesaikan formulasi linear programming
masalah pengiriman pasukan
dan
logistik
pada
Angkatan
Udara
Amerika
Serikat.
Aplikasi
untuk
menyelesaikan masalah
skala
besar
yang
nyata,
seperti
yang
ditemukan dalam
operasi
militer,
memungkinkan
optimalisasi untuk
berkembang pada
tahun
1950an
dengan
penantian
dari
dynamic
programming
oleh
Bellman, network flow
oleh
Ford
dan
Fulkerson,
nonlinear
programming oleh Kuhn dan Tacker, integer programming oleh Gomory, decomposition
oleh
Dantzig
dan
Wolfe,
dan
kode
komersial
linear
programming
yang
pertama
oleh
Orchard-Hays (Ravindran, 2009, p6-3).
Menurut
Maros
(2003,
p19),
metode
simpleks
adalah
prosedur
komputasi yang
dibutuhkan
yang
membutuhkan penggunaan
komputer.
Hal
ini
sangat
disetujui
oleh
Dantzig
pada
tahun
1988,
di
mana
pertumbuhan kebutuhan
akan
solusi
dari
masalah
sehari-hari
linear
programming
telah
menginspirasi
perkembangan komputer
secara
signifikan pada tahun 1950an sampai awal 1960an.
Dari
cara
pandang
secara
teori,
metode
simpleks
tidak
membutuhkan algoritma
untuk
menangani
kasus
terburuk
yang
merupakan
bentuk
eksponensial.
Hal
ini
berarti
jumlah
iterasi
yang dibutuhkan
untuk
menyelesaikan sebuah
masalah terikat oleh sebuah
fungsi
eksponensial
dari
m
dan
n.
Seperti
contoh
yang
dikemukakan
Klee
dan
Minty
pada
tahun
1972,
untuk
perhitungan
interasi
dari
algoritma
akan
mencapai
maksimum
secara teori. Dalam praktisnya, metode simpleks menunjukkan sebuah performa rata-rata
 |