Teknik
Artificial Variabel
PL dg 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 PL dg 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
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 :
Progam Linier dg 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
|
V. BASIS
|
Z
|
X1
|
X2
|
S1
|
S2
|
R1
|
RK
|
RATIO
|
|
Z
|
1
|
0
|
0
|
-9/2
|
0
|
(M+5)/2
|
27
|
|
|
X1
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
4/1 = 4
|
|
S2
|
0
|
0
|
0
|
3
|
1
|
-1
|
6
|
6/3=2
|
|
X2
|
0
|
0
|
1
|
-3/2
|
0
|
1/2
|
3
|
abaikan
|
|
V. BASIS
|
Z
|
X1
|
X2
|
S1
|
S2
|
R1
|
RK
|
RATIO
|
|
Z
|
1
|
0
|
0
|
0
|
3/2
|
M+1
|
36
|
|
|
X1
|
0
|
1
|
0
|
0
|
-1/3
|
1/3
|
2
|
|
|
S1
|
0
|
0
|
0
|
1
|
1/3
|
-1/3
|
2
|
|
|
X2
|
0
|
0
|
1
|
0
|
1/2
|
0
|
6
|
|
|
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 : |
||||||||
