linier programming (lp): metode...

Linier Programming (LP): Metode Simpleks

Teknik Riset operasional

2 SKS | D3 | S1

Manajemen Informatika & Teknik Informatika

Outline Bahasan

1. Model LP & Simpleks

2. Tahapan dalam Metode Simpleks

3. Contoh dan Latihan

Kompetensi

Mahasiswa dapat menjelaskan tentang penggunaan metode simpleks dalam pemrograman linier

Mahasiswa dapat menyelesaikan program linier menggunakan metode simpleks

Definisi

Metode Simpleks merupakan metode yang umum untuk mencari nilai optimal seluruh problem program linier, baik yang melibatkan dua atau lebih variabel keputusan.

Metode ini digunakan karena metode grafik tidak dapat menyelesaikan persoalan program linear yang memilki variabel keputusan yang cukup besar atau lebih dari dua.

Metode penyelesaian dari metode simpleks ini melalui perhitungan ulang (iteration) dimana langkah-langkah perhitungan yang sama diulang-ulang hingga solusi optimal diperoleh

Syarat Metode Simpleks

Model program linier (canonical form) harus diubah dulu ke dalam suatu bentuk umum yang dinamakan ”bentuk baku” (standard form).

Metode simpleks hanya bisa diaplikasikan pada “bentuk baku” simpleks

Syarat Metode Simpleks

Fungsi Batasan (Constraint):

Suatu fungsi pembatas yang mempunyai tanda ≤ diubah menjadi suatu bentuk persamaan (standar) dengan cara menambahkan suatu variabel baru yang dinamakan slack variable.

Banyaknya slack variabel bergantung pada fungsi pembatas.

Fungsi Tujuan:

Dengan adanya slack variable pada fungsi pembatas, maka fungsi tujuan juga harus disesuaikan dengan memasukkan unsur slack variable ini.

Karena slack variable tidak mempunyai kontribusi apa-apa terhadap fungsi tujuan, maka konstanta slack variable tersebut dituliskan nol.

Bentuk Standar Metode Simpleks

Fungsi Tujuan: MaksimumkanZ – C1X1- C2X2- . . . . . – CnXn - 0S1 - 0S2-. . .- 0Sn = NK

Fungsi Pembatas:a11X11 + a12X12 +. . . .+ a1nXn + 1S1 + 0S2+. . .+ 0Sn = b1

a21X21 + a22X22+. . . .+ a2nXn + 0S1 + 1S2+. . .+ 0Sn = b2

……. …….. ……. ….. ….. …. …..= …am1Xm1 + am2Xm2 +.. .+ amnXn + S1 + 0S2 +. . .+ 1Sn = bm

Var. Kegiatan Variabel Slack/Surplus/Artifisial

Bentuk Standar Metode Simpleks

Setelah fungsi batasan dirubah ke dalam bentuk persamaan(bentuk standar), maka untuk menyelesaikan masalahprogram linier dengan metode simpleks menggunakansuatu kerangka tabel yang disebut dengan tabel simpleks.

Tabel simpleks mengatur model ke dalam suatu bentuk yang memungkinkan untuk penerapan penghitungan matematismenjadi lebih mudah

Tabel Simpleks :

Var.

DasarZ X1 X2 . . . . Xn S1 S2 . . . . Sn NK

Z 1 -C1 -C2 . . . . -Cn 0 0 0 0 0

S1 0 a11 a12 . . . a1n 1 0 0 0 b1

S2 0 a21 a22 . . . a2n 0 1 0 0 b2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sn 0 am1 am2 . . . amn 0 0 0 1 bm

Terminologi dalam Metode Simpleks

a) Iterasi: tahapan perhitungan dimana nilai dalam perhitungan itutergantung dari nilai tabel sebelumnya.

b) Variabel non basis/dasar: variable yang nilainya diatur menjadi nolpada sembarang iterasi.

c) Variabel basis/dasar : variabel yang nilainya bukan nol padasembarang iterasi.

Pada solusi awal, variabel basis = variabel slack (jika fungsi kendalamerupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsikendala menggunakan pertidaksamaan ≥ atau =).

Secara umum, jumlah variabel basis =jumlah fungsi pembatas(tanpa fungsi non negatif).

d) Solusi atau Nilai Kanan (NK) : nilai sumber daya pembatas yang masihtersedia. Pada solusi awal, NK = jumlah sumber daya pembatas awalyang ada, karena aktivitas belum dilaksanakan

