linear programming

21
BAB III PEMBAHASAN DAN ANALISIS 3.1. Pembahasan Pada bab ini akan dibahas tentang pengambilan sampel produk dengan data yang sudah ada. Dengan data yang sudah ditentukan, kemudian dihitung dan dianalisa untuk mencari keuntungan yang maksimal pada produk tersebut. 3.1.1. Studi Kasus PT. Usaha Baru mempunyai sebuah mesin untuk membuat produk Majalah dan Tabloid. Masing-masing produk membutuhkan waktu operasi sesuai pada tiap operasinya. Tabel berikut menunjukkan kebutuhan operasi dan total waktu yang tersedia pada tiap-tiap operasinya selama 1 bulan. Pertimbangkan pada pemasaran yang ada sekarang, perusahaan dapat menjual sebanyak yang diproduksi dari Majalah dan Tabloid. Harga masing- masing produk yaitu Rp 8.000,- untuk Majalah dan Rp 7.000,- untuk Tabloid. Manajemen ingin memutuskan perencanaan produksi terbaik untuk memaksimalkan total pendapatan untuk bulan berikutnya : III-1

Upload: endoenk

Post on 24-Jun-2015

538 views

Category:

Documents


8 download

TRANSCRIPT

Page 1: Linear Programming

BAB III

PEMBAHASAN DAN ANALISIS

3.1. Pembahasan

Pada bab ini akan dibahas tentang pengambilan sampel produk dengan

data yang sudah ada. Dengan data yang sudah ditentukan, kemudian dihitung dan

dianalisa untuk mencari keuntungan yang maksimal pada produk tersebut.

3.1.1. Studi Kasus

PT. Usaha Baru mempunyai sebuah mesin untuk membuat produk

Majalah dan Tabloid. Masing-masing produk membutuhkan waktu operasi sesuai

pada tiap operasinya. Tabel berikut menunjukkan kebutuhan operasi dan total

waktu yang tersedia pada tiap-tiap operasinya selama 1 bulan. Pertimbangkan

pada pemasaran yang ada sekarang, perusahaan dapat menjual sebanyak yang

diproduksi dari Majalah dan Tabloid. Harga masing-masing produk yaitu Rp

8.000,- untuk Majalah dan Rp 7.000,- untuk Tabloid. Manajemen ingin

memutuskan perencanaan produksi terbaik untuk memaksimalkan total

pendapatan untuk bulan berikutnya :

Tabel 3.1. Unit Operation Times in Hours

Operasi

Jenis Produksi (menit) Kapasitas

(menit)Majalah Tabloid

Pemotongan 2 3 24

Pengeleman 2 1 16

Cetak 1 4 27

Profit per unit 8000 7000

Dari data diatas selesaikanlah dengan metode simpleks dan grafik

III-1

Page 2: Linear Programming

III-2

3.1.2. Perhitungan Manual

Dari data diatas kita dapat menyelesaikan dengan dua cara yaitu metode

grafik dan metode simpleks. Dimana metode grafik digunakan untuk

menyelesaikan variabel keputusan sama dengan dua, sedangkan metode simpleks

digunakan untuk menyelesaikan variabel keputusan dua atau lebih.

Formulasi Linear Programming:

a. Variabel Keputusan

Majalah : X1

Tabloid : X2

b. Fungsi Objektif

Maksimum Z = 8000X1 + 7000X2

c. Kendala

2X1 + 3X2 24

2X1 + X2 16

X1 + 4 X2 27

X1 ≥ 0 (kendala non negatif pertama)

X2 ≥ 0 (kendala non negatif kedua)

3.1.2.1.Penyelesaian dengan Metode Grafik

Langkah pertama dalam menyelesaikan dengan metode grafik adalah

menggambarkan fungsi kendalanya, kemudian merubah tanda pertidaksamaan

menjadi tanda persamaan sebagai berikut:

Kendala I : 2X1 + 3X2 = 24

* Memotong sumbu X1 pada saat X2 = 0

2X1 + 0 = 24

X1 =

X1 = 12

* Memotong sumbu X2 pada saat X1 = 0

0 + 3X2 = 24

X2 =

Page 3: Linear Programming

III-3

X2 = 8

Kendala I memotong sumbu X1 pada titik (12,0) dan memotong

sumbu X2 pada titik (0,8)

Kendala II : 2X1 + X2 = 16

