riset operasi program linier

43
Riset Operasi Program Linier Powerpoint Templates Page 1 Powerpoint Templates by Susi Setiawani

Upload: jack-kide

Post on 28-Dec-2015

266 views

Category:

Documents


21 download

DESCRIPTION

By Susi Setiawati

TRANSCRIPT

Riset OperasiProgram Linier

Powerpoint TemplatesPage 1

Powerpoint Templates

Program Linierby Susi Setiawani

Pengertian Riset Operasi

• Operations dapat didefinisikan sebagai tindakan-tindakanyang diterapkan pada beberapa masalah atau hipotesa.

• Research adalah suatu proses yang terorganisasi dalammencari kebenaran akan masalah atau hipotesa tadi

• riset operasi berkenaan dengan pengambilan keputusan

Powerpoint TemplatesPage 2

• riset operasi berkenaan dengan pengambilan keputusan yang optimal dalam, dan penyusunan model dari sistem-sistem baik yang diterministik maupun probabilistik yang berasal dari kehidupan nyata. Atau dunia pengelolaan atau dunia usaha yang memakai pendekatan ilmiah atau pendekatan sistematis disebut riset operasi (Operations

Resech).

Mathematic (Simbolic) ModelDibedakan menjadi 2 kelompok yaitu :

• Deterministik

Dibentuk dalam situasi kepastian (certainty). Model inimemerlukan penyederhanaan-penyederhanaan darirealitas karena kepastian jarang terjadi. Keuntungan model ini adalah dapat dimanipulasi & diselesaikan lebih mudah.

Powerpoint TemplatesPage 3

ini adalah dapat dimanipulasi & diselesaikan lebih mudah.

• Probabilistik

Meliputi kasus-kasus dimana diasumsikan ketidakpastian(uncertainty). Meskipun penggabungan ketidakpastiandalam model dapat menghasilkan suatu penyajian sistemnyata yang lebih realistis, model ini umumnya lebih sulituntuk dianalisa.

Cara Pembuatan ModelKadang-kadang, model yang pertama kali dibuat masih terlalu

rumit. Ada beberapa cara untuk membuat model menjadi lebih sederhana, misalnya :

• Melinierkan hubungan yang tidak linier

• Mengurangi banyaknya variabel atau kendala

• Mengubah sifat variabel, misalnya dari diskrit menjadi

Powerpoint TemplatesPage 4

• Mengubah sifat variabel, misalnya dari diskrit menjadi kontinyu

• Mengganti tujuan ganda menjadi tujuan tunggal

• Mengeluarkan unsur dinamik (membuat model menjadi statik)

• Mengasumsikan variabel random menjadi suatu nilai tunggal (deterministik)

Tahap-Tahap Dalam Riset Operasi

• Definisi Masalah (Identifikasi Model)

• Pembentukan Model (Penyusunan Model)

• Mencari Penyelesaian Masalah (Analisa Model)

• Validasi Model (Pengesahan Model)

Powerpoint TemplatesPage 5

• Validasi Model (Pengesahan Model)

• Penerapan Hasil Akhir (Implementasi Hasil)

DEFINISI PROGRAM LINIER (1)

• Program tidak ada hubungannya dengan program komputer.

• Program berarti memilih serangkaian tindakan/perencanaan untuk memecahkan masalah dalammembantu manajer mengambil keputusan.

• Contoh: masalah produksi, biaya, pemasaran, distribusi,

Powerpoint TemplatesPage 6

• Contoh: masalah produksi, biaya, pemasaran, distribusi, dan periklanan.

• Pimpinan perusahaan harus mampu memanfaatkan sumber daya yang ada untuk menetapkan jenis dan jumlah barang yang harus diproduksi sehingga diperolehkeuntungan maksimal atau digunakan biaya minimal.

DEFINISI PROGRAM LINIER (2)

• Program linear dan variasinya merupakan kelompok teknik analisis kuantitatif yang memakai model matematika (model simbolik). Artinya setiap penyelesaian masalah harus didahului dengan perumusan masalah ke dalam simbol-simbol matematika.

Powerpoint TemplatesPage 7

matematika.

• Dalam program linier, pada umumnya masalah berasal dari dunia nyata kemudian dibentuk menjadi model simbolik yang merupakan dunia abstrak yang dibuat mendekati kenyataan. Dikatakan linear karena peubah-peubah pembentuk model dianggap linear.

LANGKAH-LANGKAH (1)

