Teknik Riset Operasi

Tugas : Teknik Riset Operasi (Operation Research Technic)

Program Studi : S1 – Sistim Informasi / Semester IV

Tugas Rumah (Homework) #2

Soal :

Seorang petani modern ingin meminimumkan biaya produksi sapi-sapi perahnya. Setiap hari diperlukan 3 jenis makanan M1, M2 dan M3, dimana masing-masing mengandung kadar nutrisi N1, N2, N3 dan N4.

Makanan M1, M2 dan M3 masing-masing mengandung kadar nutrisi (N1, N2, N3 dan N4) sebesar (3, 2, 3 dan 1), (2, 2, 1 dan 3) dan (2, 1, 1 dan 4) satuan.

Kebutuhan nutrisi-nutrisi N1, N2, N3 dan N4 masing-masing tidak kurang dari 30, 27, 40 dan 35 satuan.

Biaya untuk membeli bahan makanan M1, M2 dan M3, masing-masing 5, 4 dan 3 satuan uang ($)

Penyelesaian :

a) Formulasinya :

minimumkan Z = 5X₁ + 4X₂ + 3X₃

dengan memperhatikan kendala-kendala :

(1) 3X₁ + 2X₂ + 2X₃ ³ 30

(2) 2X₁ + 2X₂ + 1X₃ ³ 27

(3) 3X₁ + 1X₂ + 1X₃ ³ 40

(4) 1X₁ + 3X₂ + 4X₃ ³ 35

X₁, X₂, X₃ ³ 0

b) Tabel Data Awal :

Nutrisi	Jenis Makanan (Unit)			Kebutuhan (Unit)
	M1	M2	M3
N1 N2 N3 N4	3 2 3 1	2 2 1 3	2 1 1 4	³ 30 ³ 27 ³ 40 ³ 35
Biaya ($)	5	4	3	-

Selanjutnya untuk formulasi yang ada pada point a) dalam bentuk pertidaksamaan dijadikan bentuk baku (standard form), suatu bentuk persamaan sebagai berikut :

minimumkan Z = 5X₁ + 4X₂ + 3X₃

dengan memperhatikan kendala-kendala :

(1) 3X₁ + 2X₂ + 2X₃ – S₁ = 30

(2) 2X₁ + 2X₂ + 1X₃ – S₂ = 27

(3) 3X₁ + 1X₂ + 1X₃ – S₃ = 40

(4) 1X₁ + 3X₂ + 4X₃ – S₄ = 35

X₁, X₂, X₃, S₁, S₂, S₃, S₄ ³ 0

Karena formulasi yang ada pada point a) dalam bentuk pertidaksamaan bertanda lebih dari atau sama dengan ( ³ ) maka selain – S_n perlu pula + R, sehingga persamaan-persamaan kendalanya menjadi tereduksi (reduction form), sebagai berikut :

minimumkan Z = 5X₁ + 4X₂ + 3X₃ + R₁ + R₂ + R₃ + R₄

dengan memperhatikan kendala-kendala :

(1) 3X₁ + 2X₂ + 2X₃ – S₁ + R₁ + R₂ + R₃ + R₄= 30

(2) 2X₁ + 2X₂ + 1X₃ – S₂ + R₁ + R₂ + R₃ + R₄= 27

(3) 3X₁ + 1X₂ + 1X₃ – S₃ + R₁ + R₂ + R₃ + R₄= 40

(4) 1X₁ + 3X₂ + 4X₃ – S₄ + R₁ + R₂ + R₃ + R₄= 35

X₁, X₂, X₃, S₁, S₂, S₃, S₄, R₁, R₂, R₃, R₄ ³ 0

Selanjutnya persamaan Z perlu dijadikan persamaan yang bersifat implisit yaitu semua variabel pada suatu ruas dengan mengalikan variabel R_n dengan M yang merupakan cara penyelesaian dengan teknik bilangan besar M (the big-M technic) sedangkan persamaan-persamaan kendalanya dikalikan dengan M, sehingga bentuk persamaannya menjadi sebagai berikut :

Z – 5X₁ – 4X₂ – 3X₃ – MR₁ – MR₂ – MR₃ – MR₄ = 0

dengan memperhatikan kendala-kendala :

(1) 3MX₁ + 2MX₂ + 2MX₃ – MS₁ + MR₁ + MR₂ + MR₃ + MR₄ = 30M

(2) 2MX₁ + 2MX₂ + 1MX₃ – MS₂ + MR₁ + MR₂ + MR₃ + MR₄ = 27M

(3) 3MX₁ + 1MX₂ + 1MX₃ – MS₃ + MR₁ + MR₂ + MR₃ + MR₄ = 40M

(4) 1MX₁ + 3MX₂ + 4MX₃ – MS₄ + MR₁ + MR₂ + MR₃ + MR₄ = 35M

X₁, X₂, X₃, S₁, S₂, S₃, S₄, R₁, R₂, R₃, R₄ ³ 0

Dari persamaan tersebut diatas maka didapat :

Z + (–5+9M)X₁ + (–4+8M)X₂ + (–3+8M)X₃ – MS₁ – MS₂ – MS₃ – MS₄ = 132M

Sehingga solusi problemnya adalah seperti terlihat pada tabel pengolahan data sebagai berikut :

