modul 4 - linear programming, metode simpleks.pptx
TRANSCRIPT
EKMA4413 – Riset Op-erasiProgram Studi Manaje-menOleh: M. Mujiya Ulkhaq
Raja Ampat, Papua Barat
Modul 4
Seoul, 9th of March 2014
2
Tinjauan Umum Modul 4
Secara umum, Modul 4 akan membahas mengenai penentuan alokasi sumber daya yang jumlahnya terbatas secara optimal dengan menggunakan linear programming: metode simpleks.
Modul 4 terdiri dari dua kegiatan belajar:• Kegiatan Belajar 1 – Pemecahan Masalah yang Formulasinya Berbentuk Standar dengan Metode Simpleks• Kegiatan Belajar 2 – Analisis Sensitivitas
Setelah mempelajari Modul 4, diharapkan mampu memecahkan masalah linear programming yang memi-liki variabel lebih dari dua dan lebih kompleks.
Secara khusus, setelah mempelajari Modul 4, diharapkan mampu:• Memecahkan masalah linear programming yang memiliki variabel lebih dari dua macam;• Memecahkan masalah dengan menggunakan tabel dan rumus-rumus dalam metode simpleks.
3
Pemecahan MasalahPemecahan masalah dari programma linier dapat diselesaikan dengan dua metode: metode visual (grafik) dan metode simpleks. Metode grafik sudah dibahas pada Modul 3 sedang metode simpleks akan dibahas pada Modul 4.
Kelebihan metode simpleks adalah dapat diimplementasikan pada masalah dengan variabel keputusan lebih dari tiga, di mana metode visual (grafik) tidak mampu untuk menyelesaikannya.
Kekurangannya adalah metode ini lebih rumit dalam implementasi dan perhitungan dibandingkan dengan metode visual (grafik).
4
Formulasi MasalahSebelum memulai pemograman dengan programma linier, maka kita harus merumuskan kasus atau masalah yang akan diselesaikan, tentu saja dalam persamaan-persamaan linier. Ada dua macam model per-samaan:
1. Fungsi tujuan (objektif), yang sifatnya menimimalkan atau memaksimalkan.
2. Fungsi pembatas (konstrain), yang merupakan batasan fungsional terhadap jumlah sumber daya yang terbatas.
Simbol-simbol konvensional yang dipakai:
i : Nomor (indeks) sumber daya;
j : Nomor (indeks) aktivitas;
m : Banyaknya macam sumber daya;
n : Banyaknya macam aktivitas;
aij : Kebutuhan setiap unit aktivitas j akan sumber daya i;
bi : Banyaknya sumber daya i yang tersedia;
cj : Manfaat yang diperoleh untuk setiap unit aktivitas j;
Xj : Ukuran (unit) aktivitas;
Z : Jumlah nilai yang akan dituju (maksimasi atau minimasi).
5
Formulasi MasalahIlustrasi 1:
6
Formulasi Masalah1. Fungsi Tujuan
Fungsi ini menunjukkan tujuan yang akan dioptimalkan: maksimasi atau minimasi.
Simbol yang digunakan adalah Z.
Bentuk umum:
X merupakan variabel keputusan: apa atau siapa yang akan dioptimalkan. Dari ilustrasi 1, yang akan dioptimalkan adalah jumlah produk 1 dan 2 yang akan diproduksi, maka, n = 2.
Untuk ilustrasi 1, fungsi tujuannya adalah:
Maksimasi Z – (c1X1 + c2X2) = 0
Z – 3X1 – 4X2 = 0
0
0
2211
1
nn
n
jjj
XcXcXcZ
XcZ
7
Formulasi Masalah2. Fungsi Pembatas
a. Pembatas Fungsional (Sumber Daya)
Fungsi ini menunjukkan alokasi sumber daya yang tersedia. Apabila setiap unit aktivitas j memerlukan a unit sumber daya i, maka bentuk umum pertidaksamaan fungsi pembatas fungsional adalah:
Untuk ilustrasi 1, fungsi pembatas fungsionalnya adalah:
Subject to 2X1 + 1X2 + S1= 6.000
2X1 + 3X2 + S2= 9.000
11
11 bXaSn
jjj
111212111 bSXaXaXa nn
21
22 bXaSn
jjj
m
n
jjmjm bXaS
1
222222121 bSXaXaXa nn
mnmnmm bSXaXaXa 32211
S merupakan slack variabelyang berfungsi untuk “menampung”perbedaan antara sisi kanan dan kiridiakibatkan berubahnya tanda ≤ atau ≥ menjadi =.
8
Formulasi Masalah2. Fungsi Pembatas
b. Pembatas Tanda
Fungsi ini menunjukkan bahwa variabel keputusan (Xj) tidak boleh bernilai tertentu. Biasanya, dalam kasus programma linier sederhana, variabel keputusan tidak boleh bernilai negatif (lebih besar atau sama dengan nol).
Bentuk umum:
Untuk ilustrasi 1, fungsi pembatas tandanya adalah:
X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0
0;;0;0
0;;0;0
21
21
n
n
SSS
XXX
9
Formulasi MasalahFormulasi masalah secara lengkap dari Ilustrasi 1 adalah:
Maksimasi Z – 3X1 – 4X2 = 0
Subject to (1) 2X1 + 1X2 + S1= 6.000
(2) 2X1 + 3X2 + S2= 9.000
(3) X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0
10
Metode Simpleks – Maksimasi
1. Masukkan formulasi masalah ke dalam tabel simpleks
Bentuk umum dari tabel simpleks:
Tabel simpleks dari ilustrasi 1 adalah:
V.D. merupakan variabel dasar (variabel basis)N.K. merupakan nilai dari sisi kanan dari tiap persamaan
V.D. Z X1 X2 S1 S2 N.K.
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000Variabel dasar
Variabel dasar dalam baris Z harus bernilai 0
11
Metode Simpleks – Maksimasi
2. Pilih “kolom kunci” yang merupakan kolom dengan nilai Z yang paling kecil (negatif terkecil)
Kolom kunci dari ilustrasi 1 iterasi 1 adalah:
3. Pilih “baris kunci” yang merupakan baris dengan nilai positif terkecil
Baris S1 = 6.000 / 1 = 6.000
Baris S2 = 9.000 / 3 = 3.000 → positif terkecil
Baris kunci dari ilustrasi 1 iterasi 1 adalah:
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
12
Metode Simpleks – Maksimasi
4. Ubah nilai dari “baris kunci” dengan membaginya dengan nilai dari “kolom kunci”.
Kemudian Variabel Dasar (V.D.) juga diubah menjadi Variabel Dasar dari “kolom kunci”
Untuk “baris nonkunci”, ubah nilainya sebagai berikut:
Nilai baru = nilai lama – (nilai baris yang bersesuaian pada “kolom kunci” × nilai “baris kunci” baru)
Iterasi 2
Z pada kolom X1 = –3 – (–4 × 2/3) = –1/3 S1 pada kolom X1 = 2 – (1 × 2/3) = 4/3
Z pada kolom S1 = 0 – (–4 × 0) = 0 S1 pada kolom S1 = 1 – (1 × 0) = 1
Z pada kolom S2 = 0 – (–4 × 1/3) = 4/3 S1 pada kolom S2 = 0 – (1 × 1/3) = –1/3
Z pada kolom N.K. = 0 – (–4 × 3.000) = 12.000 S1 pada kolom N.K. = 6.000 – (1 × 3.000) = 3.000
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
II
Z 1 –1/3 0 0 4/3 12.000
S1 0 4/3 0 1 –1/3 3.000
X2 0 2/3 1 0 1/3 3.000
Semua nilai pada kolom kunci bernilai 0 kecuali yang terletak pada baris kunci
13
Metode Simpleks – Maksimasi
5. Pilih “kolom kunci” yang merupakan kolom dengan nilai Z yang paling kecil (negatif terkecil)
Pilih “baris kunci” yang merupakan baris dengan nilai positif terkecil
Baris S1 = 3.000 / 4/3 = 2.250 → positif terkecil
Baris X2 = 3.000 / 2/3 = 4.500
Kolom dan baris kunci dari ilustrasi 1 iterasi 2 adalah:
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
II
Z 1 –1/3 0 0 4/3 12.000
S1 0 4/3 0 1 –1/3 3.000
X2 0 2/3 1 0 1/3 3.000
14
Metode Simpleks – Maksimasi
6. Ubah nilai dari “baris kunci” dengan membaginya dengan nilai dari “kolom kunci”.
Kemudian Variabel Dasar (V.D.) juga diubah menjadi Variabel Dasar dari “kolom kunci”
Untuk “baris nonkunci”, ubah nilainya sebagai berikut:
Nilai baru = nilai lama – (nilai baris yang bersesuaian pada “kolom kunci” × nilai “baris kunci” baru)
Iterasi 3
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
II
Z 1 –1/3 0 0 4/3 12.000
S1 0 4/3 0 1 –1/3 3.000
X2 0 2/3 1 0 1/3 3.000
III
Z 1 0 0 1/4 5/4 12.750
X1 0 1 0 3/4 –1/4 2.250
X2 0 0 1 –1/2 1/2 1.500
15
Metode Simpleks – Maksimasi
7. Pemeriksaan hasil akhir.
Karena pada iterasi terakhir tidak ada nilai Z yang bernilai negatif, maka nilai yang optimal telah diperoleh.
V.D. Z X1 X2 S1 S2 N.K.
I
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
II
Z 1 –1/3 0 0 4/3 12.000
S1 0 4/3 0 1 –1/3 3.000
X2 0 2/3 1 0 1/3 3.000
III
Z 1 0 0 1/4 5/4 12.750
X1 0 1 0 3/4 –1/4 2.250
X2 0 0 1 –1/2 1/2 1.500
Variabel keputusanyang terpilih
Nilai variabel keputu-san:X1 = 2.250;X2 = 1.500
Nilai akhirZ = 12.750
16
Informasi Tambahan1. Pada pemilihan “kolom kunci” terdapat dua atau lebih nilai negatif terkecil (pada maksimasi) atau
positif terbesar (pada minimasi) di baris Z.
Silakan pilih salah satu sesuai selera karena hasilnya akan sama saja (apabila benar dalam pengerjaan).
2. Pada pemilihan “baris kunci” terdapat dua atau lebih nilai positif terkecil.
Silakan pilih salah satu sesuai selera karena hasilnya akan sama saja (apabila benar dalam pengerjaan).
3. Terdapat lebih dari satu alternatif penyelesaian (mempunyai nilai Z yang sama namun variabel keputu-san yang terpilih berbeda).
Pada dasarnya, alternatif-alternatif tersebut adalah sama, karena mempunyai hasil (nilai Z) yang sama, namun dalam praktiknya, terkadang alternatif yang lebih “practical” yang harus dipilih.
17
“Penyimpangan”1. Fungsi tujuan Minimasi
Ketika fungsi tujuan dari programma linier adalah minimasi, maka terdapat dua cara penyelesaian: mengubah ke bentuk maksimasi atau tetap menggunakan bentuk minimasi dengan cara pengejaan yang sedikit berbeda dengan maksimasi. Namun dalam Modul ini hanya dibahas cara yang pertama. Untuk mengganti bentuk minimasi menjadi maksimasi adalah dengan mengalikan –1.
Contoh:
Minimasi Z = 3X1 + 4X2 Maksimasi –Z = –3X1 – 4X2
–Z + 3X1 + 4X2 = 0
Tabel simpleks-nya adalah:
Ingat bahwa setelah iterasi terakhir, N.K. yang diperoleh harus dikali –1 karena koefisien dari Z adalah –1 (lihat Tabel Simpleks).
V.D. Z X1 X2 … … N.K.
Z –1 3 4 … … 0
… … … … … … …
… … … … … … …
18
“Penyimpangan”2. Pembatas fungsional bertanda “=”
Ketika suatu permasalahan dalam programma linier ada pembatas fungsional yang bertanda = (sama dengan), maka kondisi ini akan menyulitkan dalam penyelesaiannya, karena matriks identitas yang akan dijadikan solusi dasar awal tidak akan ditemui. Cara penyelesaiannya adalah dengan menam-bahkan variabel artifisial R ke dalam formulasi pembatas fungsional di mana nilai dari variabel arti-fisial ini harus nol. Metode yang digunakan dalam penyelesaian masalah dengan kondisi ini ada dua: Metode Dua Fasa dan Metode Big M. Namun dalam Modul ini hanya dibahas Metode Big M.
Metode Big M merupakan metode untuk mengeliminasi variabel artifisial dengan memberikan nilai positif yang sangat besar (M) pada fungsi tujuan (untuk maksimasi bertanda negatif; untuk minimasi bertanda positif).
Contoh:
Maksimasi Z = 3X1 + 4X2 Maksimasi Z – 3X1 – 4X2 + MR1 = 0
Subject to (1) 2X1 + X2 = 6.000 Subject to (1) 2X1 + X2 + R1 = 6.000
(2) 2X1 + 3X2 ≤ 9000 (2) 2X1 + 3X2 + S2 = 9000
(3) X1 ≥ 0; X2 ≥ 0 (3) X1 ≥ 0; X2 ≥ 0; S2 ≥ 0
Z = 3X1 + 4X2 – MR1
19
“Penyimpangan”2. Pembatas fungsional bertanda “=”
Tabel simpleks dari contoh tersebut adalah:
Ingat bahwa nilai V.D. (Variabel Dasar) pada baris Z harus 0, namun dalam tabel di atas, nilai R1 adalah M, maka agar nilai R1 sebesar 0, baris Z nilainya harus diubah sedemikian rupa (ingat metode eliminasi dalam pemecahan masalah linier):
Baris pertama (Z) dikurangi M kali baris kedua (R1):
–3X1 – 4X2 + MR1 + 0S2 = 0
2MX1 + MX2 + MR1 + 0S2 = 6.000M
(–3–2M)X1 + (–4–M)X2 = – 6.000M
V.D. Z X1 X2 R1 S2 N.K.
Z 1 –3 –4 M 0 0
R1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
V.D. Z X1 X2 R1 S2 N.K.
Z 1 –3–2M –4–M 0 0 – 6.000M
R1 0 2 1 1 0 6.000
S2 0 2 3 0 1 9.000
20
“Penyimpangan”3. Pembatas fungsional bertanda “≥”
Ketika suatu permasalahan dalam programma linier ada pembatas fungsional yang bertanda ≥ (lebih besar atau sama dengan), maka penyelesaiannya dengan menambahkan variabel slack dengan tanda negatif.
Contoh:
Maksimasi Z = 3X1 + 4X2 Maksimasi Z – 3X1 – 4X2 = 0
Subject to (1) 2X1 + X2 ≤ 6.000 Subject to (1) 2X1 + X2 + S1 = 6.000
(2) 2X1 + 3X2 ≥ 9000 (2) 2X1 + 3X2 – S2 = 9000
(3) X1 ≥ 0; X2 ≥ 0 (3) X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0
Tabel simpleks dari contoh tersebut adalah:V.D. Z X1 X2 S1 S2 N.K.
Z 1 –3 –4 0 0 0
S1 0 2 1 1 0 6.000
–S2 0 2 3 0 1 9.000
Melanggar pembatas tanda S2 ≥ 0
21
“Penyimpangan”3. Pembatas fungsional bertanda “≥”
Karena variabel dasar melanggar aturan pembatas tanda, maka variabel artifisial R dapat dimasukkan ke dalam persamaan. Karena R masuk ke dalam persamaan, sehingga Metode Big M dipakai untuk menyelesaikan masalah. Maka, dalam fungsi tujuan juga harus ditambahkan M (untuk maksimasi bertanda negatif; untuk minimasi bertanda positif).
Maksimasi Z – 3X1 – 4X2 = 0 Z – 3X1 – 4X2 + MR2 = 0
Subject to (1) 2X1 + X2 + S1 = 6.000 2X1 + X2 + S1 = 6.000
(2) 2X1 + 3X2 – S2 = 9000 2X1 + 3X2 – S2 + R2 = 9000
(3) X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0 X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0
Tabel simpleks dari contoh tersebut adalah:
V.D. Z X1 X2 S1 S2 R2 N.K.
Z 1 –3 –4 0 0 M 0
S1 0 2 1 1 0 0 6.000
R2 0 2 3 0 –1 1 9.000
22
“Penyimpangan”3. Pembatas fungsional bertanda “≥”
Ingat bahwa nilai V.D. (Variabel Dasar) pada baris Z harus 0, namun dalam tabel di atas, nilai R2 adalah M, maka agar nilai R2 sebesar 0, baris Z nilainya harus diubah sedemikian rupa (ingat metode eliminasi dalam pemecahan masalah linier):
Baris pertama (Z) dikurangi M kali baris ketiga (R2):
–3X1 – 4X2 + 0S1 + 0S2 + MR2 = 0
2MX1 + 3MX2 + 0S1 – MS2 + MR2= 9.000M
(–3–2M)X1 + (–4–3M)X2 + MS2 = – 9.000M
V.D. Z X1 X2 S1 S2 R2 N.K.
Z 1 –3 –4 0 0 M 0
S1 0 2 1 1 0 0 6.000
R2 0 2 3 0 –1 1 9.000
V.D. Z X1 X2 S1 S2 R2 N.K.
Z 1 –3–2M –4–3M 0 M 0 – 9.000M
S1 0 2 1 1 0 0 6.000
R2 0 2 3 0 –1 1 9.000
23
“Penyimpangan”Contoh penyelesaian masalah untuk beberapa penyimpangan tersebut:
Minimasi Z = 5X1 + 2X2
Subject to (1) 2X1 + X2 = 6.000
(2) 2X1 + 3X2 ≥ 9000
(3) X1 + X2 ≤ 4000
(4) X1 ≥ 0; X2 ≥ 0
Ubah formulasi masalah di atas menjadi bentuk standar dengan mengubah ke bentuk maksimasi (menga-likan – 1) serta menambahkan variabel slack dan artifisial.
Maksimasi –Z + 5X1 + 2X2 + MR1 + MR2 = 0
Subject to (1) 2X1 + X2 + R1 = 6.000
(2) 2X1 + 3X2 – S2 + R2 = 9000
(3) X1 + X2 + S3 = 4000
(4) X1 ≥ 0; X2 ≥ 0; S1 ≥ 0; S2 ≥ 0; S3 ≥ 0
24
“Penyimpangan”1. Masukkan formulasi masalah ke dalam tabel simpleks
Baris pertama (Z) ditambah M kali baris pertama (R1) dan ditambah M kali baris ketiga (R2)
5X1 + 2X2 + MR1 + 0S2 + MR2 + 0S3 = 0
2MX1 + MX2 + MR1 + 0S2 + 0R2 + 0S3= 6.000M
2MX1 + 3MX2 + 0R1 – MS2 + MR2 + 0S3= 9.000M
(5–4M)X1 + (2–4M)X2 + MS2 = –15.000M
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
Z –1 5 2 M 0 M 0 0
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
25
“Penyimpangan”2. Pilih “kolom kunci” yang merupakan kolom dengan nilai Z yang paling kecil (negatif terkecil)
Karena X1 dan X2 sama-sama bernilai negatif terkecil, maka dipilih salah satu, yaitu X2.
3. Pilih “baris kunci” yang merupakan baris dengan nilai positif terkecil
Kolom kunci dan baris kunci iterasi 1 adalah:
Baris R1 = 6.000 / 1 = 6.000
Baris R2 = 9.000 / 3 = 3.000 → positif terkecil
Baris S3 = 4.000 / 1 = 4.000
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
26
“Penyimpangan”4. Ubah nilai dari “baris kunci” dengan membaginya dengan nilai dari “kolom kunci”.
Kemudian Variabel Dasar (V.D.) juga diubah menjadi Variabel Dasar dari “kolom kunci”
Untuk “baris nonkunci”, ubah nilainya sebagai berikut:
Nilai baru = nilai lama – (nilai baris yang bersesuaian pada “kolom kunci” × nilai “baris kunci” baru)
Iterasi 2
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
II
Z –1 11/3–4/3M 0 0 2/3–1/3M 4/3M–2/3 0 –6.000–3.000M
R1 0 4/3 0 1 1/3 –1/3 0 3.000
X2 0 2/3 1 0 –1/3 1/3 0 3.000
S3 0 1/3 0 0 1/3 –1/3 1 1.000
27
“Penyimpangan”5. Pilih “kolom kunci” yang merupakan kolom dengan nilai Z yang paling kecil (negatif terkecil)
6. Pilih “baris kunci” yang merupakan baris dengan nilai positif terkecil
Kolom kunci dan baris kunci iterasi 2 adalah:
Baris R1 = 3.000 / 4/3 = 2.250 → positif terkecil
Baris X2 = 3.000 / 2/3 = 4.500
Baris S3 = 1.000 / 1/3 = 3.000
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
II
Z –1 11/3–4/3M 0 0 2/3–1/3M 4/3M–2/3 0 –6.000–3.000M
R1 0 4/3 0 1 1/3 –1/3 0 3.000
X2 0 2/3 1 0 –1/3 1/3 0 3.000
S3 0 1/3 0 0 1/3 –1/3 1 1.000
28
“Penyimpangan”7. Ubah nilai dari “baris kunci” dengan membaginya dengan nilai dari “kolom kunci”.
Iterasi 3
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
II
Z –1 11/3–4/3M 0 0 2/3–1/3M –2/3+4/3M 0 –6.000–3.000M
R1 0 4/3 0 1 1/3 –1/3 0 3.000
X2 0 2/3 1 0 –1/3 1/3 0 3.000
S3 0 1/3 0 0 1/3 –1/3 1 1.000
III
Z –1 0 0 –11/4+M –1/4 –1/4+M 0 –14.250
X1 0 1 0 3/4 1/4 –1/4 0 2.250
X2 0 0 1 –1/2 –1/2 1/2 0 1.500
S3 0 0 0 –1/4 1/4 –1/4 1 250
29
“Penyimpangan”8. Pilih “kolom kunci” yang merupakan kolom dengan nilai Z yang paling kecil (negatif terkecil)
9. Pilih “baris kunci” yang merupakan baris dengan nilai positif terkecil
Kolom kunci dan baris kunci iterasi 4 adalah:
Baris X1 = 2.250 / 1/4 = 9.000
Baris X2 = 1.500 / –1/2 = –3.000
Baris S3 = 250 / 1/4 = 1.000 → positif terkecil V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
II
Z –1 11/3–4/3M 0 0 2/3–1/3M –2/3+4/3M 0 –6.000–3.000M
R1 0 4/3 0 1 1/3 –1/3 0 3.000
X2 0 2/3 1 0 –1/3 1/3 0 3.000
S3 0 1/3 0 0 1/3 –1/3 1 1.000
III
Z –1 0 0 –11/4+M –1/4 –1/4+M 0 –14.250
X1 0 1 0 3/4 1/4 –1/4 0 2.250
X2 0 0 1 –1/2 –1/2 1/2 0 1.500
S3 0 0 0 –1/4 1/4 –1/4 1 250
30
“Penyimpangan”10. Ubah nilai dari “baris kunci” dengan membaginya dengan nilai dari “kolom kunci”.
Iterasi 4
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
I
Z –1 5–4M 2–4M 0 M 0 0 –15.000M
R1 0 2 1 1 0 0 0 6.000
R2 0 2 3 0 –1 1 0 9.000
S3 0 1 1 0 0 0 1 4.000
II
Z –1 11/3–4/3M 0 0 2/3–1/3M –2/3+4/3M 0 –6.000–3.000M
R1 0 4/3 0 1 1/3 –1/3 0 3.000
X2 0 2/3 1 0 –1/3 1/3 0 3.000
S3 0 1/3 0 0 1/3 –1/3 1 1.000
III
Z –1 0 0 –11/4+M –1/4 –1/4+M 0 –14.250
X1 0 1 0 3/4 1/4 –1/4 0 2.250
X2 0 0 1 –1/2 –1/2 1/2 0 1.500
S3 0 0 0 –1/4 1/4 –1/4 1 250
IV
Z –1 0 0 –3+M 0 –1/2+M 1 –14.000
X1 0 1 0 1 0 0 –1 2.000
X2 0 0 1 –1 0 0 2 2.000
S2 0 0 0 –1 1 –1 4 1.000
31
“Penyimpangan”11. Pemeriksaan hasil akhir
Karena pada iterasi terakhir tidak ada nilai Z yang bernilai negatif, maka nilai yang optimal telah diperoleh
V.D. Z X1 X2 R1 S2 R2 S3 N.K.
IV
Z –1 0 0 –3+M 0 –1/2+M 1 –14.000
X1 0 1 0 1 0 0 –1 2.000
X2 0 0 1 –1 0 0 2 2.000
S2 0 0 0 –1 1 –1 4 1.000
Variabel keputusanyang terpilih
Nilai akhir–Z = –14.000Z = 14.000
Nilai variabel keputu-san:X1 = 2.000;X2 = 2.000;S2 = 1.000
32
Analisis SensitivitasA. Marginal Value (Shadow Price)
Marginal Value pada Table Simpleks iterasi terakhir terdapat pada kolom Slack Variable.
Contoh:
Maksimasi Z = 3X1 + 4X2
Subject to (1) 2X1 + X2 ≤ 6.000
(2) 2X1 + 3X2 ≤ 9.000
(3) X1 ≥ 0; X2 ≥ 0
Tabel Simpleks iterasi terakhir (optimal) adalah:
S1 = 1/4, maka apabila nilai ruas kanan pada fungsi pembatas pertama ditambah 1 unit, maka nilai Z akan bertambah 1/4. Dan apabila nilai ruas kanan pada fungsi pembatas kedua ditambah 1 unit, maka nilai Z akan bertambah 5/4 (S2 = 5/4).
Iterasi V.D. Z X1 X2 S1 S2 N.K.
III
Z 1 0 0 1/4 5/4 12.750
X1 0 1 0 3/4 –1/4 2.250
X2 0 0 1 –1/2 1/2 1.500
33
Analisis SensitivitasB. Mencari Nilai Optimal Baru
Apabila terjadi perubahan nilai ruas kanan pada suatu pembatas, maka nilai optimal dapat diketahui tanpa mengulangi proses perhitungan.
Pada contoh sebelumnya, tabel simpleks iterasi terakhir adalah sebagai berikut:
Apabila fungsi pembatas yang pertama bertambah 100, maka:
Z baru = Z lama + koefisien S1 × 100 = 12.750 + 1/4(100) = 12.775
X1 baru = X1 lama + koefisien S1 × 100 = 2.250 + 3/4(100) = 2.325
X2 baru = X2 lama + koefisien S1 × 100 =1.500 – 1/2(100) = 1.450
Cek feasibilitas:
(1) 2X1 + X2 ≤ 6.000
(1) 2(2.325) + 1.450 ≤ 6.000 (OK)
Iterasi V.D. Z X1 X2 S1 S2 N.K.
III
Z 1 0 0 1/4 5/4 12.750
X1 0 1 0 3/4 –1/4 2.250
X2 0 0 1 –1/2 1/2 1.500
34
Analisis SensitivitasB. Mencari Nilai Optimal Baru
Cek feasibilitas
Seperti sudah disinggung sebelumnya, setiap penambahan atau pengurangan nilai ruas kanan pembatas fung-sional, maka harus dicek feasibilitasnya dengan memasukkan nilai yang baru ke fungsi pembatas yang baru, apabila tidak sesuai, maka hal tersebut tidak dapat dilakukan.
Mencari selang feasibilitas
Pembatas fungsional 1
(1) 2.250 + 3/4×Δ 1 ≥ 0; maka Δ ≥ –3.000 (sebagai batas bawah)
(2) 1.500 – 1/2×Δ 1 ≥ 0; maka Δ ≤ 3.000 (sebagai batas atas)
Sehingga –3.000 ≤ Δ 1 ≤ 3.000 adalah selang bagi penambahan nilai ruas kanan pembatas 1.
Artinya, nilai ruas kanan dari pembatas 1 tidak boleh bertambah lebih dari 3.000 atau berkurang lebih dari 3.000.
Pembatas fungsional 2
(1) 2.250 – 1/4×Δ 2 ≥ 0; maka Δ ≤ 9.000 (sebagai batas atas)
(2) 1.500 + 1/2×Δ 2 ≥ 0; maka Δ ≥ –3.000 (sebagai batas bawah)
Sehingga –3.000 ≤ Δ 2 ≤ 9.000 adalah selang bagi penambahan nilai ruas kanan pembatas 1.
Artinya, nilai ruas kanan dari pembatas 1 tidak boleh bertambah lebih dari 9.000 atau berkurang lebih dari 3.000.
35
Analisis SensitivitasB. Mencari Nilai Optimal Baru
Mencari selang feasibilitas
Pembatas fungsional 1: –3.000 ≤ Δ 1 ≤ 3.000
Pembatas fungsional 2: –3.000 ≤ Δ 2 ≤ 9.000
Apabila fungsi pembatas yang pertama bertambah 4.000, maka:
Z baru = Z lama + koefisien S1 × 100 = 12.750 + 1/4(4.000) = 13.750
X1 baru = X1 lama + koefisien S1 × 100 = 2.250 + 3/4(4.000) = 5.250
X2 baru = X2 lama + koefisien S1 × 100 =1.500 – 1/2(4.000) = –500
Cek feasibilitas:
(1) 2X1 + X2 ≤ 6.000
(1) 2(5.250) –500 ≥ 6.000 (Tidak OK);
Selain itu, nilai X2 ≤ 0 yang juga melanggar pembatas tanda: X2 ≥ 0
EKMA4413 – Riset Op-erasiProgram Studi Manaje-menOleh: M. Mujiya Ulkhaq
Raja Ampat, Papua Barat
Modul 4
Terima Kasih
감사합니다
Sampai Bertemu Lagi di Pertemuan Selanjutnya
Seoul, 9th of March 2014