riset operasi (materi kuliah)

Pertemuan ke-1

Riset Operasi

Ir. Bambang SA, MSi

Ir. Kawiji, MP

Asri Nursiwi, STP., MSc

Siswanti, STP., MSc

Buku

• Riset Operasi oleh : Hamdy A.Taha, Edisi Ke-5 Jilid 1, Binarupa Aksara, 1996.

• Pengantar Riset Oprerasi, oleh Gerald J Lieberman dkk, edisi 5, Jilid 1 Penerbit Erlangga 1994.

• Teori dan Soal Operations Research (Seri Buku Schaum’s) oleh : Richard Bronson

Riset Operasi

Riset Operasi adalah metode untuk memformulasikan dan merumuskan

permasalahan sehari-hari baik mengenai bisnis, industri, ekonomi, sosial maupun bidang lainnya ke dalam pemodelan matematis untuk mendapatkan solusi yang optimal.

Riset Operasi

• RO sebagai metode ilmiah yang memungkinkan para manajer mengambil keputusan mengenahi kegiatan yang mereka tangani dengan dasar kuantitatif (Morse dan Kimball)

• RO sebagai aplikasi metode-metode, teknik-teknik, dan peralatan-peralatan ilmiah dalam menghadapi masalah yang timbul dalam operasi perusahaan dengan tujuan ditemukannya pemecahan yang optimum (Churchman, Arkoff dan Arnoff)

Riset Operasi

RO berkenaan dengan pengambilan keputusan optimal dalam penyusunan model dari sistem-sistem baik deterministik maupun probabilistik yang berasal dari kehidupan nyata (Subagyo, Asri dan Handoko)

Silabi

• Pendahuluan• Pemrograman matematis (LP, bentuk standar,

penyelesaian: grafik dan simplek)• Dualitas• Pemrograman bilangan bulat : algoritma

pencabangan, algoritme pemotongan, algoritme transportasi)

• Penjadwalan dan penugasan• Analisis jaringan• Pohon keputusan• Teori antrian

Pendahuluan

• Kontrak perkuliahan : pengajar, buku, sistem penilaian, silabi

• Apa itu RO

• Menerangkan fungsi tujuan dan kendala dengan memberikan contoh kasus (tukang kayu dan pembuat minuman)

Tahapan Kajian RO

• Merumuskan masalah• Membuat model matematis untuk

menggambarkan sistem yang akan dipelajari

• Menyelesaikan model• Menguji model• Menentukan kendali atas penyelesaian

model tersebut• Menjalankan penyelesaiannya

Linear Programing (LP)

• Suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber daya yang terbatas sehingga diperoleh hasil yang optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas

Tukang kayu

Seorang tukang kayu akan membuat perabot dua model yaitu I dan II. Bahan yang tersedia 8 potong kayu dan waktu 28 jam. Model I membutuhkan 2 potong kayu dan waktu 7 jam dan model II membutuhkan 1 potong kayu dan waktu 8 jam. Keuntungan yang diperoleh untuk model I 120 ribu dan model II 80 ribu.

Pembuat minuman

Seorang pemasok minuman menerima pesanan 500 galon minuman campuran dengan spek min 20 % air jeruk, 10 % air anggur dan 5 % air trawbery.

Bahan baku yang

Pertemuan II

Fungsi dalam LP

• Tujuan (Z) : fungsi yang menggambarkan tujuan sasaran dalam model LP yang berkaitan dengan penganturan secara optimal sumber daya –sumber daya untuk memperoleh keuntungan maksimal atau biaya minimal.

• Fungsi Batasan : merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan

