universitas gunadarma jakarta 2020

Bahan Ajar Riset Operasi

OLEH

Nurina Yasin, ST,. MT.

UNIVERSITAS GUNADARMA

JAKARTA

2020

ii

KATA PENGANTAR

Alhamdulillah dan puji syukur penulis panjatkan kehadirat Allah SWT atas

segala rahmat, taufik, dan hidayah-Nya, sehingga setelah melalui proses akhirnya

penyusunan bahan ajar Riset Operasi untuk perguruan tinggi ini dapat terselesaikan.

Penyusunan bahan ajar ini berdasarkan rujukan Satuan Acara Perkuliahan

(SAP) di Universitas Gunadarma. Bahan ajar ini nantinya akan digunakan sebagai

penunjang perkuliahan mahasiswa Fakultas Teknik Sipil dan Perencanaan.

Meskipun bahan ajar ini telah diselesaikan, penulis menyadari bahwa bahan

ajar ini masih jauh dari kesempurnaan, sehingga penulis mengharapkan teguran,

kritik dan saran yang membangun dari para pembaca. Akhir kata penulis berharap

semoga bahan ajar ini dapat memberikan manfaat bagi seluruh pihak dan penulis

mendo’akan kepada pihak – pihak yang telah membantu, semoga Allah SWT

membalasnya dengan pahala dan kebaikan, karena sebaik-baiknya pembalas adalah

Allah swt.

Depok, April 2020

Nurina Yasin, ST,. MT.

iii

DAFTAR ISI

HALAMAN JUDUL ....................................................................................... i

KATA PENGANTAR ..................................................................................... ii

DAFTAR ISI .................................................................................................... iii

DAFTAR GAMBAR ....................................................................................... vii

BAB 1 METODE SIMPLEKS

1.1 SYARAT METODE SIMPLEKS .......................................... 1

1.2 LANGKAH-LANGKAH PENYELESAIAN

METODE SIMPLEKS ........................................................... 2

BAB 2 METODE DUAL SIMPLEKS

2.1 KEGUNAAN METODE DUAL SIMPLEKS ....................... 6

2.2 LANGKAH-LANGKAH METODE DUAL SIMPLEKS ..... 6

BAB 3 METODE GRAFIK

3.1 LANGKAH-LANGKAH METODE GRAFIK ..................... 10

BAB 4 DUALITAS DAN ANALISIS SENSITIVITAS

4.1 HUBUNGAN ANTARA PRIMAL DUAL ........................... 14

4.2 LANGKAH-LANGKAH PENYELESAIAN ........................ 15

iv

4.3 MENGINTERPRETASIKAN MODEL PRIMAL ................ 16

4.4 MENGINTERPRETASIKAN MODEL DUAL .................... 17

4.5 ANALISIS SENSITIVITAS .................................................. 17

4.5.1 Analisis dari Dampak Perubahan Koefisien Fungsi

Tujuan ........................................................................ 18

4.5.2 Analisis dari Dampak Perubahan Koefisien Fungsi

Batasan ....................................................................... 19

BAB 5 METODE TRANSPORTASI

5.1 SOAL METODE TRANSPORTASI ..................................... 21

5.2 SOLUSI METODE NWC (NORTH WEST CORNER) ......... 22

5.3 SOLUSI METODE LC (LEAST COST) ................................. 22

5.4 SOLUSI METODE VAM (VOGEL

APPROXIMATION METHOD) ............................................. 23

5.5 SOLUSI METODE RAM (RUSSEL

APPROXIMATION METHOD) ............................................. 23

5.6 SOLUSI OPTIMAL LANGKAH AWAL MODI

(MODIFIED DISTRIBUTION) .............................................. 24

5.7 SOLUSI OPTIMAL LANGKAH KEDUA STEPPING

STONE ................................................................................... 27

v

BAB 6 METODE PENUGASAN (HUNGARIAN)

6.1 KASUS MINIMUM ............................................................... 31

6.1 KASUS MAKSIMUM ........................................................... 34

BAB 7 METODE JARINGAN

7.1 MINIMUM SPANNING TREE ............................................... 36

7.2 ALIRAN MAKSIMUM ......................................................... 37

DAFTAR PUSTAKA .......................................................................................... vi

1

BAB 1

METODE SIMPLEKS

TIU: Memahami permasalahan dan membuat mode matematik

TIK:

1. Bentuk umum LP

2. Bentuk baku LP

3. Tujuan, Kendala dan Alternatif dalam RO

4. Pemodelan Matematik

5. Pemodelan matematik kendala / pembatas.

6. Tabel simpleks

7. Penentuan solusi basis /dasar

8. Penentuan solusi optimal

1.1 SYARAT METODE SIMPLEKS

Berikut adalah syarat-syarat metode simpleks dalam menyelesaikan studi

kasus:

1. Fungsi tujuan harus = 0

2. Fungsi kendala harus positif jika – kalikan -1

3. Fungsi kendala ≤ harus diubah kebentuk – dengan menambahkan slack /

surplus.

4. Fungsi kendala ≥ harus diubah ke bentuk ≤ dengan mengalikan -1 lalu diubah

ke bentuk persamaan dengan menambahkan variabel slack. Kemudian karena

nilai kananya (NK) negatif, kalikan dengan -1 dan di tambahkan variabel

artificial (M).

5. Fungsi kendala dengan tanda = harus ditambah artificial (M).

2

1.2 LANGKAH-LANGKAH PENYELESAIAN METODE SIMPELEKS

Selesaikan soal dibawah ini dengan menggunakan metode simpleks.

Diketahui :

Fungsi Tujuan

Z = 3X1 +5X2

Fungsi Kendala

1. 2X1 ≤ 8

2. 3X2 ≤ 15

3. 6X1 + 5X2 ≤ 30

1 Mengubah Fungsi Tujuan dan Fungsi Kendala

Fungsi tujuan

Z = 3X1 + 5X2 Z - 3X1 - 5X2 = 0

Fungsi kendala

1) 2X1 ≤ 8 2X1 + X3 = 8

2) 3X2 ≤ 15 3X2 + X4 = 15

3) 6X1 + 5X2 ≤ 30 6X1 + 5X2 + X5 = 30

(X3, X4 dan X5 adalah variabel slack)

2 Menyusun Persamaan-Persamaan ke dalam Tabel

3

3 Memilih Kolom Kunci

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif

dengan angka terbesar

4 Memilih Baris Kunci

Index = Nilai Kanan (NK)

Nilai Kolom kunci angka kunci

Baris kunci adalah baris yang mempunyai index terkecil

5 Menentukan Nilai Baris Baru Kunci

Mengubah nilai-nilai baris kunci dengan cara membaginya dengan angka kunci

Baris baru kunci = baris kunci : angka kunci

4

6 Mengubah Nilai-Nilai Selain Baris Kunci Sehingga Nilai Kolom Kunci (Selain

Baris Kunci) = 0

Baris baru = baris lama – (koefisien angka kolom kunci x nilai baris baru kunci)

Baris Z

Baris lama [ -3 -5 0 0 0 0 ]

NBBK -5 [ 0 1 0 1/3 0 5 ] -

Baris baru -3 0 0 5/3 0 25

Baris X3

Baris lama [ 2 0 1 0 0 8 ]

NBBK 0 [ 0 1 0 1/3 0 5 ] -

Baris baru 2 0 1 0 0 8

Baris X5

Baris lama [ 6 5 0 0 1 30 ]

NBBK 5 [ 0 1 0 1/3 0 5 ] -

Baris baru 6 0 0 -5/3 1 5

Masukkan nilai di atas (langkah 6) ke dalam tabel, sehingga tabel menjadi seperti

berikut:

5

7 Melanjutkan Perbaikan-Perbaikan (Langkah 3-6) Sampai Baris Z Tidak Ada

Nilai Negatif

Hasil penyelesaian akhir dapat dilihat pada table berikut:

6

BAB 2

METODE DUAL SIMPLEKS

TIU:

Memahami penggunaan bentuk solusi awal buatan

TIK:

1. Menjelaskan metode dual simpleks

2. Menjelaskan kasus-kasus khusus

