Laboratorium Statistik-ISTA
PRAKTIKUM II PEMROGRAMAN LINIER (METODE SIMPLEKS)
A. Tujuan Praktikum 1. Memahami bagaimana merumuskan/ memformulasikan permasalahan yang terdapat dalam dunia nyata. 2. Memahami dan dapat memformulasikan permasalahan yang telah dirumuskan, dalam format pemrograman linier. 3. Memahami dan dapat mencari solusi/ menyelesaikan permasalahan yang telah diformulasikan tersebut menggunakan pemrograman linier
B. Landasan Teori Dalam metode grafik suatu pemecahan optimum selalu berkaitan dengan titik ekstrim atau titik sudut dari ruang pemecahannya. Pada intinya metode simpleks menerjemahkan definisi geometris dari titik ekstrim menjadi definisi aljabar. Untuk itu, dalam metode simpleks semua batasan harus dinyatakan dalam bentuk baku yakni diekspresikan dalam bentuk persamaan dengan menambahkan variabel slack, variabel surplus atau variabel semu (jika diperlukan). Akibatnya jumlah variabel biasanya lebih besar dari jumlah persamaan sehingga kadangkadang menghasilkan sejumlah titik pemecahan yang tidak terbatas. Titik ekstrim dari ruang ini dapat didefinisikan secara aljabar sebagai pemecahan dasar dari sistem persamaan tersebut. Dari pemecahan dasar ini selanjutnya bergerak secara sistematis ke pemecahan dasar lainnya yang memiliki potensi untuk memperbaiki nilai fungsi tujuan sehingga pada akhirnya diharapkan akan diperoleh suatu pemecahan dasar yang merupakan pemecahan optimum. Jadi metode simpleks merupaka prosedur perhitungan yang berulang (iterasi) dimana setiap perulangan berkaitan dengan suatu pemecahan dasar.
Modul Praktikum Riset Operasi
6
Laboratorium Statistik-ISTA
C. Contoh Kasus dan Penyelesaiannya Permasalahan pada Reddy Mikks Company dapat diselesaikan dengan metode simpleks. Adapun langkah-langkahnya adalah sebagai berikut : Langkah 0 : Buatlah pemecahan dasar awal yang layak (feasible) Tabel 2. Iterasi 0 : Pemecahan Dasar Awal yang Layak
Dasar
Z
X1
X2
S1
S2
S3
S4
Pemecahan
Titik
Z
1
-3
-2
0
0
0
0
0
Potong
S1
0
1
2
1
0
0
0
6
6/1 = 6
S2
0
2
1
0
1
0
0
8
8/2 = 4
S3
0
+1
1
0
0
1
0
1
-1/1 = -1
S4
0
0
1
0
0
0
1
2
0/2 = 0
Langkah 1 : Pilih entering variable dan leaving variable Pada Tabel 2 dapat dilihat bahwa x1 memiliki koefisien negatif paling besar dalam persamaan z dan karena itu dipilih sebagai entering variable. Kondisi kelayakan memperlihatkan bahwa s2 bersesuaian dengan titik potong terkecil sehingga menjadi leaving variable.
Langkah 2 : Tentukan nilai variabel dasar yang baru dengan metode Gauss-Jordan Metode ini dimulai dengan mengidentifikasi kolom entering variable (x1) sebagai entering column (bagian kolom yang diarsir) sedangkan yang mengidentifikasi baris leaving variable (s2) disebut persamaan pivot (pivot equation) (bagian baris yang diarsir) sementara elemen titik potong antara entering column dan persamaan pivot disebut sebagai elemen pivot. seperti pada tabel 3 Tabel 3. Menentukan Variabel Dasar
Dasar
Z
X1
X2
S1
S2
S3
S4
Pemecahan
Z
1
-3
-2
0
0
0
0
0
S1
0
1
2
1
0
0
0
6
S2
0
2
1
0
1
0
0
8
S3
0
+1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Modul Praktikum Riset Operasi
7
Laboratorium Statistik-ISTA
Metode Gauss-Jordan melakukan perubahan atas dasar penggunaan dua jenis perhitungan : 1. Persamaan Pivot Persamaan pivot baru = persamaan pivot lama / elemen pivot Tabel 4. Pesamaan Pivot Baru
Dasar
Z
X1
X2
S1
S2
S3
S4
Pemecahan
0
1
1/2
0
1/2
0
0
4
Z S1 X1 S3 S4
2. Semua persamaan lainnya, termasuk z persamaan baru = [persamaan lama - koefisien kolom masuk] x persamaan pivot baru
Untuk melengkapi tabel diatas, kita melakukan perhitungan jenis 2 berikut ini : a) Persamaan z : Persamaan z lama
:
-3
-2
0
0
0
0
0
Pesamaan pivot baru
:
1
1/2
0
1/2
0
0
4
Persamaan z baru
:
0
-1/2
0
3/2
0
0 12
Persamaan s1 lama
:
1
2
1
0
0
0
6
Pesamaan pivot baru
:
1
1/2
0
1/2
0
0
4
Persamaan s1 baru
:
0
3/2
1
-1/2
0
0
2
Persamaan s3 lama
:
-1
1
0
0
1
0
1
Pesamaan pivot baru
:
1
1/2
0
1/2
0
0
4
Persamaan s3 baru
:
0
3/2
0
1/2
1
0
5
-(-3)
x
b) Persamaan s1 : -(1)
x
c) Persamaan s3 : -(-3)
x
d) Persamaan s4 yang baru adalah sama dengan persamaan s4 yang lama, karena koefesien kolom masuknya adalah nol.
Modul Praktikum Riset Operasi
8
Laboratorium Statistik-ISTA
Jadi, tabel baru yang lengkap terlihat sebagai berikut : Tabel 5. Iterasi 1 : Pesamaan Baru
Dasar
Z
X1
X2
S1
S2
S3
S4
Pemecahan
Titik
Z
1
0
-1/2
0
3/2
0
0
12
Potong
S1
0
0
3/2
1
-1/2
0
0
2
2 4 = 3/ 2 3
X1
0
1
1/2
0
1/2
0
0
4
4 =8 1/ 2
S3
0
0
3/2
0
1/2
1
0
5
5 10 = 3/ 2 3
S4
0
0
1
0
0
0
1
2
2 =2 1
Langkah 3 : Lakukan pengecekan terhadap koefisien persamaan z apabila masih negatif maka kembali kelangkah 2 (tentukan entering variable dan leaving variable). Dengan cara yang sama maka dapat ditentukan bahwa entering variable-nya adalah x2 (karena memiliki nilai koefisien pada persamaan z yang paling negatif) dan leaving variable-nya adalah s1. Dengan menggunakan operasi Gauss-Jordan seperti langkah 2, maka akan menghasilkan tabel baru : a) Persamaan pivot (s1) baru = pesamaan s1 lama : 3/2 b) Persamaan z baru = pesamaan z lama – (-1/2) x pesamaan pivot baru c) Persamaan x1 baru = pesamaan z lama – (-1/2) x pesamaan pivot baru d) Persamaan s3 baru = pesamaan z lama – (3/2) x pesamaan pivot baru e) Persamaan s4 baru = pesamaan z lama – (1) x pesamaan pivot baru Tabel 6. Iterasi 2 : Pesamaan Baru
Dasar
Z
X1
X2
S1
S2
S3
S4
Z
1
0
0
1/3
4/3
0
0
X2
0
0
1
2/3
-1/3
0
0
4/3
X1
0
1
0
-1/3 2/3
0
0
10/3
S3
0
0
0
-1
1
1
0
3
S4
0
0
0
-2/3
1/3
0
1
2/3
Modul Praktikum Riset Operasi
Pemecahan 12
2 3
9
Laboratorium Statistik-ISTA
Pada tabel 5 (iterasi 2) ini menrupakan hasil optimal karena tidak satu pun variabel non-dasar (non basic) memiliki koefisien negatif. Pemecahan ini menghasilkan x1 (cat eksterior) = 10/3 dan x2 (cat interior) = 4/3 dengan keuntungan yang diperoleh sebesar Rp. 12,6667,-
D. Pencarian Solusi menggunakan POM 1. Pilih Start > Programs > Pom For Windows 2. Pilih Linear programming setelah itu pilih File > New, 3. Kemudian isikan title dengan nama (Lin_2), number of Constraints (6) serta number of variables (2) dan pada objective pilih maximize, lalu Ok 4. Setelah selesai meng-input-kan data, klick solve, maka akan muncul tampilan seperti gambar 5
Gambar 5. Darftar Solusi
5. Pada gambar 5 dapat dilihat bahwa solusi optimum dari permasalahan linier programing dengan menggunakan metode simpleks di atas adalah : x1 = 3,3333 x2 = 1,3333 s3 = 3 s4 = 0.6667 z = 12,6667
Modul Praktikum Riset Operasi
10
