Pada
metode grafik solusi optimum selalu terletak pada titik pojok ruang solusi.
Metode Simpleks sebenarnya didasarkan pada gagasan ini dengan
langkah-langkah sebagai berikut:
1.
Dimulai
pada suatu titik pojok yang layak, biasanya titik asal (disebut solusi awal).
2.
Bergerak
dari satu titik pojok layak ke titik pojok layak lain yang berdekatan.
Pergerakan ini akan menghasilkan nilai fungsi tujuan
yang lebih baik (meningkat untuk masalah maksimasi atau akan semakin menurun
untuk masalah minimasi). Jika solusi yang lebih baik telah diperoleh, prosedur
simpleks dengan sendirinya akan menghilangkan semua solusi lain
yang kurang baik.
3.
Proses
ini diulang-ulang sampai suatu solusi yang lebih baik tak dapat ditemukan.
Dalam
proses penghitungan kita akan bekerja menggunakan tabel simpleks agar lebih
mudah dikerjakan. Artinya bentuk baku model LP diubah ke dalam bentuk tabel.
Algoritma
simpleks adalah sbb. :
a)
Berdasarkan bentuk baku, tentukan solusi awal (initial basic feasible solution)
dengan menetapkan (n – m) variable nonbasis sama dengan nol. Dimana n
adalah banyak variabel dan m adalah banyak fungsi/persamaan kendala.
b)
Pilih sebuah entering variabel di antara yang sedang menjadi variabel non basis
yang jika dinaikkan di atas nol dapat memperbaiki nilai fungsi tujuan. Jika tak
ada, berhenti, berarti solusi sudah optimal ika tidak lakukan langkah c)
c)
Pilih sebuah leaving variabel di antara yang sedang menjadi variabel basis yang
harus menjadi nonbasis (nilainya menjadi nol) ketika entering variabel menjadi
variabel basis.
d)
Tentukan solusi yang baru dengan membuat entering variabel dan
leaving variabel menjadi nonbasis.Kembali ke langkah b).
Contoh:
Maksimumkan
Z = 3X1 + 2X2
Dengan
syarat X1 + X2 < 15
2X1
+ X2 < 28
X1
+ 2X2 < 20
X1
> 0 dan X2 > 0.
Ubah
ke bentuk baku model LP menjadi:
{Persamaan
Tujuan}
Z
-3X1 – 2X2 – 0S1 – 0S2 – 0S3 = 0
X1
+ X2 +
S1
= 15
2X1
+ X2 +
S2 = 28
X1
+ 2X2
+
S3 = 20
Kita
tetapkan X1 = 0 dan X2 = 0, maka diperoleh Z =0, S1 = 15, S2 = 28,
dan S3 = 20.
Optimality condition metode simpleks menyatakan bahwa
dalam kasus maksimalisasi, jika semua variabel non basis memiliki koefisien non
negatif dalam persamaan Z maka solusi telah optimum. Jika tidak variabel non
basis dengan koefisien negatif terbesar dipilih sebagai entering variabel.
Penerapan
optimality condition pada tabel simpleks awal menyarankan memilih X1 sebagai
entering variabel. Kemudian leaving variabel harus salah satu dari variabel
basis.
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 persamaan
kendala dengan koefisien bersangkutan yang positif pada entering variabel.
Rasio
yang didefinisikan di atas dan leaving variabel dapat ditentukan langsung dari
tebel simpleks. Pertama, coret semua elemen nol atau negatif pada persamaan
kendala di bawah entering variabel. Kemudian, tidak termasuk persamaan tujuan,
buat rasio antara sisi kanan persamaan dengan elemen yang tidak dicoret di
bawah entering variabel. Leaving variabel adalah variabel basis yang memiliki
rasio terkecil. Kolom pada entering variabel dinamakan entering column dan
baris yang berhubungan dengan leaving variabel dinamakan pivot equation. Elemen
pada perpotongan entering column dan pivot equation dinamakan pivot element.
Dalam tabel pivot element ditunjukkan dengan tanda kurung.
Selanjutnya,
menentukan new basic solution menerapkan metode Gauss Jordan, melalui dua jenis
perhitungan.
Jenis
1 (persamaan pivot)
Elemen
persamaan pivot table baru = elemen persamaan pivot table lama/elemen
pivot.
1.
Jenis
2 (semua persamaan yang lain termasuk persamaan
2.
Z)
Elemen Persamaan table baru = Elemen persamaan table lama – {
Elemen entering column x elemen persamaan pivot table baru}
Perhitungan
jenis 1 membuat pivot element sama dengan 1 pada pivot equation yang baru,
sementara perhitungan jenis 2 membuat koefisien yang lain pada entering column
sama dengan nol, seperti pada tabel di bawah.
Basis
X1 X2
S1
S2
S3 Solusi
Z
-3 -2
0
0
0
0
S1
X1
1
1/2
0
1/2 0
14
S3
Perhatikan bahwa kolom solusi
menghasilkan nilai baru X1 = 14, yang sama dengan rasio minimum
pada feasibility condition. Tabel solusi baru yang
diperbaiki dibuat dengan melakukan perhitungan jenis 2 sbb.
Basis
X1 X2
S1 S2
S3 Solusi Rasio
Z
0 -1/2
0 3/2
0
42
S1
0 (1/2)
1 -1/2
0
1 2
X1
1 1/2
0 1/2
0
14 28
S3
0 3/2 0
-1/2
1
6
4
Solusi
baru memberikan bahwa X = 14, X2 = 0 (titik B pada gambar). Sekarang nilai Z
naik dari 0 menjadi 42.
Berdasarkan
tabel, optimally 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 yaitu 2,
sehingga memperbaiki nilai fungsi tujuan sebesar 2 x ½ = 1. Dengan menggunakan
operasi Gauss Jordan diperoleh tabel baru, sbb.
Basis
X1 X2
S1 S2
S3 Solusi
Z
0 0
1 1
0 43 Optimum
X2
0
1
2 -1
0
2
X1
1
0 -1
1
0 13
S3
0
0 -3
1
1 3
Solusi
baru memberikan X1 = 13 dan X2 = 2 (titik C pada gambar) dan nilai Z naik dari
42 menjadi 43. Tabel di atas memberi solusi optimal karena tidak ada lagi
variabel nonbasis yang memiliki koefisien negatif pada persamaan Z. Ini
merupakan perhitungan metode simpleks lengkap.
Pada
contoh di atas metode simpleks diterapkan pada masalah maksimasi. Pada masalah
minimasi, optimally condition berubah, di mana entering variabel dipilih dari
variabel yang memiliki koefisien positif terbesar pada persamaan Z. Feasibility
condition adalah sama untuk kedua masalah. Kedua condition tersebut akan
ditegaskan kembali seperti berikut.
Optimally
Condition: entering variabel pada maksimasi (minimasi) adalah variabel nonbasis
dengan koefisien negatif (positif) terbesar pada persamaan Z. Suatu koefisien
kembar dipilih secara sembarang. Jika semua koefisien nonbasis pada persamaan Z
adalah nonnegatif (nonpositif), solusi optimum telah dicapai.
Feasibility
Condition: baik masalah maksimasi maupun minimasi, leaving variable adalah
variable basis yang memiliki rasion terkecil (dengan penyebut positif). Suatu
rasio kembar dipilih secara sembarang.
Contoh
soal:
1)
Maksimumkan fungsi tujuan
p
= 4x + 6 y (untuk p dalam puluhan ribu)
terhadap
konstrain 2x + y < 180
x
+ 2y < 160
x
+ y < 100
x
> 0 , y > 0
2)
Maksimumkan fungsi tujuan p = 3x + y terhadap konstrain
2x
+ y < 8
2x
+ 3y < 12
x
> 0 , y > 0
3)
Maksimumkan Z = 5x + 4y
Terhadap
x + y < 20
2x + y < 35
-3x +
y < 12
x,
y > 0
Contoh:
Maksimumkan
Z = 40X1 + 30X2 + 50X3
Dengan
syarat 6X1 + 4X2
+ X3 < 32000
6X1
+ 7X2 + 3X3 < 16000
4X1
+ 5X2 + 12X3 < 24000
X1
> 0, X2 > 0, dan X3 > 0.
Bentuk
baku model LP menjadi:
Z
– 40X1 – 30X2 – 50X3 – 0S1 – 0S2 – 0S3 = 0.
6X1
+ 4X2 + X3 +
S1
= 32000
6X1
+ 7X2 +
3X3 +
S2 =
16000
4X1
+ 5X2 +
12X3
+ S3 = 24000
Basis
X1 X2 X3 S1 S2
S3 Solusi Rasio
Z
-40 -30 -50
0 0
0 0
S1
6 4
1
1 0 0
32000 32000
S2
6 7
3 0
1 0 16000 5,333
S3
4 5 (12)
0 0 1
24000 2000
Tabel
Iterasi Pertama
Basis
X1 X2 X3
S1 S2 S3
Solusi Rasio
Z
-70/3 -55/6 0
0 0
25/6 100000
S1
17/3 14/12 0
1 0 -1/12 30000 5,294
S2
(5) 23/4
0 0
1 -1/4 10000 2000
X3
1/3 5/12
1 0
0 1/12 2000 6000
Tabel
Iterasi Kedua (Optimum)
Basis
X1 X2
X3 S1
S2 S3 Solusi
Z
0 53/3
0 0
14/3 3 440000/3
S1
0 -44/15
0 1
-17/15 1/5 56000/3
X1
1 23/20
0 0
1/5 -1/20 2000
X3
0 1/30
1 0
-1/15 1/10 4000/3
Pada
iterasi kedua telah tercapai solusi optimum dengan
X1
= 2000, X3 = 4000/3, dan Z = 1466,7.
Dan
dari tabel terlihat bahwa S2 = 0 dan S3 = 0 artinya pengambilan keputusan akan
menggunakan seluruh persediaan sumber daya kedua dan ketiga, tetapi masih
memiliki sumber daya pertama sebanyak 1666,7 karena tidak digunakan.
