metode aljabar

PERTEMUAN 6-7PERTEMUAN 6-7

METODE ALJABARMETODE ALJABAR

OLEHOLEH

Ir. Indrawani Sinoem, MS.Ir. Indrawani Sinoem, MS.

► PengertianPengertian

1. Pemecahan persoalan PL dengan 1. Pemecahan persoalan PL dengan

metode aljabar : pemecahan per-metode aljabar : pemecahan per-

soalan dengan cara substitusi soalan dengan cara substitusi antarantar

persamaan linear pada fungsi persamaan linear pada fungsi pem-pem-

batas dan fungsi tujuan. batas dan fungsi tujuan.

Prinsip yang digunakan ialah Prinsip yang digunakan ialah men-cari seluruh kemungkinan men-cari seluruh kemungkinan pemecah-an dasar pemecah-an dasar feasible feasible (layak), kemudian pilih salah (layak), kemudian pilih salah satu yang memberikan nilai satu yang memberikan nilai objektif optimal, yaitu paling objektif optimal, yaitu paling besar (maksimum) atau paling besar (maksimum) atau paling kecil (minimum).kecil (minimum).

Pemecahan persoalan Program Pemecahan persoalan Program Linear dengan metode aljabar ini Linear dengan metode aljabar ini dibagi 3 (tiga) kasus, yaitu :dibagi 3 (tiga) kasus, yaitu :

(1). Kasus Maksimisasi.(1). Kasus Maksimisasi.

(2). Kasus Minimisasi.(2). Kasus Minimisasi.

(3). Kasus-kasus Khusus. (3). Kasus-kasus Khusus.

(1). Kasus Maksimisasi(1). Kasus Maksimisasi : kasus : kasus pemecahpemecah

an persoalan PL yang bertujuan an persoalan PL yang bertujuan

mencari seluruh kemungkinan mencari seluruh kemungkinan pe-pe-

mecahan yg memberikan nilai mecahan yg memberikan nilai

objektif maksimum.objektif maksimum.

Contoh-1 :Contoh-1 :

1. Fungsi Tujuan :1. Fungsi Tujuan :

Maksimumkan Z = 8 XMaksimumkan Z = 8 X11 + 6 X + 6 X22

(Dlm Rp 1.000).(Dlm Rp 1.000).

2. Fungsi Pembatas : 2. Fungsi Pembatas :

2.1. P-Bahan : 4 X2.1. P-Bahan : 4 X11 + 2 X + 2 X11 ≤ 60 ≤ 60

2.2. Penjahitan : 2 X2.2. Penjahitan : 2 X11 + 4 X + 4 X22 ≤ 48 ≤ 48

XX11, X, X22 ≥ 0 ≥ 0

► Langkah-langkah penyelesaian : Langkah-langkah penyelesaian :

1. Merubah ketidaksamaan fungsi 1. Merubah ketidaksamaan fungsi pembatas menjadi kesamaan dengan pembatas menjadi kesamaan dengan menambah slack variabel :menambah slack variabel :

4X4X11 + 2X + 2X22 + S + S11 = 60 = 60

2X2X11 + 4X + 4X22 + S + S22 = 48 = 482. Merubah fungsi tujuan dengan 2. Merubah fungsi tujuan dengan

menambah slack variabel bernilai nol :menambah slack variabel bernilai nol :

Z = 8000 XZ = 8000 X11 + 6000 X + 6000 X22 + 0 S + 0 S11 + 0 S + 0 S22

3. Substitusikan fungsi pembatas dan fungsi 3. Substitusikan fungsi pembatas dan fungsi tujuan :tujuan :

a. Xa. X11= X= X22= 0; S= 0; S11= 60; S= 60; S22 = 48 = 48

Z = 8000(0)+6000(0)+0(60)+0(48) = 0Z = 8000(0)+6000(0)+0(60)+0(48) = 0

b. Xb. X11=S=S11=0=0

