Riset Operasi Tugas 4: Metode Big M & Contoh Kasusnya

1.          Pengertian Metode Big-M

          Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar  (bentuk standar adalah memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk  ≤ dan kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.

          Masalah ini akan muncul bila kita akan mencari basis fesibel awal sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku atau standar.

2.      Contoh Kasus Metode Big-M

Perhatikan contoh kasus di bawah ini.

Bentuk Umum:

Min. z = 4 x1 + x2 Terhadap: 3x1 + x2 = 3

4x1 + 3x2 ≥ 6x1+2x2 ≤ 4

x1, x2 ≥ 0

Bentuk Baku:

Min. z = 4 x1 + x2 Terhadap: 3x1 + x2 = 3

       4x1 + 3x2  - s1 = 6

         x1 + 2x2 + s2 = 4

         x1, x2, s1, s2 ≥

Kendala 1 dan 2 tidak mempunyai slack variables, sehingga tidak ada variabel basis awal. Untuk berfungsi sebagai variabel basis awal, pada kendala 1 dan 2 ditambahkan masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big M-nya adalah:

Min. z = 4 x1 + x2 + MA1 + MA2

Terhadap:       3x1 + x2 + A1 = 3

4x1 + 3x2 - s1 + A2 = 6 x1 + 2x2 + s2 = 4

x1, x2, s1, s2 ≥ 0

1.   Nilai A1 digantikan dari fungsi kendala pertama. A1 = 3 - 3x1 - x2

MA1  berubah menjadi M(3 - 3x1 - x2)  3M-3Mx1-Mx2

2.   Nilai A2 digantikan dari fungsi kendala ketiga.

A2 = 6 - 4x1 - 3x2  + s1

MA2 berubah menjadi M(6 - 4x1 - 3x2 + s1) 6M- 4Mx1 - 3Mx2 + Ms1

3.   Fungsi tujuan berubah menjadi

Min z = 4x1 + x2 + 3M-3Mx1-Mx2 +6M-4Mx1-3Mx2+Ms1

=  (4 -7M)x1+(1 - 4M)x2 + Ms1 +9M

4.   Tabel awal simpleks

VB	X1	X2	S1	A1	A2	S1	Solusi
z	-4+7M	-1+4M	-M	0	0	0	9M
A1	3	1	0	1	0	0	3
A2	4	3	-1	0	1	0	6
S2	1	2	0	0	0	1	4

5. Perhitungan iterasinya sama dengan simpleks sebelumnya.

Iterasi-0

	VB				X1	X2	S1		A1		A2		S2			Solusi			Rasio
	z			-4 +7M		-1 +4M	-M	0			0		0				9M		-
	A1				3	1	0	1			0		0				3		1
	A2				4	3	-1	0			1		0
																	6		3/2
	S2				1	2	0	0			0		1				4		2
				Iterasi-1
	VB			X1		X2	S1	A1			A2		S2			Solusi			Rasio
	z			0	(1 +5M)/3		-M   (4-7M)/3				0		0			4+2M			-
	X1			1		1/3	0	1/3			0		0				1		3
	A2			0		5/3	-1	-4/3			1		0
																	2		6/5
	S2			0		5/3	0	-1/3			0		1				3		9/5
				Iterasi-2
	VB			X1	X2	S1	A1		A2				S2			Solusi			Rasio
	z			0	0	1/5	8/5 – M		-1/5 – M				0				18/5		-
	X1			1	0	1/5	3/5		-1/5				0				3/5		25/3
	X2			0	1	-3/5	-4/5	3/5					0
																	6/5		-
	S2			0	0	1	1	-1					1				1		1

sumber:

http://drs-saukanihasan.blogspot.co.id/2012/06/operation-research.html