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 = 18X₁ + 36X₂

12X₁ + 6X₂ ≥ 36

4X₁ + 4X₂ ≤ 32

X₁ tak terbatas

X₂ ≥ 0

Dimana X₁ dan X₂ 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 X₁ pada malasah dia atas menjadi :

Maksimumkan

Dengan syarat Z = 18X₁’ – 18X’’ + 36X_2­ + 0S₁ + 0S₂ – MA₁

                           12X₁ – 12X’’ + 6X₂ – S₁ + A₁  = 36

                            4X₁’ – 4X’’ +4X₂ + S₂ = 32

                            X₁’  X’’  X₂  ≥ 0

Penyelesaian

Solusi terhadap masalah ini ditunjukan pada tabel berikut,

Subsitusikan A₁ Fungsi tujuan :

12X₁’ – 12X’’ + 6X₂ – S_{1 ­}+ A₁ = 36

A₁ = 36 – 12X₁’ + 12X’’ – 6X₂ + S₁

Maka :

Z = 18X₁’ – 18X’’ + 0S₁ + 0S₂ – [M(36 – 12X₁’ + 12X’’ – 6X₂ + S₁)]

                                                            -36M + (12M)X₁’- (12M)X’’+ (6M)X₂ – S₁M)

Z = (18 + 12M)X₁’ – (18 - 12M)X₂’’ + (36 + 6M)X₂ – (M) S₁ – 36M

Persamaan Z dalam tabel :

Z – (18 - 12M)X₁’ + (18 + 12M)X’’ – (36 – 6M)X₂ + (M) S₁ = -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.

X₁ = X_1­’-X’’ = 0-(-1/2) = ½ dan X₂ = 10, sehingga Z= -12