1. Menentukan jenis permasalahan program linier– Jika permasalahan membicarakan keuntungan

(profit), maka jenis permasalahan PL adalah maksimalisasi.

– Jika permasalahan membicarakan biaya (cost), maka jenis permasalahan PL adalah minimalisasi.

Powerpoint TemplatesPage 8

maka jenis permasalahan PL adalah minimalisasi.– Jika ada informasi tentang selisih antara hasil

penjualan (sales) dan biaya dengan pokok pembicaraan profit, maka jenis permasalahannya adalah maksimalisasi.

LANGKAH-LANGKAH (2)

2. Mendefinisikan peubah keputusan (decision variable), yaitu pernyataan dalam permasalahan yang hendak dicari penyelesaiannya

Beberapa hal yang harus diperhatikan adalah:– Banyaknya koefisien peubah keputusan membantu dalam

mengidentifikasikan peubah-peubah keputusan.

Powerpoint TemplatesPage 9

mengidentifikasikan peubah-peubah keputusan.

– Jika x dimisalkan sebagai peubah keputusan berkaitan dengan kursi yang diproduksi, maka x ≠ kursi, tetapi x = banyaknya kursi yang diproduksi.

LANGKAH-LANGKAH (3)

3. Merumuskan fungsi tujuan/sasaran (objective function)

– Jenis permasalahan PL dan definisi peubah keputusan akan merumuskan fungsi tujuan.

Powerpoint TemplatesPage 10

keputusan akan merumuskan fungsi tujuan.

– Jika peubah keputusan terdefinisi dengan jelas, maka fungsi tujuan akan mudah ditetapkan.

LANGKAH-LANGKAH (4a)

4. Merumuskan model kendala/syarat/ batasan (constraint)

Dua pendekatan umum perumusan model kendala:

Powerpoint TemplatesPage 11

model kendala:

– Pendekatan “ruas kanan”

– Pendekatan “ruas kiri”

LANGKAH-LANGKAH (4b)

– Pendekatan ruas “kanan”

• Ruas kanan suatu kendala tunggal dan konstan.

• Maksimalisasi: ruas kanan sering menyatakan “total sumber daya yang ada”. Prosedur pembentukannya:

– Identifikasikan nilai total sumber daya dan sesuaikan tanda

Powerpoint TemplatesPage 12

– Identifikasikan nilai total sumber daya dan sesuaikan tanda pertidaksamaan dengan masing-masing total sumber daya, biasanya “≤”.

– Kelompokkan peubah keputusan yang terkait di sebelah kiri tanda pertidaksamaan .

– Tentukan koefisien setiap peubah keputusan. Model kendala terbentuk.

LANGKAH-LANGKAH (4b)

• Minimalisasi: ruas kanan sering menyatakan“minimal sumber daya yang dibutuhkan”. Prosedur idem, kecuali tanda pertidaksamaan, biasanya “≥”.

– Pendekatan “ruas kiri”

Powerpoint TemplatesPage 13

– Pendekatan “ruas kiri”

• Semua nilai koefisien dan peubah-peubah keputusan disusun dalam bentuk matriks. Setelah matriks ini terbentuk, identifikasikan nilai-nilai ruas kanan dan tambahkan tanda pertidaksamaan.

LANGKAH-LANGKAH (5)

5. Menetapkan syarat non negatif

– Setiap peubah keputusan dari kedua jenis permasalahan PL tidak boleh negatif (harus lebih besar atau sama dengan nol)

Powerpoint TemplatesPage 14

lebih besar atau sama dengan nol)

MODEL DASAR PL

• Maksimumkan atau minimumkan:

Z = c1x1 + c2x2 + ….+ cnxn (1)

• Memenuhi kendala-kendala:

a11x1 + a12x2 + …. + a1nxn ≥ atau ≤ b1 (2)

a21x1 + a22x2 + …. + a2nxn ≥ atau ≤ b2

Powerpoint TemplatesPage 15

a21x1 + a22x2 + …. + a2nxn ≥ atau ≤ b2

.

.

am1x1 + am2x2 + …. + amnxn ≥ atau ≤ bm

dan xj ≥ 0 untuk j = 1,2,…,n. (3)

PENYELESAIAN (1)

• Aplikasi pemrograman linear di dunia nyata cukup banyak, misalnya di bidang industri, kedokteran, transportasi, ekonomi, dan pertanian. Masalah pemrograman linear dapat diselesaikan dengan berbagai cara/algoritma, seperti metode grafik, metode simpleks, revised simplex method, dan algoritma