* Memotong sumbu X1 pada saat X2 = 0

2X1 + 0 = 16

X1 =

X1 = 8

* Memotong sumbu X2 pada saat X1 = 0

0 + X2 = 16

X2 = 16

Kendala II memotong sumbu X1 pada titik (8,0) dan memotong

sumbu X2 pada titik (0,16)

Kendala III: X1 + 4X2 = 27

* Memotong sumbu X1 pada saat X2 = 0

X1 + 0 = 27

X1 = 27

* Memotong sumbu X2 pada saat X1 = 0

0 + 4X2 = 27

X2 =

X2 = 6.75

Kendala III memotong sumbu X1 pada titik (27,0) dan memotong

sumbu X2 pada titik (0,6.75)

Tabel 3.2. Titik Koordinat

Variabel Titik koordinat

Page 4: Linear Programming

III-4

2X1 + 3X2 = 24 (12,0) dan (0,8)

2X1 + X2 = 16 (8,0) dan (0,16)

X1 + 4X2 = 27 (27,0) dan (0,6.75)

Gambar 3.1. Grafik Area Layak

Untuk mencari titik potong kedua kendala bisa dicari dengan cara substitusi atau

eliminasi. Untuk mencari titik potong B dan C adalah sebagai berikut:

Titik potong B:

2X1 + 3X2 = 24 x 1 2X1 + 3X2 = 24

X1 + 4X2 = 27 x 2 2X1 + 8X2 = 54

0 - 5X2 = -30

X2 =

X2 = 6

X1 + 4X2 = 27 X1 + 4(6) = 27

X1 = 27 – 24

X1 = 3

Titik potong C:

Page 5: Linear Programming

III-5

2X1 + 3X2 = 24 x 1 2X1 + 3X2 = 24

2X1 + X2 = 16 x 1 2X1 + X2 = 16

0 + 2X2 = 8

X2 =

X2 = 4

2X1 + X2 = 16 2X1 + 4 = 16

2X1 = 16-4

2X1 = 12

X1 =

X1 = 6

Jadi titik potong B adalah (3,6) dan titik potong C adalah (6,4)

Titik A: (0,6.75)

Z = 8000X1 + 7000X2

= 8000(0) + 7000(6.75)

= 47250

Titik B: (3,6)

Z = 8000X1 + 7000X2

= 8000(3) + 7000(6)

= 66000

Titik C: (6,4)

Z = 8000X1 + 7000X2

= 8000(6) + 7000(4)

= 76000

Titik D: (8,0)

Z = 8000X1 + 7000X2

= 8000(8) + 7000(0)

= 64000

Page 6: Linear Programming

III-6

Tanda ≤ pada ketiga kendala ditunjukkan pada area sebelah kiri dari garis kendala.

Seperti tampak pada gambar 1, feasible region (area layak) meliputi daerah

sebelah kiri dari titik A (0,6.75), B (3,6), C (6,4), D (8,0)

3.1.2.2.Penyelesaian dengan Metode Simpleks

1. Merubah model matematika menjadi bentuk baku simpleks dengan cara

menambahkan batasan dengan variabel slack pada pertidaksamaan lebih kecil

sama dengan atau mengurangi dengan variabel surplus pada pertidaksamaan

lebih besar sama dengan.

+ variabel slack pada batasan

- variabel slack pada batasan ≥

Bentuk baku simpleks:

Maksimumkan Z = 8000X1 + 7000X2

Dengan syarat : 2X1 + 3X2 24

2X1 + X2 16

X1 + 4 X2 27

X1; X2 ≥ 0

Jadi bentuk baku model Linier Programming diatas adalah:

Z - 8000X1 - 7000X2 - 0S1 - 0S2 - 0S3 = 0

2X1 + 3X2 + S1 = 24

2X1 + X2 + S2 = 16

X1 + 4 X2 + S3 = 27

2. Buat Tabel Awal Simpleks

Tabel 3.3. Simpleks Awal

Dasar Z X1 X2 S1 S2 S3 Pemecahan Rasio

Z 1 -8000 -7000 0 0 0 0

S1 0 2 3 1 0 0 24

S2 0 2 1 0 1 0 16

S3 0 1 4 0 0 1 27

Page 7: Linear Programming

III-7

3. Tentukan Kolom masuk

Pada kasus maksimalisasi, kolom masuk merupakan nilai negatif terbesar pada

