METODE
dan TABEL SIMPLEX
Mengubah bentuk baku model LP ke
dalam bentuk tabel akan memudahkan proses perhitungan simplex. Langkah-langkah
perhitungan dalam algoritma simplex adalah :
1.
Berdasarkan
bentuk baku, tentukan solusi awal (initial basic feaseble solution) dengan
menetapkan m – n variabel non basis sama dengan nol.
2.
Pilih
sebuah entering variable diantara yang sedang menjadi variabel non
basis, yang jika dinaikkan diatas nol, dapat memperbaiki nilai fungsi tujuan.
Jika tidak ada, berhenti, berarti solusi sudah optimal. Jika tidak, melangkah
ke langkah 3.
3.
Pilih
sebuah leaving variable diantara yang sedang menjadi variabel basis yang
harus menjadi non basis (nilainya menjadi nol) ketika entering variable menjadi
variabel basis.
4. Tentukan solusi
yang baru dengan membuat entering variable dan leaving variable menjadi non basis. Kembali ke langkah 2.
Contoh :
Maksimumkan Z = 3X1
+ 2X2
dengan syarat : X1 + X2 ≤ 15
2X1 + X2 ≤ 28
X1 + 2X2 ≤ 20
X1 , X2 ≥ 0
Bentuk Baku model LP diatas
adalah :
Z - 3X1 - 2X2 - 0S1 - 0S2 - 0S3 =
0 (Persamaan tujuan)
X1 + X2 + S1 = 15 (Persamaan
kendala)
2X1 + X2 + S2 = 28 (Persamaan kendala)
X1 + 2X2 + S3 = 20 (Persamaan
kendala)
Lihat kembali langkah nomor 1,
solusi awal ditentukan dari persamaan kendala dengan menetapkan 2 (dua) (= 5 –
3) variabel sama dengan nol, yang akan memberikan solusi yang unik dan layak.
Dengan menetapkan X1 = 0 dan X2 = 0, diperoleh S1 = 15, S2
= 28, S3 = 20. Pada saat ini nilai Z = 0, kita dapat
merangkum informasi diatas ke dalam bentuk tabel simplex awal seperti berikut :
Informasi pada tabel dibaca
seperti berikut :
1.
Kolom
basis menunjukkan variabel yang sedang menjadi basis yaitu S1, S2, S3, yang
nilainya diberikan pada kolom solusi (NK).
2.
Secara
tidak langsung mengatakan bahwa variabel non basis X1 dan X2 (yang tidak ditunjukkan
pada kolom basis) sama dengan nol.
3.
Nilai
fungsi tujuan adalah Z - ((3 x 0) + (2 x 0) + (0 x 15) + (0 x 28) + (0 x 20)) =
0, seperti terlihat pada kolom NK.
Kapan solusi
telah optimum ?
1.
Dengan
memeriksa persamaan Z, terlihat bahwa variabel non basis yaitu X1 dan X2,
keduanya memiliki koefisien negatif, yang berarti mempunyai koefisien negative pada
fungsi tujuan yang asli.
2.
Karena
tujuan kita adalah masalah maksimasi, maka nilai Z dapat diperbaiki dengan meningkatkan
X1 dan X2 menjadi lebih besar dari nol. Yang diutamakan untuk dipilih adalah
variabel yang memiliki nilai negatif terbesar.
3.
Ringkasnya,
optimality condition metode simplex menyatakan bahwa dalam kasus maksimasi,
jika variabel non basis memiliki koefisien non negatif pada persamaan Z,
maka solusi optimum telah tercapai. Jika tidak, variabel non basis dengan
koefisien negatif terbesar dipilih sebagai entering variabel.
Penerapan optimality
condition pada tabel simplex awal contoh diatas adalah :
1.
Pilih
X1 sebagai entering variabel. Kemudian leaving variabel harus
salah satu dari variabel basis S1 , S2 , S3.
2.
Penentuan leaving variabel dilakukan dengan
menggunakan feasibility condition yang menyatakan bahwa untuk masalah
maksimasi maupun minimasi, leaving variabel adalah
variabel basis yang memiliki rasio terkecil antara sisi kanan (NK) persamaan
kendala dengan koefisien bersangkutan yang positip pada entering variabel.
3.
Rasio
dalam tabel simplex dapat dicari dengan cara :
a.
Coret
semua elemen pada persamaan kendala dibawah entering variabel.
b.
Tidak
termasuk persamaan tujuan, buat rasio antara sisi kanan dengan elemen yang
dicoret dibawah entering variabel.
c.
Leaving
variabel adalah variabel basis yang memiliki rasio terkecil.
d.
Kolom
pada entering variabel dinamakan entering coulumn dan variabel basis yang
berhubungan dengan leaving variabel dinamakan pivot equation.
e.
Elemen
pada perpotongan entering coulumn dengan pivot equation dinamakan pivot elemen.
New Basic
Solution ditentukan
dengan menerapkan metode Gauss Jordan melalui perhitungan berikut :
1.
new pivot equation = old pivot equation
: pivot element
untuk
semua persamaan yang lain termasuk persamaan Z
2.
new equation = old equation – (entering
colomn coef. x new pivot equation)
Perhitungan pertama menghasilkan
pivot elemen sama dengan 1 pada pivot equation
yang baru,
seperti ditunjukkan pada tabel berikut :
Perhatikan bahwa kolom solusi
menghasilkan nilai baru X1 = 14, yang sama dengan
rasio minimum pada feasibility
condition. Tabel solusi baru yang diperbaiki dapat dibuat
dengan melakukan perhitungan
jenis kedua metode Gauss Jordan, kecuali baris X1
yang telah
menjadi new pivot equation.
Tabel baru yang
lengkap untuk iterasi pertama adalah sebagai berikut :
Solusi yang baru memberikan nilai
X1 = 14 dan X2 = 0. Nilai Z naik dari 0 menjadi 42.
Berdasarkan
tabel iterasi pertama,
solusi tabel belum dapat dinyatakan optimal
karena variabel non basis masih
memiliki nilai negatif, maka optimality condition
memilih X2 sebagai
entering variabel karena koefisien pada persamaan Z sebesar -1/2.
Feasibility condition menunjukkan
bahwa S1 sebagai leaving variabel karena memiliki
rasio terkecil (2)
Perhitungan pertama menghasilkan
pivot elemen : 2 x ½ = 1 pada pivot equation yang
baru dan memperbaiki nili fungsi
tujuan sebasar 1 (satu) seperti ditunjukkan pada tabel
berikut :
Kolom solusi menghasilkan nilai
baru X2 = 2, yang sama dengan rasio minimum pada
feasibility
condition.
Tabel solusi baru yang diperbaiki dapat dibuat dengan melakukan
perhitungan jenis kedua metode
Gauss Jordan, kecuali baris X2 yang telah menjadi
new pivot
equation.
Tabel baru yang lengkap untuk
iterasi kedua dan merupakan tabel optimum adalah
sebagai berikut
:
Solusi baru memberikan nilai X1
= 13 dan X2 = 2, sedangkan nilai Z = 43, dan ada sisa
sumber daya yang ditunjukkan pada
kendala (3) tiga. Tabel simplex iterasi kedua dapat
dinyatakan optimum karena
variabel non basis yang ada pada koefisien fungsi tujuan Z
sudah tidak memiliki nilai
negatif. Hal ini merupakan perhitungan metode simplex yang
lengkap.
MASALAH MINIMASI
Dalam masalah maksimasi, biasanya
memiliki kendala pertidaksamaan jenis ≤.
Sekarang akan dijelaskan proses
simplex untuk suatu masalah minimasi yang biasanya
memiliki kendala pertidaksamaan
jenis ≥. Masalah minimasi menggunakan langkahlangkah
yang sama seperti pada masalah
maksimasi, namun ada beberapa
penyesuaian yang harus dibuat.
Bagi kendala pertidaksamaan jenis ≤ maka variabel
slack ditambahkan untuk
menghabiskan sumber daya yang digunakan dalam kendala.
Cara ini tidak dapat diterapkan
pada kendala pertidaksamaan jenis ≥ dan kendala
persamaan (=).
Contoh :
Minimumkan Z = - 3X1 + X2 + X3
dengan syarat : X1 - 2X2 + X3 ≤ 11
- 4X1 + X2 + 2X3 ≥ 3
2X1 - X3 = -1
X1 , X2 , X3 ≥ 0
Persamaan pada kendala ke tiga
harus dirubah agar memiliki nilai kanan positip
dengan cara dikalikan (-1),
sehingga menjadi :
- 2X1 + X3 = 1
Persamaannya berubah menjadi :
Minimumkan Z = -
3X1 + X2 + X3
dengan syarat : X1 - 2X2 + X3 ≤ 11
- 4X1 + X2 + 2X3 ≥ 3
- 2X1 + X3 = 1
X1 , X2 , X3 ≥ 0
Bentuk baku diperoleh dengan menambahkan
variabel slack pada kendala pertama,
mengurangkan
variabel surplus pada
kendala kedua. Sehingga diperoleh :
Z + 3X1 - X2 - X3 - 0S1 - 0S2 = 0
(Persamaan
tujuan)
X1 - 2X2 + X3 + S1 = 11
- 4X1 + X2 + 2X3 - S2 = 3 (Persamaan kendala)
- 2X1 + X3 = 1
Istilah variabel
slack dan variabel surplus adalah berbeda dimana slack ditambahkan
dan mencerminkan sumber daya yang
tak terpakai, sementara surplus dikurangkan dan
menunjukkan suatu kelebihan atas
keperluannya, tetapi keduanya diberikan notasi
serupa, yaitu S.
Kebutuhan utama
metode simplex adalah solusi awal layak (initial basic solution).
Tanpa ini maka tabel simplex tidak
dapat dibuat. Dari masalah diatas, terdapat tiga (3)
persamaan dan lima (5) variabel
tak diketahui, yang berarti bahwa 2 variabel harus
menjadi non basis (nilainya = 0)
pada setiap solusi. Tak seperti kasus dimana terdapat
variabel slack pada setiap persamaan,
disini kita dapat menjamin bahwa dengan
menetapkan suatu variabel sama
dengan nol, variabel basis yang dihasilkan akan non
negatif (berarti diperoleh solusi
layak). Ada dua pendekatan untuk mendapatkan suatu
solusi awal layak, yaitu :
A.
Coba-coba
Disini
suatu variabel basis dipilih secara sembarang untuk setiap kendala. Jika
dihasilkan
suatu solusi layak (nilai variabel basis pada kolom solusi non negatif), maka
metode
simplex dapat dimulai. Bisa jadi, nilai variabel basis pada kolom solusi adalah
negatif,
maka solusi yang diperoleh tak layak (melanggar kendala non negatif) dan
metode
simplex tidak dapat dimulai. Meskipun, coba-coba dapat diulangi lagi sampai
diperoleh
solusi awal layak, metode ini jelas tidak efisien.
B.
Menggunakan Artifisal Variabel
Gagasan
menggunakan artifisial variabel sangat sederhana. Tambahkan suatu artifisial
variabel
pada sisi kiri setiap persamaan variabel basis. Dinamakan variabel artifisial
(sebagai
lawan dari “real decision variable”) karena ia tidak memiliki arti
nyata.Artifisial
digunakan
hanya untuk memulai penyelesaian dan pada urutan selanjutnya mereka
harus
dijadikan nol pada solusi akhir, jika tidak, maka solusi yang dihasilkan akan
menjadi
tak layak.
Pada
bentuk baku contoh minimasi diatas, variabel slack pada persamaan
kendala
pertama
adalah variabel basis. Karena pada persamaan kedua dan ketiga tidak ada
variabel
slack (variabel basis), maka perlu ditambahkan variabel artifisial A1 dan
A2
pada
masing-masing kendala tersebut. Untuk tetap menjamin bentuk baku, A1 dan A2
dibatasi
pada nilai non negatif. Sehingga diperoleh artificial system seperti :
X1
- 2X2 + X3 + S1 = 11
-
4X1
+ X2 + 2X3 - S2 + A1 = 3
-
2X1
+ X3 + A2 = 1
Terdapat
3 persamaan dan 7 bilangan tak diketahui, sehingga solusi awal layak harus
memiliki
4 (= 7 – 3) variabel non basis yang sama dengan nol. Jika X1=X2=X3=S2=
0,
maka
S1 = 11, A1 = 3 dan A2 = 1. Tetapi ini bukan solusi layak
karena artifisial variabel
benilai
positif. Sehingga tujuan kita adalah memaksa artifisial variabel menjadi nol
secepat
mungkin. Ini dapat dicapai dengan memakai teknik M.
METODE SIMPLEX M
(BIG – M)
Pada pendekatan ini, artifisial
variabel dalam fungsi tujuan diberi suatu biaya sangat
besar (dalam perhitungan komputer
biasanya 3 atau 4 kali besarnya dibanding bilangan
lain dalam model). Dalam praktek,
huruf M digunakan sebagai biaya dalam masalah
minimasi dan –M sebagai
keuntungan dalam masalah maksimasi dengan asumsi
bahwa M adalah suatu
bilangan positif yang besar.
Untuk menjelaskan teknik ini,
lihat kembali masalah minimasi diatas. Untuk
mengarahkan artifisial variabel
menjadi nol, suatu biaya yang besar ditempatkan pada
A1 dan A2, sehingga fungsi
tujuannya menjadi :
Minimumkan Z = - 3X1 + X2 + X3 +
0S1 + 0S2 + MA1 + MA2
Tabel simplex awal dibentuk
dengan S1 , A1 dan A2 sebagai variabel basis seperti pada
tabel berikut :
Perhatikan koefisien pada
persamaan Z dalam masalah minimasi lebih mudah
diperoleh dengan menggunakan Inner
Product Rule. Aturan ini juga berlaku untuk
masalah maksimasi dan akan banyak
bermanfaat dalam analisa sensitivitas. Inner
Product Rule itu adalah :
Cj = (v)(vj) – cj, dimana
keterangan :
Cj : koefisien variabel j pada
persamaan Z
v : vektor baris koefisien fungsi
tujuan variabel basis
vj : vektor kolom elemen dibawah
variabel j
cj : koefisien
variabel j pada fungsi tujuan
Kemudian perhitungan simplex
dapat dimulai dengan penerapan optimality dan
memiliki nilai positif yang
paling besar dan A2 sebagai leaving variabel karena memiliki
rasio positif
paling kecil.
Dengan menggunakan cara yang sama
pada masalah maksimasi maka perlu dihitung
new pivot
equation untuk
A2, yang selanjutnya dengan memakai metode Gauss
Jordan hitung nilai
variabel basis yang lain.
Iterasi pertama belum
menghasilkan solusi dasar layak karena A1 masih bernilai positif.
Iterasi berikutnya menunjukkan
bahwa X2 sebagai entering varabel dan A1 sebagai
leaving
variabel.
Sekarang X2 dan X3 telah
menjadi nol pada koefisien fungsi tujuan, sehingga iterasi
kedua merupakan solusi dasar
layak, tetapi ini bukan solusi optimal karena X1 masih
bernilai positif yang dapat
memperbaiki fungsi tujuan jika menggantikan S1 sebagai
basis.
No comments:
Post a Comment