Fakultas Teknik

Universitas Pasundan

Jurusan Teknik Industri

Tjutju T Dimyati

OPERATIONS RESEARCH – I

MODEL-MODEL DETERMINISTIK

Jurusan Teknik Industri FT Unpas

PEMROGRAMAN LINIER

Tjutju T. Dimyati

PENYELESAIAN PERSOALAN DENGAN METODE SIMPLEKS

Jurusan Teknik Industri FT Unpas

Tujuan Pembelajaran

Menguasai penyelesaian persoalan Pemrograman Linier dengan metode Simpleks

Tjutju T. Dimyati

Jurusan Teknik Industri FT Unpas

Capaian Pembelajaran

Di akhir perkuliahan mahasiswa:

Mampu menyelesaikan persoalan Pemrograman Linier dengan dua atau lebih variable yang seluruh fungsi pembatasnya bertanda ≤ melalui penerapan konsep aljabar linier dan matriks

Tjutju T. Dimyati

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

ALGORITMA SIMPLEX

Digunakan untuk menyelesaikan persoalan LP dengan karakteristik sebagai berikut:

• Ada dua atau lebih variabel keputusan

• Fungsi tujuan maksimasi atau minimasi

• Seluruh fungsi pembatas merupakan

pertaksamaan dengan tanda

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Contoh Persoalan

Maks Z = 5 X1 + 14 X2

dengan pembatas:

X1 + 2 X2 6

X1 + 4 X2 8

X1 , X2 0

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Terminologi

• Bentuk standar suatu persoalan LP adalah formulasi model matematis yang seluruh fungsi pembatasnya merupakan persamaan (bertanda =).

• Untuk memperoleh bentuk standar biasa digunakan variabel slack (Si), sehingga variabel keputusan akan terdiri dari variabel keputusan asli (dari persoalan semula) dan variabel slack.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Terminologi

• Variabel basis adalah variabel keputusan yang nilainya bukan nol (kecuali pada kasus degenerasi).

• Variabel non-basis adalah variabel keputusan yang tidak mempunyai nilai.

Catatan:

Banyaknya variabel basis akan selalu sama dengan banyaknya baris fungsi pembatas

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Terminologi

• Solusi basis fisibel adalah solusi yang diperoleh berdasarkan nilai-nilai variabel basis.

• Solusi basis fisibel awal adalah solusi basis pada awal perhitungan (biasa disebut iterasi nol). Pada iterasi nol seluruh variabel keputusan asli dijadikan variabel non basis.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Terminologi

• Entering variable adalah variabel non-basis yang dijadikan variabel basis (memasuki status basis).

• Leaving variable adalah variabel basis yang dijadikan variabel non-basis (keluar dari status basis).

• Rasio ruas kanan adalah hasil bagi nilai ruas kanan setiap variabel basis dengan nilai koefisien kolom entering variable.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Algoritma Simplex

1. Formulasikan persoalan ke dalam bentuk standar dan masukkan data ke dalam Tabel Simplex (pindah ruaskan koefisien fungsi tujuan)

2. Tetapkan variabel basis awal dan solusi basis awal. Perhatikan setiap variabel basis harus membentuk matriks identitas.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Algoritma Simplex

3. Perhatikan koefisien fungsi tujuan.

Jika ada koefisien berharga:

negatif untuk persoalan maksimasi atau

positif untuk persoalan minimasi

maka tetapkan entering variable, yaitu variabel non-basis yang paling negatif (maks) atau paling positif (min) dan lanjutkan ke langkah 4.

Jika tidak ada entering variable, lanjutkan ke langkah 6.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Algoritma Simplex

4. Perhatikan ruas kanan. Tetapkan leaving variable berdasarkan nilai rasio ruas kanan positif terkecil (abaikan yang berharga nol atau negatif) dan lanjutkan ke langkah 5. Jika tidak ada leaving variable, lanjutkan ke langkah 7.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Algoritma Simplex

5. Lakukan operasi baris elementer. Kembali ke langkah 3

6. Perhitungan selesai, solusi optimal sudah diperoleh.

7. Perhitungan selesai, persoalan tidak mempunyai solusi karena ruang solusi bersifat unbounded.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Langkah Penyelesaian

Bentuk Standar:

Maks Z = 5 X1 + 14 X2 + 0 S1 + 0 S2

dengan pembatas:

X1 + 2 X2 + S1 = 6

X1 + 4 X2 + S2 = 8

X1 , X2 , S1 , S2 0

Var basis awal adalah?

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Tabel iterasi nol:

Basis X1 X2 S1 S2 Solusi

Z -5 -14 0 0 0

S1 1 2 1 0 6

S2 1 4 0 1 8

Solusi basis awal: ; EV: ;LV:

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Tabel iterasi 1:

Basis X1 X2 S1 S2 Solusi

Z

S1

X2

EV: ;LV:

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Tabel iterasi 2:

Basis X1 X2 S1 S2 Solusi

Z

X1

X2

EV: ;LV:

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Catatan:

1. Syarat fisibel suatu persoalan LP adalah seluruh nilai ruas kanan berharga positif atau nol

2. Syarat optimal suatu persoalan LP adalah apabila seluruh koefisien fungsi tujuan berharga:

Positif atau nol, jika persoalannya maksimasi

Negatif atau nol, jika persoalannya

minimasi

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Kasus-kasus khusus Persoalan LP

Pada umumnya persoalan LP akan mempunyai satu solusi optimal. Tetapi pada kondisi tertentu bisa terjadi kasus khusus, seperti:

1. Tidak mempunyai solusi fisibel, yaitu apabila ruas kanan tidak memenuhi syarat fisibel. Pada metode grafis ditandai dengan tidak ada daerah fisibel.

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

2. Mempunyai solusi alternatif, yaitu apabila ada koefisien fungsi tujuan dari variabel non-basis yang berharga nol. Pada metode grafis ditandai dengan adanya garis fungsi pembatas yang sejajar dengan garis fungsi tujuan.

Kasus-kasus khusus Persoalan LP

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

3. Unbounded, terjadi pada persoalan maksimasi dan ditandai dengan ada entering variable tetapi tidak ada leaving variable. Pada metode grafis ditandai dengan tidak adanya batas dari daerah fisibel.

4. Degenerasi, ditandai dengan adanya variabel basis yang nilai ruas kanannya berharga nol.

Kasus-kasus khusus Persoalan LP