persamaan Z atau baris Z pada tabel simpleks, sehingga X1 merupakan kolom

masuk.

4. Tentukan kolom keluar atau persamaan pivot.

Merupakan nilai terkecil dari rasio antara pemecahan dengan elemen pada

kolom masuk (Rasio = Pemecahan : Kolom Masuk X1)

Tabel 3.4. Persamaan Simplek Iterasi Pertama

Dasar Z X1 X2 S1 S2 S3 Pemecahan Rasio

Z 1 -8000 -7000 0 0 0 0 0

S1 0 2 3 1 0 0 24 24 : 2 = 12

S2 0 2 1 0 1 0 16 16 : 2 = 8

S3 0 1 4 0 0 1 27 27 : 1 = 27

Kolom X1 adalah kolom masuk dan S2 adalah kolom keluar

Variabel X1 akan menggantikan variabel S2 pada tabel simpleks iterasi pertama.

5. Tentukan elemen pivot

Merupakan angka pada perpotongan kolom masuk dan kolom keluar, sehingga

elemen pivot = 2

6. Mencari persamaan pivot baru

Persamaan pivot baru:

Tabel 3.5. Persamaan Pivot Baru

Persamaan Pivot Lama (a) 0 2 1 0 1 0 16

Elemen Pivot (b) 2 2 2 2 2 2 2

Persamaan Pivot Baru (a/b) 0 1 1/2 0 1/2 0 8

Page 8: Linear Programming

III-8

7. Mencari persamaan variabel dasar baru

Variabel dasar baru = Variabel dasar lama – (elemen kolom masuk x

persamaan pivot baru)

a. Persamaan Z baru

Tabel 3.6. Persamaan Z Baru

Persamaan Z lama (a) 1 -8000 -7000 0 0 0 0

Elemen Kolom Masuk

pada Variabel Dasar Z (b)-8000 -8000 -8000 -8000 -8000 -8000 -8000

Persamaan Pivot Baru (c) 0 1 1/2 0 1/2 0 8

b x c = (d) 0 -8000 -8000/2 0 -8000/2 0 -64000

Persamaan Z baru (a-d) 1 0 -6000/2 0 8000/2 0 64000

b. Persamaan S1 baru

Tabel 3.7. Persamaan S1 Baru

Persamaan S1 lama (a) 0 2 3 1 0 0 24

Elemen Kolom Masuk

pada Variabel Dasar S1 (b)2 2 2 2 2 2 2

Persamaan Pivot Baru (c) 0 1 1/2 0 1/2 0 8

b x c = (d) 0 2 1 0 1 0 16

Persamaan S1 baru (a-d) 0 0 2 1 -1 0 8

c. Persamaan S3 baru

Tabel 3.8. Persamaan S3 Baru

Persamaan S3 lama (a) 0 1 4 0 0 1 27

Elemen Kolom Masuk

pada Variabel Dasar S3 (b)1 1 1 1 1 1 1

Persamaan Pivot Baru (c) 0 1 1/2 0 1/2 0 8

b x c = (d) 0 1 1/2 0 1/2 0 8

Persamaan S3 baru (a-d) 0 0 3 1/2 0 -1/2 1 19

Page 9: Linear Programming

III-9

8. Tabel simpleks iterasi pertama

Tabel 3.9. Persamaan Simplek Iterasi Kedua

Dasar Z X1 X2 S1 S2 S3 Pemecahan Rasio

Z 1 0 -6000/2 0 8000/2 0 64000

S1 0 0 2 1 -1 0 8 8 : 2 = 4

X1 0 1 1/2 0 1/2 0 8 8 : ½ = 16

S3 0 0 3 1/2 0 -1/2 1 19 19 : 3 ½ = 5,42

Karena masih terdapat angka yang masih bernilai negatif pada baris Z, maka

belum mendapatkan identitas. Untuk itu kita kembali melakukan perhitungan

ke langkah 3.

9. Elemen Pivot = 2

10. Persamaan pivot baru

Tabel 3.10. Persamaan Pivot Baru

Persamaan Pivot Lama (a) 0 0 2 1 -1 0 8

Elemen Pivot (b) 2 2 2 2 2 2 2

Persamaan Pivot Baru (a/b) 0 0 1 1/2 -1/2 0 4

11. Mencari persamaan variabel dasar baru

a. Persamaan Z baru

