2

18/09/2013

PENERAPAN PROGRAM LINIER dalam OPTIMASI PRODUKSI

Ekonomi Teknik / Sigit Prabawa / 1

MASALAH yg banyak dihadapi oleh INDUSTRI adalah BAGAIMANA MENGGUNAKAN atau MENENTUKAN ALOKASI PENGGUNAAN SUMBER DAYA YG UMUMNYA TERBATAS,, untuk DAPAT MEMPEROLEH TERBATAS SUATU HASIL yang OPTIMAL HASIL YG OPTIMAL merupakan TUJUAN untuk MEMAKSIMALKAN KEUNTUNGAN atau MEMINIMALKAN BIAYA Ekonomi Teknik / Sigit Prabawa / 2

1

18/09/2013

PROGRAM LINIER

Linear Programming Salah satu TEKNIK OPTIMASI yg banyak berkaitan dg PENGGUNAAN SUMBER DAYA MULAI DIKEMBANGKAN oleh GEORGE DANTZIG pd th 1947 dg suatu teknik yg disebut METODE SIMPLEX (simplex (simplex method) method) Ekonomi Teknik / Sigit Prabawa / 3

PERSAMAAN dalam PROGRAM LINIER FUNGSI TUJUAN (maksimum atau minimum) menunjukkan tujuan yg ingin dicapai PERSAMAAN KENDALA (constraints (constraints)) menunjukkan kondisi keterbatasan yang ada Ekonomi Teknik / Sigit Prabawa / 4

2

18/09/2013

METODE dalam PROGRAM LINIER Metode GRAFIK Metode SIMPLEX


METODE GRAFIK Untuk MEMECAHKAN MASALAH PROGRAM LINIER dengan DUA PEUBAH Untuk TIGA PEUBAH sebenarnya MASIH DAPAT DITERAPKAN, tetapi AGAK RUMIT karena HARUS MENGGUNAKAN GRAFIK TIGA DIMENSI yg sering sulit untuk diikuti dg jelas Ekonomi Teknik / Sigit Prabawa / 6

3

18/09/2013

Contoh 1 Sebuah industri menghasilkan suatu jenis produk dg 2 mutu, yaitu mutu A dan mutu B. Untuk menghasilkan produk dg 2 mutu tsb digunakan 3 buah mesin, dg perlakuan yg berbeda pd tiap mesin, yaitu dlm hal lamanya proses pd setiap mesin seperti pd tabel berikut :

Setiap mesin hanya dpt digunakan tdk lebih dr 8 jam per hari. Keuntungan yg diperoleh dr tiap produk adalah Rp 5 untuk produk dg mutu A, dan Rp 8 untuk produk dg mutu B. Berapa jumlah produk A dan B yang optimal ? Ekonomi Teknik / Sigit Prabawa / 7

Penyelesaian Peubah yg blm diketahui dan akan dicari adalah jumlah produk ( P ) dg mutu A dan B setiap harinya. Fungsi tujuan : Maksimumkan P = 5A + 8B Kendala : Kondisi pembatas

jam kerja mesin 8 jam per hari (480 menit/hari)

40A + 30B ≤ 480 (kendala mesin 1) 24A + 32B ≤ 480 (kendala mesin 2) 20A + 24B ≤ 480 (kendala mesin 3)


4

18/09/2013

Bentuk persamaan selengkapnya : Maksimumkan Kendala

P = 5A + 8B 40A + 30B ≤ 480 (kendala mesin 1) 24A + 32B ≤ 480 (kendala mesin 2) 20A + 24B ≤ 480 (kendala mesin 3) A≥0 B≥0

Alternatif penyelesaian : 1. Hanya memproduksi mutu A 2. Hanya memproduksi mutu B 3. Memproduksi mutu A dan B ALTERNATIF 1 Mesin 1 : 40A ≤ 480 , atau A ≤ 12 Mesin 2 : 24A ≤ 480 , atau A ≤ 20 Mesin 3 : 20A ≤ 480 , atau A ≤ 24

