PENYELESAIAN MASALAH PL DENGAN METODE SIMPLEKS Metode simpleks merupakan suatu teknik standar yang digunakan untuk memecahkan masalah Program Linear sejak tahun 1940. Pada prinsipnya, metode simpleks mencari penyelesaian optimal dengan menentukan titik-titik sudut dari daerah feasible, proses dilakukan berulang-ulang dari suatu titik sudut ke titik sudut berikutnya yang meningkatkan nilai fungsi tujuan sampai diperoleh nilai optimal atau sampai terlihat bahwa tidak ada nilai optimal. Masalah PL dua variabel dapat diselesaikan dengan metode grafik. Secara umum, masalah PL n variabel dapat diselesaikan dengan metode aljabar yang disebut dengan metode simpleks. Metode grafik dan metode simpleks pada dasarnya adalah mencari PO yang merupakan titik-titik batas daerah layak.
Pertama-tama akan dibahas dicari PO masalah PL bentuk baku. Bentuk baku masalah PL : 1.
maksimum baku
2.
minimum baku
Kendala sistem pertidaksamaan linear pada masalah PL baku diubah menjadi SPL dengan menambahkan variabel baru yang mengetatkan atau melonggarkan, yaitu : -
Variabel Slack, yaitu variabel yang mengetatkan kendala bertanda
menjadi
bertanda = Ruas kiri kendala ke-k slack
sk
Variabel -
sk
0
ak 1 x1 ak 2 x2 ... akn xn
sehingga
menjadi
bk
ditambah variabel
ak 1 x1 ak 2 x2 ... akn xn
sk
bk .
menjadi variabel basis.
Variabel surplus, yaitu variabel yang melonggarkan kendala bertanda
menjadi
bertanda =. Ruas kanan kendala ke-k surplus
tk
0
ak 1 x1 ak 2 x2 ... akn xn
sehingga menjadi
bk
ditambah variabel
ak 1 x1 ak 2 x2 ... akn xn
bk
tk
atau
ak 1 x1 ak 2 x2 ... akn xn tk
bk .
Variabel
tk
0
bukan variabel basis
(koefisiennya bukan +1) -
variabel artifisial, yaitu variabel yang membawa kendala PL yang belum memuat variabel basis
1.
Pada
ak 1 x1 ak 2 x2 ... akn xn tk
qk
0
qk
0 merupakan variabel basis.
sehingga
bk
perlu ditambah variabel artifisial
ak 1 x1 ak 2 x2 ... akn xn tk
menjadi
qk
bk ,
PENYELESAIAN PL MAKSIMUM BAKU
Diberikan masalah PL maksimum baku : n
f (xj )
Memaksimumkan
cj xj
(1)
j 1 n
aij x j
Dengan kendala
bi , i, i 1,2,..., m
(2)
j 1
xj
0, j , j 1,2,..., n
(3)
Kendala (2) diubah menjadi SPL dengan menambahkan variabel slack sehingga diperoleh
a11 x1 a12 x2 ... a1n xn
s1
b1
a21 x1 a22 x2 ... a2 n xn
s2
b2
am1 x1 am 2 x2 ... amn xn
sm
bm
Agar nilai fungsi tujuan tidak berubah, maka koefisien biaya
ci
untuk
si
adalah nol,
i, i 1,2,..., m . Sehingga fungsi tujuan menjadi memaksimumkan
f ( x1 ,..., xn , s1 ,..., sm ) c1 x1 ... cn xn 0s1 ... 0sm Variabel slack
si
nol, sedangkan dinolkan atau
xj
xj
0, i, i 1,2,..., m
merupakan variabel basis yang nilainya tak
0, j , j 1,2,..., n
menjadi variabel non basis yang nilainya
0, j , j 1,2,..., n .
Handout Pemrograman Linier 2016_Himmawati
Page 2
Akibatnya nilai awal fungsi tujuan adalah
f ( x1 ,..., xn , s1 ,..., sm )
f (0,...0, s1 ,..., sm ) 0
dengan penyelesaian optimal awal/plb
( x1 ,..., xn , s1 ,..., sm ) (0,...0, b1 ,...,bm ) .
Masalah PL yang kendalanya berbentuk SPL dan memuat variabel basis tersebut dinamakan berbentuk kanonik. Masalah PL bentuk kanonik dalam tabel simpleks dituliskan sebagai berikut.
cj xj
ci
c1
c2
...
cn
0
0
...
0
x1
x2
...
xn
s1
s2
...
sm
bi
Ri
xi 0
s1
a11
a12
...
a1n
1
0
...
0
b1
R1
0
s2
a21
a22
...
a2 n
0
1
...
0
b2
R2
...
...
...
...
....
...
...
...
...
...
...
...
0
sm
a m1
am 2
....
a mn
0
0
...
1
bm
Rm
zj
z1
z2
....
zn
c1
c2
...
cn
Z
zj - cj
z1 - c1
z 2 - c2
z n - cn
0
0
...
0
Z
Keterangan tambahan tabel :
xi
variabel basis pada bentuk kanonik
ci
koefisien unit ongkos dari
xi
m
zj
ci aij i 1 m
Z
ci bi
nilai fungsi tujuan
i 1
Ri
rasio antara
bi
dan
aik
jika
xk
terpilih menjadi variabel basis
Handout Pemrograman Linier 2016_Himmawati
Page 3
Algoritma Simpleks PL maksimum baku 1. Masalah PL dibawa ke bentuk kanonik 2. Susun tabel awal simpleks 3. Uji keoptimuman Tabel simpleks dikatakan optimum jika
zj
cj
Nilai fungsi tujuan ada pada baris ke m+1 kolom nilai
bi
0, j
bi
dan POnya adalah susunan
untuk variabel basis dan nol untuk variabel non basis.
Jika masih ada
zj
cj
0 , maka dilanjutkan langkah 4.
4. Memperbaiki tabel simpleks Memperbaiki tabel simpleks dilakukan dengan mengganti variabel basisnya dengan variabel basis yang baru dengan harapan variabel basis baru tersebut mengoptimalkan fungsi tujuan. Langkah memperbaiki tabel: -
menentukan variabel masuk yang akan menjadi variabel basis baru, yaitu variabel dengan
z j - cj
0
terkecil. Misal
zk
ck
terkecil, maka
xk
menjadi variabel masuk -
menentukan variabel keluar yang akan digantikan oleh variebel basis baru. Pada kolom koefisien
kemudian pilih
Ri
xk ,
aik dihitung
yaitu
terkecil. Misal
Rl
rasio
terkecil, maka
ql
Ri
bi , aik aik
0,
menjadi variabel
keluar. -
menyusun tabel baru. Variabel basis baru dalam tabel baru adalah Koefisien
alk
menjadi 1 dan
q1 ,..., ql 1 , xk , ql 1 ,..., qm .
menjadi elemen pivot. Pada kolom ke-k,
aik
alk
harus diubah
0, i l . Perubahan ini dilakukan dengan OBE dan
berlaku untuk semua elemen pada baris yang sesuai sehingga diperoleh tabel baru. 5. Lakukan kembali langkah 3 dan 4 sehingga optimum tercapai. Handout Pemrograman Linier 2016_Himmawati
Page 4
CONTOH 1 Selesaikan masalah PL berikut berikut dengan metode simpleks. Memaksimumkan
f ( x1 , x2 , x3 , x4 ) 5 x1 3x2
2 x3
Dengan kendala
4 x1 5 x2
2 x3
3x1
x3
4 x2
x1 , x2 , x3 , x4
x4
20
x4
30
0
Penyelesaian : Langkah 1 Masalah PL ini diubah menjadi bentuk kanonik dengan menambahkan variabel slack
s1
0 pada kendala 1 dan s2 4 x1 5 x2
2 x3
3x1
x3
4 x2
0 pada kendala 2 sehingga kendala menjadi
x4
s1
x4
x1 , x2 , x3 , x4 , s1 , s2
s2
20 30
0
Kendala ini sudah memuat variabel basis, yaitu
s1
dan
s2 .
Fungsi tujuan dapat ditulis secara lengkap menjadi
f ( x1 , x2 , x3 , x4 , s1 , s2 ) 5 x1 3x2
2 x3 0 x4 0s1 0s2
Langkah 2 Tabel simpleks awalnya adalah
cj
ci
xj
5
3
2
0
0
0
x1
x2
x3
x4
s1
s2
bi
Ri
xi 0
s1
4
5
2
1
1
0
20
5
0
s2 zj
3
4
-1
1
0
1
30
10
0
0
0
0
0
0
0
zj- cj
-5
-3
-2
0
0
0
0
Handout Pemrograman Linier 2016_Himmawati
Page 5
Langkah 3
z j -cj
Karena masih terdapat
0 , maka tabel belum optimal.
Langkah 4 -
variabel masuk Nilai
z j -cj
0
terkecil ada pada kolom variabel
x1
sehingga
x1
merupakan
variabel baru yang masuk -
variabel keluar Nilai
Ri
terkecil adalah 5, yaitu pada variabel
s1 , sehingga s1
keluar digantikan
x1 -
memperbaiki tabel Elemen pivotnya adalah 4 yang terletak pada perpotongan kolom
x1 dan baris s1 .
Untuk mengubah 4 menjadi 1, dilakukan OBE yaitu mengalikan baris 1 dengan 1 4
x1
. Elemen pada kolom
lainnya, yaitu 3 diubah menjadi 0 dengan melakukan
OBE menambah baris ke-2 dengan
-3 kali baris ke-1 baru. Diperoleh tabel
simpleks baru sebagai berikut.
cj
ci
xj
5
3
2
0
0
x1
x2
x3
x4
s1
0
bi
s2
Ri
xi 5 0
5.
x1 s2 zj
1
5/4
2/4
1/4
1/4
0
5
0
1/4
-5/2
1/4
-3/4
1
15
5
25/4
5/2
5/4
5/4
0
25
zj - cj
0
13/4
1/2
5/4
5/4
0
25
Menguji keoptimuman tabel Dari tabel lanjutan diperoleh bahwa z j
dengan
PO
cj
0 sehingga tabel sudah optimum
( x1 , x2 , x3 , x4 , s1 , s2 ) (5,0,0,0,0,15)
f (5,0,0,0,0,15)
dan
5.5 3.0 2.0 0.0 0.0 0.15
Handout Pemrograman Linier 2016_Himmawati
nilai
maksimum
25 Page 6
SOAL LATIHAN
Tentukan PO dan nilai optimal masalah PL berikut dengan metode simpleks. 1.
Memaksimumkan fungsi
z
3x 2 y
dengan kendala
5 x 6 y 70 6 x 10 y 65 10 x 8 y 55 x, y 0 2.
Memaksimumkan fungsi f ( x1 , x2 , x3 )
x1 2 x2
x3
2 x1
x2 3x3
x2
x3
4
Memaksimumkan fungsi
z 5 x1 7 x2 12 x3
2 x1 3x2
2 x3
x4
38
3x1
4 x3
x4
55
2 x2
x1
2 x2
30
x1
2 x3
45
x2
x3
x4
dengan kendala
0
Memaksimumkan fungsi
f ( x1 , x2 , x3 ) 2 x1 2 x2
x3 , dengan kendala
40
x1 , x2 , x3 5.
3
0
x1 , x2 , x3 , x4 4.
x3 dengan kendala
5
x1 , x2 , x3 3.
2 x1 8 x2
Meminimumkan
0
z
2x
y , dengan kendala
x 3y 4 2x 2 y 7 x, y
0
(Petunjuk: meminimumkan z = memaksimumkan – z)
2.
MASALAH PL MINIMUM BAKU
Handout Pemrograman Linier 2016_Himmawati
Page 7
Diberikan
masalah
PL
minimum
sebagai
berikut.
Meminimumkan
n
n
c j x j dengan kendala
f (xj )
baku
j 1
aij x j
bi ,
i, i 1,2,..., m,
xj
0, j , j 1,2,..., n
j 1
Dalam proses penyelesaian PL minimum, nilai fungsi tujuan akan makin diperkecil menuju ke nilai minimumnya, berkebalikan dengan pola maksimumn. Oleh karena itu, walaupun langkah-langkahnya sama dengan PL berpola maksimum, ada beberapa petunjuk yang berbeda.
Algoritma Simpleks PL minimum baku 1. Masalah PL dibawa ke bentuk kanonik Kendala pertidaksamaan diubah menjadi persamaan dengan menambahkan variabel surplus ti
0 ke ruas kanan pertidaksamaan. Koefisien
ti
pada fungsi
tujuan adalah 0. Karena kendala persamaan belum memuat basis, maka ditambahkan variabel artifisial
qi
0 ke ruas kiri pertidaksamaan yang akan menjadi basis dalam tabel
awal. Koefisien qi pada fungsi tujuan adalah M (M adalah bilangan positif cukup besar). 2. Susun tabel awal simpleks
cj xj
ci
c1
...
cn
0
...
0
M
...
M
x1
...
xn
t1
...
t2
q1
...
qm
bi
Ri
xi M
q1
a11
...
a1n
-1
...
0
1
...
0
b1
R1
M
q2
a21
...
a2 n
0
...
0
0
...
0
b2
R2
... M
...
...
...
... ...
... -1
... 0
... ...
... 1
...
a m1
... 0
...
qm
... ...
bm
Rm
zj
z1
...
zn
-M
...
-M
M
...
M
Z
zj - cj
z1 - c1
...
z n - cn
-M
...
-M
0
...
0
Z
a mn
3. Uji keoptimuman Tabel simpleks dikatakan optimum jika
z j - cj
Handout Pemrograman Linier 2016_Himmawati
0, j .
Page 8
Nilai fungsi tujuan ada pada baris ke m+1 kolom nilai
bi
bi
dan POnya adalah susunan
untuk variabel basis dan nol untuk variabel non basis.
Jika masih ada
z j - cj
0
, maka dilanjutkan langkah 4.
4. Memperbaiki tabel simpleks Memperbaiki tabel simpleks dilakukan dengan mengganti variabel basisnya dengan variabel basis yang baru dengan harapan variabel basis baru tersebut mengoptimalkan fungsi tujuan. Langkah memperbaiki tabel: -
menentukan variabel masuk yang akan menjadi variabel basis baru, yaitu variabel dengan
z j - cj
0
zk
terbesar. Misal
ck
terbesar, maka
xk
menjadi variabel masuk - menentukan variabel keluar yang akan digantikan oleh variebel basis baru. Pada kolom koefisien
xk , yaitu aik dihitung rasio R
i
pilih Ri terkecil. Misal Rl terkecil, maka
sl
bi , aik aik
0 , kemudian
menjadi variabel keluar.
- menyusun tabel baru.
s1 ,..., sl 1 , xk , sl 1 ,..., sm . Koefisien
Variabel basis baru dalam tabel baru adalah
alk aik
alk
menjadi elemen pivot. Pada kolom ke-k,
0, i l .
harus diubah menjadi 1 dan
Perubahan ini dilakukan dengan OBE dan berlaku untuk
semua elemen pada baris yang sesuai sehingga diperoleh tabel baru. 5. Lakukan kembali langkah 3 dan 4 sehingga optimum tercapai.
SOAL LATIHAN 1.
Hitunglah nilai minimum dari 100 x
20 y
2000 ,
40 x
f
3000 x 2000 y dengan kendala
80 y
3200 ,
60 x 60 y 3600 ,
x, y 0 . 2.
Tentukan nilai x, y yang meminimumkan
5x 6 y 3.
70 , 6 x 10 y
z
3x 2 y
dan memenuhi
65 , 10 x 8 y 55 , x, y 0 .
Selesaikan masalah PL :
Handout Pemrograman Linier 2016_Himmawati
Page 9
Meminimumkan
f
4x 5 y
z
Dengan kendala
x y z 3 x 2y 4 x, y , z
3.
0
METODE SIMPLEKS UNTUK KENDALA UMUM Masalah PL maksimum baku mempunyai kendala yang semua tandanya
sedangkan PL minimum baku semua kendalanya bertanda bertanda
,
,
. Jika kendala-kendalanya
, atau =, maka dikatakan PL berkendala umum. Secara umum, langkah
penyelesaiannya sama dengan PL maksimum baku atau minimum baku. Hanya saja ketika mengubah menjadi bentuk kanonik agak berbeda sedikit. Jika kendala bertanda
, maka ditambah variabel slack yang sekaligus menjadi
variabel basis. Jika kendala bertanda
, maka ditambah variabel surplus di ruas kanan
pertidaksamaan dan variabel artifisial (variabel artifisial akan menjadi variabel basis). Jika kendala bertanda = maka ditambah variabel artifisial yang akan berperan sebagai variabel basis. Jika PL berpola memaksimumkan maka koefisien variabel artifisial pada fungsi tujuan adalah –M, sedangkan jika berpola minimum maka koefisien variabel artifisial adalah M dengan M bilangan positif yang cukup besar.
CONTOH 2 Akan dicari pasangan nilai x, y, z tak negatif yang memaksimumkan
f
3x 5 y 2 z
yang memenuhi
2y z
2
x 4 y 2z
5.
2y z
2
Kendala 1,
memuat sumber daya/suku tetap yang bernilai negatif
sehingga harus dikalikan -1 menjadi
2y
z
Handout Pemrograman Linier 2016_Himmawati
2 . Pada kendala 1 perlu ditambahkan Page 10
variabel surplus t dan variabel artifisial q. Kendala 2 sudah bertanda = sehingga tidak perlu ditambahklan variabel slack atau variabel surplus. Kendala 2 juga sudah memuat variabel basis, yaitu x. Dengan demikian, PL siap simpleks (berbentuk kanonik) berbentuk: Memaksimumkan
f
3x 5 y 2 z 0t
Dengan kendala
2y
z t
q
x 4 y 2z
Mq
2
5
x, y, z, t , q
0.
Selanjutnya, tabel simpleks masalah PL ini sebagai berikut.
cj
ci
xj
xi
3
5
2
0
-M
x
y
z
t
q
-1 0 M M -1 2 4 4
1 0 -M 0 1 -2 -4 M-4
-M 3
q 0 -2 1 x 1 4 2 zj 3 12+2M 6-M zj-cj 0 7+2M 4-M 2 z 0 -2 1 3 x 1 8 0 zj 3 20 2 zj-cj 0 15 0 PO (x, y, z, t, q) = (1, 0, 2, 0, 0).
bi
Ri
2 5 15-2M 15-2M 2 1 7 7
2 5/2
PO soal asli (x, y, z) = (1, 0, 2) dengan nilai maksimum f = 7.
SOAL LATIHAN
Tentukan PO dan nilai optimum masalah PL berikut dengan metode simpleks 1.
Memaksimumkan
f
x
y
dengan kendala
2x y 2 2x y 9 3x y 11 x, y 0 2.
Maksimumkan
2 x1
z 3x1 2 x2
x2 3x3
5 , x1 2 x2
4 x3
dengan kendala
x1
x3
3 , x1 , x2 , x3
0.
Handout Pemrograman Linier 2016_Himmawati
x2
x3 10 , Page 11
3.
x 2y 4.
z
Minimumkan
y
dengan kendala
3x
y
3 , 4x 3 y
6,
4 , x, y 0 .
Minimumkan
x1 2 x2
4x
z 3x1 2 x2 x3
4 x3
dengan kendala
30 , x1 2 x 2 3x3
Handout Pemrograman Linier 2016_Himmawati
4 x1 5 x2 2 x3
20 , x1 , x2 , x3
22 ,
0.
Page 12
