Optimization [PDF]

Citation preview

Kelompok 1 Max Z = 8X1 + 6X2 Batasan: 4X1 + 2X2 ≤ 60 2X1 + 4X2 ≤ 48 X1, X1 ≥ 0



PENYELESAIAN DENGAN METODE GRAFIK 1. Gambar persamaan Linier a. 4X1 + 2X2 ≤ 60 X1 = 0 , maka 2X2 ≤ 60  X2 ≤ 30 X2 = 0 , maka 4X1 ≤ 60  X1 ≤ 15



b. 2X1 + 4X2 ≤ 48 X1 = 0 , maka 4X2 ≤ 48  X2 = 12 X2 = 0 , maka 2X1 ≤ 48  X1 = 24



Gambar Fungsi Pembatas



2. Gambar fungsi tujuan grafik Z = 8X1 + 6X2  6X2 = Z – 8X1 X2 = 1/6Z – 8/6X1  X2 = 1/6Z – 4/3X1 X2 = 4 ; X1 = 3 Jika X2 = 12, maka X1 = 9



Wilayah ptimum adalah OABC -



-



-



Titik O : X1 = 0 ; X2 = 0 ; jadi ZO = 0 Titik A : X1 = 0 ; X2 = 12 ; ZA = 8X1 + 6X2 = 8 (0) + 6 (12) = 72 Titik C : X1 = 15 ; X2 = 0 ; ZC = 8X1 + 6X2 = 8 (15) + 6 (0) = 120 Titik B merupakan perpotongan antara fungsi pembatas 4X1 + 2X2 ≤ 60 dan 2X1 + 4X2 ≤ 48 4X1 + 2X2 = 60 | *2 | 8X1 + 4X2 = 120 2X1 + 4X2 = 48 | *1 | 2X1 + 4X2 = 48 6X1 = 72 X1 = 12 2X1 + 4X2 = 48



 2 (12) + 4X2 = 48 24 + 4X2 = 48 X2 = 6



Z = 8X1 + 6X2  Z = 8 (12) + 6 (6) = 96 + 36 = 132



PENYELESAIAN DENGAN METODE SIMPLEKS 1. Perumusan Fungsi Fungsi Max Z = 8X1 + 6X2 Perumusan fungsi kendala: 4X1 + 2X2 ≤ 60 2X1 + 4X2 ≤ 48 X1, X2 ≥ 0 2. Mengubah fungsi tujuan dan fungsi kendala ke bentuk standar simpleks: Z = 8X1 + 6X2  Z – 8X1 – 6X2 = 0 4X1 +2X2 + X3 = 60 2X1 + 4X2 +X4 = 48 Dengan X3 dan X4 merupakan variable slack 3. Membuat table simpleks awal Variabel Dasar Z X3



Z



X1



X2



X3



X4



NK



Indeks



1 0



-6 2



0 1



0 0



0 60



15



X4



0



-8 4 (elemen cell) 2 Kolom kunci



4



0



1



48



24



Baris kunci



Indeks = Nilai Kanan (NK) / Kolom Kunci (KK) 4. Melakukan iterasi - Membuat Baris Kunci Baru Baris kunci baru = Baris kunci lama Elemen Cell X1 = 4 2 1 0 60 4 X1 = 1 ½ ¼ 0 15 Variabel Dasar Z



Z



X1



X2



X3



X4



NK



X1 X4 -



0



1



½



¼



0



15



Membuat Baris Variabel Baru



Baris X4 Baru = Baris X4 Lama – (Nilai Kolom Kunci Baris yang sesuai * Baris Kunci Baru) Baris X4 Baru = (2 4 0 1 48) – (2)*(1 ½ ¼ 0 15) = 0 3 -½ 1 18 Variabel Dasar Z X1 X4 -



Z



X1



X2



X3



X4



NK



0 0



1 0



½ 3



¼ -½



0 1



15 18



Membuat Baris Z Baru



Baris Z Baru = Baris Z Lama – (Nilai Kolom Kunci Baris yang sesuai * Baris Kunci Baru) Baris Z Baru = (-8 -6 0 0 0) – (-8)*(1 ½ ¼ 0 15) = 0 -2 2 0 120 Variabel Dasar Z X1 X4



Z



X1



X2



X3



X4



NK



1 0 0



0 1 0



-2 ½ 3



2 ¼ -½



0 0 1



120 15 18



Lakukan Iterasi sampai tidak ada nilai baris Z yang negative Variabel Dasar Z X1 X4 -



Z



X1



X2



X3



X4



NK



Indeks



1 0 0



0 1 0



-2 ½ 3



2 ¼ -½



0 0 1



120 15 18



-60 30 6



Membuat Baris Kunci Baru



Baris Kunci Baru =



0 3 -½ 1 1



18



3 X2 = 0



1



-1/6



1/3



6



Variabel Dasar Z X1 X2 -



Z



X1



X2



X3



X4



NK



0



0



1



- 1/6



1/3



6



Membuat Baris Variabel Baru



Baris X1 Baru



= (1 =



Variabel Dasar Z X1 X2 -



½



1



¼



0



1/3



0



15) - ( ½ )*(0 -1/6



1



-1/6



1/3



6)



12



Z



X1



X2



X3



X4



NK



0 0



1 0



0 1



1/3 - 1/6



-1/6 1/3



12 6



Membuat Baris Z Baru



Baris Z Baru



= (0 -2 2 = 0



Variabel Dasar Z X1 X2



0



0



5/3



120) - (-2)*(0 2/3



1



-1/6



1/3



6)



132



Z



X1



X2



X3



X4



NK



1 0 0



0 1 0



0 0 1



5/3 1/3 - 1/6



2/3 -1/6 1/3



132 12 6



Hasil Kesimpulan Dari table iterasi pada baris Z sudah tidak ada nilai negative, berarti iterasi selesai, dan solusi yang diperoleh adalah: Z



= 12X1 + 6X2



= 132