simpleks maksimum
TRANSCRIPT
Metode SimpleksMaksimum
Nur Asyifa (1113017000032)
Hanna Ramadhana. W (1113017000040)
Ana Matofani (1113017000045)
Jafar as-shodiq Al-jufri (1113017000053)
Andina Aulia Rachma (1113017000054)
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
1. Semua kendala berupa persamaan
dengan sisi kanan non negatif
2. Semua variabel non negatif
3. Fungsi tujuan dapat memaksimumkan
atau meminimumkan
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
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
Variabel bebas :
X1 = banyaknya meja
X2 = banyaknya kursi
Fungsi Tujuan :
Z max = 8X1 + 6X2
Batasan :
4X1 + 2X2 60
2X1 + 4X2 48
X1, X2 ≥ 0
Menambahkan Slack berupa S1, s2 dst. Untuk
menjadikan persamaan bertanda “sama dengan”
4X1 + 2X2 + S1 = 60
2X1 + 4X2 + S2 = 48
-8X1 – 6X2 + Z = 0
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.
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
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
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
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
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
Maks Z = 8X1 + 9X2 + 4X3
Kendala X1 + X2 + 2X3 ≤ 2
2X1 + 3X2 + 4X3 ≤ 3
7X1 + 6X2 + 2X3 ≤ 8
X1, X2, X3 ≥ 0
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
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
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
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
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
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
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
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
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
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