03_Metode Simpleks

Report
Metode Simpleks
Dyah Darma Andayani
PENDAHULUAN




Metode Simpleks adalah metode penentuan solusi optimal
menggunakan simpleks didasarkan pada teknik eliminasi Gauss
Jordan.
Penentuan solusi optimal dilakukan dengan memeriksa titik
ekstrim (sama dengan solusi grafik) satu persatu dengan cara
perhitungan iteratif sehingga penentuan solusi optimal dengan
simpleks dilakukan tahap demi tahap yang disebut dengan
iterasi.
Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).
Ada beberapa istiilah yang sangat sering kita gunakan delam
metode simpleks, diantaranya iterasi, variabel non-basis,
variabel basis, solusi atau nilai kanan, variabel slack, variabel
surplus, variabel buatan, kolom pivot, baris pivot, elemen pivot,
variabel masuk dan variabel keluar.
BENTUK BAKU



Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk
umum, diubah menjadi persamaan (=) dengan
menambahkan satu variabel slack.
Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk
umum, dirubah menjadi persamaan (=) dengan
mengurangkan satu variabel surplus.
Fungsi kendala dengan persamaan dalam bentuk umum
ditambahkan satu artificial variable (variabel buatan).
CONTOH KASUS


Minimumkan
Kendala
z = 2x1 + 5,5 x2
x1 + x2 = 90
0,001x1 + 0,002x2 ≤ 0.9
0,09x1 + 0,6x2 ≥ 27
0,02x1 + 0,06x2 ≤ 45
x1, x2 ≥ 0
Bentuk di atas adalah bentuk umum pemrograman linear.
Bentuk tersebut dapat diubah ke dalam bentuk
baku/standar dengan menambahkan variabel buatan,
variabel slack dan variabel surplus sebagai berikut :


Minimumkan
Terhadap :
z = 2x1 + 5,5x2
x1 + x2 + s1 = 90
0,001x1 + 0,002x2 + s2 = 0,9
0,09x1 + 0,6x2 – s3 = 27
0,02x1 + 0,06x2 + s4 = 4,5
x1, x2, s1, s2, s3, s4 ≥ 0
Fungsi kendala pertama mendapatkan variabel buatan (s1)
karena bentuk umumnya sudah menggunakan bentuk
persamaan. Fungsi kendala kedua dan keempat (s2 dan s4)
mendapatkan variabel slack karena bentuk umumnya
menggunakan pertidaksamaan ≤, sedangkan fungsi kendala
ketiga mendapat surplus variabel (s3) karena bentuk
umumnya menggunakan pertidaksamaan ≥.
CONTOH KASUS 2


Maksimumkan
Terhadap :
z = 2x1 + 3x2
10x1 + 5x2 ≤ 600
6x1 + 20x2 ≤ 600
8x1 + 15x2 ≤ 600
x1, x2 ≥ 0
Bentuk di atas juga merupakan bentuk umum. Perubahan
ke dalam bentuk baku hanya membutuhkan variabel slack,
karena semua fungsi kendalanya menggunakan bentuk
pertidaksamaan ≤ dalam bentuk umumnya.



Bentuk bakunya adalah sebagai berikut :
Maksimumkan
z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3
Terhadap :
10x1 + 5x2 + s1 = 600
6x1 + 20x2 + s2 = 600
8x1 + 15x2 + s3 = 600
x1, x2, s1. s2, s3 ≥ 0
dimana s1, s2, dan s3 merupakan variabel slack.
PEMBENTUKAN TABEL SIMPLEKS

Gunakan kasus di atas maka tabel awal simpleksnya adalah
LANGKAH-LANGKAH PENYELESAIAN


Periksa apakah tabel layak atau tidak. Kelayakan tabel
simpleks dilihat dari solusi (nilai kanan). Jika solusi ada
yang bernilai negatif, maka tabel tidak layak. Tabel yang
tidak layak tidak dapat diteruskan untuk dioptimalkan.
Tentukan kolom pivot. Penentuan kolom pivot dilihat dari
koefisien fungsi tujuan (nilai di sebelah kanan baris z) dan
tergantung dari bentuk tujuan. Jika tujuan berupa
maksimasi, maka kolom pivot adalah kolom dengan
koefisien negatif terbesar. Jika tujuan minimasi, maka
kolom pivot adalah kolom dengan koefisien positif
terkecil. Tidak digunakan kata-kata nilai terkecil dan
terbesar karena dalam metode ini tidak memilih nilai
terkecil dan terbesar.