2.1 KEGUNAAN METODE DUAL SIMPLEKS

Berikut adalah kegunaan metode dual simpleks:

1 Prosedur perhitungan yang bergerak pada solusi dasar yang belum optimum

2 Proses untuk mencapai solusi optimum

3 Mendapatkan solusi dasar awal yang baik

4 Artificial Variable digunakan untuk solusi yang layak

2.2 LANGKAH-LANGKAH METODE DUAL SIMPLEKS

Metode ini dapat digunakan dengan syarat jika fungsi kendali ≥

Perhatikan soal dan penyelesaian berikut:

Minimumkan, Z = 4X1 + 2X2

FK 1. 3X1 + X2 ≥ 27

2. X1 + X2 ≥ 21

3. X1 + 2X2 ≥ 30

Lakukan analisis simplek

1 Mengubah persamaan menjadi pertidaksamaan ≤ dengan menambahkan

variable slack.

1 -3X1 – X2 ≤ -27 = -3X1 – X2 + X3 = -27

2 -X1 – X2 ≤ -21 = -X1 – X2 + X4 = -21

3 -X1 – 2X2 ≤ -30 = -X1 – 2X2 + X5 = -30

7

Bentuk diatas adalah Simpleks awal, terlihat variable stack (S1, S2, S3) tidak

memberikan solusi awal yang layak

2 Masukan ke dalam tabel

3 Pilih baris kunci = Pilih NK (-) terbesar

4 Pilih kolom Kunci = Indeks terkecil ( Z / Baris Kunci)

5 Mencari Nilai Baru Baris Kunci

(-1/(-2)), (-2/(-2)), (0/(-2)), (0/(-2)), (1/(-2)), (-30/(-2))

Hasilnya;

NBBK [ 1 2⁄ 1 0 0 - 1 2⁄ 15 ]

6 Mencari Nilai Baru Baris Z, X3, dan X4

• Nilai baru Z = Z – kk [NBBK]

𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 NK

-4 -2 0 0 0 0

-2 [ 1 2⁄ 1 0 0 - 1 2⁄ 15 ] -

-3 0 0 0 -1 30

8

Nilai baru 𝑋3 = 𝑋3 - kk . [NBBK]

𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 NK

-3 -1 1 0 0 -27

-1 [ 1 2⁄ 1 0 0 - 1 2⁄ 15 ] -

-5 2⁄ 0 1 0 -1 2⁄ -12

Nilai baru 𝑋4 = 𝑋4 - kk . [NBBK]

𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 NK

-1 -1 0 1 0 -21

-1 [ 1 2⁄ 1 0 0 - 1 2⁄ 15 ] -

-1 2⁄ 0 0 1 -1 2⁄ -6

7 Masukan Tabel Iterasi Pertamav

Pada tabel iterasi pertama ini dihasilkan solusi yang belum layak, bisa

dilihat dari nilai NK dimana masih ada yang bernilai negatif. Oleh karena itu kita

lakukan lagi pencarian NBBK pada iterasi pertama ini dengan cara yang sama

seperti pencarian NBBK sebelumnya. Ulangi sampai NK positif semua.

9

Berikut merupakan tabel hasik akhir:

Pembuktian

Pada tabel akhir dapat kita lihat bahwa solusi optimal dan layak dengan tidak

adanya bilangan bernilai negatif pada NK, dengan nilai fungsi tujuan adalah 48.

Untuk mengecek apakah hasil tersebut benar maka kita akan lakukan pembuktian

seperti ini.

Z = 48 𝑿𝟏 = 3 𝑿𝟐 = 18

Z = 4𝑿𝟏 + 2𝑿𝟐 (soal)

= 4(3) + 2(18)

48 = 48 (Terbukti)

10

BAB 3

METODE GRAFIK

TIU:

Mengenal, memahami dan menyelesaikan permasalahan menggunakan solusi

grafik

TIK:

1. Memahami soal dengan solusi Grafik

2. Mendapat Solusi Optimum

3.1 LANGKAH-LANGKAH METODE GRAFIK

11

12

13

14

BA B 4

DUALITAS DAN ANALISIS SENSITIVITAS

TIU:

Mengenal dualitas dan Analisa sensitivitas.

TIK:

1. Menjelaskan penyelesaian permasalahan dual

2. Menyebutkan interpretasi solusi permasalahan dual

3. Menjelaskan penggunaan analisa sensitifitas

4.1 HUBUNGAN ANTARA PRIMAL DUAL

1 Variabel dual Y1,Y2,Y3 berhubungan dengan batasan model primal, dimana

untuk setiap batasan dalam primal, terdapat satu variabel dual.

2 Nilai kuantitas pada sisi kanan pertidaksamaan dalam model primal merupakan

koefisien fungsi tujuan dual.

3 Koefisien batasan model primal merupakan nilai kuantitas pada sisi kanan

pertidak samaan pada model dual.

4 Pada bentuk standard, model maksimalisasi primal memiliki batasan ,

sedangkan model minimasi dual memiliki batasan .

15

4.2 LANGKAH-LANGKAH PENYELESAIAN

Perhatikan contoh soal berikut:

Bentuk Primal

Fungsi tujuan : Memaksimalkan Z = 160 x1 + 200 x2

Fungsi batasan :

2x1 + 4x2 40

18x1 + 18x2 216

24 x1 + 12x2 240

x1,x2 0

Bentuk Dual

Fungsi tujuan : Meminimalkan W= 40 y1+216 y2+240 y3

Fungsi batasan :

2 y1+18y2+ 24y3 160

4y1 +18y2 + 12y3 200

y1,y2,y3 0

16

4.3 MENGINTERPRETASIKAN MODEL PRIMAL

(Lihat Contoh 1)

Solusi optimal dari model primalnya adalah sbb :

1 Jumlah produk A yang diproduksi adalah x1 = 4

2 Jumlah produk B yang diproduksi adalah x2 = 8

3 Sisa luas gudang adalah S3 = 48 m2

4 Nilai baris cj-zj di bawah kolom S1 adalah -20. Nilai ini menunjukkan harga

bayangan (shadow prizes=nilai marginal) dari batasan ke 1 (tenaga kerja). Ini

berarti jika tenaga kerja ditambah 1 jam akan menambah laba sebesar $20

5 Nilai baris cj-zj di bawah kolom S2 adalah -20/3 atau -6.667. Nilai ini

menunjukkan harga bayangan (shadow prizes) dari batasan ke 2 (bahan baku)

6 Laba yang diperoleh adalah sebesar $2240

7 Untuk batasan ke 3 (luas gudang) pada tabel optimal terlihat bahwa nilai S3

pada baris cj-zj bernilai nol, artinya bahwa gudang memiliki shadow prizes

sebesar nol, yang berarti tidak akan ada pembayaran tambahan untuk 1 m2 luas

gudang.

17

4.4 MENGINTERPRETASIKAN MODEL DUAL

Solusi optimal dari model dual adalah:

1 Dari batasan dual yang pertama, yaitu 2y1+18y2+24y3 160 laba per produk

A. Artinya nilai dari ketiga sumber yang digunakan untuk memproduksi produk

A, paling sedikit harus sebesar laba yang diperoleh dari produk A.

2 Dari batasan dual yang kedua, yaitu 4y1+18y2+12y3 200 laba per produk B.

Artinya nilai dari ketiga sumber yang digunakan untuk memproduksi produk B,

paling sedikit harus sebesar laba yang diperoleh dari produk B.

3 Fungsi tujuan untuk model dual adalah meminimalkan Z = 40y1+216y2+240y3,

ini berarti nilai total sumber-sumber daya (jam tenaga kerja, bahan baku,

gudang) adalah sebesar : 40.20 + 216 .20/3 + 240.0 = 2240. Artinya, nilai total

minimal untuk kebutuhan sumber adalah 2240.

4.5 ANALISIS SENSITIVITAS

Pada masalah sebelumnya, selalu diasumsikan bahwa parameter dari model

( diantaranya, koefisien fungsi tujuan, nilai kuantitas dari pertidaksamaan fungsi

batasan, dan koefisien batasan ), selalu dianggap pasti, padahal dalam kenyataannya

