metode simplex

IKG3M3 / Optimasi dan Kontrol

Dede Tarwidi

KK Pemodelan dan Simulasi

METODE SIMPLEKS 1

Merupakan prosedur aljabar yang bersifat iteratif, yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrim pada daerah feasible menuju ke titik ekstrim optimum.

2 1/22/2015

Metode Simpleks

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

Metode Simpleks (Memaksimumkan)

IKG3M3 OPTIMASI DAN KONTROL

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.

4 1/22/2015

Beberapa ketentuan dalam metode Simpleks

Setelah ditambahkan variabel slack maka persamaan kendala menjadi

dengan si ≥ 0, i=1,2,…,n.

5 1/22/2015

Metode Simpleks

IKG3M3 OPTIMASI DAN KONTROL

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.

6 1/22/2015

Metode Simpleks

Tabel yang terdiri dari matriks yang diperluas dari persamaan kendala dengan fungsi tujuan berbentuk

7 1/22/2015

Tabel Simpleks

Kode dan nama MK

8 1/22/2015

Bentuk Tabel Simpleks

maks z = 4x1 + 6x2

terhadap kendala

9 1/22/2015

Contoh 1 (Maks)

Kode dan nama MK

Tabel Simpleks untuk masalah tesebut adalah

Basic variable: s1, s2, dan s3

Nonbasic variable: x1, dan x2

10 1/22/2015

Contoh 1 (Jawab)

Kode dan nama MK

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

Contoh (Jawab)

Kode dan nama MK

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

Catatan Metode Simpleks

Kode dan nama MK

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

Pivoting

Kode dan nama MK

Entering dan departing variable dari contoh 1 adalah

14 1/22/2015

Contoh 1 (Jawab)

Kode dan nama MK

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

Contoh 1 (Jawab)

Kode dan nama MK

Selanjutnya lakukan eliminasi Gauss-Jordan:

16 1/22/2015

Contoh 1 (Jawab)

Kode dan nama MK

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

Contoh 1 (Jawab)

Kode dan nama MK

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

Contoh 1 (Jawab)

Kode dan nama MK

Tabel Simpleks yang baru adalah

Lakukan eliminasi Gauss-Jordan sekali lagi maka diperoleh Simpleks tabel sebagai berikut.

19 1/22/2015

Contoh 1 (Jawab)

Kode dan nama MK

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

Contoh 1 (Jawab)

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

Rangkuman Metode Simpleks (Maks)

maks z = 2x1 – x2 + 2x3

terhadap kendala

dengan x1, x2, x3 ≥ 0.

22 1/22/2015

Contoh 2 (Maks)

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 2 (Jawab)

25 1/22/2015

Contoh 3

maks z = 3x1 + 2x2 + x3

terhadap kendala

dengan x1, x2, x3 ≥ 0.

26 1/22/2015

Contoh 3 (Jawab)

s1 lebih tepat disebut artificial variable dibandingkan dengan slack variable

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

Contoh 3 (Jawab)

1.Selesaikan masalah memaksimumkan berikut:

28 1/22/2015

Latihan (Maks)

2.Selesaikan masalah memaksimumkan berikut :

29 1/22/2015

Latihan (Maks)

Masalah meminimumkan dalam bentuk standar adalah sbb:

min w = c1x1 + c2x2 + … + cnxn

terhadap kendala

30 1/22/2015

Metode Simpleks (Meminimumkan)

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, nilai-nilai 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

Langkah-langkah Metode Simpleks (Min)

1. min w = 3x1 + 2x2

terhadap kendala

dengan x1, x2 ≥ 0

35 1/22/2015

Contoh 1 (Min)

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 1 (Jawab)

min w = 2x1 + 10x2 + 8x3

terhadap kendala

dengan

40 1/22/2015

Contoh 2 (min)

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

Contoh 2 (Jawab)

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

Latihan (Min)

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.

Solusi:

Metode Simpleks belum bisa dimulai sampai

ditemukan feasible solution. 49 1/22/2015

Metode Simpleks (Kendala Campuran)

tidak feasible

Untuk mencari solusi feasible pada awal tabel Simpleks kita gunakan “trial and error”.

Solusi:

50 1/22/2015

Metode Simpleks (Kendala Campuran)

tidak feasible

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

Sehingga nilai maksimum kita peroleh z = 64 terjadi saat x1 = 0, x2 = 36, x3 = 14.

52 1/22/2015

Metode Simpleks (Kendala Campuran)

Baris terakhir sudah tidak ada yg negatif.

maks z = 3x1 + 2x2 + 4x3

terhadap kendala

dengan x1, x2, x3 ≥ 0

53 1/22/2015

Contoh 1

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)

Nilai maksimum z = 17 terjadi saat

x1 = 0, x2 = 13/2, x3 = 1.

57 1/22/2015

Contoh 1 (Jawab)

Baris terakhir sudah tidak ada yg negatif.

min w = 4x1 + 2x2 + x3

terhadap kendala

dengan x1, x2, x3 ≥ 0

58 1/22/2015

Contoh 2

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

Contoh 2 (Jawab)

1.

64 1/22/2015

Latihan

2.

65 1/22/2015

Latihan

THANK YOU

66 1/22/2015