penyelesaian masalah optimasi dengan metode grafik
DESCRIPTION
penyelesaian masalah optimasi dengan metode grafikTRANSCRIPT
Tugas IIIMetode OptimisasiKelompok I :• Adonia Nafi (355751)
• Cornelis FJ Latupapua (371986)
• Fauzun Attabiq (372069)
• Juan Roberth Sirait (371990)
• Jan Seleky (354433)
• Thiery Mugenzy (372050)
Kelompok I :• Adonia Nafi (355751)
• Cornelis FJ Latupapua (371986)
• Fauzun Attabiq (372069)
• Juan Roberth Sirait (371990)
• Jan Seleky (354433)
• Thiery Mugenzy (372050)
Program Studi Magister Ilmu KomputerFakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Gadjah MadaYogyakarta
Review ProblemsGroup A no. 3 , Winston Operation Research, hal 213
3. Selesaikan soal dibawah ini :
Penyelesaian Optimalisasi dengan Metode Grafik
2X1 + X2 = 6
X1 = 0 , X2 = 6 (0,6) titik AX2 = 0 , X1 = 3 (3,0) titik B
X1 + X2 ≤ 4
X1 = 0 , X2 = 4 (0,4) titik CX2 = 0 , X1 = 4 (4,0) titik D
X1 + 2X2 ≤ 5
X1 = 0 , X2 = 2,5 (0, 2,5) titik EX2 = 0 , X1 = 5 (5,0) titik F
X1, X2 ≥ 0
2X1 + X2 = 6
X1 = 0 , X2 = 6 (0,6) titik AX2 = 0 , X1 = 3 (3,0) titik B
X1 + X2 ≤ 4
X1 = 0 , X2 = 4 (0,4) titik CX2 = 0 , X1 = 4 (4,0) titik D
X1 + 2X2 ≤ 5
X1 = 0 , X2 = 2,5 (0, 2,5) titik EX2 = 0 , X1 = 5 (5,0) titik F
X1, X2 ≥ 0
Penyelesaian Optimalisasi dengan Metode Grafik
A
C
E
X2
B D F
2X1 + X2 = 6X1 + X2 ≤ 4X1 + 2X2 ≤ 5
X1
Penyelesaian Optimalisasi dengan Metode Grafik
Menggambar garis isoprofit untuk mencari arah optimalisasi fungsi tujuan :check misalkan dengan mengambil sembarang nilai Z dalam hal ini misalkanZ1 = 5, dan Z2 = 0 sehingga garis isoprofit:5X1 – X2 = 5
X1 = 0 , X2 = -5 0,-5X2 = 0 , X1 = 1 1,0
Menggambar garis isoprofit untuk mencari arah optimalisasi fungsi tujuan :check misalkan dengan mengambil sembarang nilai Z dalam hal ini misalkanZ1 = 5, dan Z2 = 0 sehingga garis isoprofit:5X1 – X2 = 5
X1 = 0 , X2 = -5 0,-5X2 = 0 , X1 = 1 1,0
Penyelesaian Optimalisasi dengan Metode Grafik
A
C
E
X2
Z = 5Z = 0
Arah optimalisasi
feasible region
B D F
2X1 + X2 = 6X1 + X2 ≤ 4X1 + 2X2 ≤ 5
X1
Penyelesaian Optimalisasi dengan Metode Grafik
Walaupun feasible region sudah diketahui, titik optimalisasi harus berada padafungsi kendala 2X1 + X2 = 6 (garis warna merah / garis A-B).Dan sesuai dengan arah optimalisasi yang diperoleh, maka titik optimal akandiperoleh pada titik B (3.0).
Penyelesaian Optimalisasi dengan Metode Grafik
A
C
E
X2
Z = 5Z = 0
Arah optimalisasi
feasible region(2.3 , 1.3)
Titik Z2.3 , 1.3 10.23.0 15
B D F
2X1 + X2 = 6X1 + X2 ≤ 4X1 + 2X2 ≤ 5
X1
(2.3 , 1.3)
Penyelesaian Optimalisasi dengan Metode Simplex
Dalam soal diatas, fungsi kendala 2X1 + X2 = 6 diubah menjadi 2X1 + X2 ≤ 6Sehingga menjadi :
max Z = 5X1 – X2
s.t. 2X1 + X2 ≤ 6X1 + X2 ≤ 4X1 + 2X2 ≤ 5X1, X2 ≥ 0
Diubah menjadi semua fungsi menjadi fungsi standar :2X1 + X2 + S1 = 6X1 + X2 + S2 = 4X1 + 2X2+ S3 = 5
Z = 5X1 – X2 + 0.S1 +0.S2 + 0.S3
Z – 5X1 + X2 – 0.S1 – 0.S2 – 0.S3 = 0
Dalam soal diatas, fungsi kendala 2X1 + X2 = 6 diubah menjadi 2X1 + X2 ≤ 6Sehingga menjadi :
max Z = 5X1 – X2
s.t. 2X1 + X2 ≤ 6X1 + X2 ≤ 4X1 + 2X2 ≤ 5X1, X2 ≥ 0
Diubah menjadi semua fungsi menjadi fungsi standar :2X1 + X2 + S1 = 6X1 + X2 + S2 = 4X1 + 2X2+ S3 = 5
Z = 5X1 – X2 + 0.S1 +0.S2 + 0.S3
Z – 5X1 + X2 – 0.S1 – 0.S2 – 0.S3 = 0
Penyelesaian Optimalisasi dengan Metode Simplex
Membuat Tabel Simplex
Menentukan basis dan calon basis :
Basis adalah kolom X1 s.d Sn yang salah satu barisnya bernilai 1 dan yanglainnya bernilai 0.Calon basis adalah baris 0 dengan nilai minimum atau terkecil.
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0 -1 0 2 1 1 0 0 62 0 1 1 0 1 0 43 0 1 2 0 0 1 5
Membuat Tabel Simplex
Menentukan basis dan calon basis :
Basis adalah kolom X1 s.d Sn yang salah satu barisnya bernilai 1 dan yanglainnya bernilai 0.Calon basis adalah baris 0 dengan nilai minimum atau terkecil.
3 0 1 2 0 0 1 5
Penyelesaian Optimalisasi dengan Metode Simplex
Tabel Simplex
Pada saat inibasis adalah S1, S2, S3
calon basis adalah X1 -5
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0 -1 0 2 1 1 0 0 62 0 1 1 0 1 0 43 0 1 2 0 0 1 5
Tabel Simplex
Pada saat inibasis adalah S1, S2, S3
calon basis adalah X1 -5
3 0 1 2 0 0 1 5
Penyelesaian Optimalisasi dengan Metode Simplex
Tabel Simplex
Check Ratio untuk menentukan pivotPivot adalah nilai check ratio terkecil *
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0 -1 0 2 1 1 0 0 6 6/2=3*2 0 1 1 0 1 0 4 4/1=43 0 1 2 0 0 1 5 5/1=5
Tabel Simplex
Check Ratio untuk menentukan pivotPivot adalah nilai check ratio terkecil *
3 0 1 2 0 0 1 5 5/1=5
Penyelesaian Optimalisasi dengan Metode Simplex
Tabel Simplex
Membuat basis dari calon basis dengan mengoperasikan setiap baris
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0 -1 0 2 1 1 0 0 6 6/2=3*2 0 1 1 0 1 0 4 4/1=43 0 1 2 0 0 1 5 5/1=5
Tabel Simplex
Membuat basis dari calon basis dengan mengoperasikan setiap baris
3 0 1 2 0 0 1 5 5/1=5
pivot
Penyelesaian Optimalisasi dengan Metode Simplex
Tabel Simplex
Operasi Baris ke-1 -> membuat pivot =1
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0 -1 0 2 1 1 0 0 6 6/2=3*2 0 1 1 0 1 0 4 4/1=43 0 1 2 0 0 1 5 5/1=5
Tabel Simplex
Operasi Baris ke-1 -> membuat pivot =1
3 0 1 2 0 0 1 5 5/1=5
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 0
B1/2 1 0 1 ½ ½ 0 0 32 0 1 1 0 1 0 43 0 1 2 0 0 1 5
Penyelesaian Optimalisasi dengan Metode Simplex
Operasi Baris ke-2
Hasil Operasi Baris ke-2
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 01 0 1 ½ ½ 0 0 3
B2-B1’ 2 0 1 1 0 1 0 43 0 1 2 0 0 1 5
Operasi Baris ke-2
Hasil Operasi Baris ke-2Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio
0 1 -5 2 0 0 0 01 0 1 ½ ½ 0 0 3
B2-B1’ 2 0 0 ½ -1/2 1 0 13 0 1 2 0 0 1 5
3 0 1 2 0 0 1 5
Penyelesaian Optimalisasi dengan Metode Simplex
Operasi Baris ke-3
Hasil Operasi Baris ke-3
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 -5 2 0 0 0 01 0 1 ½ ½ 0 0 32 0 0 ½ -1/2 1 0 1
B3-B1’ 3 0 1 2 0 0 1 5
Operasi Baris ke-3
Hasil Operasi Baris ke-3Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio
0 1 -5 2 0 0 0 01 0 1 ½ ½ 0 0 32 0 0 ½ -1/2 1 0 1
B3-B1’ 3 0 0 1.5 -1/2 0 1 2
B3-B1’ 3 0 1 2 0 0 1 5
Penyelesaian Optimalisasi dengan Metode Simplex
Operasi Baris ke-0
Hasil Operasi Baris ke-0
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasioB0+5.B1’ 0 1 -5 2 0 0 0 0
1 0 1 ½ ½ 0 0 32 0 0 ½ -1/2 1 0 13 0 0 1.5 -1/2 0 1 2
Operasi Baris ke-0
Hasil Operasi Baris ke-0Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio
B0+5.B1’ 0 1 0 4.5 2.5 0 0 151 0 1 ½ ½ 0 0 32 0 0 ½ -1/2 1 0 13 0 0 1.5 -1/2 0 1 2
3 0 0 1.5 -1/2 0 1 2
Penyelesaian Optimalisasi dengan Metode Simplex
Hasil akhir tabel simplex
Karena baris 0 sudah tidak ada yang bernilai negatif maka operasi selesai.Kesimpulan :Jadi Z max dicapai saat X1 = 3; S2 = 1; dan S3 = 2 dengan X2 dan S1 = 0.Pada kasus ini dari tabel simplex, nilai Z diperolah = 15Z= 5X1 – X2 + 0.S1 + 0.S2 + 0.S3
= 5.3 – 0 + 0.0 + 0.1 + 0.2 = 15 // terbukti
Operasi Baris Z X1 X2 S1 S2 S3 rhs Check rasio0 1 0 4.5 2.5 0 0 151 0 1 ½ ½ 0 0 32 0 0 ½ -1/2 1 0 1
Hasil akhir tabel simplex
Karena baris 0 sudah tidak ada yang bernilai negatif maka operasi selesai.Kesimpulan :Jadi Z max dicapai saat X1 = 3; S2 = 1; dan S3 = 2 dengan X2 dan S1 = 0.Pada kasus ini dari tabel simplex, nilai Z diperolah = 15Z= 5X1 – X2 + 0.S1 + 0.S2 + 0.S3
= 5.3 – 0 + 0.0 + 0.1 + 0.2 = 15 // terbukti
3 0 0 1.5 -1/2 0 1 2