e) Variabel Slack : variabel yang ditambahkan ke model matematikakendala untuk mengkonversi pertidaksamaan ≤ menjadi =

f) Variabel Surplus : variabel yang dikurangkan dari model matematikauntuk mengkonversikan pertidaksamaan ≥ menjadi persamaan =

Terminologi dalam Metode Simpleks

g) Variabel buatan: variabel yang ditambahkan ke dalam model matematika kendala dengan bentuk ≥ atau = untuk difungsikansebagai variabel basis awal.

h) Kolom Pivot/Kunci/Kerja : kolom yang memuat variabel masuk.

i) Baris Pivot/Kunci/Kerja : salah satu baris dari antara variabel baris yang memuat variabel keluar.

j) Elemen atau Nilai Pivot/Kunci/Kerja : elemen yang terletak padaperpotongan/pertemuan kolom dan baris kunci/pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks iterasiberikutnya.

k) Variabel masuk : variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antaravariabel non basis pada setiap iterasi. Variabel ini pada iterasiberikutnya akan bernilai positif.

l) Variabel keluar : variabel yang keluar dari variabel basis pada iterasiberikutnya dan digantikan dengan variabel masuk

Langkah-Langkah Metode Simpleks

1. Rumuskan persoalan PL ke dalam model umum PL (fungsi tujuan dan fungsi pembatas).

2. Merubah model umum PL menjadi model simpleks :

a. Fungsi Pembatas : tambahkan slack variabel dan/atau surplusvariabel, dan/atau variabel buatan (artifisial var).

b. Fungsi Tujuan :

o Ubahlah bentuk fungsi tujuan eksplisit menjadi persamaan bentuk implisit

o Tambahkan/kurangi dengan slack var, surplus var dan/atau variabel buatan yg bernilai nol.

3. Formulasikan ke dalam Tabel Simpleks.

4. Lakukan langkah-langkah penyelesaian.

Contoh 1

Model Program Linear

Fungsi Tujuan : Maksimumkan

Z= 8X1 + 6X2 (Dlm Rp1000)

Fungsi Pembatas :

Bahan A : 4X1 + 2X2 ≤ 60

Bahan B : 2X1 + 4X2 ≤ 48

X1, X2

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z

S1

S2

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z -8 -6 0 0 0

S1

S2

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Tabel Simpleks :

Variabel Dasar

X1 X2 S1 S2 NK

Z -8 -6 0 0 0

S1 4 2 1 0 60

S2

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z -8 -6 0 0 0

S1 4 2 1 0 60

S2 2 4 0 1 48

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Model Simpleks :

Fungsi Tujuan : Maksimumkan

Z– 8X1–6X2–0S1- 0S2 = 0

Fungsi Pembatas :

4X1+2X2+ 1S1+ 0S2 = 60

2X1+4X2+ 0S1+ 1S2 = 48

X1, X2, S1, S2 ≥ 0

Variabel Dasar

X1 X2 S1 S2 NK

Z -8 -6 0 0 0

S1 4 2 1 0 60

S2 2 4 0 1 48

Langkah-langkah penyelesaian:

2. Iterasi-1 :

a. Menentukan kolom kunci :

Kolom kunci : kolom yang mempunyai koefisien fungsi tujuanyang bernilai negatif terbesar.

Langkah-langkah penyelesaian:

2. Iterasi-1 :

a. Menentukan kolom kunci :

Kolom kunci : kolom yang mempunyai koefisien fungsi tujuanyang bernilai negatif terbesar.

Variabel Dasar

X1 X2 S1 S2 NK Indeks

Z -8 -6 0 0 0 -

S1 4 2 1 0 60 15

S2 2 4 0 1 48 24

C. Perubahan-perubahan nilai baris :

- Nilai baris kunci baru = (Nilai baris kunci lama) : angka kunci

- Nilai baris lain = Baris lama – (Angka kolom kunci baris ybs *

Nilai baris kunci baru)

Variabel Dasar

X1 X2 S1 S2 NK

Z

X1 1 ½ ¼ 0 15

S2

4/4 2/4 1/4 0/4 60/4

Mengubah nilai-nilai selain pada baris kunci

Rumus :

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

Nilai lama -8 -6 0 0 0

(-8) 1 1/2 1/4 0 15 ( - )

Nilai baru = 0 -2 2 0 120

Baris ke-1 (Z)

Baris ke-3 (batasan 2)

Nilai lama 2 4 0 1 48

(2) 1 1/2 1/4 0 15 ( - )

Nilai baru = 0 3 -1/2 1 18

VariabelDasar

