OPERATION RESEARCH
PEMPROGRAMAN LINIER : ALGORITMA SIMPLEKS
DOSEN PENGAMPU :
Rika Dwi Harsasi, S.E., M.S.M.
NAMA KELOMPOK :
Dani Purniawan (132010200198)
Ibadurrahman Mukholadun (132010200193)
Agung Setyo Pribadi (132010200197)
Eka Kurnia (132010200190)
FAKULTAS EKONOMI PROGRAM STUDI MANAJEMEN A - 2 ( PAGI ) SEMESTER – IV
UNIVERSITAS MUHAMMADIYAH SIDOARJO
KATA PENGANTAR
Kami panjatkan puji syukur kehadirat Allah SWT, atas limpahan rahmat hidayah dan inayahnya sehingga makalah ini dapat terbentuk sedemikian rupa. Tak lupa kami hanturkan sholawat serta salam kepada junjungan kita Nabi Besar Muhammad SAW yang telah membimbing kita menuju jalan yang benar.
Makalah ini kami buat dengan sengaja agar acara yang kami rencanakan dapat berjalan dengan lancar tanpa suatu kendala apapun. Harapan kami, semoga makalah ini dapat diterima dan bermanfaat untuk semua masyarakat.
Demikianlah makalah ini kami buat, kurang lebihnya kami mohon maaf yang sebesar-besarnya. Kami ucapkan terimakasih atas perhatiannya.
Sidoarjo,07 April 2015
Penyusun
DAFTAR ISI
KATA PENGANTAR 2
Pemilihan Cj-Zjyang kontroversial 4
Pemilihan Cj-Zj terkecil kasus Bawika 5
Interasi I: Pengujian di titik sudut A(10,0) 5
Interasi II: Pengujian di titik Sudut B(10, 1,67) 6
Iterasi III: pengujian di titik sudut C(6, 5) 10
Algoritma simpleks langkah mundur 12
Iterasi I pengujian mundur 16
Iterasi II pengujian mundur 17
Iterasi III PengujianMundur 18
Algoritma Simpleks II :KasusSukraRasmi 20
KoefisiensiVariabelArtifisial “αi” padaFungsiTujuan 21
IterasiI :AlgoritmaSimpleksSukraRasmi 22
IterasiII :AlgoritmaSimpleksSukraRasmi 25
IterasiIII :AlgoritmaSimpleksSukraRasmi 28
IterasiIV :AlgoritmaSimpleksSukraRasmi. 31
4.7.3 algoritma simpleks III : kasus Gupita 36
Iterasi 0 : kasus Gupita 37
Iterasi I : kasus Gupita 39
Iterasi II : kasus Gupita 41
Slack Variable Pada Variable Basis Adalah Sisa Kapasitas 45
DAFTAR PUSTAKA 46
Pemilihan Cj-Zjyang kontroversial
Pemilihan kolom kunci pada penyelesaian kasus Bawika telah berpedoman pada nilai Cj-Zj terbesar. Pedoman ini lebih didasarkan pada konsep opportunity cost sehingga pemilihan Cj-Zj terbesar belum tentu mengasilkan pertambahan nilai Z terbesar. Pertambahan nilai Z pada setiap interasi bukan hanya ditentukan oleh nilai Cj-Zj kolom kunci tetapi juga dipengaruhi oleh rasio baris kunci. Di samping itu pedoman persebut tidak menjamin efisiensi pengujian.
Peraga 4.42 menanyakan geometri sebuah kasus pemograman linear dimana sumbagan laba per unit X2 = Rp300,- dan X1 = Rp200,- seperti yang ditunjukan oleh garis laba Z = 0. Titik sudut B(6, 5) menjadi titik sudut ekstrem yang membuat nilai Z maksimum pada Z = 27. Pengujian titik sudut dengan algoritma simpleks bisa dilakukan melaliu dua arah
Pertama, arah pengujian melalui sumbu X2 dimana,
1. Iterasi 0 : pengujian titik sudut O(0,0)
2. Iterasi I : pengujian titik sudut D(0,6)
3. Iterasi II : pengujian titik sudut C(4,6)
4. Iterasi III : pengujian titik sudut B(6,5)
Cara ini dilakukan pada tabel simpleks dengan pemilihan X2 sebagai kandidat variabel basis yang pertama dan tercermin di dalam pemilihan kolom kunci yang memiliki Cj-Zj = 300 sebagai Cj-Zj tebesar. Dengan demikian, pada cara pertama ini kita akan menemukan nilai Z maksimum sebesar 27 B(6,5) setelah empat interasi.
Kedua, arah pengujian menelusuri sumbu X1 di mana,
1. Iterasi 0 : pengujian titik sudut O(0,0)
2. Iterasi 0 : pengujian titik sudut A(6,0)
3. Iterasi 0 : pengujian titik sudut B(6,5)
Cara ini pada tabel simpleks dilakukan dengan pemilihan X1 sebagai kandidat variabel basik yang pertama, dan tercermin di dalam pemilihan kolom kunci yang memiliki Cj-Zj = 200 sebagai Cj-Zj terkecil. Dengan cara ini kita akan menemukan nilai Z maksimum sebesar 27 di B(6,5) setelah tiga interasi.
Dengan demikian, kita telah membuktikan bahwa pemilihan kolom kunci yang mengacu pada Cj-Zj belum tentu lebih efisien dibandingkan pemilihan kolom kunci yang mengacu pada Cj-Zj terkecil.
Pemilihan Cj-Zj terkecil kasus Bawika
Kini, marilah kita melihat proses penyelesaian simpleks yang menggunakan pedoman Cj-Zj terkecil untuk memilih kolom kunci.
Interasi I: Pengujian di titik sudut A(10,0)
Pemilihan kolom satu yang memiliki Cj-Zj = 2 sebagai kolom kunci akan membawa kita kepada pengukian di titik sudut A(10,0).
Pada saat kita bergerak ke arah titik sudut A, nilai X1 menjadi semakin besar dan sebagai akibatnya nilai S3= 0, maka posisinya kini berubah menjadi variabel nonbasis dan digantikan oleh X1. Proses ini tercermin pada pemilihan kolom kunci dan basis kunci yang ditanyakan pada peraga 4.44. Selanjutnya peraga 4.45 dan peraga 4.46 menyakan seluruh variabel basis pada tabel simpleks interasi I dan tabel simpleks lengkap interasi I.
Interasi II: Pengujian di titik Sudut B(10, 1,67)
Tujuan pengujian selanjutnya adalah titik sudut B(10, 1,67).Di titik sudut ini X1 tetap bernilai 10 dan X2 menjadi 1,67, lihat peraha 4.47.
Pada peraga 4.47, kita melihat bahwa perpindahan pengujian dari A(10,0) ke B(10, 1,67) akan membuat nilai S1 semakin lama menjadi semakin kecil, seiring dengan kenaikan nilai X2, hingga akhirnya sama dengan nol pada saat X2 = 1,67. Jadi, X2 akan berubah menjadi variabel basis dan S1 sebagai akibatnya berubah menjadi variabel nonbasis. Perhatikan elemen kunci a12 = 6. Karena variabel basis harus berkoefisien +1, maka seluruh elemen pada baris satu harus di bagi dengan enam.
Dari uraian sebelumnya, kita telah mengetahui bahwa nilai Cj-Zj mencerminkan kontribusi variabel ke-j terhadap nilai Z. Nilai Cj-Zj< 0 jelas akan menurunkan nilai Z dan sebaliknya nilai Cj-Zj> 0 pasti akan menaikan nilai Z. Pada tabel simpleks interasi II yang di tanyakan oleh peraga 4.49 kita masih menjumpai Cj-Zj> 0 yaitu C5-Z5 = 5/2. Dengan demikian, kita bisa menyimpulkan bahwa nilai Z masih bisa dinaikan dengan memasukan S3 sebagai variabel basis. Oleh karena itu, pengujian harus di lanjutkan.
Iterasi III: pengujian di titik sudut C(6, 5)
Pengujian selanjutnya menurut peraga 4.50 adalah pengujian di titik sudut C(6. 5). Ketika kita meninggalkan titik sudut B(10, 1,67) menuju titik sudut C(6, 5), nilai S3 berubah menjadi positif. Semakin jauh kita kita meninggalkan titik sudut B(10, 1,67), semakin besar nilai S3. Di sisi yang lain, nilai S2 semakin kecil hingga akhirnya menjadi nol dan menjadi variabel nonbasis.
Proses pengujian titik sudut C(6, 5) melalui analisis geometri peraga 4.50 berhubungan dengan tabel simpleks peraga 4.51. Selain itu, di sini kita menjumpai elemen kunci yang tidak bernilai +1, yaitu a25 = 2/3. Oleh karena itu, seluruh elemen pada basis dua harus di bagi dengan 2/3 agar pada tabel simpleks iterasi berikutnya elemen a25 = +1.
Tabel simplek peraga 4.52 adalah tabel simpleks optimal yang ditandai oleh Cj-Zj = 0. Karena seluruh nilai Cj-Zj tidak ada yang posotif, maka tidak ada lagi peluang untuk menaikan nilai Z.
Pengujian beda arah dalam kasus Bawika ini telah membuktikan bagaimana algoritma simpleks tidak terikat pada ketentuan mengenai pemilihan kolom kunci yang harus di pillih. Selama masih ada Cj-Zj> 0 maka nilai fungsi tujuan masih bisa dinaikkan. Demikian pula bila masih dijumpai Cj-Zj< 0 maka nilai fungsi tujuan masih bisa dimunimumkan.
Algoritma simpleks langkah mundur
Pertanyaan kritis yang akan segera muncul adalah: “bagaimana dengan pemiliha Cj-Zj< 0?”. Apabila kita menggunakan analogi penyelesaian algoritma simpleks kasus Bawika ini, maka pemilihan Cj-Zj< 0 tentunya juga akan menentukan nilai Z pada interasi berikutnya. Bila Cj-Zj> 0 akan menaikan nilai Z maka pemilihan Cj-Zj< 0 tentu sebaliknya menurunkan nilai Z.
Tabel optimal simpleks kasus Bawika dinyatakan kembali pada peraga 4.53. Dari peraga tersebut kita menjumpai C3-Z3 = -1/4 dan C4-Z4 = - 3/4. Dengan demikian kita memiliki dua pilihan kandidat kolom kunci, yaitu kolom ke tiga dan kolom ke empat untuk menurunkan nilai Z.
Pemilihan kolom ke tiga sebagai kolom kunci akan membuat basis ke-1sebagai baris kunci dengan rasio terkecil +4, lihat peraga 4.54. Pilihan ini akan membuat S1 menjadi variabel basis dan S4 menjadi variabel nonbasis. Di samping itu, pilihan ini akan membuat nilai Z turun – 1/4 (4) = -1 sehingga nilai Z pada iterasi berikutnya akan menjadi 27 – 1 = 26.
Melalui geometri peraga 4.55, kita melihat bahwa perubahan S1 menjadi variabel basis dan S4 menjadi Variabel nonbasis terjadi pada saat pengujian perpindahan dari titik sudut C(6, 5) ke titik sudut D(4, 6). Dengan demikian kita mengetahui bahwa pemilihan kolom ketiga dengan C3-Z3 = - 1/4 sebagai kolom kunci akan membuat langkah simpleks mundur satu interasi ke pengujian titik sudut sebelumnya yaitu titik sudut D(4, 6) di mana nilai Z akan turun menjadi 26.
Di sisi lain kita mungkin memilih kolom keempat dengan C4-Z4 = - 3/4 sebagai kolom kinci. Pilihan ini akan membuat baris ketiga sebagai baris kunci karena memiliki rasio terkecil yaitu 8/3, lihat peraga 4.56.
Pilihan kolom keempat sebagai baris kunci akan membuat S2 menjadi variabel nonbasis. Ini berarti pengujian mundur ke titik sudut B(10, 1,67) seperti ditanyakan oleh geometri peraga 4.57.
Dengan demikian, kini semakin jelas bahwa dua macam pilihan Cj-Zj< 0 ternyata membawa kita ke arah pengujian mundur. Mana yang dipilih akan membawa kita kepada titik sudut O(0,0).
Iterasi I pengujian mundur
Pemilhan kolom ketiga sebagai kolom kinci membawa kita ke iterasi I yaitu pengujian di titik sudut D(4,6). Tabel simpleks lengkap iterasi ini ditanyakan pada peraga 4.58.
Bila kita ingin melangkah mundur lagi maka kita mempunyai pilihan kolom keempat dengan C4-Z4 = -2 sebagai kolom kunci. Pilihan ini akan membuat baris kedua menjadi baris kunci.
Iterasi II pengujian mundur
Pilihan kolom keempat sebagai kolom kunci, membawa kita ke pengujian titik sudut E(0,6) dimana Z akan turun dengan -2(4) = -8 sehingga nilai Z di titik sudut itu akan menjadi 26 – 8 = 16, lihat peraga 4.59 dan geometri peraga 4.60.
Iterasi III PengujianMundur
IterasimundursudahsampaidititiksudutE(0,6) , sepertipengujianmundurmasih bias dilanjutkankarena C6-Z6= -3 .
Kolomenamsebagaikolomkunci, bariskeempatsebagaibariskunci.
Cj 2 3 0 0 0 0 bi
Ci VB X1 X2 S1 S2 S3 S4
0 S1 5 0 1 0 0 -6 24
0 S2 1 0 0 1 0 -2 4
0 S3 1 0 0 0 1 0 10
0 X2 0 1 0 0 0 1 6
ZJ 0 3 0 0 0 3 18
Cj-Zj 2 0 0 0 0 -3
KolomkuncidansebagaikonsekuensinyabariskeempatsebagaibariskunciakanmembawakepengujiantitiksudutO(0,0) .
Pilihaniniakanmenyebabkannilai Z turundengan -3(6) = - 18 sehingganilaifungsitujuan Z padaiterasiberikutnyaakanmenjadi 18-18 = 0.
Interasi III pengujianmunduir yang ditayangkanpadaperaga 4.63 adalah tables simplekskasusBawikadimanasudahtidakmenjumpailagiCj-Zj<0 .danberartisudahtidakmungkinlagimelakukanpengujianlangkahhmundur.
Pengujianmunduriterasi III
TabelawalsimplekskasusBawika.
Cj 2 3 0 0 0 0 bi
Ci VB X1 X2 S1 S2 S3 S4
0 S1 5 6 1 0 0 0 60
0 S2 1 2 0 1 0 0 16
0 S3 1 0 0 0 1 0 10
0 S4 0 1 0 0 0 1 6
ZJ 0 3 0 0 0 0 0
Cj-Zj 2 0 0 0 0 0
Maksimumkan 2X1 + 3X3
Terhadapfunsi-fungsikendala,
1. Dept. I 5X1 + 6X2 ≤ 60
2. Dept. II X1 + 2X2 ≤ 16
3. Permintaan X1 X1≤ 10
4. Permintaan X2 X2≤ 6
X1 ,X2≤ 0
Dengan demikian, model matematissebuah table optimal simpleksmelaluipengujiantitikmundur.PemilihankolomkejdimanaCj-Zj< 0 akanmembuatpengujiantitiksudutkembalikearahpengujianiterasisebelumnya.
PemilihanCj-Zj< 0 akanmenaikkannilaifungsitujuandansebaliknyapemilihanCj-Zj< 0 akanmenurunkannilaifungsitujuantanpaharusterikatpadatujuan yang hendakdicapai.
Algoritma Simpleks II :KasusSukraRasmi
KasusSukraRasmidengananalisisgeometritelahdilakukanpada model matematisSukraRasmiadalah :
1. FungsiTujuan : Maks 40X1 + 30X2 [4.26]
Terhadapkendala-kendala :
2. 2X1+ X2 ≤ 20 [4.27]
3. 2X1+ 3X2 ≤ 32 [4.28]
4. 2X1- X2 ≤ 0 [4.29]
5. X2 ≥ 2 [4.30]
Model matematisdiolahdenganalgoritmasimpleksmenambahslack variablepadakemdalabaris ke-2 dan ke-3, surpus variabledanartificial variablepadakendalabaris ke-4 dan ke-5 sehinggabangunmatematikkendala-kendalamenjadi :
2. 2X1+X2 +S1 = 20 [4.31]
3. 2X1+ 3X2 + S2 = 30 [4.32]
4. 2X1- X2 - S3 + α3 = 0 [4.33]
5. X2 - S3 + α4 = 2 [4.34]
KoefisiensiVariabelArtifisial “αi” padaFungsiTujuan
Variabelartifisialadalahsuatususunankendalaakanmempengaruhifungsitujuan,tidaksepertisurpus variabledanslack variable yang tidakberpengaruhterhadapfungsitujuankarenamemilikikoefisiennol, artificial variable parameter M yaitubilangan yang sangatbesar. Kehadiranartificial variableα3danα4 menghendakipenggunaanbialngan M sebagaikoefisienfungsitujuanuntukmenandaieksistensinya, [4.14] ; sehinggafungsitujuanSukraRasmi [4.26] menjadiMaks 40X1 + 30X2 - M α3 -- M α4 [4.35]
Koefisien “α” fungi tujuankasuspemrograman linier mungkinmempunyaikoefisienpositif (+M) ataumungkinmempunyaikoefisien negative (-M).
TabelawalsimplekskasusSukraRasmi, pengujian di 0(0, 0).
Cj 2 3 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬-M α3 2 -1 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj ¬-2M 0 0 0 +M +M +M ¬-M ¬-2M
Cj-Zj 40+2M 30 0 0 ¬-M ¬-M ¬-M 0
Padakolomvariabel basis kitatidakmenjumpaiS3danS4 sebagaivariabel basis.Table simpleksmengandungsebuahbentukmatriksidentitaspadasetiap table simpleksmenandaiidentitasvariabel basis.Kehadiranartificial variableα3danα4 yang memilikikoefisien +1 diperlukanuntukmembentukmatriksidentitasberhubungsurpus variable S3danS4 yang memilikikoefisien -1.
IterasiI :AlgoritmaSimpleksSukraRasmi
KetikaseluhvariabelkeputusanX1danX2 adalahvariabelnonbasis; kedua, padaiterasipertama, ketikavariabelkeputusanX1 ssebagaivariabelnonbasis; kedua, padaiterasiX2 tetapsebagaivariabelnonbasis. Pemilihankolomsatusebagaikolomkuncitidakakanmembuatnilaifungsitujuan Z bertambahkarenapengujianmasihdilakukanpadatitiksudut yang sama.
Iterasi I, pengujiantitiksudut0(0, 0)
Pemilihankolomkesatusebagaikolomkuncimembuat X1 menjadikandidatvariabel basis padaiterasipertama.Konsekuenlogis, barisketigamenjadibariskuncisehinggaartificial variableα3 akanmenjadivariabelnonbasis.
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬M α3 2 -1 0 0 -1 0 0 0 0
¬M α4 0 1 0 0 0 -1 1 1 1
Zj ¬2M 0 0 0 +M +M +M ¬-M ¬-2M
Cj-Zj 40+2M 30 0 0 ¬-M ¬-M ¬-M 0
Variabel basis Iterasi I.
Cj 40 30 0 0 0 0 ¬M ¬M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 -0,5 1 0 -0,5 0 1 0
0 S2 0 0 1
40 α3 1 0 0 0
¬M α4 0 0 0 1
Zj
Cj-Zj
Variabel basis iterasi I.
Cj 2 3 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 2 1 0 0 0 -1 0 20
0 S2 0 4 0 1 0 0 -1 0 32
¬-40 α3 1 -0,5 0 0 -0,5 0 0,5 0 0
¬-M α4 0 1 0 0 0 -1 1 1 2
Zj
Cj-Zj
Nilairuaskanankendala yang beradadibawahkolom “bi” .karenaiterasi I masihmwngujititiksudut
O(0, 0) sepertiiterasi 0 makalogiskalautidakadaperubahanpadabi untukseluruhi. atau, tidakadapenggunaankapasitaskendalameskipunX1 telahmenjadivariabel basis. Strukturkendaladan parameter kendalaketigatidakmembuat X1 bernilaipositif.
IterasiII :AlgoritmaSimpleksSukraRasmi
Memilihkolomkeduasebagaikolomkunciuntukmelihatperilakubilangan M. bilakolomkeduaterpilihsebagaikolomkuncimakabariskeempatsebagaikonsekuensinyaterpilihsebagaibariskunci.PemilihankolomkeduasebagaikolomkuncidanbariskeempatbariskunciakanmenjadivariabelkeputusanX2sebagaivariabel basis danmemaksaartificial variableα4 membuatkeputusanvariabelnonbasis.
Table simplekslengkapiterasi I, pengujian di titiksudut0(0, 0).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬40 X1 2 -1 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj 40 ¬-20-M 0 0 -20 +M -M ¬-M ¬-2M
Cj-Zj 50+M 0 0 ¬20 ¬-M ¬-20-M 0
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 2 1 0 0 0 0 0 20
0 S2 0 4 0 1 0 0 0 0 32
¬40 X1 1 -0,5 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj 40 ¬-20-M 0 0 -20 +M 20 ¬-M ¬-2M
Cj-Zj 50+M 0 0 ¬20 ¬-M ¬-20-M 0
+ (100 + 200M) = 100algoritmasimpleksuntukmelengkapi table simpleksiterasikeduatidakberbeda.
Pengujian di titiksudutA(1, 2), ditunjukkanolehnilaivariabel basis X1 = 1danX2= 2.VribelkeputusanX1memangsudahmunculsebagaivariabel basis, kemunculannyatidakberpindahanpengujiandarititiksudutO(0, 0) karenaX1= 0danX2= 0 tetapsebagaivariabelnonbasis.
TabelSimplekslengkapiterasi II, pengujiantitiksudutA(1, 2).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 0 0 2 -1 0 16
0 S2 0 0 0 1 0 4 -1 0 24
¬40 X1 1 0 0 0 -0,5 -0,5 0,5 0 1
¬30 X2 0 1 0 0 0 0 0 1 2
Zj 40 30 0 0 -20 -50 20 -M 100
Cj-Zj 0 0 0 0 20 50 -20-M 0
Pengujian di titiksudutA(1, 2).
IterasiIII :AlgoritmaSimpleksSukraRasmi
Berdasarkanindikasi C5 – Z5 = 20 dan C6 – Z6 = 50 ,pemilihankolombaris ke-5 dan ke-6 sebagaikolomkunciakammembuatpengujiantitiksudutmenjadilebihpanjangdiamanpadaakhirnyapengujianakankembalipadakondisibilakolomm ke-6 dipilihsebagaikolomkunci.
Pemilihankolomkuncidanbariskunci
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 0 1 2 -1 0 16
0 S2 0 0 0 1 1 4 -1 0 24
¬40 X1 1 0 0 0 -1/2 -0,5 1/2 0 1
¬30 X2 0 1 0 0 -1 0 0 1 2
Zj 40 30 0 0 -20 -50 20 -M 100
Cj-Zj 0 0 0 0 20 50 -20-M 0
Pemilihankolom ke-6 sebagaikolomkuncidanbaris ke-2 sebagaibariskunciakanmembawakeiterasi III yaitupengujian di titiksudutD(4, 8).
Pengujian di titiksudutD(4, 8).
Tabelsimpleksiterasi III yaitupengujian di titiksudutD(4, 8) . Tabelinibelum optimal karenamasihmengandung C5 – Z5 = 7,5sehinggamempunyaikesempatanuntukmenaikkannilai Z.
IterasiIV :AlgoritmaSimpleksSukraRasmi.
Pemilihankolom ke-5 sebagaikolomkunciakanmembuatbarispertamaterpilihmenjadibariskuncikarenamemilikirasioterkecilyaitu 8. Karenaakanmenambahnilai Z.
TabelSimplekslengkapiterasi III, Pengujian di titiksudutD(4, 8).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 -0,5 -0,5 0 -0,5 0 4
0 S2 0 0 0 0,25 0,25 1 -0,25 0 6
¬40 X1 1 0 0 0,13 0,38 0 0,38 0 4
¬30 X2 0 1 0 0,25 -0,25 0 -0,25 1 8
Zj 40 30 0 12,5 -7,5 0 7,5 0 400
Cj-Zj 0 0 0 -12,5 7,5 0 -7,5 - M -M
Dengan (7,5 x 8) = 60 sehingganilaifungsitujuan Z padaiterasi IV menjadi 400 + 60 = 460 , secarageometrispemilihanakanmembawakepengujiantitiksudutC(7, 6).
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 -0,5 -0,5 0 -0,5 0 4
0 S2 0 0 0 0,25 0,25 1 -0,25 1 6
¬40 X1 1 0 0 0,13 0,38 0 0,38 0 4
¬30 X2 0 1 0 0,25 -0,25 0 -0,25 0 8
Zj 40 30 0 12,5 -7,5 0 7,5 0 400
Cj-Zj 0 0 0 -12,5 7,5 0 -7,5 - M -M
Pengujian di titiksudutC(7,6).
TitiksudutC(7,6) ,nilaifungsitujuanmenjadi Z = 40(7) + 30(6) = 460. Jadisepertinilai Z table simpleksiterasiakanmenjadi 460.
Dari titik sudut C (7,6) nilai fungsi tujuan ini menjadi Z=40(7) + 30(6) = 460 jadi literasi tabel siplek menjadi 460. Peraga 4.78 menayangkan tabel simpleks iterasi IV pengujian titik sudut C(7,6). Optimalisasi tabel ini ditandai oleh Cj – Zj ≤ 0 untuk selujuh J dengan ini tidak bisa lagi menaikkan nilia fungsi tujuan Z.
Fungsi tujuan kasusu sukra rasmi dari [4.26] maks 40X1 + 30X2. Karena X1 = 7 dan X2 = 6 maka nilai fungsi tujuan maksimum 40X1 + 30X2 karena X1 = 7 dan X2 = 6 maka nilai tujuan maksimum 40(7) + 30(6) = 460.
Surplus variabel S3 dan S4 muncul sebagai variabel basis menandai kapasitas yang terlampaui. Dari [4.33].
Karena surplus variabel S3 dan S4 muncul sebagai variabel basis jelas shadow price atau dual price dan kendala ke tiga dan empat bernilai nol.
Kedudukan S1 dan S2 sebagai variabel bahwa kendala pertama dan kedua adalah kendala aktif, yaitu kendala berbentuk titik sudut ekstrem sehingga slack variable. Pada kedua kendala ini bernilai nol. [4.31].
Sebagai kendala aktif maka shadow price atau dual price kedua kendala itu menjadi positif yaitu 15 dan 5. Lihat kasus sukra rasmi peraga 4.79.
4.7.3 algoritma simpleks III : kasus Gupita
Model matematis gupita adalah :
Agar model ini dapat diolah menggunakan algoritma simpleks harus ditambahkan slack variable, surplus variable, dan artificial variable agar membentuk matriks identiti.
Kasus gupita memiliki 5 kendala kendala pertama ketiga adalah kendala syarat dan tiga sisanya adalah kendala pembatas. Peraga 4.81 ke tabel awal simpleks dan peraga 4.82 tabel awal simpleks.
Iterasi 0 : kasus Gupita
Pada tabel awal menjumpai Cj –Zj < 0 membuat fungsi tujuan Z berkurang, hal ini juga menjadi kolom kunci. Tabel 4.82 menguji titik sudut A(0,0 ) peraga (4.84) membuat X1 menjadi variabel basis yang menggantika variabele basi S4 yang menjadikan variable non basis pada iterasi berikutnya. Langkah ini menjadika fungsi tujuan Z menjadi lebih kecil. Maka pengujian kembali ke titik O (0.0).
Dari sisi yang lain pemiliha kolom kedua senbagi kolom kunci akan membuat X2 sebagi variable basis ketiga dan memaksa artifial variable a3 menjadi variable non basis pada iterasi berikutnya peraga [4.85]. karena rasio basis ketiga adalah 3 maka 3(30 – 5M) = 90 – 15M menjadi 22M + (90 – 15M) = 7M + 90.
Iterasi I : kasus Gupita
Pilihan kolom kedua sebagai kolom kunci akan membawa kita ke pengujian titik sudut D(0,3) seperti tertayang pada peraga 4.86. selanjutnya peraga 4.87 menayangkan tabel simpleks iterasi I kasus Gupita yaitu pengujian titik sudut D(0,3).
Iterasi II : kasus Gupita
Kita memiliki dua pilihan untuk melanjutkan ke titik berikutnya, ditunjukkan oleh C1 – Z1 = 12,5 – 1,75M dan C5 – Z5 = 7,5 – 0,25M. Dalam kasus Gupita sangat bagus karena memiliki kolom kunci dimana kita bisa memilih alternatif pilihan selain kolom yang menjadi pilihan. Disini kita bisa memilih kolom kesatu atau kolom yang mengandung variable keputusan, selain tujuannya menemukan X1 dan X2 yang dapat meminimalkan fungsi tujuan Z, X1 menjadi variable basis dengan nilai 7 : 1,75 = 4. Pilihan ini secara otomatis akan membuat baris kesatu sebagai basis kunci (peraga 4.88). dimana afficial variable a1 dipaksa sebagai variable non basis.
Pilihan satu sebagai titik kunci yaitu O (4,2). Seperti peraga 4.89, hasil pengujian ditunjukkan peraga 4,90 yang memberikan nilai Z minimumnya 140.
Ketika kolom kesatu dipakai sebagai kolom kunci bahwa nilai Z iterasi selanjutnya adalah : 4(12,5 – 1,75M) = (50 – 7M) sehingga menjadi (7M + 90) + (50 – 7M) = 140 yang ditunjukkan tabel simpleks literasi II, ditabel ini didapat bahwa, Cj – Zj ≥ 0 untuk seluruh j didapat bahwa pegara 4.90 adalah tabel simpleks optimal khusus Gupita. Ringkasan optimal ini ditunjukkan peraga 4.91.
Surplus variable S1 dan S3 yang terletak pada baris kedua dan keempat peraga 4.91 bernilai nol. Nilai ini menunjukkan bahwa memiliki kendala aktif. Pada peraga 4.89 dilihat bahwa titik sudut ekstrem O(4,2). Dibentuk oleh perpotongan dua garis kendala itu. Shadow price dan dual price menunjukkan perubahan nilai fungsi tujuan bila nilai ruas kanan kendala berubah satu unit. Karena kendala shadow price dan dual price adalah kendala aktif maka dihasilkan C3 –Z3 = 7,143 dan C5 – Z5 = 5,714 pada tabel simpleks optimal pada peraga 4.90.
Dan peranan artificial variable itu bernilai nol sehingga,
Slack Variable Pada Variable Basis Adalah Sisa Kapasitas
Kemunculan slack variable, sebuah kendala pada variable basis menunjukkan bahwa kendala ini adalah : kendalah tidak aktif, artinya tidak berperan di dalam pembentukkan titik sudut ekstrem. Pada peraga 4.89 diditu tidak semua kendala digunakan, untuk mengetahui kendala sisa ada di kolom bi baris kedua, empat, dan kelima pada tabel simpleks 4.90.
Melalui penyelesaian kasus Gupita dapat diketahui bahwa penyelesaian kasus pemprograman linier dengan metoda simpleks menghasilkan informasi yang lebih banyak, dibanding dengan metoda geometri.
DAFTAR PUSTAKA
1. Siswanto. 2007. “Operation Research”. Jilid 1. Erlangga. Jakarta
PEMPROGRAMAN LINIER : ALGORITMA SIMPLEKS
DOSEN PENGAMPU :
Rika Dwi Harsasi, S.E., M.S.M.
NAMA KELOMPOK :
Dani Purniawan (132010200198)
Ibadurrahman Mukholadun (132010200193)
Agung Setyo Pribadi (132010200197)
Eka Kurnia (132010200190)
FAKULTAS EKONOMI PROGRAM STUDI MANAJEMEN A - 2 ( PAGI ) SEMESTER – IV
UNIVERSITAS MUHAMMADIYAH SIDOARJO
KATA PENGANTAR
Kami panjatkan puji syukur kehadirat Allah SWT, atas limpahan rahmat hidayah dan inayahnya sehingga makalah ini dapat terbentuk sedemikian rupa. Tak lupa kami hanturkan sholawat serta salam kepada junjungan kita Nabi Besar Muhammad SAW yang telah membimbing kita menuju jalan yang benar.
Makalah ini kami buat dengan sengaja agar acara yang kami rencanakan dapat berjalan dengan lancar tanpa suatu kendala apapun. Harapan kami, semoga makalah ini dapat diterima dan bermanfaat untuk semua masyarakat.
Demikianlah makalah ini kami buat, kurang lebihnya kami mohon maaf yang sebesar-besarnya. Kami ucapkan terimakasih atas perhatiannya.
Sidoarjo,07 April 2015
Penyusun
DAFTAR ISI
KATA PENGANTAR 2
Pemilihan Cj-Zjyang kontroversial 4
Pemilihan Cj-Zj terkecil kasus Bawika 5
Interasi I: Pengujian di titik sudut A(10,0) 5
Interasi II: Pengujian di titik Sudut B(10, 1,67) 6
Iterasi III: pengujian di titik sudut C(6, 5) 10
Algoritma simpleks langkah mundur 12
Iterasi I pengujian mundur 16
Iterasi II pengujian mundur 17
Iterasi III PengujianMundur 18
Algoritma Simpleks II :KasusSukraRasmi 20
KoefisiensiVariabelArtifisial “αi” padaFungsiTujuan 21
IterasiI :AlgoritmaSimpleksSukraRasmi 22
IterasiII :AlgoritmaSimpleksSukraRasmi 25
IterasiIII :AlgoritmaSimpleksSukraRasmi 28
IterasiIV :AlgoritmaSimpleksSukraRasmi. 31
4.7.3 algoritma simpleks III : kasus Gupita 36
Iterasi 0 : kasus Gupita 37
Iterasi I : kasus Gupita 39
Iterasi II : kasus Gupita 41
Slack Variable Pada Variable Basis Adalah Sisa Kapasitas 45
DAFTAR PUSTAKA 46
Pemilihan Cj-Zjyang kontroversial
Pemilihan kolom kunci pada penyelesaian kasus Bawika telah berpedoman pada nilai Cj-Zj terbesar. Pedoman ini lebih didasarkan pada konsep opportunity cost sehingga pemilihan Cj-Zj terbesar belum tentu mengasilkan pertambahan nilai Z terbesar. Pertambahan nilai Z pada setiap interasi bukan hanya ditentukan oleh nilai Cj-Zj kolom kunci tetapi juga dipengaruhi oleh rasio baris kunci. Di samping itu pedoman persebut tidak menjamin efisiensi pengujian.
Peraga 4.42 menanyakan geometri sebuah kasus pemograman linear dimana sumbagan laba per unit X2 = Rp300,- dan X1 = Rp200,- seperti yang ditunjukan oleh garis laba Z = 0. Titik sudut B(6, 5) menjadi titik sudut ekstrem yang membuat nilai Z maksimum pada Z = 27. Pengujian titik sudut dengan algoritma simpleks bisa dilakukan melaliu dua arah
Pertama, arah pengujian melalui sumbu X2 dimana,
1. Iterasi 0 : pengujian titik sudut O(0,0)
2. Iterasi I : pengujian titik sudut D(0,6)
3. Iterasi II : pengujian titik sudut C(4,6)
4. Iterasi III : pengujian titik sudut B(6,5)
Cara ini dilakukan pada tabel simpleks dengan pemilihan X2 sebagai kandidat variabel basis yang pertama dan tercermin di dalam pemilihan kolom kunci yang memiliki Cj-Zj = 300 sebagai Cj-Zj tebesar. Dengan demikian, pada cara pertama ini kita akan menemukan nilai Z maksimum sebesar 27 B(6,5) setelah empat interasi.
Kedua, arah pengujian menelusuri sumbu X1 di mana,
1. Iterasi 0 : pengujian titik sudut O(0,0)
2. Iterasi 0 : pengujian titik sudut A(6,0)
3. Iterasi 0 : pengujian titik sudut B(6,5)
Cara ini pada tabel simpleks dilakukan dengan pemilihan X1 sebagai kandidat variabel basik yang pertama, dan tercermin di dalam pemilihan kolom kunci yang memiliki Cj-Zj = 200 sebagai Cj-Zj terkecil. Dengan cara ini kita akan menemukan nilai Z maksimum sebesar 27 di B(6,5) setelah tiga interasi.
Dengan demikian, kita telah membuktikan bahwa pemilihan kolom kunci yang mengacu pada Cj-Zj belum tentu lebih efisien dibandingkan pemilihan kolom kunci yang mengacu pada Cj-Zj terkecil.
Pemilihan Cj-Zj terkecil kasus Bawika
Kini, marilah kita melihat proses penyelesaian simpleks yang menggunakan pedoman Cj-Zj terkecil untuk memilih kolom kunci.
Interasi I: Pengujian di titik sudut A(10,0)
Pemilihan kolom satu yang memiliki Cj-Zj = 2 sebagai kolom kunci akan membawa kita kepada pengukian di titik sudut A(10,0).
Pada saat kita bergerak ke arah titik sudut A, nilai X1 menjadi semakin besar dan sebagai akibatnya nilai S3= 0, maka posisinya kini berubah menjadi variabel nonbasis dan digantikan oleh X1. Proses ini tercermin pada pemilihan kolom kunci dan basis kunci yang ditanyakan pada peraga 4.44. Selanjutnya peraga 4.45 dan peraga 4.46 menyakan seluruh variabel basis pada tabel simpleks interasi I dan tabel simpleks lengkap interasi I.
Interasi II: Pengujian di titik Sudut B(10, 1,67)
Tujuan pengujian selanjutnya adalah titik sudut B(10, 1,67).Di titik sudut ini X1 tetap bernilai 10 dan X2 menjadi 1,67, lihat peraha 4.47.
Pada peraga 4.47, kita melihat bahwa perpindahan pengujian dari A(10,0) ke B(10, 1,67) akan membuat nilai S1 semakin lama menjadi semakin kecil, seiring dengan kenaikan nilai X2, hingga akhirnya sama dengan nol pada saat X2 = 1,67. Jadi, X2 akan berubah menjadi variabel basis dan S1 sebagai akibatnya berubah menjadi variabel nonbasis. Perhatikan elemen kunci a12 = 6. Karena variabel basis harus berkoefisien +1, maka seluruh elemen pada baris satu harus di bagi dengan enam.
Dari uraian sebelumnya, kita telah mengetahui bahwa nilai Cj-Zj mencerminkan kontribusi variabel ke-j terhadap nilai Z. Nilai Cj-Zj< 0 jelas akan menurunkan nilai Z dan sebaliknya nilai Cj-Zj> 0 pasti akan menaikan nilai Z. Pada tabel simpleks interasi II yang di tanyakan oleh peraga 4.49 kita masih menjumpai Cj-Zj> 0 yaitu C5-Z5 = 5/2. Dengan demikian, kita bisa menyimpulkan bahwa nilai Z masih bisa dinaikan dengan memasukan S3 sebagai variabel basis. Oleh karena itu, pengujian harus di lanjutkan.
Iterasi III: pengujian di titik sudut C(6, 5)
Pengujian selanjutnya menurut peraga 4.50 adalah pengujian di titik sudut C(6. 5). Ketika kita meninggalkan titik sudut B(10, 1,67) menuju titik sudut C(6, 5), nilai S3 berubah menjadi positif. Semakin jauh kita kita meninggalkan titik sudut B(10, 1,67), semakin besar nilai S3. Di sisi yang lain, nilai S2 semakin kecil hingga akhirnya menjadi nol dan menjadi variabel nonbasis.
Proses pengujian titik sudut C(6, 5) melalui analisis geometri peraga 4.50 berhubungan dengan tabel simpleks peraga 4.51. Selain itu, di sini kita menjumpai elemen kunci yang tidak bernilai +1, yaitu a25 = 2/3. Oleh karena itu, seluruh elemen pada basis dua harus di bagi dengan 2/3 agar pada tabel simpleks iterasi berikutnya elemen a25 = +1.
Tabel simplek peraga 4.52 adalah tabel simpleks optimal yang ditandai oleh Cj-Zj = 0. Karena seluruh nilai Cj-Zj tidak ada yang posotif, maka tidak ada lagi peluang untuk menaikan nilai Z.
Pengujian beda arah dalam kasus Bawika ini telah membuktikan bagaimana algoritma simpleks tidak terikat pada ketentuan mengenai pemilihan kolom kunci yang harus di pillih. Selama masih ada Cj-Zj> 0 maka nilai fungsi tujuan masih bisa dinaikkan. Demikian pula bila masih dijumpai Cj-Zj< 0 maka nilai fungsi tujuan masih bisa dimunimumkan.
Algoritma simpleks langkah mundur
Pertanyaan kritis yang akan segera muncul adalah: “bagaimana dengan pemiliha Cj-Zj< 0?”. Apabila kita menggunakan analogi penyelesaian algoritma simpleks kasus Bawika ini, maka pemilihan Cj-Zj< 0 tentunya juga akan menentukan nilai Z pada interasi berikutnya. Bila Cj-Zj> 0 akan menaikan nilai Z maka pemilihan Cj-Zj< 0 tentu sebaliknya menurunkan nilai Z.
Tabel optimal simpleks kasus Bawika dinyatakan kembali pada peraga 4.53. Dari peraga tersebut kita menjumpai C3-Z3 = -1/4 dan C4-Z4 = - 3/4. Dengan demikian kita memiliki dua pilihan kandidat kolom kunci, yaitu kolom ke tiga dan kolom ke empat untuk menurunkan nilai Z.
Pemilihan kolom ke tiga sebagai kolom kunci akan membuat basis ke-1sebagai baris kunci dengan rasio terkecil +4, lihat peraga 4.54. Pilihan ini akan membuat S1 menjadi variabel basis dan S4 menjadi variabel nonbasis. Di samping itu, pilihan ini akan membuat nilai Z turun – 1/4 (4) = -1 sehingga nilai Z pada iterasi berikutnya akan menjadi 27 – 1 = 26.
Melalui geometri peraga 4.55, kita melihat bahwa perubahan S1 menjadi variabel basis dan S4 menjadi Variabel nonbasis terjadi pada saat pengujian perpindahan dari titik sudut C(6, 5) ke titik sudut D(4, 6). Dengan demikian kita mengetahui bahwa pemilihan kolom ketiga dengan C3-Z3 = - 1/4 sebagai kolom kunci akan membuat langkah simpleks mundur satu interasi ke pengujian titik sudut sebelumnya yaitu titik sudut D(4, 6) di mana nilai Z akan turun menjadi 26.
Di sisi lain kita mungkin memilih kolom keempat dengan C4-Z4 = - 3/4 sebagai kolom kinci. Pilihan ini akan membuat baris ketiga sebagai baris kunci karena memiliki rasio terkecil yaitu 8/3, lihat peraga 4.56.
Pilihan kolom keempat sebagai baris kunci akan membuat S2 menjadi variabel nonbasis. Ini berarti pengujian mundur ke titik sudut B(10, 1,67) seperti ditanyakan oleh geometri peraga 4.57.
Dengan demikian, kini semakin jelas bahwa dua macam pilihan Cj-Zj< 0 ternyata membawa kita ke arah pengujian mundur. Mana yang dipilih akan membawa kita kepada titik sudut O(0,0).
Iterasi I pengujian mundur
Pemilhan kolom ketiga sebagai kolom kinci membawa kita ke iterasi I yaitu pengujian di titik sudut D(4,6). Tabel simpleks lengkap iterasi ini ditanyakan pada peraga 4.58.
Bila kita ingin melangkah mundur lagi maka kita mempunyai pilihan kolom keempat dengan C4-Z4 = -2 sebagai kolom kunci. Pilihan ini akan membuat baris kedua menjadi baris kunci.
Iterasi II pengujian mundur
Pilihan kolom keempat sebagai kolom kunci, membawa kita ke pengujian titik sudut E(0,6) dimana Z akan turun dengan -2(4) = -8 sehingga nilai Z di titik sudut itu akan menjadi 26 – 8 = 16, lihat peraga 4.59 dan geometri peraga 4.60.
Iterasi III PengujianMundur
IterasimundursudahsampaidititiksudutE(0,6) , sepertipengujianmundurmasih bias dilanjutkankarena C6-Z6= -3 .
Kolomenamsebagaikolomkunci, bariskeempatsebagaibariskunci.
Cj 2 3 0 0 0 0 bi
Ci VB X1 X2 S1 S2 S3 S4
0 S1 5 0 1 0 0 -6 24
0 S2 1 0 0 1 0 -2 4
0 S3 1 0 0 0 1 0 10
0 X2 0 1 0 0 0 1 6
ZJ 0 3 0 0 0 3 18
Cj-Zj 2 0 0 0 0 -3
KolomkuncidansebagaikonsekuensinyabariskeempatsebagaibariskunciakanmembawakepengujiantitiksudutO(0,0) .
Pilihaniniakanmenyebabkannilai Z turundengan -3(6) = - 18 sehingganilaifungsitujuan Z padaiterasiberikutnyaakanmenjadi 18-18 = 0.
Interasi III pengujianmunduir yang ditayangkanpadaperaga 4.63 adalah tables simplekskasusBawikadimanasudahtidakmenjumpailagiCj-Zj<0 .danberartisudahtidakmungkinlagimelakukanpengujianlangkahhmundur.
Pengujianmunduriterasi III
TabelawalsimplekskasusBawika.
Cj 2 3 0 0 0 0 bi
Ci VB X1 X2 S1 S2 S3 S4
0 S1 5 6 1 0 0 0 60
0 S2 1 2 0 1 0 0 16
0 S3 1 0 0 0 1 0 10
0 S4 0 1 0 0 0 1 6
ZJ 0 3 0 0 0 0 0
Cj-Zj 2 0 0 0 0 0
Maksimumkan 2X1 + 3X3
Terhadapfunsi-fungsikendala,
1. Dept. I 5X1 + 6X2 ≤ 60
2. Dept. II X1 + 2X2 ≤ 16
3. Permintaan X1 X1≤ 10
4. Permintaan X2 X2≤ 6
X1 ,X2≤ 0
Dengan demikian, model matematissebuah table optimal simpleksmelaluipengujiantitikmundur.PemilihankolomkejdimanaCj-Zj< 0 akanmembuatpengujiantitiksudutkembalikearahpengujianiterasisebelumnya.
PemilihanCj-Zj< 0 akanmenaikkannilaifungsitujuandansebaliknyapemilihanCj-Zj< 0 akanmenurunkannilaifungsitujuantanpaharusterikatpadatujuan yang hendakdicapai.
Algoritma Simpleks II :KasusSukraRasmi
KasusSukraRasmidengananalisisgeometritelahdilakukanpada model matematisSukraRasmiadalah :
1. FungsiTujuan : Maks 40X1 + 30X2 [4.26]
Terhadapkendala-kendala :
2. 2X1+ X2 ≤ 20 [4.27]
3. 2X1+ 3X2 ≤ 32 [4.28]
4. 2X1- X2 ≤ 0 [4.29]
5. X2 ≥ 2 [4.30]
Model matematisdiolahdenganalgoritmasimpleksmenambahslack variablepadakemdalabaris ke-2 dan ke-3, surpus variabledanartificial variablepadakendalabaris ke-4 dan ke-5 sehinggabangunmatematikkendala-kendalamenjadi :
2. 2X1+X2 +S1 = 20 [4.31]
3. 2X1+ 3X2 + S2 = 30 [4.32]
4. 2X1- X2 - S3 + α3 = 0 [4.33]
5. X2 - S3 + α4 = 2 [4.34]
KoefisiensiVariabelArtifisial “αi” padaFungsiTujuan
Variabelartifisialadalahsuatususunankendalaakanmempengaruhifungsitujuan,tidaksepertisurpus variabledanslack variable yang tidakberpengaruhterhadapfungsitujuankarenamemilikikoefisiennol, artificial variable parameter M yaitubilangan yang sangatbesar. Kehadiranartificial variableα3danα4 menghendakipenggunaanbialngan M sebagaikoefisienfungsitujuanuntukmenandaieksistensinya, [4.14] ; sehinggafungsitujuanSukraRasmi [4.26] menjadiMaks 40X1 + 30X2 - M α3 -- M α4 [4.35]
Koefisien “α” fungi tujuankasuspemrograman linier mungkinmempunyaikoefisienpositif (+M) ataumungkinmempunyaikoefisien negative (-M).
TabelawalsimplekskasusSukraRasmi, pengujian di 0(0, 0).
Cj 2 3 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬-M α3 2 -1 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj ¬-2M 0 0 0 +M +M +M ¬-M ¬-2M
Cj-Zj 40+2M 30 0 0 ¬-M ¬-M ¬-M 0
Padakolomvariabel basis kitatidakmenjumpaiS3danS4 sebagaivariabel basis.Table simpleksmengandungsebuahbentukmatriksidentitaspadasetiap table simpleksmenandaiidentitasvariabel basis.Kehadiranartificial variableα3danα4 yang memilikikoefisien +1 diperlukanuntukmembentukmatriksidentitasberhubungsurpus variable S3danS4 yang memilikikoefisien -1.
IterasiI :AlgoritmaSimpleksSukraRasmi
KetikaseluhvariabelkeputusanX1danX2 adalahvariabelnonbasis; kedua, padaiterasipertama, ketikavariabelkeputusanX1 ssebagaivariabelnonbasis; kedua, padaiterasiX2 tetapsebagaivariabelnonbasis. Pemilihankolomsatusebagaikolomkuncitidakakanmembuatnilaifungsitujuan Z bertambahkarenapengujianmasihdilakukanpadatitiksudut yang sama.
Iterasi I, pengujiantitiksudut0(0, 0)
Pemilihankolomkesatusebagaikolomkuncimembuat X1 menjadikandidatvariabel basis padaiterasipertama.Konsekuenlogis, barisketigamenjadibariskuncisehinggaartificial variableα3 akanmenjadivariabelnonbasis.
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬M α3 2 -1 0 0 -1 0 0 0 0
¬M α4 0 1 0 0 0 -1 1 1 1
Zj ¬2M 0 0 0 +M +M +M ¬-M ¬-2M
Cj-Zj 40+2M 30 0 0 ¬-M ¬-M ¬-M 0
Variabel basis Iterasi I.
Cj 40 30 0 0 0 0 ¬M ¬M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 -0,5 1 0 -0,5 0 1 0
0 S2 0 0 1
40 α3 1 0 0 0
¬M α4 0 0 0 1
Zj
Cj-Zj
Variabel basis iterasi I.
Cj 2 3 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 2 1 0 0 0 -1 0 20
0 S2 0 4 0 1 0 0 -1 0 32
¬-40 α3 1 -0,5 0 0 -0,5 0 0,5 0 0
¬-M α4 0 1 0 0 0 -1 1 1 2
Zj
Cj-Zj
Nilairuaskanankendala yang beradadibawahkolom “bi” .karenaiterasi I masihmwngujititiksudut
O(0, 0) sepertiiterasi 0 makalogiskalautidakadaperubahanpadabi untukseluruhi. atau, tidakadapenggunaankapasitaskendalameskipunX1 telahmenjadivariabel basis. Strukturkendaladan parameter kendalaketigatidakmembuat X1 bernilaipositif.
IterasiII :AlgoritmaSimpleksSukraRasmi
Memilihkolomkeduasebagaikolomkunciuntukmelihatperilakubilangan M. bilakolomkeduaterpilihsebagaikolomkuncimakabariskeempatsebagaikonsekuensinyaterpilihsebagaibariskunci.PemilihankolomkeduasebagaikolomkuncidanbariskeempatbariskunciakanmenjadivariabelkeputusanX2sebagaivariabel basis danmemaksaartificial variableα4 membuatkeputusanvariabelnonbasis.
Table simplekslengkapiterasi I, pengujian di titiksudut0(0, 0).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 2 1 1 0 0 0 0 0 20
0 S2 2 3 0 1 0 0 0 0 32
¬40 X1 2 -1 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj 40 ¬-20-M 0 0 -20 +M -M ¬-M ¬-2M
Cj-Zj 50+M 0 0 ¬20 ¬-M ¬-20-M 0
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 2 1 0 0 0 0 0 20
0 S2 0 4 0 1 0 0 0 0 32
¬40 X1 1 -0,5 0 0 -1 0 0 0 0
¬-M α4 0 1 0 0 0 1 1 1 1
Zj 40 ¬-20-M 0 0 -20 +M 20 ¬-M ¬-2M
Cj-Zj 50+M 0 0 ¬20 ¬-M ¬-20-M 0
+ (100 + 200M) = 100algoritmasimpleksuntukmelengkapi table simpleksiterasikeduatidakberbeda.
Pengujian di titiksudutA(1, 2), ditunjukkanolehnilaivariabel basis X1 = 1danX2= 2.VribelkeputusanX1memangsudahmunculsebagaivariabel basis, kemunculannyatidakberpindahanpengujiandarititiksudutO(0, 0) karenaX1= 0danX2= 0 tetapsebagaivariabelnonbasis.
TabelSimplekslengkapiterasi II, pengujiantitiksudutA(1, 2).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 0 0 2 -1 0 16
0 S2 0 0 0 1 0 4 -1 0 24
¬40 X1 1 0 0 0 -0,5 -0,5 0,5 0 1
¬30 X2 0 1 0 0 0 0 0 1 2
Zj 40 30 0 0 -20 -50 20 -M 100
Cj-Zj 0 0 0 0 20 50 -20-M 0
Pengujian di titiksudutA(1, 2).
IterasiIII :AlgoritmaSimpleksSukraRasmi
Berdasarkanindikasi C5 – Z5 = 20 dan C6 – Z6 = 50 ,pemilihankolombaris ke-5 dan ke-6 sebagaikolomkunciakammembuatpengujiantitiksudutmenjadilebihpanjangdiamanpadaakhirnyapengujianakankembalipadakondisibilakolomm ke-6 dipilihsebagaikolomkunci.
Pemilihankolomkuncidanbariskunci
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 0 1 2 -1 0 16
0 S2 0 0 0 1 1 4 -1 0 24
¬40 X1 1 0 0 0 -1/2 -0,5 1/2 0 1
¬30 X2 0 1 0 0 -1 0 0 1 2
Zj 40 30 0 0 -20 -50 20 -M 100
Cj-Zj 0 0 0 0 20 50 -20-M 0
Pemilihankolom ke-6 sebagaikolomkuncidanbaris ke-2 sebagaibariskunciakanmembawakeiterasi III yaitupengujian di titiksudutD(4, 8).
Pengujian di titiksudutD(4, 8).
Tabelsimpleksiterasi III yaitupengujian di titiksudutD(4, 8) . Tabelinibelum optimal karenamasihmengandung C5 – Z5 = 7,5sehinggamempunyaikesempatanuntukmenaikkannilai Z.
IterasiIV :AlgoritmaSimpleksSukraRasmi.
Pemilihankolom ke-5 sebagaikolomkunciakanmembuatbarispertamaterpilihmenjadibariskuncikarenamemilikirasioterkecilyaitu 8. Karenaakanmenambahnilai Z.
TabelSimplekslengkapiterasi III, Pengujian di titiksudutD(4, 8).
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 -0,5 -0,5 0 -0,5 0 4
0 S2 0 0 0 0,25 0,25 1 -0,25 0 6
¬40 X1 1 0 0 0,13 0,38 0 0,38 0 4
¬30 X2 0 1 0 0,25 -0,25 0 -0,25 1 8
Zj 40 30 0 12,5 -7,5 0 7,5 0 400
Cj-Zj 0 0 0 -12,5 7,5 0 -7,5 - M -M
Dengan (7,5 x 8) = 60 sehingganilaifungsitujuan Z padaiterasi IV menjadi 400 + 60 = 460 , secarageometrispemilihanakanmembawakepengujiantitiksudutC(7, 6).
Pemilihankolomkuncidanbariskunci.
Cj 40 30 0 0 0 0 ¬-M ¬-M bi
Ci VB X1 X2 S1 S2 S3 S4 α3 α4
0 S1 0 0 1 -0,5 -0,5 0 -0,5 0 4
0 S2 0 0 0 0,25 0,25 1 -0,25 1 6
¬40 X1 1 0 0 0,13 0,38 0 0,38 0 4
¬30 X2 0 1 0 0,25 -0,25 0 -0,25 0 8
Zj 40 30 0 12,5 -7,5 0 7,5 0 400
Cj-Zj 0 0 0 -12,5 7,5 0 -7,5 - M -M
Pengujian di titiksudutC(7,6).
TitiksudutC(7,6) ,nilaifungsitujuanmenjadi Z = 40(7) + 30(6) = 460. Jadisepertinilai Z table simpleksiterasiakanmenjadi 460.
Dari titik sudut C (7,6) nilai fungsi tujuan ini menjadi Z=40(7) + 30(6) = 460 jadi literasi tabel siplek menjadi 460. Peraga 4.78 menayangkan tabel simpleks iterasi IV pengujian titik sudut C(7,6). Optimalisasi tabel ini ditandai oleh Cj – Zj ≤ 0 untuk selujuh J dengan ini tidak bisa lagi menaikkan nilia fungsi tujuan Z.
Fungsi tujuan kasusu sukra rasmi dari [4.26] maks 40X1 + 30X2. Karena X1 = 7 dan X2 = 6 maka nilai fungsi tujuan maksimum 40X1 + 30X2 karena X1 = 7 dan X2 = 6 maka nilai tujuan maksimum 40(7) + 30(6) = 460.
Surplus variabel S3 dan S4 muncul sebagai variabel basis menandai kapasitas yang terlampaui. Dari [4.33].
Karena surplus variabel S3 dan S4 muncul sebagai variabel basis jelas shadow price atau dual price dan kendala ke tiga dan empat bernilai nol.
Kedudukan S1 dan S2 sebagai variabel bahwa kendala pertama dan kedua adalah kendala aktif, yaitu kendala berbentuk titik sudut ekstrem sehingga slack variable. Pada kedua kendala ini bernilai nol. [4.31].
Sebagai kendala aktif maka shadow price atau dual price kedua kendala itu menjadi positif yaitu 15 dan 5. Lihat kasus sukra rasmi peraga 4.79.
4.7.3 algoritma simpleks III : kasus Gupita
Model matematis gupita adalah :
Agar model ini dapat diolah menggunakan algoritma simpleks harus ditambahkan slack variable, surplus variable, dan artificial variable agar membentuk matriks identiti.
Kasus gupita memiliki 5 kendala kendala pertama ketiga adalah kendala syarat dan tiga sisanya adalah kendala pembatas. Peraga 4.81 ke tabel awal simpleks dan peraga 4.82 tabel awal simpleks.
Iterasi 0 : kasus Gupita
Pada tabel awal menjumpai Cj –Zj < 0 membuat fungsi tujuan Z berkurang, hal ini juga menjadi kolom kunci. Tabel 4.82 menguji titik sudut A(0,0 ) peraga (4.84) membuat X1 menjadi variabel basis yang menggantika variabele basi S4 yang menjadikan variable non basis pada iterasi berikutnya. Langkah ini menjadika fungsi tujuan Z menjadi lebih kecil. Maka pengujian kembali ke titik O (0.0).
Dari sisi yang lain pemiliha kolom kedua senbagi kolom kunci akan membuat X2 sebagi variable basis ketiga dan memaksa artifial variable a3 menjadi variable non basis pada iterasi berikutnya peraga [4.85]. karena rasio basis ketiga adalah 3 maka 3(30 – 5M) = 90 – 15M menjadi 22M + (90 – 15M) = 7M + 90.
Iterasi I : kasus Gupita
Pilihan kolom kedua sebagai kolom kunci akan membawa kita ke pengujian titik sudut D(0,3) seperti tertayang pada peraga 4.86. selanjutnya peraga 4.87 menayangkan tabel simpleks iterasi I kasus Gupita yaitu pengujian titik sudut D(0,3).
Iterasi II : kasus Gupita
Kita memiliki dua pilihan untuk melanjutkan ke titik berikutnya, ditunjukkan oleh C1 – Z1 = 12,5 – 1,75M dan C5 – Z5 = 7,5 – 0,25M. Dalam kasus Gupita sangat bagus karena memiliki kolom kunci dimana kita bisa memilih alternatif pilihan selain kolom yang menjadi pilihan. Disini kita bisa memilih kolom kesatu atau kolom yang mengandung variable keputusan, selain tujuannya menemukan X1 dan X2 yang dapat meminimalkan fungsi tujuan Z, X1 menjadi variable basis dengan nilai 7 : 1,75 = 4. Pilihan ini secara otomatis akan membuat baris kesatu sebagai basis kunci (peraga 4.88). dimana afficial variable a1 dipaksa sebagai variable non basis.
Pilihan satu sebagai titik kunci yaitu O (4,2). Seperti peraga 4.89, hasil pengujian ditunjukkan peraga 4,90 yang memberikan nilai Z minimumnya 140.
Ketika kolom kesatu dipakai sebagai kolom kunci bahwa nilai Z iterasi selanjutnya adalah : 4(12,5 – 1,75M) = (50 – 7M) sehingga menjadi (7M + 90) + (50 – 7M) = 140 yang ditunjukkan tabel simpleks literasi II, ditabel ini didapat bahwa, Cj – Zj ≥ 0 untuk seluruh j didapat bahwa pegara 4.90 adalah tabel simpleks optimal khusus Gupita. Ringkasan optimal ini ditunjukkan peraga 4.91.
Surplus variable S1 dan S3 yang terletak pada baris kedua dan keempat peraga 4.91 bernilai nol. Nilai ini menunjukkan bahwa memiliki kendala aktif. Pada peraga 4.89 dilihat bahwa titik sudut ekstrem O(4,2). Dibentuk oleh perpotongan dua garis kendala itu. Shadow price dan dual price menunjukkan perubahan nilai fungsi tujuan bila nilai ruas kanan kendala berubah satu unit. Karena kendala shadow price dan dual price adalah kendala aktif maka dihasilkan C3 –Z3 = 7,143 dan C5 – Z5 = 5,714 pada tabel simpleks optimal pada peraga 4.90.
Dan peranan artificial variable itu bernilai nol sehingga,
Slack Variable Pada Variable Basis Adalah Sisa Kapasitas
Kemunculan slack variable, sebuah kendala pada variable basis menunjukkan bahwa kendala ini adalah : kendalah tidak aktif, artinya tidak berperan di dalam pembentukkan titik sudut ekstrem. Pada peraga 4.89 diditu tidak semua kendala digunakan, untuk mengetahui kendala sisa ada di kolom bi baris kedua, empat, dan kelima pada tabel simpleks 4.90.
Melalui penyelesaian kasus Gupita dapat diketahui bahwa penyelesaian kasus pemprograman linier dengan metoda simpleks menghasilkan informasi yang lebih banyak, dibanding dengan metoda geometri.
DAFTAR PUSTAKA
1. Siswanto. 2007. “Operation Research”. Jilid 1. Erlangga. Jakarta
Tidak ada komentar:
Posting Komentar