Progam Linier
dg kendala ³ atau
= : Metode Teknik M
Pembahasan yang kemarin hanya
kendala bertanda ≤ , maka berikutnya artikel ini selanjutnya untuk kendala
bertanda ≥ dan atau bertanda =
Untuk menyelesaikan kasus
tersebut kita memerlukan variable dummy (variable palsu) atau artificial var.
sehingga basis awal bisa tetap ada .
Untuk tanda ≥ masih menggunakan
variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.
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.
Contoh 1
Solusi PL dg Teknik M
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 = -18M
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
|
Sehingga tabel simpleks awal (iterasi 0) dan iterasi ke 1 diberikan dalam tabel berikut
ini:
Contoh 1
Solusi PL lanjutan
- 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
Contoh 1
Solusi PL lanjutan
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
|
Contoh 2
Solusi PL dgTeknik M
Penyelesaian :
Minimumkan
Z = 3x1 + 2x2 +
0s1 + 0s2 + MR1 + MR2
3x1
+ x2 - s1
+ R1 = 20
.25x1 +
.5 x2 + s2 = 4
x1 +
x2
+ R2 = 10
x1 ³ 0, x2 ³ 0, s1, s2, R1, R2 ³ 0
dengan M
bilangan yang besar
Substitusikan R1
= 20 - 3x1 - x2 + s1 dan
R2 = 10 - x1 - x2 pada pers. Z, diperoleh :
Z = 3x1+2x2+M(20
- 3x1 - x2 + s1) + M(10 - x1 - x2)
Atau Z =
(-4M+3)x1 + (-2M+2)x2 +Ms1 + 30M
Atau Z +
(4M-3)x1 + (2M-2)x2 – Ms1 = 30 M
Var.
Basis
|
x1
|
x2
|
s1
|
s2
|
R1
|
R2
|
RK
|
Z
|
4M-3
|
2M-2
|
-M
|
0
|
1
|
0
|
30M
|
R1
|
3
|
1
|
-1
|
0
|
1
|
0
|
20
|
s2
|
.25
|
.5
|
0
|
1
|
0
|
0
|
4
|
R2
|
1
|
1
|
0
|
0
|
0
|
1
|
10
|
Pers. Z yg
mempunyai koef. positip terbesar adalah x1 sebesar 4M-3, sehingga x1 menjadi
entering v., sedangkan yang mempunyai ratio terkecil adalah R1 sebesar 20/3 ,
sehingga R1 menjadi leaving variable
x1
|
x2
|
s1
|
s2
|
R1
|
R2
|
RK
|
|
Z
|
0
|
2/3M-1
|
M/3-1
|
0
|
-4/3M+1
|
0
|
10M/3+20
|
x1
|
1
|
1/3
|
-1/3
|
0
|
1/3
|
0
|
20/3
|
s2
|
0
|
5/12
|
1/12
|
1
|
-1/12
|
0
|
7/3
|
R2
|
0
|
2/3
|
1/3
|
0
|
-1/3
|
1
|
10/3
|
Pers. lain yang
baru = pers. lain yang lama – koef. Entering x pers. poros baru seperti tampak
pada Tabel 2. Selanjutnya x2 menjadi entering var. sedangkan R2 menjadi leaving
var. dan diperoleh Tabel 3 berikut ini.
Tampak pada Tabel 3, koef Z berharga negatip atau nol, sehingga solusi
optimal tercapai dengan Z = 25, x1 = 5, dan x2 = 5.
x1
|
x2
|
s1
|
s2
|
R1
|
R2
|
RK
|
|
Z
|
0
|
0
|
-1/2
|
0
|
-M+1/2
|
-M+3/2
|
25
|
x1
|
1
|
0
|
-1/2
|
0
|
1/2
|
-1/2
|
5
|
s2
|
0
|
0
|
-1/8
|
1
|
1/8
|
-5/8
|
1/4
|
x2
|
0
|
1
|
1/2
|
0
|
-1/2
|
3/2
|
5
|
Contoh Soal 3
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 jambu dalam botol
x2 = besarnya kandungan (ons) jus apel 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 3
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
·
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
Lanjutttt besokk
Ok.. Terima Kasih atas Postingnya !!!.....
BalasHapus