AlgoritmaSimplex

AlgoritmaSimplexadalahalgoritmayangdigunakanuntukmengoptimalkanfungsiobjektifdanmemperhatikansemuapersamaan

kendala.(GeorgeDantizg,USA,1950)

ContohKasusSuatuperusahaaninginmemproduksi2jenisbarang,yaitukursidanmeja.1Kursimembutuhkanmaterial:2kgkayu,1kgplastik,dan1kgbesi.1mejamembutuhkanmaterial1kgkayu,2kgplastik,dan3kgbesi.

Ternyata,perusahaanitusetiapjamnyahanyamampumenyediakanmaksimal16kgkayu,11kgplastik,dan15kgbesi.Untukpenjualan,1kursidapatdijualseharga30$,sedangkan1mejadapatdijualseharga50$.Jadi,berapabanyakkursidanmejayangharusdiproduksiolehperusahaanitusetiapjamnyaagarkeuntungannyamaksimum?

Penyelesaian1. KalimatMatematis.

FungsiObjektif:

Kendala:

Kendalavariabel:

2. GambarGrafik

Titikoptimumnyaadalah(7,2).

Artinya: Setiap jam, jumlah kursi yang diproduksi haruslahsebanyak 7, dan jumlah meja yang diproduksi haruslahsebanyak2,sehinggadapatmenghasilkankeuntungansebesar310$.

(0,0) Z=0(0,5) Z=250(3,4) Z=290(7,2) Z=310(8,0) Z=240

Metodegrafiktidakbisadigunakanjikavariabelnyalebihdari2.Maka,digunakanmetodesimpleks,yangakanmenutupi

kekuranganitu.

Caramenggunakanmetodesimpleks.Buatkalimatmatematis:

FungsiObjektif:

Kendala:

Kendalavariabel:

Ubahpertidaksamaanmenjadipersamaan.

Artinya,akanmunculsuatuvariabelbaruyangnilainyatidakdiketahui.KitanamakanvariabelitusebagaiVariabelSlack,karenaberfungsiuntukmenampungnilaisisa.

menjadi ,dimana .FungsiObjektif:

Kendala:

Kendalavariabel:,

, ,

Ubahfungsiobjektifsehingganilaikanannyaadalahkonstanta.(tidakharuspositif)

Pindahkanruaskanankeruaskiri,menjadi:

Dengandemikian,kitadapatmenuliskankembalipersamaanmatematikanyamenjadi:FungsiObjektif:

Kendala:

Kendalavariabel:,

, ,

BuatTABLEAWALSIMPLEKS:

Tambahkan1kolombaru:VariabelBasis:

IterasiI.TabelAwalSimplex

Selanjutnya,gunakanTahapanSimplex,berikut:

1.DaribarisZpilihangkayangnegatifdanpalingnegatif.Makakolomitumenjadikolomkunci.

2.Hitungrasiotiapbaris.Pilihyangterkecildanpositif.Makabarisitumenjadibariskunci.Perpotonganbariskuncidankolomkuncidinamakanpivot.

3.Ubahpivotmenjadi1denganoperasiperkalian.4.Ubahselselpadakolomkunci(kecualipivot)menjadinoldenganoperasimatematika.

5.Ubahvariabelbasismenjadiyangsesuai.6.JikadibarisZ,masihadaselyangnegatifmakaulangilangkahnomor1.Jikasemuaselsudahpositif,makaiterasiselesai,dankondisioptimumsudahterpenuhi.

Bingung???LangsungContohaja.

IterasiPertama:Tabelawal:

1.DibarisZada2nilainegatif,yaitu30dan50.Karena50adalahyangpalingnegatif,makapilihkolommsebagaikolomkunci.

2.Hitungrasioditiapbariskendala.RasiotiapbarisdihitungdenganmembagiRHSdenganseldikolomkunci.Rasioyangterkecildanpositifadalah5.Artinyakendalake3menjadibariskunci.

Pivotadalahperpotonganantarabariskuncidankolomkunci.3.Supayapivotmenjadi"1",makabagilahbariske4dengan3,makamenjadi:

4.Selanjutnya,usahakanagarselselyangberadadikolomkuncisemuanyamenjadinol.(kecualipivot).Barispertamayangbaru=barispertamayanglama+50*bariske4.Bariskeduayangbaru=bariskeduayanglamabariske4Barisketigayangbaru=barisketigayanglama2*bariske4.

Maka,hasilnyaadalahsebagaiberikut:

5.Langkahinisungguhmudah.Cukupmengeluarkan"S3"darivariabelbasisdanmenggantinyadengan"m".

6.Ternyata,dibarisZmasihterdapatselnegatif,yaitu13.333.

Olehkarenaitu,kitalakukaniterasiberikutnyadenganmenggunakanlangkahyangsamasepertipadanomor1s/d6,namunmenggunakantabelyangterakhirdiperoleh.

IterasiKedua:Tabelawal:

Denganmenggunakanlangkahlangkahyangsamapersissepertidiatas,makadapatkanhasilakhiriterasikedua,sbb:

KarenamasihadaselyangnegatifdibarisZ,makalakukaniterasiberikutnya.

IterasiKetiga:Tabelawalyangdigunakansamasepertihasilakhiriterasikedua.Denganlangkahlangkahyangdigunakantetapsama.Makakitadapatkanhasilakhiriterasiketigasbb:

KarenasemuaseldibarisZsudahsemuanyanonnegatif,makaiterasiberakhir,danpenyelesaiandidapatdenganmelihatvariabelbasisdanRHSyangbersesuaian:

k=7,m=2denganZ(maks)=310

Ringkasan:

IterasiiterasiIterasi1awal:

======k=0,m=0,Z=0======

Iterasi2awal:

======k=0,m=5,Z=250======

Iterasi3awal:

======k=3,m=4,Z=290======

Iterasi4(3akhir):

======k=7,m=2,Z=310======

Dapatdilihatbahwasemakiniterasi,makanilaiZakansemakinmeningkat.Lebihjauhlagi,jikadilihatdarigrafik,sebenarnyaiterasisimpleksberjalanmengitaridaerahyangdibatasiolehtitiktitikpojokdandiaakanberhentijikadiatidakdapatbergeraklagi.Perhatikangambardibawah:

Latihan:Denganmenggunakanmetodesimpleks:1.Maksimumkanfungsi dengankendalasebagaiberikut:

2.Maksimumkanfungsi dengankendalasebagaiberikut:

Jawaban1.

2.