1) Formulasikan dan standarisasikan modelnya 2) Bentuk tabel awal simpleks berdasarkan informasi model di atas 3) Tentukan kolom kunci di antara kolom-kolom variabel yang ada, yaitu kolom yang mengandung nilai (cj - Zj) paling positif untuk kasus maksimasi dan atau mengandung nilai (cj – Zj) paling negatif untuk kasus minimasi
4) Tentukan baris kunci di antara baris-baris variabel yang ada, yaitu baris yang memiliki rasio kuantitas dengan nilai positif terkecil. 5) Bentuk tabel berikutnya dengan memasukkan variabel pendatang ke kolom variabel dasar dan mengeluarkan perantau dari kolom tersebut, serta lakukan transformasi baris-baris variabel. Dengan menggunakan rumus transformasi berikut:
• Baris baru selain baris kunci = baris lama – (rasio kunci x baris kunci lama) • Baris kunci baru = baris kunci lama
angka kunci Keterangan: Rasio kunci = unsur kolom kunci angka kunci
6) Lakukan uji optimalitas. Dengan kriteria jika semua koefisien pada baris (cj – Zj) sudah tidak ada lagi yang bernilai positif (untuk kasus maksimasi), atau sudah tidak ada lagi yang bernilai negatif (untuk kasus minimasi), berarti tabel sudah optimal. Jika kriteria di atas belum terpenuhi maka diulangi mulai dari langkah ke-3 sampai ke-6, hingga terpenuhi kriteria tersebut.
Variabel dasar
Tujuan Cj
c1
K
x1
c2 x2
… …
cn
0 xn
0 s1
…
0
s2
…
sm
Q S1
0
B1
a11
a12 …
a1n
1
0
…
0
S2
0
B2
a21
a22 …
a2n
0
1
…
0
….
….
….
…
…
…
…..
…
…
….
….
…..
….
….
…
….
…
…..
….
…
…..
…
Sm
0
bm
am1
am2
….
Amn
0
0
…..
1
Zj
0
0
0
….
0
0
0
….
0
cj-Zj
c1
Cn
0
0
….
0
c2
….
1. Dengan menggunakan contoh yang sama pada pertemuan sebelumnya, lakukan optimasi menggunakan metode simpleks!
1) Formulasi dan standarisasi model program linier Maksimumkan Z = 8x1 + 6x2 + 0.s1 + 0.s2 Batasan-batasan: 4x1 + 2x2 + 1.s1 + 0.s2 = 60 2x1 + 4x2 + 0.s1 + 1.s2 = 48
2) Menyusun model dalam tabel simpleks Variabel dasar
Tujuan
Cj K
8
6
0
0
x1
x2
s1
s2
Q
Rasio Kuantitas
S1
0
60
4
2
1
0
60:4 = 15
S2
0
48
2
4
0
1
48:2 = 24
Zj=Jmlh (Tujuan*K)
0
0
0
0
0
cj – Zj
8
6
0
0
3) Menentukan kolom kunci Karena kasusnya adalah maksimasi, maka pemilihan kolom kunci adalah nilai (cj – Zj) yang paling positif (positif terbesar). Pada tabel di atas kolom kuncinya adalah kolom x1 di mana nilai (cj – Zj) = 8.
4) Menentukan baris kunci Kriteria baris kunci dipilih pada baris yang nilai rasio kuantitasnya adalah positif terkecil. Tabel tersebut baris kuncinya adalah baris s1 karena nilai rasio kuantitasnya adalah 15.
5) Perubahan baris kunci dan baris non kunci Karena yang terpilih kolom kunci adalah kolom x1, maka variabel dasar s1 digantikan oleh variabel x1 (sebagai variabel pendatang) sedangkan nilai-nilai baris kunci baru diperoleh dengan cara membaginya dengan nilai kunci (4), sehingga diperoleh baris kunci yang baru seperti tabel berikut:
• Transformasi baris s1 Cj
8
6
0
0
K
X1
X2
S1
S2
1
½
¼
0
Variabel Dasar
Tujuan
Q
X1
8
15
S2 Zj Cj-Zj
• Sedangkan baris selain baris kunci hitungannya sebagai berikut: • Baris baru selain baris kunci = baris lama – (rasio kunci x baris kunci lama) • Baris s2 akan menjadi: • Baris baru = (0 48 2 4 0 1) 2/4 x (0 60 4 2 1 0) ____________________________________________ __ (0 18 0 3 -1/2 1)
• Nilai-nilai baru tersebut disusun kembali dalam tabel berikutnya sebagai hasil iterasi pertama seperti berikut: Cj
8
6
0
0
K
X1
X2
S1
S2
Variabel Dasar
Tujuan
Q
Rasio Kuantitas
X1
8
15
1
½
¼
0
15:1/2 = 30
S2
0
18
0
3
-1/2
1
18:3 = 6
Zj
120
8
4
2
0
cj – Zj
0
2
-2
0
6) Uji Optimalitas Karena pada baris (cj – Zj) masih ada yang bernilai positif (2), maka dilanjutkan langkah perbaikan/ transformasi baris. Pertama tentukan kolom kunci dan baris kunci. Pada tabel di atas, kolom kuncinya adalah kolom x2 dimana nilai (cj – Zj) adalah 2 (positif terbesar), sedangkan baris kuncinya adalah baris s2 dimana nilai rasio kuantitasnya positif terkecil. Baris kunci baru variabel dasarnya s2 digantikan oleh x2 sebagai variabel pendatang, sedangkan nilai-nilai lainnya dibagi dengan angka kunci (3) sehingga diperoleh:
• Untuk baris selain baris kunci yaitu baris x1 akan berubah menjadi: (8 15 1 ½ ¼ 0) 1/6 (0 18 0 3 -1/2 1) ______________________________________ __ (8 12 1 0 1/3 -1/6) Sehingga hasil dari perubahan-perubahan di atas bila disusun dalam tabel simpleks akan terlihat sebagai berikut:
• Hasil transformasi kedua Cj
8
6
0
0
K
X1
X2
S1
S2
Variabel Dasar
Tujuan
Q
X1
8
12
1
0
1/3
-1/6
X2
6
6
0
1
-1/6
1/3
Zj
132
8
6
5/3
2/3
Cj – Zj
0
0
-5/3
-2/3
• Dari tabel di atas, tampak bahwa nilai pada baris terakhir (cj – Zj) sudah tidak ada lagi yang bernilai positif, artinya tabel sudah optimal. Sebagai hasilnya terlihat bahwa nilai maksimum laba adalah 132 dengan masing-masing variabel x1 = 12 dan x2 = 6.
1) Sebuah industri keramik membuat dua jenis produk unggulan A dan B. Untuk menghasilkan satu buah jenis A diperlukan waktu pengerjaan 1 jam dan bahan baku 4 kg, sedangkan jenis B membutuhkan 2 jam dan bahan baku 3 kg. Waktu dan bahan baku yang tersedia masing-masing 40 jam dan 120 kg. Keuntungan tiap unit A dan B masing-masing $40 dan $50, tentukan jumlah produksi A dan B untuk mendapatkan laba terbesar dengan menggunakan metode simpleks!
