Jumat, 06 Juli 2018

RISET OPERASI | METODE SIMPLEKS


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 :
  1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.
  2. 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 :

VB
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










Tidak ada komentar:

Posting Komentar