Teknik Artificial Variabel [ Materi 4 ]

Teknik Artificial Variabel

Progam Linier dg kendala ³ atau = : Metode Teknik M

• Pembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda  ≥ dan atau bertanda =
• Untuk menyelesaikan kasus tersebut kita memerlukan variable dummy(variable palsu) atau artificial var. sehingga basis awal bisa tetap ada .
• Untuk tanda ≥ masih menggunakan variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.
• Contoh : 

          Maksimumkan Z = 3X1 + 5X2

          Berdasarkan kendala :

          X1              ≥ 4

             2X2 ≥ 12

         3X1 + 2X2 = 18

         

         X1, X2 ≥ 0 

PL dg kendala ³ atau = lanjutan

•   Jika dituliskan dalam  bentuk standar :

            Maksimumkan Z = 3X1 + 5X2 +0S1 + 0S2 – MR1– MR2 – MR3

           Atau

            Z – 3X1 – 5X2 + 0S1 + 0S2  + MR1 + MR2 + MR3 = 0

           X1         - S1            +   R1                             = 4

             2X2           – S2                  + R2                = 12

           3X1  + 2X2                                                   + R3  = 18

           X1, X2 , S1 , S2 , R1 , R2 , R3 ≥ 0

• Perrhatikan bahwa penalty M di atas bertanda (–) karena fungsi tujuannya maksimasi, jika fungsi tujuannya minimasi, maka penalty bertanda (+), dengan M adalah bilangan yang cukup besar. 

 

Contoh 1 Solusi PL dg Teknik M

Metoda Big M (metode penalty)

Contoh 1 : Cari solusi PL berikut ini :

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala :

  X1              ≤ 4

             2X2 ≤ 12

  3X1 + 2X2 = 18

  X1, X2 ≥ 0

 Penyelesaian :

Karena pembatas ketiga bertanda ( = ) maka untuk mendapatkan solusi basis awalnya kita harus menambahkan variable artificial sehingga diperoleh bentuk :

Maksimumkan :

  Z = 3X1 + 5X2 + 0.S1 + 0.S2 – MR1

 

 

  X1              + S1                 = 4

  2X2                  + S2           = 12

  3X1 + 2X2                + R1 = 18

  X1, X2, R1 , S1, S2 ≥ 0

 Untuk memasukan model diatas kedalam bentuk table, maka terlebih dahulu subtitusikan 

 R1 dari persamaan kendala ketiga :

  

 R1 = 18 - 3X1 + 2X2

  Kemudian masukan kedalam persamaan Z :

  Z = 3X1 + 5X2 + 0.S1 + 0.S2 – M(18 - 3X1 + 2X2 )

  Atau

  Z = (3M + 3)X1 + (2M – 5)X2 + 0.S1 + 0.S2 – 18M     atau

  Z - (3M + 3)X1 - (2M – 5)X2 - 0.S1 - 0.S2 = -18M

Sehingga tabel simpleks awal (iterasi 0)  dan iterasi ke 1 diberikan dalam tabel berikut ini :

 Contoh 1 Solusi PL lanjutan

•         Terlihat pd. Tabel 1 (iterasi 0), X1 terpilih sebagai entering var. (koef. Negatip terbesar) dan S1 terpilih sebagai leaving var. (memp. Ratio terkecil).
•          Karena koef. Entering var. untuk S1 adalah 1, pers. poros baru (X1) pada Tabel 2 sama dengan pers poros lama (S1) pada Tabel 1.
•          Pers. Z yg baru = Pers. Z yg lama – koef. Entering x pers. poros baru
•          baris Z baru = Z lama – (3M+3) x pers./baris poros baru ® ini merupakan OBE (operasi baris elementer).
•          Pers. R1 yg baru = pers. R1 yg lama – koef. Entering x pers.poros baru
•          baris R1 baru = baris R1 lama – 3 x per./baris poros baru.
•          Hasil selengkapnya ditampilkan pada Tabel 2 (iterasi 1).
•          Dari Tabel 2, X2 terpilih sebagai entering v. dan R1 terpilih sebagai leaving var., dan pers. /baris Z, X1 yang baru dihitung seperti halnya.