Iterasi

Basic

Variabel Non-Basic

Variabel Basic

RHS

Rasio

X1

X2

X3

S1

S2

S3

S4

R1

R2

R3

R4

1

Z

-5+9M

-4+8M

-3+8M

-M

-M

-M

-M

0

0

0

0

132M

R1 R2 R3 R4

3M 2M 3M M

2M 2M M 3M

2M M M 4M

-M 0 0 0

0 -M 0 0

0 0 -M 0

0 0 0 -M

M 0 0 0

0 M 0 0

0 0 M 0

0 0 0 M

30M 27M 40M 35M

RHS = Right Hand Side (ruas sebelah kanan)

Tugas : Teknik Riset Operasi (Operation Research Technic)

Program Studi : S1 – Sistim Informasi / Semester IV

Tugas Rumah (Homework) #3

Dari penyelesaian Tugas #2, didapat bahwa bagian yang di-entace adalah X₁ karena memiliki M terbesar yaitu 9M, sedangkan bagian yang di-drop adalah R₁ karena memiliki rasio yang minimum yaitu 10 sehingga untuk iterasi 1 dapat ditetapkan sebagai berikut :

Untuk X₁ X₁ = 1

X₂ = 2/3

X₃ = 2/3

S₁ = -1/3

S₂ = 0/3 = 0

S₃ = 0/3 = 0

S₄ = 0/3 = 0

R₁ = 1/3

R₂ = 0/3 = 0

R₃ = 0/3 = 0

R₄ = 0/3 = 0

RHS = 30/3 = 10

Untuk Z X₁ = 0 maka (-5+9M)+PT.(1) = 0 ....... PT adalah Pengali Tetap

PT = 5-9M

S₂ = -M + (5-9M)0

= -M

S₃ = -M + (5-9M)0

= -M

S₄ = -M + (5-9M)0

= -M

R₂ = 0 + (5-9M)0

= 0

R₃ = 0 + (5-9M)0

= 0

R₄ = 0 + (5-9M)0

= 0

RHS = 132M + (5-9M)10

= 132M + 50 – 90M

= 50 + 42M

Untuk R₂ X₁ = 0 maka 2+PT.(1) = 0 ....... PT adalah Pengali Tetap

PT = -2

= -1

S₃ = 0 + (-2)0

= 0

S₄ = 0 + (-2)0

= 0

R₂ = 1 + (-2)0

= 1

R₃ = 0 + (-2)0

= 0

R₄ = 0 + (-2)0

= 0

RHS = 27 + (-2)10

= 27 – 20

= 7

Untuk R₃ X₁ = 0 maka 3+PT.(1) = 0 ....... PT adalah Pengali Tetap

PT = -3

= 1 – 2

= -1

= 1 – 2

= -1

= -1

S₂ = 0 + (-3)0

= 0

S₃ = -1 + (-3)0

= -1

S₄ = 0 + (-3)0

= 0

= -1

R₂ = 0 + (-3)0

= 0

R₃ = 1 + (-3)0

= 1

R₄ = 0 + (-3)0

= 0

RHS = 40 + (-3)10

= 40 – 30

= 10

Untuk R₄ X₁ = 0 maka 1+PT.(1) = 0 ....... PT adalah Pengali Tetap

PT = -1

S₂ = 0 + (-1)0

= 0

S₃ = 0 + (-1)0

= 0

S₄ = -1 + (-1)0

= -1

R₂ = 0 + (-1)0

= 0

R₃ = 0 + (-1)0

= 0

R₄ = 1 + (-1)0

= 1

RHS = 35 + (-1)10

= 35 – 10

= 25

Selanjutnya masing-masing RHS dibagi dengan X₃ yang mempunyai M terbesar yaitu 1+6M untuk mendapatkan rasio sebagai berikut :

Untuk X₁

Untuk R₂

Untuk R₃

Untuk R₄

Dari rasio diatas maka R₂ memiliki rasio yang minimum yaitu –21

Tabel pengolahan data untuk Iterasi 0 dan 1 :

Iterasi	Basic	Variabel Non-Basic							Variabel Basic				RHS	Rasio
		X1	X2	X3	S1	S2	S3	S4	R1	R2	R3	R4
0	Z	-5+9M	-4+8M	-3+8M	-M	-M	-M	-M	0	0	0	0	132M
	R1 R2 R3 R4	3 2 3 1	2 2 1 3	2 1 1 4	-1 0 0 0	0 -1 0 0	0 0 -1 0	0 0 0 -1	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1	30 27 40 35	10 (minimum) 13 1/2 13 1/3 35
1	Z	0				-M	-M	-M		0	0	0	50+42M
	X1 R2 R3 R4	1 0 0 0	2/3 2/3 -1 7/3	2/3 -1/3 -1 10/3	-1/3 2/3 1 1/3	0 -1 0 0	0 0 -1 0	0 0 0 -1	1/3 -2/3 -1 -1/3	0 1 0 0	0 0 1 0	0 0 0 1	10 7 10 25	15 -21 (minimum) -10 7 1/2

RHS = Right Hand Side (ruas sebelah kanan)

yang memiliki M terbesar yang memiliki Rasio terkecil bagian yang di-entrace Bbagian yang di-drop