Powerpoint TemplatesPage 16

simpleks, revised simplex method, dan algoritma Karmakar. Algoritma yang akan dibahas di sini adalah metode grafik dan metode simpleks. Masalah program linear dua variabel (n=2) diselesaikan dengan metode grafik, sedangkan untuk n≥2 diselesaikan dengan metode simpleks.

METODE GRAFIK

• Masalah program linear dengan dua variabel dapat diselesaikan dengan metode grafik.

• Meskipun dalam praktek masalah program linear jarang yang hanya memuat dua peubah,

Powerpoint TemplatesPage 17

linear jarang yang hanya memuat dua peubah, tetapi metode grafik mempermudah orang dalam memahami pengertian-pengertian yang timbul dalam program linear.

METODE GRAFIK (Contoh 1)

• Selesaikan masalah program linear berikut ini dengan metode grafik:

Maksimumkan Z = 5x1 + 4x2

dengan kendala 6x1 + 4x2 ≤ 24

Powerpoint TemplatesPage 18

dengan kendala 6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

x1, x2 ≥ 0

METODE GRAFIK (Peny. 1a)

1

3

Powerpoint TemplatesPage 19

2

3

METODE GRAFIK (Peny. 1b)

Powerpoint TemplatesPage 20

METODE GRAFIK (Contoh 2)

• Selesaikan masalah program linear berikut ini dengan metode grafik:

Minimumkan Z = 20x1 + 30x2

dengan kendala 2x + x ≥ 12

Powerpoint TemplatesPage 21

dengan kendala 2x1 + x2 ≥ 12

5x1 + 8x2 ≥ 74

x1 + 6x2 ≥ 12

x1, x2 ≥ 0

METODE GRAFIK (Peny. 2a)

Powerpoint TemplatesPage 22

METODE GRAFIK (Peny. 2b)

Powerpoint TemplatesPage 23

KEJADIAN KHUSUS PL (1)

• Masalah program linear belum tentu mempunyai satu penyelesaian optimal.

• 3 kejadian khusus dari masalah PL:1. Mempunyai beberapa penyelesaian

Contoh :

Powerpoint TemplatesPage 24

Contoh :

Maksimumkan Z = 300x1 + 200x2

dengan kendala : 6x1 + 4x2 ≤ 240x1 + x2 ≤ 50x1 , x2 ≥ 0

KEJADIAN KHUSUS PL (2)

2. Tidak mempunyai penyelesaian optimal (infeasible solution).

Contoh :

Maksimumkan Z = x + x

Powerpoint TemplatesPage 25

Maksimumkan Z = x1 + x2

dengan kendala : x1 + x2 ≤ 4

x1 - x2 ≥ 5

x1 , x2 ≥ 0

KEJADIAN KHUSUS PL (3)

3. Mempunyai penyelesaian tak terbatas (unbounded solutions) � tidak mempunyai penyelesaian optimal.

Contoh :

Powerpoint TemplatesPage 26

Contoh :

Maksimumkan Z = 2x1 - x2

dengan kendala : x1 - x2 ≤ 1

2x1 + x2 ≥ 6

x1 , x2 ≥ 0

CONTOH KASUS

• Suatu perusahaan memproduksi pembersih mobil X dan polisher Y dan menghasilkan profit $10 untuk setiap X dan $30 untuk setiap Y. Kedua produk membutuhkan pemrosesan melalui mesin-mesin yang sama A dan B, tetapi X membutuhkan 4 jam di A dan 8 jam di B, sedangkan Y membutuhkan 6 jam di A dan 4 jam di B.

Powerpoint TemplatesPage 27

sedangkan Y membutuhkan 6 jam di A dan 4 jam di B. Dalam minggu-minggu akan datang, mesin A dan B memiliki kapasitas masing-masing 12 dan 16 jam. Anggap ada permintaan untuk kedua produk, berapa banyak produk dari keduanya harus dihasilkan untuk memaksimalkan profit ?

Soal

• Suatu pabrik farmasi menghasilkan dua macam kapsul obat flu yang diberi nama Fluin dan Fluon. Masing-masing memuat tiga unsur utama. 1 kapsul Fluin mengandung 2 gr aspirin, 5 gr bikarbonat, 1 gr kodein. 1 kapsul Fluon mengandung 1 gr aspirin, 8 gr bikarbonat, 6 gr kodein. Seseorang yang sakit flu biasa akan

Powerpoint TemplatesPage 28

