Materi Riset Operasi Metode Big M

Cara mining bitcoin free klik disini
Metode Big M

            Pada pendekatan ini, artifisial variabel dalam fungsi tujuan diberi suatu biaya sangat besar (biasanya 3 atau 4 kali besarnya dibanding bilangan lain dalam model). Dalam praktek ini huruf M digunakan sebagai biaya dalam masalah minimasi dan –M sebagai keuntungan dalam masalah maksimasi dengan asumsi bahwa M adalah suatu bilangan positif yang besar.

Contoh Soal.

Perhatikan persoalan di bawah ini :

Maksimumkan :	z = 3x1 + 5x2
Berdasarkan pembatas :
x1		 4
	2x2	 12
3x1	+ 2x2	= 18
x1  , x2   0

Karena pembatas ketiga bertanda ( =), maka untuk mendapatkan solusi basis awalnya kita harus menambahkan variabel artifisial sehingga diperoleh bentuk :

Maksimumkan :  z = 3x1	+ 2x2  + 0S1 + 0S2 - MA1
Berdasarkan pembatas :
x1	+ S1		= 4
	2x2	+ S2	= 12
3x1	+ 2x2	+ A1	= 18

x₁  , x₂ , S₁, S₂ , A₁   0

Untuk memasukkan model diatas ke dalam bentuk tabel, maka terlebih dahulu substitusikan A₁ dengan cara :

A₁ = 18 - 3x₁  - 2x₂

Kemudian masukkan ke dalam persamaan z sebagai berikut : z = 3x₁ + 2x₂ + 0S₁ + 0S₂ – M(18 - 3x₁ - 2x₂)

atau :

z = (3M + 3) x₁ + (2M + 5) x₂ + 0S₁ + 0S₂ - 18M z - (3M + 3) x₁ - (2M + 5) x₂ - 0S₁ - 0S₂ = - 18 M

Hal ini dilakukan dengan maksud agar dalam pembuatan tabel simpleks awalnya, sudah secara otomatis “dipaksa” berharga nol. Selanjutnya penyelesaian persoalan di atas dapat dilakukan sebagai berikut :

Iterasi	Basis		x1			x2				S1			S2			A1			Solusi
	S1		1			0				1			0			0			4
0	S2		0			2				0			1			0			12
	A1		3			2				0			0			1			18
	z		(-3M-3)   (-2M-5)							0			0			0			- 18 M
	x1		1			0				1			0			0			4
1	S2		0			2				0			1			0			12
	A1		0			2				- 3			0			1			6
	z		0			(-2M-5)				(3M+3)			0			0			-6M +12
	x1		1			0				1			0			0			4
2	S2		0			0				3			1			- 1			6
	x2		0			1				- 3/2			0			1/2			3
	z		0			0				-9/2			0			(M+5/2)			27
	x1		1			0				0			- 1/3			1/3			2
3	S1			0	0			1				1/3					- 1/3			2
	x2			0	1			0				1/2					0			6
	z			0	0			0				3/2					(M+1)			36
Contoh lainnya :
Minimumkan :  z = 3x1 + 5x2
Berdasarkan pembatas :
	x1				 4
			2x2		= 12
	3x1  + 2x2				 18
	x1  , x2   0
Bentuk standar :
	z = 3x1  + 2x2  + 0S1 + 0S2  + MA1 + MA2
	x1				+ S1							= 4
				2x2				+ A1				= 12
	3x1  + 2x2				- S2			+ A2  = 18
	x1  , x2 , S1, S2 , A1 , A2  0
(perhatikan bahwa penalty M bertanda positip).
Substitusi :
A1 = 12 - 2x2
A2 = 18 - 3x1  - 2x2  + S2
Sehingga didapat :
z = 3x1  + 2x2				+ 0S1 + 0S2				+ M(12 - 2x2) + M(18 - 3x1  - 2x2  + S2)
Atau :
z = (-3M+3) x1 + (-4M+5) x2 + 0S1  + MS2 + 30M
z - (-3M+3) x1 - (-4M+5) x2 - 0S1  - MS2 = 30M
Iterasi	Basis			x1	x2			S1				S2			A1		A2			Solusi
	S1			1	0			1				0			0		0			4
0	A1			0	2			0				0			1		0			12
		A2	3				2		0		-1			0				1		18
		z	(3M-3)				(4M-5)		0		-M			0				0		30M
		S1	1				0		1		0			0				0		4
1		x2	0				1		0		0			1/2				0		6
		A2	3				0		0		-1			-1				1		6
		z	(3M-3)				0		0		-M			(-2M+5/2)				0		6M+30
		S1	0				0		1		1/3			1/3				-1/3		2
2		x2	0				1		0		0			1/2				0		6
		x1	1				0		0		-1/3			-1/3				1/3		2
		z	0				0		0		-1			(-M+3/2)				(-M+1)		36