Linear Programming

),...,,( 21 nxxxfZ

g1(x1, x2,… , xn)g2(x1, x2,… , xn)………………..………………..gn(x1, x2,… , xn)

≤

=

≥

b1

b2

.

.bn

Tujuan :

Kendala :

Asumsi LP

• Proportionality : Naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding dengan perubahan tingkat kegiatan

• Additivity : Nilai tujuan setiap kegiatan tidak saling mempengaruhi,

• Divisibility : output dari setiap kegiatan dapat berupa bilangan pecahan, demikian juga nilai tujuan

• Diterministic : semua parameter yang terdapat dalam model LP dapat diperkirakan dengan tepat meskipun belum tentu benar

Penyelesaian dengan Grafik

Maks : Z = 120 X1 + 80 X2

Kendala 2 X1 + X2 ≤ 8

5 X1 + 8 X2 ≤ 20

Buat grafik sumbu hirizontal X1 dan Vertikal X2 dengan garis-garis dari fungsi kendala

Untuk kendala 1

Jika X1 = 0, maka X2 = 8 (0,8)

X2 = 0, maka X1 = 4 (4,0)

Untuk kendala 2

Jika X1 = 0, maka X2 = 3.5 (0,3.5)

X2 = 0, maka X1 = 4 (4,0)

Untuk tujuan, dimisalkan Z = 240

Jika X1 = 0, maka X2 = 3 (0,3)

X2 = 0, maka X1 = 2 (2,0)

X2

X1

10

6

2

1062

Titik (0,3.5), kalu

dimasukan ke Z = 280

Titik (4,0), kalu

dimasukan ke Z = 480

• Maksimumkan Z = 3 X1 + 5 X2

• Kendala :

2X1 ≤ 8

3X2 ≤ 15

6X1 + 5X2 ≤ 30

X1

X2

10

6

2

1062

Titik D (5/6,5) kalu

dimasukan ke Z = 27,52X1 ≤ 8

3X2 ≤ 15

6X1 + 5X2 ≤ 30Daerah Fiasible

E

C

BA

D

(4, 6/5)

Titik D (4,6/5) kalu

dimasukan ke Z = 18

Latihan soal

Maks Z = 2x1 + x2

Kendala x1 + 5x2 ≤ 10

x1 + 3x2 ≤ 6

2x1 + 2x2 ≤ 8

Min Z = 5x1 + 2x2

Kendala 6x1 + x2 ≥ 10

4x1 + 3x2 ≥ 12

x1 + 2x2 ≥ 4

Maks Z = 2x1 + x2Kendala x1 + 5x2 ≤ 10 x1 + 3x2 ≤ 6 2x1 + 2x2 ≤ 8

X2

10

6

2

1062

X1+5x2 ≤ 10

X1 + 3X2 ≤ 6

2X1 + 2X2 ≤ 8

Daerah Fiasible

Min Z = 5x1 + 2x2

Kendala 6x1 + x2 ≥ 10 4x1 + 3x2 ≥ 12 x1 + 2x2 ≥ 4

X2

10

6

2

1062

x1 + 2x2 ≥ 4

4x1 + 3x2 ≥ 12

Daerah Fiasible6x1 + x2 ≥ 10

Metode Simplek : Bentuk Standar

Persyaratan :

1. b i tidak boleh negatif

n

jijij bxa

1

2. Menghilangkan kendala lebih atau kurang dengan menambahkan variabel kurang atau lebih (slag atau surplus)

3. Sudah adakah pemecahan awal yang layak atau belum ? Bila sudah, langkah berhenti disini dan bila belum, langkah dilanjutkan ke-4. Pemecahan awal layak jika semua variabel keputusan bernilai positif atau nol

4. Tambahkan variabel lain sebagai biaya hukuman (penalty cost). Karena penambahan variabel ini akan mengubah kendala, maka penambahan pada fungsi tujuan harus diikutkan dengan konstanta bernilai. Untuk tujuan maks, maka ditambahkan nilai negatif yang besar sekali (-M) dan untuk tujuan min, maka ditambahkan nilai positif yang besar sekali (M)

Contoh 1: bentuk standar

Tujuan : Z = X1 + X2

Kendala : X1 + 5X2 ≤ 5

2X1 + X2 ≤ 41. Semua nilai bn sudah positif

2. Hilangkan tanda kurang dan lebih

Tujuan : Z = X1 + X2 + 0X3 + 0X4

Kendala : X1 + 5X2 + X3 = 5

2X1 + X2 + X4 = 4

3. Apakah sudah ada pemecahan awal yang layak

Dimisalkan, X1 dan X2 = 0, maka X3 = 5 dan X4 = 4

Jadi sudah ada pemecahan awal yang layak

Contoh 2 : bentuk standar

Tujuan Min Z = x1 + 2x2 + 3x3

Kendala : 3x1 + 4x3 ≤ 5

5x1 + x2 + 6x3 = 7

8x1 + 9x3 ≥ 2

Langkah 1 : bn positif ?

Tujuan Min Z = x1 + 2x2 + 3x3

Kendala : 3x1 + 4x3 ≤ 5

5x1 + x2 + 6x3 = 7

8x1 + 9x3 ≥ 2

Langkah 2 : Variabe + dan -

Tujuan Min Z = x1 + 2x2 + 3x3 + 0x4 + 0x5

Kendala : 3x1 + 4x3 + x4 = 5

5x1 + x2 + 6x3 = 7

8x1 + 9x3 - x5 = 2

Langkah 3 : Apakah sudah ada pemecahan awal yang layak ?

Tujuan Min Z = x1 + 2x2 + 3x3 + 0x4 + 0x5

Kendala : 3x1 + 4x3 + x4 = 5

5x1 + x2 + 6x3 = 7

8x1 + 9x3 - x5 = 2

Misalkan : x1, x3 = 0, maka x2 = 7, x4 = 5 dan x5 = -2

Jadi belum ada pemecahan awal yang layak karena masih ada variabel yang bernilai bukan positif atau nol

Langkah 4 : Tambah pinalty cost

Tujuan Min Z = x1 + 2x2 + 3x3 + 0x4 + 0x5 + Mx6

Kendala : 3x1 + 4x3 + x4 = 5

5x1 + x2 + 6x3 = 7

8x1 + 9x3 - x5 + x6 = 2

Misalkan : x1, x3, x5 = 0, maka x2 = 7, x4 = 5 dan x6 = 2

Jadi sudah ada pemecahan awal yang layak

Contoh 3 dan 4 : bentuk standar

Tujuan Min Z = 2x1 - x2 + 4x3

Kendala : 5x1 + 2x2 - 3x3 ≥ -7

2x1 - 2x2 + x3 ≤ 8

Tujuan Min Z = 10x1 + 2x2 + 3x3 + x4

Kendala : 2x1 + 7x2 ≤ 7

5x1 + 8x2 + 2x4 = 10

x1 + x3 = 11


Tujuan Min Z = 2x1 - x2 + 4x3 + 0x4 + 0x5

Kendala : (5x1 + 2x2 - 3x3 ≥ -7)x-1

-5x1 - 2x2 + 3x3 + x4 = 7

2x1 - 2x2 + x3 + x5 = 8

Jadi pemecahan awal yang layak x1, x2, x3 = 0, x4 = 7 dan x5 = 8


Tujuan Min Z = 10x1 + 2x2 + 3x3 + x4 + M x5

Kendala : 2x1 + 7x2 + x5 = 7

5x1 + 8x2 + 2x4 = 10

x1 + x3 = 11

Jadi pemecahan awal yang layak x1, x2,= 0, x3= 11, x4 = 5 dan x5 = 7

Kuis 1.Ubah LP dibawah ini kedalam bentuk standar1. Min Z = 5x1 + 2x2 + x3 + 0x4 +0x5 +0x6 +0x7

Kendala : 2x1 + 3x2 + x3 + x4 = 20

6x1 + 8x2 + 5x3 + x5 = 30

7x1 + x2 + 3x3 + x6 = 40

x1 + 2x2 + 4x3 + x7 = 50

x1, x2, x3 = 0 x4 =20, x5=30, x6=40, x7 = 50

Kuis 1.Ubah LP dibawah ini kedalam bentuk standar

2. Maks Z = 20w1 + 30w2 +40w3 + 50w4+ 0w5 + 0w6 – Mw7 – Mw8

Kendala : 2w1 + 6w2 + 7w3 + w4 + w5 = 5

3w1 + 8w2 + w3 + 2w4 + w7 = 2

w1 + 5w2 + 3w3 + 4w4 - w6 + w8 = 1

w1, w2, w3, w4, w6 =0, w5 = 5, w7 = 2, w8 = 1

Kuis 1.Ubah LP dibawah ini kedalam bentuk standar1. Min Z = 5x1 + 2x2 + x3 + 0x4 + 0x5 + 0x6 + Mx7

+ Mx8 + Mx9

Kendala : 2x1 + 3x2 + x3 – x4 + x7 = 20

6x1 + 8x2 + 5x3 – x5 + x8 = 30

7x1 + x2 + 3x3 + x9 = 40

x1 + 2x2 + 4x3 + x6 = 50X1, x2, x3, x4, x5 = 0, x7 = 20, x8 = 30, x9 = 40 dan x6 = 50

Pertemuan ke-3

Metode SimplekOptimasi : Z = CT X

Dengan kendala : AX = B

dan X ≥ 0

XT

CT

Xo Co A B

-(CT – CToA) CT

o B

Bentuk tabel Simplek maks :

Tujuan : Maks Z = x1 + 9x2 + x3

Kendala : x1 + 2x2 + 3x3 ≤ 9

3x1 + 2x2 + 2x3 ≤ 15

Misalkan x1, x2, x3 = 0, maka x4 = 9

dan x5 = 15, jadi sudah ada pemecahan awal yang layak

Tujuan : Maks Z = x1 + 9x2 + x3 + 0x4 + 0x5

Kendala : x1 + 2x2 + 3x3 + x4 = 9

3x1 + 2x2 + 2x3 + x5 = 15

10223

01321A

15

9B

00191TC

54321 xxxxxxT

0

00C

5

40 x

xx

Tujuan : Maks Z = x1 + 9x2 + x3 + 0x4 + 0x5

Kendala : x1 + 2x2 + 3x3 + x4 = 9

3x1 + 2x2 + 2x3 + x5 = 15

Tabel Simplek

x1 x2 x3 x4 x5

1 9 1 0 0

x4 0

x5 0

1 2 3 1 0

3 2 2 0 1

9

15

-1 -9 -1 0 0 0

Tabel simplek dikatakan optimal bila semua nilai pada baris terakhir sama dengan 0 atau positif

Penyelesaian Tabel Simplek

Penyelesaian dikatakan optimal bila nilai elemen pada baris paling bawah (kecuali kolom terakhir) semua positif atau nol

Langkah : Simplek

1. Tentukan letak bilangan yang paling negatif dalam baris terbawah dari tabel simplek, dengan mengabaikan kolom terakhir. Namakan kolom yang terdapat bilangan paling negatif tadi dengan kolom kerja. Jika terdapat lebih dari satu, pilih salah satu

2. Bentuklah nilai-nilai banding dengan membagi setiap bilangan positif dalam kolom terakhir, dengan elemen dalam baris yang sama pada kolom kerja, dimana baris terakhirnya diabaikan. Namakan elemen dalam kolom kerja ini yang menghasilkan nilai-banding terkecil sebagai elemen pasak (pivot element). Jika terdapat lebih dari satu elemen, pilih salah satunya. Jika tidak ada elemen dalam kolom kerja yang positif, maka programnya tdk memiliki pemecahan.

Langkah : Simplek

3. Gunakan operasi-operasi baris elementer untuk mengubah elemen pivot menjadi 1 dan kemudian reduksikan semua elemen lainnya dalam kolom kerja ini menjadi 0

4. Gantikan variabel-x dalam baris pivot dan kolom pertama dengan variabel-x dalam baris pertama dan kolom pivot.

Langkah : Simplek5. Ulangi langkah 1 sampai dengan 4 hingga tidak

terdapat lagi elemen negatif dalam baris terakhir, dengan tidak mamasukkan kolom terakhir.

6. Pemecahan optimal diperoleh dengan menetapkan untuk tiap-tiap variabel dalam kolom pertama nilai dalam baris dan kolom terakhir yang bersangkutan. Semua variabel yang lainnya ditetapkan bernilai nol. Nilai fungsi tujuan adalah bilangan yang terdapat dalam baris terakhir dan kolom terakhir untuk program maksimasi dan negatifnya untuk program minimasi

Tentukan kolom kerja dan baris kunci

x1 x2 x3 x4 x5

1 9 1 0 0

x4 0

x5 0

1 2 * 3 1 0

3 2 2 0 1

9/2

15/2

-1 -9 -1 0 0 0

Lakukan operasi matrik elementer

x1 x2 x3 x4 x5

1 9 1 0 0

x4 0

x5 0

1/2 1 3/2 1/2 0

3 0 2 0 1

9/2

15

-1 0 -1 0 0 0

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

x1 x2 x3 x4 x5

1 9 1 0 0

x2 0

x5 0

1/2 1 3/2 1/2 0

2 0 -1 -1 1

9/2

6

7/2 0 25/2 9/2 0 81/2

2-(2x3/2)3-(2x1/2) 0-(2x1/2)

1-(2x0)

Jadi nilai optimal X2 = 9/2 dan Z = 81/2

Latihan

Maks Z = 2x1 + x2

Kendala x1 + 5x2 ≤ 10

x1 + 3x2 ≤ 6

2x1 + 2x2 ≤ 8

Contoh Soal

Maks Z = x1 + x2

Kendala : x1 + 5x2 ≤ 5

2x1 + x2 ≤ 4

Maks Z = 3x1 + 4x2

Kendala : 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

Maks Z = 6x1 - x2 + 3X3

Kendala : 7 x1 + 11 x2 + 3 X3 ≤ 25

2 x1 + 8 x2 + 6 X3 ≤ 30

6 x1 + x2 + 7 X3 ≤ 35

Pertemuan VI

Metode Simplek dengan variabel buatan tak NOL (M)

Contoh 2 : Metode Simplek dengan variabel

buatan tak NOL (M)

Tujuan Min Z = 80x1 + 60x2

Kendala 0,2 x1 + 0,32 x2 ≤ 0,25

x1 + x2 = 1

Contoh 2 : Metode Simplek

Tujuan Min Z = 80x1 + 60x2 + 0x3 + Mx4

Kendala 0,2 x1 + 0,32 x2 + x3 = 0,25

x1 + x2 + x4 = 1

Langkah penyelesaian

1. Baris terakhir diuraikan menjadi dua baris, dimana yang pertama mengandung suku-suku yang tidak ada M dan yang suku yang ada nilai M. Tulis koefisiennya saja.

2. Langkah 1 dari metode implek diterapkan pada baris terakhir, diikuti langkah 2, 3, dan 4, hingga baris ini tidak mengandung elemen negatif. Selanjutnya, langkah 1 – 4 metode simplek juga diterapkan pada baris di atasnya. Sampai diperoleh solusi yang optimal.

Pertemuan ke-4KD1

Pertemuan VI

Tabel Simplek

x1 x2 x3 x4

80 60 0 M

x3 0

x4 M

0,2 0,32 1 0 1 1 0 1

0,25

1

80 60 0 0 -1 -1 0 0

0 -1


3. Setiap saat sebuah variabel buatan bukan merupakan suatu variabel dasar yakni, ia dihilangkan dari kolom 1 dari tabel sebagai hasil dari langkah 4, maka ia dicoret dari baris teratas tabel dan begitu pula seluruh kolom dibawahnya.

4. Baris terakhir dapat dicoret dari tabel apabila semua elemennya nol

Tabel Simplek

x1 x2 x3 x4

80 60 0 M

x3 0

x1 M

0 0,12 1 0 1 1 0 1

0,05

1

0 -20 0 0 0 0 0 0

-80 0


5. Jika variabel-variabel buatan yang tak nol terdapat dalam himpunan elemen dasar terakhir, maka programnya tidak memiliki pemecahan. Sebaliknya variabel-variabel buatan yang berharga nol dapat muncul sebagai variabel dasar dalam pemecahan akhir apabila salah satu atau lebih dari persamaan kendala adalah mubadir.

Tabel Simplek

x1 x2 x3

80 60 0

x3 0

x1 M

0 0,12 1 1 1 0

0,05

1

0 -20 0

-80

Tabel Simplek

x1 x2 x3

80 60 0

x2 0

x1 M

0 1 8,33 1 0 -8,33

0,416

0,583

0 0 166,7

-71,67

Jadi nilai optimal Z = 71,67 dan x1 = 0,583 dan x2 = 0,416

Contoh 2

Maks Z = 2X1 + 3X2

Dengan kendala X1 + 2X2 ≤ 2

6X1 + 4X2 ≥ 24

x1 x2 x3 x4 x5

2 3 0 0 -M

X3 0

X5 -M

1 2 1 0 0

6 4 0 -1 1

2

24

-2 -3 0 0 0 -6 -4 0 1 0

-2-6M -3-4M 0 M 0

0-24

-24M

Tabel 1

x1 x2 x3 x4 x5

2 3 0 0 -M

X1 0

X5 -M

1 2 1 0 0

0 -8 -6 -1 1

2

12

0 1 2 0 0 0 8 6 1 0

4-12

Tabel 1

Contoh 3

Maks Z = 5X1 + 2X2

Dengan kendala 6X1 + X2 ≥ 6

4X1 + 3X2 ≥ 12

X1 + 2X2 ≥ 4

x1 x2 x3 x4 x5 x6 x7 x8

5 2 0 0 0 -M -M -M

X6 -M

X7 -M

X8 -M

6 1 -1 0 0 1 0 0

4 3 0 -1 0 0 1 0

1 2 0 0 -1 0 0 1

6

12

4

-5 -2 0 0 0 0 0 0 -11 -6 1 1 1 0 0 0

0 -22

Tabel 1

x1 x2 x3 x4 x5 x7 x8

5 2 0 0 0 -M -M

X1

X7

X8

1 1/6 -1/6 0 0 0 0

0 2,33 0,67 -1 0 1 0

0 1,83 0,167 0 -1 0 1

1

8

3

0 -1,167 -0,83 0 0 0 0 0 -4,16 -0,83 1 1 0 0

5 -11

Tabel 2

x1 x2 x3 x4 x5 x7

5 2 0 0 0 -M

X1

X7

X2

1 0 -0,18 0 0,09 0

0 0 0,45 -1 1,27 1

0 1 0,09 0 -0,54 0

0,727

4,181

1,637

0 0 -0,73 0 -0,64 0 0 0 -0,45 1 -1,27 0

6,910-4,180

Tabel 3

x1 x2 x3 x4 x5

5 2 0 0 0

X1

X5

X2

1 0 -0,214 0,0714 0

0 0 0,357 -0,785 1

0 1 0,286 -0,4286 0

0,428

3,284

3,429

0 0 -0,5000 -0,5001 0 0 0 -0,0002 0,0001 0

9,0010,0005

Tabel 4

x1 x2 x3 x4 x5

5 2 0 0 0

X4

X5

X2

1 0 -0,214 0,0714 0

0 0 0,357 -0,785 1

0 1 0,286 -0,4286 0

0,428

3,284

3,429

0 0 -0,5000 -0,5001 0

9,001

Tabel 5

x1 x2 x3 x4 x5

5 2 0 0 0

X4

X5

X2

14 0 -3,001 1 0

11 0 -2,000 0 1

6 1 -1,000 0 0

6,000

7,997

6,001

7,001 0 -2,001 0 0

12,00

Tabel 6

Contoh 3

Min Z = X1 + 2X2

Dengan kendala X1 + 3X2 ≥ 11

2X1 + X2 ≥ 9

≤

Maks Z = -X1 - X2

Dengan kendala X1 + 2X2 ≥ 5000

5X1 + 3X2 ≥ 12000

Contoh Soal

Min Z = x1 + 2x2

Kendala : x1 + 3x2 ≥ 11

2x1 + x2 ≥ 9

Maks Z = -x1 - x2

Kendala : x1 + 2x2 ≥ 5

5x1 + 3x2 ≥ 12

Dual-dual tak simetris

Primal

Min : Z = CT X


dan X ≥ 0

Dual

Maks : Z = BT W

Dengan kendala : ATW ≤ C

Primal

Maks : Z = CT X


dan X ≥ 0

Dual

Min : Z = BT W

Dengan kendala : ATW ≥ C

Min Z = 5x1 + 2x2 + x3

Kendala : 2x1 + 3x2 + x3 ≥ 20

6x1 + 8x2 + 5x3 ≥ 30

7x1 + x2 + 3x3 ≥ 40

x1 + 2x2 + 4x3 ≥ 50

Semua variabel tak negatifMaks Z = 20w1 + 30w2 +40w3 + 50w4

Kendala : 2w1 + 6w2 + 7w3 + w4 ≤ 5

3w1 + 8w2 + w3 + 2w4 ≤ 2

w1 + 5w2 + 3w3 + 4w4 ≤ 1

Semua variabel tak negatif

Primal

Dual

Contoh Soal :

Min Z = 10w1 + 30w2 + 40w3

Kendala : w1 + w2 + 2w3 ≥ 2

5w1 + 3w2 + 2w3 ≥ 1


Maks Z = 2x1 + x2

Kendala : x1 + 5x2 ≤ 10

x1 + 3x2 ≤ 6

2x1 + 2x2 ≤ 8


Bentuk standar

Maks Z = 2x1 + x2 +0x3 + 0x4 + 0x5

Kendala : x1 + 5x2 + x3 = 10

x1 + 3x2 + x4 = 6

2x1 + 2x2 + x5 = 8


Tabel simplek

x1 x2 x3 x4 x5

2 1 0 0 0

x3 0

x4 0

x5 0

1 5 1 0 0

1 1 0 1 0

2 2 0 0 1

10

6

8

-2 -1 0 0 0 0

Bentuk standar

Min Z = 10w1 + 30w2 + 40w3+ 0w4 + 0w5 + Mw6 + Mw7

Kendala : w1 + w2 + 2w3 – w4 + w6 = 2

5w1 + 3w2 + 2w3 – w5 + w7 = 1


Tabel simplek

w1 w2 w3 w4 w5 w6 w7

10 6 8 0 0 M M

w6 M

w7 M

1 1 2 -1 0 1 0

5 3 2 0 -1 0 1

2

1

10 6 8 0 0 0 0- 6 - 4 - 4 1 1 0 0

0 - 3

Latihan Soal

Contoh

Permasalahan RO

Perusahaan Minuman

Sebuah perusahaan minuman untuk memenuhi permintaan pelanggannya akan membuat lima buah jenis minuman campuran. Masing-masing jenis minuman memiliki spesifikasi standar sendiri sesuai yang disyaratkan konsumennya. Tersedia 10 buah bahan pembuat minuman dengan harga masing-masing dan jumlahnya juga terbatas. Perusahaan juga harus memenuhi jumlah pesanan. Permasalahan yang dihadapi oleh pihak menejemen adalah berapa jumlah masing-masing minuman yang harus dibuat agar semua kendala terpenuhi.

Produsen baja

Permalahan yang dihadapi adalah polusi udara pabriknya. Perusahaan memiliki dua sumber polusi yaitu tanur tinggi dan tanur terbuka. Para ahlinya memutuskan bahwa metode yang dapat digunakan ada tiga cara yaitu menaikkan tinggi tanur, memakai alat filter dalam cerobongnya dan memakai bahan bakar yang lebih bersih dan bermutu. Semua metode memiliki batas emisi sejauh mana polusi dapat dikurangi. Standar emisi juga telah ditentukan oleh pihak berwenang. Data biaya dan kapasitas penggunaan tanur ada.

Transportasi

Perusahaan pengalengan kacang polong memiliki beberapa pabrik. Perusahaan juga memiliki beberapa agen distribusi di beberapa wilayah. Manajemen tahu bahwa biaya transportasi termasuk yang tinggi dalam komponen biaya produksi. Maka pihak manejemen memutuskan untuk mencari pengurangan biaya yang optimal untuk pengirimannya. Biaya pengiriman dari pabrik dan agen sudah dihitung.

Model Teori Antrian

Sebuah perusahaan pergudangan melayani semua jenis barang untuk dapat disimpan digudang miliknya. Bila waktu sepi, karyawan yang bertugas cukup 1 orang. Namun bila suasana ramai, karyawan kewalahan untuk menangani konsumen. Maka pihak manejer memerlukan tambahan karyawan lagi. Saat kapan tambahan diperlukan dan berapa jumlahnya

Antrian

Sebuah perusahaan memakai 10 mesin yang identik dibagian produksinya. Karena mesin mudah macet, maka diputuskan untuk menempatkan operator mesin dalam jumlah tertentu pada 8 buah mesinnya. Distribusi sebuah mesin mengalami kerusakan dan distrubusi perbaikan dapat dicari. Perusahaan ingin menambah operator agar perusahaan berjalan baik. Kapan dan berapa orang

riset operasi (materi kuliah)

Documents