Page 62 - e-book PROGRAM LINEAR okeeee

menggunakan bentuk pertidaksamaan ≥, perubahan dari bentuk
umum ke bentuk baku memerlukan satu variabel surplus. Variabel
surplus tidak dapat berfungsi sebagai variabel basis awal, karena
koefisiennya bertanda negatif. Sebagai variabel basis pada solusi
awal, harus ditambahkan satu variabel buatan. Variabel buatan
pada solusi optimal harus bernilai 0, karena variabel ini memang
tidak ada.

Pada pendekatan ini, artifisial variabel dalam fungsi tujuan diberi
suatu biaya sangat besar (dalam perhitungan komputer biasanya 3 atau 4
kali besarnya dibanding bilangan lain dalam model). Dalam praktek,
huruf M digunakan sebagai biaya dalam masalah minimasi dan -M
sebagai keuntungan dalam masalah maksimasi dengan asumsi bahwa M
adalah suatu bilangan positif yang besar.

Satu kekurangan dari metode M ini adalah kemungkinan kesalahan
perhitungan yang dapat dihasilkan dari pemberian nilai yang terlalu besar
untuk konstanta M. Kasus minimasi harus diubah menjadi maksimasi
dengan cara mengganti tanda positif dengan negative pada fungsi tujuan.
Sedangkan pada fungsi kendala ditambahkan variabel buatan. Variabel
buatan tersebut yang bertidak sebagai variabel dasar (variabel basis).

2. Contoh Kasus
Contoh 1)
Cari x1, x2
s.r.s Z = 5x1 + 3x2
d.p 2x1 + x2 ≥ 3
x1 + x2 ≥ 2
x1 ≥ 0, x2 ≥ 0
Persoalan minimum dirubah menjadi maksimum
-Z = -5x1 – 3x2 → -Z = Z*
Z* = -5x1 - 3x2 ; maksimum
2x1 + x2 - x3 = 3
x1 + x2 + x4 = 2
1
2 1 −1 0 2 3
[ ] [ ] = [ ]
1 1 0 −1 3 2
4

Matrik A tidak memenuhi identity matriks

61