Minggu, 12 April 2009

metode simplex

http://e-learning.unram.ac.id/riset/pdf-doc/modul/Dokumen/Simplex.pdf

II. PROGRAM LINIER: METODE SIMPLEX
Persoalan program linier tidak selalu sederhana karena melibatkan banyak
constraint (pembatas) dan banyak variabel sehingga tidak mungkin
diselesaikan dengan metode grafik. Oleh karena itu serangkaian prosedur
matematik (aljabar linier) diperlukan untuk mencari solusi dari persoalan
yang rumit tersebut. Prosedur yang paling luas digunakan adalah Metode
Simplex. Penemuan metode ini merupakan lompatan besar dalam Riset Operasi
dan ia digunakan sebagai prosedur penyelesaian dari setiap program
komputer.
Bentuk Aljabar Metode Simplex
Dengan menggunakan contoh pada kasus perusahaan TAS terdahulu maka model
linier persoalan tersebut dapat dinyatakan sebagai berikut:
Max. Z = 3X1 + 2X2
Subject to
2X1 + 2X2 <= 800
2X1 + 3.3X2 <= 1000
1X1 + 0.5X2 <= 300
2X1 + 1.5X2 <= 650
Dengan menyertakan variabel Slack atau surplus maka model tersebut dibuat
menjadi bentuk standar berikut:
Max. Z = 3X1 + 2X2 + 0S1 + 0S2 + 0S3 + 0S4
Subject to constraint:
2X1 + 2X2 + 1S1 = 800 ... (1)
2X1 + 3.3X2 + 1S2 = 1000 ... (2)
1X1 + 0.5X2 + 1S3 = 300 ... (3)
2X1 + 1.5X2 + 1S4 = 650 ... (4)
X1,X2,S1,S2,S3,S4 ≥ 0
Properti Aljabar Metode Simplex
Keempat fungsi pembatas tersebut merupakan suatu persamaan sistem dengan
enam variabel. Jika suatu sistem persamaan memiliki veriabel yang lebih
banyak dibanding dengan jumlah persamaannya maka solusi dari persamaan
sistem tersebut adalah infinity. Metode simplex dengan demikian merupakan
prosedur aljabar untuk mendapatkan solusi terbaik bagi suatu sistem
persamaan. Dalam proses mencari solusi terbaik (best solution), solusi yang
tidak memenuhi persyaratan non negatif akan dieliminasi.
Mendapatkan Solusi dasar
Oleh karena jumlah variabel dalam persamaan sistem lebih besar dibanding
jumlah persamaaannya –-dalam hal ini ada enam variabel untuk empat
persamaan-- maka metode simplex memberikan nilai nol untuk dua variabel,
dan mencari solusi terbaik bagi empat variabel lainnya dalam sistem
persamaan tersebut. Misalkan X2 = 0 dan S1 = 0 sehingga persamaan sistem
tersebut menjadi:
2X1 = 800 ... (5)
2X1 + 1S2 = 1000 ... (6)
1X1 + 1S3 = 300 ... (7)
2X1 + 1S4 = 650 ... (8)
Dengan menetapkan nilai nol untuk variabel X2 dan S1 maka persamaan sistem
tersebut direduksi menjadi empat persamaan dengan empat variabel
(X1,S2,S3,S4).
Dari persamaan (5) diperoleh
2
2X1 = 800
sehingga X1 = 800/2 = 400.
Dari persamaan (6) masukkan nilai x1 = 400 untuk mendapatkan nilai S2 yaitu
2X1 + 1S2 = 1000
sehingga S2 = 1000 – (2*400) = 200
Dari persamaan (7) diperoleh
1X1 + 1S3 = 300
sehingga S3 = 300 – 400 = -100
Dari persamaan (8) diperoleh
2X1 + 1S4 = 650
sehingga diperoleh S4 = 650 – (2*400) = -150
Dengan demikian diperoleh solusi dari persamaan sistem dengan enam variabel
dan empat persamaan, yaitu:
X1 = 400
X2 = 0
S1 = 0
S2 = 200
S3 = -100
S4 = -150
Solusi diatas disebut Solusi dasar (Basic Solution).
Prosedur umum untuk mendapatkan basic solution adalah dengan membangun
bentuk persamaan standar untuk n variabel (termasuk variabel keputusan,
slack dan surplus) dan m persamaan pembatas dimana n lebih besar dari m.
Solusi Dasar
Untuk mendapatkan solusi dasar, tetapkan n-m variabel mana saja sebagai
variabel non basic dan beri nilai nol dan temukan solusi dari m
persamaan pembatas untuk m variabel lainnya.
Solusi fisibel dasar (Basic Feasible Solution)
Solusi dasar mungkin saja fisibel atau infisibel. Sebuah solusi dasar
fisibel akan memenuhi persyaratan tidak negatif. Solusi dasar yang
diperoleh diatas dengan menetapkan X2 dan S1 sebagai variabel bukan basis
dan bernilai sama dengan nol telah mendapatkan solusi untuk nilai
X1,S2,S3,S4 bukan sebagai solusi dasar fisibel karena nilai S3 = -100 dan
S4 = -150. Oleh karena itu pemilihan variabel bukan basis perlu diubah.
Jadi jika variabel yang dipilih sebagai variabel bukan basis adalah X1 dan
X2 dan bernilai nol maka solusi basis yang diperoleh adalah fisibel, yaitu:
S1 = 800
S2 = 1000
S3 = 300
S4 = 650
dengan variabel bukan basis X1 = 0 dan X2 = 0.
3
Daerah fisibel beserta titik-titik ekstrim dari persoalan perusahaan TAS
tersebut disajikan pada gambar berikut:
Pemeriksaan&Pengepakan
0 X1
X2
5
4
3
2
Pemotongan
Penjahitan
Penyelesaian
〇1 〇



