Linier Programming (Metode Simpleks) (Contoh Soal)

Contoh Soal:

Selesaikan kasus berikut ini menggunakan metode simpleks:

Maksimum z = 8 x₁ + 9 x₂ + 4x₃

Kendala :

x₁ + x₂ + 2x₃ ≤ 2

2x₁ + 3x₂ + 4x₃ ≤ 3

7x₁ + 6x₂ + 2x₃ ≤ 8

x₁,x₂,x₃ ≥ 0

Penyelesaian:

Bentuk bakunya adalah:

Maksimum z = 8 x₁ + 9 x₂ + 4x₃ + 0s₁ + 0s₂ + 0s₃ atau

                     z - 8 x₁ - 9 x₂ - 4x₃ + 0s₁ + 0s₂ + 0s₃ = 0

Kendala:

x₁ + x₂ + 2x₃ + s₁  = 2

2x₁ + 3x₂ + 4x₃ + s₂ = 3

7x₁ + 6x₂ + 2x₃  + s₃ = 8

x₁,x₂,x₃ ,s₁ , s₂ , s₃ ≥ 0

Solusi / table awal simpleks:

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-8	-9	-4	0	0	0	0
S1	1	1	2	1	0	0	2
S2	2	3	4	0	1	0	3
S3	7	6	2	0	0	1	8

Karena nilai negative terbesar  ada pada kolom X₂, maka kolom X₂ adalah kolom pivot dan X₂ adalah variabel masuk. Rasio pembagian nilai kanan  dengan kolom pivot terkecil adalah 1 bersesuaian  dengan  baris s₂, maka baris s₂ adalah baris pivot dan s₂ adalah varisbel keluar. Elemen pivot adalah 3.

VB	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
S2	2	3	4	0	1	0	3	1
S3	7	6	2	0	0	1	8	8/6

Iterasi 1

Nilai pertama yang kita miliki adalah nilai baris  pivot baru (baris x₂). Semua nilai pada baris s₂ pada tabel solusi awal dibagi dengan 3 (elemen pivot).

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z
S1
x2	2/3	1	4/3	0	1/3	0	1
S3

Perhitungan nilai barisnya:

Baris z:

             -8         -9         -4         0          0          0          0

    -9 (  2/3          1         4/3       0          1/3        0          1 )   -

            -2           0          8         0           3         0         9

Baris s₁:

             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

Maka tabel iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel sudah optimal atau belum. Karena nilai baris z di bawah variabel x₁ masih negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada tabel di bawah ini:

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
S3	3	0	-6	0	-2	1	2	2/3

Variabel masuk  dengan demikian adalah X₁ dan variabel  keluar adalah S₃ . Hasil perhitungan iterasi ke 2 adalah sebagai berikut:

Iterasi 2:

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
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

Tabel sudah optimal, sehingga perhitungan iterasi dihentikan !

Perhitungan dalam simpleks menuntut ketelitian  tinggi, khususnya jika angka yang digunakan adalah pecahan. Pembulatan harus diperhatikan dengan baik. Disarankan jangan menggunakan bentuk bilangan desimal, akan lebih teliti jika menggunakan bilangan pecahan. Pembulatan dapat menyebabkan iterasi lebih panjang atau bahkan tidak selesai karena ketidaktelitian dalam melakukan pembulatan.

Perhitungan iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari kondisi nol (dimana semua aktivitas/variabel keputusan bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan perhitungan iteratif sebanyak n kali.