simpleks maksimum

25
Metode Simpleks Maksimum Nur Asyifa (1113017000032) Hanna Ramadhana. W (1113017000040) Ana Matofani (1113017000045) Jafar as-shodiq Al-jufri (1113017000053) Andina Aulia Rachma (1113017000054)

Upload: andina-aulia-rachma

Post on 22-Jul-2015

273 views

Category:

Education


7 download

TRANSCRIPT

Page 1: Simpleks maksimum

Metode SimpleksMaksimum

Nur Asyifa (1113017000032)

Hanna Ramadhana. W (1113017000040)

Ana Matofani (1113017000045)

Jafar as-shodiq Al-jufri (1113017000053)

Andina Aulia Rachma (1113017000054)

Page 2: Simpleks maksimum

Metode simpleks adalah suatu prosedur

aljabar yang bukan secara grafik untuk

mencari nilai optimal dari fungsi tujuan

dalam masalah optimasi yang terkendala

Penentuan solusi optimal dilakukan dengan

memeriksa titik ekstrim satu per satu

dengan cara perhitungan iteratif

Penentuan solusi optimal dengan simpleks

dilakukan tahap demi tahap yang disebut

dengan iterasi

Page 3: Simpleks maksimum

1. Semua kendala berupa persamaan

dengan sisi kanan non negatif

2. Semua variabel non negatif

3. Fungsi tujuan dapat memaksimumkan

atau meminimumkan

Page 4: Simpleks maksimum

Langkah 1 : Membuat permodelan dengan:

a. Menentukan variabel bebas

b. Menentukan batasan-batasan

c. Menentukan fungsi tujuan

Langkah 2 : Menentukan slack atau surplus

Langkah 3 : Membuat tabel iterasi

Langkah 4 : Menentukan pivot kolom dengan mencari nilai fungsi tujuan (Z) terkecil

Langkah 5 : Mencari pivot number dengan cara membagi kolom i

Langkah 6 : Melakukan iterasi pada pivot kolom sehingga nilai pivot kolom menjadi 1

Page 5: Simpleks maksimum

Bayu furniture memproduksi 2 jenis produk yaitu meja

dan kursi yang harus diproses melalui perakitan dan

finishing. Alokasi waktu untuk memproses perakitan

adalah 60 jam kerja dan alokasi waktu proses finishing

adalah 48 jam kerja

Berapakah jumlah meja dan kursi yang

harus diproduksi untuk mendapatkan

keuntungan yang maksimal?

Perakitan Finishing Laba/unit

Meja 4 jam 2 jam Rp. 80.000

Kursi 2 jam 4 jam Rp. 60.000

Page 6: Simpleks maksimum

Variabel bebas :

X1 = banyaknya meja

X2 = banyaknya kursi

Fungsi Tujuan :

Z max = 8X1 + 6X2

Batasan :

4X1 + 2X2 60

2X1 + 4X2 48

X1, X2 ≥ 0

Page 7: Simpleks maksimum

Menambahkan Slack berupa S1, s2 dst. Untuk

menjadikan persamaan bertanda “sama dengan”

4X1 + 2X2 + S1 = 60

2X1 + 4X2 + S2 = 48

-8X1 – 6X2 + Z = 0

Page 8: Simpleks maksimum

Initial Visible Basic Solution

VARIABEL BASIS VARIABEL NON BASIS

SI = 60 X1 = X2 = 0

S2 = 40

Z = 0

Variabel basis dapat dilihat dari tabel yang kolomnya

membentuk matriks identitas.

Page 9: Simpleks maksimum

X1 X2 S1 S2 Z Solusi

4 2 1 0 0 60

2 4 0 1 0 48

-8 -6 0 0 1 0

Langkah 4

X1 X2 S1 S2 Z Solusi

4 2 1 0 0 60

2 4 0 1 0 48

-8 -6 0 0 1 0-8

Variabel

S1

S2

Z

Variabel

S1

S2

Z

Kolom pivot dan sebagai variabel masukPenentu kolom pivot

Page 10: Simpleks maksimum

Langkah 6

X1 X2 S1 S2 Z Solusi

4 2 1 0 0 60

2 4 0 1 0 48

-8 -6 0 0 1 0-8

Variabel

S1

S2

Z

Variabel keluar

Rasio

60:4 = 15

48:2 = 24

-

Pivot number

Page 11: Simpleks maksimum

Langkah 7

X1 X2 S1 S2 Z Solusi

1 1/2 1/4 0 0 15

2 4 0 1 0 48

-8 -6 0 0 1 0-8

baris pivot baru

Variabel

X1

S2

Z

Page 12: Simpleks maksimum

X1 X2 S1 S2 Z Solusi

1 ½ ¼ 0 0 15

0 3 -1/2 1 0 18

0 -2 2 0 1 120

X1 X2 S1 S2 z Solusi

1 0 1/3 -1/6 0 12

0 1 -1/6 1/3 0 6

0 0 5/3 2/3 1 132

Langkah 8

Page 13: Simpleks maksimum

Maka diperoleh x1 = 12 dan x2 = 6

Untuk mendapatkan keuntungan

maksimum, dengan metode simpleks

perusahaan dapat memproduksi meja

