Metode Simpleks – Maksimasi (2)


Pada tulisan sebelumnya Metode Simpleks – Maksimasi (1) dibahas mengenai bagaimana mangubah formulasi program linier ke dalam Bentuk Baku atau Bentuk Kanonik. Selanjutnya pada tulisan ini akan dibahas langkah selanjutnya dalam penggunaan Metode Simpleks, yaitu membuat Tabel Simpleks Awal.

BENTUK TABEL SIMPLEKS AWALSimpleks-Maks_01

Pada tabel di atas terlihat bahwa terdapat kolom Variabel Dasar, yang merupakan solusi awal. Pada table simpleks awal yang berperan sebagai variable dasar adalah variable tambahan yang bernilai positif, yaitu variable slack, surplus dan artificial. Selanjutnya akan terjadi perubahan yang menjadi variable dasar dengan adanya Variable Masuk (entering variable) dan Variable Keluar (leaving variable).

ALGORITMA SIMPLEKS

1. Menentukan Kolom Kunci

Menentukan kolom kunci ini dengan cara mencari nilai paling negative pada baris fungsi tujuan atau baris Z. Variabel yang berada pada kolom kunci ini akan menjadi Variabel Masuk untuk mengantikan Variabel Dasar sebelumnya. Variabel dasar mana yang akan digantikan akan ditentukan pada langkah kedua.

2. Menentukan Baris Kunci (Baris Pivot)

Menentukan Baris Kunci, yaitu dengan cara membuat nilai perbandingan antar Nilai Kanan dengan nilai pada Kolom Kunci pada setiap baris kecuali pada baris fungsi tujuan. Baris yang dengan nilai terkecil yang akan menjadi Baris Kunci. Variabel Dasar yang berada pada baris kunci yang akan menjadi Variabel Keluar.

3. Menentukan Angka Kunci (Pivot Elemen)

Kemudian yang menjadi Angka Kunci adalah pertemuan antara Kolom Kunci dengan Baris Kunci.

4. Menentukan Baris Kunci Baru

Membagi setiap elemen pada Baris Kunci dengan Angka Kunci

5. Operasi Baris Elementer

Yaitu merubah semua nilai pada setiap baris kecuali Baris Kunci dengan cara :

Nilai Baru = Nilai lama – (nilai Kolom Kerja x nilai Baris Kunci Baru)

6. Uji Optimisasi

Langkah terakhir adalah memeriksa apakah sudah maksimum atau belum. Jika masih terdapat nilai negative pada baris Fungsi Tujuan, maka table tersebut belum optimal. Sehingga perlu dilakukan kembali langkah-langkah di atas sedemikian hingga memperoleh penyelesaian yang optimum.

Contoh 1.

Fungsi Tujuan : Z = 750X_1 + 500X_2

Kendala :  2,5X_1 -2X_2 \leq 100

X_1 + 6X_2 \leq 50

3X_1 \leq 75

Langkah 1 : Bentuk Kanonik

Z -750X_1 -500X_2 + S_1 + S_2 + S_3 = 0

2,5X_1 -2X_2 + S_1 = 100

X_1 + 6X_2 + S_1 = 50

3X_1 + S_3 = 75

Langkah 2 : Tabel Simpleks AwalSimpleks-Maks_02Langkah 3 : Kolom Kunci

Negatif terbesar pada baris Z.Simpleks-Maks_03Langkah 4 : Baris Kunci

Nilai perbandingan NK dengan Kolom Kunci, yaitu

100 : 5/2 = 40

50 : 1 = 50

75 : 3 = 25Simpleks-Maks_04

Baris Kunci adalah baris yang mempunyai nilai perbandingan paling kecil, yaitu baris S_3.Simpleks-Maks_05

Langkah 5 : Menentukan Angka Kunci

Pada table di atas terlihat bahwa yang menjadi Angka Kunci adalah angka pada baris 4 kolom 2, yaitu 3.

Langkah 6 : Baris Kunci Baru

Yaitu membagi Baris Kunci dengan Angka KunciSimpleks-Maks_06

Langkah 7 : Operasi Baris Elementer

Nilai Baru = Nilai lama – (nilai Kolom Kunci x nilai Baris Kunci Baru)

Baris Z:

Kolom X_1 : -750 – (-750 x 1) = 0

Kolom X_2 : -500 – (-750 x 0) = -500

Kolom S_1 : 0 – (-750 x 0) = 0

Kolom S_2 : 0 – (-750 x 0) = 0

Kolom S_3 : 0 – (-750 x 1/3) = 250

Kolom NK : 0 – (-750 x 25) = 18750

Baris S_1:

Kolom X_1 : 5/2 – (5/2 x 1) = 0

Kolom X_2 : -2 – (5/2 x 0) = -2

Kolom S_1 : 1 – (5/2 x 0) = 1

Kolom S_2 : 0 – (5/2 x 0) = 0

Kolom S_3 : 0 – (5/2 x 1/3) = 5/6

Kolom NK : 100 – (5/2 x 25) = 37,5

Baris S_2:

Kolom X_1 : 1 – (1 x 1) = 0

Kolom X_2 : 6 – (1 x 0) = 6

Kolom S_1 : 0 – (1 x 0) = 0

Kolom S_2 : 1 – (1 x 0) = 1

Kolom S_3 : 0 – (1 x 1/3) = -1/3

Kolom NK : 50 – (1 x 25) = 25

Sehingga diperoleh Tabel Simpleks sebagai berikutSimpleks-Maks_07

Karena masih ada variable yang bernilai negative pada baris Z, maka table simplex tersebut belum optimal, sehingga harus melakukan langkah yang sama lagi.

Langkah 1 : Kolom KunciSimpleks-Maks_08

Langkah 4 : Baris Kunci

Nilai perbandingan NK dengan Kolom Kunci, yaitu

-2 : 37,5 = -2 : 75/2 = 4/75

6 : 25 = 6/25

0 : 25 = 0Simpleks-Maks_09

Langkah 3 : Menentukan Angka Kunci

Dalam hal ini, yang menjadi Angka Kunci adalah baris 3 kolom 3, yaitu 6.

Langkah 4 : Baris Kunci Baru

Yaitu membagi Baris Kunci dengan Angka KunciSimpleks-Maks_10

Langkah 5 : Operasi Baris Elementer

Nilai Baru = Nilai lama – (nilai Kolom Kunci x nilai Baris Kunci Baru)

Baris Z:

Kolom X_1 : 0 – (-500 x 0) = 0

Kolom X_2 : -500 – (-500 x 1) = 0

Kolom S_1 : 0 – (-500 x 0) = 0

Kolom S_2 : 0 – (-500 x 1/6) = 500/6

Kolom S_3 : 250 – (-500 x -1/18) = 2000/9

Kolom NK : 18750 – (-500 x 25/6) = 62500/3

Baris S_1:

Kolom X_1 : 0 – (-2 x 0) = 0

Kolom X_2 : -2 – (-2 x 1) = 0

Kolom S_1 : 1 – (-2 x 0) = 1

Kolom S_2 : 0 – (-2 x 1/6) = 1/3

Kolom S_3 : 5/6 – (-2 x -1/18) = 13/18

Kolom NK : 75/2 – (-2 x 25/6) = 275/6

Sehingga diperoleh Tabel Simpleks sebagai berikutSimpleks-Maks_11Karena koefesien semua variable pada baris Z bernilai positif, maka Tabel Simpleks tersebut sudah optimal. Sehingga diperoleh solusinya adalah

X_1 = 25 dan X_2 = \dfrac{25}{6}

Serta Z = 750X_1 + 500X_2  = \dfrac{62500}{3}

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s