4X4X11+2X+2X22+S+S11 = 60 X = 60 X22 = 60/2 =30 = 60/2 =30

2X2X11+4X+4X22+S+S22 = 48 4(30)+S = 48 4(30)+S22 = 48 = 48

SS22 =-72 =-72

(tdk fisibel)(tdk fisibel)

(c). X(c). X11= S= S22 = 0 = 0

2X2X11+4X+4X22+S+S22 = 48 4X = 48 4X22 = 48 = 48

XX22 = 48/4 = 48/4

XX22 = 12 = 12

4X4X11+2X+2X22+S+S11 = 60 2(12)+S = 60 2(12)+S11=60=60

SS11 = 60-24 = 60-24

= 36= 36

Z = Z = 8000(0)+6000(12)+0+0=720008000(0)+6000(12)+0+0=72000

(d). X(d). X22=S=S11=0=0

4X4X11+2X+2X22+S+S11=60 4X=60 4X11= 60 X= 60 X11=15=15

2X2X11+4X+4X22+S+S22=48 2(15) + S=48 2(15) + S22 = 48 = 48

SS22 = 48-30=18 = 48-30=18

Z = 8000(15)+6000(0)+0+0= Z = 8000(15)+6000(0)+0+0= 120.000120.000

(e). X(e). X22=S=S22=0=0

2X2X11+4X+4X22+S+S22 =48 2X =48 2X11=48 X=48 X11=24=24

4X4X11+2X+2X22+S+S11 =60 S =60 S11=60-4(24)=-36=60-4(24)=-36

(Tdk fisibel)(Tdk fisibel)

(f). S(f). S11=S=S22=0=0

4X4X11+2X+2X22 = 60 2X = 60 2X22=60-4X=60-4X11

XX22=30-2X=30-2X11

2X2X11+4X+4X22 = 48 2X = 48 2X11+4(30-2X+4(30-2X11)=48)=48

2X2X11+120-8X+120-8X11 = 48 = 48

6X6X11 = 120-48 = 120-48

XX11 = 12 = 12

XX2 2 =30-24= 6=30-24= 6

Z =8000(12)+6000(6)=132.000Z =8000(12)+6000(6)=132.000

Kesimpulan : Kesimpulan :

Perusahaan konveksi “Maju” harus Perusahaan konveksi “Maju” harus mempro-duksi Celana (Xmempro-duksi Celana (X11) = 12 dan ) = 12 dan Baju (XBaju (X22) = 6) = 6

untuk memperoleh laba maksimum untuk memperoleh laba maksimum sebesarsebesar

Rp 132.000.-Rp 132.000.-

►Contoh-2Contoh-2

Suatu perusahaan mengahsilkan 2 Suatu perusahaan mengahsilkan 2 barang, yaitu A dan B. Masing-masing barang, yaitu A dan B. Masing-masing barang membutuhkan sumberdaya barang membutuhkan sumberdaya seperti terlihat pada Tabel berikut.seperti terlihat pada Tabel berikut.

SumberdayaSumberdaya Barang ABarang A Barang BBarang B Kapasitas Kapasitas SumberdayaSumberdaya

Bahan Bahan MentahMentah 11 22 1010

BuruhBuruh 66 66 3636

Laba/unitLaba/unit 4.0004.000 5.0005.000 MaksimumkaMaksimumkann

Peubah Peubah KegiatanKegiatan

XX11 XX22 ZZ

Disamping itu, menurut ramalan Disamping itu, menurut ramalan bagian penjualan permintaan barang A bagian penjualan permintaan barang A tidak akan melebih 4 unit. Tentukan tidak akan melebih 4 unit. Tentukan jumlah barang A dan B yang dihasilkan jumlah barang A dan B yang dihasilkan sehingga memberikan laba maksimum sehingga memberikan laba maksimum bagi perusahaan !bagi perusahaan !

Penyelesaian :Penyelesaian :

Model Program Linear Model Program Linear

1. Fungsi Tujuan :1. Fungsi Tujuan :

Maksimumkan : Z = 4000XMaksimumkan : Z = 4000X11+5000X+5000X22

2. Fungsi Pembatas :2. Fungsi Pembatas :

2.1. Bahan Mentah : X2.1. Bahan Mentah : X11+2X+2X22 ≤ 10 ≤ 10

2.2. Buruh2.2. Buruh : 6X: 6X11+6X+6X22 ≤ 36 ≤ 36

2.3. Permintan A : X2.3. Permintan A : X11 ≤ 4 ≤ 4

XX11, X, X22 ≥ 0 ≥ 0

Metode AljabarMetode Aljabar

1. Merubah ketidaksamaan fungsi pemba-1. Merubah ketidaksamaan fungsi pemba-

tas menjadi persamaan dgn menambahtas menjadi persamaan dgn menambah

slack variabel (S).slack variabel (S).

XX1 1 + 2X+ 2X22 + S + S11 = 10 = 10

6X6X11 + 6X + 6X22 + S + S22 = 36 = 36

XX11 + S + S33 = 4 = 4

2. Merubah fungsi tujuan dgn menambah 2. Merubah fungsi tujuan dgn menambah

slack variabel bernilai nol.slack variabel bernilai nol.

Z = 4000XZ = 4000X11+5000X+5000X22+0S+0S11+0S+0S22+0S+0S33

3. Substitusikan fungsi pembatas dan 3. Substitusikan fungsi pembatas dan

fungsi tujuan.fungsi tujuan.

(a). X(a). X11=X=X22=0; S=0; S11=10; S=10; S22=36; S=36; S33=4=4

Z =4000(0)+5000(0)+0(10)+0(36)+Z =4000(0)+5000(0)+0(10)+0(36)+

0(4) = 00(4) = 0

(b). X(b). X11=S=S11=0=0

XX11+2X+2X22+S+S11=10 2X=10 2X22 =10 X =10 X22=5=5

6X6X11+6X+6X22+S+S22=36 S=36 S22 =36-30=6 =36-30=6

4X4X11+S+S33= 4 S= 4 S33=4=4

Z = 4000(0)+5000(5)+0+0=25.000.Z = 4000(0)+5000(5)+0+0=25.000.

(c). X(c). X11=S=S22=0=0

6X6X11+6X+6X22+S+S22=36 6X=36 6X22=36=36

XX22=6=6

XX11+2X+2X22+S+S11=10 S=10 S11=10-12=-2=10-12=-2

(Tidak Fisibel)(Tidak Fisibel)

(d). X(d). X11=S=S33=0=0

XX11+S+S33=4 =4 (Tidak Fisibel)(Tidak Fisibel)

(e). X(e). X22=S=S11=0=0

XX11+2X+2X22+S+S11=10 X=10 X11=10=10

6X6X11+6X+6X22+S+S22=36 S=36 S22=36-60=-24=36-60=-24 (Tidak Fisibel)(Tidak Fisibel)

(f). X(f). X22=S=S22=0=0

6X6X11+6X+6X22+S+S22=36 X=36 X11=6=6

XX11+2X+2X22+S+S11=10 S=10 S11=10-6=4=10-6=4

XX11+S+S33 = 4 S = 4 S33= -4-6=-2= -4-6=-2 (Tidak Fisibel)(Tidak Fisibel)

(g). X(g). X22=S=S33=0=0 XX11+S+S33=4 X=4 X11= 4= 4

XX11+2X+2X22+S+S11=10 S=10 S11=10-4=6=10-4=6 6X6X11+6X+6X22+S+S22=36 S=36 S22=36-24=12=36-24=12 Z =4000(4)+5000(0)+0+0=16.000.Z =4000(4)+5000(0)+0+0=16.000.

(h). S(h). S11=S=S22=0=0 XX11+2X+2X22+S+S11=10 X=10 X11=10-2X=10-2X22

6X6X11+6X+6X22+S+S22=36 6(10-=36 6(10-2X2X22)+6X)+6X22=36=36