tidak selalu demikian, karena kadang bisa berubah, untuk itu biasanya si pembuat

keputusan ingin mengetahui dampak yang terjadi pada solusi model, jika

parameternya diubah. Analisis terhadap perubahan parameter dan dampaknya

terhadap solusi optimal model disebut Analisis Sensitivitas. Akan dibicarakan

analisis dari dampak perubahan pada koefisien fungsi tujuan dan nilai kuantitas

dari pertidaksamaan fungsi batasan.

18

4.5.1 Analisis dari Dampak Perubahan Koefisien Fungsi Tujuan

Perhatikan contoh 1 :

Fungsi tujuan : Memaksimalkan Z = 160 x1 + 200 x2

Fungsi batasan :

2x1 + 4x2 40

18x1 + 18x2 216

24 x1 + 12x2 240

x1,x2 0

Pertanyaan :

a. Jika laba untuk produk A (x1) dinaikkan menjadi 170, berapa laba yang di

dapat?

b. Jika laba untuk produk A (x1) dinaikkan menjadi 220, berapa laba yang di

dapat?

Penyelesaian

a. Untuk menentukan laba optimal jika terjadi perubahan pada fungsi tujuan, tidak

perlu diubah dari iterasi 0, tetapi dapat diubah langsung pada tabel optimalnya

saja, yaitu dengan cara :

Laba optimal berubah menjadi $2280

19

b. Jika laba A terus dinaikkan menjadi $220, maka yang akan terjadi adalah :

Dari tabel optimal terlihat jika laba dinaikkan menjadi $220, maka keadaan optimal

tidak terpenuhi lagi, karena pada baris cj-zj terdapat nilai positif. Untuk itu, pada

soal c, akan diselidiki seberapa jauh (range) perubahan yang dapat dilakukan agar

keadaan tetap optimal.

4.5.2 Analisis dari Dampak Perubahan Koefisien Fungsi Batasan

Perhatikan contoh 1 :

Fungsi tujuan : Memaksimalkan Z = 160 x1 + 200 x2

Fungsi batasan :

2x1 + 4x2 40 jam tenaga kerja

18x1 + 18x2 216 kg bahan baku

24 x1 + 12x2 240 m2 luas gudang

x1,x2 0

Pertanyaan :

a. Jika jam untuk tenaga kerja diturunkan menjadi 35, berapa laba yang didapat?

b. Jika jam untuk tenaga kerja diturunkan menjadi 30, berapa laba yang didapat?

20

Penyelesaian

a. Untuk menentukan laba optimal jika terjadi perubahan pada nilai kanan fungsi

batasan, tidak perlu diubah dari iterasi 0, tetapi dapat diubah langsung pada tabel

optimalnya saja, yaitu dengan cara.

b. :

Dari tabel optimal dapat dilihat, jika jumlah jam tenaga kerja diturunkan menjadi

35, maka laba juga akan turun menjadi $ 2140.

c. Jika jam tenaga kerja diturunkan lagi menjadi 30, maka :

Karena nilai kuantitas menjadi negatif, maka tidak memenuhi syarat sebagai

simpleks.

21

BAB 5

METODE TRANSPORTASI

TIU:

Memahami penggunaan metode transportasi dan menyelesaikan kasus-kasus

metode transportasi.

TIK:

1. Menjelaskan permasalahan yang dapat diselesaikan dengan metode

transportasi

2. Menjelaskan metode NWC

3. Menjelaskan metode LC.

4. Menjelaskan metode VAM

5. Menjelaskan penentuan solusi yang optimal

5.1 SOAL METODE TRANSPORTASI

22

5.2 SOLUSI METODE NWC (NORTH WEST CORNER)

5.3 SOLUSI METODE LC (LEAST COST)

23

5.4 SOLUSI METODE VAM (VOGEL APPROXIMATION METHOD)

5.5 SOLUSI METODE RAM (RUSSEL APPROXIMATION METHOD)

24

5.6 SOLUSI OPTIMAL LANGKAH AWAL MODI (MODIFIED

DISTRIBUTION)

Metode ini dalam merubah alokasi produk untuk mendapatkan alokasi

