CONTOH SOAL DENGAN MENGGUNAKAN METODE SIMPLEKS (TEKNIK M)

-->

2. Persamaan matematis suatu program linier adalah sebagai berikut :

Minimasi : Z = 6X₁ + 7,5X₂

Dengan pembatas :

7X₁ + 3X₂ ≥ 210

6X₁ + 12X₂ ≥ 180

4X₂ ≥ 120

X₁, X₂ ≥ 0

Carilah harga X₁ dan X₂ ?

JAWABAN

Pada kasus ini kita akan menggunakan metode simplex M (BIG – M), hal ini dikarenakan pada kasus ini pertidk samaan pembatasnya menggunakan ≥ (lebih dari sama dengan).

Persamaan Tujuan : Z - 6x₁ - 7,5X₂ - 0S₁ - 0S₂ - 0S₃ = 0 Baris 0

Persamaan Kendala : 7x₁ + 3x₂ - S₁ +A₁ = 210 Baris 1

6x₁ + 12x₂ - S₂ +A₂ = 180 Baris 2

4x₂ - S₃ + A₃ = 120 Baris 3

Bagi kendala pertidaksamaan jenis ≤, maka variabel slack ditambahkan untuk menghabiskan sumber daya yang digunakan dalam kendala. Cara ini tidak dapat diterapkan pada kendala pertidaksamaan jenis ≥ dan kendala persamaan (=) persamaan diatas diperoleh karena tanda ≥ harus mengurangi variable surplus.

Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar ditempatkan pada A₁, A₂, dan A₃ sehingga fungsi tujuannya menjadi :

Z = 6x₁ + 7,5X₂ + 0S₁ + 0S₂ + 0S₃ + MA₁ + MA₂ + MA₃

Table simplex awal dibentuk dengan A₁, A₂, dan A₃ sebagai variable basis, seperti table berikut :

Basis	X1	X2	S1	S2	S3	A1	A2	A3	NK	RASIO
Z	13M-6	19M-7,5	-M	-M	-M	0	0	0	510M
A1	7	3	-1	0	0	1	0	0	210	210 : 3 = 70
A2	6	12	0	-1	0	0	1	0	180	180 : 12 = 15
A3	0	4	0	0	-1	0	0	1	120	120 : 4 = 30

Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini dikarenakan seluruh NBV masih mempunyai koefisien yang berharga positif. Oleh karena itu Untuk x₂ terpilih sebagai entry variable karena x₂ memiliki nilai koefisien positif yang paling besar, dan A3 menjadi Leaving Variable. Dan yang akan menjadi pivot adalah baris 2 karena memiliki rasio paling kecil.

Langkah-langkah ERO Iterasi Pertama :

ERO 1 : Menjadikan nilai koefisien x₂ berharga 1 pada baris 2

½ x₁ + x₂ - ¹/₁₂ S₂ +¹/₁₂ A₂ = 15

ERO 2 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 0

Z = ⁹/₄ x₁ + 0S₁ + ¹⁵/₂₄ S₂ + 0S₃ + MA₁ + [ M - ¹⁵/₂₄]A₂ + MA₃ + 112,5

ERO 3 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 1

¹¹/₂ x₁ + ¼ S₂ + A₁ - ¹/₄ A₂= 165

ERO 4 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 3

-2x₁ + ¹/₃ S₂ - S₃ - ¹/₃ A₂ + A₃ = 60

Konversi bentuk standard iterasi Pertama :

Z = ⁹/₄ x₁ + 0S₁ + ¹⁵/₂₄ S₂ + 0S₃ + MA₁ + [ M - ¹⁵/₂₄]A₂ + MA₃ + 112,5

¹¹/₂ x₁ + ¼ S₂ + A₁ - ¹/₄ A₂ = 165

-2x₁ + ¹/₃ S₂ - S₃ - ¹/₃ A₂ + A₃ = 60

½ x₁ + x₂ - ¹/₁₂ S₂ +¹/₁₂ A₂ = 15

Tabel Iterasi Pertama

Basis	X1	X2	S1	S2	S3	A1	A2	A3	NK	RASIO
Z	-13/2M-6	0	0	7/12 - 15/24	-M	0	1/24 - M	0	225M – 112,5	*
A1	11/2	0	0	1/4	0	1	-1/4	0	165	165 : 5,5 = 30
A3	-2	0	0	1/3	-1	0	-1/3	1	60	*
X2	½	1	0	-1/12	0	0	1/12	0	15	15 : 0,5 = 30

Pada fungsi tujuan masih terdapat variable dengan nilai koefisien positif, oleh karena itu lakukan iterasi kedua.

Langkah-langkah ERO Iterasi Kedua:

ERO 1 : Menjadikan nilai koefisien x₁ berharga 1 pada baris 1