6 gr kodein. Seseorang yang sakit flu biasa akan sembuh dalam 3 hari, minimum menelan 12 gr aspirin, 74 gr bikarbonat, 24 gr kodein. Harga Fluin Rp 200 dan Fluon Rp 300, berapa kapsul yang harus dibeli supaya sembuh?

PROGRAM LINEAR

METODE SIMPLEX

Powerpoint TemplatesPage 29

Bentuk Matematis

• Maksimumkan Z = 3X1 + 5X2

• Batasan (constrain)

(1) 2X1 ≤ 8

Powerpoint TemplatesPage 30

(2) 3X2 ≤ 15

(3) 6X1 + 5X2 ≤ 30

LINEAR PROGRAMMING METODE SIMPLEKS

• Langkah-langkah metode simpleks

Langkah 1: Mengubah fungsi tujuan dan batasan-batasan

• Fungsi tujuan

Z = 3X + 5X diubah menjadi Z - 3X - 5X = 0.

Powerpoint TemplatesPage 31

Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.

• Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)

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

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

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

Slack variabel adalah variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan

LINEAR PROGRAMMING METODE SIMPLEKS

• Fungsi tujuan : Maksimumkan Z - 3X1 - 5X2 = 0

• Fungsi batasan

(1) 2X1 + X3 = 8

Powerpoint TemplatesPage 32

1 3

(2) 3X2 + X4 = 15

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

Langkah 2:

Menyusun persamaan-persamaan di dalam tabel

Beberapa Istilah dlm Metode Simplek

• NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda

sama dengan ( = ). Untuk batasan 1 sebesar 8, batasan 2 sebesar

15, dan batasan 3 sebesar 30.

• Variabel dasar adalah variabel yang nilainya sama dengan sisi

Powerpoint TemplatesPage 33

• Variabel dasar adalah variabel yang nilainya sama dengan sisi

kanan dari persamaan. Pada persamaan 2X1 + X3 = 8, kalau belum

ada kegiatan apa-apa, berarti nilai X1 = 0, dan semua kapasitas

masih menganggur, maka pengangguran ada 8 satuan, atau nilai X3

= 8. Pada tabel tersebut nilai variabel dasar (X3, X4, X5) pada fungsi

tujuan pada tabel permulaan ini harus 0, dan nilainya pada batasan-

batasan bertanda positif

1. Tabel simpleks yang pertama

Variabel

Z = 3X1 + 5X2 diubah menjadi Z Z = 3X1 + 5X2 diubah menjadi Z -- 3X1 3X1 -- 5X2 = 0.5X2 = 0.

(1) 2X1(1) 2X1 ≤≤ 8 menjadi 8 menjadi 2X12X1 + X3 + X3 = 8= 8(2) 3X2(2) 3X2 ≤≤ 15 menjadi 15 menjadi 3X23X2 + X4 + X4 = 15= 15(3) 6X1 + 5X2(3) 6X1 + 5X2 ≤≤ 30 menjadi 30 menjadi 6X1 + 6X1 + 5X25X2 + X5+ X5 = 30= 30

Powerpoint TemplatesPage 34

VariabelDasar

Z X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

Langkah 3: Memilih kolom kunci

• Kolom kunci adalah kolom yang

merupakan dasar untuk mengubah tabel

simplek. Pilihlah kolom yang mempunyai

Powerpoint TemplatesPage 35

nilai pada garis fungsi tujuan yang

bernilai negatif dengan angka terbesar.

Dalam hal ini kolom X2 dengan nilai pada

baris persamaan tujuan –5. Berilah tanda

segi empat pada kolom X2, seperti tabel

berikut

VariabelDasar

Z X1 X2 X3 X4 X5 NKKeterangan

(Indeks)

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

2 Tabel simpleks: pemilihan kolom kunci pada tabel pertama

Powerpoint TemplatesPage 36

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

JikaJika suatusuatu tabeltabel sudahsudah tidaktidak memilikimemiliki nilainilai negatifnegatif padapada barisbaris fungsifungsi tujuan,tujuan, berartiberartitabeltabel ituitu tidaktidak bisabisa dioptimalkandioptimalkan lagilagi (sudah(sudah optimal)optimal)..

Langkah 4: Memilih baris kunci

• Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci.

• Indeks = (Nilai Kolom NK) / (Nilai kolom kunci)Untuk baris batasan 1 besarnya indeks = 8/0 = ∼, baris batasan 2 = 15/3 = 5, dan baris batasan 3 = 30/5 = 6. Pilih baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2 yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam baris kunci disebut angka kunci

