BAB VIII
METODE REVISED SIMPLEX
8.1. Pendahuluan
Meskipun perhitungan yang sangat banyak dari metode big-M atau Dua Fase
dapat dilakukan dengan bantuan komputer, tetapi dalam penerapan di lapangan
terkadang kedua metode sebelumnya sangat tidak efisien. Hal ini akan tampak sangat
terlihat mencolok manakala terjadi kondisi yang tidak wajar. Apabila secara analisa di
kedua metode menyatakan bahwa telah terjadi kasus tidak ada penyelesaian tetapi
kesimpulan ini diperoleh setelah iterasi yang terakhir didapatkan dan ini sangat
memakan banyak waktu, sehingga dianggap tidak efisien.
Metode Revised simplex merupakan suatu prosedur sistematis untuk
mengimplementasikan langkah-langkah metode simpleks dalam suatu
susunan/kesatuan (array) yang lebih kecil, sehingga menghemat ruang (memory)
penyimpanan. Metode ini sangat efektif apabila jumlah kendala dan variabel yang
digunakan adalah sangat banyak dan lebih berdaya guna manakala terjadi
penyimpangan pada solusi layak dasar ang awal.
Deteksi awal dari teknik ini sangat diperlukan untuk kondisi di lapangan,
dimana setiap penentu kebijakan harus sesegera mungkin memutuskan permasalahan
yang dihadapi. Apalagi jika model program linier sudah terbentuk, maka sangat tidak
dianjurkan jika harus membuat berjumlah-jumlah iterasi hanya untuk memutuskan
sejumlah kecil keputusan tertentu saja.
8.2. Langkah Penyelesaian Simpleks yang Direvisi
Misalkan ada basis layak B (dengan invers B-1). Selanjutnya dilakukan sebagai
berikut:
1
1. Solusi basis layak adalah x B B b b dan xN = 0. Nilai fungsi tujuan
Z C B B 1b C b .
B
2. Hitung simpleks multipliers, w = CBB-1. Untuk setiap variabel non basis, hitung
harga dari Zj – Cj = CBB-1aj – Cj = waj – Cj. Misalkan Zk – Ck = Maksimum dari Zj
– Cj. Jika Zk – Ck 0, maka berhenti, dan solusi yang sedang berlaku sudah
optimal. Jika Zk – Ck > 0, maka lanjutkan ke langkah 3.
3. Hitung yk = B-1ak. Jika yk 0 , maka berhenti dan solusi optimalnya adalah
tidak terbatas. Untuk kondisi lainnya, tentukan indeks dari variabel xBr yang akan
meninggalkan basis
b
br i
Minimum ; y ik 0
y rk 1 i m y ik
Perbaharui B dengan mengganti aBr dengan ak dan kembali ke langkah 1.
Dari langkah-langkah tersebut, metode simpleks dapat dilakukan dengan
menggunakan suatu susunan (array) yang lebih kecil. Misalkan ada solusi basis layak
B dengan invers B-1. Susunan berikut dapat dibangun dimana w = CBB-1 dan
b B 1 b .
INVERS BASIS RHS
W CBb
B-1 b
Tabel di atas disebut tabel revised simplex. Bayangkan seolah-olah kita
menjalankan algoritma simpleks pada seluruh tabel, tetapi semua informasi
disembunyikan, kecuali:
1) Informasi yang ada pada susunan di atas (tabel revised simplex)
2) Informasi lain yang dibutuhkan.
Informasi pertama yang dibutuhkan adalah nilai-nilai dari Zj – Cj. Karena w
diketahui, maka nilai-nilai tersebut dapat dihitung seperti pada langkah 2 untuk
memeriksa keoptimalan solusi. Misalkan Zk – Ck > 0. Selanjutnya kita ingin
memeriksa kolom yang diperbaharui dari xk. Dengan menggunakan B-1, kita dapat
menghitung yk = B-1ak. Jika yk 0, maka berhenti dan nilai solusi optimal adalah
tidak terbatas. Untuk kondisi lainnya, kolom yang diperbaharui dari xk dapat
ditambahkan pada tabel revised simplex, sedangkan informasi-informasi lainnya tetap
disembunyikan.
INVERS BASIS RHS Xk
W CBb Zk - Ck
b1 y1k
y2k
b2
:
:
B-1 :
:
yrk
br :
: :
: ymk
bm
Indeks r pada langkah 3 sekarang dapat dihitung dengan menggunakan uji rasio
minimum. Operasi pivot pada yrk akan menghasilkan nilai-nilai baru dari w, B-1,
dan b dan CB b , dan prosesnya diulangi.
8.3. Tabel Simpleks yang Direvisi
1. Langkah Inisialisasi
Temukan suatu solusi basis layak dengan invers B-1.
Hitung w = CBB-1 dan b = B-1b
Bentuk tabel Revised Simplex
INVERS BASIS RHS
W CBb
B-1 b
2. Langkah Pokok
Untuk setiap variabel non basis, hitung Zj – Cj = waj – Cj.
Misalkan Zk – Ck = Maksimasi dari Zj – Cj. Jika Zk – Ck 0, maka berhenti
dan solusi basis layak yang ada sudah optimal.
Untuk kondisi lainnya, hitung yk = B-1ak. Jika yk 0, maka berhenti dan
nilai solusi optimal adalah tidak terbatas. Jika yk 0, masukkan kolom
Zk Ck
di sebelah kanan tabel sehingga diperoleh tabel berikut:
y k
INVERS BASIS RHS Xk
W CBb Zk - Ck
B-1 b y1k
Tentukan indeks r sebagai berikut:
b
br i
Minimum ; y ik 0
y rk 1 i m y ik
Lakukan operasi pivot pada yrk dan ini akan memperbaharui tabel. Sekarang
kolom yang berkorespondensi dengan xk dihilangkan dari tabel.
Ulangi langkah Utama.
8.4. Kejadian Tanpa Artifisial
Contoh:
Minimasi -x1 –2x2 + x3 – x4 – 4x5 + 2x6
Kendala x1 + x2 + x3 + x4 + x5 + x6 6
2x1 - x2 - 2x3 + x4 4
x3 + x4 + 2x5 + x6 4
x1, x2, x3, x4, x5, x6 0
Tambahkan variabel-variabel slack x7, x8, dan x9. Basis awal adalah B = [a7, a8, a9] =
I3; w = CBB-1 = (0 0 0); dan b = b.
Iterasi 1.
INVERS BASIS RHS
Z 0 0 0 0
x7 1 0 0 6
x8 0 1 0 4
x9 0 0 1 4
w = (0, 0, 0); Zj –Cj = waj – Cj.
Z1 – C1 = 1
Z2 – C2 = 2
Z3 – C3 = -1 k = 5, x5 : masuk ke dalam basis
Z4 – C4 = 1
Z5 – C5 = 4
Z6 – C6 = -2
1 0 0 1 1
y5 = B-1a5 = 0 1 0 0 0
0 0 1 2 2
Z5 C5 4
Masukkan vektor di kanan tabel
y 5 1
0
2
INVERS BASIS RHS x5
Z 0 0 0 0 4
x7 1 0 0 6 1
x8 0 1 0 4 0
x9 0 0 1 4 2
Pivot pada y35 = 2
INVERS BASIS RHS
Z 0 0 -2 -8
x7 1 0 -1/2 4
x8 0 1 0 4
x5 0 0 1/2 2
Iterasi 2.
1 0 1 / 2
CB = (C7, C8, C5) = (0, 0, -4) b = 0 1 0 b
0 0 1 / 2
Z = CB b = -8
1 0 1 / 2
W = CBB-1 = (0, 0, -4) 0 1 0 = (0, 0, -2)
0 0 1 / 2
Zj – Cj = waj – Cj
1 1
Z1 – C1 = (0, 0, -2) 2 - (-1) = 1; Z2 – C2 = (0, 0, -2)
1 - (-2) = 2
0 0
1 1
Z3 – C3 = (0, 0, -2) 2 - 1 = -3; Z4 – C4 = (0, 0, -2)
1 - (-1) = -1
1 1
1 0
Z6 – C6 = (0, 0, -2) 0 - 2 = -4; Z9 – C9 = (0, 0, -2)
0 - 0 = -2
1 1
k = 2, x2: masuk ke basis
1 0 1 / 2 1 1
y2 = B-1a2 = 0 1 0
1 1
0 0 1 / 2 0 0
Z2 C2 2
Masukkan vektor di kanan tabel.
y 2 1
- 1
0
INVERS BASIS RHS X2
Z 0 0 -2 -8 2
x7 1 0 -1/2 4 1
x8 0 1 0 4 -1
X5 0 0 1/2 2 0
Pivot pada y12 = 1
INVERS BASIS RHS
Z -2 0 -1 -16
x2 1 0 -1/2 4
x8 1 1 -1/2 8
x5 0 0 1/2 2
Iterasi 3.
CB = (C2, C8, C5) = (-2, 0, -4)
1 0 1 / 2
w = CBB-1 = (-2, 0, -4) 1 1 1 / 2 = (-2, 0, -1)
0 0 1 / 2
Zj – Cj = waj - Cj
1
Z1 – C1 = (-2, 0, -1) 2 - (-1) = -1;
0
1 1
Z3 – C3 = (-2, 0, -1) 2 - 1 = - 4; Z4 – C4 = (-2, 0, -1)
1 - (-1) = - 2
1 1
1 1
Z6 – C6 = (-2, 0, -1) 0 - 2 = - 5; Z7 – C7 = (-2, 0, -1)
0 - 0 = -2
1 0
0
Z9 – C9 = (-2, 0, -1) 0 - 0 = - 1
1
Karena Zj – Cj 0 untuk semua variabel non basis, maka berhenti; solusi basis layak
yang ada adalah optimal.
Solusi optimalnya: x1 = 0, x2 = 4, x3 = 0, x4 = 0, x5 = 2, x6 = 0 dan Z = -16
8.5. Kondisi Dengan Artifisial
Contoh:
Minimasi Z = -3x1 + x2 + x3
Kendala x1 - 2x2 + x3 11
-4x1 + x2 + 2x3 3
2x1 - x3 = -1
x1, x2, x3 0
Tambahkan variabel-variabel slack x4 dan x5 dan kalikan kendala ke-3 dengan –1.
x1 - 2x2 + x3 + x4 = 11
-4x1 + x2 + 2x3 - x5 = 3
-2x1 + x3 =1
Tambahkan variabel-variabel artifisial x6 dan x7, dan misalkan digunakan Metode
Big-M.
Minimasi -3x1 + x2 + x3 + Mx6 + Mx7
Kendala x1 - 2x2 + x3 + x4 = 11
-4x1 + x2 + 2x3 - x5 + x6 =3
-2x1 + x3 + x7 = 1
x1, x2, x3, x4, x5, x6, x7 0
1 2 1 1 0
a1= 4 ; a2 = 1 ;a =
3
2 ; a =
4
0 ; a =
5
1
2 0 1 0 0
0 0 11
a6 = 1 ; a7 = 0 ; b =
3
0 1 1
B = [a4, a6, a7] = I3 ; B-1 = I3
w = CBB-1 = (C4, C6, C7) I3 = (0, M, M)
11 11
b B 1b 3 ; Z = CBB-1b = (0, M, M) 3 = 4M
1 1
Iterasi 1.
INVERS BASIS RHS
Z 0 M M 4M
x4 1 0 0 11
x6 0 1 0 3
x7 0 0 1 1
Zj – Cj = waj - Cj
1
Z1 – C1 = (0, M, M) 4 - (-3) = - 6M + 3;
2
2 1
Z2 – C2 = (0, M, M) 1 - 1 = M-1; Z3 – C3 = (0, M, M)
2 - 1 = 3M-1
0 1
0
Z5 – C5 = (0, M, M) 1 - 0 = - M
0
1
k = 3 dan x3 masuk ke dalam basis. y3 = B-1a3 = 2
1
Z 3 C3 3M 1
Masukkan vektor di kanan tabel
y3 1
2
1
INVERS BASIS RHS x3
Z 0 M M 4M 3M-1
x4 1 0 0 11 1
x6 0 1 0 3 2
x7 0 0 1 1 1
Pivot pada y33 = 1
INVERS BASIS RHS
Z 0 M -2M+1 M+1
x4 1 0 -1 10
x6 0 1 -2 1
x3 0 0 1 1
Iterasi 2.
CB = (C4, C6, C3) = (0, M, 1)
1 0 1
w = CBB-1 = (0, M, 1) 0 1 2 = (0, M, -2M+1)
0 0 1
Zj – Cj = waj - Cj
1
Z1 – C1 = (0, M, -2M+1) 4 - (-3) = 1;
2
2
Z2 – C2 = (0, M, -2M+1) 1 - 1 = M - 1;
0
0
Z5 – C5 = (0, M, -2M+1) 1 - 0 = - M ;
0
0
Z7 – C7 = (0, M, -2M+1) 0 - M = -3M + 1;
1
k = 2 dan x2 masuk ke dalam basis
1 0 1 2 2
y2 = B-1a2 = 0 1 2
1 = 1
0 0 1 0 0
Z C 2 M 1
Masukkan vektor 2 di kanan tabel.
y 2 - 2
1
0
INVERS BASIS RHS x2
Z 0 M -2M+1 M+1 M-1
x4 1 0 -1 10 -2
x6 0 1 -2 1 1
x3 0 0 1 1 0
Pivot pada y22 = 1
INVERS BASIS RHS
Z 0 1 -1 2
x4 1 2 -5 12
x2 0 1 -2 1
x3 0 0 1 1
Iterasi 3.
CB = (C4, C2, C3) = (0, 1, 1)
1 2 5
w = CBB-1 = (0, 1, 1) 0 1 2 = (0, 1, -1)
0 0 1
Zj – Cj = waj - Cj
1
Z1 – C1 = (0, 1, -1) 4 - (-3) = 1;
2
0
Z5 – C5 = (0, 1, -1) 1 - 0 = - 1 ;
0
0
Z6 – C6 = (0, 1, -1) 1 - M = - M + 1;
0
0
Z7 – C7 = (0, 1, -1) 0 - M = - M - 1;
1
k = 1 dan x1 masuk ke dalam basis
1 2 5 1 3
y1 = B-1a1 = 0 1 2
4 = 0
0 0 1 2 2
Z1 C1 1
Masukkan vektor di kanan tabel.
y1 3
0
2
INVERS BASIS RHS x1
Z 0 1 -1 2 1
x4 1 2 -5 12 3
x2 0 1 -2 1 0
x3 0 0 1 1 -2
Pivot pada y11 = 3
INVERS BASIS RHS
Z -1/3 1/3 2/3 -2
x1 1/3 2/3 -5/3 4
x2 0 1 -2 1
x3 2/3 4/3 -7/3 9
Iterasi 4.
CB = (C1, C2, C3) = (-3, 1, 1)
1 / 3 2 / 3 5 / 3
w = CBB-1 = (-3, 1, 1) 0 1 2 = (-1/3, 1/3, 2/3)
2 / 3 4 / 3 7 / 3
1
Z4 – C4 = (-1/3, 1/3, 2/3) 0 - 0 = -1/3;
0
0
Z5 – C5 = (-1/3, 1/3, 2/3) 1 - 0 = - 1/3 ;
0
0
Z6 – C6 = (-1/3, 1/3, 2/3) 1 - M = - M + 1/3;
0
0
Z7 – C7 = (-1/3, 1/3, 2/3) 0 - M = - M + 2/3;
1
Solusi sudah optimal
x1 = 4
x2 = 1 x4 = x5 = x6 = x7 = 0
x3 = 9
Z = -2
8.6. Penutup
Pada permasalahan minimisasi kita jumpai fungsi kendala dengan tanda ≥ ,
artinya bahwa kita dapat menggunakan sumberdaya lebih dari yang tersedia. Pertanyaan
yang muncul adalah berapa besarnya kelebihan sumberdaya yang telah kita gunakan dari
yang tersedia ? Untuk menyatakan kelebihan sumberdaya yang digunakan dari yang
tersedia ini, maka kita harus mengurangi kendala tersebut dengan surplus variabel.
Surplus variabel ini sering juga disebut sebagai slack variabel yang negatif.
Karena nilai solusi pada permasalahan LP harus non-negatif maka untuk
mengatasi masalah ini kita harus menambahkan artificial variabel (A). Artificial
variabel ini secara phisik tidak mempunyai arti, dan hanya digunakan untuk kepentingan
perhitungan saja.
Soal-soal
1. Suatu perusahaan akan memproduksi 2 macam barang yang jumlahnya tidak
boleh lebih dari 18 unit. Keuntungan dari kedua produk tersebut masing-
masing adalah Rp. 750,- dan Rp. 425,- per unit. Dari survey terlihat bahwa
produk I harus dibuat sekurang-kurangnya 5 unit sedangkan produk II
sekurang-kurangnya 3 unit. Mengingat bahan baku yang ada maka kedua
produk tersebut dapat dibuat paling sedikit 10 unit. Tentukan banyaknya
produk yang harus dibuat untuk mendapatkan keuntungan yang maksimum
(dengan menggunakan Simpleks yang direvisi)?
2. Sebuah pabrik obat menyediakan 2 jenis campuran A dan B. Bahan-bahan
dasar yang terkandung dalam tiap kg campuran A dan B adalah sebagai
berikut:
Dari campuran A dan B hendak dibuat campuran C. Campuran C ini
sekurang-kurangnya mengandung bahan-1 sebanyak 4 kg dan bahan-2
sebanyak 3 kg. Harga tiap kg campuran A adalah Rp. 20.000,00 dan tiap kg
campuran B adalah Rp.10.000,00. Berapakah campuran A dan B harus dibeli
supaya biaya total pembuatan campuran C semurah-murahnya dan berapa
biaya yang harus dikeluarkan (dengan menggunakan Simpleks yang direvisi)?
3. Sebuah usaha penggemukan ayam potong menggunakan tiga jenis pakan
ternak, Grade 1, Grade 2 dan Grade 3.
Grade
I II III
Ca 0,7 0,8 0
Kandungan Fe 0,9 0,8 0,8
(dalam
gram) Protein 0,8 1,5 0,9
Lemak 0,5 0,6 0,4
Biaya ketiga jenis pakan ternak tersebut per pon berturut-turut adalah sebagai
berikut : $ 0.25, $ 0.10 dan $ 0.08. Sebagai syarat nutrisi pakan ternak per hari
adalah : kandungan kalsium minimal 10 gram, kandungan zat besi minimum
12 gram, kandungan protein minimum 15 gram, kandungan lemak maksimum
7.5 gram. Tentukan biaya yang paling minimum yang memenuhi syarat gizi
pakan ternak per hari melalui kombinasi penggunaan Grade 1, Grade 2 dan
Grade 3 (dengan menggunakan Simpleks yang direvisi).
4. Queen City Inc. memproduksi kue. Perencana produksi melihat bahwa dua
jenis produk yang memberikan nilai tambah cukup signifikan, yaitu :Toplegit
(T) dan Biglegit (B). Setiap kilogram T membutuhkan 10 buah komponen
bumbu, sedang setiap kilogram B membutuhkan 7 buah komponen bumbu.
Pada bulan ini perusahaan hanya dapat menyediakan komponen tersebut
sebanyak 49 buah. Bagian penjualan diperkirakan cukup puas jika bagian
produksi dapat menyiapkan minimal 5 kue untuk dijual. Keuntungan/unit T =
$50,000 dan B = $ 34,000 (dengan menggunakan Simpleks yang direvisi).
5. Galuh Chemical Company harus membuat 1000 unit campuran phospate dan
postassium. Biaya per unit phospate adalah $5, sedangkan biaya per unit
postassium $6. Jumlah phospate yang dapat digunakan tidak lebih dari 300 unit
sedangkan postassium harus digunakan minimal 150 unit. Berapa masing-masing
jumlah phospate dan postassium yang harus digunakan agar biaya total minimum
(dengan menggunakan Simpleks yang direvisi)?
6. Perusahaan kimia memproduksi campuran kimia untuk seorang langganan
dalam batch pon. Campuran berisi tiga komponen zinc, mercury dan potasium.
Campuran harus memenuhi spesifikasi formula tertentu yang diberikan oleh
pelanggan. Perusahaan ingin mengetahui jumlah campuran yang dapat
memenuhi semua persyaratan dan meminimumkan total biaya. Pelanggan
memberikan spesifikasi formula untuk setiap batch campuran sbb:
a. Campuran harus berisi paling sedikit 200 pon mercury
b. Campuran harus berisi paling sedikit 300 pon zinc
c. Campuran harus berisi paling sedikit 100 pon potasium
d. Biaya per pon untuk mercury adalah $ 4; untuk zincc $8 dan untuk
pottasium $9
7. Bob Sadino sebagai manajer perusahaan penghasil sosis menghadapi masalah
perubahan harga bahan baku dan secara langsung mengadakan evaluasi
terhadap proporsi campuran bahan yang digunakan dalam pembuatan paling
sedikit 1 kuintal sosis. Hasil analisis menemukan presentase presentase protein
tidak boleh kurang dari 15%, lemak tidak boleh melebihi 30%. Serat paling
banyak 40% dan karbohidrat paling sedikit 20%. Protein, lemak, serat, dan
karbohidrat tersebut dapat diperoleh dari empat jenis bahan baku yang
memiliki karakteristik dan harga yang berbeda seperti diperlihatkan pada table
berikut:
Bahan Protein Lemak Serat Karbohidrat Harga/kg
A 40% 10% 20% 20% Rp. 800
B 20% 15% 30% 40% Rp. 700
C 10% 35% 15% 25% Rp. 400
D 15% 40% 10% 30% Rp. 200
Selesaikan program linear dari masalah di atas (dengan menggunakan
Simpleks yang direvisi).
Daftar Pustaka
Lieberman, G. J., and Hillier, F.S., Operations Research, Eighth Edition, Holden Day,
Inc. San Fransisco, 2005
Taha, H. A., Operations Research: An Introduction, Seventh Edition, Prentice Hall,
2004
Winston, W. C., Operations Research, International Edition, Thomson Learning, Inc.,
Belmont, C.A., 2004