6s-1 LP Metode Simpleks
Operations Management
OPERATIONS
RESEARCH
William J. Stevenson
8th edition
6s-2 LP Metode Simpleks
Kaidah dalam Metode Simpleks
Mengkonversi Pertidaksamaan (≤ dan ≥) menjadi
Persamaan (=)
Untuk mengkonversi pertidaksamaan (≤) menjadi
persamaan (=) dilakukan dengan cara menambahkan
variabel slack nonnegatif pada sisi kiri constraint.
Contohnya:
2X1 + 3X2 8
diubah menjadi 2X1 + 3X2 + S1 = 8, S1 ≥ 0
6s-3 LP Metode Simpleks
Untuk mengkonversi pertidaksamaan (≥)
menjadi persamaan (=) dilakukan dengan
cara mengurangi variabel surplus
nonnegatif pada sisi kiri constraint.
Contohnya:
2X1 + 3X2 ≥ 8
diubah menjadi
2X1 + 3X2 - Sp1 = 8, Sp1 ≥ 0
6s-4 LP Metode Simpleks
Untuk mengkonversi sisi kanan bernilai
negatif dilakukan dengan cara mengalikan
kedua sisi dengan - 1
Contohnya:
2X1 + 3X2 ≥ -8 diubah menjadi
2X1 + 3X2 - Sp1 = -8
kemudian kedua sisi dikalikan dengan -1
sehingga -2X1 - 3X2 + Sp1 = 8
6s-5 LP Metode Simpleks
Langkah-Langkah Metode Simpleks
Langkah 1: Mengubah fungsi tujuan dan batasan-batasan
Langkah 2: Menyusun Persamaan Dalam Tabel
Langkah 3: Memilih Kolom Kunci
Langkah 4: Memilih Baris Kunci (Untuk pemaksimalan pilih angka positif
terkecil. Untuk peminimalan pilih angka negatif terbesar)
Langkah 5: Mengubah Nilai-Nilai Pada Baris Kunci
Langkah 6: Mengubah Nilai-Nilai Baris Lainnya Selain Baris Kunci
Langkah 7: Mengulangi langkah 3 sampai langkah 6 (Fungsi Tujuan tidak
ada bernilai Negatif (pemaksimalan) atau Positif (peminimalan))
6s-6 LP Metode Simpleks
Merek I1 I2 Kapasitas
Mesin (X1) (X2) Maksimum
1 2 0 8
2 0 3 15
3 6 5 30
Sumbangan laba 3 5
Maksimumkan Z = 3X1 + 5X2
Batasan (constrain)
(1) 2X1 8
(2) 3X2 15
(3) 6X1 + 5X2 30
6s-7 LP Metode Simpleks
LINEAR PROGRAMMING
METODE SIMPLEKS
Langkah-langkah metode simpleks
Langkah 1:
Mengubah fungsi tujuan dan batasan-batasan
Fungsi batasan (merubah pertidaksamaan menjadi kesamaan dengan cara
menambah slack variabel)
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
Fungsi tujuan
Z = 3X1 + 5X2 diubah menjadi Z = 3X1 + 5X2 + 0S1 + 0S2 + 0S3.
Kemudian Fungsi tujuan di nolkan sehingga
Z - 3X1 - 5X2 - 0S1 - 0S2 - 0S3 = 0
6s-8 LP Metode Simpleks
Langkah 2:
Menyusun persamaan-persamaan di dalam tabel
Beberapa Istilah dlm Metode Simplek
NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama
dengan ( = ). Untuk batasan 1 sebesar 8, batasan 2 sebesar 15, dan
batasan 3 sebesar 30.
Variabel dasar adalah variabel yang nilainya sama dengan sisi
kanan dari persamaan. Pada persamaan 2X1 + S1 = 8, kalau belum
ada kegiatan apa-apa, berarti nilai X1 = 0, dan semua kapasitas
masih menganggur, maka pengangguran ada 8 satuan, atau nilai S1
= 8.
Fungsi tujuan pada tabel permulaan ini harus 0, dan nilainya pada
batasan-batasan bertanda positif
6s-9 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 - 0S2 - 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel
Dasar Z X1 X2 S1 S2 S3 NK
Z
S1
S2
S3
6s-10 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 - 0S2 - 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1
S1 0
S2 0
S3 0
6s-11 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 – 0S2 – 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0
S2 0
S3 0
6s-12 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 + 0S2 + 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0
S3 0
6s-13 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 + 0S2 + 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0
6s-14 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 + 0S2 + 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30
6s-15 LP Metode Simpleks
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 - 0S1 + 0S2 + 0S3 = 0.
(1) 2X1 8 menjadi 2X1 + S1 = 8
(2) 3X2 15 menjadi 3X2 + S2 = 15
(3) 6X1 + 5X2 30 menjadi 6X1 + 5X2 + S3 = 30
1. Tabel simpleks yang pertama
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30
6s-16 LP Metode Simpleks
Langkah 3: Memilih kolom kunci
Kolom kunci adalah kolom yang mempunyai
nilai pada garis fungsi tujuan yang bernilai
negatif dengan angka terbesar.
6s-17 LP Metode Simpleks
3. Pemilihan kolom kunci pada tabel pertama
Variabel X1 X2 Keterangan
Z S1 S2 S3 NK (Indeks)
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30
Catatan: Jika pada fungsi tujuan (baris Z) tidak ada memiliki nilai
negatif, maka tabel itu tidak bisa dioptimalkan lagi (sudah optimal).
6s-18 LP Metode Simpleks
Langkah 4: Memilih baris kunci
Baris kunci adalah baris yang mempunyai
indeks positif dengan angka terkecil.
Indeks = Nilai Kolom (NK) / (Nilai kolom kunci)
Nilai yang masuk dalam kolom kunci dan juga
masuk dalam baris kunci disebut angka kunci
6s-19 LP Metode Simpleks
Variabel X1 X2 Keterangan
Z S1 S2 S3 NK (Indeks)
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
ANGKA KUNCI = 3
6s-20 LP Metode Simpleks
Langkah 5: Mengubah nilai-nilai baris kunci
Nilai baris kunci diubah dengan cara:
Semua angka yang ada dibaris kunci
dibagi dengan angka kunci, seperti tabel
3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 =
0; 1/3 = 1/3; 0/3 = 0; 15/3 = 5). Gantilah
variabel dasar pada baris itu dengan
variabel yang terdapat di bagian atas
kolom kunci (X2).
6s-21 LP Metode Simpleks
4. Cara mengubah nilai baris kunci
Variabel X1 X2 Keterangan
Z S1 S2 S3 NK
Dasar (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2
S2 0
S3 0
6s-22 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keterangan
Z S1 S2 S3 NK
Dasar (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0
S3 0
0/3
6s-23 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keterangan
Z S1 S2 S3 NK
Dasar (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1
S3 0
3/3
6s-24 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0
S3 0
0/3
6s-25 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0 1/3
S3 0
1/3
6s-26 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0 1/3 0
S3 0
0/3
6s-27 LP Metode Simpleks
3 Tabel simpleks: Cara mengubah nilai baris kunci
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0 1/3 0 5
S3 0
15/3
6s-28 LP Metode Simpleks
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0 1/3 0 5
S3 0
BARIS BARU KUNCI
6s-29 LP Metode Simpleks
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8 8/0 = ∞
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1
S1 0
X2 0 0 1 0 1/3 0 5
S3 0
6s-30 LP Metode Simpleks
Langkah 6: Mengubah nilai-nilai selain pada baris kunci
Rumusnya :
Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci
Variabel X1 X2 Keteranga
Z S1 S2 S3 NK
Dasar n (Indeks)
Z 1 -3 -5 0 0 0 0
S1 0 2 KOEFISIEN 0 1 0 0 8 8/0 = ∞
BARIS LAMA
S2 0 0 3 0 1 0 15 15/3 = 5
S3 0 6 5 0 0 1 30 30/5 = 6
Z 1 BARIS BARU
S1 0
X2 0 0 1 0 1/3 0 5
S3 0
BARIS BARU KUNCI
6s-31 LP Metode Simpleks
Perhitungan untuk fungsi tujuan (Z):
BARIS LAMA Z [ -3 -5 0 0 0, 0]
-5 X [ 0 1 0 1/3 0, 5] _
Nilai Baru = -3 0 0 5/3 0, 25 ]
-5 X 0 = 0 → -3 – 0 = -3
-5 X 1 = -5 → - 5 – (-5) = -5 + 5 = 0
-5 X 0 = 0 → 0 – 0 = 0
-5 X 1/3 = -5/3 → 0 – (-5/3) = 0 + 5/3 = 5/3
-5 X 0 = 0 → 0 – 0 = 0
-5 X 5 = -25 → 0 – (-25) = 0 + 25 = 25
6s-32 LP Metode Simpleks
Perhitungan untuk fungsi batasan pertama (S1) :
BARIS LAMA S1 [ 2 0 1 0 0, 8]
0 X [ 0 1 0 1/3 0, 5] _
Nilai Baru = 2 0 1 0 0, 8]
0X0=0→2–0=2
0X1=0→0–0= 0
0X0=0→1–0=1
0 X 1/3 = 0 → 0 – 0 = 0
0X0=0→0–0=0
0X5=0→8–0=8
6s-33 LP Metode Simpleks
Perhitungan untuk fungsi batasan ketiga (S3) :
BARIS LAMA S3 [ 6 5 0 0 1, 30 ]
5 X [ 0 1 0 1/3 0, 5] _
Nilai Baru = 6 0 0 -5/3 1, 5]
5X0=0→6–0=6
5X1=5→5–5= 0
5X0=0→0–0=0
5 X 1/3 = 5/3 → 0 – 5/3 = -5/3
5X0=0→1–0=1
5 X 5 = 25 → 30 – 25 = 5
6s-34 LP Metode Simpleks
Tabel pertama nilai lama dan tabel kedua nilai baru
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 -5 0 0 0 0
S1 0 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30
Z 1 -3 0 0 5/3 0 25
S1 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
S3 0 6 0 0 -5/3 1 5
Langkah 7: Lanjutkan perbaikan apabila baris Z masih
ada bernilai negatif
Caranya: Ulangilah langkah 3 sampai langkah ke-6. Perubahan baru berhenti
setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif
6s-35 LP Metode Simpleks
Variabel Keterangan
Z X1 X2 S1 S2 S3 NK
Dasar (Indeks)
Z 1 -3 0 0 5/3 0 25
S1 0 2 0 1 0 0 8 = 8/2 = 4
X2 0 0 1 0 1/3 0 5
S3 0 6 0 0 -5/3 1 5 = 5/6 (minimum)
Z 1
S1 0
X2 0
X1 0 1 0 0 -5/18 1/6 5/6
6/6 0/6 0/6
1/6 5/6
-5/3:6 = -5/3 X 1/6 = -5/18
6s-36 LP Metode Simpleks
Perhitungan untuk Baris Pertama (Z):
BARIS LAMA Z [ -3 0 0 5/3 0, 25 ]
-3 X [ 1 0 0 -5/18 1/6, 5/6 ] _
Nilai Baru = 0 0 0 5/6 1/2, 27,5 ]
-3 X 1 = -3 → -3 – (-3) = -3 + 3 = 0
-3 X 0 = 0 → 0 – 0 = 0
-3 X 0 = 0 → 0 – 0 = 0
-3 X -5/18 = 15/18 → 5/3 – 15/18 = 30/18 - 15/18 = 15/18 = 5/6
-3 X 1/6 = -3/6 → 0 – (-3/6) = 0 + 3/6 = 3/6 = 1/2
-3 X 5/6 = -15/6 → 25 – (-15/6) = 25 + 15/6 = 25 + 2,5 = 27,5
6s-37 LP Metode Simpleks
Perhitungannya untuk Baris Kedua (S1):
BARIS LAMA S1 [ 2 0 1 0 0, 8]
2 X [ 1 0 0 -5/18 1/6, 5/6 ] _
Nilai Baru = 0 0 1 5/9 -1/3, 19/3 ]
2X1=2→2–2=0
2X0=0→0–0=0
2X0=0→1–0=1
2 X -5/18 = -10/18 → 0 – (-10/18) = 0 + 10/18 = 10/18= 5/9
2 X 1/6 = 2/6 → 0 – 2/6 = -2/6 = -1/3
2 X 5/6 = 10/6 → 8 – 10/6 = 48/6 - 10/6 = 38/6 = 19/3
6s-38 LP Metode Simpleks
Perhitungannya untuk Baris ketiga (X2):
BARIS LAMA X2 [ 0 1 0 1/3 0, 5]
0 X [ 1 0 0 -5/18 1/6, 5/6 ] _
Nilai Baru = 0 1 0 1/3 0, 5]
0X1=0→0–0=0
0X0=0→1–0=1
0X0=0→0–0=0
0 X -5/18 = 0 → 1/3 – 0 = 1/3
0 X 1/6 = 0 → 0 – 0 = 0
0 X 5/6 = 0 → 5 – 0 = 5
6s-39 LP Metode Simpleks
Tabel pertama nilai lama dan tabel kedua nilai baru
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 -3 0 0 5/3 0 25
S1 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
S3 0 6 0 0 -5/3 1 5
Z 1 0 0 0 5/6 1/2 27,5
S1 0 0 0 1 5/9 -1/3 61/3
X2 0 0 1 0 1/3 0 5
X1 0 1 0 0 -5/18 1/6 5/6
Perbaikan tidak perlu dilakukan lagi karena angka di baris
Z sudah bernilai positif
6s-40 LP Metode Simpleks
Tabel simpleks final hasil perubahan
Variabel X1 X2
Z S1 S2 S3 NK
Dasar
Z 1 0 0 0 5/6 ½ 271/2
S1 0 0 0 1 5/9 -1/3 61/3
X2 0 0 1 0 1/3 0 5
X1 0 1 0 0 -5/18 1/6 5/6
Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak
dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal
Dari tabel final didapat
X1 = 5/6
X2 = 5
Zmaksimum = 271/2
6s-41 LP Metode Simpleks
Kasus Maksimisasi :
Model Program Linear
1. Fungsi Tujuan :
Maksimumkan : Z=8X1 + 6X2
(Dlm Rp1000)
2. Fungsi Pembatas :
Bahan A : 4X1 + 2X2 ≤ 60
Bahan B : 2X1 + 4X2 ≤ 48
X1, X2 ≥ 0