Jika hanya A saja yang diproduksi, maka tdk boleh lebih dr 12 Ekonomi Teknik / Sigit Prabawa / 9

Keuntungan yg diperoleh = 12 x Rp 5 = Rp 60 / hari ALTERNATIF 2 Mesin 1 : 30B ≤ 480 , atau B ≤ 16 Mesin 2 : 32B ≤ 480 , atau B ≤ 15 Mesin 3 : 24B ≤ 480 , atau B ≤ 20

Jika hanya B saja yang diproduksi, maka tdk boleh lebih dr 15

Keuntungan yg diperoleh = 15 x Rp 8 = Rp 120 / hari ALTERNATIF 3 Semua persamaan kendala yang ada digambarkan di dalam suatu grafik yang sama.


5

18/09/2013

30

25

20

Produk A

15

10

5

0 0

5

10

15

20

Mesin 1 Mesin 2

-5

Mesin 3 -10

Produk B


Ternyata memproduksi mutu B saja akan memberikan keuntungan paling maksimal Titik kombinasi A = 1,714 dan B = 13,714 diperoleh dr titik potong antara persamaan kendala mesin 1 dan 2. Apabila perusahaan akan memproduksi dalam 2 mutu, maka kombinasi tsb merupakan kombinasi terbaik, tetapi bukan yg paling menguntungkan Ekonomi Teknik / Sigit Prabawa / 12

6

18/09/2013

METODE SIMPLEX Untuk MEMECAHKAN MASALAH UMUM PROGRAM LINIER. SUATU PROSEDUR ALJABAR, yang melalui SERANGKAIAN OPERASIOPERASI-OPERASI BERULANG DAPAT MEMECAHKAN SUATU MASALAH yang terdiri dari TIGA PEUBAH atau LEBIH Ekonomi Teknik / Sigit Prabawa / 13

Contoh 2 : Sebuah perusahaan memproduksi 2 jenis produk, yaitu X dan Y. Setiap produk X memberikan keuntungan Rp 4,4,dan produk Y memberikan keuntungan Rp 8,8,-. Satu unit X memerlukan waktu proses 8 jam pd mesin A dan 4 jam pd mesin B. Produk Y memerlukan 12 jam pd mesin A, 12 jam pd mesin B, dan 2 jam pd mesin C. Mesin A mempunyai kapasitas kerja maksimum 240 jam per bulan, mesin B 144 jam per bulan, dan mesin C hanya 20 jam per bulan. Berapa jumlah produk X dan Y yg dihasilkan supaya perusahaan dpt memperoleh keuntungan yg maksimum ? Ekonomi Teknik / Sigit Prabawa / 14

7

18/09/2013

Penyelesaian LANGKAH I : Merumuskan masalah dalam bentuk persamaan Fungsi tujuan : Maksimumkan Z = 4X + 8Y Persamaan Kendala : 8X + 12Y ≤ 240 (kendala mesin A) 4X + 12Y ≤ 144 (kendala mesin B) 2Y ≤ 20 (kendala mesin C) A≥0 B≥0


LANGKAH II : Menyusun peubah slack Perumusan pd Langkah I diubah, sehingga tanda ketidaksamaan ( ≤ ) berubah menjadi persamaan ( = ). Untuk itu diperlukan tambahan peubah yang disebut dg peubah slack (slack variable), variable), dg simbol S1, S2, S3, dan seterusnya, yang menunjukkan jumlah sumber daya yang tidak digunakan. 8X + 12Y + S1 = 240 4X + 12Y + S2 = 144 2Y + S3 = 20 Shg persamaan selengkapnya menjadi : Z = 4X + 8Y + 0 S1 + 0 S2 + 0 S3 8X + 12Y + 1 S1 + 0 S2 + 0 S3 = 240 4X + 12Y + 0 S1 + 1 S2 + 0 S3 = 144 0X + 2Y + 0 S1 + 0 S2 + 1 S3 = 20 Ekonomi Teknik / Sigit Prabawa / 16

8

18/09/2013

Tabel Simplex Awal

