PROGRAM LINIEAR DENGAN METODE SIMPLEX
A. TEKNIK PENYELESAIAN Bentuk Soal Program Liniear p
Kedala utama masalah program liniear dapat berbentuk
aij x j bi atau j 1
p
atau
a x j 1
ij
j
p
a x j 1
ij
j
bi
bi . Kendala yang berbentuk pertidaksamaan daoat diubah menjadi
persamaan sebagai berikut : Misalnya kendala
2 x1 x2 3x3 8 dapat diganti menjadi 2x1 x2 3x3 t 8 Secara Umum p
(i).
a x j 1
ij
j
bi
Dalam ruas kiri disisipkan si sedemikian sehingga :
j
s j bi
dengan si ≥ 0
p
a x j 1
ij
p
Dalam hal ini si = 0 bila p
(ii).
a x j 1
ij
j
p
a x j 1
ij
j
bi bi ti atau
aij x j bi dan si > 0 bila j 1
p
a x j 1
ij
j
bi
Dalam ruas kanan disisipkan ti sedemikian sehingga : p
a x j 1
ij
j
ti bi dengan ti ≥ 0
Sesuai dengan peranannya, si , ti di atas disebut peubah pengetat (slack variabel), karena peranannya adalah untuk membuat ruas yang semula longgar menjadi ketat, sehingga sama nilainya dengan ruas yang lainnya. Jadi, misalnya diketahui susunan kendala :
2 x1 x 2 3x 3 8 x1 x2 x3 10 3 x1 x 3 7 x1 , x 2 , x 3 0 Susunan ini dapat diubah menjadi :
Metode Simplex untuk Masalah Program Linier
1
2 x1 x 2 3x 3 x 4 8 x1 x2 x3 x5 10 3 x1 x 3 7 x1 , x 2 , x 3 , x 4 , x 5 0 Muncul susunan persamaan liniear dengan x1 , x2 , x3 sebagai peubah asli dan
x4 , x5 sebagai peubah pengetat. Untuk menyesuaikan dengan bentuk kendala yang baru, fungsi sasaran yang semula berbentuk : p
f c j x j c1x1 c 2 x2 ... c p x p j 1
Dilengkapi menjadi : n
f c j x j c1x1 c 2 x2 ... c p x p 0( x p1 ... xn ) j 1
Dengan
c p1 c p2 ... cn 0 Dengan demikian soal akan berbunyi : Mencari Yang memenuhi :
Dan memaksimumkan (atau meminimumkan)
Bentuk soal seperti di atas (dengan semua kendala utama berbentuk persamaan) disebut bentuk kanonik dari soal program liniear. Apabila fungsi sasaran harus dimaksimumkan, maka soal disebut berpola maksimum, dan apabila fungsi sasaran harus diminimumkan maka soal disebut berpola minimum.
Metode Simplex untuk Masalah Program Linier
2
Contoh 1 : Ubahlah soal di bawah ini ke bentuk kanonik. Mencari x1, x2, x3 tak negatif yang memenuhi :
2 x1 x 2 x 3 6 x1 3x2 10 Dan memaksimumkan f 20x1 10x2 5x3 Jawab : Pada masing-masing kendala utama disisipkan suatu peubah pengetat namakan
x4 , x5 sehingga menjadi : Mencari x1 , x2 , x3 , x4 , x5 tak negative yang memenuhi :
2 x1 x 2 x 3 x 4 6 x1 3x2 x5 10 Dan memaksimumkan :
f 20x1 10x2 5x3 0x4 0x5 Soal ini sudah berbentuk kanonik dan berpola maksimum, dengan x1 , x2 , x3 sebagai peubah asli dan x4 , x5 adalah peubah pengetat. Contoh 2 : Tulislah bentuk kanonik dari soal yang berbunyi : Mencari u, v, w yang memenuhi :
3u 5 v w 20 u 5v 2 w 50 u v w 25 u, v, w 0 Dan meminimumkan f 100 3u v 5w Jawab : Pada masing-masing kendala utama sisipkan peubah s dan t, sehingga menjadi : Mencari u, v, w, s, t yang memenuhi :
3u 5v w s 20 u 5v 2 w t 50 u v w 25 u, v, w, s , t 0 Dan meminimumkan f 100 3u v 5w 0s 0t
Metode Simplex untuk Masalah Program Linier
3
B. TABEL SIMPLEX Berikut bentuk Tabel Simplex
Cj
C1
C2
…
Cn
Ci
xi \ x j
x1
x2
…
xn
bi
Ri
C1
x1
a11
a12
…
a1n
b1
R1
C2
x2
a21
…
a2n
b2
R2
…
…
…
…
…
…
…
…
Cm
xm
am 1
am 2
…
amn
bm
Rm
Zj
Z1
Z2
…
Zn
Z
Zj C j
Z1 C1
Z2 C 2
…
Zn Cn
Z
Dengan Ri
a22
bi , untuk aik 0 aik
xj
: Peubah-peubah lengkap.
aij
: Koefisien teknis.
bi
: Suku tetap (tidak negative)
Cj
: Koefisien ongkos
xi
: Peubah yang menjadi basis dalam tablo yang ditinjau
Ci
: Koefisien ongkos untuk peubah basis xi
Zj
:
Z
:
m
c a i 1
i ij
m
c b i 1
i i
(jumlah dari hasil kali c i dengan aij )
(jumlah dari hasil kali c i dengan bi )
Z j C j : Selisih Z j dengan C j
A. POLA MAKSIMUM BAKU Untuk memahami penerapan metode simplek dalam menyelesaikan program liniear diberikan contoh langsung.
Metode Simplex untuk Masalah Program Linier
4
Note : Pada pola maksimum baku, tablo sudah maksimum bila
untuk semua j
Kunci 1 Pilih k dengan
yang paling kecil. Maka
terpilih menjadi basis.
Kunci 2 Pilih p dengan
yang terkecil. Maka
terpilih untuk keluar dari basis.
Contoh : Tentukan nilai x, y agar f 32x 20y maksimum, dengan kendala :
2 x 5 y 600 4 x 3 y 530 2 x y 240 x, y 0 Jawab : Masalah di atas diubah dulu ke bentuk kanonik dengan menambahkan variabel r, s, dan t kedalam kendala. Sehingga diperoleh
2 x 5y r 600 4 x 3 y s 530 2 x y t 240 x, y , r , s, t 0
Dan memaksimumkan f 32x 20y 0(r s t ) Menyusun Tablo Awal. Tablo 1.
Cj
32
20
0
0
0
Ci
xi \ x j
x
y
r
s
t
bi
Ri
0
r
2
5
1
0
0
600
600/2 = 300
0
s
4
3
0
1
0
530
530/4 = 132,5
0
t
2
1
0
0
1
240
240/2 = 120
Zj
0
0
0
0
0
Z=0
Zj C j
-32
-20
0
0
0
Z=0
Metode Simplex untuk Masalah Program Linier
5
Untuk menyusun tablo yang kedua, harus dicari kolom yang memuat nilai yang
Z j C j 0 yang terkecil untuk menjadi basis. Dan baris yang memuat Ri yang terkecil untuk keluar dari basis. (Kunci 1 dan Kunci 2)
Cj
32
20
0
0
0
Ci
xi \ x j
x
y
r
s
t
bi
Ri
0
r
2
5
1
0
0
600
600/2 = 300
0
s
4
3
0
1
0
530
530/4 = 132,5
0
t
2
1
0
0
1
240
240/2 = 120
Zj
0
0
0
0
0
Z=0
Zj C j
-32
-20
0
0
0
Z=0
Langkah untuk menyusun tablo kedua : 1. Baris ke-3 baru = baris ke-3 lama : 2 2. Baris ke-1 baru = baris ke-1 lama – 2 kali baris ke-3 baru 3. Baris ke-2 baru = baris ke-2 lama – 4 kali baris ke-3 baru. 4. Baris ke-3 pada kolom C i diisi dengan 32 (koefisien x) dan pada kolom C j diisi dengan x (basis baru). 5. Hitung Z j dengan rumus Z j
m
c a i 1
i ij
Setelah melakukan proses di atas diperoleh susunan tablo kedua sebagai berikut : Tablo 2.
Cj
32
20
0
0
0
Ci
xi \ x j
x
y
r
s
t
bi
Ri
0
r
0
4
1
0
-1
360
360/4=90
0
s
0
1
0
1
-2
50
50/1=50
32
x
1
1 2
0
0
1 2
120
120/(1/2)=240
Zj
32
16
0
0
16
Z = 3840
Zj C j
0
-4
0
0
16
Z = 3840
Metode Simplex untuk Masalah Program Linier
6
Untuk menyusun tablo yang ketiga, harus dicari kolom yang memuat nilai yang
Z j C j 0 yang terkecil untuk menjadi basis. Dan baris yang memuat Ri yang terkecil untuk keluar dari basis (Kunci 1 dan Kunci 2)
Cj
32
20
0
0
0
Ci
xi \ x j
x
y
r
s
t
bi
Ri
0
r
0
4
1
0
-1
360
360/4=90
0
s
0
1
0
1
-2
50
50/1=50
32
x
1
1 2
0
0
1 2
120
120/(1/2)=240
Zj
32
16
0
0
16
Z = 3840
Zj C j
0
-4
0
0
16
Z = 3840
Langkah untuk menyusun tablo ketiga : 1. Baris ke-2 baru = baris ke-2 lama (karena pivot sudah = 1) 2. Baris ke-1 baru = baris ke-1 lama – 4 kali baris ke-2 baru 3. Baris ke-3 baru = baris ke-3 lama –
1 kali baris ke-2 baru. 2
4. Baris ke-2 pada kolom C i diisi dengan 20 (koefisien y) dan pada kolom C j diisi dengan y (basis baru). 5. Hitung Z j dengan rumus Z j
m
c a i 1
i ij
Setelah melakukan proses di atas diperoleh susunan tablo ketiga sebagai berikut : Tablo 3.
Cj
32
20
0
0
0
Ci
xi \ x j
x
y
r
s
t
bi
0
r
0
0
1
-4
7
160
20
y
0
1
0
1
-2
50
32
x
1
0
0
Zj
32
20
0
4
8
Z = 4040
Zj C j
0
0
0
4
8
Z = 4040
Metode Simplex untuk Masalah Program Linier
-
1 2
3 2
Ri
95
7
Membaca Penyelesaian. Nilai peubah basis r, y, x terbaca langsung pada kolom bi ialah 160, 50, 95, sedangkan nilai s dan t adalah nol karena s dan t peubah bukan basis yang memang diberi nilai nol, sehingga penyelesaian optimum soal tersebut berbunyi : (x, y, r, s, t) = (95, 50, 160, 0, 0) dengan nilai maksimum Z = 4040. Soal Latihan : 1.
Seorang pengusaha mebel membuat Almari dan Meja. Untuk membuat Almari diperlukan 1 batang besi, 5 lembar paku dan 3 ons paku. Sedangkan untuk membuat meja diperlukan 2 batang besi, 4 lembar kayu dan 1 ons paku. Persediaan untuk besi adalah 36 batang, untuk kayu 90 lembar dan untuk paku 45 ons. Laba yang diperoleh untuk satu almari adalah Rp. 40.000 dan laba untuk satu meja adalah Rp. 50.000. Buatlah model matematika, bentuk kanonik dari model matematika dan kemudian gunakan table simplex untuk menentukan produksi almari dan meja agar memperoleh keuntungan maksimum.
2.
Tentukan nilai u, v, w tak negative yang memenuhi : 2u + 3v – 5w ≤ 12 2u – v + 3w ≤ 3 3u + v – 2w ≤ 2 Dan memaksimumkan f = 9u + 2v + 5w
Metode Simplex untuk Masalah Program Linier
8
