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

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.

Pembentukan Model

Merumuskan Masalah

Penyelesaian Masalah

Validasi Model

Penerapan Hasil Akhir

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 :

Gambar 2.2 Tahap Analisis Kuantitatif

Sumber : Barry Render, 2006, p3

Developing

a Model

Acquiring

Input Data

Developing

a Solution

Testing the

Solution

Analyzing

the Results

Implementing

the Results

DEFINING

the Problem

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

Linear and integer programming

Simulation

Dynamic Inventory models

PERT ( critical path ) models

Simulation

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 : aij x

j (≤ , = , ≥) b

i , untuk semua i (i = 1, 2, …m) semua

xj ≥ 0

Keterangan :

• xj

= banyaknya kegiatan j, dimana j = 1, 2, …n, yang berarti terdapat n

variabel keputusan

• Z = nilai fungsi tujuan

• cj = sumbangan per unit kegiatan j, untuk masalah maksimasi c

j menunjukkan atau

penerimaan per unit, sementara dalam kasus minimasi ia menunjukkan biaya per

unit.

• bi : jumlah sumberdaya ke i (i = 1, 2, …m), berarti terdapat m jenis sumberdaya.

• aij

: 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 80 100 0 0

Basis X1 X2 S1 S2 bi bi / akk

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

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 80 100 0 0

Basis X1 X2 S1 S2 bi bi / akk

S1 0 1 2 NK 1 0 40 20 BK

S2 0 4 3 0 1 120 40

Zj 0 0 0 0 0

Cj-Zj 80 100

KK

0 0

Sumber : Perhitungan Metode Simpleks

KK = 100 Nilai dari kolom Cj – Zj yang terbesar

BK = 20 Nilai dari kolom bi / akk yang terkecil

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 :

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

B1 baru = ( B1 lama ) / NK

B2 baru = B2 lama - ( B1 lama * Ratio )

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 80 100 0 0

Basis X1 X2 S1 S2 bi bi / akk

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

27

Setelah ini kembali ke langkah ( c , d )

Tabel 2.5 Contoh Simpleks IV

Cj 80 100 0 0

Basis X1 X2 S1 S2 bi bi / akk

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

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

Basis X1 X2 S1 S2 bi bi / akk

X2 100 1/2 1 1/2 0 20 40

S2 0 5/2 NK 0 -3/2 1 60 24 BK

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

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 80 100 0 0

Basis X1 X2 S1 S2 bi bi / akk

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

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

Tujuan perusahaan untuk

memaksimalkan

2.7 Kerangka Pemikiran

Gambar 2.3 Kerangka Pemikiran

Sumber : Penulis

Munculnya kendala /

masalah keterbatasan.

Solusi Pengalokasian

Penerapan LP

dengan simpleks

MAKSIMASI KEUNTUNGAN

&

KOMBINASI PRODUK

FASILITAS

Studio

Indoor

Variabel

Keputusan

Fungsi

Tujuan

Fungsi

Kendala