Model umum metode simpleks Fungsi Tujuan: ๐ โ ๐ถ1 ๐1 โ ๐ถ2 ๐2 โ โฏ โ ๐ถ๐ ๐๐ โ 0๐1 โ 0๐2 โ โฏ โ 0๐๐ = ๐๐พ FungsiPembatas: ๐11 ๐1 + ๐12 ๐12 + โฏ + ๐1๐ ๐1๐ + 1๐1 + 0๐2 + โฏ + 0๐๐ = ๐1 ๐21 ๐1 + ๐22 ๐12 + โฏ + ๐2๐ ๐1๐ + 0๐1 + 1๐2 + โฏ + 0๐๐ = ๐2 โฎ ๐๐ 1 ๐1 + ๐๐ 2 ๐๐ 2 + โฏ + ๐๐๐ ๐๐๐ + 0๐1 + 0๐2 + โฏ + 1๐๐ = ๐๐ Variabel Kegiatan (Pengambilan Keputusan)
Slack Variabel
Bentuk model metode simpleks akan diformulasikan dalam suatu tabel yang disebut tabel simpleks. VariabelDasar
๐
๐ฟ๐
๐ฟ๐
โฆ
๐ฟ๐
๐บ๐
๐บ๐
โฆ
๐บ๐
๐ต๐ฒ
๐
1
โ๐ถ1
โ๐ถ2
โฆ
๐ถ๐
0
0
โฆ
0
0
๐บ๐
0
๐11
๐12
โฆ
๐1๐
0
โฆ
0
๐1
๐บ๐
0
๐21
๐22
โฆ
๐2๐
0
1
โฆ
0
๐2
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
โฎ
๐บ๐
0
๐๐ 2
๐๐ 2
โฆ
๐๐๐
0
0
โฆ
1
๐๐
1
Keterangan : ๐
: jumlah persamaan linear pada fungsi pembatas
๐
: jumlah variabel yang nilainya tidak diketahui
๐๐พ
: Nilai sebelah kanan fungsi tujuan
๐๐
: nilai sebelah kanan fungsi pembatas (kapasitas kegiatan)
Langka-Langkah Metode Simpleks Untuk memudahkan pemecahan persoalan program linear dengan metode simpleks disusunlah suatu prosedur/ langkah-langkah sebagai berikut:
1. Rumuskan persoalan program linear kedalam model umum program linear (fungsi tujuan dan fungsi pembatas) 2. Merubah model umum program linear menjadi model simpleks a. Pada fungsi kendala: tambahkan dengan slack variabel b. Pada fungsi tujuan: ๏ท
Ubahlah bentuk persamaan fungsi tujuan yang implisit menjadi bentuk persamaan fungsi eksplisit
๏ท
Tambahkan dengan slack variabel dan/atau variabel buatan yang bernilai nol
3. Formulasikan model simpleks kedalam tabel simpleks 4. Lakukan langkah-langkah penyelesaian atau perhitungan untuk mendapatkan solusi optimum dari metode simpleks yang akan diuraikan dengan contoh kasus maksimisasi, minimisasi.
Contoh Kasus Maksimisasi Model Program Linear 1. Fungsi Tujuan Maksimumkan
: ๐ = 150.000๐1 + 100.000๐2
2. Fungsi Kendala Kendala 1
: ๐1 + ๐2 โค 600
Kendala 2
: 2๐1 + ๐2 โค 1000
Syarat non negative
: ๐1 , ๐2 โฅ 0
Model Simpleks : 1. Fungsi Tujuan ๐ โ 150.000๐1 โ 100.000๐2 โ 0๐1 โ 0๐2 = 0 2. Fungsi Pembatas ๐1 + ๐2 + ๐1 + 0๐2 โค 600 2๐1 + ๐2 +0๐1 + ๐2 โค 1000 ๐1 , ๐2 , ๐1 , ๐2 โฅ 0
Tabel Simpleks
Tabel Simpleks 1 Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
1
โ15
โ10
0
0
0
๐บ๐
0
1
1
1
0
600
๐บ๐
0
2
1
0
1
1000
Langkah-langkah penyelesaian/ perhitungan: (1) Penyelesaian Awal (iterasi โ 0) Tabel Simpleks 1 Menentukan Kolom Kunci Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
1
โ15
โ10
0
0
0
๐บ๐
0
1
1
1
0
600
๐บ๐
0
2
1
0
1
1000
(2) Penyelesaian langkah pertama a. Menentukan kolom kunci Kolom kunci merupakan langkah dasar dalam merubah tabel simpleks pada iterasi 1. Pilihlah kolom yang mempunyai nilai koefisien fungsi tujuan yang bernilai negative dan terbesar.
Tabel Simpleks 1 Menentukan Baris Kunci Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
1
โ15
โ10
0
0
0
๐บ๐
0
1
1
1
0
600
๐บ๐
0
2
1
0
1
1000
Indeks
b. Menentukan baris kunci Baris kunci merupakan langkah dasar dalam merubah tabel simpleks pada iterasi 1. Pada penentuan baris kunci, tentukan terlebih dahulu nilai indeks dengan rumus sebagai berikut:
๐๐๐๐๐ ๐ผ๐๐๐๐๐ =
๐๐พ ๐๐ข๐๐๐ ๐ ๐ก๐ข๐๐ข๐๐ ๐๐๐๐๐ ๐๐๐๐๐ ๐๐ข๐๐๐ ๐๐ข๐๐๐ ๐ ๐๐๐๐๐๐ก๐๐
TabelSimpleks 3 Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
1
โ15
โ10
0
0
0
โ
๐บ๐
0
1
1
1
0
600
600
๐บ๐
0
2
1
0
1
1000
500
Indeks
Memilih baris kunci fungsi kendala pada iterasi 1 ditentukan dengan memilih nilai indeks yang terkecil. Pada tabel simpleks di atas nilai indeks terkecil adalah 500 pada variabel dasar ๐บ๐ (3) Menentukan angka kunci Angka kunci merupakan langkah dasar dalam merubah table simpleks pada iterasi-1. Angka kunci adalah angka yang terletak pada perpotongan kolom kunci dengan baris kunci. Nilai-nilai baris kunci๐1 yang baru masuk pada variable dasar akan berubah dengan rumus sebagai berikut: ๐๐๐๐๐ โ ๐๐๐๐๐ ๐๐๐๐๐ ๐๐ข๐๐๐ ๐๐๐๐ข ๐๐๐๐๐ ๐๐๐๐๐ ๐๐ข๐๐๐ contoh: variable dasar baru๐1 : kolom ๐1
=2/2 = 1
kolom ๐2
=ยฝ
kolom ๐1
= 0/2 = 0
kolom ๐1
=ยฝ
kolom NK
= 1000/2 = 500
(4) Merubah nilai-nilai baris selain baris๐1 (variable dasar baru) dengan rumus sebagai berikut: ๐๐๐๐๐๐ ๐๐๐ ๐๐๐๐๐ ๐๐๐๐ข = ๐๐๐๐๐ ๐๐๐๐ โ ( ๐๐๐๐ ๐๐๐๐๐ ๐๐ข๐๐๐) ร (๐๐๐๐๐ โ ๐๐๐๐๐ ๐๐๐๐๐ ๐๐๐๐ ๐ฃ๐๐๐๐๐๐๐ ๐๐๐ ๐๐ ๐๐๐๐ข) ๐๐๐๐๐
Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
Indeks
1
1
โ5/2
0
15/2
7.500
-
๐บ๐
0
0
1/2
1
โ1/2
100
-
๐ฟ๐
0
1
1/2
0
1/2
500
-
(5) Ulangi langkah-langkah di atas sampai diperoleh penyelesaian optimum. Penyelesaian perhitungan sudah optimum jika pada koefisisen fungsi tujuan (baris pertama table simpleks) tidak ada lagi yang bernilai negative.
Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
Indeks
1
โ15
โ10
0
0
0
-
๐บ๐
0
1
1
1
0
600
600
๐บ๐
0
2
1
0
1
1000
500
Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
Indeks
1
1
โ5/2
0
15/2
7.500
-
๐บ๐
0
0
1/2
1
โ1/2
100
-
๐ฟ๐
0
1
1/2
0
1/2
500
-
Variabel Dasar ๐
๐
๐ฟ๐
๐ฟ๐
๐บ๐
๐บ๐
๐ต๐ฒ
Indeks
1
1
0
0
5
8.000
-
๐ฟ๐
0
0
1
1
2
200
-
๐ฟ๐
0
1
0
0
โ1
400
-
Pada iterasi ke 2 terlihat bahwa sudah tidak adalagi yang mempunyai nilai negative, proses perubahan selesai dan ini menunjukkan penyelesaian persoalan program linear dengan metode simpleks sudah mencapai optimum dengan hasil sebagai berikut:
๐ฟ๐ = ๐๐๐ ๐ฟ๐ = ๐๐๐ ๐๐๐๐๐ ๐๐๐ข๐ = 8.000