Tabel menunjukkan keadaan dimana perusahaan tidak atau belum berproduksi, shg nilai Cj semua sama dg nol, karena kolom ini menunjukkan keuntungan dr peubah pd kolom kedua (msh berisi peubah slack, yg tdk memberikan keuntungan). Ekonomi Teknik / Sigit Prabawa / 17

• Kolom ke-3 s/d ke-7 menunjukkan koefisien peubah dari setiap persamaan kendala. • Kolom terakhir (kuantitas/Q) merupakan jumlah sumber daya yg tersedia dalam setiap mesin. • Baris Zj merupakan besarnya keuntungan kotor yg dihasilkan melalui pemasukan satu unit peubah. • Nilai Zj di bawah kolom kuantitas adalah keuntungan total. • Dlm tabel awal tsb, semua nilai Zj sama dengan nol karena tdk ada produk yg dihasilkan. • Baris paling bawah menunjukkan keuntungan bersih per unit yg didapatkan melalui pemasukan per unit peubah tertentu. Baris ini ditandai sebagai baris Cj–Zj Ekonomi Teknik / Sigit Prabawa / 18

9

18/09/2013

Perhitungan Zj dan Cj– Cj–Zj


LANGKAH III : Menentukan kolom peubah pengganti Dicari nilai Cj – Zj yang positip Dalam contoh terdapat dua nilai positip. Karena dlm masalah ini tujuannya adalah memaksimumkan keuntungan (maksimalisasi), maka dicari nilai yg terbesar, yaitu 8, yg terdapat pd kolom peubah Y. Y. LANGKAH IV : Menentukan peubah yg diganti Untuk menentukan baris peubah yg akan diganti, perlu dilakukan perhitungan dg membagi setiap bilangan dlm kolom Q dg kolom terpilih (peubah Y), dan dipilih hasil bagi yang terkecil Baris S1 : 240/12 = 20 Baris S2 : 144/12 = 12 Baris S3 : 20/2 = 10 Karena hasil bagi terkecil adalah 10 maka S3 akan diganti. diganti. Ini merupakan jumlah Y maksimum yg dpt dimasukkan dlm penyelesaian, yg berarti bahwa produksi lebih dr 10 unit Y akan melebihi kapasitas mesin C. Ekonomi Teknik / Sigit Prabawa / 20

10

18/09/2013

LANGKAH V : Menghitung nilai baris baru Baris terpilih (baris S3) digantikan dg peubah dr kolom terpilih (Y). Nilai untuk baris ini diperoleh dg membagi setiap nilai sekarang dg nilai dlm kolom Y pd baris yg sama, yaitu angka 2. Nilai ini disebut elemen perpotongan (intersectional element), element), karena terletak pd perpotongan antara baris dan kolom terpilih.

Perubahan baris lama menjadi baris baru (Y) adalah sbb. : Baris lama ( S3 ) : 0 Baris baru ( Y ) : 0

2 1

0 0

0 1 20 0 1/2 10

Nilai kolom Cj pd unsur baris yg diganti (nilai lama 0), diubah menjadi nilai dr baris Cj pd kolom yg menggantikan, yaitu dr nilai keuntungan Y (nilainya 8). Ekonomi Teknik / Sigit Prabawa / 21

LANGKAH VI : Mengganti nilai baris lainnya Diupayakan nilai pd baris yg lain (S1 dan S2), unsur pd kolom terpilih diubah menjadi nol. Unsur ini adalah 12 untuk S1 dan 12 untuk S2 (kebetulan sama). Perhitungan dilakukan dg cara semua unsur pd baris yg diubah dikurangi dg semua unsur pd baris baru sebelumnya (baris S3 yg telah diubah menjadi baris Y), dg dikalikan suatu faktor yg besarnya sama dg unsur pd baris tsb yg harus dibuat nol.


11

18/09/2013

Tabel Simplex Kedua ( hasil perhitungan langkah 3 – 6 )

Keuntungan yg diperoleh Rp 80,Perbaikan kombinasi msh mungkin dilakukan karena msh ada nilai positip pd baris Cj – Zj Ekonomi Teknik / Sigit Prabawa / 23

