Tugas 3 Riset Operasi Rute terpendek

Tugas 2 Riset operasi Teori antrian

Antrian adalah suatu kejadian yang biasa dalam kehidupan sehari–hari. Menunggu di depan loket untuk mendapatkan tiket kereta api atau tiket bioskop, pada pintu jalan tol, pada bank, pada kasir supermarket, dan situasi–situasi yang lain merupakan kejadian yang sering ditemui. Studi tentang antrian bukan merupakan hal yang baru.

Satu saluran satu tahap (Single Channel – Single Phase)

Single Channel berarti hanya ada satu jalur yang memasuki sistem pelayanan atau ada satu fasilitas pelayanan. Single Phase berarti hanya ada satu pelayanan.

MODEL ANTRIAN SATU SALURAN SATU TAHAP [M/M/1]

 Pada model ini kedatangan dan keberangkatan mengikuti distribusi Poisson dengan tingkat 1 dan µ , terdapat satu pelayan, kapasitas pelayanan dan sumber kedatangan tak terbatas.

Untuk menentukan operating characteristics atau ciri-ciri operasi, dapat dilakukan dengan mudah setelah diperoleh probabilitas n pengantri dalam sistem (P_n). Melalui penurunan matematik yang cukup panjang, dalam kondisi steady state dapat ditunjukkan bahwa P_n = (1 – R) R_n , dimana R = λ / µ ≤1 dan n = 0, 1, 2, ....

Contoh:

Penumpang kereta api datang pada sebuah loket mengikuti distribusi Poisson dengan tingkat rata-rata 20 per jam. Misalkan secara rata-rata setiap penumpang dilayani 2 menit dan waktu layanan mengiluti distribusi eksponensial. Setelah sistem dalam steady state, carilah: a) P4 ; b) L ; c) Lq ; d) W ; e) Wq ; f) P0 atau I ; g) Berapa probabilitas pengantri tidak mendapat tempat duduk jika kursi yang disediakan di depan loket hanya 3?

Jawab

 Tingkat kedatangan rata-rata λ = 20 per jam, dan tingkat pelayanan rata-rata µ = 30 per jam. Sehingga R = 2/3.

Multi Channel – Single Phase
Sistem Multi Channel – Single Phase terjadi kapan saja di mana ada dua atau lebih fasilitas pelayanan dialiri oleh antrian tunggal, sebagai contoh model ini adalah antrian pada teller sebuah bank.

MODEL ANTRIAN BANYAK SALURAN SATU TAHAP [ M/M/c]

Jika traffic intensity (R = 1/ µ ) mendekati satu, rata-rata waktu antri menjadi makin lama dan pengantri dapat menjadi frustasi. Dalam menghadapi kasus ini, dapat diatasi dengan menambah saluran pelayanan.

Contoh 

Karena beberapa alasan angkutan kereta api makin diminati. Misalkan kedatangan calon penumpang mengikuti distribusi Poisson dengan rata-rata 75 per jam. Misalkan lagi, waktu pelayanan mengikuti distribusi eksponensial negatif dengan rata-rata 2 menit. Jika dibuka 3 loket, setelah steady state tercapai carilah operating characteristicsnya.

Jawab 

Jika kepala stasiun ingin mengganti pelayan atau mengubah jumlah loket, maka operating characteristics yang baru perlu ditemukan untuk membantu mengevaluasi perubahan biaya pelayanan dan biaya menunggu. Dengan demikian, tingkat pelayanan yang diharapkan lebih menguntungkan dari segi biaya dapat diketahui.

sumber
https://masdwijanto.files.wordpress.com/2012/06/bab-8.pdf

Tugas 1 Riset operasi Metode simpleks

Metode simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah program linier yang didasarkan pada proses iterasi.

Prosedur Metode Simpleks

1. Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

2. Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

3. Membuat Table Simpleks Awal

4. Algoritma metode simpleks 

Program Linier : Bentuk Standar

1. Ruas kanan (RK) fungsi tujuan harus nol (0)

2. Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.

3. Fungsi kendala dengan tanda “£ ” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

4. Fungsi kendala dengan tanda “³ ” diubah ke bentuk “£ ” dengan cara mengalikan dengan –1, lalu diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1, karena bertanda negatip.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar

1. Ada tiga bentuk fungsi kendala:  £, ≥, dan =.

2. Konversi fungsi kendala bertanda £: menambahkan slack variable pada fungsi kendala tersebut.

3. Untuk kendala berbentuk ‘³’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.

4. Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.

5. Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala. 

CONTOH

Maksimum       

Z = 18X₁ + 36X₂

12X₁ + 6X₂ ≥ 36

4X₁ + 4X₂ ≤ 32

X₁ tak terbatas

X₂ ≥ 0

Dimana X₁ dan X₂ adalah tingkat produksi barang 1 dan barang untuk mengubah masalah ini ke dalam bentuk baku dengan semua variable non negatif, X_­1‘ –  X’’ harus menggantikan X₁ pada malasah dia atas menjadi :

Maksimumkan

Dengan syarat Z = 18X₁’ – 18X’’ + 36X_2­ + 0S₁ + 0S₂ – MA₁

                           12X₁ – 12X’’ + 6X₂ – S₁ + A₁  = 36

                            4X₁’ – 4X’’ +4X₂ + S₂ = 32

                            X₁’  X’’  X₂  ≥ 0

Penyelesaian

Solusi terhadap masalah ini ditunjukan pada tabel berikut,

Subsitusikan A₁ Fungsi tujuan :

12X₁’ – 12X’’ + 6X₂ – S_{1 ­}+ A₁ = 36

A₁ = 36 – 12X₁’ + 12X’’ – 6X₂ + S₁

Maka :

Z = 18X₁’ – 18X’’ + 0S₁ + 0S₂ – [M(36 – 12X₁’ + 12X’’ – 6X₂ + S₁)]

                                                            -36M + (12M)X₁’- (12M)X’’+ (6M)X₂ – S₁M)

Z = (18 + 12M)X₁’ – (18 - 12M)X₂’’ + (36 + 6M)X₂ – (M) S₁ – 36M

Persamaan Z dalam tabel :

Z – (18 - 12M)X₁’ + (18 + 12M)X’’ – (36 – 6M)X₂ + (M) S₁ = -36M

Tabel 1.1 (Tabel simpleks awal)

Basis	X1	X’’	X2	S1	S2	S3	Solusi	Rasio
Z	-18 -12M	18 + 12M	- 36 - 6M	M	0	0	-36M
A1	12	-12	6	-1	0	1	36	3
S2	4	-4	4	0	1	0	32	8

Tabel 1.2 (pivot point untuk iterasi pertama)

Basis	X1	X2	X3	S1	S2	S3	Solusi
Z
A1	1	-1	1/2	-1/12	0	1/12	36
S2

Tabel 1.3 (tabel iterasi pertama)

Basis	X1	X’’	X2	S1	S2	S3	Solusi	Rasio
Z	0	0	-27	-3/2	0	0	54
A1	1	-1	1/2	-1/12	0	1/12	36	72
S2	0	0	2	1/3	1	0	20	10

Tabel 1.4 (Pivot point untuk iterasi kedua)

Basis	X1	X2	X3	S1	S2	S3	Solusi
Z
X2	4	-4	2	-1/3	0	*	12
S2

Tabel 1.5 (tabel iterasi kedua)

Basis	X1	X’’	X2	S1	S2	S3	Solusi	Rasio
Z	108	-108	27	-21/2	0	*	42
X2	4	-4	2	-1/3	0	*	12	*
S2	-8	8	-2	1	1	*	-4	10

Tabel 1.6 (pivot point untuk iterasi ketiga)

Basis	X1	X2	X3	S1	S2	S3	Solusi
Z
X2
X’’	-1	1	-1/4	1/8	1/8	*	-1/2

Tabel 1.7 (tabel iterasi ketiga yang menghasilkan nilai optimum)

Basis	X1	X’’	X2	S1	S2	S3	Solusi	Rasio
Z	0	0	0	-24	13.5	*	-12	optimum
X2	0	0	1	-5/6	-1/2	*	10
X2’’	-1	1	1/4	1/8	1/8	*	-1/2

                     Setelah diperoleh tabel optimum, untuk menentukan solusi terhadap variable masalah asli, variable harus diubah kembali kedalam bentuk asli.

X₁ = X_1­’-X’’ = 0-(-1/2) = ½ dan X₂ = 10, sehingga Z= -12