Powerpoint TemplatesPage 37

juga masuk dalam baris kunci disebut angka kunci

Langkah 5: Mengubah nilaiLangkah 5: Mengubah nilai--nilai baris kunci nilai baris kunci

Nilai baris kunci diubah dengan cara membaginya dengan angka kunci,seperti tabel 3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3 = 1/3; 0/3 = 0;15/3 = 5). Gantilah variabel dasar pada baris itu dengan variabel yangterdapat di bagian atas kolom kunci (X2).

3 Tabel simpleks: Cara mengubah nilai baris kunci

VariabelDasar

Z X1 X2 X3 X4 X5 NKKeterangan (Indeks)

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X 0 6 5 0 0 1 30

8/0 = ∞

15/3 = 5

30/5 = 6

Powerpoint TemplatesPage 38

X5 0 6 5 0 0 1 30

Z

X3

X2

X5

0/3 0/3 3/3 0/3 1/3 0/3 15/3

30/5 = 6

0 0 1 0 01/3 15/3

LangkahLangkah 6: Mengubah nilai6: Mengubah nilai--nilai selain pada baris kunci nilai selain pada baris kunci

Rumus :Rumus :

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

[-3 -5 0 0 0, 0 ]

(-5) [ 0 1 0 1/3 0, 5 ] ( - )

Nilai baru = [-3 0 0 5/3 0, 25]

BarisBaris pertamapertama (Z)(Z)

Powerpoint TemplatesPage 39

Nilai baru = [-3 0 0 5/3 0, 25]

Baris keBaris ke--2 (batasan 1)2 (batasan 1)

[2 0 1 0 0, 8 ]

(0) [ 0 1 0 1/3 0, 5 ] ( - )

Nilai baru = [2 0 1 0 0, 8]

Baris ke-4 (batasan 3)

[ 6 5 0 0 1, 30 ]

(5) [ 0 1 0 1/3 0, 5 ] ( - )

Nilai baru = [ 6 0 0 -5/3 1, 5 ]

Variabel Dasar

Z X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0

Tabel pertama nilai lama dan tabel kedua nilai baruTabel pertama nilai lama dan tabel kedua nilai baru

Powerpoint TemplatesPage 40

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

Z 1 -3 0 0 5/3 0 25

X3 0 2 0 1 0 0 8

X2 0 0 1 0 1/3 0 5

X5 0 6 0 0 -5/3 1 5

VariabelDasar

Z X1 X2 X3 X4 X5 NKKeterangan

(Indeks)

Z 1 -3 0 0 5/3 0 25

X3 0 2 0 1 0 0 8

Langkah 7: Melanjutkan perbaikan

Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai

negatif

= 8/2 = 4

Powerpoint TemplatesPage 41

X3 0 2 0 1 0 0 8

X4 0 0 1 0 1/3 0 5

X5 0 6 0 0 -5/3 1 5

Z 1

X3 0

X2 0

X1 0 6/6 0 0 -5/18 1/6 5/6

6/6 0/6 0/6 (-5/3)/6 1/6 5/6

= 8/2 = 4

= 5/6 (minimum)

Nilai baruNilai baru

BarisBaris keke--11

[-3 0 0 5/3 0, 25 ]

(-3) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = [ 0 0 0 5/6 ½, 271/2]

[ 2 0 1 0 0, 8 ]

Baris keBaris ke--2 (batasan 1)2 (batasan 1)

Powerpoint TemplatesPage 42

[ 2 0 1 0 0, 8 ]

(2) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = 0 0 1 5/9 -1/3, 61/3]

BarisBaris keke--33 tidaktidak berubahberubah karenakarena nilainilai padapada kolomkolom kuncikunci == 00

[ 0 1 0 1/3 0, 5 ]

(0) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = 0 1 0 1/3 0, 5]

Tabel simpleks final hasil perubahanTabel simpleks final hasil perubahan

Variabel Dasar

Z X1 X2 X3 X4 X5 NK

Z 1 0 0 0 5/6 ½ 271/2

X3 0 0 0 1 5/9 -1/3 61/3

X2 0 0 1 0 1/3 0 5

X1 0 1 0 0 -5/18 1/6 5/6

Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak

Powerpoint TemplatesPage 43

Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal

Dari tabel final didapatDari tabel final didapat

XX11 = 5/6= 5/6XX22 = 5= 5ZZmaksimummaksimum = 27= 2711//22