X1 X2 S1 S2 NK

Z 0 - 2 2 0 120

X1 1 ½ ¼ 0 15

S2 0 3 - ½ 1 18

Tabel Simpleks Hasil Iterasi-1

VariabelDasar

X1 X2 S1 S2 NK Indeks

Z 0 - 2 2 0 120 -

X1 1 ½ ¼ 0 15 30

S2 0 3 - ½ 1 18 6

Tabel Simpleks Hasil Iterasi-1

Variabel Dasar

X1 X2 S1 S2 NK Indeks

Z

X1

X2 0 1 - 1/6 1/3 6 -

Mengubah nilai-nilai selain pada baris kunci

Rumus :

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

Nilai lama 0 -2 2 0 120

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

Nilai baru = 0 0 5/3 2/3 132

Baris ke-1 (Z)

Baris ke-2 (batasan 1)

Nilai lama 1 1/2 1/4 0 15

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

Nilai baru = 1 0 1/3 -1/6 12

Variabel Dasar

X1 X2 S1 S2 NK Indeks

Z 0 0 5/3 2/3 132 -

X1 1 0 1/3 - 1/6 12 -

X2 0 1 - 1/6 1/3 6 -

Tabel Simpleks Hasil Iterasi-2

Pada iterasi-2 terlihat bahwa koefisien fungsi tujuan sudah tidak ada lagi yang mempunyai nilai negatif, proses perubahan selesai dan ini menunjukkan penyelesaian persoalan linear dengan metode simpleks sudah mencapai optimum dengan hasil sbb :

X1= 12 dan X2 = 6

dengan Zmaksimum = Rp 132.000.-

Kesimpulan Contoh 1

LP dengan Metode Simpleks

Bagian Ke-2

Model Program Linear

1. Fungsi Tujuan :

Maksimumkan : Z =15X1 + 10X2 (Dlm Rp10.000)

2. Fungsi Kendala:

Bahan A : X1 + X2 ≤ 600

Bahan B : 2X1 + X2 ≤ 1000

X1, X2 ≥ 0

Carilah solusi model LP tersebut denganmenggunakan metode simpleks.

Contoh 2

Model Simpleks

1. Fungsi Tujuan : Maksimumkan

Z– 15X1–10 X2–0S1– 0S2 = 0

2. Fungsi Pembatas :

X1+X2+ S1+ 0S2 = 600

2X1+X2+0S1+ 1S2 = 1000

X1, X2, S1, S2

Contoh 2

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z

S1

S2

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z -15 -10 0 0 0

S1

S2

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z -15 -10 0 0 0

S1 1 1 1 0 600

S2

Tabel Simpleks :

VariabelDasar

X1 X2 S1 S2 NK

Z -15 -10 0 0 0

S1 1 1 1 0 600

S2 2 1 0 1 1000

Langkah-langkah penyelesaian :

1. Iterasi Awal (Iterasi-0)

VariabelDasar

X1 X2 S1 S2 NK

Z -15 -10 0 0 0

S1 1 1 1 0 600

S2 2 1 0 1 1000

2. Iterasi-1 :

a. Menentukan kolom kunci :

Kolom kunci : kolom yang mempunyai koefisien fungsi tujuan yang bernilai negatif terbesar.

VariabelDasar

X1 X2 S1 S2 NK

Z -15 -10 0 0 0

S1 1 1 1 0 600

S2 2 1 0 1 1000

VariabelDasar

X1 X2 S1 S2 NK Indeks

Z -15 -10 0 0 0 -

S1 1 1 1 0 600 600

S2 2 1 0 1 1000 500

2. Iterasi-1 :

C. Perubahan-perubahan nilai baris :

Nilai baris kunci baru = (Nilai baris kunci lama) : n-angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

VariabelDasar

X1 X2 S1 S2 NK

Z

S1

X1 1 ½ 0 ½ 500

Mengubah nilai-nilai selain pada baris kunci

Rumus :

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

Nilai lama -15 -10 0 0 0

(-15) 1 ½ 0 ½ 500 ( - )

Nilai baru = 0 -2½ 0 7½ 7500

Baris ke-1 (Z)

Baris ke-2 (batasan 1)

Nilai lama 1 1 1 0 600

(1) 1 ½ 0 ½ 500 ( - )

Nilai baru = 0 ½ 1 - ½ 100

2. Iterasi-1 :

C. Perubahan-perubahan nilai baris :

Nilai baris kunci baru = (Nilai baris kunci lama) : nilai angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

VariabelDasar

