riset operasi
Post on 05-Dec-2014
217 Views
Preview:
DESCRIPTION
TRANSCRIPT
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 1
RISET OPERASI
Ada beberapa definisi mengenai Riset Operasi (RO). Dasar dari berbagai
macam definisi dilator belakangi bahwa ahli Riset Operasi dari berbagai disiplin
ilmu seperti teknik, bisnis, matematik, dll.
Operational research Society Of Great Britain mendefinisikan RO adalah
aplikasi metode ilmiah dalam masalah yang kompleks dan system manajemen
besar atas manusia, mesin, material, dan dana dalam industry, bisnis, pemerintah
dan militer.
Operational research Society Of America mendefinisikan RO adalah
berkenaan dengan pengambilan keputusan secara ilmiah, bagaimana membuat
model terbaik dam membutuhkan alokasi sumber daya yang terbatas. Sedara lebih
umum RO dapat didifinisikan senagai model kwantitatif atau matematik yang
digunakan dalam pengambilan keputusan managemen.
Riset operasi adalah metode untuk memformulasikan dan merumuskan
permasalahan sehari-hari mengenai bisnis,ekonomi,sosial maupun bidang lainya
dalam pemodelan matematis untuk mendapatkan solusi yang optimal.
Komputer Dan Riset Operasi
Penggunaan komputer dalam RO secara terus menerus mengalami
peningkatan terutama dalam menghadapi persaingan lingkungan internasional dan
masalah produktivitas . Tanpa bantuan computer sangat mustahil untuk
menyelesaikan masalah yang cukup besar.
Pendalaman Matematis
Bagian terpenting Riset Operasi adalah bagian menerjemahkan
permasalahan sehari-hari kedalam model matematis. Faktor-faktor yang
mempengaruhi pemodelan harus disederhanakan dan apabila ada data yang
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 2
kurang, kekurangan tersebut dapat diasumsikan atau diisi dengan pendekatan yang
bersifat rasional. Dalam Riset Operasi diperlukan dan memudahkan kita
mendapatkan hasil, kita dapat menggunakan komputer. Software yang dapat
digunakan antara lain : LINDO ( Linier Interactive And Discreate Optimizer ).
Proses Pembuatan Model Riset Operasi
Langkah-langkah dalam pembuatan model matematika sebagai berikut :
1. Mendefinisikan masalah yang sedang dihadapi. Langkah ini penting dan
dapat melibatkan manajemen maupun anggota organisasi lainya.
2. Memformulisasikan model. Model adalah gambaran abstrak dari masalah
yang sedang dihadapi. Ketepatan dalam memformulasikan model sangat
ditentukan oleh asumsi yang digunakan. Asumsi harus realitas dan
merupakan factor kesulitan dalam menbuat model. Komponen utama dalam
memformulasikan model adalah sebagai berikut :
� Variabel Keputusan ( Decision Variabel )
� Tujuan ( Objektive )
� Kendala ( Consttaint )
3. Mengukur Validitas
4. Implementasi Keputusan
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 3
METODE SIMPLEKS
Salah satu teknik penentuan solusi optimal yang digunakan dalam
pemrograman linier adalah metode simpleks. Penentuan solusi optimal
menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan.
Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu
dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan
simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i
hanya tergantung dari iterasi sebelumnya (i-1)
Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks,
diantaranya :
1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu
tergantung dari nilai tabel sebelumnya.
2. Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada
sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu
sama dengan derajat bebas dalam sistem persamaan.
3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang
iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi
kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi
kendala menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah
variabel basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non
negatif).
4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih
tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah
sumber daya pembatas awal yang ada, karena aktivitas belum dilaksanakan.
5. Variabel slack adalah variabel yang ditambahkan ke model matematik
kendala untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan (=).
Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal,
variabel slack akan berfungsi sebagai variabel basis.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 4
6. Variabel surplus adalah variabel yang dikurangkan dari model matematik
kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=).
Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel
surplus tidak dapat berfungsi sebagai variabel basis.
7. Variabel buatan adalah variabel yang ditambahkan ke model matematik
kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis
awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini
harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak
ada. Variabel hanya ada di atas kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk.
Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk
menentukan baris pivot (baris kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis
yang memuat variabel keluar.
10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan
kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk
tabel simpleks berikutnya.
11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis
pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non
basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai
positif.
12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi
berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu
dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi
berikutnya akan bernilai nol.
� Contoh soal :
Selesaikan kasus berikut ini menggunakan metode simpleks :
Maksimum z = 8 x1 + 9 x2 + 4x3
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 5
� 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 + 0s3 atau
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.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 6
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
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 7
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
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 8
bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan
melakukan perhitungan iteratif sebanyak n kali.
� Contoh soal :
Persamaan matematis suatu program linier adalah sebagai berikut :
Minimasi : Z = 6X1 + 7,5X2
Dengan pembatas :
7X1 + 3X2 ≥ 210
6X1 + 12X2 ≥ 180
4X2 ≥ 120
X1, X2 ≥ 0
Carilah harga X1 dan X2 ?
� Jawab :
Pada kasus ini kita akan menggunakan metode simplex M (BIG – M), hal ini
dikarenakan pada kasus ini pertidk samaan pembatasnya menggunakan ≥
(lebih dari sama dengan).
Persamaan Tujuan : Z - 6x1 - 7,5X2 - 0S1 - 0S2 - 0S3 = 0 Baris 0
Persamaan Kendala : 7x1 + 3x2 - S1 +A1 = 210 Baris 1
6x1 + 12x2 - S2 +A2 = 180 Baris 2
4x2 - S3 + A3 = 120 Baris 3
Bagi kendala pertidaksamaan jenis ≤, maka variabel slack ditambahkan untuk
menghabiskan sumber daya yang digunakan dalam kendala. Cara ini tidak
dapat diterapkan pada kendala pertidaksamaan jenis ≥ dan kendala persamaan
(=) persamaan diatas diperoleh karena tanda ≥ harus mengurangi variable
surplus.
Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar
ditempatkan pada A1, A2, dan A3 sehingga fungsi tujuannya menjadi :
Z = 6x1 + 7,5X2 + 0S1 + 0S2 + 0S3 + MA1 + MA2 + MA3
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 9
Table simplex awal dibentuk dengan A1, A2, dan A3 sebagai variable
basis, seperti table berikut :
Basis X1 X2 S1 S2 S3 A1 A2 A3 NK RASIO
Z 13M-6 19M-
7,5
-M -
M
-M 0 0 0 510M
A1 7 3 -1 0 0 1 0 0 210 210 : 3 =
70
A2 6 12 0 -1 0 0 1 0 180 180 : 12 =
15
A3 0 4 0 0 -1 0 0 1 120 120 : 4 =
30
Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini
dikarenakan seluruh NBV masih mempunyai koefisien yang berharga positif.
Oleh karena itu Untuk x2 terpilih sebagai entry variable karena x2 memiliki
nilai koefisien positif yang paling besar, dan A3 menjadi Leaving Variable.
Dan yang akan menjadi pivot adalah baris 2 karena memiliki rasio paling
kecil.
Langkah-langkah ERO Iterasi Pertama :
ERO 1 : Menjadikan nilai koefisien x2 berharga 1 pada baris 2
½ x1 + x2 - 1/12 S2 +
1/12 A2 = 15
ERO 2 : Menjadikan nilai koefisien x2 berharga 0 pada baris 0
Z = 9/4 x1 + 0S1 + 15/24 S2 + 0S3 + MA1 + [ M - 15/24]A 2 + MA3 + 112,5
ERO 3 : Menjadikan nilai koefisien x2 berharga 0 pada baris 1 11/2 x1 + ¼ S2 + A1 -
1/4 A2= 165
ERO 4 : Menjadikan nilai koefisien x2 berharga 0 pada baris 3
-2x1 + 1/3 S2 - S3 - 1/3 A2 + A3 = 60
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 10
Konversi bentuk standard iterasi Pertama :
Z = 9/4 x1 + 0S1 + 15/24 S2 + 0S3 + MA1 + [ M - 15/24]A 2 + MA3 + 112,5 11/2 x1 + ¼ S2 + A1 -
1/4 A2 = 165
-2x1 + 1/3 S2 - S3 - 1/3 A2 + A3 = 60
½ x1 + x2 - 1/12 S2 +
1/12 A2 = 15
Tabel Iterasi Pertama
Basis X1 X2 S1 S2 S3 A1 A2 A3 NK RASIO
Z
-13/2M-
6
0 0 7/12 - 15/24
-M 0 1/24 -
M 0
225M –
112,5 *
A1 11/2 0 0 ¼ 0 1 -1/4 0 165
165 : 5,5
= 30
A3 -2 0 0 1/3 -1 0 -1/3 1 60 *
X2 ½ 1 0 -1/12
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 11
METODE GRAFIK
Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan
dimana hanya terdapat dua variabel keputusan. Untuk menyelesaikan
permasalahan tersebut, langkah pertama yang harus dilakukan adalah
memformulasikan permasalahan yang ada ke dalam bentuk Linear Programming
(LP).
Contoh :
Perusahaan Krisna Furniture yang akan membuat meja dan kursi.
Keuntungan yang diperoleh dari satu unit meja adalah $7,- sedang keuntungan
yang diperoleh dari satu unit kursi adalah $5,-.
Namun untuk meraih keuntungan tersebut Krisna Furniture menghadapi
kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4
jam kerja. Untuk pembuatan 1 unit kursi dia membutuhkan 3 jam kerja. Untuk
pengecatan 1 unit meja dibutuhkan 2 jam kerja, dan untuk pengecatan 1 unit kursi
dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk pembuatan meja
dan kursi adalah 240 jam per minggu sedang jumlah jam kerja untuk pengecatan
adalah 100 jam per minggu. Berapa jumlah meja dan kursi yang sebaiknya
diproduksi agar keuntungan perusahaan maksimum?
Dari kasus di atas dapat diketahui bahwa tujuan perusahaan adalah
memaksimumkan profit. Sedangkan kendala perusahaan tersebut adalah
terbatasnya waktu yang tersedia untuk pembuatan dan pengecatan. Apabila
permasalahan tersebut diringkas dalam satu tabel akan tampak sebagai berikut:
Jam kerja untuk membuat 1 unit
produk
Total waktu
tersedia per
minggu Meja Kursi
Pembuatan 4 2 240
Pengecatan 2 1 100
Profit per Unit 7 5
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 12
Mengingat produk yang akan dihasilkan adalah meja dan kursi, maka
dalam rangka memaksimumkan profit, perusahaan harus memutuskan berapa
jumlah meja dan kursi yang sebaiknya diproduksi. Dengan demikian dalam kasus
ini, yang merupakan variabel keputusan adalah meja (X1) dan kursi (X2).
1. Fungsi Tujuan
Profit = ($ 7 x jml meja yang diproduksi) + ($ 5 x jml kursi yang diproduksi)
Secara matematis dapat ditulis :
Maksimisasi : Z = 7 X1 + 5 X2
2. Fungsi Kendala
• Kendala : Waktu pembuatan
1 unit meja memerlukan 4 jam untuk pembuatan -> 4 X1
1 unit kursi memerlukan 3 jam untuk pembuatan -> 3 X2
Total waktu yang tersedia per minggu untuk pembuatan -> 240 Jam
Dirumuskan dalam pertidaksamaan matematis -> 4 X1 + 3 X2 ≤≤≤≤ 240
• Kendala : Waktu pengecatan
1 unit meja memerlukan 2 jam untuk pengecatan -> 2 X1
1 unit kursi memerlukan 1 jam untuk pengecatan -> X2
Total waktu yang tersedia per minggu untuk pengecatan -> 100 Jam
Dirumuskan dalam pertidaksamaan matematis -> 2 X1 + X2 ≤≤≤≤ 100
Formulasi masalah secara lengkap :
Fungsi Tujuan : Maks. Z = 7 X1 + 5 X2
Fungsi Kendala : 4 X1 + 3 X2 ≤ 240
2 X1 + X2 ≤ 100
X1 , X2 ≥ 0 (kendala non-negatif)
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 13
Setelah formulasi lengkapnya dibuat, maka Kasus Krisna Furniture
tersebut akan diselesaikan dengan metode grafik. Keterbatasan metode grafik
adalah bahwa hanya tersedia dua sumbu koordinat, sehingga tidak bisa digunakan
untuk menyelesaikan kasus yang lebih dari dua variabel keputusan.
Langkah pertama dalam penyelesaian dengan metode grafik adalah
menggambarkan fungsi kendalanya. Untuk menggambarkan kendala pertama
secara grafik, kita harus merubah tanda pertidaksamaan menjadi tanda persamaan
seperti berikut.
4 X1 + 3 X2 = 240
Untuk menggambarkan fungsi linear, maka cari titik potong garis tersebut
dengan kedua sumbu. Suatu garis akan memotong salah satu sumbu apabila nilai
variabel yang lain sama dengan nol. Dengan demikian kendala pertama akan
memotong X1, pada saat X2 = 0, demikian juga kendala ini akan memotong X2,
pada saat X1 = 0.
Kendala I :
4 X1 + 3 X2 = 240
memotong sumbu X1 pada saat X2 = 0
4 X1 + 0 = 240
X1 = 240 / 4
X1 = 60.
memotong sumbu X2 pada saat X1 = 0
0 + 3 X2 = 240
X2 = 240/3
X2 = 80
Kendala I memotong sumbu X1 pada titik (60, 0) dan memotong sumbu X2
pada titik (0, 80).
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 14
Kendala II :
2 X1 + 1 X2 = 100
memotong sumbu X1 pada saat X2 = 0
2 X1 + 0 = 100
X1 = 100/2
X1 = 50
memotong sumbu X2 pada saat X1 =0
0 + X2 = 100
X2 = 100
Kendala I memotong sumbu X1 pada titik (50, 0) dan memotong sumbu X2
pada titik (0, 100).
Titik potong kedua kendala bisa dicari dengan cara substitusi atau eliminasi
2 X1 + 1 X2 = 100 -> X2 = 100 - 2 X1
4 X1 + 3 X2 = 240 X2 = 100 - 2 X1
4 X1 + 3 (100 - 2 X1) = 240 X2 = 100 - 2 * 30
4 X1 + 300 - 6 X1 = 240 X2 = 100 - 60
- 2 X1 = 240 - 300 X2 = 40
- 2 X1 = - 60
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 15
X1 = -60/-2 = 30.
Sehingga kedua kendala akan saling berpotongan pada titik (30, 40).
Tanda ≤ pada kedua kendala ditunjukkan pada area sebelah kiri dari garis
kendala. Feasible region (area layak) meliputi daerah sebelah kiri dari titik A (0;
80), B (30; 40), dan C (60; 0).
Untuk menentukan solusi yang optimal, ada dua cara yang bisa digunakan
yaitu
1. dengan menggunakan garis profit (iso profit line)
2. dengan titik sudut (corner point)
Penyelesaian dengan menggunakan garis profit adalah penyelesaian
dengan menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser
ke kanan sampai menyinggung titik terjauh dari dari titik nol, tetapi masih berada
pada area layak (feasible region). Untuk menggambarkan garis profit, kita
mengganti nilai Z dengan sembarang nilai yang mudah dibagi oleh koefisien pada
fungsi profit. Pada kasus ini angka yang mudah dibagi angka 7 (koefisien X1) dan
5 (koefisien X2) adalah 35. Sehingga fungsi tujuan menjadi 35 = 7 X1 + 5 X2.
Garis ini akan memotong sumbu X1 pada titik (5, 0) dan memotong sumbu X2
pada titik (0, 7).
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 16
Iso profit line menyinggung titik B yang merupakan titik terjauh dari titik
nol. Titik B ini merupakan titik optimal. Untuk mengetahui berapa nilai X1 dan
X2, serta nilai Z pada titik B tersebut, kita mencari titik potong antara kendala I
dan kendala II (karena titik B merupakan perpotongan antara kendala I dan
kendala II). Dengan menggunakan eliminiasi atau subustitusi diperoleh nilai X1 =
30, X2 = 40. dan Z = 410. Dari hasil perhitungan tersebut maka dapat disimpulkan
bahwa keputusan perusahaan yang akan memberikan profit maksimal adalah
memproduksi X1 sebanyak 30 unit, X2 sebanyak 40 unit dan perusahaan akan
memperoleh profit sebesar 410.
Penyelesaian dengan menggunakan titik sudut (corner point) artinya kita
harus mencari nilai tertinggi dari titik-titik yang berada pada area layak (feasible
region). Dari peraga 1, dapat dilihat bahwa ada 4 titik yang membatasi area layak,
yaitu titik 0 (0, 0), A (0, 80), B (30, 40), dan C (50, 0).
Keuntungan pada titik O (0, 0) adalah (7 x 0) + (5 x 0) = 0.
Keuntungan pada titik A (0; 80) adalah (7 x 0) + (5 x 80) = 400.
Keuntungan pada titik B (30; 40) adalah (7 x 30) + (5 x 40) = 410.
Keuntungan pada titik C (50; 0) adalah (7 x 50) + (5 x 0) = 350.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 17
Karena keuntungan tertinggi jatuh pada titik B, maka sebaiknya
perusahaan memproduksi meja sebanyak 30 unit dan kursi sebanyak 40 unit, dan
perusahaan memperoleh keuntungan optimal sebesar 410.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 18
LINEAR PROGRAMMING
SEJARAH
Linear Programming pertama kali dicetuskan oleh seorang ahli
matematika asal Rusia bernama L.V. Kantorivich dalam bukunya yang berjudul
”MATHEMATICAL METHODS IN THE ORGANIZATION AND PLANNING
OF PRODUCTION”. Dengan buku ini, ia telah merumuskan pertama kalinya
persoalan “Linear Programming”. Namun, cara-cara pemecahan persoalan in di
Rusia tidak berkembang dengan baik dan ternyata para ahli di negara Barat dan
AS yang menggunakan cara ini dimanfaatkan dengan baik.
Pada tahun 1947, seorang ahli matematika dari AS yang bernama George
B. Dantzig menemukan suatu cara untuk memecahkan persoalan-persoalan linear
programming. Cara pemecahan ini dinamakan ” Simplex Method”, yang diuraikan
dalam bukunya ”LINEAR PROGRAMMING AND EXTENTION”.
LINEAR PROGRAMMING (LP)
Linear programming adalah teknik matematika yang dirancang untuk
membantu dalam merencanakan dan membuat keputusan.
Linear Programming memiliki empat ciri khusus, yaitu :
1. Penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau
minimisasi.
2. Kendala yang ada membatasi tingkat pencapaian tujuan
3. Ada beberapa alternatif penyelesaian
4. Hubungan matematis bersifat linier
Untuk membentuk suatu model linear programming perlu diterapkan
asumsi-asumsi dasar, yaitu :
1. Linearity
Fungsi obyektif dan kendala haruslah merupakan fungsi linier dan variabel
keputusan. Hal ini akan mengakibatkan fungsi bersifat proporsional dan
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 19
additif, misalnya untuk memproduksi 1 kursi dibutuhkan waktu 5 jam, maka
untuk memproduksi 2 kursi dibutuhkan waktu 10 jam.
2. Divisibility
Nilai variabel keputusan dapat berupa bilangan pecahan. Apabila diinginkan
solusi berupa bilangan bulat (integer), aka harus digunakan metoda untuk
integer programming.
3. Non negativity variable
Nilai variabel keputusan haruslah tidak negatif ( ≥ 0)
4. Certainty
Semua konstanta (parameter) diasumsikan mempunyai nilai yang pasti. Bila
nilai-nilai parameternya probabilistik, maka harus digunakan formulasi
pemrograman masalah stokastik.
� Contoh soal
Ibu Angel membuat dua macam jenis, kue nastar dan putrie salju. Bahan baku
gula dan tepung untuk memproduksi 3 ons kue nastar diperlukan 2 bagian gula
dan 4 bagian tepung, kemudian untuk memproduksi 3 ons kue putrie salju
diperlukan satu bagian gula dan 3 bagian tepung, untuk gula tersedia tersedia 250
dan tepung 200. 1 ons kue nastar dihargai Rp.10.000,00 dan putrie salju
Rp.15.000,00?
� Jawab:
Pada kasus ini saya akan menggunakan metode linier Programing, hal ini
dikarenakan pada kasus ini pertidaksamaan pembatasnya menggunakan ≤ (kurang
dari sama dengan).
Bagi kendala pertidaksamaan jenis ≤, maka variabel slack ditambahkan untuk
menghabiskan sumber daya yang digunakan dalam kendala.
Z= 10000x1 + 15000x2
2x1 + x2 ≤ 250
4x1 + 3x2 ≤ 200
10000x1 + 15000x2 + X3 + X4
2x1 + x2 + x3 = 250
4x1 + 2x2 + x4 = 200
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 20
1. X1 = X2 = 0
X3 = 250, X4 = 200
Z1=10000(0)+15000(0)+250(0)+200(0)=
0
2. X1 = X3 = 0
X2= 250
2x2 + X4= 200, 2(250) + X4
= 200
500 + X4 = 200
X4 = -300
Z2 ≠ (tidak dihitung)
3. X1 = X4 = 0
2X2 = 200, X2= 100
X2 + X3= 250, 200 + X3= 250
X3= 50
Z3=10000(0) + 15000(100) + 0(50) +
0(0)
=1.500.000
4. X2 = X3 = 0
2X1 = 250, X1 = 125
4X1 + X4 = 200
4(125) + X4 = 200
500 + X4 = 200
X4= -300
Z4 ≠ (tidak dihitung)
5. X2 = X4 = 0
4X1= 200
X1= 50
2X1 + X3= 250
2(50) + X3= 250
X3= 150
Z5= 10000(50) + 15000(0) + 0(150) +
0(0)
=100000
6. X3 = X4 = 0
2X1 + X2= 250,
X1= ½ (250-X2 + 2X2=
200
125-1/2X2 + 2X2= 200
125 + 3/2X2= 200
3/2X2= 200 - 125
3/2X2= 125
X2= 125 . 2/3
= 83 1/3
X1= ½ (250=83 1/3)
= ½ (166 2/3)
= 83 1/3
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 21
� KESIMPULAN:
Jadi diantara pemecahan fisibel ada satu nilai Z yang terbesar aitu Z6= 1.500.000
dengan kesimpulan:
� X1= 83 1/3 , produk A diproduksi 83 1/3 unit.
� X2= 83 1/3 , produk B diproduksi 83 1/3 unit.
� X3= 50 , bahan baku pertama dipakai 50 dari dalam proses produksi.
� X4= 0 , bahan baku kedua habis dipakai dalam proses produksi.
� Contoh Soal:
Perusahaan industri PT MULIA menghasilkan dua jenis produk yaitu
P1 dan P2 masing-masing memerlukan dua macam bahan baku, A dan
B. Harga jual tiap satuan P1 sebesar Rp 150,- dan P2 sebesar Rp 100,-.
Bahan baku A yang tersedia sebanyak 600 satuan dan B 1.000 satuan.
Satu satuan P1memerlukan satu satuan A dan dua satuan B, sedangkan
satuan P2 memerlukan satu satuan A dan satu satuan B.
Contoh Tabel sebagai berikut :
Produksi
Bahan
Jenis Produksi Bahan Yang
Tersedia P1 P2
A 1 1 600
B 2 1 1000
Harga Jual 150 100
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 22
Masalahnya adalah menentukan alokasi bahan A dan B sebanyak
mungkin, atau dengan kata lain dengan menentukan jumlah produksi P1 dan P2
Sehingga mencapai tujuan perusahaan yaitu meraih keuntungan semaksimal
mungkin. Meskipun Tabel Diatas sudah menggambarkan situasi Produksi dalam
masalah yang dihadapai akan tetapi penentuan jumlah produksi P1 dan P2 masih
sulit. Oleh itu kita akan menerjemahkan masalah ini kedalam model matematika
dengan rumusan yang sederhana Sehingga mudah dicari penyelesaianya.
Misalkan Jumlah Produk jenis produk P1 dan P2 adalah penjualan satuan X1
dan X2 satuan. Maka hasil tentu saja sama dengan : F = 150 X1 dan 100 X2
Tujuan PT mulia ialah mengusahakan F sebesar-besarnya sehingga
keuntungan juga akan maksimal. Karena untuk menghasilkan satu satuan P1
diperlukan satu satuan bahan A dan dua satuan bahan B, maka untuk sejumlah X1
satuan jenis P1 diperlukan sejumlah X1 satuan bahan A dan sejumlah 2x1 satuan
bahan B. Dengan cara yang sama untik menghasilkan sejumlah X2 satuan jenis P2
diperlukan sejumlah X2 satuan bahan A dan sejumlah X2 satuan bahan B. Dengan
demikian jumlah bahan A yang diperlukan untuk menghasilkan sejumlah X1
satuan P1 dan sejumlah X2 satuan P2 adalah (X1 + X2) satuan. Bahan B yang
diperlukan ialah (2x2 + x2) satuan.
Karena bahan A dan bahan B masing-masing hanya tersedia 600 dan 1000
satuan, maha (X1 + X2) dan (2x2 + x2) masing-masing tidak mungkin melebihi 600
dan 1000 satuan. Pernyataan tersebut dapat ditulis dengan bentuk :
(X1 + X2 ) ≤ 600 dan (2x2 + x2) ≤ 1000
Atau
X1 + X2 - ≤600
2x2 + x2 - ≤ 1000
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 23
Kalau semua keterangan ini dikumpulkan, maka akan sampai kepada satu
bentuk model matematika yang menggambarkan masalah produksi yang sedang
dihadapi PT MULIA, yaitu :
F = 150 x1 + 100 x2
G = X1 + X2 - 600
H = 2x2 + x2 – 1000
Tujuan dari model ini adalah menentukan jumlah produksi P1 (=X1) dan
jumlah produksi P2 (=X2) sehingga hasil jumlah penjualan F = 150 x1 + 100 x2
maksimal sesuai dengan keterbatasan yang ada.
Sacara simgkat dapat ditulis : tentukan X1 dan X2 yang memenuhi batasan
F = 150 x1 + 100 x2
X1 + X2 ≤ 600
2x2 + x2 ≤1000
X1 ≥ 0
X2 ≥ 0
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 24
METODE TRANSPORTASI
Metode transportasi merupakan metode yang digunakan untuk
mengaturdistribusi dari sumber-sumber yang menyediakan produk, ketempat yang
membutuhkan secara optimal. Alokasi produk ini harus diatur sedemikaian rupa,
karene terdapat perbedaan biaya-biaya alokasi dari suatu sumber ke suatu tempat
tujuan yang berbeda-beda, dan dari suatu sumber ke suatu tempat yang berbeda-
beda juga.
Metode Stepping Stone
� Contoh Soal :
Suatu perusahaan mempunyai 3 buah pabrik di W,H dan P. Perusahaan
mengalami masalah alokasi hasil produksinyake gudang-gudang penjualan di A,B
dan C. Kapasitas pabrik , kebutuhan gudang dan biaya pengangkutan dari tiap
pabrik kegudang adalah sebagai berikut :
Pabrik Kapasitas produksi tiap bulan
W 90 ton
H 60 ton
P 50 ton
Jumlah 200 ton
Gudang Kapasitas produksi tiap bulan
A 50 ton
B 110 ton
C 50 ton
Jumlah 40 ton
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 25
Dari
Biaya tiap ton ( Dalam Ribuan Rp. )
Gudang A Gudang B Gudang C
Pabrik W 20 5 8
Pabrik H 15 20 10
Pabrik P 25 10 9
� Penyusunan Tabel Alokasin :
Ke
Dari
Gudang
A
Gudang
B
Gudang
C
Kapasitas
Pabrik
Pabrik
W
20
X11
5
X12
8
X13 90
Pabrik
P
15
X21
20
X22
10
X23 60
Pabrik
H
25
X31
10
X32
19
X33 50
Kebutuhan
Gudang 50 110 40 200
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 26
Prosedur Alokasi
Setelah data tersusun dalam tabel maka langkah selanjutnya adalah
mengalokasikan produk dari pabrik-pabrik ke gudang-gudang. Pedoman yang
digunakan adalah pedoman sudut barat laut, Mulai dari sudut kiri atas dari table :
� Alokasi tahap pertama dengan pedoman sudut barat laut.
Ke
Dari
Gudang
A
Gudang
B
Gudang
C
Kapasitas
Pabrik
Pabrik
W
20
50
5
40
8
90
Pabrik
P
15
20
60
10
60
Pabrik
H
25
10
10
19
40 50
Kebutuhan
Gudang 50 110 40 200
Besarnya pengangkutan untuk alokasi tahap pertama
= 50 (20) + 40 (20) + 60 (20) + 10 (10) + 40 (19) = 3260
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 27
Mengubah Alokasi Secara Trial Dan Error
Terlihat pada kokom gudang A , sel SH belum terisi,maka diciba untuk diisi
satu satuan (ton). Tentu saja perlu memindahkan dari sel yang lain, misalnya dari
WA agar jumlah gudang tetap 50. Disamping itu juga mempengaruhi sel WB dan
HB.
Perubahan biaya yang diakibatkan adalah sebagai berikut :
� Tambahan biaya Dari H ke A = 15
Dari W ke B = 5 +
Jumlah = 20
� Pengurangan biaya Dari H ke A = 20
Dari W ke B = 20 +
Jumlah = 40
Tambahan 20 dan pengurangan 40 berarti penghematan 20 untuk pemindahan
1 unit ke sel HA dan WB dari WA dan HB. Berdasarkan kenyataan ini, bila
jumlah alokasi yang dipindah lebih banyak maka penghematan tentunya akan
lebih banyak juga.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 28
� Perbaikan pertama dengan trial dan error
Ke
Dari
Gudang
A
Gudang
B
Gudang
C
Kapasitas
Pabrik
Pabrik
W
20
50 (-)
5
40(+)
8
90
Pabrik
P
15
(+)
20
60 (-)
10
60
Pabrik
H
25
10
10
19
40 50
Kebutuhan
Gudang 50 110 40 200
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 29
� Perbaikan kedua dengan trial dan error
Ke
Dari
Gudang
A
Gudang
B
Gudang
C
Kapasitas
Pabrik
Pabrik
W
20
5
90
8
90
Pabrik
P
15
50
20
10
10
60
Pabrik
H
25
10
10
19
40 50
Kebutuhan
Gudang 50 110 40 200
Perubahan alokasi ini dapat juga dilaakukan dengan mengubah alokasi
pada sel yang tidak berdekatan. Misalnya alan diisi sel WC maka sel yang lain
yang ikut berubah dapat berupa sel WB, PB dan PC. Seperti pada table transport =
50 (5) + 40 (8) + 50 (15) + 10 (20) + 50 (10) = 2020.
Demikian seterusnya diadakan perubahan , bila dengan peruhaban itu
dapat mengurangi biaya. Sampai akhirnya diperoleh biaya transport yang terendah
(optimal).
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 30
� Perbaikan dengan alokasi sel yang berdekatan.
Ke
Dari
Gudang
A
Gudang
B
Gudang
C
Kapasitas
Pabrik
Pabrik
W
20
5
50
8
40 90
Pabrik
P
15
50
20
10
10
60
Pabrik
H
25
10
50
19
50
Kebutuhan
Gudang 50 110 40 200
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 31
PENUTUP
Kesimpulan
Riset operasi adalah metode untuk memformulasikan dan merumuskan
permasalahan sehari-hari mengenai bisnis,ekonomi,sosial maupun bidang lainya
dalam pemodelan matematis untuk mendapatkan solusi yang optimal.
Demikian kilasan tentang Riset operasi , kami sadar bahwa perjuangan
kami masih panjang dan masih banyak hal yang perlu diperjuangkan terus agar
generasi bangsa Indonesia menjadi generasi yang unggul.
Rangkuman Riset Operasi oleh Feri Tulistiyono (UNSIQ) NIM 8209018 32
Daftar Pustaka
1.Bambang Yuwono, Bahan kuliah Riset Operasi,2007
2. Pangestu dkk, Dasar-Dasar Riset Operasi, BPFE, 1783, Yogyakarta
3. Hamdy Taha, Operation Research An Introduction, Edisi 4, Macmillan, New
York
4. Aminnudin, Prinsip-Prinsip Riset Operasi, Erlangga, 2005
top related