Jika kolom pivot ditandaui dan ditarik ke atas, maka kita akan
mendapatkan variabel keluar. Jika nilai negatif terbesar (untuk
tujuan maksimasi) atau positif terbesar (untuk tujuan minimasi)
lebih dari satu, pilih salah satu secara sembarang.
Tentukan baris pivot. Baris pivot ditentukan setelah membagi
nilai solusi dengan nilai kolom pivot yang bersesuaian (nilai
yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0
pada kolom pivot tidak diperhatikan, artinya tidak ikut menjadi
pembagi. Baris pivot adalah baris dengan rasio pembagian
terkecil. Rasio pembagian tidak mungkin bernilai negatif, karena
nilai kanan tidak negatif demikian juga dengan nilai kolom pivot.
Jika baris pivot ditandai dan ditarik ke kiri, maka kita akan
mendapatkan variabel keluar. Jika rasio pembagian terkecil lebih
dari satu, maka pilih salah satu secara sembarang.



Tentukan elemen pivot. Elemen pivot merupakan nilai yang
terletak pada perpotongan kolom dan baris pivot.
Bentuk tabel simpleks baru. Tabel simpleks baru dibentuk
dengan pertama kali menghitung nilai baris pivot baru. Baris
pivot baru adalah baris pivot lama dibagi dengan elemen pivot.
Baris baru lainnya merupakan pengurangan nilai kolom pivot
baris yang bersangkutan dikali baris pivot baru dalam satu
kolom terhadap baris lamanya yang terletak dalam satu kolom
juga.
Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat
dari koefisien fungsi tujuan (nilai pada baris z) dan tergantung
dari bentuk tujuan. Untuk tujuan maksimasi, tabel sudah
optimal jika semua nilai pada baris z sudah positif atau 0. Pada
tujuan minimasi, tabel sudah optimal jika semua nilai pada baris
z sudah negatif atau 0. Jika belum, kembali ke langkah no.2, jika
sudah optimal baca solusi optimalnya.

Penyelesaian pada kasus 2 ;
X2 adalah variabel masuk dan s2 adalah variabel keluar.
Elemen pivot adalah 20
Iterasi 1


Perhitungan dilanjutkan ke iterasi 2.
Variabel masuk adalah x1 dan variabel keluar adalah s3

Tabel sudah optimal sehingga perhitungan iterasi
dihentikan.
TABEL OPTIMAL

Membaca tabel optimal adalah bagian penting bagi
pengambil keputusan. Ada beberapa hal yang bisa dibaca
dari tabel optimal “
1. Solusi optimal variabel keputusan.
2. Satus sumber daya
3. Harga bayangan (dual /shadow prices).

Solusi optimal : x1 = 42,857 ; x2 = 17,1329 dan z = 94,2857,
artinya untuk mendapatkan keuntungan maksimum sebesar
$94,2857 maka sebaiknya perusahaan memproduksi produk 1
sebesar 42,857 unit dan produk 2 sebesar 17,1329 unit

Status sumber daya : sumber daya pertama dilihat dari
keberadaan variabel basis awal dari setiap fungsi kendala
pada tabel optimal. Dalam kasus di atas, fungsi kendala
pertama periksa keberadaan s1 pada variabel basis tabel
optimal; periksa keberadaan s2 pada variabel basis tabel
optimal untuk fungsi kendala kedua’ periksa keberadaan s3
pada variabel basis tabel optimal untuk fungsi kendala
ketiga.
 S1 = 85,7155. Sumber daya iini disebut berlebih
(abundant).
 S2 = s3 = 0. Kedua sumber daya ini disebut habis
terpakai (scarce).




Harga bayangan : harga bayangan dilihat dari koefisien
variabel slack atau surplus pada baris fungsi tujuan.
Koefisien s1 pada baris fungsi tujuan tabel optimal = 0,
dengan demikian harga bayangan sumber daya pertama
adalah = 0.
Koefisien s2 pada baris fungsi tujuan tabel optimal = 9/70,
dengan demikian harga bayangan sumber daya kedua
adalah 9/70.
Koefisien s3 pada baris fungsi tujuan tabel optimal = 1/35
dengan demikian harga bayangan sumber daya ketiga
adalah 1/5.

similar documents