Teknik Artificial Variabel

Teknik Artificial Variabel

Progam Linier dengan kendala ³ atau = : Metode Teknik M

vPembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda  ≥ dan atau bertanda =

vUntuk menyelesaikan kasus tersebut kita memerlukan variable dummy(variable palsu) atau artificial var. sehingga basis awal bisa tetap ada .

vUntuk tanda ≥ masih menggunakan variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.

vContoh :

  Maksimumkan Z = 3X1 + 5X2

  Berdasarkan kendala :

  X1              ≥ 4

             2X2 ≥ 12

  3X1 + 2X2 = 18

  X1, X2 ≥ 0 

Program Linier dengan kendala ³ atau = lanjutan

vJika 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

vPerhatikan 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 Program Linear dengan Teknik M

vMetoda 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

  

Berdasarkan kendala :

  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 Program Linear lanjutan

vTerlihat pd. Tabel 1 (iterasi 0), X1 terpilih sebagai entering var. (koef. Negatip terbesar) dan S1 terpilih sebagai leaving var. (memp. Ratio terkecil).

vKarena koef. Entering var. untuk S1 adalah 1, pers. poros baru (X1) pada Tabel 2 sama dengan pers poros lama (S1) pada Tabel 1.

vPers. 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).

vPers. 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.

vHasil selengkapnya ditampilkan pada Tabel 2 (iterasi 1).

vDari Tabel 2, X2 terpilih sebagai entering v. dan R1 terpilih sebagai leaving var., dan pers. /baris Z, X1 yang baru dihitung seperti halnya pada iterasi sebelumnya, sehingga diperoleh hasil sebagai mana ditampilkan pada iterasi 2 (Tabel 3).

vDari iterasi 3 (Tabel 4), tampak bahwa koef. Pers. /baris Z berharga positip atau nol, sehingga solusi yang optimal telah diperoleh.

vSolusi yang optimal adalah : Z = 36, X1 = 2, dan X2 = 6 (harga-harga tersebut dilihat pada kolom RK).

Contoh 2.

Minimumkan Z = 3x1 + 2x2

  berdasarkan kendala :

  3x1  +        x2 ³ 20

           .25x1  +   .50x2 £  4

              x1  +        x2 = 10 

         x1 ³ 0, x2 ³ 0

      Penyelesaian : Susun bentuk standar PL di

       atas :

Penyelesaian :

Minimumkan 

Z = 3x1 + 2x2 + 0s1 + 0s2 + MR1 + MR2

      3x1  +  x2  -   s1      + R1          = 20

   .25x1 +  .5 x2     +  s2                             =  4

       x1 +      x2                            +    R2    = 10

  x1 ³ 0, x2 ³ 0, s1, s2, R1, R2 ³ 0

dengan M bilangan yang besar

Substitusikan R1 = 20 - 3x1 - x2 + s1     dan

            R2 = 10 - x1 - x2     pada pers. Z, diperoleh :

Z = 3x1+2x2+M(20 - 3x1 - x2 + s1) + M(10 - x1 - x2)

Atau Z = (-4M+3)x1 + (-2M+2)x2 +Ms1 + 30M

Atau Z + (4M-3)x1 + (2M-2)x2 – Ms1 = 30 M

Pers. Z yg mempunyai koef. positip terbesar adalah x1 sebesar 4M-3, sehingga x1 

menjadi entering v., sedangkan yang mempunyai ratio terkecil adalah R1 sebesar 20/3 , 

sehingga R1 menjadi leaving variabel

Pers. lain yang baru = pers. lain yang lama – koef. Entering x pers. poros baru seperti 

tampak pada Tabel 2. Selanjutnya x2 menjadi entering var. sedangkan R2 menjadi 

leaving var. dan diperoleh Tabel 3 berikut ini.  Tampak pada Tabel 3, koef Z berharga 

negatip atau nol, sehingga solusi optimal tercapai dengan Z = 25, x1 = 5, dan x2 = 5.

Contoh Soal 3 PL dg Teknik M

vPerusahaan minuman Bevco memproduksi  minuman tanpa alkohol Super-Orange.

Super-Orange dibuat dengan  mengkombinasikan  air soda rasa jeruk  dengan  jus 

jeruk. Setiap  air soda rasa jeruk mengandung 0.5 ons gula dan 1 mg vitamin C. 

Setiap  ons jus  jeruk mengandung 0.25 oms gula dan 3 mg vitamin C. Biaya untuk 

memproduksi 1 ons air soda rasa jeruk adalah  2¢, sedangkan 1 ons jus jeruk 

diproduksi dengan biaya 3¢. Bagian pemasaran perusahaan Bevco memutuskan 

bahwa setiap botol Super-Orange ukuran  10-ons paling sedikit mengandung 30 mg 

vitamin C dan paling banyak 4 ons gula. Dengan menggunakan program linier, 

bagaimana Bevco dapat memenuhi kebutuhan bagian pemasaran dengan biaya 

produksi minimum.

Solusi Masalah Menggunakan Metode Big M

Misalkan :

       x1 = besarnya kandungan (ons) air soda rasa jeruk dalam botol

       x2 = besarnya kandungan (ons) jus jeruk dalam botol

Persoalan di atas mempunyai model PL sbb. :

min z = 2x1 +    3x2 , dengan Z adalah biaya produksi      

