Progam Linier dg kendala ≥ atau = : Metode Teknik M.
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.
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 .
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 :
V.
BASIS
|
Z
|
X1
|
X2
|
S1
|
S2
|
R1
|
RK
|
RATIO
|
Z
|
1
|
-3M-3
|
-2M-5
|
0
|
0
|
0
|
-18M
|
|
S1
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
4/1 =
4
|
S2
|
0
|
0
|
2
|
0
|
1
|
0
|
12
|
Abaikan
|
R1
|
0
|
3
|
2
|
0
|
0
|
1
|
18
|
18/3 =
6
|
V.
BASIS
|
Z
|
X1
|
X2
|
S1
|
S2
|
R1
|
RK
|
RATIO
|
Z
|
1
|
0
|
-2M-5
|
3M+3
|
0
|
0
|
-6M+12
|
|
X1
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
Abaikan
|
S2
|
0
|
0
|
2
|
0
|
1
|
0
|
12
|
12/2=6
|
R1
|
0
|
0
|
2
|
-3
|
0
|
1
|
6
|
6/2=3
|
Terlihat pd. Tabel 1 (iterasi 0), X1 terpilih sebagai
entering var. (koef. Negatip terbesar) dan S1 terpilih sebagai leaving var.
(memp. Ratio terkecil).
Karena koef. Entering var. untuk S1 adalah 1, pers. poros
baru (X1) pada Tabel 2 sama dengan pers poros lama (S1) pada Tabel 1.
Pers. 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).
Pers. 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.
Hasil selengkapnya ditampilkan pada Tabel 2 (iterasi 1).
Dari 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).
Dari iterasi 3 (Tabel 4), tampak bahwa koef. Pers. /baris
Z berharga positip atau nol, sehingga solusi yang optimal telah diperoleh.
Solusi yang optimal adalah : Z = 36, X1 = 2, dan X2 = 6
(harga-harga tersebut dilihat pada kolom RK).
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
|
Metode Dua Phasa adalah 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
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.
Contoh Soal PL
Metode Dua Phasa :
Contoh 1 :
Tentukan
solusi optimal masalah PL berikut :
Maksimumkan
Z = 3X1 + 5X2
Berdasarkan kendala :
X1 ≤ 4
2X2
≤ 12
3X1
+ 2X2 = 18
X1,
X2 ≥ 0
Penyelesaian
:
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 :
Basis
|
X1
|
X2
|
S1
|
S2
|
R3
|
RK
|
r
|
3
|
2
|
0
|
0
|
0
|
18
|
S1
|
1
|
0
|
1
|
0
|
0
|
4
|
S2
|
0
|
2
|
0
|
1
|
0
|
12
|
R3
|
3
|
2
|
0
|
0
|
1
|
18
|
r
|
0
|
2
|
-3
|
0
|
0
|
6
|
X1
|
1
|
0
|
1
|
0
|
0
|
4
|
S2
|
0
|
2
|
0
|
1
|
0
|
12
|
R3
|
0
|
2
|
-3
|
0
|
1
|
6
|
r
|
0
|
0
|
0
|
0
|
-1
|
0
|
X1
|
1
|
0
|
1
|
0
|
0
|
4
|
S2
|
0
|
0
|
3
|
1
|
-1
|
6
|
X2
|
0
|
1
|
-3/2
|
0
|
1/2
|
3
|
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.
Basis
|
X1
|
X2
|
S1
|
S2
|
RK
|
Z
|
0
|
0
|
-9/2
|
0
|
27
|
X1
|
1
|
0
|
1
|
0
|
4
|
S2
|
0
|
0
|
3
|
1
|
6
|
X2
|
0
|
1
|
-3/2
|
0
|
3
|
Z
|
0
|
0
|
0
|
3/2
|
36
|
X1
|
1
|
0
|
0
|
-1/3
|
2
|
S2
|
0
|
0
|
1
|
1/3
|
2
|
X2
|
0
|
1
|
0
|
1/2
|
6
|
Tampak bahwa diperoleh solusi optimal X1 = 2, X2 = 6, dengan
Z = 36.
Ok.. Terima Kasih atas Postingnya !!!.....
BalasHapus