XX22=4;X=4;X11=10-8=2=10-8=2

Z = Z = 4000(2)+5000(4)+0+0=28.0004000(2)+5000(4)+0+0=28.000

(h). S(h). S11=S=S33=0=0

XX11+S+S33=4=4 X X11=4 =4

XX11+2X+2X22+S+S11=10 =10 XX22=(10-4)/2=3=(10-4)/2=3

6X6X11+6X+6X22+S+S22=36 S=36 S22=-6=-6

(Tidak Fisibel)(Tidak Fisibel)

(i). S(i). S22=S=S33=0=0

XX11+S+S33=4 X=4 X11=4=4

6X6X11+6X+6X22+S+S22=36 X=36 X22=2=2

XX11+2X+2X22+S+S11=10 S=10 S11=2=2Z Z

=4000(4)+5000(2)+0+0=26.000.=4000(4)+5000(2)+0+0=26.000.Kesimpulan:Kesimpulan:Barang A=2 unit, barang B=4 unit Barang A=2 unit, barang B=4 unit akan menghasilkan laba maks = akan menghasilkan laba maks = Rp28.000.-Rp28.000.-

(2) Kasus Minimisasi : (2) Kasus Minimisasi : kasus pemecahan kasus pemecahan masalah program linear yang bertujuan masalah program linear yang bertujuan seluruh kemungkinan pemecahan yang seluruh kemungkinan pemecahan yang memberikan nilai objektif minimum.memberikan nilai objektif minimum.

Contoh :Contoh :

Seorang petani modern menghadapi Seorang petani modern menghadapi suatu persoalan sebagai berikut : suatu persoalan sebagai berikut : setiap sapi peliharaan agar supaya setiap sapi peliharaan agar supaya sehat harus diberi makanan yang sehat harus diberi makanan yang mengandung paling sedikit : 27,21, mengandung paling sedikit : 27,21, dan 30 satuan unsur dan 30 satuan unsur

nutrisi jenis A, B, dan C setiap nutrisi jenis A, B, dan C setiap harinya. Dua jenis makanan Mharinya. Dua jenis makanan M11 dan M dan M22 diberikan kepada sapi peliharaan diberikan kepada sapi peliharaan tersebut. Satu gram makanan jenis Mtersebut. Satu gram makanan jenis M11 mengandung unsur nutrisi jenis A, B, mengandung unsur nutrisi jenis A, B, dan C masing-masing sebesar 3,1, dan 1 dan C masing-masing sebesar 3,1, dan 1 satuan. Sedangkan satu gram makanan satuan. Sedangkan satu gram makanan jenis Mjenis M22 mengandung unsur nutrisi jenis mengandung unsur nutrisi jenis A,B, dan C masing-masing 1,1, dan 2 A,B, dan C masing-masing 1,1, dan 2 satuan. Harga satu gram Msatuan. Harga satu gram M11 dan M dan M22 masing-masing sebesar Rp40000 dan masing-masing sebesar Rp40000 dan Rp20000.-Rp20000.-

Petani tersebut harus memutuskan Petani tersebut harus memutuskan apakah membeli satu jenis makanan saja apakah membeli satu jenis makanan saja atau kedua-duanya kemudian atau kedua-duanya kemudian mencampurnya. Tujuan adalah agar mencampurnya. Tujuan adalah agar jumlah pengeluaran petani tersebut jumlah pengeluaran petani tersebut minimum.minimum.

a. Merumuskan Tabel Persoalana. Merumuskan Tabel PersoalanNutrisiNutrisi

Kandungan NutrisiKandungan Nutrisi

Makanan MMakanan M11 Makanan Makanan MM22

Jumlah Jumlah KandunganKandungan

Jenis AJenis A 3 13 1 2727

Jenis BJenis B 1 11 1 2121

Jenis CJenis C 1 11 1 3030

Harga/gramHarga/gram 40.000 20.00040.000 20.000 MinimumkaMinimumkann

