Bab 04 Metode Simpleks - 2014 March 20

  • Published on
    19-Jan-2016

  • View
    7

  • Download
    0

Embed Size (px)

Transcript

  • BAB 4 METODE SIMPLEKS

    4.1 Pendahuluan

    Penentuan solusi optimal menggunakan simpleks didasarkan pada teknik eliminasi Gauss

    Jordan.

    Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat kembali solusi

    grafik) satu per satu dengan cara perhitungan iteratif.

    Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang kita

    sebut dengan iterasi.

    Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).

    Ada beberapa istilah yang sangat sering kita gunakan dalam metode simpleks, diantaranya

    iterasi, variabel non basis, variabel basis, solusi atau nilai kanan, variabel slack, variabel

    surplus, variabel buatan, kolom pivot, baris pivot, elemen pivot, variabel masuk, variabel

    keluar.

    4.2 Bentuk Baku

    Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku/standar dari sebuah

    kendala, yaitu:

    1. Fungsi kendala dengan pertidaksamaan dalam bentuk umum, diubah menjadi bentuk baku

    persamaan (=) dengan menambahkan suatu variable baru yang disebut sebagai slack

    variable untuk setiap kendala. Slack variable menyatakan jumlah sunber daya yang tidak

    digunakan dari kendala sumber daya yang diwakilinya.

    Contoh,

    3 x1 + 4 x2 10 3 x1 + 4 x2 + S1 = 10

    2. Fungsi kendala dengan pertidaksamaan dalam bentuk umum, diubah menjadi bentuk baku

    persamaan (=) dengan menambahkan satu surplus variable (negative dari slack variable)

    dan artificial variable. Surplus variable perlu ditambahkan untuk mengubah kendala kedlam

    bentuk persamaan. Karena surplus variable mempunyai koefisien -1 maka perlu

  • ditambahkan artificial variable untuk membentuk suatu matriks identitas pada tabel awal

    simpleks.

    Contoh,

    3 x1 + 4 x2 10 3 x1 + 4 x2 - S1 + A1 = 10

    3. Fungsi kendala dengan persamaan = dalam bentuk umum, diubah menjadi bentuk baku

    persamaan dengan menambahkan satu artificial variable. Artificial variable ditambahkan

    untuk membentuk suatu matriks identitas pada tabel awal simpleks. Pada kahir iterasi (solusi

    optimal), artificial variable tidak diperkenangkan mempunyai suatu nilai yang tidak sama

    dengan nol. Apabila artificial variable mempunyai suatu nilai yang tidak sama dengan nol

    maka solusi yang diperoleh dinyatakan sebagai solusi yang tidak layak.

    Contoh,

    3 x1 + 4 x2 = 10 3 x1 + 4 x2 + A1 = 10

    4. Fungsi kendala yang mempunyai nilai kanan bernilai negatif, perlu diubah dengan

    mengalikan dengan -1.

    Contoh,

    3 x1 + 4 x2 -10 -3 x1 - 4 x2 10 -3 x1 - 4 x2 + S1 = 10

    Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku/standar dari sebuah

    variabel, yaitu syarat umum bentuk baku sebuah pemrograman linear untuk simpleks adalah

    bahwa semua variabel harus bernilai non-negatif.

    Suatu variable yang bernilai tidak terbatas (unrestricted) berarti bahwa variabel tersebut bisa

    bernilai positif maupun negatif. Untuk variabel yang bernilai tidak terbatas (mungkin bernilai

    negatif) maka perlu diubah kedlam bentuk variabel non-negatif. Pengubahan variabel tidak

    terbatas menjadi variabel non-negatif dapat dilakukan dengan menjadikan variabel tersebut

    menjadi selisih dua variabel yang bernilai non-negatif.

  • Contoh,

    Maksimumkan Z = 15 x1 + 20 x2

    terhadap:

    3 x1 + 4 x2 10 (garis kendala 1)

    2 x1 + 5 x2 8 (garis kendala 2)

    x1 0, x2 tak terbatas (garis kendala 3)

    Agar x2 bernilai non-negatif maka x2 digantikan dengan variabel (x2 - x2) sehingga formulasi

    berubah menjadi:

    Maksimumkan Z = 15 x1 + 20 x2 - 20 x2

    terhadap:

    3 x1 + 4 x2 - 4 x2 10 (garis kendala 1)

    2 x1 + 5 x2 - 5 x2 8 (garis kendala 2)

    x1 0, x2 0, x2 0 (garis kendala 3)

    Bentuk baku dari formulasi diatas menjadi:

    Maksimumkan Z = 15 x1 + 20 x2 - 20 x2 + S1 + S2 terhadap:

    3 x1 + 4 x2 - 4 x2 + S1 = 10 (garis kendala 1)

    2 x1 + 5 x2 - 5 x2 + S2 = 8 (garis kendala 2)

    x1 0, x2 0, x2 0, S1 0, S2 0 (garis kendala 3)

    Contoh 1.

    Minimumkan z = 2 x1 + 5.5 x2

    terhadap:

    x1 + x2 = 90 (garis kendala 1)

  • 0.001 x1 + 0.002 x2 0.9 (garis kendala 2)

    0.09 x1 + 0.6 x2 27 (garis kendala 3)

    0.02 x1 + 0.06 x2 4.5 (garis kendala 4)

    x1, x2 0 (garis kendala 5)

    Bentuk di atas adalah bentuk umum pemrograman linearnya. Kedalam bentuk baku/standar,

    model matematik tersebut akan berubah menjadi:

    Minimumkan z = 2 x1 + 5.5 x2

    Terhadap:

    x1 + x2 + s1 = 90

    0.001 x1 + 0.002 x2 + s2 = 0.9

    0.09 x1 + 0.6 x2 - s3 = 27

    0.02 x1 + 0.06 x2 + s4 = 4.5

    x1, x2, s1, s2, s3, s4 0

    Fungsi kendala pertama mendapatkan variabel buatan (s1), karena bentuk umumnya sudah

    menggunakan bentuk persamaan.

    Fungsi kendala kedua dan keempat (s2 dan s4) mendapatkan variable slack karena bentuk

    umumnya menggunakan pertidaksamaan , sedangkan fungsi kendala ketiga mendapatkan

    surplus variable (s3) karena bentuk umumnya menggunakan pertidaksamaan ..

  • Contoh 2.

    Maksimumkan z = 2 x1 + 3 x2

    terhadap:

    10 x1 + 5 x2 600

    6 x1 + 20 x2 600

    8 x1 + 15 x2 600

    x1, x2 0

    Bentuk di atas juga merupakan bentuk umum. Perubahan kedalam bentuk baku hanya

    membutuhkan variable slack, karena semua fungsi kendala menggunakan bentuk

    pertidaksamaan dalam bentuk umumnya.

    Maka bentuk bakunya adalah sebagai berikut:

    Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3

    Terhadap :

    10x1 + 5x2 + s1 = 600

    6x1 + 20x2 + s2 = 600

    8x1 + 15x2 + s3 = 600

    x1, x2, s1, s2, s3 0

    Semua fungsi kendala (s1, s2 dan s3) mendapatkan variable slack karena bentuk umumnya

    menggunakan pertidaksamaan ,

  • 4.3 Pembentukan Tabel Simpleks

    Langkah-langkah pembentukan sebuah tabel simpleks:

    1. Memeriksa kelayakan tabel

    Kelayakan tabel simpleks dapat dilihat dari solusi (nilai kanan). Jika solusi ada yang

    bernilai negatif, maka tabel tidak layak. Tabel yang tidak layak tidak dapat diteruskan untuk

    proses optimalisasi.

    2. Menetukan kolom pivot

    Penentuan kolom pivot dilihat dari koefisien fungsi tujuan (nilai di sebelah kanan baris z)

    dan tergantung dari bentuk tujuan.

    Jika tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien

    negatif terbesar.

    Jika tujuan minimisasi, maka kolom pivot adalah kolom dengan koefisien positif

    terkecil.

    Perhatikan, kita tidak menggunakan kata-kata nilai terkecil dan terbesar, karena kita

    memang tidak memilih nilai terkecil dan terbesar. Jika kolom pivot ditandai dan ditarik ke

    atas, maka kita akan mendapatkan variabel keluar. Jika nilai negatif terbesar (untuk tujuan

    maksimisasi) atau positif terbesar (untuk tujuan minimisasi) lebih dari satu, pilih salah satu

    secara sembarang.

    3. Menetukan baris pivot

    Baris pivot ditentukan setelah membagi nilai solusi dengan nilai kolom pivot yang

    bersesuaian (nilai yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada

    kolom pivot tidak diperhatikan, artinya tidak ikut menjadi pembagi.

    Baris pivot adalah baris dengan rasio pembagian terkecil. Perhatikan, rasio pembagian tidak

    mungkin bernilai negatif, karena nilai kanan tidak negatif demikian juga dengan nilai kolom

    pivot.

    Jika baris pivot ditandai dan ditarik ke kiri, maka kita akan mendapatkan variabel keluar.

    Jika rasio pembagian terkecil lebih dari satu, pilih salah satu secara sembarang.

    4. Menentukan elemen pivot

    Elemen pivot merupakan nilai yang terletak pada perpotongan kolom dan baris pivot.

    5. Membentuk tabel simpleks baru.

  • Tabel simpleks baru dibentuk dengan pertama sekali menghitung nilai baris pivot baru.

    Baris pivot baru adalah baris pivot lama dibagi dengan elemen pivot. Baris baru lainnya

    merupakan pengurangan nilai kolom pivot baris yang bersangkutan dikali baris pivot baru

    dalam satu kolom terhadap baris lamanya yang terletak dalam satu kolom yang sama.

    6. Memeriksa apakah tabel sudah optimal.

    Keoptimalan tabel dilihat dari koefisien fungsi tujuan (nilai pada baris z) dan tergantung dari

    bentuk tujuan. Untuk tujuan maksimisasi, tabel sudah optimal jika semua nilai pada baris z

    sudah positif atau 0. Pada tujuan minimisasi, tabel sudah optimal jika semua nilai pada baris

    z sudah negatif atau 0. Jika belum, kembali ke langkah no.2, jika sudah optimal baca solusi

    optimalnya.

    Contoh.

    Jika diketahui bentuk baku sebagai berikut:

    Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3

    Terhadap :

    10x1 + 5x2 + s1 = 600

    6x1 + 20x2 + s2 = 600

    8x1 + 15x2 + s3 = 600

    x1, x2, s1, s2, s3 0

    Tabel awal simpleks dari persamaan baku diatas dapat dilihat pada Tabel 4.1.

    Tabel 4.1: Variabel baku

    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

  • Penyelesaian:

    1. Memeriksa kelayakan tabel

    Kelayakan tabel simpleks dapat dilihat dari solusi (nilai kanan).

    Tabel 4.1: Memeriksa kelayakan tabel

    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

    Solusi tidak ada yang bernilai negatif, maka tabel dianggap layak dan proses optimalisasi

    bisa diteruskan.

    2. Menetukan kolom pivot

    Tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien negatif

    terbesar.

    Tabel 4.2: Menentukan kolom pivot

    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

    Kolom pivot ditandai dan kemudian ditarik ke atas, maka diperoleh X2 sebagai variabel

    masuk.

    3. Menetukan baris pivot

    Baris pivot ditentukan setelah membagi nilai solusi dengan nilai kolom pivot yang

    bersesuaian (nilai yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada

    kolom pivot tidak diperhatikan, artinya tidak ikut menjadi pembagi.

  • Tabel 4.3: Menghitung rasio

    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

    Dari Tabel 4.3 didapatkan bahwa nilai rasio pembagi terkecil adalah 30 sehingga baris pivot

    adalah seperti yang ditunjukkan pada Tabel 4.4.

    Tabel 4.4: Menentukan baris pivot

    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

    Baris pivot ditandai dan kemudian ditarik ke kiri, maka diperoleh S2 sebagai variabel keluar.

    4. Menentukan elemen pivot

    Dari Tabel 4.4 terlihat bahwa nilai yang terletak pada perpotongan kolom dan baris pivot

    adalah 20; sehingga 20 disebut sebagai elemen pivot.

    5. Membentuk tabel simpleks baru.

    Iterasi ke-0.

    Tabel 4.4 kemudian digambarkan sebagai Tabel 4.5; tabel awal simpleks (itersi ke-0).

    Dimana X2 adalah variabel masuk, S2 adalah variabel keluar dan 20 adalah elemen pivot.

    Tabel 4.5: Tabel awal simpleks; iterasi ke-0

    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

  • Iterasi ke-1.

    Tabel simpleks baru (itersi ke-1) dibentuk dengan menghitung nilai baru baris pivot. Baris

    pivot baru adalah baris pivot lama dibagi dengan elemen pivot.

    Tabel 4.6: Nilai baru baris pivot

    Variabel Baku X1 X2 S1 S2 S3 Solusi Rasio Z S1 X2 6/20 20/20 0 1/20 0 600/20 30 S3

    Nilai baru untuk baris selain baris pivot = Nilai lama - (Nilai pada kolom kerja * Nilai baru

    baris pivot).

    Nilai pada kolom kerja adalah nilai pada titik perpotongan kolom pivot dengan baris yang

    akan dicari nilai baru-nya.

    Tabel 4.7: Nilai baru baris pivot; baris ke-1

    X1 X2 S1 S2 S3 Solusi Z lama -2 -3 0 0 0 0

    -3 6/20 20/20 0/20 1/20 0/20 600/20 Z baru -2 - (-3*6/20) = - 1.1

    -3 - (-3*20/20) = 0

    0 - (-3*0) = 0

    0 - (-3*1/20) = 0.15

    0 - (-3*0) = 0

    0 - (-3*600/20) = 90

    Tabel 4.8: Nilai baru baris pivot; baris ke-2

    X1 X2 S1 S2 S3 Solusi S1 lama 10 5 1 0 0 600

    5 6/20 20/20 0/20 1/20 0/20 600/20 S1 baru 10 - (5*6/20) = 8.5

    5 - (5*20/20) = 0

    1 - (5*0) = 1

    0 - (5*1/20) = -0,25

    0 - (5*0) = 0

    600 - (5*600/20) = 450

  • Tabel 4.9: Nilai baru baris pivot; baris ke-4

    X1 X2 S1 S2 S3 Solusi S3 lama 8 15 0 0 1 600

    15 6/20 20/20 0/20 1/20 0/20 600/20 S3 baru 8 - (15*6/20) = 3.5

    15 - (15*20/20) = 0

    0 - (15*0) = 0

    0 - (15*1/20) = -0,75

    1 - (15*0) = 1

    600 - (15*600/20) = 150

    Memasukkan nilai-nilai Zbaru, S1 baru dan S3 baru kedalam Tabel 4.6. Dan diperoleh Tabel 4.10

    sebagai tabel nilai baru untuk interasi ke-2.

    Tabel 4.10: Tabel nilai baru; iterasi ke-1

    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

    Dari Tabel 4.10 terlihat bahwa masih terdapat nilai negative pada fungsi tujuan sehingga

    dapat dinyatakan bahwa solusi yang diperoleh belum optimal. Untuk itu perlu dilakukan

    perbaikan solusi dengan cara lanjut ke iterasi berikutnya.

    Iterasi ke-2.

    Tujuan berupa maksimisasi, maka kolom pivot adalah kolom dengan koefisien negatif

    terbesar.

    Tabel 4.11: Menentukan kolom pivot untuk iterasi ke-1

    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

  • Tabel 4.12: Menghitung rasio untuk iterasi ke-1

    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

    Dari Tabel 4.12 didapatkan bahwa nilai rasio pembagi terkecil adalah 42,857 sehingga baris

    pivot adalah seperti yang ditunjukkan pada Tabel 4.13.

    Tabel 4.13: Menentukan baris pivot

    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

    Variabel masuk adalah x1, variabel keluar adalah S3 dan 3,5 adalah elemen pivot.

    Tabel simpleks baru (itersi ke-2) dibentuk dengan menghitung nilai baru baris pivot. Baris

    pivot baru adalah baris pivot lama dibagi dengan elemen pivot.

    Tabel 4.14: Nilai baru baris pivot

    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

    Nilai baru untuk baris selain baris pivot = Nilai lama - (Nilai pada kolom kerja * Nilai baru

    baris pivot).

    Nilai pada kolom kerja adalah nilai pada titik perpotongan kolom pivot dengan baris yang

    akan dicari nilai baru-nya.

  • Tabel 4.15: Nilai baru baris pivot; baris ke-1

    X1 X2 S1 S2 S3 Solusi Z lama -1,1 0 0 0,15 0 90

    -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

    0 - (-1,1*0) = 0

    0 - (-1,1*0) = 0

    0,15 - (-1,1*-0,2143) = 0,1264

    0 - (-1,1*0,2857) = 0.3143

    900 - (-1,1*42,857) = 137,1429

    Tabel 4.16: Nilai baru baris pivot; baris ke-2

    X1 X2 S1 S2 S3 Solusi S1 lama 8,5 0 1 -0,25 0 450

    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

    0 - (8,5*0) = 0

    1 - (8,5*0) = 1

    -0,25 - (8,5*-0,2143) = 1,5715

    0 - (8,5*0,2857) = -2,4285

    450 - (8.5*42,857) = 85,7155

    Tabel 4.17: Nilai baru baris pivot; baris ke-3

    X1 X2 S1 S2 S3 Solusi X2 lama 6/20 20/20 0 1/20 0 600/20

    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

    1 - (0,3*0) = 1

    0 - (0,3*0) = 0

    0,05 - (0,3*-0,2143) = 0,...