x₁ + ¹/₂₂ S₂ + ²/₁₁A₁ - ¹/₂₂ A₂ = 30

ERO 2 : Menjadikan nilai koefisien x₁ berharga 0 pada baris 0

Z = 0S₁ + 0,725 S₂ + 0S₃ + MA₁ -0,4A₁ + [ M – 0,725]A₂ + MA₃ + 180

ERO 3 : Menjadikan nilai koefisien x₁ berharga 0 pada baris 2

0.5 A₂ = 0

ERO 4 : Menjadikan nilai koefisien x₁ berharga 0 pada baris 3

0,39 S₂ - S₃ +0,36A₁ + 0,21 A₂ + A₃ = 120

Konversi bentuk standard iterasi kedua :

Z = 0S₁ + 0,725 S₂ + 0S₃ + [M -0,4]A₁ + [ M – 0,725]A₂ + MA₃ + 180

x₁ + ¹/₂₂ S₂ + ²/₁₁A₁ - ¹/₂₂ A₂ = 30

0.5 A₂ = 0

0,39 S₂ - S₃ + 0,36A₁ + 0,21 A₂ + A₃ = 120

Tabel Iterasi Kedua

Basis	X1	X2	S1	S2	S3	A1	A2	A3	NK
Z	0	0	0	-0,725	0	-M+0,4	-1/2M+0,725	M	-180
x1	1	0	0	1/22	0	2/11	-1/22	0	30
A3	0	0	0	0	0	0	½	0	0
X2	0	0	0	0,39	-1	0,36	0,21	1	120

Iterasi kedua adalah optimum karena koefisien pada persamaan Z semuanya non positif, dengan x₁ = 30, x₂ = 120 dan z=-180.

3. PT Unilever bermaksud membuat 2 jenis sabun, yakni sabun bubuk dan sabun batang. Untuk itu dibutuhkan 2 macam zat kimia, yakni A dan B. jumlah zat kimia yang tersedia adalah A=200Kg dan B=360Kg.

Untuk membuat 1Kg sabun bubuk diperlukan 2 Kg A dan 6 Kg B. untuk membuat 1 Kg sabun batang diperlukan 5 Kg A dan 3 Kg B. bila keuntungan yang akan diperoleh setiap membuat 1Kg sabun bubuk = $3 sedangkan setiap 1 Kg sabun batang = $2, berapa Kg jumah sabun bubuk dan sabun batang yang sebaiknya dibuat ?

JAWABAN

Pemodelan matematika :

Maksimumkan : Z = 3x₁ + 2x₂

Pembatas : 2x₁ + 5x₂ = 200

6x₁ + 3x₂ = 360

Persamaan Tujuan : Z - 3x₁ - 2x₂ = 0 Baris 0

Persamaan Kendala : 2x₁ + 5x₂ + A₁ = 200 Baris 1

6x₁ + 3x₂ + A₂ = 360 Baris 2

Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar ditempatkan pada A₁, A₂, dan A₃ sehingga fungsi tujuannya menjadi :

Z = 3x₁ - 2X₂ + MA₁ + MA₂

Basis	x1	x2	A1	A2	NK	Rasio
Z	8M-3	8M+2	0	0	560M
A1	2	5	1	0	200	200:5=40
A2	6	3	0	1	360	360:3=120

Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini dikarenakan belum seluruhnya NBV mempunyai koefisien yang berharga positif. Oleh karena itu Untuk x₂ terpilih sebagai entry variable karena x₂ memiliki nilai koefisien negatif, dan A₁ menjadi Leaving Variable. Dan yang akan menjadi pivot adalah baris 1 karena memiliki rasio paling kecil.

Langkah-langkah ERO Iterasi Pertama :

ERO 1 : Menjadikan nilai koefisien x₂ berharga 1 pada baris 1

0,4x₁ + x₂ + 0,2A₁ = 40

ERO 2 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 0

Z = 3,8x₁ + [M-0,4]A₁ + MA₂ - 80

ERO 3 : Menjadikan nilai koefisien x₂ berharga 0 pada baris 2

4,8x₁ – 0,6A₁ + A₂ = 240

Konversi bentuk standard iterasi pertama :

Z = 3,8x₁ + [M-0,4]A₁ + MA₂ - 80

0,4x₁ + x₂ + 0,2A₁ = 40

4,8x₁ – 0,6A₁ + A₂ = 240

Basis	x1	x2	A1	A2	NK	Rasio
Z	4,8M-3,8	0	0,4-0,4M	0	240M+80
X2	0,4	1	0,2	0	40
A2	4,8	0	0,6	1	240

Iterasi pertama adalah optimum karena koefisien pada persamaan Z semuanya positif, dengan x₁ = 40, x₂ = 240 dan z=240M+80.