IKG3M3 / Optimasi dan Kontrol
Dede Tarwidi
KK Pemodelan dan Simulasi
METODE SIMPLEKS
Metode Simpleks
Merupakan prosedur aljabar yang bersifat iteratif,
yang bergerak selangkah demi selangkah, dimulai
dari suatu titik ekstrim pada daerah feasible
menuju ke titik ekstrim optimum.
1/22/2015
Metode Simpleks (Memaksimumkan)
Bentuk standar pemrograman linear:
maks z = c1x1 + c2x2 + + cnxn
terhadap kendala
dengan xi 0 dan bi 0, i=1,2,,n.
3
1/22/2015
IKG3M3 OPTIMASI DAN KONTROL
Beberapa ketentuan dalam metode
Simpleks
Nilai kanan fungsi tujuan harus nol
Nilai kanan fungsi kendala harus positif. Apabila
negatif, kalikan dengan -1.
Fungsi kendala dengan tanda diubah ke
bentuk = dengan menambahkan variabel
slack/surplus. Penambahan variabel ini
menyatakan kapasitas yang tidak digunakan atau
tersisa pada sumber daya tersebut.
1/22/2015
Metode Simpleks
Setelah ditambahkan variabel slack maka
persamaan kendala menjadi
dengan si 0, i=1,2,,n.
5
1/22/2015
IKG3M3 OPTIMASI DAN KONTROL
Metode Simpleks
Basic solution dari pemrograman linear adalah
solusi berbentuk (x1,x2,,xn,s1,s2,,sm) dimana
terdapat paling banyak m variabel tidak nol.
Basic variable adalah variabel tidak nol dari basic
solution.
Basic feasible solution adalah basic solution
dengan semua variabel tidak negatif.
1/22/2015
Tabel Simpleks
Tabel yang terdiri dari matriks yang diperluas dari
persamaan kendala dengan fungsi tujuan
berbentuk
1/22/2015
Kode dan nama MK
Bentuk Tabel Simpleks
1/22/2015
Contoh 1 (Maks)
maks
z = 4x1 + 6x2
terhadap kendala
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Tabel Simpleks untuk masalah tesebut adalah
Basic variable: s1, s2, dan s3
Nonbasic variable: x1, dan x2
10
1/22/2015
Kode dan nama MK
Contoh (Jawab)
Sehingga diperoleh solusi untuk saat ini adalah
x1 = 0, x2 = 0, s1 = 11, s2 = 27, s3 = 90.
Jadi, basic feasible solution ditulis
(x1,x2,s1,s2,s3) = (0,0,11,27,90)
11
1/22/2015
Kode dan nama MK
Catatan Metode Simpleks
Jika baris terakhir dari tabel Simpleks masih
mengandung entri negatif maka solusi belum
optimal.
Solusi optimal diperoleh jika semua entri dalam
baris terakhir sudah positif semua.
12
1/22/2015
Kode dan nama MK
Pivoting
Entering variable adalah entri terkecil (paling
negatif) dalam baris terakhir dari tabel Simpleks.
Departing variable adalah rasio tak-negatif terkecil
dari bi/aij dalam kolom yang ditentukan entering
variable.
Tentukan nilai pivot yaitu entri dari perpotongan
kolom entering variable dan baris departing
variable.
Lakukan eliminasi Gauss-Jordan pada kolom yang
mengandung pivot.
13
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Entering dan departing variable dari contoh 1
adalah
14
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
X2 adalah entering variable karena -6 adalah entri
terkecil dari baris terakhir.
Mencari departing variable:
11/1 = 11,
27/1 = 27,
90/5 = 18,
rasio tak-negatif terkecil adalah 11, maka
departing variable adalah s1.
Pivot adalah entri dari baris pertama kolom
kedua.
15
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Selanjutnya lakukan eliminasi Gauss-Jordan:
16
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Setelah pivoting tabel Simpleks menjadi
(x1,x2,s1,s2,s3) = (0,11,0,16,35) dengan nilai z =
4(0) + 6(11) = 66 (belum optimal)
17
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Selanjutnya tentukan entering dan departing
variable yang baru, yaitu entering variable x1 dan
departing variable s3. Kemudian lakukan Eliminasi
Gauss-Jordan lagi.
18
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Tabel Simpleks yang baru adalah
Lakukan eliminasi Gauss-Jordan sekali lagi maka
diperoleh Simpleks tabel sebagai berikut.
19
1/22/2015
Kode dan nama MK
Contoh 1 (Jawab)
Tabel Simpleks :
Diperoleh solusi optimal
(x1,x2,s1,s2,s3) = (15,12,14,0,0) dengan z = 4(15)
+ 6(12) = 132.
20
1/22/2015
Rangkuman Metode Simpleks (Maks)
1. Tambahkan variabel slack pada kendala untuk
memperoleh persamaan kendala.
2. Bentuk tabel Simpleks awal.
3. Tentukan entering column dan departing row.
4. Lakukan Eliminasi Gauss-Jordan (OBE).
5. Jika entri pada baris terakhir semuanya positif
atau nol maka SELESAI. Jika tidak, kembali ke 3.
6. Nilai maksimum diperoleh dari entri baris dan
kolom terakhir.
21
1/22/2015
Contoh 2 (Maks)
maks z = 2x1 x2 + 2x3
terhadap kendala
dengan x1, x2, x3 0.
22
1/22/2015
Contoh 2 (Jawab)
23
1/22/2015
Contoh 2 (Jawab)
Solusi optimal :
(x1,x2,x3,s1,s2,s3) = (5,0,5/2,0,20,0)
Nilai maksimum z = 2(5) (0) + 2(5/2) = 15.
24
1/22/2015
Contoh 3
maks z = 3x1 + 2x2 + x3
terhadap kendala
dengan x1, x2, x3 0.
25
1/22/2015
Contoh 3 (Jawab)
s1 lebih tepat disebut
artificial variable dibandingkan
dengan slack variable
26
1/22/2015
Contoh 3 (Jawab)
Solusi optimal :
(x1,x2,x3,s1,s2,s3) = (3,18,0,0,0,1)
Nilai maksimum z = 3(3) + 2(18) + (0) = 45.
27
1/22/2015
Latihan (Maks)
1. Selesaikan masalah memaksimumkan berikut:
28
1/22/2015
Latihan (Maks)
2. Selesaikan masalah memaksimumkan berikut :
29
1/22/2015
Metode Simpleks (Meminimumkan)
Masalah meminimumkan dalam bentuk standar
adalah sbb:
min w = c1x1 + c2x2 + + cnxn
terhadap kendala
30
1/22/2015
Langkah-langkah Metode Simpleks
(min)
Langkah 1: bentuk matriks yg diperluas dari
persamaan kendala, kemudian pada baris terakhir
tambahkan koefisien fungsi tujuan.
31
1/22/2015
Langkah-langkah Metode Simpleks
(Min)
Langkah 2: Transposkan matriks tersebut.
32
1/22/2015
Langkah-langkah Metode Simpleks
(Min)
Langkah 3: Dari matriks hasil transpos kita
peroleh dual problem sbb:
maks z = b1y1 + b2y2 + + bmym
terhadap kendala
dengan yi 0.
33
1/22/2015
Langkah-langkah Metode Simpleks
(Min)
Langkah 4: Lakukan metode Simpleks untuk
dual problem seperti pada masalah
memaksimumkan. Nilai maksimum dari z akan
menjadi nilai minimum dari w. Selanjutnya, nilainilai untuk variabel-variabel x1, x2, , xn pada
baris terakhir dari tabel Simpleks terakhir pada
kolom-kolom yang berkaitan dengan slack
variable.
34
1/22/2015
Contoh 1 (Min)
1.
min w = 3x1 + 2x2
terhadap kendala
dengan x1, x2 0
35
1/22/2015
Contoh 1 (Jawab)
Matriks yang diperluas:
Transpos dari matriks di atas adalah
36
1/22/2015
Contoh 1 (Jawab)
Dual problem:
maks z = 6y1 + 4y2
terhadap kendala
dengan y1, y2 0.
37
1/22/2015
Contoh 1 (Jawab)
Lakukan metode Simpleks pada dual problem.
38
1/22/2015
Contoh 1 (Jawab)
Dari tabel Simpleks diperoleh nilai maksimum z = 10
(untuk dual problem). Sehingga untuk masalah
meminimumkan kita peroleh nilai minimum
w = 10 = 3(2) + 2(2)
terjadi pada saat x1 = 2 dan x2 = 2.
39
1/22/2015
Contoh 2 (min)
min w = 2x1 + 10x2 + 8x3
terhadap kendala
dengan
40
1/22/2015
Contoh 2 (Jawab)
Matriks yang diperluas dan transposnya adalah
41
1/22/2015
Contoh 2 (Jawab)
Dual problem:
maks z = 6y1 + 8y2 + 4y3
terhadap kendala
42
1/22/2015
Contoh 2 (Jawab)
Selesaikan dual problem:
43
1/22/2015
Contoh 2 (Jawab)
Diperoleh nilai minimum w = 36 terjadi pada saat
x1 = 2, x2 = 0, x3 = 4.
44
1/22/2015
Latihan (Min)
1. Cari nilai minimum untuk masalah berikut.
45
1/22/2015
Latihan (Min)
2. Untuk soal berikut:
a. Selesaikan masalah
masalah meminimumkan
dengan metode grafik.
b. Buat dual problem
c. Selesaikan dual problem
menggunakan metode grafik.
46
1/22/2015
Metode Simpleks (Kendala Campuran)
Contoh masalah pemrograman linear yang
melibatkan kendala campuran adalah sbb:
maks
z = x1 + x2 + 2x3
terhadap kendala
dengan x1, x2, x3 0.
47
1/22/2015
Metode Simpleks (Kendala Campuran)
Untuk pertidaksamaan pertama pada kendala kita
tambahkan slack variable, menjadi
Sedangkan untuk pertidaksamaan kedua dan
ketiga kita kurangkan dengan surplus variable,
menjadi
48
1/22/2015
Metode Simpleks (Kendala Campuran)
Sehingga kita peroleh tabel Simpleks sbb.
tidak feasible
Solusi:
Metode Simpleks belum bisa dimulai sampai
ditemukan feasible solution.
49
1/22/2015
Metode Simpleks (Kendala Campuran)
Untuk mencari solusi feasible pada awal tabel
Simpleks kita gunakan trial and error.
tidak feasible
Solusi:
50
1/22/2015
Metode Simpleks (Kendala Campuran)
Akhirnya, kita temukan solusi feasible:
Oleh karena itu, dari sini kita bisa mulai metode
Simpleks seperti biasa.
51
1/22/2015
Metode Simpleks (Kendala Campuran)
Setelah sekali pivoting kita peroleh
Baris terakhir sudah tidak ada yg negatif.
Sehingga nilai maksimum kita peroleh z = 64
terjadi saat x1 = 0, x2 = 36, x3 = 14.
52
1/22/2015
Contoh 1
maks
z = 3x1 + 2x2 + 4x3
terhadap kendala
dengan x1, x2, x3 0
53
1/22/2015
Contoh 1 (Jawab)
tabel Simpleks awal
Solusi awal tidak feasible, lakukan trial and
error misal: departing s3 dan entering x2.
54
1/22/2015
Contoh 1 (Jawab)
Kita temukan feasible solution:
(x1,x2,x3,s1,s2,s3) = (0,4,0,10,8,0).
Dari sini kita mulai metode Simpleks.
55
1/22/2015
Contoh 1 (Jawab)
56
1/22/2015
Contoh 1 (Jawab)
Baris terakhir sudah tidak ada yg negatif.
Nilai maksimum z = 17 terjadi saat
x1 = 0, x2 = 13/2, x3 = 1.
57
1/22/2015
Contoh 2
min w = 4x1 + 2x2 + x3
terhadap kendala
dengan x1, x2, x3 0
58
1/22/2015
Contoh 2 (Jawab)
Pertama kita ubah fungsi tujuan dengan cara
mengalikan dengan -1, diperoleh
z = -4x1 2x2 x3
(revisi fungsi tujuan)
Memaksimumkan revisi fungsi tujuan ekivalen
dengan meminimumkan fungsi tujuan yg awal.
Selanjutnya kita selesaikan masalah
memaksimumkan seperti biasa.
59
1/22/2015
Contoh 2 (Jawab)
Lakukan trial and error untuk menemukan
feasible solution. Coba departing s2 dan entering
x2.
Setelah pivoting kita peroleh tabel Simpleks sbb:
60
1/22/2015
Contoh 2 (Jawab)
Kalikan persamaan ketiga dengan (-1), diperoleh
feasible solution.
61
1/22/2015
Contoh 2 (Jawab)
Lakukan metode Simpleks seperti biasa.
62
1/22/2015
Contoh 2 (Jawab)
Akhirnya kita temukan nilai maksimum untuk
revisi fungsi tujuan yaitu z = -2, sehingga nilai
minimum untuk fungsi tujuan asal adalah
w = 2.
terjadi pada saat x1 = 0, x2 = 0, dan x3 = 2.
63
1/22/2015
Latihan
1.
64
1/22/2015
Latihan
2.
65
1/22/2015
1/22/2015
66
THANK YOU