7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 1

• Menggunakan prinsip eliminasi Gauss-Jordan.

• Penentuan solusi optimal dilakukan denganmemeriksa satu per satu titik-titik ekstrim padadaerah penyelesaian Perhitungan iteratif

• Langkah-langkah penyelesaian:Ubah bentuk umum PL ke bentukbaku/standarBentuk tabel simpleks awal berdasarkanbentuk bakuPeriksa kelayakan tabelLakukan perhitungan iteratif sampaididapatkan solusi optimal

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 2

Perhitungan iteratif

1. Tentukan kolom pivot (variabel masuk):

• Kolom dengan nilai baris z negatif terbesar, jika tujuan maksimisasi.

• Kolom dengan nilai baris z positif terbesar, jikatujuan minimisasi.

2. Tentukan baris pivot:

• Bagi nilai kanan dengan nilai kolom pivot ygbersesuaian (variabel keluar).

• Baris pivot adalah baris dengan rasiopembagian terkecil.

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 3

3. Tentukan elemen pivot : elemen yg terletak pd perpotongan kolom dan baris pivot.

4. Hitung nilai tabel baru (iterasi ke-n):

• Baris pivot baru = baris pivot lama dibagielemen pivot

• Baris-baris lainnya = baris lama – nilaikolom pivot baris tersebut x nilai baris pivot baru pada kolom yg sama.

5. Periksa keoptimalan.

• Jika tabel sudah optimal, baca solusioptimalnya.

• Jika tabel belum optimal, kembali kelangkah 1.

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 4

BENTUK BAKUAda beberapa hal yang harus diperhatikan dalam

membuat bentuk baku/standar, yaitu:• Fungsi kendala dengan pertidaksamaan ≤ dalam

bentuk umum, diubah menjadi persamaan (=) dengan menambahkan satu variabel slack.

• Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, diubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.

Perhatikan kasus berikut:1. Minimumkan z = 2 x1 + 5.5 x2

Kendala: x1 + x2 = 900.001x1 + 0.002x2 ≤ 0.9

0.09x1 + 0.6x2 ≥ 270.02x1 + 0.06x2 ≤ 4.5

x1, x2 ≥ 0

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 5

Bentuk bakunya adalah:

Minimumkan z = 2 x1 + 5.5 x2 Terhadap: x1 + x2 + s1 = 90

0.001x1 + 0.002x2 + s2 = 0.90.09x1 + 0.6x2 - s3 = 270.02x1 + 0.06x2 + s4 = 4.5

x1, x2, s1, s2, s3, s4 ≥ 0

2. Maksimumkan z = 2x1 + 3x2Terhadap :

10x1 + 5x2 ≤ 6006x1 + 20x2 ≤ 6008x1 + 15x2 ≤ 600

x1, x2 ≥ 0

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 6

Bentuk Baku:Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3Terhadap :

10x1 + 5x2 + s1 = 6006x1 + 20x2 + s2 = 6008x1 + 15x2 + s3 = 600x1, x2, s1, s2, s3 ≥ 0

s1, s2, s3 oleh karenanya merupakan variabel slack.

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 7

Tabel/solusi awal

VB X1 X2 S1 S2 S3 solusiz -2 -3 0 0 0 0S1 10 5 1 0 0 600S2 6 20 0 1 0 600S3 8 15 0 0 1 600

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 8

Iterasi 0 (tabel awal simpleks).

VB X1 X2 S1 S2 S3 solusi rasio

z -2 -3 0 0 0 0 -

S1 10 5 1 0 0 600 600/5=120

S2 6 20 0 1 0 600 600/20=30

S3 8 15 0 0 1 600 600/15=40

X2 adalah variabel masuk dan s2 adalah variabel keluar. Elemen pivot adalah 20.

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 9

Iterasi 1

VB X1 X2 S1 S2 S3 solusi Rasio

z -11/10 0 0 3/20 0 90 -

S18.5 0 1 -1/4 0 450 52.9

X23/10 1 0 1/20 0 30 100

S33.5 0 0 -¾ 1 150 42.85

7

Perhitungan kita ulang ke iterasi 2.Variabel masuk adalah x1 dan variabel keluar adalah s3.

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 10

Iterasi-2

VB X1 X2 S1 S2 S3 Solusiz 0 0 0 9/70 1/35 94.285

7S1 0 0 1 11/7 -17/7 85.715

5X2 0 1 0 8/70 -3/35 17.132

9X1 1 0 0 -3/14 2/7 42.857

7/30/2005 Metode Simpleks, created by Hotniar Siringoringo 11

Solusi optimal : x1 = 42.857; x2 = 17.1329 dan z = 94.2857.

Status sumber daya :s1 = 85.7155. Sumber daya pertama disebut berlebih (abundant)s2 = s3 = 0. Kedua sumber daya (kedua dan ketiga)disebut habis terpakai (scarce).

Harga bayangan :Harga bayangan sumber daya pertama adalah 0.Harga bayangan sumber daya kedua adalah 9/70.Harga bayangan sumber daya ketiga adalah 1/5.