PeubahPeubah XX11 X X22 ZZ

b. Model Program Linearb. Model Program Linear

1. Fungsi Tujuan :1. Fungsi Tujuan :

Minimumkan : Z = Minimumkan : Z = 40000X40000X11+20000X+20000X22

2. Fungsi Pembatas :2. Fungsi Pembatas :

2.1. Nutrisi A : 3X2.1. Nutrisi A : 3X11+ X+ X22 ≥ 27 ≥ 27

2.2. Nutrisi B : X2.2. Nutrisi B : X11+ X+ X2 2 ≥ 21≥ 21

2.3. Nutrisi C : X2.3. Nutrisi C : X11+2X+2X22 ≥ 30 ≥ 30

XX11, X, X22 ≥ 0 ≥ 0

c. Penyelesaianc. Penyelesaian

(1). Metode Aljabar :(1). Metode Aljabar :

((a). Merubah ketidaksamaan fungsi a). Merubah ketidaksamaan fungsi pem-pem-

batas menjadi kesamaan dengan me batas menjadi kesamaan dengan me

ngurangi dengan ngurangi dengan surplussurplus variabel variabel

(S).(S).

3X3X11+ X+ X22-S-S1 1 = 27= 27

XX11+ X+ X22-S-S22 = 21 = 21

XX11+2X+2X22-S-S3 3 = 30= 30

(b). Merubah fungsi tujuan dengan me-(b). Merubah fungsi tujuan dengan me-

nambah nambah surplussurplus variabel bernilai nol. variabel bernilai nol.

Z = 40000XZ = 40000X11+20000X+20000X22+0S+0S11+0S+0S22+0S+0S33

(c). Substitusikan fungsi pembatas dan(c). Substitusikan fungsi pembatas dan

fungsi tujuan.fungsi tujuan.

1. X1. X11=X=X22=0; S=0; S11=27;S=27;S22=21;S=21;S33=30=30

Z = 0.Z = 0.

2. X2. X11=S=S11=0=0

3X3X11+X+X22-S-S11=27; X=27; X22=27=27

XX1 1 + X+ X22 – S – S22 = 21; S = 21; S22 = 6 = 6

XX11 +2X +2X22- S- S33 = 30; S = 30; S33 = 24 = 24

Z = 40000(0)+20000(27)+0+0+0Z = 40000(0)+20000(27)+0+0+0

= 540.000= 540.000

(3). X(3). X11=S=S22= 0= 0

XX1 1 + X+ X22 – S – S22 = 21; X = 21; X22=21=21

3X3X11+X+X22-S-S11=27; S=27; S11=-12=-12

(Tidak Fisibel)(Tidak Fisibel)

(4). X(4). X11=S=S33=0=0

XX11 +2X +2X22- S- S33 = 30; X = 30; X22=30/2 = 15=30/2 = 15

XX1 1 + X+ X22 – S – S22 = 21; S = 21; S22=-7=-7

(Tidak Fisibel)(Tidak Fisibel)

(5). X(5). X22=S=S11=0=0

3X3X11+X+X22-S-S11=27; X=27; X11 = 27/3 = 9 = 27/3 = 9

XX11+X+X22–S–S22=21; S=21; S22=-12=-12

(Tidak Fisibel)(Tidak Fisibel)

(6). X(6). X22=S=S22=0=0

XX11+X+X22–S–S22=21; X=21; X11=21=21

XX11+2X+2X22- S- S33=30; S=30; S33=-9 =-9 (Tidak (Tidak Fisibel)Fisibel)

(7). X(7). X22=S=S33=0=0

XX11+2X+2X22- S- S33=30; X=30; X11=30=30

3X3X11+X+X22-S-S11=27; S=27; S11=90-27=63=90-27=63

XX11+X+X22–S–S22=21; S=21; S22=9=9

Z =40000(30)+20000(0)+0+0+0Z =40000(30)+20000(0)+0+0+0

= 1.200.000.-= 1.200.000.-

