Variabel Buatan (Artificial Variable) dalam Pemrograman Linear

Variabel buatan adalah konsep penting dalam metode Simplex untuk menyelesaikan masalah pemrograman linear (LP) yang tidak memiliki solusi awal yang feasible (layak). Variabel ini ditambahkan ke dalam persamaan kendala agar setiap kendala dapat dipenuhi dengan nilai nonnegatif pada tahap awal iterasi.

1. Mengapa Variabel Buatan Diperlukan?

Pemrograman linear biasanya ditulis dalam bentuk standar:

• Fungsi tujuan: maximisez = cx
• Kendala: Ax b,x 0

Jika semua elemen b bernilai positif, solusi awal dapat diambil dengan memberi nilai nol pada semua variabel keputusan (x) dan menambahkan variabel slack (atau surplus) untuk mengubah ketidaksamaan menjadi persamaan. Namun, bila terdapat b negatif atau kendala yang berupa persamaan =, solusi awal yang feasible tidak langsung tersedia. Di sinilah variabel buatan masuk.

2. Cara Menambahkan Variabel Buatan

Untuk setiap kendala yang tidak dapat dipenuhi dengan variabel slack/surplus saja, tambahkan satu variabel buatan a. Bentuk umum persamaannya menjadi:

        a + (variabel slack/surplus) +  (koefisien  x) = b    

Semua variabel buatan diinisialisasi dengan nilai b (yang biasanya positif setelah mengalikan kendala dengan 1 bila b negatif). Karena variabel buatan tidak memiliki arti dalam model asli, tujuan selanjutnya adalah mengeluarkannya dari basis solusi dengan cara meminimalkan totalnya.

3. Metode Dua Fase

Metode yang paling umum untuk menangani variabel buatan adalah Metode Dua Fase:

Fase1

• Tujuan: meminimalkan a (jumlah semua variabel buatan).
• Jika nilai optimum fase1 = 0, semua variabel buatan dapat dihapus; solusi feasible untuk masalah asli telah ditemukan.
• Jika nilai optimum > 0, maka tidak ada solusi feasible pada masalah asli (model tidak konsisten).

Fase2

• Setelah semua variabel buatan keluar dari basis, gunakan solusi feasible tersebut sebagai titik awal bagi metode Simplex standar untuk mengoptimalkan fungsi tujuan asli.
• Jika fase1 menghasilkan nilai optimum 0, fase2 akan menghasilkan solusi optimal masalah asli (max atau min).

4. Metode BigM

Alternatif lain adalah Metode BigM. Dalam metode ini, variabel buatan ditambahkan ke fungsi tujuan dengan koefisien sangat besar M (positif untuk maksimisasi, negatif untuk minimisasi):

        maxz = cx  M a   (atau  minz = cx + M a)    

Koefisien M dipilih cukup besar supaya solusi optimal tidak akan menyertakan variabel buatan kecuali tidak ada solusi feasible lain. Kekurangan utama ialah pemilihan nilai M yang terlalu besar dapat menimbulkan masalah numerik.

5. Contoh Praktis

Misalkan masalah:

        maxz = 3x + 5x        s.t.            2x +  x  8            x + 3x  12            x , x  0    

Langkahlangkah:

1. Ubah semua kendala menjadi persamaan.
   • Untuk gunakan slack s.
   • Untuk gunakan surplus s dan variabel buatan a.
2. Model menjadi:

                   s + a = 8  2x  x                 s    = 12  x  3x                 x , x , s , s , a  0            

3. Fase1: minimalkan a. Jika optimum = 0, a keluar dari basis dan solusi feasible (misalnya x=2, x=2) tercapai.
4. Fase2: gunakan titik feasible tersebut untuk memaksimalkan z = 3x + 5x, menghasilkan solusi optimal z = 16 pada (x=2, x=2).

6. Kapan Hindari Penggunaan Variabel Buatan?

Jika semua kendala sudah dalam bentuk dengan b positif, cukup tambahkan variabel slack dan langsung gunakan Simplex tanpa fase tambahan. Penggunaan variabel buatan menambah ukuran tabel Simplex dan meningkatkan beban komputasi, sehingga sebaiknya dihindari bila tidak diperlukan.

7. Kesimpulan

Variabel buatan adalah alat bantu yang memungkinkan algoritma Simplex memulai iterasi pada titik feasible ketika model asli tidak menyediakan titik tersebut secara langsung. Dua pendekatan utamaMetode Dua Fase dan Metode BigMmenyediakan cara sistematis untuk mengeliminasi variabel buatan dan melanjutkan proses optimasi. Memahami cara menambah, mengelola, dan menghilangkan variabel buatan merupakan keterampilan penting bagi praktisi optimasi dan analis operasi.