X1 X2 S1 S2 NK

Z

S1 0 ½ 1 - ½ 100

X1 1 ½ 0 ½ 500

2. Iterasi-1 :

C. Perubahan-perubahan nilai baris :

Nilai baris kunci baru = (Nilai baris kunci lama) : nilai angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

Variabel Dasar

X1 X2 S1 S2 NK

Z 0 -2½ 0 7½ 7500

S1 0 ½ 1 - ½ 100

X1 1 ½ 0 ½ 500

3. Iterasi-2 :

Perhatikan apakah koefisien fungsi tujuan pada Tabel simpleks

masih ada yang bernilai negatif.

Variabel Dasar

X1 X2 S1 S2 NK Indeks

Z 0 -2½ 0 7½ 7500 -

S1 0 ½ 1 - ½ 100 200

X1 1 ½ 0 ½ 500 1000

Angka Kunci

3. Iterasi-2 :

C. Perubahan-perubahan nilai baris pada angka kunci dan baris-baris lainnya :

Nilai baris kunci baru = (Nilai baris kunci lama) : nilai angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

VariabelDasar

X1 X2 S1 S2 NK Indeks

Z

X2 0 1 2 -1 200 -

X1

Mengubah nilai-nilai selain pada baris kunci

Rumus :

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

Nilai lama 0 -2½ 0 7½ 7500

(-2½) 0 1 2 -1 200 ( - )

Nilai baru = 0 0 5 5 8000

Baris ke-1 (Z)

Baris ke-3 (batasan 3)

Nilai lama 1 ½ 0 ½ 500

(1/2) 0 1 2 -1 200 ( - )

Nilai baru = 1 0 -1 1 400

3. Iterasi-2 :

C. Perubahan-perubahan nilai baris pada angka kunci dan baris-baris lainnya :

Nilai baris kunci baru = (Nilai baris kunci lama) : nilai angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

Variabel Dasar

X1 X2 S1 S2 NK Indeks

Z

X2 0 1 2 -1 200 -

X1 1 0 -1 1 400 -

3. Iterasi-2 :

C. Perubahan-perubahan nilai baris pada angka kunci dan baris-baris lainnya :

Nilai baris kunci baru = (Nilai baris kunci lama) : nilai angka kunci

Nilai baris yang lain = Baris lama – (angka kolom kunci baris ybs *Nilai baris kunci baru)

VariabelDasar

X1 X2 S1 S2 NK Indeks

Z 0 0 5 5 8000 -

X2 0 1 2 -1 200 -

X1 1 0 -1 1 400 -

Pada iterasi-2 terlihat bahwa koefisien fungsi tujuansudah tidak ada lagi yang mempunyai nilai negatif,proses perubahan selesai dan ini menunjukkanpenyelesaian persoalan linear dengan metodesimpleks sudah mencapai optimum dengan hasilsbb :

X1= 400 dan X2 = 200

Zmaksimum = Rp 8.000,- (dlm Rp10.000)

Kesimpulan:

1. Fungsi Tujuan : Maksimumkan

Z = 60x1+30x2+20x3

Fungsi Pembatas :

8x1 + 6x2 + x3 ≤ 48

4x1 + 2x2 + 1.5x3 ≤ 20

2x1 + 1.5x2 + 0.5x3 ≤ 8

x1, x2, x3 ≥ 0

2. Fungsi Tujuan : Maksimum

Z = 8x1 + 9x2 + 4x3

Fungsi Pembatas :

x1 + x2 + 2x3 ≤ 2

2x1 + 3x2 + 4x3 ≤ 3

7x1 + 6x2 + 2x3 ≤ 8

x1, x2, x3 ≥ 0

Latihan

3. Fungsi Tujuan : Maksimumkan

Z = 8x1 + 7x2 + 3x3

Fungsi Pembatas :

x1 + x2 + 2x3 ≤ 42x1 + 3x2 + 4x3 ≤ 73x1 + 6x2 + 2x3 ≤ 8

x1, x2, x3 ≥ 0

Gunakan metode simpleks untukmenentukan solusi dari model LPtersebut!

3. Fungsi Tujuan : Maksimumkan

Z = 8x1 + 7x2 + 3x3

Fungsi Pembatas :

x1 + x2 + 2x3 ≤ 42x1 + 3x2 + 4x3 ≤ 73x1 + 6x2 + 2x3 ≤ 8

x1, x2, x3 ≥ 0

Gunakan metode simpleks untukmenentukan solusi dari model LPtersebut!