Tabel 3.11. Persamaan Z Baru

Persamaan Z lama (a) 1 0 -6000/2 0 8000/2 0 64000

Elemen Kolom Masuk

pada Variabel Dasar Z (b)-6000/2 -6000/2 -6000/2 -6000/2 -6000/2 -6000/2 -6000/2

Persamaan Pivot Baru (c) 0 0 1 1/2 -1/2 0 4

b x c = (d) 0 0 -6000/2 -3000/2 3000/2 0 -24000/2

Persamaan Z baru (a-d) 1 0 0 3000/2 5000/2 0 152000/2

Page 10: Linear Programming

III-10

b. Persamaan X1 baru

Tabel 3.12. Persamaan X1 Baru

Persamaan X1 lama (a) 0 1 1/2 0 1/2 0 8

Elemen Kolom Masuk

pada Variabel Dasar X1 (b)1/2 1/2 1/2 1/2 1/2 1/2 1/2

Persamaan Pivot Baru (c) 0 0 1 1/2 -1/2 0 4

b x c = (d) 0 0 1/2 1/4 -1/4 0 2

Persamaan X1 baru (a-d) 0 1 0 -1/4 3/4 0 6

c. Persamaan S3 baru

Tabel 3.13 Persamaan S3 Baru

Persamaan S3 lama (a) 0 0 3 1/2 0 -1/2 1 19

Elemen Kolom Masuk

pada Variabel Dasar S3 (b)3 1/2 3 1/2 3 1/2 3 1/2 3 1/2 3 1/2 3 1/2

Persamaan Pivot Baru (c) 0 0 1 1/2 -1/2 0 4

b x c = (d) 0 0 3 1/2 1 3/4 -1 3/4 0 14

Persamaan S3 baru (a-d) 0 0 0 -1 3/4 1 1/4 1 5

12. Tabel simpleks iterasi kedua

Tabel 3.14. Simplek Iterasi Ketiga (optimal)

Dasar Z X1 X2 S1 S2 S3 Pemecahan

Z 1 0 0 3000/2 5000/2 0 152000/2

X2 0 0 1 1/2 -1/2 0 4

X1 0 1 0 -1/4 3/4 0 6

S3 0 0 0 -1 3/4 1 1/4 1 5

Tabel simpleks iterasi kedua diatas sudah optimum karena variabel pada

persamaa Z sudah bernilai positif, sehingga:

X1 = 6

X2 = 4

Z = 152000/2 = 76000

Page 11: Linear Programming

III-11

Pada tabel iteraksi kedua diatas S1 dan S2 = 0. Artinya persediaan sumber daya

kesatu dan kedua habis digunakan, tetapi masih memiliki sumber daya ketika (S3)

sebesar 5 karena tidak digunakan

3.1.3. Perhitungan Software

Langkah pertama penyelesaian dengan menggunakan software WinQSB

adalah sebagai berikut:

Software yang digunakan yaitu WINQSB. Langkah-langkah penggunaan

software ini dalam penyelesaian kasus di atas sebagai berikut:

1. Mengaktifkan program WINQSB lalu memilih menu File New

Problem. Setelah itu akan muncul panel dan kita setting seperti pada gambar

3.1. Lalu klik OK.

Gambar 3.2. Setting panel awal WINQSB

2. Memasukkan parameter-parameter yang digunakan pada tabel

seperti pada Gambar 3.3.

Page 12: Linear Programming

III-12

Gambar 3.3. Setting parameter

3. Melihat hasil berdasarkan iterasi dilakukan dengan cara meng-klik

Solve and Analyze Solve and Display Steps lalu akan muncul iterasi per-

tama seperti pada (Gambar 3.4.) Iterasi ke dua (Gambar 3.5.) dan ke tiga

(Gambar 3.6.) dilakukan dengan mengklik Simplex Iteration Next Itera-

tion.

Gambar 3.4. Iterasi pertama

Gambar 3.5. Iterasi ke dua

Gambar 3.6. Iterasi ke tiga

Page 13: Linear Programming

III-13

4. Hasil akhir penyelesaian dilakukan dengan mengklik Solve and

Analyze Solve the Problem. Lalu akan muncul data hasil akhir seperti pada

gambar3.7.

Gambar 3.7. Data Penyelesaian Kasus.

3.2. Analisis

Dalam modul Linear Programming ini, penulis memberikan analisa

