METODE SIMPLEKS

Pengertian Metode Simpleks : metode pemecahan persoalan program linear yang begitu kompleks dan luas, dan besar yg dengan metode aljabar (sederhana) dan grafik sulit dan tidak dapat diandalkan.

Ciri khas metode simpleks ialah dengan memasukkan kegiatan disposal (disposal activities). Peranan kegiatan disposal ini adalah untuk menampung sumberdaya yg tersisa atau tidak digunakan. Dengan ada-nya kegiatan disposal ini kita dapat mem-buat ketidaksamaan suatu rumusan mate-tematika menjadi suatu persamaan. Metode simpleks hanya diperkenankan nilai positif dari peubah-peubah Xij.

 Model Umum Metode Simpleks. 1. Kasus Maksimisasi. Fungsi Tujuan : Maksimumkan

Z C1X1-C2X2- . . . . . CnXn-0S1-0S2-. . .-0Sn = NK

Fungsi Pembatas :
a11X11+a12X12+. . . .+a1nXn+ S1+0S2+. . .+0Sn = b1
a21X21+a22X22+. . . .+a2nXn+ 0S1+1S2+. . .+0Sn = b2 . .. . .. .. . ..= am1Xm1+am2Xm2+. . . .+amnXn+ S1+0S2+. . .+1Sn = bm Var. Kegiatan Slack Var

Tabel Simpleks : Var. Dasar Z

X1

X2

....

Xn

S1

S2

....

Sn

NK

-C1 a11 a21 ...

-C2 a12 a22 ...

....

-Cn a1n a2n ...

S1 S2 ...

...

b1 b2 ...

...

...

...

...

...

...

...

Sn

am1

am2

...

amn

bm

2. Kasus Minimisasi Fungsi Tujuan : Minimumkan

Z C1X1-C2X2- . . . . . CnXn-0S1-0S2-. . .-0Sn = NK

Fungsi Pembatas :
a11X11+a12X12+. . . .+a1nXn - S1 -0S2-. . . - 0Sn = b1 a21X21+a22X22+. . . .+a2nXn - 0S1-1S2 -. . . - 0Sn = b2 . .. . .. .. . ..= am1Xm1+am2Xm2+. . . .+amnXn- S1- 0S2 -. . . -1Sn = bm

[Link]

Surplus var.

Tabel Simpleks :

Var. Dasa r
Z S1 S2 ... Sn

X1

X2

....

Xn

S1

S2

....

Sn

NK

1 0 0 ... 0

-C1 a11 a21 ... am1

-C2 a12 a22 ... am2

.... ... ... ... ...

-Cn a1n a2n ... amn

0 -1 0 ... 0

0 0 -1 ... 0

0 0 0 ... 0

0 0 0 ... -1

0 b1 b2 ... bm

3. Kasus-kasus khusus Perubahan tanda ketidaksamaan men-jadi persamaan pada fungsi pembatas menyesuaikan dengan tanda ketidaksamaan masing-masing persamaan linearnya.

 Langkah-langkah Metode Simpleks 1. Rumuskan persoalan PL ke dalam model umum PL (fungsi tujuan dan fungsi pembatas). 2. Merubah model umum PL menjadi model simpleks : a. Fungsi Pembatas : tambahkan slack variabel dan/atau surplus variabel, dan/atau variabel buatan (artifisial var).

b. Fungsi tujuan : - Rubahlah bentuk fungsi tujuan implisit menjadi persamaan bentuk eksplisit. - Tambahkan/kurangi dengan slack var, surplus var dan/atau variabel buatan yg bernilai nol. 3. Formulasikan ke dalam Tabel Simpleks. 4. Lakukan langkah-langkah penyelesaian.

 Kasus Maksimisasi : Model Program Linear 1. Fungsi Tujuan : Maksimumkan : Z=30X + 20Y (Dlm Rp10.000) 2. Fungsi Pembatas : 2.1. Bahan A : 2X + Y 40 2.2. Bahan B : X + Y 25 X, Y 0

Model Simpleks : 1. Fungsi Tujuan : Maksimumkan Z= 30X + 20 Y+0S1 +0S2 = 0 2. Fungsi Pembatas : Bahan A : 2X + Y + 1S1 +0S2 = 40 Bahan B : X + Y + 0S1 +1S2 = 25 X, Y, S1, S2 0

Tabel Simpleks
Z= 30X + 20 Y+0S1 +0S2 = 0 Fungsi Pembatas : 2X + Y + 1S1 +0S2 = 40 X + Y + 0S1 +1S2 = 25 X, Y, S1, S2 0
Ci bi 30 X 2 1 20 Y 1 1 0 S1 1 0 0 S2 0 1 indeks

Var

0 0 Z-C

S1 S2

40 25

Tabel Simpleks Cari nilai Z-C

C Var Ci bi

30
X 2 1 -30

20
Y 1 1 -20

0
S1 1 0 0

0
S2 0 1 0 indeks

0 0 Z-C

S1 S2

40 25 Z=0

Cari kolom nilai negatif paling besar

C Var Ci bi 30 X 2 1 -30 20 Y 1 1 -20 0 S1 1 0 0 0 S2 0 1 0 indeks

0 0 Z-C

S1 S2

40 25 Z=0

Tabel Simpleks cari nilai indeks bi : kolom kunci

C Var Ci bi

30
X 2 1 -30

20
Y 1 1 -20