sebanyak 12 buah dan kursi sebanyak 6

buah, sehingga mendapat penghasilan

Z maks = 80.000x1 + 60.000x2

= 80.000(12) + 60.000(6)

= 960.000 + 360.000

= 1.320.000

Page 14: Simpleks maksimum

Maks Z = 8X1 + 9X2 + 4X3

Kendala X1 + X2 + 2X3 ≤ 2

2X1 + 3X2 + 4X3 ≤ 3

7X1 + 6X2 + 2X3 ≤ 8

X1, X2, X3 ≥ 0

Page 15: Simpleks maksimum

Ubah ke dalam bentuk persamaan

Z = 8X1 + 9X2 + 4X3

Z – 8X1 – 9X2 – 4X3 = 0

X1 + X2 + 2X3 + S1 = 2

2X1 + 3X2 + 4X3 + S2 = 3

7X1 + 6X2 + 2X3 + S3 = 8

X1, X2, X3 ≥ 0

Page 16: Simpleks maksimum

Menentukan kolom pivot dan baris pivot

Variabel X1 X2 X3 S1 S2 S3 NK Rasio

Z -8 -9 -4 0 0 0 0 -

S1 1 1 2 1 0 0 2 2:1 = 2

S2 2 3 4 0 1 0 3 3:3 = 1

S3 7 6 2 0 0 1 88:6 =

4/3

-9

Kolom pivot dan sebagai variabel masuk Penentu kolom pivot

Page 17: Simpleks maksimum

Menentukan kolom pivot dan baris pivot

Variabel X1 X2 X3 S1 S2 S3 NK Rasio

Z -8 -9 -4 0 0 0 0 -

S1 1 1 2 1 0 0 2 2:1 = 2

S2 2 4 0 1 0 3 3:3 = 1

S3 7 6 2 0 0 1 88:6 =

4/3

3

Pivot number

Baris pivotBaris pivot

Page 18: Simpleks maksimum

Merubah nilai garis pivot

Baris Z -8 -9 -4 0 0 0 0

-9 (2/3 1 4/3 0 1/3 0 1) ___

Baris Baru -2 0 8 0 3 0 9

Variabel X1 X2 X3 S1 S2 S3 NK

Z -8 -9 -4 0 0 0 0

S1 1 1 2 1 0 0 2

X2 2/3 1 4/3 0 1/3 0 1

S3 7 6 2 0 0 1 8

Page 19: Simpleks maksimum

Baris S1 1 1 2 1 0 0 2

1 (2/3 1 4/3 0 1/3 0 1) __

1/3 0 2/3 1 -1/3 0 1

Baris S3 7 6 -2 0 0 1 8

6 (2/3 1 4/3 0 1/3 0 1 __

3 0 -6 0 -2 1 2

Page 20: Simpleks maksimum

Variabel X1 X2 X3 S1 S2 S3 NK

Z -2 0 8 0 3 0 9

S1 1/3 0 2/3 1 -1/3 0 1

x2 2/3 1 4/3 0 1/3 0 1

S3 3 0 -6 0 -2 1 2

VB = S1 = 1 VNB = X1=S2=X3=0

X2 = 1

S3 = 2

Z = 9

Karena nilai bariz Z pada kolom X1 masih terdapat angka negatif,

maka tabel belum optimal

Variabel keluar

Page 21: Simpleks maksimum

VB X1 X2 X3 S1 S2 S3 NK Rasio

Z -2 0 8 0 3 0 9 -

S1 1/3 0 2/3 1 -1/3 0 1 3

X2 2/3 1 4/3 0 1/3 0 1 3/2

X1 3 0 -6 0 -2 1 2 2/3

Baris kolom baru

Page 22: Simpleks maksimum

VB X1 X2 X3 S1 S2 S3 Solusi

Z -2 0 8 0 3 0 9

S1 1/3 0 2/3 1 -1/3 0 1

X2 2/3 1 4/3 0 1/3 0 1

X1 1 0 -2 0 -2/3 1/3 2/3

Variabel keluar

Pada tahap ini kita melihat keoptimalan pada tabel

karena terdapat nilai negatif pada baris Z, maka harus dilakukan

pengulangan langkah 2 pada baris selain X2

Page 23: Simpleks maksimum

Baris z -2 0 8 0 3 0 1

-2 (1 0 -2 0 -2/3 1/3 2/3) __

0 0 4 0 5/3 2/3 31/3

Baris S1 1/3 1 4/3 0 1/3 0 1

1/3 (1 0 -2 0 -2/3 1/3 2/3) __

0 1 8/3 0 7/9 -2/9 5/9

Page 24: Simpleks maksimum

VB X1 X2 X3 S1 S2 S3 NK

Z 0 0 4 0 5/3 2/3 31/3

S1 0 0 4/3 1 -1/9 -1/9 7/9

X2 0 1 8/3 0 7/9 -2/9 5/9

X1 1 0 -2 0 -2/3 1/3 2/3

VB = S1 = 7/9

X2 = 5/9 VNB = X3 = S2 = S3 =0

X1 = 2/3

Z = 31/3

Tabel optimal dengan Z maks = 31/3

Baris kolom baru

Page 25: Simpleks maksimum