Bab 04 Metode Simpleks - 2014 March 20

  • Published on
    19-Jan-2016

  • View
    6

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>BAB 4 METODE SIMPLEKS </p><p>4.1 Pendahuluan </p><p> Penentuan solusi optimal menggunakan simpleks didasarkan pada teknik eliminasi Gauss </p><p>Jordan. </p><p> Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat kembali solusi </p><p>grafik) satu per satu dengan cara perhitungan iteratif. </p><p> Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang kita </p><p>sebut dengan iterasi. </p><p> Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1). </p><p> Ada beberapa istilah yang sangat sering kita gunakan dalam metode simpleks, diantaranya </p><p>iterasi, variabel non basis, variabel basis, solusi atau nilai kanan, variabel slack, variabel </p><p>surplus, variabel buatan, kolom pivot, baris pivot, elemen pivot, variabel masuk, variabel </p><p>keluar. </p><p>4.2 Bentuk Baku </p><p>Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku/standar dari sebuah </p><p>kendala, yaitu: </p><p>1. Fungsi kendala dengan pertidaksamaan dalam bentuk umum, diubah menjadi bentuk baku </p><p>persamaan (=) dengan menambahkan suatu variable baru yang disebut sebagai slack </p><p>variable untuk setiap kendala. Slack variable menyatakan jumlah sunber daya yang tidak </p><p>digunakan dari kendala sumber daya yang diwakilinya. </p><p>Contoh, </p><p>3 x1 + 4 x2 10 3 x1 + 4 x2 + S1 = 10 </p><p>2. Fungsi kendala dengan pertidaksamaan dalam bentuk umum, diubah menjadi bentuk baku </p><p>persamaan (=) dengan menambahkan satu surplus variable (negative dari slack variable) </p><p>dan artificial variable. Surplus variable perlu ditambahkan untuk mengubah kendala kedlam </p><p>bentuk persamaan. Karena surplus variable mempunyai koefisien -1 maka perlu </p></li><li><p>ditambahkan artificial variable untuk membentuk suatu matriks identitas pada tabel awal </p><p>simpleks. </p><p>Contoh, </p><p>3 x1 + 4 x2 10 3 x1 + 4 x2 - S1 + A1 = 10 </p><p>3. Fungsi kendala dengan persamaan = dalam bentuk umum, diubah menjadi bentuk baku </p><p>persamaan dengan menambahkan satu artificial variable. Artificial variable ditambahkan </p><p>untuk membentuk suatu matriks identitas pada tabel awal simpleks. Pada kahir iterasi (solusi </p><p>optimal), artificial variable tidak diperkenangkan mempunyai suatu nilai yang tidak sama </p><p>dengan nol. Apabila artificial variable mempunyai suatu nilai yang tidak sama dengan nol </p><p>maka solusi yang diperoleh dinyatakan sebagai solusi yang tidak layak. </p><p>Contoh, </p><p>3 x1 + 4 x2 = 10 3 x1 + 4 x2 + A1 = 10 </p><p>4. Fungsi kendala yang mempunyai nilai kanan bernilai negatif, perlu diubah dengan </p><p>mengalikan dengan -1. </p><p>Contoh, </p><p>3 x1 + 4 x2 -10 -3 x1 - 4 x2 10 -3 x1 - 4 x2 + S1 = 10 </p><p>Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku/standar dari sebuah </p><p>variabel, yaitu syarat umum bentuk baku sebuah pemrograman linear untuk simpleks adalah </p><p>bahwa semua variabel harus bernilai non-negatif. </p><p>Suatu variable yang bernilai tidak terbatas (unrestricted) berarti bahwa variabel tersebut bisa </p><p>bernilai positif maupun negatif. Untuk variabel yang bernilai tidak terbatas (mungkin bernilai </p><p>negatif) maka perlu diubah kedlam bentuk variabel non-negatif. Pengubahan variabel tidak </p><p>terbatas menjadi variabel non-negatif dapat dilakukan dengan menjadikan variabel tersebut </p><p>menjadi selisih dua variabel yang bernilai non-negatif. </p></li><li><p>Contoh, </p><p>Maksimumkan Z = 15 x1 + 20 x2 </p><p>terhadap: </p><p>3 x1 + 4 x2 10 (garis kendala 1) </p><p>2 x1 + 5 x2 8 (garis kendala 2) </p><p>x1 0, x2 tak terbatas (garis kendala 3) </p><p>Agar x2 bernilai non-negatif maka x2 digantikan dengan variabel (x2 - x2) sehingga formulasi </p><p>berubah menjadi: </p><p>Maksimumkan Z = 15 x1 + 20 x2 - 20 x2 </p><p>terhadap: </p><p>3 x1 + 4 x2 - 4 x2 10 (garis kendala 1) </p><p>2 x1 + 5 x2 - 5 x2 8 (garis kendala 2) </p><p>x1 0, x2 0, x2 0 (garis kendala 3) </p><p>Bentuk baku dari formulasi diatas menjadi: </p><p>Maksimumkan Z = 15 x1 + 20 x2 - 20 x2 + S1 + S2 terhadap: </p><p>3 x1 + 4 x2 - 4 x2 + S1 = 10 (garis kendala 1) </p><p>2 x1 + 5 x2 - 5 x2 + S2 = 8 (garis kendala 2) </p><p>x1 0, x2 0, x2 0, S1 0, S2 0 (garis kendala 3) </p><p>Contoh 1. </p><p>Minimumkan z = 2 x1 + 5.5 x2 </p><p>terhadap: </p><p>x1 + x2 = 90 (garis kendala 1) </p></li><li><p>0.001 x1 + 0.002 x2 0.9 (garis kendala 2) </p><p>0.09 x1 + 0.6 x2 27 (garis kendala 3) </p><p>0.02 x1 + 0.06 x2 4.5 (garis kendala 4) </p><p>x1, x2 0 (garis kendala 5) </p><p>Bentuk di atas adalah bentuk umum pemrograman linearnya. Kedalam bentuk baku/standar, </p><p>model matematik tersebut akan berubah menjadi: </p><p>Minimumkan z = 2 x1 + 5.5 x2 </p><p>Terhadap: </p><p>x1 + x2 + s1 = 90 </p><p>0.001 x1 + 0.002 x2 + s2 = 0.9 </p><p>0.09 x1 + 0.6 x2 - s3 = 27 </p><p>0.02 x1 + 0.06 x2 + s4 = 4.5 </p><p>x1, x2, s1, s2, s3, s4 0 </p><p> Fungsi kendala pertama mendapatkan variabel buatan (s1), karena bentuk umumnya sudah </p><p>menggunakan bentuk persamaan. </p><p> Fungsi kendala kedua dan keempat (s2 dan s4) mendapatkan variable slack karena bentuk </p><p>umumnya menggunakan pertidaksamaan , sedangkan fungsi kendala ketiga mendapatkan </p><p>surplus variable (s3) karena bentuk umumnya menggunakan pertidaksamaan .. </p></li><li><p>Contoh 2. </p><p>Maksimumkan z = 2 x1 + 3 x2 </p><p>terhadap: </p><p>10 x1 + 5 x2 600 </p><p>6 x1 + 20 x2 600 </p><p>8 x1 + 15 x2 600 </p><p>x1, x2 0 </p><p>Bentuk di atas juga merupakan bentuk umum. Perubahan kedalam bentuk baku hanya </p><p>membutuhkan variable slack, karena semua fungsi kendala menggunakan bentuk </p><p>pertidaksamaan dalam bentuk umumnya. </p><p>Maka bentuk bakunya adalah sebagai berikut: </p><p>Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3 </p><p>Terhadap : </p><p>10x1 + 5x2 + s1 = 600 </p><p>6x1 + 20x2 + s2 = 600 </p><p>8x1 + 15x2 + s3 = 600 </p><p>x1, x2, s1, s2, s3 0 </p><p>Semua fungsi kendala (s1, s2 dan s3) mendapatkan variable slack karena bentuk umumnya </p><p>menggunakan pertidaksamaan , </p></li><li><p>4.3 Pembentukan Tabel Simpleks </p><p>Langkah-langkah pembentukan sebuah tabel simpleks: </p><p>1. Memeriksa kelayakan tabel </p><p>Kelayakan tabel simpleks dapat dilihat dari solusi (nilai kanan). Jika solusi ada yang </p><p>bernilai negatif, maka tabel tidak layak. Tabel yang tidak layak tidak dapat diteruskan untuk </p><p>proses optimalisasi. </p><p>2. Menetukan kolom pivot </p><p>Penentuan kolom pivot dilihat dari koefisien fungsi tujuan (nilai di sebelah kanan baris z) </p><p>dan tergantung dari bentuk tujuan. </p><p> Jika tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien </p><p>negatif terbesar. </p><p> Jika tujuan minimisasi, maka kolom pivot adalah kolom dengan koefisien positif </p><p>terkecil. </p><p>Perhatikan, kita tidak menggunakan kata-kata nilai terkecil dan terbesar, karena kita </p><p>memang tidak memilih nilai terkecil dan terbesar. Jika kolom pivot ditandai dan ditarik ke </p><p>atas, maka kita akan mendapatkan variabel keluar. Jika nilai negatif terbesar (untuk tujuan </p><p>maksimisasi) atau positif terbesar (untuk tujuan minimisasi) lebih dari satu, pilih salah satu </p><p>secara sembarang. </p><p>3. Menetukan baris pivot </p><p>Baris pivot ditentukan setelah membagi nilai solusi dengan nilai kolom pivot yang </p><p>bersesuaian (nilai yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada </p><p>kolom pivot tidak diperhatikan, artinya tidak ikut menjadi pembagi. </p><p>Baris pivot adalah baris dengan rasio pembagian terkecil. Perhatikan, rasio pembagian tidak </p><p>mungkin bernilai negatif, karena nilai kanan tidak negatif demikian juga dengan nilai kolom </p><p>pivot. </p><p>Jika baris pivot ditandai dan ditarik ke kiri, maka kita akan mendapatkan variabel keluar. </p><p>Jika rasio pembagian terkecil lebih dari satu, pilih salah satu secara sembarang. </p><p>4. Menentukan elemen pivot </p><p>Elemen pivot merupakan nilai yang terletak pada perpotongan kolom dan baris pivot. </p><p>5. Membentuk tabel simpleks baru. </p></li><li><p>Tabel simpleks baru dibentuk dengan pertama sekali menghitung nilai baris pivot baru. </p><p>Baris pivot baru adalah baris pivot lama dibagi dengan elemen pivot. Baris baru lainnya </p><p>merupakan pengurangan nilai kolom pivot baris yang bersangkutan dikali baris pivot baru </p><p>dalam satu kolom terhadap baris lamanya yang terletak dalam satu kolom yang sama. </p><p>6. Memeriksa apakah tabel sudah optimal. </p><p>Keoptimalan tabel dilihat dari koefisien fungsi tujuan (nilai pada baris z) dan tergantung dari </p><p>bentuk tujuan. Untuk tujuan maksimisasi, tabel sudah optimal jika semua nilai pada baris z </p><p>sudah positif atau 0. Pada tujuan minimisasi, tabel sudah optimal jika semua nilai pada baris </p><p>z sudah negatif atau 0. Jika belum, kembali ke langkah no.2, jika sudah optimal baca solusi </p><p>optimalnya. </p><p>Contoh. </p><p>Jika diketahui bentuk baku sebagai berikut: </p><p>Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3 </p><p>Terhadap : </p><p>10x1 + 5x2 + s1 = 600 </p><p>6x1 + 20x2 + s2 = 600 </p><p>8x1 + 15x2 + s3 = 600 </p><p>x1, x2, s1, s2, s3 0 </p><p>Tabel awal simpleks dari persamaan baku diatas dapat dilihat pada Tabel 4.1. </p><p>Tabel 4.1: Variabel baku </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Z -2 -3 0 0 0 0 S1 10 5 1 0 0 600 S2 6 20 0 1 0 600 S3 8 15 0 0 1 600 </p></li><li><p>Penyelesaian: </p><p>1. Memeriksa kelayakan tabel </p><p>Kelayakan tabel simpleks dapat dilihat dari solusi (nilai kanan). </p><p>Tabel 4.1: Memeriksa kelayakan tabel </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Z -2 -3 0 0 0 0 S1 10 5 1 0 0 600 S2 6 20 0 1 0 600 S3 8 15 0 0 1 600 </p><p>Solusi tidak ada yang bernilai negatif, maka tabel dianggap layak dan proses optimalisasi </p><p>bisa diteruskan. </p><p>2. Menetukan kolom pivot </p><p>Tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien negatif </p><p>terbesar. </p><p>Tabel 4.2: Menentukan kolom pivot </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Z -2 -3 0 0 0 0 S1 10 5 1 0 0 600 S2 6 20 0 1 0 600 S3 8 15 0 0 1 600 </p><p>Kolom pivot ditandai dan kemudian ditarik ke atas, maka diperoleh X2 sebagai variabel </p><p>masuk. </p><p>3. Menetukan baris pivot </p><p>Baris pivot ditentukan setelah membagi nilai solusi dengan nilai kolom pivot yang </p><p>bersesuaian (nilai yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada </p><p>kolom pivot tidak diperhatikan, artinya tidak ikut menjadi pembagi. </p></li><li><p>Tabel 4.3: Menghitung rasio </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z -2 -3 0 0 0 0 - S1 10 5 1 0 0 600 600/5 = 120 S2 6 20 0 1 0 600 600/20 = 30 S3 8 15 0 0 1 600 600/15 = 40 </p><p>Dari Tabel 4.3 didapatkan bahwa nilai rasio pembagi terkecil adalah 30 sehingga baris pivot </p><p>adalah seperti yang ditunjukkan pada Tabel 4.4. </p><p>Tabel 4.4: Menentukan baris pivot </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z -2 -3 0 0 0 0 - S1 10 5 1 0 0 600 600/5 = 120 S2 6 20 0 1 0 600 600/20 = 30 S3 8 15 0 0 1 600 600/15 = 40 </p><p>Baris pivot ditandai dan kemudian ditarik ke kiri, maka diperoleh S2 sebagai variabel keluar. </p><p>4. Menentukan elemen pivot </p><p>Dari Tabel 4.4 terlihat bahwa nilai yang terletak pada perpotongan kolom dan baris pivot </p><p>adalah 20; sehingga 20 disebut sebagai elemen pivot. </p><p>5. Membentuk tabel simpleks baru. </p><p>Iterasi ke-0. </p><p>Tabel 4.4 kemudian digambarkan sebagai Tabel 4.5; tabel awal simpleks (itersi ke-0). </p><p>Dimana X2 adalah variabel masuk, S2 adalah variabel keluar dan 20 adalah elemen pivot. </p><p>Tabel 4.5: Tabel awal simpleks; iterasi ke-0 </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z -2 -3 0 0 0 0 - S1 10 5 1 0 0 600 120 X2 6 20 0 1 0 600 30 S3 8 15 0 0 1 600 40 </p></li><li><p>Iterasi ke-1. </p><p>Tabel simpleks baru (itersi ke-1) dibentuk dengan menghitung nilai baru baris pivot. Baris </p><p>pivot baru adalah baris pivot lama dibagi dengan elemen pivot. </p><p>Tabel 4.6: Nilai baru baris pivot </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z S1 X2 6/20 20/20 0 1/20 0 600/20 30 S3 </p><p>Nilai baru untuk baris selain baris pivot = Nilai lama - (Nilai pada kolom kerja * Nilai baru </p><p>baris pivot). </p><p>Nilai pada kolom kerja adalah nilai pada titik perpotongan kolom pivot dengan baris yang </p><p>akan dicari nilai baru-nya. </p><p>Tabel 4.7: Nilai baru baris pivot; baris ke-1 </p><p> X1 X2 S1 S2 S3 Solusi Z lama -2 -3 0 0 0 0 </p><p> -3 6/20 20/20 0/20 1/20 0/20 600/20 Z baru -2 - (-3*6/20) = - 1.1 </p><p>-3 - (-3*20/20) = 0 </p><p>0 - (-3*0) = 0 </p><p>0 - (-3*1/20) = 0.15 </p><p>0 - (-3*0) = 0 </p><p>0 - (-3*600/20) = 90 </p><p>Tabel 4.8: Nilai baru baris pivot; baris ke-2 </p><p> X1 X2 S1 S2 S3 Solusi S1 lama 10 5 1 0 0 600 </p><p> 5 6/20 20/20 0/20 1/20 0/20 600/20 S1 baru 10 - (5*6/20) = 8.5 </p><p>5 - (5*20/20) = 0 </p><p>1 - (5*0) = 1 </p><p>0 - (5*1/20) = -0,25 </p><p>0 - (5*0) = 0 </p><p>600 - (5*600/20) = 450 </p></li><li><p>Tabel 4.9: Nilai baru baris pivot; baris ke-4 </p><p> X1 X2 S1 S2 S3 Solusi S3 lama 8 15 0 0 1 600 </p><p> 15 6/20 20/20 0/20 1/20 0/20 600/20 S3 baru 8 - (15*6/20) = 3.5 </p><p>15 - (15*20/20) = 0 </p><p>0 - (15*0) = 0 </p><p>0 - (15*1/20) = -0,75 </p><p>1 - (15*0) = 1 </p><p>600 - (15*600/20) = 150 </p><p>Memasukkan nilai-nilai Zbaru, S1 baru dan S3 baru kedalam Tabel 4.6. Dan diperoleh Tabel 4.10 </p><p>sebagai tabel nilai baru untuk interasi ke-2. </p><p>Tabel 4.10: Tabel nilai baru; iterasi ke-1 </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Z -1,1 0 0 0,15 0 90 S1 8.5 0 1 -0,25 0 450 X2 6/20 20/20 0 1/20 0 600/20 S3 3.5 0 0 -0,75 1 150 </p><p>Dari Tabel 4.10 terlihat bahwa masih terdapat nilai negative pada fungsi tujuan sehingga </p><p>dapat dinyatakan bahwa solusi yang diperoleh belum optimal. Untuk itu perlu dilakukan </p><p>perbaikan solusi dengan cara lanjut ke iterasi berikutnya. </p><p>Iterasi ke-2. </p><p>Tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien negatif </p><p>terbesar. </p><p>Tabel 4.11: Menentukan kolom pivot untuk iterasi ke-1 </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Z -1,1 0 0 0,15 0 90 S1 8.5 0 1 -0,25 0 450 X2 6/20 20/20 0 1/20 0 600/20 S3 3.5 0 0 -0,75 1 150 </p></li><li><p>Tabel 4.12: Menghitung rasio untuk iterasi ke-1 </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z -1,1 0 0 0,15 0 90 - S1 8,5 0 1 -0,25 0 450 450/8,5 = 52,94 X2 6/20 20/20 0 1/20 0 600/20 (600/20) / (6/20) = 100 S3 3,5 0 0 -0,75 1 150 150/3,5 = 42,857 </p><p>Dari Tabel 4.12 didapatkan bahwa nilai rasio pembagi terkecil adalah 42,857 sehingga baris </p><p>pivot adalah seperti yang ditunjukkan pada Tabel 4.13. </p><p>Tabel 4.13: Menentukan baris pivot </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z -1,1 0 0 0,15 0 90 - S1 8,5 0 1 -0,25 0 450 52,94 X2 6/20 20/20 0 1/20 0 600/20 100 S3 3,5 0 0 -0,75 1 150 42,857 </p><p>Variabel masuk adalah x1, variabel keluar adalah S3 dan 3,5 adalah elemen pivot. </p><p>Tabel simpleks baru (itersi ke-2) dibentuk dengan menghitung nilai baru baris pivot. Baris </p><p>pivot baru adalah baris pivot lama dibagi dengan elemen pivot. </p><p>Tabel 4.14: Nilai baru baris pivot </p><p>Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z S1 X2 X1 3,5/3,5 0/3,5 0/3,5 -0,75/3,5 1/3,5 150/3,5 42,857/3,5 </p><p>Nilai baru untuk baris selain baris pivot = Nilai lama - (Nilai pada kolom kerja * Nilai baru </p><p>baris pivot). </p><p>Nilai pada kolom kerja adalah nilai pada titik perpotongan kolom pivot dengan baris yang </p><p>akan dicari nilai baru-nya. </p></li><li><p>Tabel 4.15: Nilai baru baris pivot; baris ke-1 </p><p> X1 X2 S1 S2 S3 Solusi Z lama -1,1 0 0 0,15 0 90 </p><p> -1,1 3,5/3,5 0/3,5 0/3,5 -0,75/3,5 1/3,5 150/3,5 Z baru -1,1 - (-1,1*1) = 0 </p><p>0 - (-1,1*0) = 0 </p><p>0 - (-1,1*0) = 0 </p><p>0,15 - (-1,1*-0,2143) = 0,1264 </p><p>0 - (-1,1*0,2857) = 0.3143 </p><p>900 - (-1,1*42,857) = 137,1429 </p><p>Tabel 4.16: Nilai baru baris pivot; baris ke-2 </p><p> X1 X2 S1 S2 S3 Solusi S1 lama 8,5 0 1 -0,25 0 450 </p><p> 8,5 3,5/3,5 0/3,5 0/3,5 -0,75/3,5 1/3,5 150/3,5 S1 baru 8,5 - (8,5*1) = 0 </p><p>0 - (8,5*0) = 0 </p><p>1 - (8,5*0) = 1 </p><p>-0,25 - (8,5*-0,2143) = 1,5715 </p><p>0 - (8,5*0,2857) = -2,4285 </p><p>450 - (8.5*42,857) = 85,7155 </p><p>Tabel 4.17: Nilai baru baris pivot; baris ke-3 </p><p> X1 X2 S1 S2 S3 Solusi X2 lama 6/20 20/20 0 1/20 0 600/20 </p><p> 6/20 3,5/3,5 0/3,5 0/3,5 -0,75/3,5 1/3,5 150/3,5 X2 baru 0,3 - (0,3*1) = 0 </p><p>1 - (0,3*0) = 1 </p><p>0 - (0,3*0) = 0 </p><p>0,05 - (0,3*-0,2143) = 0,...</p></li></ul>