Maximize or Minimize Z = f (x,y) Subject to: g (x,y) = c BV
CV
M
K
S1
S2
S1
60
4
2
1
0
S2
48
2
4
0
1
Zj
0
-8
-6
0
0
Rasio
PENYELESAIAN MODEL LINEAR PROGRAMMING SECARA MATEMATIK (METODE SIMPLEKS) Prof. Dr. Ir. ZULKIFLI ALAMSYAH, M.Sc.
PROGRAM STUDI AGRIBISNIS
FAKULTAS PERTANIAN UNIVERSITAS JAMBI
Metode Simpleks adlh suatu metode yg secara matematis dimulai dari suatu pemecahan dasar yg feasibel (basic feasible solution) ke pemecahan dasar feasibel lainnya dan dilakukan secara berulangulang (iteratif) sehingga akhirnya diperoleh suatu pemecahan dasar yang optimum. Langkah 1:
Ubah model LP kedalam bentuk kanoniknya, semua fungsi kendala berupa persamaan, dg cara menambahkan slack variabel Setiap fungsi kendala mempunyai slack variabel. ⇒ jumlah slack variable = jumlah fungsi kendala Nilai sebelah kanan (right-hand side) semua kendala tidak boleh negatif. Magister Agribisnis UNJA
2
Zulkifli Alamsyah
Perhatikan kembali persoalan sebagai berikut Proses Perakitan Pemolesan Laba/unit
Waktu yang dibutuhkan per unit Meja Kursi 4 2 2 4 80.000 60.000
(Kuliah ke-2): Total jam tersedia 60 48
Model Linear Programming: Maks.: Laba = 8 M + 6 K Dengan kendala: 4M + 2K ≤ 60 2M + 4K ≤ 48 M ≥ 0 K ≥ 0 Magister Agribisnis UNJA
(dlm satuan Rp.10. 000)
3
Zulkifli Alamsyah
Fungsi Kendala diubah menjadi bentuk persamaan: 4M + 2K + S1 = 60 2M + 4K + S2 = 48
atau S1 = 60 – 4M – 2K atau S2 = 48 – 2M – 4K
S1 adalah variabel slack (waktu tak terpakai) dalam perakitan S2 adalah variabel slack (waktu tak terpakai) dalam pemolesan Semua variabel yang tdk mempengaruhi kesamaan ditulis dg koefisien nol.
Model Iconic : Maks Dg kendala:
Laba = 8M + 6K + 0S1 + 0S2 4M + 2K + S1 + 0S2 = 60 2M + 4K + 0S1 + S2 = 48 M ≥ 0; K ≥ 0
Variabel dibagi menjadi non-basic variables dan basic variables. Non-basic variables ⇒ variabel yg tdk keluar sbg sulusi pd setiap iterasi, nilainya sama dg nol. basic variables ⇒ variabel yg keluar sbg sulusi pd setiap iterasi Magister Agribisnis UNJA
4
Zulkifli Alamsyah
Langkah 2: Membuat tabel simpleks awal
Elemen pivot BV
CV
M
K
S1
S2
Rasio
Baris-1
S1
60
4
2
1
0
60/4
Baris-2
S2
48
2
4
0
1
48/2
Baris-3
Zj
0
-8
-6
0
0
Persamaan pivot
Langkah 3:
Penentuan baris dan kolom kunci sebagai dasar iterasi. Kolom kunci ditentukan oleh nilai baris Z negatif terbesar, yaitu pada kolom M Hitung rasio antara CV dan nilai pada Kolom kunci Baris kunci ditentukan dari rasio CV/ nilai Kolom kunci terkecil, yaitu baris S1.
Langkah 4: Iterasi
Variabel yang masuk sbg basic variable (BV) adlh M dan variabel yang keluar dari BV adalah S1. M masuk pada kolom BV menggantikan S1 (baris-1).
Magister Agribisnis UNJA
5
Zulkifli Alamsyah
Iterasi : Untuk melakukan iterasi, digunakan metode perhitungan Gauss-Jordan sbb: Elemen pivot BV
CV
M
K
S1
S2
Rasio
Baris-1
S1
60
4
2
1
0
60/4
Baris-2
S2
48
2
4
0
1
48/2
Baris-3
Zj
0
-8
-6
0
0
Persamaan pivot
Persamaan Pivot (baris-1): Persamaan pivot baru = Persamaan pivot lama : elemen pivot BV
CV
M
K
S1
S2
Lama
S1
60
4
2
1
0
Baru
M
60/4
4/4
2/4
1/4
0
Rasio
Persamaan lainnya, termasuk Z: Persamaan baru = (Persamaan lama) – (persamaan pivot baru) x (Koef kolom masuk) Magister Agribisnis UNJA
6
Zulkifli Alamsyah
Iterasi
(lanjutan)…….:
Untuk Baris-2 BV
CV
M
K
S1
S2
Lama
S2
48
2
4
0
1
Pers pivot Baru
M
15
1
1/2
1/4
0
Baru
S2
48-15.2 = 18
2-1.2 =0
4-(1/2).2 =3
0-(1/4).2 = -1/2
1-0.2 =1
Rasio
-
x2
Untuk Baris-3 : FT BV
CV
M
K
S1
S2
Lama
Zj
0
-8
-6
0
0
Pers pivot Baru
M
15
1
1/2
1/4
0
Baru
Zj
0-15.(-8) = 120
-8-1.(-8) =0
-6-(1/2). (-8) = -2
0-(1/4). (-8) = 2
1-0.-8 =0
Hasil Iterasi:
Magister Agribisnis UNJA
BV
CV
M
K
S1
S2
M
15
1
1/2
1/4
0
S2
18
0
3
-1/2
1
Zj
120
0
-2
2
0
7
Rasio
-
x -8
Rasio
Zulkifli Alamsyah
Iterasi
(lanjutan)…….:
Hasil Iterasi 1: BV
CV
M
K
S1
S2
M
15
1
1/2
1/4
0
S2
18
0
3
–1/2
1
Zj
120
0
–2
2
0
Rasio
Kriteria Solusi Optimal:
Semua nilai pada baris Zj tidak ada yang negatif. Pada hasil iterasi 1, masih ada nilai pada baris Zj yang bernilai negatif, yaitu variabel K dengan nilai –2. Oleh karen itu, solusi belum optimal dan perlu dilakukan iterasi kembali. Ikuti langkah-langkah iterasi sebelumnya: Tentukan kolom dan baris kunci Hitung rasio CV/Nilai pada kolom kunci Tentukan persamaan pivot. Lakukan iterasi Magister Agribisnis UNJA
8
Zulkifli Alamsyah
Hasil iterasi 2: Solusi Optimal BV
CV
M
K
S1
S2
M
12
1
0
1/3
-1/6
K
6
0
1
-1/6
1/3
Z
132
0
0
5/3
2/3
Reduced costs
Rasio
Dual Prices
Karena nilai-nilai pada baris Zj sudah non-negatif, berarti iterasi selesai, dan solusi yang diperoleh adalah: M = 12, K = 6 dan Z (laba) = 132. Dari tabel akhir iterasi diatas juga diperoleh informasi mengenai nilai Reduced Costs dan Dual (shadow) prices. Selain itu, dgn sedikit perhitungan juga dapat dilakukan analisis sensitivitas. Magister Agribisnis UNJA
9
Zulkifli Alamsyah
Penjelasan Reduced Cost dan Dual Price Reduced Cost Berkaitan dengan variabel keputusan, yaitu nilai pada kolom
variabel keputusan pada baris Z dalam tabel simpleks akhir. Bila suatu variable keluar sebagai solusi optimal maka nilai
Reduced Cost adalah nol (RC = 0); sebaliknya, bila tidak keluar sebagai solusi maka nilai Reduced Cost lebih besar dari nol (RC > 0) untuk persoalan maksimisasi dan RC < 0 untuk persoalan minimisasi. Jika RC suatu variabel adalah x, berarti pemaksaan variabel
tersebut masuk sebagai solusi akan menurunkan (pada persoalan maksimisasi) atau meningkatkan (pada persoalan minimisasi) nilai fungsi tujuan sebesar x. Magister Agribisnis UNJA
10
Zulkifli Alamsyah
Dual (Shadow) Price: Berkaitan dengan kendala, yaitu nilai pada kolum slack variabel
pada baris Z dalam tabel simpleks akhir. Bila
sumberdaya pada suatu kendala tidak habis terpakai berdasarkan solusi optimal, berarti sumberdaya tersebut bukan pembatas dalam aktivitas ekonomi. Oleh karena itu, nilai dual (shadow) untuk sumberdaya tersebut adalah nol (SP = 0).
Bila sumberdaya pada suatu kendala habis terpakai berdasarkan
solusi optimal, berarti sumberdaya tersebut merupakan pembatas dalam aktivitas ekonomi. Oleh karena itu, nilai dual (shadow) untuk sumberdaya tersebut lebih besar dari nol (SP > 0). Artinya nilai sumberdaya pada aktivitas tersebut sama dengan nilai shadow price. Jika
ketersediaan sumberdaya pada kendala yang bersangkutan ditambah 1 (satu) unit, maka nilai fungsi tujuan akan meningkat sebesar nilai shadow price sumberdaya.
Magister Agribisnis UNJA
11
Zulkifli Alamsyah
Latihan 7: Carilah solusi persoalan berikut menggunakan metode simpleks. (1) max Z = 6 X1 + 5 X2 st X1 + X2 ≤ 10 2 X1 + 3 X2 ≤ 24 3 X1 + 5 X2 ≤ 42 X1, X2 ≥ 0 (2)
Magister Agribisnis UNJA
max Z = 3 X1 + 4 X2 st X1 + 2 X2 ≤ 18 3 X1 + 2 X2 ≤ 24 2 X1 + 5 X2 ≤ 40 X1, X2 ≥ 0 12
Zulkifli Alamsyah