produksi yang optimal menggunakan suatu indeks perbaikan yang berdasarkan

pada nilai baris dan nilai kolom.

Kita gunakan soal pada metode transportasi di atas untuk solusi metode

NWC. Pakai tabel terakhirnya.

25

26

27

5.7 SOLUSI OPTIMAL LANGKAH KEDUA STEPPING STONE

Metode ini dalam merubah alokasi produk untuk mendapatkan alokasi

produksi yang optimal menggunakan cara trial and error atau coba – coba.

28

29

30

31

BAB 6

METODE PENUGASAN (HUNGARIAN)

TIU:

Model penugasan menggunakan Metode Hungarian.

TIK:

1 Menjelaskan proses pembentukan tabel penugasan, sampai dengan

pencarian solusi yang optimal

2 Menggunakan metode hungarian, baik untuk jumlah tugas = jumlah pekerja

ataupun jumlah tugas ≠ jumlah pekerja

6.1 KASUS MINIMUM

Sebuah perusahaan kecil mempunyai 4 pekerjaan yang berbeda untuk

diselesaikan oleh 4 karyawan. Biaya penugasan seorang karyawan untuk pekerjaan

yang berbeda adalah berbeda karena sifat pekerjaan berbeda-beda. Setiap karyawan

mempunyai tingkat ketrampilan, pengalaman kerja dan latar belakang pendidikan

serta latihan yang berbeda pula. Sehingga biaya penyelesaian pekerjaan yang sama

oleh para karyawan yang berlainan juga berbeda. Tabel biaya sebagai berikut:

1. Memilih biaya terkecil setiap baris

32

2. Mengurangkan setiap biaya dengan biaya terkecil

3. Mengurangkan kolom pada kolom yang belum mempunyai nilai nol, pilih

yang terkecil

4. Chek optimumnya (menarik garis)

*Jika jumlah garis sama dengan jumlah baris/ kolom maka penugasan telah

optimal. Jika tidak maka harus direvisi.

33

5. Melakukan Revisi matrix (iterasi)

Untuk merevisi total opportunity cost, pilih angka terkecil yang tidak terliput

(dilewati) garis

Kurangkan angka yang tidak dilewati garis dengan angka terkecil

Pada tabel yang dilewati 2 garis ditambah dengan angka terkecil.

6. Kembali ke langkah 4

Jumlah garis = jumlah baris / kolom = OPTIMAL

34

7. Tabel penugasan

6.2 KASUS MAKSIMUM

Untuk penyelesaian kasus maksimum hampir sama dengan minimum hanya

langkah pertama yang berbeda, yaitu memilih biaya TERBESAR.

35

Hasil dari kasus maksimum dapat di lihat pada gambar di bawah ini.

36

BAB 7

METODE JARINGAN

TIU:

Mengenal Teknik-teknik analisis jaringan.

TIK:

1 Menjelaskan arti jaringan

2 Menjelaskan arti istilah pada jaringan

3 Menjelaskan pencarian minimum spanning tree, rute terpendek dan aliran

maksimum

7.1 MINIMUM SPANNING TREE

Minimum Spanning Tree adalah menghubungkan seluruh simpul dalam jaringan

sehingga total panjang cabang dapat diminimumkan. Dengan syarat yaitu :

1 Pilih simpul manapun yang memiliki nilai cabang terkecil

2 Tidak boleh membentuk grup

3 Semua simpul harus dialiri

37

7.2 ALIRAN MAKSIMUM

Aliran Maksimum adalah jumlah titik awal dan titik akhir harus memiliki

jumlah yang sama. Dengan cara yaitu :

1 Pilih titik awal dan titik akhir

2 Titik awal dimulai dari yang memiliki nilai maksimal

38

viii

DAFTAR PUSTAKA

Setyawan, Aris Budi 2010. Riset Operasional 1.

http://arisbudi.staff.gunadarma.ac.id/Downloads/folder/0.1 (diakses pada

tanggal April 2020)

Setyawan, Aris Budi 2010. Riset Operasional 2.

http://arisbudi.staff.gunadarma.ac.id/Downloads/folder/0.1 (diakses pada

tanggal April 2020)