Selasa, 28 Maret 2017

Tugas 1 Riset operasi Metode simpleks

Metode simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah program linier yang didasarkan pada proses iterasi.

Prosedur Metode Simpleks
1. Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
2. Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar
3. Membuat Table Simpleks Awal
4. Algoritma metode simpleks 

Program Linier : Bentuk Standar
1. Ruas kanan (RK) fungsi tujuan harus nol (0)
2. Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.
3. Fungsi kendala dengan tanda “£ ” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.
4. Fungsi kendala dengan tanda “³ ” diubah ke bentuk “£ ” dengan cara mengalikan dengan –1, lalu diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1, karena bertanda negatip.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar
1. Ada tiga bentuk fungsi kendala:  £, ≥, dan =.
2. Konversi fungsi kendala bertanda £: menambahkan slack variable pada fungsi kendala tersebut.
3. Untuk kendala berbentuk ‘³’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.
4. Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.
5. Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala. 

CONTOH
Maksimum       
Z = 18X1 + 36X2
12X1 + 6X2 ≥ 36
4X1 + 4X2 ≤ 32
X1 tak terbatas
X2 ≥ 0

Dimana X1 dan X2 adalah tingkat produksi barang 1 dan barang untuk mengubah masalah ini ke dalam bentuk baku dengan semua variable non negatif, X­1‘ –  X’’ harus menggantikan X1 pada malasah dia atas menjadi :

Maksimumkan
Dengan syarat Z = 18X1’ – 18X’’ + 36X + 0S1 + 0S2 – MA1
                           12X1 – 12X’’ + 6X2 – S1 + A1  = 36
                            4X1’ – 4X’’ +4X2 + S2 = 32
                            X1’  X’’  X2  ≥ 0


Penyelesaian
Solusi terhadap masalah ini ditunjukan pada tabel berikut,
Subsitusikan A1 Fungsi tujuan :
12X1’ – 12X’’ + 6X2 – S1 ­+ A1 = 36
A1 = 36 – 12X1’ + 12X’’ – 6X2 + S1

Maka :

Z = 18X1’ – 18X’’ + 0S1 + 0S2 – [M(36 – 12X1’ + 12X’’ – 6X2 + S1)]
                                                            -36M + (12M)X1’- (12M)X’’+ (6M)X2 – S1M)

Z = (18 + 12M)X1’ – (18 - 12M)X2’’ + (36 + 6M)X2 – (M) S1 – 36M

Persamaan Z dalam tabel :
Z – (18 - 12M)X1’ + (18 + 12M)X’’ – (36 – 6M)X2 + (M) S1 = -36M

Tabel 1.1 (Tabel simpleks awal)
Basis
X1
X’’
X2
S1
S2
S3
Solusi
Rasio
Z
-18 -12M
18 + 12M
- 36 - 6M
M
0
0
-36M

A1
12
-12
6
-1
0
1
36
3
S2
4
-4
4
0
1
0
32
8


Tabel 1.2 (pivot point untuk iterasi pertama)
Basis
X1
X2
X3
S1
S2
S3
Solusi
Z







A1
1
-1
1/2
-1/12
0
1/12
36
S2




























Tabel 1.3 (tabel iterasi pertama)
Basis
X1
X’’
X2
S1
S2
S3
Solusi
Rasio
Z
0
0
-27
-3/2
0
0
 54

A1
1
-1
1/2
-1/12
0
1/12
36
72
S2
0
0
2
1/3
1
0
20
10

Tabel 1.4 (Pivot point untuk iterasi kedua)
Basis
X1
X2
X3
S1
S2
S3
Solusi
Z







X2
4
-4
2
-1/3
0
*
12
S2

























Tabel 1.5 (tabel iterasi kedua)
Basis
X1
X’’
X2
S1
S2
S3
Solusi
Rasio
Z
108
-108
27
-21/2
0
*
 42

X2
4
-4
2
-1/3
0
*
12
*
S2
-8
8
-2
1
1
*
-4
10

Tabel 1.6 (pivot point untuk iterasi ketiga)
Basis
X1
X2
X3
S1
S2
S3
Solusi
Z







X2







X’’
-1
1
-1/4
 1/8
1/8
*
-1/2















Tabel 1.7 (tabel iterasi ketiga yang menghasilkan nilai optimum)
Basis
X1
X’’
X2
S1
S2
S3
Solusi
Rasio
Z
0
0
0
-24
13.5
*
 -12
optimum
X2
0
0
1
-5/6
-1/2
*
10

X2’’
-1
1
1/4
1/8
1/8
*
-1/2


                     Setelah diperoleh tabel optimum, untuk menentukan solusi terhadap variable masalah asli, variable harus diubah kembali kedalam bentuk asli.
X1 = X’-X’’ = 0-(-1/2) = ½ dan X2 = 10, sehingga Z= -12