MAKALAH
RISET OPERASI
METODE
SIMPLEKS
MIRA ZAKIA
18314169
2TA02
DOSEN : DODDY ARI SURYANTO
FAKULTAS
TEKNIK SIPIL DAN PERENCANAAN
JURUSAN
TEKNIK SIPIL
UNIVERSITAS
GUNADARMA
KATA
PENGANTAR
Dengan
menyebut nama Allah SWT yang Maha Pengasih lagi Maha Panyayang, Kami panjatkan
puja dan puji syukur atas kehadirat-Nya, yang telah melimpahkan rahmat,
hidayah, dan inayah-Nya kepada kami, sehingga kami dapat menyelesaikan makalah
ilmiah tentang limbah dan manfaatnya untuk masyarakat.
Makalah ilmiah ini telah kami susun dengan
maksimal dan mendapatkan bantuan dari berbagai pihak sehingga dapat
memperlancar pembuatan makalah ini. Untuk itu kami menyampaikan banyak terima
kasih kepada semua pihak yang telah berkontribusi dalam pembuatan makalah ini.
Terlepas dari semua itu, Kami
menyadari sepenuhnya bahwa masih ada kekurangan baik dari segi susunan kalimat
maupun tata bahasanya. Oleh karena itu dengan tangan terbuka kami menerima
segala saran dan kritik dari pembaca agar kami dapat memperbaiki makalah ilmiah
ini.
Akhir kata kami berharap
semoga makalah ilmiah tentang limbah dan manfaatnya untuk masyarakan ini dapat
memberikan manfaat maupun inpirasi terhadap pembaca.
Depok, 5 April 2018
Mira Zakia
Daftar Isi
KATA PENGANTAR.............................................................................................................
DAFTAR ISI...........................................................................................................................
BAB I PENDAHULUAN.....................................................................................................
1.1 Latar Belakang...........................................................................................................
1.2 Rumusan Masalah…………………………………………………………………..
1.3
Tujuan Penulisan…………………………………………………………………....
BAB II LANDASAN TEORI...............................................................................................
2.1
Landasan Teori...........................................................................................................
BAB III PEMBAHASAN.....................................................................................................
3.1
Penegertian Metode
Simpleks....................................................................................
3.2
Sejarah Metode
Simpleks..........................................................................................
3.3
Bentuk Baku Metode
Simpleks.................................................................................
BAB IV PENUTUP..............................................................................................................
4.1 Kesimpulan...............................................................................................................
4.2 Saran.........................................................................................................................
DAFTAR PUSTAKA...........................................................................................................
BAB
I
PENDAHULUAN
1.1 Latar
Belakang
Metode
penyelesaian program linier dengan metode simpleks pertamakali dikemukakan oleh
George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika diketemukan
alat hitung elektronik dan menjadi popular ketika munculnya computer. Proses
perhitungan metode ini dengan melakukan iterasi berulang-ulang sampai tercapai
hasil optimal dan proses perhitungan ini menjadi mudah dengan komputer.
Selanjutnya
berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program
linear bahkan sampai pada masalah riset operasi hingga tahun 1950an seperti
pemrogaman dinamik, teori antrian, dan persediaan.
Program
Linier merupakan metode matematik dalam mengalokasikan sumber daya yang langka
untuk mencapai tujuan tunggal seperti memaksimumkan atau meminimumkan biaya.
Program linier banyak diterapkan dalam membantu menyelesaikan masalah ekonomi,
industri, militer, social, dan lain-lain.
1.2 Rumusan
Masalah
1. Apa pengertian Metode Simpleks?
2. Bagaimana sejarah Metode Simpleks?
3. Bagaimana
bentuk baku dari Metode Simpleks ?
1.3 Tujuan Penulisan
1.
Mengetahui pengertian Metode Simpleks
2. Mengetahui sejarah Metode Simpleks
3. Mengetahui bentuk baku Metode Simpleks
BAB
II
TINJAUAN
TEORITIS
2.1 Landasan
Teori
Metode
simplex digunakan untuk menyelesaikan masalah optimasi yang melibatkan tiga
variabel atau lebih yang tidak dapat diselesaikan oleh metode grafik. Metode
simpleks adalah metode yang digunakan untuk menyelesaikan permasalahan yang
memiliki lebih dari dua variabel. Metode simpleks didefinisakan sebagai
cara menyelesaikan permasalan yang memiliki variabel keputusan minimal dua
dengan menggunalkan alat bantu tabel. Metode simpleks dibedakan menjadi dua
yaitu, metode simpleks maksimasi untuk mencari keuntungan maksimal dan metode
simpleks minimasi untuk mencari biaa minimal.
Algoritma simpleks dapat dianggap sebagai
generalisasi yang berarti dari eliminasi Gauss-Jordan standar atas aljabar
linier biasa. Tahap perhitungan dasar dalam algoritma simpleks sama dengan
tahap perhitungan dasar dalam sebagian besar aljabar linier dasar, yang disebut
dengan operasi pivot. Ini merupakanoperasi atas matriks-matriks yang digunakan
untuk menyelesaikan sistem persamaan linier, untuk menempatkan matriks dalam
bentuk baku (eselon), untuk mengevaluasi determinan, dan lain-lain.
Diberikan sebuah matriks A, lalu pilih entri pivot
tak nol aij dan tambahkan kelipatan baris i ke baris lainnya untuk memperoleh
nol pada kolom ke-j. Kemudian baris i dinormalisasikan dengan membaginya dengan
aij. Untuk menyelesaikan persamaan-persamaan linier elemen pivot bisa salah
satu dari entri yang tidak nol. Sebaliknya, metode simpleks membatasi pilihan
entri pivot dan ditetapkan secara total dengan memberikan sepasang kaidah
sederhana, kaidah masuk yang menentukan kolom pivot j dan kaidah keluar yang
menentukan baris pivot I (secara teori, ketiga kaidah baris elementer mungkin
diperlukan untuk menghindari kasus degenerate). Dengan mengikuti kaidah ini
yang dimulai dari data awal
algoritma
sampai pada penyelesaian program linier dengan sejumlah berhingga pivot.
BAB
III
PEMBAHASAN
Ada
dua faktor lainnya yang turut berkontribusi dalam pengembangan riset
operasional. Pertama adalah kemajuan mendasar yang dibuat di awal dalam
pengembangan teknik yang ada terhadap riset operasional. Setelah perang, banyak
ilmuwan yang berpartisipasi dalam tim riset operasional atau yang mendengarkan
keberhasilan tim termotivasi untuk melanjutkan penelitian relevan terhadap
suatu bidang, yang menunjukkan pengembangan penting dari sudut seni yang
dihasilkan. Salah satu contoh paling penting adalah ditemukannya metode
simpleks untuk menyelesaikan permasalahan pemrograman linear oleh George
Dantzig tahun 1947. Banyak teknik riset operasional, seperti pemrograman
linear, pemrograman dinamis, teori antrian dan teori inventori telah
dikembangkan dengan baik di akhir tahuan 1950-an.
Faktor
kedua adalah perkembangan teknologi komputer. Perhitungan kompleks sering harus
dilakukan untuk permasalahan kompleks. Jika dilakukan dengan tangan (secara
manual) sering menjadi masalah dan bahkan sering tidak mungkin dilakukan. Pengembangan
komputer digital elektronik dengan kemampuan melakukan perhitungan aritmetik
tinggi telah memberikan penyelesian yang ribuan atau jutaan kali lebih cepat
daripada yang bisa manusia lakukan dengan tangan.
3.1 Pengertian Metode
Simpleks
Program linier merupakan metode
matematika dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu
tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Program linier
banyak diterapkan dalam masalah ekonomi industri, militer, sosial dan lain-lain.
Program linier berkaitn dengan penjelasan suatu kasus dalam dunia nyata sebagai
suatu metode matematika.
Salah satu
teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah
metode simpleks. Penentuan solusi optimal menggunakan metode simpleks
didasarkan pada teknik eliminasi Gaus Jordan. penentuan solusi optimal
dilakukan dengan memeriksa titik ekstrim satu persatu dengan cara perhitungan
iteratif. sehingga penentuan solusi optimal dengan simpleks dilakukan dengan
tahap demi tahap yang disebut dengan iterasi.
Metode simpleks
ini adalah metode yang biasanya digunakan untuk memecahkan setiap permasalahan
pada pemrograman linier yang kombinasi variabelnya terdiri dari tiga variabel
atau lebih. Metode simplex merupakan sebuah metode lanjutan dari metode grafik.
Metode grafik tidak dapat menyelesaikan persoalan manajemen yang memiliki
variabel keputusan yang cukup besar, sehingga untuk menyelesaikannya dibutuhkan
sebuah metode yang lebih kompleks yaitu dengan menggunakan program komputer QSB
( Quantitative System For Business) atau menggunakan metode simplex. Dalam
kenyataanya penggunaan komputer lebih efisien, akan tetapi metode dasar yang
digunakan dalam pengoperasian komputer tetap metode simplex.
Metode simplex
adalah metode yang dapat digunakan untuk menyelesaikan persoalan manajerial
yang telah diformulasikan terlebih dahulu ke dalam persamaan matematika program
linear yang mempunyai variable keputusan mulai dari lebih besar atau sama
dengan 2 (dua) sampai multivariable. Sedangkan metode grafik hanya dapat
digunalan apabila jumlah variable keputusan maksimal 2 (dua) buah. Sehingga
dapat disimpulkan bahwa suatu persoalan linear programing yang diselesaikan
dengan metode grafik juga dapat diselesaikan dengan metode simpleks, sebaliknya
suatu persoalan yang hanya bisa diselesaikan dengan metode simplex tidak dapat
diselesaikan dengan metode grafik.
3.2 Sejarah Metode Simpleks
Penemu
metode simpleks adalah George Bernard Dantzig. Dantzig adalah matematikawan
Amerika yang lahir di Oregon pada 8 November 1914 dan wafat pada 13 Mei 2005.
Beliau adalah Profesor Emiritus Ilmu Transportasi dan Profesor Riset Operasi
dan Ilmu Komputer di Stanford. Pada tahun 1974, beliau memperoleh penghargaan
John Von Neumann Theory Prize dan pada tahun 1975 mendapat penghargaan National
Medal of Science.
Metode
simpleks menjadi teknik standard untuk menyelesaikan masalah PL sejak tahun
1947. Metode simpleks adalah suatu prosedur perhitungan yang berulang-ulang
dengan bilangan terbatas yang dimulai dari suatu penyelesaian dasar fisibel
(PDF). Apabila PDF bukan PO, maka metode simpleks akan mencari PDF lain yang
lebih baik sehingga diperoleh PDF yang optimal (jika ada). Metode simpleks
didasarkan atas prinsip bahwa PO dari masalah PL selalu dapat ditemukan pada PDF.
Secara geometris metode simpleks melangkah dari titik-titik ekstrem daerah
penyelesaian fisibel dan secara cepat meningkatkan nilai fungsi tujuan sampai
menemukan PO atau menegaskanbahwa tidak ada PO. Titik ekstrem daerah
penyelesaian fisibel perpadanan dengan PDF. Oleh karena itu langkah pertama
metode simpleks adalah mengupayakan adanya PDF.
3.3 Bentuk
Baku Metode Simpleks
Sebelum melakukan perhitungan
iteratif untuk menentukan solusi optimal, pertama sekali bentuk umum
pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku
dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk
sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel
basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi
sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel keputusan
semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala pada
bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala
tersebut masih harus tetap berubah.
Ada beberapa hal yang harus diperhatikan dalam
membuat bentuk baku, yaitu :
- Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah
menjadi persamaan (=) dengan menambahkan satu variabel slack.
- Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah
menjadi persamaan (=) dengan mengurangkan satu variabel surplus.
BENTUK BAKU
Sebelum melakukan perhitungan iteratif untuk
menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier
dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks
tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi
setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel
basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas
yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai
nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman
linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap
berubah.
Ada beberapa hal yang harus diperhatikan dalam
membuat bentuk baku, yaitu :
a) Fungsi
kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan
(=) dengan menambahkan satu variabel slack.
b) Fungsi
kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan
(=) dengan mengurangkan satu variabel surplus.
c) Fungsi
kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial
variabel (variabel buatan).
Contoh soal
:
Selesaikan
kasus berikut ini menggunakan metode simpleks :
Maksimum z
= 8 x1 + 9 x2 + 4x3
Kendala :
x1 +
x2 + 2x3 ≤ 2
2x1 +
3x2 + 4x3 ≤ 3
7x1 +
6x2 + 2x3 ≤ 8 x1,x2,x3 ≥ 0
Penyelesaian
:
Bentuk
bakunya adalah :
Maksimum z
= 8 x1 + 9 x2 + 4x3 + 0s1 + 0s2 + 0s3atau z - 8
x1 - 9 x2 - 4x3 + 0s1 + 0s2 + 0s3 = 0
Kendala :
x1 +
x2 + 2x3 + s1 = 2 2x1 + 3x2 + 4x3 + s2 = 3
7x1 + 6x2 + 2x3 + s3= 8 x1,x2,x3 ,s1 , s2 , s3≥ 0
Solusi /
table awal simpleks :
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
|
|
|
|
|
|
|
|
|
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
|
|
|
|
|
|
|
|
|
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
|
|
|
|
|
|
|
|
|
|
Karena
nilai negative terbesar ada pada kolom X2, maka kolom X2 adalah kolom
pivot dan X2 adalah variabel masuk. Rasio pembagian nilai kanan dengan
kolom pivot terkecil adalah 1 bersesuaian dengan baris s2, maka baris
s2 adalah baris pivot dan s2 adalah varisbel keluar. Elemen pivot
adalah 3.
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
2
|
|
|
|
|
|
|
|
|
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
1
|
|
|
|
|
|
|
|
|
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
8/6
|
|
|
|
|
|
|
|
|
|
Iterasi 1
Nilai
pertama yang kita miliki adalah nilai baris pivot baru (baris x2). Semua nilai
pada baris s2 pada tabel solusi awal dibagi dengan 3 (elemen pivot).
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
Z
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
|
|
|
|
|
|
|
|
|
|
S3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Perhitungan
nilai barisnya :
Baris z :
|
|
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
-9 ( 2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
) -
|
|
|
|
-2
|
0
|
8
|
0
|
3
|
0
|
9
|
|
|
Baris
s1 :
|
|
|
|
|
|
|
|
|
|
|
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
|
|
1
|
(2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1 ) -
|
|
|
|
|
|
1/3
|
0
|
2/3
|
1
|
-1/3
|
0
|
1
|
|
|
Baris s3
:
|
|
|
|
|
|
|
|
|
|
|
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
|
|
6
|
( 2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1 ) -
|
|
|
|
|
3
|
0
|
-6
|
0
|
-2
|
1
|
2
|
|
|
Maka tabel
iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel
sudah optimal atau belum. Karena nilai baris z di bawah variabel x1 masih
negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada tabel
di bawah ini :
|
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
Z
|
-2
|
0
|
8
|
0
|
3
|
0
|
9
|
-
|
|
|
|
|
|
|
|
|
|
S1
|
1/3
|
0
|
2/3
|
1
|
-1/3
|
0
|
1
|
3
|
|
|
|
|
|
|
|
|
|
X2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
3/2
|
|
|
|
|
|
|
|
|
|
S3
|
3
|
0
|
-6
|
0
|
-2
|
1
|
2
|
2/3
|
|
|
|
|
|
|
|
|
|
Variabel
masuk dengan demikian adalah X1 dan variabel keluar adalah S3.Hasil
perhitungan iterasi ke 2 adalah sebagai berikut :
Iterasi 2 :
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
Z
|
0
|
0
|
4
|
0
|
5/3
|
2/3
|
31/3
|
|
|
|
|
|
|
|
|
|
|
S1
|
0
|
0
|
4/3
|
1
|
-1/9
|
-1/9
|
7/9
|
|
|
|
|
|
|
|
|
|
|
X2
|
0
|
1
|
8/3
|
0
|
7/9
|
-2/9
|
5/9
|
|
|
|
|
|
|
|
|
|
|
X1
|
1
|
0
|
-2
|
0
|
-2/3
|
1/3
|
2/3
|
|
|
|
|
|
|
|
|
|
|
Tabel sudah optimal, sehingga
perhitungan iterasi dihentikan !
Perhitungan
dalam simpleks menuntut ketelitian tinggi, khususnya jika angka yang digunakan
adalah pecahan. Pembulatan harus diperhatikan dengan baik. Disarankan jangan
menggunakan bentuk bilangan desimal, akan lebih teliti jika menggunakan
bilangan pecahan. Pembulatan dapat menyebabkan iterasi lebih panjang atau
bahkan tidak selesai karena ketidaktelitian dalam melakukan pembulatan.
Perhitungan
iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu
titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari
kondisi nol (dimana semua aktivitas/variabel keputusan bernilai nol). Jika
titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan
perhitungan iteratif sebanyak n kali.
BAB
IV
PENUTUP
4.1 Kesimpulan
Metode
simplek ini adalah metode yang biasanya digunakan untuk memecahkan setiap
permasalahan pada pemrograman linier yang kombinasi variabelnya terdiri dari
tiga variabel atau lebih. Metode simplex merupakan sebuah metode lanjutan dari
metode grafik. Metode grafik tidak dapat menyelesaikan persoalan manajemen yang
memiliki variabel keputusan yang cukup besar, sehingga untuk menyelesaikannya
dibutuhkan sebuah metode yang lebih kompleks yaitu dengan menggunakan program
komputer QSB (Quantitative System For Business) atau menggunakan metode
simplex. Dalam kenyataanya penggunaan komputer lebih efisien, akan tetapi
metode dasar yang digunakan dalam pengoperasian komputer tetap metode simplex.
4.2 Saran
Semoga
penulis dan pembaca dapat mengetahui dan memahami materi Metode Simpleks ini
terutama pengaplikasiannya di bidang Teknik Sipil .Jika ada kesalahan dalam
penulisan makalah ini penulis mengharapkan kritikan atau saran dari pembaca.
DAFTAR PUSTAKA
