Teknik Artificial Variabel
Progam Linier dg kendala ³ atau = : Metode Teknik M
v Pembahasan terdahulu hanya
kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda ≥ dan atau bertanda =
v Untuk menyelesaikan kasus
tersebut kita memerlukan variable dummy(variable palsu) atau artificial var.
sehingga basis awal bisa tetap ada .
v Untuk tanda ≥ masih menggunakan
variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.
v Contoh :
Maksimumkan
Z = 3X1 + 5X2
Berdasarkan
kendala :
X1 ≥ 4
2X2 ≥ 12
3X1
+ 2X2 = 18
X1, X2 ≥ 0
PL dg kendala ³ atau = lanjutan
v 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
v 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
v 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 = -
Sehingga
tabel simpleks awal (iterasi 0) dan
iterasi ke 1 diberikan dalam tabel berikut ini :
Contoh 1
Solusi PL lanjutan
v Terlihat
pd. Tabel 1 (iterasi 0), X1 terpilih sebagai entering var. (koef. Negatip
terbesar) dan S1 terpilih sebagai leaving var. (memp. Ratio terkecil).
v Karena
koef. Entering var. untuk S1 adalah 1, pers. poros baru (X1) pada Tabel 2 sama
dengan pers poros lama (S1) pada Tabel 1.
v 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).
v 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.
v Hasil
selengkapnya ditampilkan pada Tabel 2 (iterasi 1).
v Dari
Tabel 2, X2 terpilih sebagai entering v. dan R1 terpilih sebagai leaving var.,
dan pers. /baris Z, X1 yang baru dihitung seperti halnya
Contoh 1
Solusi PL lanjutan
Pada iterasi
sebelumnya, sehingga diperoleh hasil sebagai mana ditampilkan pada iterasi 2
v Dari
iterasi 3 ), tampak bahwa koef. Pers. /baris Z berharga positip atau
nol, sehingga solusi yang optimal telah diperoleh.
v Solusi
yang optimal adalah : Z = 36, X1 = 2, dan X2 = 6 (harga-harga tersebut dilihat
pada kolom RK).
Contoh
Soal PL dg Teknik M
Perusahaan
minuman Bevco memproduksi minuman tanpa
alkohol Super-Orange. Super-Orange
dibuat dengan mengkombinasikan air soda rasa jeruk dengan
jus jeruk. Setiap air soda rasa
jeruk mengandung 0.5 ons gula dan 1 mg vitamin C. Setiap ons jus
jeruk mengandung 0.25 oms gula dan 3 mg vitamin C. Biaya untuk
memproduksi 1 ons air soda rasa jeruk adalah
2¢, sedangkan 1 ons jus jeruk diproduksi dengan biaya 3¢. Bagian
pemasaran perusahaan Bevco memutuskan bahwa setiap botol Super-Orange ukuran 10-ons paling sedikit mengandung 30 mg vitamin
C dan paling banyak 4 ons gula. Dengan menggunakan program linier, bagaimana
Bevco dapat memenuhi kebutuhan bagian pemasaran dengan biaya produksi minimum.
Solusi
Masalah Menggunakan Metode Big M
Misalkan :
x1 = besarnya kandungan (ons) air soda
rasa jeruk dalam botol
x2 = besarnya kandungan (ons) jus jeruk
dalam botol
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
Solusi
Contoh Soal
Jika iterasi
ini diteruskan akan diperoleh solusi :
x1 = x2 = 5, dan z = 25.
Artinya
perusahaan itu akan memenuhi tuntutan bagian pemasaran dengan menentukan
kandungan air soda rasa jeruk (x1) dan kandungan jus jeruk (x2) dalam botol
sebesar 5 ons agar biaya (z) memproduksi air soda rasa jeruk dan jus jeruk
minimal sebesar 25¢.
Catatan : solusi ini diperoleh
dengan menggunakan software POM for Windows.
Metode
Dua Phasa
v 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 :
v 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.
Metode
Dua Phasa Lanjutan
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
v Contoh
1 :
Tentukan solusi optimal masalah
PL berikut :
Maksimumkan Z = 3X1 + 5X2
v Berdasarkan
kendala :
X1 ≤ 4
2X2
≤ 12
3X1 + 2X2 = 18
X1, X2 ≥ 0
Solusi PL
menggunakan Metode Dua Fase :
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
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.
End >>>> Next Materi 5
Ok.. Terima Kasih atas Postingnya !!!.....
ReplyDelete