(8). S(8). S11=S=S22=0=0

3X3X11+X+X22-S-S11=27; X=27; X22=27-3X=27-3X11

XX11+X+X22–S–S22=21; X=21; X11+27-3X+27-3X11=21=21

XX11=6/2=3=6/2=3

XX22= 27-3(3)=18= 27-3(3)=18

XX11+2X+2X22- S- S33=30; 3+2(18)-=30; 3+2(18)- SS3 3 =30=30

SS33=39-30=9=39-30=9 Z =40000(3)+2000(18)+0+0+0Z =40000(3)+2000(18)+0+0+0 =480.000.-=480.000.-

(9). S(9). S11=S=S33=0=0

3X3X11+X+X22-S-S11=27; X=27; X22=27-3X=27-3X11

XX11+2X+2X22- S- S33=30; X=30; X11+2(27-3X+2(27-3X11)=30)=30

XX11=(54-30)/5=4,8=(54-30)/5=4,8

XX22=27-=27-3(4,8)=12,63(4,8)=12,6

XX11+X+X22–S–S22=21; S=21; S22 =-3,6 =-3,6

(Tidak Fisibel)(Tidak Fisibel)

(10). S(10). S22=S=S33=0=0

XX11+X+X22–S–S22=21; X=21; X22=21-X=21-X11

XX11+2X+2X22- S- S33=30; X=30; X11+2(21-X+2(21-X11)=30)=30

XX11 = 42-30=12 = 42-30=12

XX22 = 21-12=9 = 21-12=9

3X3X11+X+X22-S-S11=27; S=27; S11 = 18 = 18

Z =40000(12)+2000(9)+0+0+0Z =40000(12)+2000(9)+0+0+0

= 660.000.-= 660.000.-

Jadi : Pengeluaran petani yang Jadi : Pengeluaran petani yang minimum minimum

jika membeli makanan sapi A jika membeli makanan sapi A = 3= 3

satuan dan makanan sampi B satuan dan makanan sampi B = 12= 12

satuan dengan Zsatuan dengan Zminmin=Rp =Rp 480.000.-480.000.-

Jadi : Pengeluaran petani yang Jadi : Pengeluaran petani yang minimum minimum

jika membeli makanan sapi A jika membeli makanan sapi A = 3= 3

satuan dan makanan sampi B satuan dan makanan sampi B = 12= 12

satuan dengan Zsatuan dengan Zminmin=Rp =Rp 480.000.-480.000.-

(3). Kasus-kasus khusus(3). Kasus-kasus khusus

Beberapa kasus khusus selain Beberapa kasus khusus selain kasus maksimisasi dan minimisasi kasus maksimisasi dan minimisasi adalah kasus solusi optimum adalah kasus solusi optimum ganda dan tidak memiliki solusi ganda dan tidak memiliki solusi yang layak.yang layak.

Contoh :Contoh :

a. Solusi Optimum Gandaa. Solusi Optimum Ganda

1. Fungsi Tujuan :1. Fungsi Tujuan :

Maksimumkan Z = 4XMaksimumkan Z = 4X11 + 4X + 4X22

2. Fungsi Pembatas :2. Fungsi Pembatas :

XX11 + 2X + 2X22 ≤ 10 ≤ 10

XX11 + 6X + 6X22 ≤ 36 ≤ 36

XX11 ≤ 4 ≤ 4

XX11, X, X22 ≥ 0 ≥ 0

b. Tidak Memiliki Solusi Layakb. Tidak Memiliki Solusi Layak

1. Fungsi Tujuan :1. Fungsi Tujuan :

Maksimumkan Z = 5XMaksimumkan Z = 5X11 + 3X + 3X22

2. Fungsi Pembatas :2. Fungsi Pembatas :

4X4X11 + 2X + 2X22 ≤ 8 ≤ 8

XX11 ≥ 3 ≥ 3

XX22 ≥ 7 ≥ 7

XX11, X, X22 ≥ 0 ≥ 0