Berdasarkan kendala : 

  0.5x1  + 0.25x2   ≤  4  (gula)

     x1 +    3x2      ≥ 20  (Vitamin C)

     x1 +     x2      = 10  (10 ons dalam 1 botol)

     x1, x2   ³ 0

Bentuk standar PL masalah ini ditampilkan dalam slide berikut : 

Baris 1 :  -z  +  2x1  +        3x2      = 0

Baris 2 :  0.5x1  +   0.25x2 + s1      =  4

Baris 3 : x1 +         3x2       - s2 = 20

Baris 4 :x1 +           x2             = 10

Dengan menggunakan teknik artificial variables,  yakni dengan menambahkan variabel 

artifisial a2 pada baris ketiga dan a3 pada baris keempat. Variabel a2 dan a3 ditulis 

hitam, maka diperoleh :

Baris 1 :  -z  +  2x1 +      3x2    = 0

Baris 2 :  0.5x1  + 0.25x2 + s1   =  4

Baris 3 :  x1 +  3x2 - s2 + a2    = 20

Baris 4 :  x1 +  x2   + a3  = 10

Jika iterasi ini diteruskan akan diperoleh solusi :

  x1 = x2 = 5, dan z = 25.

Artinya perusahaan itu akan memenuhi tuntutan bagian pemasaran dengan menentukan kandungan air soda rasa jeruk (x1) dan kandungan jus jeruk (x2) dalam botol sebesar 5 ons agar biaya (z) memproduksi air soda rasa jeruk dan jus jeruk minimal sebesar 25¢.

Catatan : solusi ini diperoleh dengan menggunakan software POM for Windows.

Metode Dua Phasa

vDigunakannya konstanta M ( bilangan positif yang sangat besar) sebagai penalty,

bisa terjadi kesalahan perhitungan, terutama apabila perhitungan itu dilakukan 

dengan menggunakan computer. Kesalahan itu bisa terjadi karena koefisien fungsi 

tujuan relative sangat kecil dibandingkan dengan harga M sehingga computer akan 

memperlakukannya sebagai koefisien yang berharga nol. Kesulitan ini bisa dikurangi 

dengan menggunakan metoda dua fase. Disini konstanta M dihilangkan dengan cara 

menyelesaikan persoalan dalam dua fase sebagai berikut :

vFase 1 : Fase ini digunakan untuk menguji apakah persoalan yang kita hadapi 

memiliki solusi fisibel atau tidak. Pada fase ini fungsi tujuan semula diganti dengan 

meminimumkan jumlah variable artifisialnya. Jika nilai minimum fungsi tujuan baru ini 

berharga nol, berarti persoalan memiliki solusi fisibel, lanjutkan ke fase 2 tetapi, jika 

nilai minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki 

solusi fisibel. STOP

Metode Dua Phasa Lanjutan

vFase 2 :

  Gunakan solusi basis optimum dari fase 1 sebagai

  solusi awal bagi persoalan semula. Dalam hal ini

  ubahlah bentuk fungsi tujuan fase 1 dengan

  mengembalikannya pada fungsi tujuan persoalan

  semula.

  Pemecahan persoalan dilakukan dengan cara seperti biasa.

Contoh Soal  PL Metode Dua Phasa 

vContoh 1 :

  Tentukan solusi optimal masalah PL berikut :

  Maksimumkan Z = 3X1 + 5X2

vBerdasarkan kendala :

  X1              ≤ 4

  2X2 ≤ 12

  3X1 +  2X2 = 18

  X1, X2 ≥ 0

  Penyelesaian :  

Solusi PL menggunakan Metode Dua Fase :

Bentuk standar :

Maksimumkan Z = 3X1 + 5X2 + 0.S1 + 0.S2 – M.R1

Berdasarkan kendala :

  X1              + S1                  = 4

             2X2         + S2          = 12

  3X1 + 2X2                 + R1 = 18

  X1, X2, S1, S2, R1 ≥ 0

Dari persamaan diatas diperoleh harga R3 = 18 – 3X1 – 2X2

Fase 1 :

Minimumkan r = R3 atau r = 18 – 3X1 – 2X2

Berdasarkan kendala :

  X1              + S1                   = 4

             2X2         + S2           = 12

  3X1 + 2X2                  + R3   = 18

  X1, X2, S1, S2, R3 ≥ 0 

Iterasi 1,2, dan 3 Fase 1 :

Persoalan diatas memiliki solusi fisibel, karena solusinya nol. Selanjutnya R tidak diikutsertakan lagi.

Fase 2 :

Dari table optimum pada fase 1 di atas dapat dituliskan persamaan persamaan berikut :

  X1 + S1 = 4 →X1 = 4 – S1

  3S1 + S2 = 6

  X2 - 3/2 S1 = 3 →X2 = 3 + 3/2 S1

Kembali kepada model persoalan semula, dan dengan mensubtitusi persamaan persamaan diatas kita dapatkan :

Maksimumkan Z = 3(4 – S1) + 5(3- 3/2 S1 )

  atau Z = 9/2 S1 + 27

  Berdasarkan kendala :

  X1              + S1          = 4

        3S1 + S2 = 6

          X2 – 3/2 S1        = 3

Akan diperoleh solusi yang optimal X1= 2, X2 = 6 dengan Z = 36, sebagaimana tampak pada tabel berikut ini. 

Iterasi 1 dan 2 Fase 2 :