Teknik Artificial Variabel

Progam Linier dengan kendala  Metode Teknik M

Pembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda ≥ dan atau bertanda =  maka 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

Perhatikan 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

Contoh 1 Solusi PL dg Teknik M

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 :

Solusi Masalah Menggunakan Metode Big M

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 :

Solusi Masalah Menggunakan Metode Big M

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

Metode Dua Phasa

Digunakannya 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 : 

 

Fase 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

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