RPKPS & BAHAN AJAR
MATA KULIAH TPT2007 RISET OPERASI
oleh Ir. Tn Purwadi, M.Eng.
JURUSAN TEKNIK PERTANIAN FAKULTAS TEKNOLOGI PERTANIAN UNIVERSITAS GADJAH MADA
Format RPKPS 1. Nama Mata Kuliah
:
Riset Operasi
2. Kode/SKS
:
TPT2007/2
3. Program Studi
:
Teknik Pertanian
4. Prasyarat
:
-
5. Status
:
wajib
6. Deskripsi Singkat
:
Mata kuliah riset operasi terutama mempelajari teknik pengambilan keputusan untuk mencapai hasil yang optimum. Mata kuliah ini diajarkan pada semester 4 dan bersifat wajib. Dalam beban studi 2 SKS, materi yang diberikan dalam mata kuliah mi meliputi : pengertian riset operasi (operations research), model program linier (linear programming model), aplikasi program linier, model transportasi (transportation model), analisis jaringan (network analysis) termasuk CPM dan PERT.
7. Tujuan Pembelajaran
:
Membimbing mahasiswa memahami dan rnnguasai beberapa teknik pengambilan keputusan menurut ilmu riset operasi (operations research) dan aplikasinya dalam bidang teknik pertanian.
8. Outcome/Kompetensi : Pembelajaran
Mahasiswa mampu mentransfer masalah sehari-hari di bidang teknik pertanian yang meliputi masalah alokasi sumber daya yang terbatas, masalah trasnportasi dan masalah penjadwalan ke dalam suatu bentuk model matematik
kemudian
dan
model
tersebut
dapat
dilakukan analisis untuk meneroleh solusi yang optimal.
Universitas Gadjah Mada
10. Evaluasi. Nilai mata kuliah ditentukan atas dasar nilai yang diperoleh dari: 1. Ujian sisipan semester 2. Tugas/pekerjaan rumah 3. Ujian akhir semester dengan bobot sbb:
(3 x sisipan ) + (2x PR) + (5 x akhir) 10
11. Bahan Acuan 1. Hillier, Frederick S. and Lieberman, Gerald J. Operations Reserach, Holden-Day, Inc. San Francisco, Second Ed., 1973 2. Miller, David M., and Schmidt, J.W. Indutrial Engineering and Operations Research,
Universitas Gadjah Mada
PENDAHULUAN Riset Operasional (Operation Research) kadang-kadang juga disebut sebagai management science atau System An/ysis. Riset Operasional adalah suatu teknik pengambilan keputusan untuk memecahkan masalah praktis dalam suatu sistem yang diarahkan pada pencapaian solusi yang optimum. Teknik
pengambilan
keputusan
praktis
itu
dilakukan
dengan
melakukan
riset/pengamatan terhadap keterkaitan setiap komponen dan operasi dan sistem tersebut kemudian diabtraksikan dalam bentuk model. Dan model itu kemudian dapat dilakukan analisis dengan teknik komputasi atau simulasi sehingga diperoleh solusi yang optimal. Oleh karena itu Operations Research sering disebut juga sebagai Research on Operations. Berdasarkan model pemecahan masalah kita kenal beberapa teknik pengambilan keputusan dalam operations research yaitu Linear programming, Transportation problem, Network modeling, Dynamic programming, Inventory theory, Queuing theory, Markov process, dan Time series fortcasting
LINEAR PROGRAMMING Linear programming (LP) merupakan teknik pengambilan keputusan dalam masalah alokasi sumber daya yang terbatas yang secara bersamaan diperlukan oleh beberapa aktivitas sedemikian rupa sehingga akan memperoleh hasil yang optimum terbaik. Pemecahan
masalah
dengan
Linear
Programming
dilakukan
dengan
cara
mengabtraksikan masalah tersebut kedalam bentuk model mathematik. Kata linear dan LP memberikan pengertian bahwa fungsi mathematik dalam model tersebut semua dalam bentuk fungsi linear.
Contoh Kasus Linear Programming ”Windor GlassCo”, merupakan suatu perusahaan kaca yang memproduksi kusen alumunium dan kusen kayu dengan berbagai ukuran. Untuk menghasilkan produk itu diperlukan 3 macam bengkel. Bengkel-1 untuk pembuatan kerangka alumunium, bengkel 2 untuk pembuatan kerangka kayu, dan bengkel - 3 untuk penyetelan dan pemasangan kaca pada kerangka kusen. Karena menghadapi masalah pemasaran, perusahaan itu terpaksa menghentikan pembuatan beberapa produk yang kurang laku, narnun akibatnya 3 bengkel yang dimilikinya mempunyai kelebiahan kapasitas kerja. Untuk memanfaatkan kelebihan kapasitas kerja itu, perusahaan akan memproduksi 2 macam produk yang sangat laku di pasaran yaitu kusen alumunium ukuran 2 x 3
Universitas Gadjah Mada
meter,, dan kusen kayu ukuran 2 x 3 m. Karena kedua produk itu sam sama-sama dikerjakan pada bengkel - 3 masalahnya adalah menentukan berapa unit masing masingmasing produk itu harus dibuat agar bengkel tersebut dapat dimanfaatkan dengan hash yang paling baik. Untuk memecahkan memecahkan masalah itu pihak manajemen menugaskan pada tim OR untuk menyelesaikaimya. Setelah mengamati setiap komponen dan operasi dan perusahaan itu. Tim OR menentukan untuk meneliti : 1) kelebihan kapasitas kerja dan masing masing bengkel, 2) penggunaan kapasitas pasitas kerja dan masing-masing masing produk, 3) unit keuntungan dan masing-masing masing masing produk. Hasil pengamatan ditabulasikan sebagai berikut:
Formulasi Model Mathrmatik Misalkan X1 dan X2 berturut-turut berturut adalah unit produk-1 dan produk-2 2 yang akan diproduksi tiap hari, dan Z adalah total keuntungan tiap hari yang akan diperoleh dari penjualan 2 macam produk tersebut, maka secara mathematik dapat dirumuskan bahwa: Z=3X1+5X2 Dengan Z
= total keuntungan euntungan yang diperoleh (Rp/hari) (Rp/har
X1 = laju produksi produk-1(unit/har 1(unit/hari) X2 = laju produksi produk-2 2 (unit/hari (unit/hari) X1 dan X2 merupakan variabel keputusan dari model dan sasarannya adalah menentukan berapa nilai X1 dan X2 agar Z = 3 x 1 + 5 x 2,, mencapai nilai yang rnaksirnum namun tidak melampa melampaui kendala keterbatasan kapasitas bengkel engkel yang tersedia. Dari tabel di atas menunjukkan bahwa b pembuatan setiap unit produk-1 1 tiap han membutuhkan 1 jam kapasitas kerja bengkel-1 1 secara matematik dapat dirurnuskan
bahwa X1<= 4, dengan cara yang sama bentuk mathematik kendala untuk bengkel-2 adalah 2 X 2 <= 12, dan kendala untuk bengkel-3 adalah : 3 X1 + 2 X2 <= 18, dan karena laju produksi tidak mungkin negative maka X1
0 dan X2
.
Dalam bahasa mathematik, penyelesaian masalah tersebut dengan teknik LP adalah menentukan berapa besarnya nilai X1 dan X2 untuk: Memaksimumkan
:
Z=3X1+5X2
Dengan kendala
:
X1
<= 4
2 X2
<= 12
3 X1 + 2 X 2 <= 18 dan
X1
0, X2
0
Komputasi Linear Programming Metode Grafik Setelah selesai menyusun model mathematik dan masalah yang akan dipecahkan, langkah selanjutnya adalah menghitung berapa besarnya nilai variabel keputusan agar fungsi objectif mencapai nilai yang optimum. Contoh kasus “Wyndor Glass Co” merupakan model LP yang sangat kecil, kasus itu hanya terdiri dari 2 variabel keputusan. Untuk kasus seperti itu dapat dipecahkan dengan metode grafik, yaitu dengan cara menggambarkan dalam grafik 2 dimensi dengan absis sebagai sumbu X1 dan ordinat sebagai sumbu X2. Metode Simplex Metode simplex merupakan metode yang sangat efisien dan prosedur yang paling digunakan untuk komputasi linear programming. Prinsip dari Metode Simplex komputasi simultan untuk menghitung besarnya multi variabel yang akan oleh Gaus Yordan.
Universitas Gadjah Mada
Prosedur Komputasi Metode Simplex 1. Memasukkan slack vanabel untuk merubah bentuk fungsi kendala dan bentuk (<) menjadi ( = ) Mak : Z = 3X1 + 5X2
Mak : Z – 3X1 – 3X2
Kendala :
Kendala :
=0
X1
<= 4
X1 + X3
=4
2X2
<= 12
2X2 + X4
= 12
3X1 + 2X2
<= 18
3X1 + 2X2 + X5
= 18
X1, X2
>= 0
X1, X2, X3, X4, X5
>= 0
X3, X4 dan X5 adalah slack variable 2. Penyusunan dalam bentuk tabel awal simplex
X3, X4, dan X5 adalah disebut diseb variabel abel dasar besamya sama dengan harga pada kolom nilai, sedangkan X1 dan X2 disebut variabel non dasar dan nilainya nya = 0 Solusi awal: X1 =0, X2 =0, X3 =4, X4 = 12, X5 = 18 dan fungsi objectif Z = 0 Kesimpulan : belum optimal
3. Mulai Komputasi Menentukan variabel non dasar yang akan menjadi variabel dasar yang baru, dan menentukan variabel dasar yang yang akan digantikan oleh variabel dasar yang baru masuk
Persamaan IV bentuk simplek tidak memiliki slack variabel yang akan dimasukkan sebagai initial basic variabel dalam tabel dalam tabel awal. OIeh karena itu diperlukan tambahan variabel baru yang disebut disebut artificial variabel, sehingga persamaan IV menjadi 3 X1 + 2 X2 + X5 = 18 Dengan syarat bahwa pada solusi akhir nilai dari X5 harus 0
Solusi awal : X3
=4
X4
= 12
X5
= 18
X1, X2
=0
Fungsi objectif : Z = 0
Metode Big M Tabel itu bila dilanjutkan dengan iterasi tidak menjamin bahwa pada akhir solusi akan menghasilkan X5 = 0, untuk mengatasi itu maka digunakan Metode Big M, Fungsi objektifsekarang diubah menjadi: Z = 3X1 + 5X2 – M –X5 M : suatu bilangan yang relative sangat besar
Fungsi oblektif tersebut akan mencapai nilai yang maksimumkan bila X5 = 0 Untuk menyusun tabel simplex bentuk fungsi objectif diubah bentuknya menjadi Iterasi – 1
Hasil Iterasi – 1
Solusi : X1 =0, X2 = 6, X3 = 4, X4 = 0, X5 = 6 Fungsi obejctif Z = 30, Iterasi – 2
Hasil iterasi – 2
Kesimpulan : belum optimal
Solusi : X1 = 2, X2 = 6, X3 = 2, X4, X5 = 0 Fungsi objectif Z = 36,
Kesimpulan : telah mencapai optimal
Model Linear Programming Dalarn contoh kasus “Wyndor Glass Co”, terlihat bahwa dalam dalam model itu hanya terdiri dari 3 sumber daya yang dialokasikan terbatas (kapasitas bengkel) yang dimanfaatkan untuk 2 macam aktivitas (memproduksi produk-2 produk 2 dan produk produk-2). Seandainya suatu model mempunyai (m) sumber daya yang terbatas dan akan digunakan untuk melakukan (n) aktivitas aktivitas kemudian misalkan (c) adalah unit keuntungan tungan dan variabel keputusan Xj, Xj dan an (bi) adalah nilai kendala dari sumber daya ke-i,i, kemudian aij unit sumber daya ke ke-1 1 yang dipenlukan untuk aktivitas j, maka data itu dapat ditabulasikan sbb:
Dari tabel di tersebut kemudian data dibuat model mathematik sebagai berikut: Maksimumkan:
Z = Cl X1 + C2 X2 X + ………. + Cn Xn
Dengan kendala
A11 X1 + A12 X2 + ………….+ Am Xn <= Bi A2 1 X1 + X22 X2 + ………+ A2n Xn <= B2 Am1 X1 + Am2 X2 + ……. + AmnXn <= Bm X1,, X2 >= 0
Model seperti tersebut diatas disebut bentuk standard dan masalah linear programming. Setiap permasalahan yang model mathematiknya menghasilkan model seperti itu maka masalah tersebut diklasifikasikan dalam kelompok LP. Namun demikian tidak semua masalah LP P akan menghasilkan model mathematik dalam bentuk standar seperti diatas, misalnya: 1. Fungsi objectif bukan memaksimumkan tetapi justru meminimumkan 2. Fungsi kendala bukan (<=) tetapi ( = ) 3. Fungsi kendala bukan (<=) tetapi ( >= ) 4. Variabel keputusan belum pasti >= 0 tetapi mungkin negative atau positif
Model LP Dengan Fungsi Kendala ( = )
Persamaan IV bentuk simplek tidak memiliki slack variabel yang akan dimasukkan sebagai initial basic variabel dalam tabel dalam tabel awal. OIeh karena itu diperlukan tambahan an variabel baru yang disebut artificial variabel, sehingga persamaan IV menjadi 3 X1 + 2 X2 + X5 = 18 Dengan syarat bahwa pada solusi akhir nilai dari X5 harus 0
Solusi awal : X3
=4
X4
= 12
X5
= 18
X1, X2
=0
Fungsi objectif : Z = 0
Metode Big M Tabel itu bila dilanjutkan dengan iterasi tidak menjamin bahwa pada akhir solusi akan menghasilkan X5 = 0, untuk mengatasi itu maka digunakan Metode Big M, Fungsi objektifsekarang diubah menjadi: Z = 3X1 + 5X2 – M –X5 M : suatu bilangan yang relative sangat besar Fungsi oblektif tersebut akan mencapai nilai yang maksimumkan bila X5 = 0 Untuk menyusun tabel simplex bentuk fungsi objectif diubah bentuknya menjadi Z–3
X1 – 5 X2 + M X5 = 0
Sehingga dihasilkan table awal sbb :
Solusi Awal : X1 = 0, X2 = 0, X3 = 4, X4 = 12X dan X5 = 18 Fungsi objecyif Z = ( 3 ) ( 0 ) + ( 5 ) ( 0 ) + ( 0 ) ( 4 ) + ( 0 ) ( 12 ) – ( M ) ( 18 ) solusi itu tidak fisibel karena seharusnya Z = 0 Pers. I perlu dimodifikasi dengan cara sebagai berikut : I
Z – 3X1 5 – X2 + 0 X3 + 0 X4 + M X5
=0
III
3 X1 + 2 X2 + X5
= 18
I
Z – 3 X1 – 5 X2 + 0 X3 + 0 X3 + 0 X4 + MX5
=0
IIIxM
3M X1 + 2M X2 + M X5
= 18 M
Z – (3M + 3) X1 – (2M + 5) X2 + 0 X3 + 0 X4 + 0X5
= - 18 M
Masukkan kembali kedalam table simplex diperoleh hasil sebagai berikut berikut :
Solusi awal: X1 = 0,X2 = 0,X3 = 4, X4 = 12, X5 = 18,Z = - 18 M Interasi - 1
Hasil Interasi - 1
Solusi ; X1 = 4, X2 = 0, X3 = 0, X4 = 12, X5 = 6, Fungsi objectif Z = -6M + 12, belum optimal Interasi – 2
Hasil Interasi – 2
Solusi ; X1 = 4, X2 = 3, X3 = 0, X4 = 6, X5 = 0, Fungsi objektif Z = 27, belum optimal
Model Linear programming dengan kendala (>=) Contoh: Z mak = 3 X 1 + 5 X 2 X1 <= 4 2 X 2 <= 12 3 X 1+ 2 X 2 >= 18 Kendala: 3 X1 + 2 X 2 >= 18 Dapat diubah dengan mengkalikan —1, sehingga menjadi: -3 X 1 – 2 X2 + X5= -18 kemudian masukkan slack variabel kedalam persamaan tersebut -3 X 1- 2 X2 + X5=- 18 dan akan menghasilkan tabel awal sbb:
Dari tabel awal itu akan menghasilkan solusi awal sebagai berikut: X1 = 0, X2 = 0, X3 = 4, X4 = 12, dan X5 = -18, fIingsi objektif Z = 0, Solusi yang dihasilkan tersebut tidak fisibel karena X5 = -18, 18, padahal seharusnya X5>=0 Seandainya persamaan tersebut dikalikan dengan -1, 1, maka akan berubah menjadi 3 X1 + 2 X2 X5 = 18, dan an akan menghasilkan tabel awal sebagai berikut: be kut:
Tabel abel tersebut tetap belurn dapat rnenghasilkan solusi yang fisibel karena koefisien variabel dasar untuk X5 nilainya ni - 1, padahal seharusnya + 1 Persarnaan : 3 X1 + 2 X2 - X5 = 18 dianggap sebagai kendala dengan tanda ( = ), kemudian dimasukkan variabel artificial X6, akan diperoleh: 3 X1 + 2 X2 - X5 + X6 = 18 dan menambahkan ahkan Big M dalam fungsi objektif Z = 3 X1 + 5 X2 - MX6 X5 disebut sebagai surplus variabel, va variabel ini tidak dak dimunculkan sebagai Basic variabel pada solusi awal. Untuk menyusun kedalam bentuk tabel awal diperlukan modifikasi dan fungsi objektif dengan cara sebagai berikut: I
Z – 3 X1 – 5 X2 + M X6
IV I
=0
3 X1 + 2 X2 - X5 + X6
= 18
Z – 3 X1 - 5 X2 + M X6
=0
IV x M 3MXI + 2 M X2- MX5 + M X6
= 18M
Z - (3M+3) X1 - (2M+5) (2M X2 + MX5
= -18M
Masukkan an dalam tabel simplex diperoleh hasil sebagai berikut: be Tabel Awal
Solusi awal : X1= 0, X2 = 0,X3 = 4, X4 = 12, X5 = 0,X6 18, Z= -18M dilakukan iterasi akan diperoleh hasil sebagai berikut: Minimasasi Minimumkan: Z = 3X1 + 5X2 Kendala
X1
=4
2X2
=12
3 X1 + 2 X2 >= 18 X1 X2 >= 0 X1,
Secara mathematik matik merninirnumkan merninirnumkan suatu fungsi sarna dengan rnernaksirnumkan harga negatif dari fungsi itu, sehingga: Minimurnkan Z = 3 X1 + 5 X2, sama dengan Maksimurnkan : -Z = -3 3 X1 X — 5 X2, dengan demikian model di atas dapat dirubah bentuknya menjadi: Maksimumkan : -Z = -3 3 X1 X —5 X2 Kendala
: X1
=4
2 X2 = 12 3 X1 + 2 X2 >= 18 X1, X2 >= Langkah selanjutnya adalah menyusun model tersebut kedalam bentuk tabel simplek, dengan lebih dahulu dilakukan modifikasi karena adanya kendala yang tidak standar atau ( >= ) dengan cara sebagai berikut: I III IV
-z
+3 X1+ 5 X2 + M X4 + M X6 2MX2 + M X4
=0 = 12 M
3 MX 1+ 2M X2 – M X5 + M X6 -Z - (3M - 3) X1 - (4M-5) (4M X2 + MX5
= 18 M = - 30 M
Interasi-1
Hasil Interasi - 1
Interasi-2
MODEL TRANSPORTASI Suatu Perusahaan perkebunan mempunyai 3 kebun dan 3 gudang pupuk yang lokasinya saling terpisah satu dengan lainnya. Masing-masing Masing masing kebun memerlukan pupuk 35 ton, 40 ton dan 40 ton. Sementara itu masing-masing masing masing gudang mempunyai stok pupuk 45 ton, 50 ton dan 20 ton. Karena lokasi yang berbeda biaya angkut tiap ton pupuk dan gudang ke kebun berbeda eda pula sesuai dengan jaraknya, yaitu sebagai berikut:
.
Namun un secara teknis waktu untuk iterasi dengan menggunakan metode simplex terhadap masalah tersebut sebetulnya terlalu panjang, ada metode lain yang lebih pendek waktu interasinya nya yaitu dengan menggunakan metode transportasi. Solusi awal metode transportasi Ada 3 cara: 1.
Metode North-west west corner
2.
Metode Vogel Approximatiom
3.
Metode Rusell’s Approximation
Solusi awal: Z = 25.5 + 20.20 + 10.10 + 40.8 + 20.20 = 1345 Modified Distribution Method (MODI) Untuk mendapatkan solusi yang optimum dan solusi awal yang diperoleh dan 3 cara tersebut di atas, diperlukan langkah iterasi dengan metode MODI Solusi awal : North-west west corner
NETWORK SCHEDULING Network adalah abstraksi dan pelaksanaan suatu proyek yang digambarkan dalam bentuk garis-garis garis yang menunjukkan hubungan antara satu kegiatan dengan kegiatan lainnya. Network scheduling merupakan teknik penjadwalan dengan sasaran agar proyek tersebut dapat terlaksana tepat kontrol dan tepat waktu. Ada dua metode dalam network scheduling yaitu CPM (Critical Path Method) dan PERT (Program Evaluation and Review Technique). Kedua metode di atas sering juga disebut dengan istilah CPS (Critical Path Scheduling) Langkah Membuat Network 1.
Menentukan daftar kegiatan (aktivitas), dan alokasi waktu
2.
Menentukan keterkaitan antar kegiatan
3.
Menyusun network ork atas dasar kedua informasi di atas
1.
Menentukan daftar kegiatan
Contoh Proyek Pembuatan Mesin Pertanian
3. Membuat network Setiap kegiatan digambarkan oleh sebuah garis panah yang pada pa setiap ujungnya diberi nomor. Contoh :
Network di atas menggarnbarkan bahwa aktivitas design mempunyai alokasi waktu 4 unit waktu dan dimulai dan titik 1, dan berakhir pada titik 2 2. Kadangkadang aktivitas design itu dapat pula disebut dengan aktivitas 1-2
Gambar di atas rnenunjukkan bahwa akhir kegiatan A merupakan awal kegiatan B dan keterkaitan antara kedua kegiatan itu ditulis dengan simbol A< B.
Network di atas menggambarkan bahwa akhir aktivitas B dan C baru dapat dimulai bila aktivitas A telah selesai, akhir aktivitas A merupakan awal dan aktivitas B dan C, keterkaitan itu ditulis dengan simbol A< B, C
Network di atas menggambarkan bahwa aktivitas L baru dapat dimulai setelah aktivitas J dan. K telah selesai, akhir aktivitas aktivitas J dan K merupakan awal dan aktivitas L, keterkaitan itu ditulis dengan simbol J< K, dan K< L
Network di atas menggambarkan aktivitas khayal, yaitu aktivitas dengan alokasi waktu 0 unit waktu, aktivits ini diperlukan pada kondisi sbb: Tiga aktivitas as dengan keterkaitan A < C dan B < C tidak boleh digambarkan dengan network sbb:
Network di atas salah karena dua aktivitas (A dan B) menggunakan titik awal dan titik akhir yang sama. Untuk mengatasi itu maka dapat digunakan aktivitas dummy seperti rti di bawah mi:
Atau
PERT PERT digunakan untuk menganalisis time scheduling proyek yang dialokasi waktunya bersifat stokastik yang distribusinya mengikuti pola beta distribution. Beta distribution : Batas bawah (optimistic estimate)
: (a)
Mode (most like estimate)
: (m)
Batas atas (pesimistic estimate)
: (b)
