Senin, 19 Januari 2015

Program Linier : Metode Simpleks

Metode simpleks digunakan untuk memecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan
Prosedur Metode Simpleks
v  Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
v  Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar
v  Membuat Table Simpleks Awal
v  Algoritma metode simpleks


Ketentuan yang perlu diperhatikan


  Contoh
Maksimumkan Z = 3X1 + 5X2
Batasan (constrain)

(1)
2X1
8
(2)
3X2
15
(3)
6X1 + 5X2
30


Bagaimana menyelesaikan dengan metode
Simplex ?
Langkah-langkah metode simpleks



Langkah 1:
Mengubah fungsi tujuan dan batasan-batasan



•   Fungsi tujuan
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.



•   Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)
(1) 2X1                                             8  menjadi        2X1 + X3 = 8
(2) 3X2                                             15 menjadi        3X2    + X4 = 15
(3) 6X1 + 5X2                              30 menjadi        6X1    +    5X2 + X5= 30






Slack variabel adalah variabel tambahan yang mewakili tingkat pengangguran
atau kapasitas yang merupakan batasan
Langkah 2:
Menyusun persamaan-persamaan di dalam tabel


Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.


(1) 2X1                  8  menjadi        2X1                 + X3            = 8 (2) 3X2                  15 menjadi        3X2               + X4             = 15 (3) 6X1 + 5X2       30 menjadi        6X1 +    5X2          + X5     = 30

    

1. Tabel simpleks yang pertama

         Variabel
   Dasar


Z


X1


X2


X3


X4


X5  


   NK

Z

1

-3

-5

0

0

0

   0

X3

0

2

0

1

0

0

   8

X4

0

0

3

0

1

0

    15

X5

0

6

5

0

0

1

    30
Langkah 3: Memilih kolom kunci


  Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti
tabel itu tidak bisa dioptimalkan lagi (sudah optimal).
Langkah 4: Memilih baris kunci
 Langkah 5: Mengubah nilai-nilai baris kunci






Langkah 6: Mengubah nilai-nilai selain pada baris kunci
sehingga nilai-nilai kolom kunci (selain baris kunci) = 0



Baris baru = baris lama (koefisien Angka kolom kunci) x nilai baris baru kunci 

  


Masukkan nilai di atas ke dalam tabel,
sehingga tabel menjadi seperti berikut




Iterasi 1


Langkah 7: Melanjutkan perbaikan



Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif



Variabel
Dasar

Z

X1

X2

X3

X4

X5

NK
Keterangan
(Indeks)

Z

1


-3


0

0

5/3

0

25


X3

0


2


0

1

0

0

8

= 8/2 = 4

X4

0


0


1

0

1/3

0

5


X5

0


6


0

0

-5/3

1

5


= 5/6 (minimum)

Z

1








X3

0








X2

0








X1

0

6/6

0

0

-5/18

1/6

5/6


6/6         0/6       0/6    (-5/3)/6        1/6       5/6                           













                        

Nilai baru

Baris ke-1



[-3
0
0
5/3
0,
25 ]


(-3)
[ 1
0
0
-5/18
1/6,
5/6]
( - )
Nilai baru
=
[ 0
0
0
5/6
½,
271/2]





Baris ke-2 (batasan 1)



[ 2
0
1
0
0,
8 ]


(2)
[ 1
0
0
-5/18
1/6,
5/6]
( - )
Nilai baru
=
0
0
1
5/9
-1/3,
61/3]




Baris ke-3 tidak berubah karena nilai pada kolom kunci = 0



[ 0
1
0
1/3
0,
5 ]


(0)
[ 1
0
0
-5/18
1/6,
5/6]
( - )
Nilai baru
=
0
1
0
1/3
0,
5]


Tabel simpleks final hasil perubahan


Variabel
Dasar


Z


X1


X2


X3


X4


X5


NK

Z

1

0

0

0

5/6

½

271/2

X3

0

0

0

1

5/9

-1/3

61/3

X2

0

0

1

0

1/3

0

5

X1

0

1

0

0

-5/18

1/6

5/6

Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak
dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal





 
Dari tabel final didapat


X1 = 5/6
X2 = 5
Zmaksimum = 271/2



1 komentar: