BUKU AJAR

RISET OPERASI

Oleh :
Ir. Koesriwulandari, MP

PROGRAM STUDI AGRIBISNIS

FAKULTAS PERTANIAN
UNIVERSITAS WIJAYA KUSUMA SURABAYA
2018
PROGRAMASI LINIER : METODE SIMPLEX
Suatu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah
metode simplek. Metode simplex digunakan untuk menyelesaikan masalah optimasi yang
melibatkan tiga variabel atau lebih yang tidak dapat diselesaikan oleh metode grafik.
Penentuan solusi optimal dengan menggunakan metode simplek didasarkan pada teknik
eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik
ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi opimal
dengan metode simpleks dilakukan dengan tahap demi tahap yang disebut dengan proses
iterasi, dimana iterasi ke –i tergantung dari iterasi sebelumnya (n-i).
Ada beberapa istiah :
1. Iterasi adalah tahapan dimana nilai dalam perhitungan itu tergantung dari nilai
tabel sebelumnya
2. Variabel non basis adalah merupakan variabel yang nilainya diatur menjadi nol
pada sembarang iterasi
3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang
iterasi. Pada solusi awal variabel basis merupakan variabel SLACK ( jika fungsi
kendala merupakan pertidak samaan ≤) atau variabel buatan ( Jika fungsi kendala
merupakan pertidaksamaan ≥ atau =). Secara umum jumlah variabel basis sama
dengan jumlah fungsi pembatas (tanpa fungsi non negatif)
4. Variabel Slack adalah variabel yang ditambahkan ke model matematik kendala
untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan =. Penambahan ini
pada setiap tahap inisiasi. Pada solusi awal variabel slack akan berfungsi sebagai
variabel basis
5. Variabel Surplus adalah variabel yang dikurangkan ke model matematik kendala
untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan =. Penambahan ini
pada setiap tahap inisiasi. Pada solusi awal variabel surplus tidak dapat berfungsi
sebagai variabel basis
6. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien
pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris pivot
(baris kerja)
7. Baris pivot (baris kerja) adalah satu baris di antara variabel basis yang memuat
variabel keluar
8. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom
dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks
berikutnya
9. Variabel Masuk adalah variabel yang terpilih untuk menjadi variabel basis pada
iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada
setiap iterasi. Variabel ini pada iterasi berikutya akan bernilai positif
10. Variabel Keluar adalah variabel yang keluar dari variabel basispada iterasi
berikutnya dan diganti oleh. variabel masuk. Variabel keluar dipilih satu dari
antara variabel basis pada setiap iterasi. Variabel ini pada iterasi berikutya akan
bernilai nol.

Untuk menyelesaikan masalah optimasi dengan metode simplex ini terlebih dahulu kita
rumuskan fungsi tujuan dan kendala-kendalanya.
Contoh :
Perusahaan “Maju Lancar” menghadapi
Fungsi tujuan : Z = 50x1 + 20x2 + 30x3, dengan
Fungsi Kendala :
o 2x1 + 3x2 ≤ 1000
o 3x1 + 2x3 ≤ 2100
o x2 + 5x3 ≤ 1500
o x1, x2, x3 ≥ 0
Tentukan tingkat produksi yang harus dilakukan agar Z maksimum!

PENYELESAIAN
Untuk menyelesaikan masalah di atas dilakukan langkah-langkah dibawah ini :
1. Pada fungsi tujuan, pindahkan seluruh variabel ke ruas kiri.
Z = 50x1 + 20x2 + 30x3  Z - 50x1 - 20x2 - 30x3 = 0
2. Untuk fungsi kendala, tambahkan variabel antara (slack variabel) disetiap fungsi
kendala secara berurutan dan ubah tanda ≥ dan ≤ menjadi = . Variabel Slack adalah
variabel yang ditambahkan pada model matematik untuk mengubah pertidaksamaan
menjadi persamaan. Variabel Slack ini akan berfungsi sebagai variabel basis.
Variabel basis ini merupakan variabel yang nilainya bukan nol (0). Secara umum
jumlah variabel basis sama dengan jumlah kendala.
Contoh :
Kendala :
2x1 + 3x2 ≤ 1000  2X1 + 3X2 + X4 = 1000
3x1 + 2x3 ≤ 2100  3X1 + 2X3 + X5 = 2100
x2 + 5x3 ≤ 1500  X2 + 5X3 + X6 = 1500
3. Masukkan setiap koefisien variabel ke dalam tabel simplex.
Dalam perhitungan iteratif kita akan beKerja dengan menggunakan tabel. Bentuk baku
yang sudah diperoleh harus dibat ke dalam bentuk tabel. Semua variabel yang bukan
variabel basis mempunyai solusi (nilai kanan) sama dengan 0 dan koefisien variabel basis
pada baris tujuan sama dengan nol.
Sehingga :

Variabel
Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Dasar
Z 1 -50 -20 -30 0 0 0 0
x4 0 2 3 0 1 0 0 1000
x5 0 3 0 2 0 1 0 2100
x6 0 0 1 5 0 0 1 1500

4. Tentukan kolom kunci dengan mengidentifikasi nilai negatif yang terbesar pada baris
tujuan (baris Z).
Pada contoh di atas nilai negatif yang tebesar adalah -50 pada kolom x1.
Sehingga :
Variabel
Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Dasar
Z 1 -50 -20 -30 0 0 0 0
x4 0 2 3 0 1 0 0 1000
x5 0 3 0 2 0 1 0 2100
x6 0 0 1 5 0 0 1 1500
↓
 Kolom kunci

5. Tentukan baris kunci dengan membagi nilai kanan dengan setiap angka pada kolom
kunci. Carilah nilai positif yang terkecil. Index = Nilai Kolom NK
Nilai Kolom Kunci

1000
Baris x 4  500  Nilai positif terkecil
2

2100
Baris x 5  700
3

1500
Baris x 6   tak terdefinisi
0

Jadi nilai terkecil adalah 500, sehingga baris kuncinya ada pada x4.
Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1 -50 -20 -30 0 0 0 0
x4 0 2 3 0 1 0 0 1000 → baris kunci
x5 0 3 0 2 0 1 0 2100
x6 0 0 1 5 0 0 1 1500
↓
Kolom kunci
Angka kunci = 2

6. Karena nilai kunci berada pada kolom x 1, maka baris x4 kita ubah namanya menjadi x1,
dan nilai-nilai pada baris x4 kita ubah pula dengan cara membagi nilai baris dengan angka
kunci.
Sehingga :
Maka kita mendapat nilai baris kunci yang baru (baris x1) :
Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1
x1 0 1 1,5 0 0,5 0 0 500
x5 0
x6 0

7. Untuk mengisi nilai setiap sel, gunakan rumus :

Baris baru : baris lama – (angka kolom kunci X nilai baru baris kunci)
Misalnya :
Pada baris Z lama :
Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1 -50 -20 -30 0 0 0 0
x1
x5
x6
↓
Kolom kunci
Angka kolom kunci = -50

Sedangkan baris kunci yang baru :

Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1
x1 0 1 1,5 0 0,5 0 0 500
x5 0
x6 0

Sehingga baris Z yang baru :

x1 = (-50) – ((-50) X 1) = -50 + 50 = 0
x2 = (-20) – ((-50) X 1,5) = 55
x3 = (-30) –((-50) X 0) = -30
x4 = 0 – ((-50) X 0,5) = 25
x5 = 0 – ((-50) X 0) = 0
x6 = 0 – ((-50) X 0) = 0
Nilai kanan baru = 0 – ((-50) X 500) = 25000
Untuk baris x5, angka kolom kuncinya adalah 3. Sehingga baris x5 baru :
x1 = 3 – (3 X 1) = 0
x2 = 0 – (3 X 1,5) = -4,5
x3 = 2 – (3 X 0) = 2
x4 = 0 – (3 X 0,5) = -1,5
x5 = 1 – (3 X 0) = 1
x6 = 0 – (3 X 0) = 0
Nilai kanan baru = 2100 – (3 X 500) = 600
Untuk baris x6, angka kolom kuncinya adalah 0. Sehingga baris x6 baru :
x1 = 0 – (0 X 1) = 0
x2 = 1 – (0 X 1,5) = 1
x3 = 5 – (0 X 0) = 5
x4 = 0 – (0 X 0,5) = 0
x5 = 0 – (0 X 0) = 0
x6 = 1 – (0 X 0) = 1
Nilai kanan baru = 1500 – (0 X 500) = 1500

8. Masukkan nilai-nilai tersebut ke dalam tabel simplex yang baru.

Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1 0 55 -30 25 0 0 25000
x1 0 1 1,5 0 0,5 0 0 500
x5 0 0 -4,5 2 -1,5 1 0 600
x6 0 0 1 5 0 0 1 1500

9. Perhatikan kembali tabel di atas, bila pada baris Z masih ada variabel yang bernilai
negatif, maka fungsi tujuan belum maksimal. Sehingga untuk menghilangkan nilai negatif
kita ulangi lagi langkah-langkah sebelumnya. Ini kita lakukan terus-menerus hingga tiada
variabel Z yang negatif.

Nilai
Variabel Dasar Z x1 x2 x3 x4 x5 x6
Kanan
Z 1 0 55 -30 25 0 0 25000
x1 0 1 1,5 0 0,5 0 0 500
x5 0 0 -4,5 2 -1,5 1 0 600
x6 0 0 1 5 0 0 1 1500
↓ → baris kunci
Kolom kunci

Angka kunci = 5
Menentukan baris kunci :

Nilai baris kunci yang baru (x3) dihitung dengan

membagi semua angka baris kunci dengan angka
kunci.
Baris x3 baru :
Nilai baris kunci yang baru :
Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z
x1
x5
x3 0 0,2 0,2 1 0 0 0,2 300

Baris Z lama :
0 55 -30 25 0 0 25000
↓
Angka kolom kunci = -30

Baris Z baru :
6 61 0 25 0 6 34000

Baris x1 lama :
1 1,5 0 0,5 0 0 500
↓
 Angka kolom kunci = 0
Baris x1 baru :
1 1,5 0 0,5 0 0 500

Baris x5 lama :
0 -4,5 2 -1,5 1 0 600
↓
Angka kolom kunci = 2

Baris x5 baru :
-0,4 -4,9 0 -1,5 1 -0,4 0

Sehingga tabel simplex yang baru :

Variabel Dasar Z x1 x2 x3 x4 x5 x6 Nilai Kanan
Z 1 6 61 0 25 0 6 34000
x1 0 1 1,5 0 0,5 0 0 500
x5 0 -0,4 -4,9 0 -1,5 1 -0,4 0
x3 0 0,2 0,2 1 0 0 0,2 300

Perhatikan tabel di atas! Karena seluruh variabel pada fungsi Z sudah bernilai positif, maka
fungsi kita sudah maksimal.
Sehingga dapat kita simpulkan bahwa untuk memperoleh hasil maksimum, perusahaan
harus memproduksi :
x1 = 500 unit
x2 = 0
x3 = 300 unit
Z = 50 x1 + 20 x2 + 30 x3
Z = 50(500) + 20(0) + 30(300)
Z = 34000