tugas metnum
DESCRIPTION
schoolTRANSCRIPT
PENYELESAIAN CONTOH MASALAH DENGAN MENGGUNAKAN TEKNIK
OPTIMISASI KOMPUTASI NUMERIS
Nama / NIM : Wahyu Budi Prasetyo / 10418
Al-Zaisar Trimulyo / 10414
Nila Puspitasari / 10416
Anindita S / 10442
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS GADJAH MADA YOGYAKARTA
2007
\
Pendahuluan :
Masalah komputasi dan penyelesaiannya banyak ditemukan dalam kehidupan sehari-hari, salah satu
contohnya adalah teknik optimisasi.
Teknik optimisasi merupakan suatu bidang yang sangat bermanfaat bagi para pengambil keputusan dalam
bidang teknik maupun ekonomi, seperti misalnya dlam bidang industry, bisnis, pemerintahan dan organisasi
militer, dengan suatu tujuan untuk mempertinggi kualitas keputusan yang diambil (Marland dan Sweigart,
(1987).
Permasalahan optimisasi adalah memilih suatu pemecahan optimal bisa berarti memaksimumkan hasil yang
diinginkan atau meminimumkan kerugian atau biaya yang menyertainya (Sri Mulyono 1991).
Salah satu teknik memecahkan permasalahan teknik optimisasi adalah dengan netode pemrograman linier.
Pemrograman Linier :
Program linier (Linear Programming yang disingkat LP) mungkin merupakan salah satu Teknik Optimisasi yang
digunakan paling luas dan diketahui dengan baik.
LP merupakan metode matematik dalam mengalokasi sumber daya yang langka untuk mencapai suatu tujuan
seperti memaksimumkan keuntungan dan meminimumkan biaya.
LP banyak diterapkan dalam masalah ekonomi, industri, militer, sosial, dan lain-lain. LP berkaitan dengan
penjelasan suatu dunia
Contoh soal : Penyelesaian masalah optimasi dengan metode pemrograman linier
Bob Sadino sebagai manajer perusahaan penghasil sosis menghadapi masalah perubahan harga bahan baku
dan secara langsung mengadakan evaluasi terhadap proporsi campuran bahan yang digunakan dalam
pembuatan paling sedikit 1 kuintal sosis. Hasil analisis menemukan presentase presentase protein tidak boleh
kurang dari 15%, lemak tidak boleh melebihi 30%. Serat paling banyak 40% dan karbohidrat paling sedikit 20%.
Protein, lemak, serat, dan karbohidrat tersebut dapat diperoleh dari empat jenis bahan baku yang memiliki
karakteristik dan harga yang berbeda seperti diperlihatkan pada table berikut:
Bahan Protein Lemak Serat Karbohidrat Harga/kg
A 40% 10% 20% 20% Rp. 800
B 20% 15% 30% 40% Rp. 700
C 10% 35% 15% 25% Rp. 400
D 15% 40% 10% 30% Rp. 200
Selesaikan program linear dari masalah di atas.
Penyelesaian :
Dari table diatas, diinginkan jumlah minimal adalah 1 kuintal (100kg) maka dapat dibuat table baru sebagai
berikut:
X1 X2 X3 X4 Batasan
Protein 40 20 10 15 >=15(x1 + x2 + x3 + x4)
Lemak 10 15 35 40 <=30(x1 + x2 + x3 + x4)
Serat 20 30 15 10 <=40(x1 + x2 + x3 + x4)
Karbohidrat 20 40 25 30 >=20(x1 + x2 + x3 + x4)
Jumlah 1 1 1 1 >=100
Harga Rp. 800 Rp. 700 Rp. 400 Rp. 200 Minimisasi
Persamaannya dapat dibuat :
25x1 + 5x2 - 5x3 >= 0
-20x1 - 15x2 + 5x3 + 10x4 <= 0
-20x1 - 10x2 - 25x3 - 30x4 <= 0
5x1 + 20x2 + 5x3 + 10x4 >= 0
X1 + x2 + x3 + x4 >= 100
Dengan variable tujuan sebagai berikut :
800x1 + 700x2 + 400x3 + 200x4= min Z
Minimisasi dapat diubah menjadi maksimisasi dengan bentuk : Min z = - Max (-z) = Max Q sehingga persamaan tujuan menjadi :
Max Q = - 800x1 - 700x2 - 400x3 - 200x4
Dan variable syarat menjadi :
25x1 + 5x2 - 5x3 – x5 + R1 = 0
-20x1 - 15x2 + 5x3 + 10x4 + x6 = 0
-20x1 - 10x2 - 25x3 - 30x4 + x7 = 0
5x1 + 20x2 + 5x3 + 10x4 – x8 + R2 = 0
x1 + x2 + x3 + x4 – x9 + R3 = 100
dan berikut tabel awal iterasinya:
Basis X1 X2 X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
R1 25 5 -5 0 1 -1 0 0 0 0 0 0 0
X6 -20 -15 5 10 0 0 1 0 0 0 0 0 0
X7 -20 -10 -25 -30 0 0 0 1 0 0 0 0 0
R2 0 20 5 10 0 0 0 0 1 -1 0 0 0
R3 1 1 1 1 0 0 0 0 0 0 1 -1 100
Selanjutnya akan dilakukan iterasi sebagai berikut:
Iterasi 1
Basis X1 X2 X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
X1 1 0,2 -0,2 0 0,04 -0,04 0 0 0 0 0 0 0
X6 0 -11 1 10 0,8 -0,8 1 0 0 0 0 0 0
X7 0 -6 -29 -30 0,8 -0,8 0 1 0 0 0 0 0
R2 0 20 5 10 0 0 0 0 1 -1 0 0 0
R3 0 0,8 1,2 1 -0,04 0,04 0 0 0 0 1 -1 100
Iterasi 2
Basis X1 X2 X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
X1 1 0 -0,25 -0,1 0,04 -0,04 0 0 -0,01 0,01 0 0 0
X6 0 0 3,75 15,5 0,8 -0,8 1 0 0,55 -0,55 0 0 0
X7 0 0 -27,5 -27 0,8 -0,8 0 1 0,3 -0,3 0 0 0
X2 0 1 0,25 0,5 0 0 0 0 0,05 -0,05 0 0 0
R3 0 0 1 0,6 -0,04 0,04 0 0 -0,04 0,04 1 -1 100
Iterasi 3
Basis X1 X2 X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
X1 1 0 0 0,9333 0,0933 -0,0933 0,0667 0 0,0267 -0,0267 0 0 0
X3 0 0 1 4,1333 0,2133 -0,2133 0,2667 0 0,1467 -0,1467 0 0 0
X7 0 0 0 86,6667 6,6667 -6,6667 7,3333 1 4,3333 -4,3333 0 0 0
X2 0 1 0 -0,5333 -0,0533 0,0533 -0,0667 0 0,0133 -0,0133 0 0 0
R3 0 0 0 -3,5333 -0,2533 0,2533 -0,2667 0 -0,1867 0,1867 1 -1 100
Iterasi 4
Basis X1 X2
X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
X1 1 1,75 0 0 0 0 -0,05 0 0,05 -0,05 0 0 0
X3 0 4 1 2 0 0 0 0 0,2 -0,2 0 0 0
X7 0 125 0 20 0 0 -1 1 6 -6 0 0 0
X5 0 18,75 0 -10 -1 1 -1,25 0 0,25 -0,25 0 0 0
R3 0 -4,75 0 -1 0 0 0,05 0 -0,25 0,25 1 -1 100
Iterasi 5
Basis X1 X2
X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q
X1 1 0,8 0 -0,2 0 0 -0,04 0 0 0 0,2 -0,2 20
X3 0 0,2 1 1,2 0 0 0,04 0 0 0 0,8 -0,8 80
X7 0 11 0 -4 0 0 0,2 1 0 0 24 -24 2.400,00
X5 0 14 0 -11 -1 1 -1,2 0 0 0 1 -1 100
X8 0 -19 0 -4 0 0 0,2 0 -1 1 4 -4 400
Iterasi 6
Basis X1 X2 X3
X4 R1
X5 X6 X7
R2
X8 R3 X9 Jumlah
Q
X1 1 0,833 0,1667 0 0 0 -0,033 0 0 0 0,3333 -0,3333 33,3333
X4 0 0,1667 0,8333 1 0 0 0,0333 0 0 0 0,6667 -0,6667 66,6667
X7 0 11,666 3,3333 0 0 0 0,3333 1 0 0 26,666 -26,6667 2.666,67
X5 0 15,833 9,1667 0 -1 1 -0,833 0 0 0 8,3333 -8,3333 833,3334
X8 0 -18,33 3,3333 0 0 0 0,3333 0 -1 1 6,6667 -6,6667 666,6667
Iterasi 7
Basis X1 X2 X3 X4 R1 X5 X6 X7 R2 X8 R3 X9 Jumlah
Q 40.000
X2 1,2 1 0,2 0 0 0 -0,04 0 0 0 0,4 -0,4 40
X4 -0,2 0 0,8 1 0 0 0,04 0 0 0 0,6 -0,6 60
X7 -14 0 1 0 0 0 0,8 1 0 0 22 -22 2.200,00
X5 -19 0 6 0 -1 1 -0,2 0 0 0 2 -2 200
X8 22 0 7 0 0 0 -0,4 0 -1 1 14 -14 1.400,00
Dari tabel iterasi diatas, didapatkan nilai optimumnya adalah Rp. 40.000. Dengan rincian:
X1 = 0
X2 = 40
X3 = 0
X4 = 60