4
BAB 2 LANDASAN TEORI
2.1 Riset Operasi 2.1.1 Pengertian Riset Operasi Definisi dari Riset Operasi ( Operations Research Society of America ) ” Operations
research concerned with scientifically deciding how to best design and operate man – machine systems, usually under conditions requiring the allocation of scarce resources. ” Jika diartikan ke dalam bahasa Indonesia menjadi ” Riset operasi yang berkaitan dengan menentukan pilihan secara ilmiah bagaimana merancang dan menjalankan sistem manusia – mesin secara terbaik, dimana biasanya membutuhkan alokasi terhadap sumber daya yang langka.” Pengertian Riset Operasi lainnya ( Hamdi A. Taha 1976 ) ” Operation Research
adalah pendekatan dalam pengambilan keputusan yang ditandai dengan penggunaan pengetahuan ilmiah melalui usaha kelompok antar disiplin yang bertujuan menentukan penggunaan terbaik sumber daya yang terbatas. ” Pengertian Riset Operasi menurut ( Churchman, Ackoff, dan Arnoff 1957 ) ”
Operation Research is the application of scientific methods, techniques and tools to problems involving the operations of a system so as to provide in control of the system with optimum solutions to the problem. ”
Jika diartikan ke dalam bahasa Indonesia
menjadi ” Riset operasi adalah penerapan metode – metode ilmiah, teknik – teknik, dan alat – alat terhadap masalah – masalah yang menyangkut operasi – operasi dari sistem – sistem, sedemikian rupa sehingga mampu memberikan penyelesaian optimal terhadap masalah yang dihadapi. ”
5
2.1.2 Model Dalam Riset Operasi Jenis model dasar dalam riset operasi adalah ( Sri Mulyono, 2004. P5 ) :
1. Iconic ( Physical ) Model Model iconic adalah suatu penyajian fisik yang tampak seperti aslinya dari suatu sistem nyata dengan skala yang berbeda. Contohnya = mainan anak – anak, potret, histogram dan lain – lain. Model iconic mudah untuk diamati, dibentuk dan dijelaskan, tetapi sulit untuk memanipulasi dan tak berguna untuk tujuan peramalan. Biasanya model ini menunjukkan peristiwa statik.
2. Analogue Model Model analogue lebih abstrak dibanding model iconic, karena tak kelihatan sama antara model dengan sistem nyata. Contohnya jaringan pipa tempat air mengalir dapat digunakan dengan pengertian yang sama sebagai distribusi aliran listrik. Model analog lebih mudah untuk memanipulasi dan dapat menunjukkan situasi dinamis.
3. Mathematic ( Simbolic ) Model Model matematik memiliki sifat yang paling abstrak. Model ini menggunakan seperangkat simbol matematik untuk menunjukkan komponen – komponen ( dan hubungan antar mereka ) dari sistem nyata. Namun, sistem nyata tidak selalu diekspresikan dalam rumusan matematik.
2.1.3 Tahap - Tahap Riset Operasi Pola dasar penerapan Riset Operasi dapat dipisahkan menjadi 5 tahapan dimulai dari munculnya masalah hingga hasil akhir. Kelima tahapan tersebut yaitu :
6 Merumuskan Masalah
Pembentukan Model
Penyelesaian Masalah
Validasi Model
Penerapan Hasil Akhir
Gambar 2.1 Tahap Riset Operasi Sumber : Sri Mulyono, 2004, p7-8 1. Merumuskan masalah Dalam perumusan masalah ada tiga pertanyaan penting yang harus dijawab: • Variabel keputusan / Instrument Æ Unsur – unsur dalam persoalan yang dapat dikendalikan oleh pengambil keputusan. • Fungsi Tujuan / Objective Function Æ Hubungan matematika linear yang menjelaskan tujuan perusahaan dalam terminologi variabel keputusan.
7
• Kendala / Constraint Æ Pembatas – pembatas terhadap alternatif tindakan yang tersedia. 2. Pembentukan model Model merupakan ekspresi kuantitatif dari tujuan dan kendala – kendala persoalan dalam variabel keputusan. 3. Mencari penyelesaian masalah Pada tahap ini bermacam – macam teknik dan metode solusi kuantitatif yang merupakan bagian utama dari Riset Operasi memasuki proses. Penyelesaian masalah sesungguhnya merupakan aplikasi satu atau lebih teknik – teknik ini terhadap model. 4. Validasi Model Model harus diperiksa apakah ia mencerminkan berjalannya sistem yang diwakili. Model dikatakan valid jika dengan kondisi input yang serupa, ia dapat menghasilkan kembali performance seperti masa lampau. Masalahnya adalah bahwa tak ada yang menjamin performance masa depan akan berlanjut meniru cerita lama. 5. Penerapan hasil akhir Tahap terakhir adalah menerapkan hasil model yang telah diuji.
2.1.4 Tahapan Analisis Kuantitatif Dalam Manajemen Analisis kuantitatif merupakan pendekatan secara ilmiah yang membantu manajerial untuk
membuat
keputusan.
Dalam
pembuatan
keputusan,
manajer
harus
mempertimbangkan faktor kualitatif ( cuaca, hukum, teknologi ) maupun kuantitatif (
8
arus kas, tingkat investasi ). Ketika faktor kualitatif yang dimiliki sedikit maka hasil dari analisis kuantitatif dapat membantu dalam proses pengambilan keputusan. Jika berdasarkan tahapan riset operasi untuk pengambilan keputusan terdapat 5 tahapan, namun pada analisis kuantitatif terdapat 7 tahapan yaitu :
DEFINING the Problem
Developing a Model
Acquiring Input Data
Developing a Solution
Testing the Solution
Analyzing the Results
Implementing the Results Gambar 2.2 Tahap Analisis Kuantitatif Sumber : Barry Render, 2006, p3
9
1. Defining the Problem ( Merumuskan masalah ) Langkah pertama dalam analisis kuantitatif adalah menetapkan pernyataan masalah yang jelas dan ringkas. Pernyataan ini akan memberikan petunjuk untuk langkah berikutnya. Suatu masalah mungkin memiliki hubungan dengan masalah lainnya. Jika menyelesaikan satu masalah tanpa mempertimbangkan masalah lainnya maka bisa membuat situasi menjadi lebih buruk. Oleh karena itu penting untuk menganalisis bagaimana solusi untuk suatu masalah mempengaruhi masalah lainnya atau mempengaruhi situasi secara umum. Pada umumnya sebuah perusahaan akan memiliki beberapa permasalahan. Namun analisis kuantitatif tidak bisa digunakan untuk mengatasi keseluruhan permasalahan secara bersamaan, jadi perlu konsentrasi hanya pada beberapa permasalahan. Permasalahan yang biasanya dipilih adalah permasalahan dengan solusi yang menghasilkan keuntungan terbesar atau solusi yang menghasilkan biaya terkecil.
2. Developing a Model ( Mengembangkan model ) Model merupakan sebuah gambaran dari situasi yang ada. Macam – macam model yaitu physical, scale, schematic, dan mathematical models. Model biasanya mewakilkan satu atau lebih variabel dan parameter. Model yang dikembangkan haruslah bisa dipecahkan, realistic, mudah dimengerti dan diperbaharui, serta input data yang diperlukan dapat dikumpulkan. Dalam proses pengembangan model, terdapat beberapa klasifikasi model yaitu :
10
Tabel 2.1 Klasifikasi Model
Decision Problem
Major variables in a decision problem are : Certain
Uncertain
Simple
Case models
Decision analysis ( decision trees )
Complex
Case models
Simulation
Linear and integer programming Dynamic
Inventory models
Simulation
PERT ( critical path ) models
Inventory models Queuing models
Sumber : (Render, Barry, Stair, Ralph M., Jr. 1997. ) • Simple Problems ( masalah sederhana )
Simple models hanya terdiri dari jumlah variabel / faktor yang sedikit dan hanya beberapa alternatif. Simple models sangat bermanfaat bahkan untuk masalah pengambilan keputusan yang penting.
Case / scenario model adalah model dari masalah pengambilan keputusan yang dianalisis dengan cara mencoba beberapa alternatif. Para manajer biasanya menggunakan model trial and error process. Decision analysis models menggabungkan beberapa peluang dalam proses pengambilan keputusan. • Complex Problems Pada model ini melibatkan banyak faktor / variabel dan banyak alternatif untuk dipertimbangkan. Model Linear and integer programming menggunakan teknik matematika untuk memecahkan masalah perusahaan yang lebih kompleks. Teknik matematika ini digunakan untuk menemukan nilai maksimum atau nilai minimum dari sebuah fungsi tujuan dan masalah kendala yang
11
dihadapi. Simulasi adalah teknik untuk mengatasi sistem permasalahan yang lebih kompleks pada keadaan yang tidak pasti. • Dynamic Problems Pada model ini melibatkan beberapa bagian yang jauh lebih kompleks ( dimana ada rangkaian beberapa keputusan yang saling berhubungan untuk beberapa periode ). Inventory model digunakan untuk memutuskan kapan melakukan pemesanan dan berapa banyak yang akan disimpan. PERT / critical
path adalah model untuk penjadwalan produk. Queuing models untuk mengatasi masalah yang berhubungan dengan antrian.
3. Acquiring Input Data ( Memperoleh data ) Setelah
mengembangkan
model
maka
langkah
berikutnya
adalah
mengumpulkan data yang akurat. Data yang diperlukan dapat diperoleh dari berbagai sumber. Sebagai contoh : laporan perusahaan, wawancara dengan karyawan dan sampling secara statistik.
4. Developing a Solution ( Mengembangkan solusi ) Dalam
pengembangan
solusi,
model
yang
ada
dimanfaatkan
untuk
menghasilkan solusi yang optimal bagi suatu masalah. Solusi yang akurat tergantung dari data dan model yang akurat pula.
5. Testing the Solution ( Menguji solusi )
12
Sebelum sebuah solusi bisa dianalisis dan diimplementasi, solusi tersebut haruslah diuji terlebih dahulu. Data dan model juga harus diuji karena data dan model mempengaruhi solusi. Data dan model diuji agar terbukti akurat karena data yang tidak akurat akan menghasilkan solusi yang tidak akurat juga.
6. Analyzing the Results ( Analisis hasil ) Analisis hasil dimulai dengan menentukan implikasi dari solusi. Pada beberapa kasus, solusi untuk permasalahan akan menghasilkan tindakan atau perubahan terhadap proses operasional perusahaan. Implikasi dari tindakan atau perubahan tersebut haruslah dianalisis terlebih dahulu sebelum hasil tersebut diimplementasi.
7. Implementing the Results ( Implementasi hasil ) Proses ini merupakan proses memasukkan solusi ke dalam perusahaan. Proses ini bisa menjadi bagian sulit daripada yang pernah dibayangkan. Jika solusi sudah optimal dan menghasilkan keuntungan jutaan dollar, namun jika manajer menentang solusi tersebut maka usaha dari analisa akan menjadi sia – sia. Setelah diimplementasi, perusahaan harus melakukan pengawasan secara berkala.
2.1.5 Ciri - ciri Riset Operasi Ada beberapa ciri dari riset operasi yang menonjol antara lain ( Sri Mulyono, 2004, p10 ) : •
Riset Operasi merupakan pendekatan kelompok antar disiplin untuk mencari hasil optimum.
13
•
Riset Operasi menggunakan teknik penelitian ilmiah untuk mendapatkan solusi optimum.
•
Riset Operasi hanya memberikan jawaban yang buruk terhadap persoalan jika tersedia jawaban yang lebih buruk. Ia tidak memberikan jawaban sempurna terhadap masalah itu, sehingga Riset Operasi hanya memperbaiki kualitas solusi.
2.1.6 Masalah Dalam Riset Operasi Beberapa masalah Riset Operasi yang didefinisikan dengan baik dan diterima umum dapat digolongkan sebagai berikut ( Sri Mulyono, 2004, p9 ) : 1. Masalah alokasi 2. Masalah teori permainan 3. Masalah antrian 4. Masalah jaringan 5. Masalah persediaan
2.2 Program Linier George B . Dantzig diakui umum sebagai pioner LP, karena jasanya dalam menemukan metode mencari solusi masalah LP dengan banyak variabel keputusan. Dantzig bekerja pada penelitian teknik matematika untuk memecahkan masalah logistik militer ketika dipekerjakan oleh angkatan udara Amerika Serikat selama Perang Dunia 2.
14
2.2.1 Pengertian Program Linier • Suatu teknik matematika yang didesain untuk membantu para manager dalam merencanakan dan membuat keputusan yang diperlukan untuk mengalokasikan sumber daya. ( Heizer & Render, 2004, p588. ) • Model yang terdiri dari hubungan linear yang menggambarkan keputusan perusahaan dengan suatu tujuan dan batasan sumber daya tertentu ( Taylor III, 2005, p32. ) • Suatu teknik aplikasi matematika dalam menentukan pemecahan masalah yang bertujuan untuk memaksimumkan atau meminimumkan sesuatu yang dibatasi oleh batasan – batasan tertentu. ( Tumpal JR, 2006, p2.) • Suatu cara untuk menyelesaikan persoalan pengalokasian sumber yang terbatas diantara beberapa aktivitas yang bersaing, dengan cara terbaik yang mungkin dilakukan. Persoalan pengalokasian itu akan muncul manakala seseorang harus memilih tingkat aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas tersebut. (Bahtiar Saleh Abbas, Robert Tang Herman & Shinta. Jurnal Piranti Warta Vol 11 No 3 Agustus 2008. p472. )
2.2.2 Persyaratan Persoalan Dalam Program Linier Persoalan LP mempunyai empat sifat umum yaitu ( Heizer & Render, 2004, p590) : •
Persoalan LP bertujuan untuk memaksimalkan atau meminimalkan kuantitas ( pada umumnya berupa laba atau biaya ). Sifat umum ini disebut sebagai fungsi tujuan ( objective function ) dari suatu persoalan LP.
15
•
Adanya batasan atau kendala, yang membatasi tingkat sampai di mana sasaran dapat dicapai.
Untuk memaksimalkan atau meminimalkan suatu
kuantitas bergantung pada sumber daya yang jumlahnya terbatas. •
Harus ada beberapa alternatif tindakan yang dapat diambil. Jika tidak ada alternatif yang dapat diambil maka LP tidak diperlukan.
•
Tujuan dan batasan dalam permasalahan pemrograman linear harus dinyatakan dalam hubungan dengan pertidaksamaan atau persamaan linear.
2.2.3 Manfaat dan Tujuan Program Linier Masalah keputusan yang sering dihadapi dalam LP adalah alokasi optimum sumber daya yang langka. Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan dan teknologi. Tujuan dari LP adalah mencapai hasil terbaik yang mungkin dengan keterbatasan sumber daya itu. Hasil yang diinginkan mungkin ditunjukkan sebagai maksimisasi dari beberapa ukuran seperti profit, penjualan dan kesejahteraan atau minimisasi seperti pada biaya, waktu dan jarak.
2.3 Formulasi Model Program Linier Setelah masalah diidentifikasikan, tujuan ditetapkan, langkah selanjutnya adalah formulasi model matematik yang meliputi tiga tahap seperti ( Sri Mulyono, 2004, p14 ) : 1. Tentukan variabel yang tidak diketahui ( variabel keputusan ) dan nyatakan dalam simbol matematik. 2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier ( bukan perkalian) dari variabel keputusan.
16
3. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam persamaan atau tidak persamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumber daya masalah itu. Dalam proses pembuatannya, kendala terdiri dari beberapa jenis / tipe yaitu (Render, Barry, Stair, Ralph M., Jr. 1997. ) : 1. Capacity constraints Kendala ini dibatasi oleh jumlah peralatan, tempat atau ketersediaan sumber daya manusia. 2. Market constraints Kendala ini dibatasi oleh seberapa banyak produk bisa dijual atau dimanfaatkan. 3. Availability constraints Kendala ini dibatasi oleh kelangkaan bahan baku, tenaga kerja, dana dan sumber daya lainnya. 4. Quality or blending constraints Kendala ini dibatasi oleh perpaduan komposisi, biasanya untuk menentukan kualitas dari produk hasil. 5. Production technology or material balance constraints Kendala ini menetapkan hasil dari suatu proses merupakan input untuk proses lainnya. 6. Definitional constraints Kendala yang menetapkan sebuah istilah di suatu bidang
17
Bentuk umum persoalan program linear (MDH Gamal & Zaiful Bahri. Jurnal Natur Indonesia. 2003. ) ; Fungsi Memaksimumkan ( Meminimumkan ) =
Dengan syarat :
a x (≤ , = , ≥) b , untuk semua i (i = 1, 2, …m) semua ij
j
i
x≥0 j
Keterangan :
x
•
j
= banyaknya kegiatan j, dimana j = 1, 2, …n, yang berarti terdapat n
variabel keputusan •
Z=
•
c
j
nilai fungsi tujuan
= sumbangan per unit kegiatan j, untuk masalah maksimasi c menunjukkan atau j
penerimaan per unit, sementara dalam kasus minimasi ia menunjukkan biaya per unit. •
b
•
a
i
: jumlah sumberdaya ke i (i = 1, 2, …m), berarti terdapat m jenis sumberdaya.
ij
: banyaknya sumberdaya i yang dikonsumsi sumberdaya j.
18
Sebagai contoh : 1. Variabel keputusan X1 = jumlah produk 1 X2 = jumlah produk 2 X3 = jumlah produk 3 2. Fungsi Tujuan Z = 300X1 + 500X2 + 200X3 Dimana : Z
= Total laba per hari
3x1 = laba dari produk 1 ( sebesar 300 ) 5x2 = laba dari produk 2 ( sebesar 500 ) 2x3 = laba dari produk 3 ( sebesar 200 ) 3. Sistem Kendala Tepung
Æ 5 X1 + 2 X2 + 4X3 ≤ 400
Dimana : 5x1 = jumlah tepung untuk produksi produk 1 2x2 = jumlah tepung untuk produksi produk 2 4x3 = jumlah tepung untuk produksi produk 3 240 = jumlah tepung yang bisa digunakan untuk memproduksi x1, x2, x3 ≤
= lambang untuk maksimalisasi ( contoh : memaksimalkan laba )
Jika untuk meminimalisasi ( contoh : minimisasi biaya ) maka lambang yang digunakan adalah ≥.
19
Mesin
Æ 4 X1 + 6 X2 + 3 X3 ≤ 200
Dimana : 4x1 = jam kerja mesin untuk produksi produk 1 6x2 = jam kerja mesin untuk produksi produk 2 3x3 = jam kerja mesin untuk produksi produk 3 200 = jumlah jam kerja mesin yang digunakan untuk produksi x1, x2, x3
2.4 Asumsi Model Program Linier Model LP mengandung asumsi – asumsi implisit tertentu yang harus dipenuhi agar definisinya sebagai suatu masalah LP menjadi absah. Asumsi – asumsi itu adalah ( Sri Mulyono, 2004, p23 – 24 ) :
1. Linierity and Additivity Syarat utama dari LP adalah bahwa fungsi tujuan dan semua kendala harus linier. Dengan kata lain, jika suatu kendala melibatkan 2 variabel keputusan, dalam diagram dimensi akan berupa suatu garis lurus. Begitu juga, suatu kendala yang melibatkan tiga variabel akan menghasilkan suatu bidang datar dan kendala yang melibatkan n variabel akan menghasilkan hyperplane ( bentuk geometris yang rata ) dalam ruang berdimensi n. Kata linier secara tidak langsung mengatakan bahwa hubungannya proporsional yang berarti bahwa tingkat perubahan atau kemiringan hubungan fungsional itu adalah konstan dan karena itu perubahan nilai variabel akan mengakibatkan perubahan relatif nilai fungsi tujuan dalam jumlah yang sama
20
Aditif dapat diartikan sebagai tak adanya penyesuaian pada perhitungan variabel kriteria karena terjadinya interaksi. ( Every function in a LP model is the
sum of the individual contributions of the respective activities ) 2. Divisibility Asumsi ini berarti bahwa nilai solusi yang diperoleh, tidak harus berupa bilangan bulat.
3. Deterministic Dalam LP, semua parameter model diasumsikan diketahui konstan. LP secara tak langsung mengasumsikan suatu masalah keputusan dalam suatu kerangka statis di mana semua parameter diketahui dengan kepastian. Dalam kenyataannya, parameter model jarang bersifat deterministik, karena mereka mencerminkan kondisi masa depan maupun sekarang, dan keadaan masa depan jarang diketahui dengan pasti.
2.5
Penyelesaian Dalam Model LP Untuk menyelesaikan masalah dalam Linear programming dapat dilakukan dengan 2 cara yaitu : 1. Penyelesaian dengan model grafik Æ Dalam menemukan solusi optimum, digunakan grafik ( digunakan untuk produk =2). 2. Penyelesaian dengan metode simpleks Æ Dalam menemukan solusi optimum, digunakan tabel simpleks ( digunakan untuk produk yang jumlahnya ≥ 2 ).
21
2.6 Metode Simpleks Pemograman Linear Masalah – masalah LP yang ada di dunia nyata biasanya memiliki lebih dari 2 buah variabel sehingga sulit untuk diselesaikan dengan menggunakan grafik. Oleh karena itu dibutuhkan metode simpleks untuk menyelesaikan masalah tersebut. Pengertian dari metode simpleks adalah suatu algoritma untuk memecahkan berbagai permasalahan pemograman linear yang melibatkan 2 variabel maupun lebih dua variabel ( Mulyono, 2004, p31 ). Metode ini menyelesaikan LP melalui perhitungan ulang ( iteration ) di mana langkah – langkah perhitungan yang sama diulang berkali – kali sebelum solusi optimum tercapai. Dalam menggunakan metode simpleks untuk menyelesaikan masalah – masalah LP, model LP harus diubah ke dalam suatu bentuk umum yang dinamakan ” bentuk baku ” (
standard form ). Ciri – ciri bentuk baku model LP adalah ( Sri Mulyono, 2004 , p32 ) : 1.
Semua kendala berupa persamaan dengan sisi kanan non negatif.
2.
Semua variabel non negatif.
3.
Fungsi tujuan dapat maksimum maupun minimum.
Dalam penyelesaian masalah LP dengan grafik, telah dinyatakan bahwa solusi optimum selau terletak pada titik pojok ruang solusi. Metode simpleks didasarkan pada gagasan ini, dengan langkah – langkah seperti berikut ( Tumpall JR, 2006, p9 ): a.
Merubah model program linear menjadi model persamaan linear
b.
Menyusun tabel simpleks awal
c.
Menghitung nilai Zj pada setiap kolom variabel dan kolom bi.
d.
Menghitung nilai ( Cj-Zj ) pada setiap kolom variabel.
22
e.
Periksa nilai – nilai ( Cj-Zj ), jika
( Cj-Zj ) ≤ 0 ( untuk tujuan
memaksimumkan) maka ke langkah ( l ) atau jika ( Cj-Zj ) ≥ 0 ( untuk tujuan meminimumkan ) maka ke langkah ( l ) f.
Tentukan kolom kunci berdasarkan nilai ( Cj-Zj ). Kolom kunci terletak pada kolom variabel yang nilai
( Cj-Zj ) positif terbesar jika tujuannya
memaksimumkan, sebaliknya kolom kunci terletak pada kolom variabel yang nilai ( Cj-Zj ) negatif terbesar jika tujuannya meminimumkan. g.
Tentukan baris kunci berdasarkan nilai ( bi / akk ) positif terkecil.
h.
Tentukan angka kunci (ak ) yaitu angka yang terletak pada kolom kunci dan baris kunci.
i.
Ganti variabel yang terletak pada baris kunci dengan variabel yang terletak pada kolom kunci.
j.
Lakukan transformasi setiap baris yang dimulai dengan baris kunci dengan rumus transformasi sebagai berikut :
k.
Kembali ke langkah ( c )
l.
Solusi optimal diperoleh, dimana nilai variabel basis untuk masing - masing baris terletak pada kolom bi
Contoh Soal Variabel keputusan Æ X1 , X2 Fungsi tujuan Æ Z = 80x1 + 100x2 Fungsi Kendala
23
Æ 1x1 + 2x2 ≤ 40 ( 1 ) Æ 4x1 + 3x2 ≤ 120 ( 2 ) Æ
x1 , x2 ≥ 0
Penyelesaian Langkah ( a ) : Z = 80x1 + 100x2 + 0s1 + 0s2 Fungsi kendala Æ 1x1 + 2x2 + 1s1 + 0s2 = 40 Æ 4x1 + 3x2 + 0s1 + 1s2 = 120 Langkah ( b, c , d ) : Tabel 2.2 Contoh Simpleks I
Cj Basis
80
100
0
0
X1
X2
S1
S2
bi
S1
0
1
2
1
0
40
S2
0
4
3
0
1
120
Zj
0
0
0
0
0
Cj-Zj
80
100
0
0
Sumber : Perhitungan Metode Simpleks
Langkah ( e ) : Cj-Zj ( x1 ) = 80 Cj-Zj ( x2 ) = 100
bi / akk
24
Cj-Zj ( s1 ) = 0 Cj-Zj ( s2 ) = 0 Bila diperhatikan, nilai – nilai (Cj-Zj ) ≥ 0, maka hal ini menunjukkan bahwa nilai Z masih dapat ditingkatkan ( tujuannya memaksimumkan ) atau dengan kata lain table simpleksnya harus direvisi ( belum menyediakan solusi optimal )
Langkah ( f,g, h ) : Berdasarkan nilai (Cj-Zj ) dan tujuan memaksimumkan, maka kolom kuncinya adalah kolom variable X2. Hal ini menunjukkan bahwa variabel X2 akan ditempatkan pada kolom basis untuk menggantikan variabel basis yang terletak di kolom basis. Tabel 2.3 Contoh Simpleks II
Cj Basis
80
100
0
0
X1
X2
S1
S2
bi
bi / akk
S1
0
1
2 NK
1
0
40
20
S2
0
4
3
0
1
120
40
Zj
0
0
0
0
0
Cj-Zj
80
100
0
0
KK Sumber : Perhitungan Metode Simpleks KK = 100 Æ Nilai dari kolom Cj – Zj yang terbesar BK = 20 Æ Nilai dari kolom bi / akk yang terkecil
BK
25
NK = 2 Æ Perpotongan dari KK dan BK Ratio Tetap = angka pada kolom kunci / NK = 3 / 2
Langkah ( i, j ) : Pada tabel simpleks berikutnya, variabel S1 digantikan oleh X2 dengan nilai Cj untuk variabel X2 sebesar 100. Kemudian unsur – unsur pada setiap baris ditransformasi, misalnya unsur – unsur baris pertama yang merupakan baris kunci ditransformasikan dengan rumus :
B1 baru = ( B1 lama ) / NK B2 baru = B2 lama - ( B1 lama * Ratio )
Kolom baru dari basis S1 menjadi basis X2 Rumus B1 baru ”1”
= 1 /2
”2”
= 2/2
”1”
= 1/2
”0”
=0/2
” 40 ”
=2
26
Kolom baru untuk basis S2 Rumus B2 baru ”4”
= 4 – ( 1 * 3/2 ) = 5/2
”3”
= 3 – ( 2 * 3/2 ) = 0
”0”
= 0 – ( 1 * 3/2 ) = - 3/2
”1”
= 1 – ( 0 * 3/2 ) = 1
” 120 ” = 120 – ( 40 * 3/2 ) =60
Tabel 2.4 Contoh Simpleks III
Cj Basis
80
100
0
0
X1
X2
S1
S2
bi
X2
100
1/2
1
1/2
0
20
S2
0
5/2
0
-3/2
1
60
Zj Cj-Zj Sumber : Perhitungan Metode Simpleks
bi / akk
27
Setelah ini kembali ke langkah ( c , d ) Tabel 2.5 Contoh Simpleks IV
Cj Basis
80
100
0
0
X1
X2
S1
S2
bi
X2
100
1/2
1
1/2
0
20
S2
0
5/2
0
-3/2
1
60
Zj
50
100
50
0
2000
Cj-Zj
30
0
-50
0
bi / akk
Sumber : Perhitungan Metode Simpleks
Langkah ( e ) : Cj-Zj ( x1 ) = 30 Cj-Zj ( x2 ) = 0 Cj-Zj ( s1 ) = - 50 Cj-Zj ( s2 ) = 0
Nilai – nilai ( Cj-Zj ) tersebut di atas menunjukkan bahwa tabel simpleks harus direvisi karena tujuannya adalah untuk memaksimumkan. Hal ini dikarenakan masih ditemukannya nilai Cj –Zj yang positif yaitu 30.
28
Langkah ( f, g , h ) : Tabel 2.6 Contoh Simpleks V
Cj
80
100
0
0
X1
X2
S1
S2
Basis
bi
bi / akk
X2
100
1/2
1
1/2
0
20
40
S2
0
5/2 NK
0
-3/2
1
60
24
Zj
50
100
50
0
2000
Cj-Zj
30
0
-50
0
KK Sumber : Perhitungan Metode Simpleks
KK = 30 Æ Nilai dari kolom Cj – Zj yang terbesar BK = 24 Æ Nilai dari kolom bi / akk yang terkecil NK = 5/2 Æ Perpotongan dari KK dan BK Ratio Tetap = angka pada kolom kunci / NK = ( 1/2 ) / ( 5/2 ) = 2 / 10 = 1/5
BK
29
LANGKAH ( I , J ) Pada table simpleks berikutnya, variable S2 digantikan oleh X1 dengan nilai Cj untuk variable X1 sebesar 80. Kemudian unsur – unsur setiap baris ditransformasi.
Kolom baru dari basis S2 menjadi basis X1 Rumus B1 baru ” 5/2 ” = ( 5 / 2 ) / ( 5/ 2 ) = 1 ”0”
= 0/ ( 5/2 ) = 0
” -3/2 ” = (-3/2) / ( 5/2 ) = - 3/5 ”1”
= 1 / (5/2) = 2 / 5
” 60 ”
= 60 / (5/2) = 24
Kolom baru untuk basis X2 Rumus B2 baru ” 1/2 ” = 1/2 – ( 5/2 * 1/5 ) = 0 ”1”
= 1 – ( 0 * 1/5 ) = 1
” 1/2 ” = 1/2 – ( -3/2 * 1/5 ) = 4/5 ”0”
= 0 – ( 1 * 1/5 ) = -1/5
” 20 ”
= 20 - (60*1/5 ) = 8
30
Tabel 2.7 Contoh Simpleks VI
Cj Basis
80
100
0
0
X1
X2
S1
S2
bi
X2
100
0
1
4/5
-1/5
8
X1
80
1
0
-3/5
2/5
24
Zj
80
100
32
12
2720
Cj-Zj
0
0
-32
-12
bi / akk
Sumber : Perhitungan Metode Simpleks
Apakah solusi dimana X1 = 24, X2 = 8, S1 = 0, S2 = 0 dan Z maksimum sebesar 2720 merupakan solusi optimal ?? Pertanyaan akan dijawab melalui langkah berikut : Cj-Zj ( x1 ) = 0 Cj-Zj ( x2 ) = 0 Cj-Zj ( s1 ) = - 32 Cj-Zj ( s2 ) = -12 Karena ( Cj – Zj ) ≤ o, maka solusi di atas optimal, dimana produk X1 uang harus dihasilkan adalah sebanyak 24 dan produk X2 yang harus dihasilkan sebanyak 8. Laba maksimum yang akan diperoleh ( Z maks ) = 2720.
31
Kebutuhan utama metode simpleks adalah adanya solusi awal layak (initial basic
feasible solution). Tanpa ini tabel simpleks tak dapat dibuat. Ada dua pendekatan untuk mendapatkan suatu solusi awal yang layak yaitu dengan cara (Sri Mulyono, 2004, p40–41): 1. Coba – coba Di sini suatu variabel basis dipilih secara sembarang untuk setiap kendala. Jika dihasilkan suatu solusi layak (nilai variabel basis pada kolom solusi non negatif), maka metode simpleks bisa dimulai. Meskipun coba – coba dapat diulangi lagi sampai diperoleh solusi awal layak, metode ini jelas tidak efisien dan mahal. 2. Menggunakan Artificial Variable Gagasan penggunaan artifical variable sangat sederhana. Tambahkan suatu
artificial variable pada sisi kiri setiap persamaan yang tidak memiliki variabel basis. Dinamakan artificial (sebagai lawan dari ” real decision variable ”) karena ia tidak memiliki arti nyata. Artificial digunakan hanya untuk memulai penyelesaian dan pada urutan selanjutnya mereka harus dijadikan nol pada solusi akhir, jika tidak, solusi yang dihasilkan akan menjadi tak layak.
32
2.7 Kerangka Pemikiran Tujuan perusahaan untuk memaksimalkan
Munculnya kendala / masalah keterbatasan. FASILITAS
Studio Indoor
Solusi Pengalokasian
Variabel
Fungsi
Fungsi
Keputusan
Tujuan
Kendala
Penerapan LP dengan simpleks
MAKSIMASI KEUNTUNGAN & KOMBINASI PRODUK Gambar 2.3 Kerangka Pemikiran Sumber : Penulis