0
S1 1 0 0

0
S2 0 1 0 indeks

0 0 Z-C

S1 S2

40 25 Z=0

40/2=20 25/1=25

Cari baris nilai terkecil (positif) / terbesar (negatif) dari indeks

C Var Ci bi 30 X 2 1 -30 20 Y 1 1 -20 0 S1 1 0 0 0 S2 0 1 0 indeks

0 0 Z-C

S1 S2

40 25 Z=0

40/2=20 25/1=25

Tabel Simpleks
30 X 2 1 -30 20 Y 1 1 -20 0 S1 1 0 0 0 S2 0 1 0

Var

Ci bi

indeks

0 0 Z-C

S1 S2

40 25 Z=0

40/2=20 25/1=25

Cari nilai angka baris kunci yang baru (yg dirubah yg kunci): S1: 40:2=20, 2:2=1, 1:2=, 1:2=, 0:2=0 20,1, , , 0 S2: 25 , 1, 1, 0, 1 25,1,1,0, 1

Angka baris kedua yangbaru:

Nilai baru S2 = 25,1, 1, 0, 1 20,1, , , 0 (1) 5, 0, ,- , 1

Tabel Simpleks
C Var Ci bi 30 X 20 Y 0 S1 0 S2 indeks

0
0 Z-C

S1
S2

40
25 Z=0

2
1 -30

1
1 -20

1
0 0

0
1 0

40/2=20
25/1=25

Cari nilai angka baris yang baru: Z- C Z-C ` = 0, -30, -20, 0, 0 Nilai baris baru S1 = 20, 1 , , , 0 (-30) -

600, 0, -5, 15, 0

Tabel Simpleks Nilai baru Z-C = 600, 0, -5, 15, 0

Nilai baru S2 = 5, 0, ,- , 1 Nilai baru S1 (kunci) = 20,1, , , 0

Ci bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

Var

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

Tabel Simpleks Nilai baru Z-C = 600, 0, -5, 15, 0

Nilai baru S2 = 5, 0, ,- , 1 Nilai baru S1 (kunci) = 20,1, , , 0

Ci bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

Var

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

Tabel Simpleks Nilai baru Z-C = 600, 0, -5, 15, 0

Nilai baru S2 = 5, 0, ,- , 1 Nilai baru S1 (kunci) = 20,1, , , 0

Ci bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

Var

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

20/0,5=40 5/0,5=10

Tabel Simpleks Nilai baru Z-C = 600, 0, -5, 15, 0

Nilai baru S2 = 5, 0, ,- , 1 Nilai baru S1 (kunci) = 20,1, , , 0

Ci bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

Var

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

20/0,5=40 5/0,5=10

Tabel Simpleks
C Var Ci Bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

20/0,5=40 5/0,5=10

Cari nilai angka baris kunci yang baru: S1: 20 , 1 , 0,5 , 0,5 , 0 S2: 5:0,5=10, 0:0,5=0, 0,5:0,5=1, -0,5:0,5=-1, 1:0,5=2 10,0, 1, -1, 2(baris kunci)

Angka baris kedua yangbaru:

Nilai baru S1 = 20, 1, 0,5, 0,5, 0 10, 0, 1, -1, 2 (0,5) 15, 1, 0 , 1 , -1

Tabel Simpleks
C Var Ci bi 20 5 600 30 X 1 0 0 20 Y 0,5 0,5 -5 0 S1 0 S2 indeks

0 0 Z-C

S1 S2

0,5 -0,5 15

0 1 0

20/0,5=40 5/0,5=10

Cari nilai angka baris kunci yang baru: S1: 20 , 1 , 0,5 , 0,5 , 0 S2: 5:0,5=10, 0:0,5=0, 0,5:0,5=1, -0,5:0,5=-1, 1:0,5=2 10,0, 1, 1, 2(baris kunci)

Cari nilai angka baris yang baru: Z- C Z-C ` = 600, 0, -5, 15, 0 Nilai baris baru S2 = 10, 0, 1 , -1 , 2 (-5) -

Z-C

= 650,

0,

0, 10, 10

Tabel Simpleks

Z-C

= 650,

Nilai baru S1 = 15, Nilai baris baru S2 = 10,

0, 0, 10, 10 1, 0 , 1 , -1 0, 1 , -1 , 2

C 30 20 Z-C

Var

Ci bi 15 10 650

30 X 1 0 0

20 Y 0 1 0

0 S1

0 S2

X Y

1 -1 10

-1 2 10

x=15 y=10 maka Zmaks=650 atau (30x15)+(20x10)

Small Test
Seorang manajer di perusahaan penghasil keramik hias yang mempekerjakan pengrajin untuk memproduksi piring dan gelas hias. Sumberdaya utama peusahaan adalah tanah liat dan tenaga kerja. Dengan sumberdaya terbatas sang manajer ingin tahu berapa banyak sebaiknya produksi pirng dan gelas per hari untuk memaksimalkan keuntungan/laba. Data yang berhasil dihimpun:

Produk Piring Gelas

Jam kerja per unit produk 1 2

Ons tanah liat per unit produk 4 3

Laba per unit produk 80 100

Persediaan per hari

40

120

Berapa banyak piring dan gelas hias yang harus diroduksi tiap hari? Disimbolkan: x1 = jumlah piring/hari; Y = jumlah gelas/hari, selesaikan dengan metode simpleks.