dengan menggunakan perhitungan manual dan perhitungan software. Berikut

penjelasan analisa-analisanya:

3.2.1. Analisis Perhitungan Manual

Perhitungan manual untuk nilai Z maksimasi yang digunakan untuk

menyelesaikan kasus ini adalah metode grafis dan metode simplek. Pada dasarnya

kedua metode ini bertujuan sama, tetapi berbeda dalam cara penyelesaiannya.

Metode grafis lebih mudah dilakukan dibanding metode simplek karena

perhitungan yang dilakukan tidak sebanyak metode simplek dimana dari data

yang ada dilakukan berbagai persamaan melalui tabel iterasi.

Hal pertama yang dilakukan untuk melakukan metode grafis adalah

menjabarkan fungsi kendalanya dan merubah pertidaksamaannya menjadi

persamaan. Pada langkah pertama ini, cara untuk mendapat nilai X1 dan X2 adalah

dengan cara memotong sumbu X1 pada saat X2 = 0 danbegitu juga sebaliknya

pada tiap kendala yang tadi dijabarkan. Dari hasil langkah tadilah titik-titik

Page 14: Linear Programming

III-14

perpotongan didapat sehingga grafiknya dapat tergambarkan dimana variabel

kendala A adalah 2X1 + 3X2 = 24 dengan titik koordinat (12,0) dan (0,8); variabel

kendala B adalah 2X1 + X2 = 16 dengan titik koordinat (8,0) dan (0,16); variabel

kendala C adalah X1 + 4X2 = 27 dengan titik koordinat (27,0) dan (0,6.75). Untuk

mencari titik potong kedua kendala bisa dicari dengan cara substitusi atau

eliminasi. Setelah didapat hasil lewat cara substitusi tadi maka nilai-nilai X1 dan

X2 yang ada kembali dimasukkan ke dalam rumusan Z awal pada tiap-tiap titik

potongnya. Setelah didapat nilai-nilai Z pata tiap-tiap titik potongnya, cari yang

nilainya paling besar karena yang dicari adalah nilai Z maksimasi. Nilai Z

maksimasi pada metode ini adalah sebesar 76.000.

Metode simplek dilakukan dengan cara menambahkan batasan dengan

variabel slack pada pertidaksamaan lebih kecil sama dengan atau mengurangi

dengan variabel surplus pada pertidaksamaan lebih besar sama dengan. Lalu

dilakukan persamaan-persamaan melalui tabel iterasi. Nilai Z maksimasi yang

didapat pada metode ini adalah 76.000.

Karena hasil dari kedua metode ini sama, maka perhitungan yang

dilakukan adalah benar. Jadi nilai Z maksimasi untuk masalah ini adalah 76.000.

3.2.2. Analisis Perhitungan Software

Pada gambar iterasi pertama (Gambar 3.4.), kolom yang ditunjukkan

dengan box biru merupakan angka elemen kerjanya dengan X1 sebagai Entering

Variable (EV) dan Slack_C2 sebagai Leaving Variable (LV). Dengan demikian

Basis variabel Slack_C2 pada iterasi ke dua berubah menjadi X1. Pada iterasi ke

dua (Gambar 3.5.), kolom yang ditunjukkan dengan box biru merupakan angka

elemen kerjanya dengan X2 sebagai Entering Variable (EV) dan Slack_C1

sebagai Leaving Variable (LV). Dengan demikian Basis variabel Slack_C1 pada

iterasi ke tiga berubah menjadi X2. Pada iterasi ke tiga, sudah didapat nilai

konstanta X1, X2, dan nilai Z melalui kolom R.H.S (Right Hand Solution) yaitu

X1 = 6; X2 = 4; Z = 76.000.

Page 15: Linear Programming

III-15

Pada Gambar 3.7 diperlihatkan data keseluruhan kasus melalui metode

simplex. Perubahan nilai X1 berkisar antara 4.666 – 14.000 dari unit cost, dan X2

antara 4.000 – 12.000 untuk memperoleh hasil maksimum.

3.2.3. Analisis Perbandingan Perhitungan Manual dan Software

Perhitungan manual dan software memiliki hasil yang sama yaitu nilai

maksimum sebesar 76.000 dengan nilai X1= 6 dan X2 = 4. Nilai variabel basis

tiap iterasi juga sama antara perhitungan manual dan software.