300
400
300 400 500
600
325
433
Prosedur penyelesaian program linear dengan Metode Simplex
1. Formulasikan persoalan menjadi model linear
2. Transformasikan model tersebut kedalam bentuk standar dengan
menambahan variabel slack atau mengurangi dengan variable surplus
3. Buatlah tableau form
Menyusun Tabel Simplex Awal (Initial Simplex Tableau)
Setelah melakukan konversi program linier kedalam tabel simplex maka tahap
pertama adalah membangun tabel simplex awal (initial simplex tableau). Pada
tahap ini termasuk pemberian notasi bagi semua koefisien yaitu:
cj = koefisien fungsi tujuan untuk variabel j
bi = koefisien sisi kanan (RHS) untuk constraint ke i
aij = koefisien yang berasosiasi dengan variabel j pada constraint i
Koefisien-koefisien ini merupakan bagian yang menyususn tabel simplex
seperti berikut:
C1 C2 ... Cn bi
a11 a12 ...a1n
a21 a22 ...a2n
. . ... .
. . ... .
. . ... .
am1 am2 ...amn
b1
b2
.
.
.
.
bm
Jadi tabel simplex awal untuk persoalan perusahaan TAS adalah
4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Baris pertama tabel simplex awal tersebut menunjukkan koefisien dari
masing-masing variabel pada fungsi tujuan, sedangkan koefisien di bawahnya
dan di sebelah kiri garis vertikal merupakan koefisien dari masing-masing
variabel pada setiap constraint. Elemen di sebelah kanan garis vertikal
menunjukkan nilai dari sisi kanan dari constraint. Demi kemudahan, setiap
kategori koefisien diperlakukan sebagai suatu grup yang terdiri dari:
Baris C = baris dari koefisien fungsi tujuan
Kolom B = kolom dari nilai sisi kanan masing-masing constraint
Matrik A = marupakan matrik m x n dari koefisien masing-masing
variabel pada setiap constraint.
Baris C
Matrix
A
Kolom
B
Guna lebih memudahkan dalam mengingat masing-masing koefisien maka di
bagian paling atas tabel simplex dituliskan simbol masing-masing variabel
menjadi:
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Dari tabel simplex awal dapat diketahui dengan mudah solusi fisibel dasar
awal (initial basic feasible solution) karena untuk setiap kolom dari
variabel basis terdapat koefisien yang bernilai satu demikian juga untuk
setiap barisnya. Nilai dari variabel basis dengan demikian dinyatakan oleh
nilai sisi kanan yang berada pada kolom bi. Misalkan nilai S2 adalah 1000
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0 bi
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Perbaikan Solusi
Guna meningkatkan solusi maka metode simplex harus menghasilkan solusi
fisibel dasar (basic feasible solution) yang baru (ekstreme point) yang
memberikan perbaikan pada nilai fungsi tujuan. Hal ini dilakukan dengan
mengganti salah satu variabel basis dengan variabel bukan basis, artinya
Nilai S2
Kolom Baris yang berasosiasi dengan variable S2 yang berasosiasi dengan variable S2
5
menetapkan variabel yang semula adalah bukan basis untuk menggantikan satu
variabel yang semula variabel basis. Metode simplex memberikan cara dan
prosedur untuk proses penggantian variabel ini.
Untuk lebih memudahkan proses maka ditambahkan dua kolom pada bagian kiri
tabel simplex awal, satu kolom diberi label Basis dan kolom lainnya diberi
label Cb. Pada kolom basis ditulis nama variabel basis sedangkan pada kolom
Cb ditulis nilai koefisien dari variabel basic tersebut seperti terdapat
pada fungsi tujuan.
Untuk kasus perusahaan TAS maka Tabel Simplex menjadi
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Untuk mengetahui apakah perbaikan solusi masih dapat dilakukan, maka
ditambahkan dua baris lagi pada bagian bawah tabel simplex ini. Baris yang
satu diberi label Zj yang menunjukkan perubahan pada nilai fungsi tujuan
jika satu unit variabel matrik A pada kolom j dimasukkan menjadi variabel
basis. Baris yang kedua diberi label Cj-Zj yang menyatakan pengaruh neto
dari pemasukan satu unit variabel tersebut pada nilai fungsi tujuan. Baris
ini disebut baris evaluasi netto (net evaluation row).
Berikut disajikan bagaimana elemen baris Zj disusun bila satu unit variabel
X1 menjadi variabel dasar sedangkan variabel X2 tetap sebagai bukan
variabel dasar yang bernilai nol. Dari persamaan pembatas (constraint)
pertama diketahui:
2X1 + 2X2 + 1S1 = 800
Variabel dasar saat ini adalah S1, dan jika X1 yang merupakan bukan
variabel dasar nilainya ditingkatkan satu unit dari 0 menjadi 1 maka nilai
S1 harus dikurangi 2 unit agar tetap memenuhi pembatas pertama tersebut.
Dari pembatas kedua dan seterusnya maka variabel S2 juga harus dikurangi 2
unit, variabel S3 berkurang 1 unit dan variabel S4 berkurang 2 unit.
Setelah dilakukan analisis untuk semua persamaan pembatas maka dapat
dikatakan koefisien pada kolom X1 menunjukkan jumlah unit dari variabel
dasar harus dikurangkan dengan masuknya variabel X1 menjadi variabel dasar
bernilai 1 untuk tetap menjaga terpenuhinya semua pembatas. Hal yang sama
dapat dilakukan untuk bukan variabel dasar lainnya seperti X2. Dengan
menetapkan X1 sebagai bukan variabel dasar benilai 0 maka untuk satu unit
penambahan nilai X2 dari 0 menjadi 1 maka variabel S1 harus dikurangi 2
unit, S2 berkurang 2.3 unit, S3 berkurang 0.5 unit dan S4 berkurang 1.5
unit supaya tetap memenuhi semua fungsi pembatas secara simultan.
Karena kolom Cb merupakan koefisien dari variabel dasar pada fungsi tujuan
maka untuk menghitung perubahan nilai fungsi tujuan (Zj) apabila nilai
variabel dasar Xj meningkat dari nol menjadi 1 adalah:
Z1 = 0(2)+ 0(2) + 0(1) + 0(2) = 0
Z2 = 0(2)+ 0(2.3)+ 0(0.5)+ 0(1.5) = 0
Z3 = 0(1)+ 0(0) + 0(0) + 0(0) = 0
Z4 = 0(0)+ 0(1) + 0(0) + 0(0) = 0
Z5 = 0(0)+ 0(0) + 0(1) + 0(0) = 0
Z6 = 0(0)+ 0(0) + 0(1) + 0(1) = 0
6
Karena nilai koefisien C1, C2, C3, C4, C5, C6 pada fungsi tujuan masingmasing
bernilai 3, 2, 0, 0, 0, 0 maka C1-Z1 = 3-0 = 3; C2-Z2 = 2-0 = 2 dan
seterusnya. Sampai dengan tahap ini maka tabel simplex menjadi:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Pada tabel tersebut juga diperoleh nilai Zj = 0 dengan cetak tebal pada
kolom terakhir yang merupakan perkalian antara kolom bi dengan koefisien
variabel basis-nya [0(800)+ 0(1000)+ 0(300)+ 0(650)] = 0
Dari baris evaluasi neto diketahui setiap produksi satu unit X1 (tas model
ransel) memberikan tambahan keuntungan Rp. 3 (dlm puluhan ribu) dan Rp. 2
(juga dlm puluhan ribu) untuk satu unit X2 pada nilai fungsi tujuan. Guna
memaksimumkan nilai fungsi tujuan maka variabel X1 dimasukan sebagai
variabel basic karena memiliki nilai positif terbesar dan menggantikan
salah satu variabel basic yang ada. Untuk menemukan variabel basic yang
harus diganti maka dicari variabel yang berasosiasi dengan constraint yang
paling membatasi nilai X1 (most restrictive). Dari contraint 1 diperoleh
nilai maksimum X1 adalah 400 karena untuk setiap tas model ransel
memerlukan 2 jam pengerjaan karena waktu yang tersedia adalah 800. Pada
constraint kedua X1 bernilai 500, constraint ketiga dan keempat
menghasilkan X1 masing-masing bernilai 300 dan 325. Dari analisis tersebut
terlihat bahwa constraint tiga paling membatasi sehingga nilai X1 tidak
boleh melebihi 300. Oleh karena itu variabel basic yang berasosiasi dengan
constraint ini yaitu variabel S3 menjadi variabel non basic.
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi bi/ai1
S1 0 2 2 1 0 0 0 800 (800/2=400)
S2 0 2 2.3 0 1 0 0 1000 (1000/2=500)
S3 0 1 0.5 0 0 1 0 300 (300/1=300)
S4 0 2 1.5 0 0 0 1 650 (650/2=325)
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Untuk memperbaiki solusi awal X1=0, X2=0, S1=800, S2=1000, S3=300, dan
S4=650 yang menghasilkan keutungan pada nilai fungsi tujuan = 0 maka X1
ditingkatkan nilainya menjadi 300 sehingga keuntungan menjadi 3(300) = 900.
Dengan memproduksi 300 unit tas model ransel maka semua waktu kerja yang
tersedia pada bagian penyelesaian habis digunakan dan menyebabkan nilai S3
menjadi nol, sehingga X1 sekarang menjadi variabel basic menggantikan
variabel S3 yang sekarang menjadi non basic.
Elemen matrik yang merupakan perpotongan antara kolom X1 dengan baris S3
disebut elemen pivot (tanda kotak), sedangkan baris dan kolom yang
berasosiasi dengan elemen pivot disebut baris pivot dan kolom pivot.
Penyusunan Tabel Simplex berikutnya
7
Untuk menemukan basic solution yang baru maka perlu dilakukan perubahan
pada tabel simplex yang terakhir. Masuknya variabel X1 sebagai variabel
basic harus tetap menjaga pola seperti pola variabel S3 yang digantikannya
yang sekarang menjadi non basic. Matrik kolom X1 tetap dipertahankan
seperti pola seperti matrik unity S3 yaitu:
0
0
1
0
Prosedur transformasi tabel simplex sehingga tetap merupakan sistem
persamaan constraint yang ekuivalen adalah dengan mengikuti langkah Operasi
Baris Elementer (elementary row operation).
Operasi Baris Elementer
1. Kalikan setiap baris (persamaan) dengan bilangan bukan nol
2. Gantikan setiap baris (persamaan)dengan hasil penambahan atau
pengurangan berganda dari baris lainnya
Operasi baris elementer ini tidak merubah solusi dari sistem persamaan
simultan tetapi operasi ini akan merubah koefisien dari variabel dan nilai
sisi kanan constraint. Tujuan dari oprasi baris ini adalah untuk
mentransformasikan sistem persamaan constraint menjadi bentuk yang mudah
untuk mengidentifikasi solusi basic yang baru.
Kolom X1 pada tabel simplex menjadi:
a11 = 0
a21 = 0
a31 = 1
a41 = 0
Secara kebetulan elemen matrik a31 sudah bernilai 1 seperti tampak pada
persamaan constraint baris 3 berikut:
1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4 = 300
sehingga tidak diperlukan operasi baris elementer. Baris tersebut sekarang
menjadi baris pivot yang baru pada tabel simplex yang diperbaiki.
Untuk membuat elemen a11 = 0 maka operasi baris elementer yang dilakukan
adalah dengan mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
Berikutnya adalah mengurangkan baris pertama dengan persamaan diatas
menjadi
(2X1 + 2X2 + 1S1)- (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 800 – 600
atau 0X1 + 1X2 + 1S1 – 0S2 -2S3 -0S4 = 200
Untuk membuat elemen a21 = 0 maka operasi yang harus dilakukan adalah
mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
8
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris kedua sehingga
(2X1 + 3.3X2 + 1S2) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 1000-600
atau 0X1 + 2.3X2 – 0S1 + 1S2 – 2S3 – 0S4 = 400
Untuk menghasilkan elemen a41 = 0 maka baris pivot juga kalikan 2 menjadi
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris keempat sehingga
(2X1 + 1.5X2 + 1S4) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 650-600
atau 0X1 + 0.5X2 – 0S1 - 1S2 – 2S3 + 1S4 = 50
Karena pola matrik kolom X1 sudah ditransformasikan menjadi unity maka
bagian tabel simplex yang baru adalah sebagai berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada tabel simplex awal maka
diperoleh tabel simplex iterasi pertama berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Proses selanjutnya adalah terus mengusahakan perbaikan nilai fungsi tujuan
dengan memasukan variabel non basic menjadi variabel basic yang baru dengan
mengikuti prosedur seperti pada iterasi pertama. Dari evaluasi baris neto
diketahui variabel X2 memiliki nilai positif terbesar (0.5) sehingga ia
menjadi variabel basic yang baru, kolom X2 sekarang adalah sebagao kolom
pivot. Untuk menemukan baris pivot maka dicari nilai terkecil dari X2
dengan menghitung nilai Bi/ai2 (most restrictive X2). Hasilnya disajian
pada tabel berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi bi/ai2
9
S1 0 0 1 1 0 -2 0 200 (200/1=200)
S2 0 0 2.3 0 1 -2 0 400 (400/2.3=174)
X1 3 1 0.5 0 0 1 0 300 (300/0.5=600)
S4 0 0 0.5 0 0 -2 1 50 (50/0.5=100)
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Dari tabel tersebut diketahui constraint 4 paling restriktif sehingga
variabel S4 menjadi non basic karena bernilai nol karena semua jam kerja
yang ada pada bagaian ini digunakan untuk menghasilkan 100 unit X2 (tas
model klasik).
Operasi baris elementer harus dilakukan untuk membuat elemen metrik kolom
X2 menjadi unity dengan mempertahankan pola seperti S4, yaitu:
a12 = 0
a22 = 0
a32 = 0
a42 = 1
Untuk menjadikan elemen matrik a42 = 1 maka baris pivot harus dikalikan 2
menjadi 2(0X1 + 0.5X2 + 0S1 + 0S2 – 2S3 + 1S4) = 2(50)
atau 0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4 = 100
Persamaan tersebut sekarang menjadi baris pivot yang baru.
Untuk mendapatkan elemen matrik a12 = 0 maka operasi baris elementer
dilakukan dengan hanya mengurangkan baris pivot dari persamaan baris
pertama (variabel basic S1) karena koefisien X2 yang ada pada baris pertama
dengan yang ada pada baris pivot, yaitu sama-sama 1. Baris pertama yang
baru dengan demikian menjadi:
(0X1+1X2+1S1+0S2–2S3+0S4)-(0X1+1X2+0S1+0S2–4S3+2S4) = 200-100
atau 0X1 – 0X2 + 1S1 + 0S2 + 2S3 – 2S4 = 100
Untuk mendapatkan elemen matrik a22 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 2.3 dan mengurangkan
hasilnya dari persamaan baris 2 (variabel basic S2), yaitu:
2.3(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 2.3(100)
atau 0X1 + 2.3X2 + 0S1 + 0S2 – 9.2S3 + 4.6S4 = 230
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(0X1+2.3X2+0S1+1S2-2S3+0S4)-(0X1+2.3X2+0S1+0S2–9.2S3+4.6S4) = 400-230
atau 0X1 + 0X2 + 0S1 + 1S2 + 7.2S3 -4.6S4 = 170
Untuk mendapatkan elemen matrik a32 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 0.5 dan mengurangkan
hasilnya dari persamaan baris 3 (variabel basic X1), yaitu:
0.5(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 0.5(100)
atau 0X1 + 0.5X2 + 0S1 + 0S2 –2S3 + 1S4 = 50
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(1X1+0.5X2+0S1+0S2+1S3+0S4)-(0X1+0.5X2+0S1+0S2–2S3+1S4) = 300-50
atau 1X1 + 0X2 + 0S1 + 0S2 + 3S3 -1S4 = 250
10
Setelah mendapatkan semua persamaan constraint maka bagian tabel simplex
yang baru adalah
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada iterasi pertama maka diperoleh
tabel simplex iterasi kedua berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Zj 3 2 0 0 1 1 950
Cj-Zj 0 0 0 0 -1 -1
Interpretasi Solusi Optimal
Dari baris evaluasi neto tidak lagi ditemukan nilai positif yang berarti
solusi yang diperoleh sudah maksimum, yaitu X1 = 250, X2 = 100 dan nilai
fungsi tujuan Zj = 950 ( dalam puluhan ribu rupiah)
Dari tabel tersebut diketahui S1 = 100 dan S2 = 170 yang berarti waktu
kerja pada bagian pemotongan masih tersisa (slack) 100 jam sedangkan sisa
waktu pada bagian penjahitan adalah 170 jam. Pada bagian lainnya
(penyelesaian, pemeriksaan & pengepakan) seluruh waktu kerja sudah habis
digunakan.
Merujuk kembali pada gambar terdahulu diketahui bahwa solusi optimal
bergerak mulai dari titik ekstem 1 dengan solusi awal X1=0, X2=0, S1=800,
S2=1000, S3=300, S4=650 dan menghasilkan nilai fungsi tujuan nol. Pada
iterasi pertama variabel X1 memasuki basis dan mengakibatkan variabel S3
menjadi non basic variabel. Solusi basic kedua berada pada titik ekstem 2
yaitu X1=300, X2=0, S1=200, S2=400, S3=0, dan S4=50 serta menghasilkan
nilai 900 pada fungsi tujuan. Pada iterasi selanjutnya X2 memasuki basis
mendorong S4 untuk keluar. Hal ini menyebabkan solusi bergerak kearah sumbu
X2 menuju titik ekstem 3. Pada titik ini solusi yang didapat sudah optimum
yaitu X1=250, X2=100, S1=100, S2=170, S3=0 dan S4=0 sedangkan nilai fungsi
tujuan maksimum yaitu 950.
Ringkasan Prosedur Metode Simplex
1. Formulasikan persoalan kedalam model linear
2. Tambahkan variabel Slack pada masing-masing constraint (pembatas)
untuk memperoleh bentuk standar. Model ini digunakan untuk
11
identifikasi solusi feasible awal dari pembatas bertanda lebih kecil
atau sama dengan.
3. Buat tabel simplex awal (initial simplex tableau)
4. Pilih variabel non basic yang memiliki nilai positif terbesar pada
baris evaluasi neto menjadi variabel basic. Variabel ini menjadi
kolom pivot, yaitu kolom yang berasosiasi dengan variabel basic yang
masuk.
5. Pilih baris pivot yang memiliki ratio bi/aij terkecil dimana aij ≥ 0,
dimana j adalah kolom pivot. Hal ini sekaligus menunjukkan variabel
yang meninggalkan basis menjadi non basis.
6. Lakukan operasi baris elementer jika diperlukan untuk
mentransformasikan kolom dari variabel yang memasuki basis menjadi
kolom unitary yang bernilai 1 pada baris pivotnya.
a. Kalikan atau bagi setiap elemen baris pivot dengan pivot elemen
b. Hasilkan nilai 0 pada elemen kolom lainnya dengan cara
mengurangkan baris pivot dari baris-baris constraint lainnya
7. Lakukan pengujian tingkat optimaliti. Jika Cj-Zj ≤ 0 untuk semua
kolom maka solusi optimal sudah diperoleh, jika tidak maka ulangi
prosedur 4 kembali.