Tahap berikutnya diulang lagi dr langkah 3. Dari Tabel Simplex Kedua diperoleh nilai positip tertinggi dr baris Cj – Zj adalah angka 4, atau kolom peubah X. Dari langkah 4, kolom Q menghasilkan nilai : Baris S1 : 120/8 = 15 Baris S2 : 24/4 = 6 Baris Y : 10/0 = ∞ Karena nilai terkecil di atas adalah 6, maka baris yg diganti adalah baris kedua (baris S2), dan digantikan dg peubah X. Dengan menggunakan cara yg sama untuk langkahlangkah-langkah berikutnya maka diperoleh Tabel Simplex Ketiga.


12

18/09/2013

Tabel Simplex Ketiga

Keuntungan yg diperoleh Rp 104,Perbaikan kombinasi msh mungkin dilakukan karena msh ada nilai positip pd baris Cj – Zj Ekonomi Teknik / Sigit Prabawa / 25

Tabel Simplex Keempat

Keuntungan yg diperoleh Rp 128,Perbaikan kombinasi tdk dilakukan karena tdk ada lagi nilai positip pd baris Cj – Zj : OPTIMAL X

24 unit

Y

4 unit Ekonomi Teknik / Sigit Prabawa / 26

13

18/09/2013

Masalah TRANSPORTASI SALAH SATU MASALAH KHUSUS dlm MASALAH PROGRAM LINIER Ada sejumlah TITIK ASAL yg bersifat sbg TITIK PRODUSEN, yang perlu mendistribusikan sejumlah barang ke beberapa TITIK TUJUAN yang bersifat sbg TITIK KONSUMEN Umumnya menyangkut ALOKASI PENYEBARAN atau PENGANGKUTAN BARANG dr titik asal ke titik tujuan Ekonomi Teknik / Sigit Prabawa / 27

Contoh 3 : Sebuah perusahaan pupuk mempunyai 2 pabrik yg terletak di kota A dan B. Pabrik tsb mempunyai kapasitas masingmasing-masing 6 dan 8 ton per hari. Kedua pabrik tsb mempunyai 2 daerah pemasaran, yaitu kota C dan D, yg masingmasing-masing memerlukan 10 dan 4 ton pupuk per hari. Ongkos angkut ditentukan sebesar Rp 1000/ton/km. Skema jalan angkutan dan jarak yg harus ditempuh digambarkan sebagai berikut : Ekonomi Teknik / Sigit Prabawa / 28

14

18/09/2013

Dari gambar di atas dpt dilihat beberapa kemungkinan cara pengangkutan yg dpt dilakukan, yaitu dr A C D D B

C

D

D Ekonomi Teknik / Sigit Prabawa / 29

Penyusunan tabel dimulai dg asumsi bahwa semua produk dr A diangkut ke C semaksimal mungkin. Karena C memerlukan 10 ton, sedangkan A memproduksi 6 ton, maka yg dpt diangkut maksimal adalah 6 ton, shg dr A ke D tdk ada yg perlu diangkut. Sedangkan dr B perlu diangkut ke C sebanyak 4 ton untuk menambah kekurangan dari kebutuhan sebanyak 10 ton, dan sisanya 4 ton diangkut ke D. Alternatif berikutnya dilakukan dg mengubah jumlah yg dibawa dr A ke C menjadi 5 ton, dstnya mengikuti kendala yg ada, yaitu jumlah produk dan kebutuhan. Ekonomi Teknik / Sigit Prabawa / 30

15

18/09/2013

Penyelesaian Contoh 3 dg Metode SIMPLEX

Fungsi tujuan : Minimumkan biaya angkut Z = 150.000 XAC + 100.000 XAD + 80.000 XBC + 75.000 XBD Persamaan Kendala : XAC + XAD = 6 XBC + XBD = 8 XAC + XBC = 10 XAD + XBD = 4

(ketersediaan di kota A) (ketersediaan di kota B) (ketersediaan di kota C) (ketersediaan di kota D)


16

2

Recommend Documents