Pemrograman Linier (2)

Pemrograman Linier (2) Solusi model PL dengan metode simpleks

Ahmad Sabri Universitas Gunadarma, Indonesia

1

Pemrograman Linier (2)

Bentuk umum model PL

Ingat kembali bentuk umum model PL maksimum Maks Z = c1 x1 + c2 x2 + . . . + cn xn Dengan kendala: a11 x1 + a12 x2 + . . . + a1n xn a21 x1 + a22 x2 + . . . + a2n xn .. . am1 x1 + am2 x2 + . . . + amn xn xi ≥ 0, i = 1, 2, . . . n

≤ ≤ .. .

b1 b2 .. .

≤

bm

2


Bentuk baku model PL maksimisasi Maks Z = c1 x1 + c2 x2 + . . . + cn xn Dengan kendala: a11 x1 + a12 x2 + . . . + a1n xn +s1 a21 x1 + a22 x2 + . . . + a2n xn +s2 .. . am1 x1 + am2 x2 + . . . + amn xn xi ≥ 0, i = 1, 2, . . . n si ≥ 0, i = 1, 2, . . . m

+sm

= = .. .

b1 b2 .. .

=

bm

• si disebut juga variabel slack • Bentuk baku digunakan untuk menyelesaikan model PL dengan metode simpleks 3


Tinjau kembali model PL untuk problem rumah produksi coklat, beserta solusi optimalnya yang diperoleh dengan metode grafis: Maks Z = 55M + 89H Dengan kendala: 4M + 18H 12M + 6H M, H ≥ 0

≤ ≤

1296 1824

4


Daerah solusi dari model tersebut

5


Alternatif solusi dan solusi optimal: (M, H) (0, 0) (0, 72) (130.5, 43) (152, 0)

Z = 55M + 89H 0 6408 11004.5 8360

(maksimum)

Diperoleh solusi optimal Z = 11004.5, dengan M = 130.5 dan H = 43.

6


Akan ditunjukkan penyelesaian model PL ini dengan metode simpleks.

7


Metode simpleks

Metode simpleks adalah prosedur aljabar untuk menyelesaikan masalah PL. Tidak seperti pada metode grafis, metode simpleks mengevaluasi beberapa alternatif solusi saja (tidak semua) untuk menemukan solusi optimal. Metode ini bersifat iteratif.

8


Metode simpleks

Metode simpleks adalah prosedur aljabar untuk menyelesaikan masalah PL. Tidak seperti pada metode grafis, metode simpleks mengevaluasi beberapa alternatif solusi saja (tidak semua) untuk menemukan solusi optimal. Metode ini bersifat iteratif.

8


Penyelesaian PL dengan metode simpleks

Berikut diberikan contoh penyelesaian model PL pada masalah rumah produksi coklat. Langkah pertama, buatlah bentuk baku dari model. Maks Z = 55M + 89H Dengan kendala: 4M + 18H+s1 12M + 6H +s2 M, H, s1 , s2 ≥ 0

= =

1296 1824

9


Iterasi ke-0: tabel simpleks awal

Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio

Solusi pada iterasi ke-0 (solusi dasar awal): M = 0, H = 0, Z = 0

10


Iterasi ke-0: menentukan kolom pivot

Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio

Pilih kolom pivot, yaitu kolom yang memiliki koefisien paling negatif pada baris (0); dalam kasus ini adalah kolom H.

11


Iterasi ke-0: menghitung rasio

Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio 1296 18 = 72 1824 6 = 304

Hitung rasio pada setiap baris (kecuali untuk baris Z), di mana: rasio = (solusi) / (koefisien pada kolom pivot)

12


Iterasi ke-0: menentukan baris pivot

Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio 1296 18 = 72 1824 6 = 304

Pilih baris pivot, yaitu baris yang memiliki rasio non-negatif terkecil; dalam kasus ini adalah baris (1), yang diasosiasikan sebagai variabel s1 . Elemen persekutuan antara kolom pivot dan baris pivot disebut elemen pivot; dalam hal ini elemen pivot-nya adalah 18. Pada langkah ini, H akan masuk menjadi basis, dan s1 akan keluar dari basis.

13



Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio 1296 18 = 72 1824 6 = 304


13



Itr. 0

No. (0) (1) (2)

Basis Z s1 s2

Z 1 0 0

M -55 4 12

H -89 18 6

s1 0 1 0

s2 0 0 1

Solusi 0 1296 1824

Rasio 1296 18 = 72 1824 6 = 304


13


Update tabel No.

Basis

Z

M

H

s1

s2

Solusi

Opr. Gauss-Jordan

(1)

H

0

4 18

1

1 18

0

72

(1)lama ÷ 18

Operasi baris Gauss-Jordan 1

Operasi pada baris pivot Pada kolom Basis, gantilah variabel keluar dengan variabel masuk 2 Baris pivot baru = Baris pivot lama ÷ elemen pivot 1

2

Operasi pada baris lainnya: Baris baru = (Baris lama) − (koefisien kolom pivot) × (Baris pivot baru)

14


Update tabel No. (0) (1)

Basis Z H

Z 1 0

M − 317 9 4 18

H 0 1

s1 89 18 1 18

s2 0 0

Solusi 6408 72

Opr. Gauss-Jordan (0)lama + 89 · (1)baru (1)lama ÷ 18



2


15


Update tabel No. (0) (1) (2)

Basis Z H s2

Z 1 0 0

M − 317 9 4 18 32 3

H 0 1 0

s1 89 18 1 18 − 13

s2 0 0 1

Solusi 6408 72 1392

Opr. Gauss-Jordan (0)lama + 89 · (1)baru (1)lama ÷ 18 (2)lama − 6 · (1)baru



2


16


Iterasi ke-1 Itr. 1

No. (0) (1) (2)

Basis Z H s2

Z 1 0 0

M − 317 9 4 18 32 3

H 0 1 0

s1 89 18 1 18 − 13

s2 0 0 1

Solusi 6408 72 1392

Rasio

Solusi pada iterasi ke-1: M = 0, H = 72, Z = 6408 Pada tahapan ini, H sudah masuk menjadi basis, dan s1 ke luar dari basis. Perhatikan bahwa pada baris (0) masih terdapat koefisien dari variabel non basis yang bernilai negatif, yang berarti nilai Z masih belum optimal; oleh karena itu lakukan langkah serupa dengan yang sebelumnya.

17


Iterasi ke-1: menentukan kolom pivot

Itr. 1

No. (0) (1) (2)

Basis Z H s2

Z 1 0 0

M −317 9 4 18 32 3

H 0 1 0

s1 89 18 1 18 −1 3

s2 0 0 1

Solusi 6408 72 1392

Rasio

18


Iterasi ke-1: menghitung rasio

Itr. 1

No. (0) (1) (2)

Basis Z H s2

Z 1 0 0

M −317 9 4 18 32 3

H 0 1 0

s1 89 18 1 18 −1 3

s2 0 0 1

Solusi 6408 72 1392

Rasio 72 4/18 = 324 1392 32/3 = 130.5

19



Itr. 1

No. (0) (1) (2)

Basis Z H s2

Z 1 0 0

M − 317 9 4 18 32 3

H 0 1 0

s1 89 18 1 18 −1 3

s2 0 0 1

Solusi 6408 72 1392

Rasio 72 4/18 = 324 1392 32/3 = 130, 5

elemen pivot = 32 3

20


Update tabel

No.

Basis

Z

M

H

s1

s2

Solusi

Opr. Gauss-Jordan

(2)

M

0

1

0

1 − 32

3 − 32

130,5

(2)lama ÷

32 3

21


Update tabel

No. (0)

Basis Z

Z 1

M 0

H 0

s1 123 32

s2 317 96

Solusi 11004,5

(2)

M

0

1

0

1 − 32

3 − 32

130,5

Opr. Gauss-Jordan (0)lama + 317 9 · (2)baru (2)lama ÷

32 3

22


Update tabel

No. (0) (1) (2)

Basis Z H M

Z 1 0 0

M 0 0 1

H 0 1 0

s1 123 32 1 16 1 − 32

s2 317 96 −1 48 3 − 32

Solusi 11004,5 43 130,5

Opr. Gauss-Jordan (0)lama + 317 9 · (2)baru 4 (1)lama − 18 · (2)baru (2)lama ÷ 32 3

23


Iterasi ke-2: tabel simpleks optimal

Itr. 2

No. (0) (1) (2)

Basis Z H M

Z 1 0 0

M 0 0 1

H 0 1 0

s1 123 32 1 16 1 − 32

s2 317 96 −1 48 3 − 32

Solusi 11004,5 43 130,5

Rasio

Solusi pada iterasi ke-2: M = 130, 5, H = 43, Z = 11004, 5 Pada tahapan ini, seluruh koefisien pada persamaan (0) tidak ada yang negatif, menandakan bahwa solusi optimal telah tercapai.

24


Tabel simpleks lengkap Berikut ini adalah tabel simpleks untuk seluruh iterasi yang dilakukan: Itr. 0

1

2

No. (0) (1) (2) (0) (1) (2) (0) (1) (2)

Basis Z s1 s2 Z H s2 Z H M

Z 1 0 0 1 0 0 1 0 0

M -55 4 12 − 317 9 4 18 32 3

0 0 1

H -89 18 6 0 1 0 0 1 0

s1 0 1 0 89 18 1 18 −1 3 123 32 1 16 1 − 32

s2 0 0 1 0 0 1 317 96 −1 48 3 − 32

Solusi 0 1296 1824 6408 72 1392 11004,5 43 130,5

Rasio 1296 18 = 72 1824 6 = 304 72 4/18 = 324 1392 32/3 = 130, 5

25


Kondisi untuk variabel masuk dan variabel keluar

Kondisi optimalitas. Dalam masalah maksimisasi [minimisasi], variabel masuk adalah variabel non-basis dengan koefisien paling negatif [positif] pada baris (0). Optimal dicapai jika semua koefisien dari variabel non-basis adalah non-negatif [non-positif]. Kondisi kelayakan. Untuk masalah maksimisasi ataupun minimisasi, variabel keluar adalah variabel basis dengan rasio non-negatif terkecil.

26


Langkah-langkah metode simpleks

1

Buatlah tabel simpleks awal (didapatkan solusi dasar awal).

2

Tentukan variabel masuk berdasarkan kondisi optimalitas. Berhenti jika tidak ada lagi variabel masuk; pada tahapan ini, solusi optimal telah tercapai. Jika tidak, lanjutkan ke langkah 3.

3

Tentukan variabel keluar berdasarkan kondisi kelayakan.

4

Tentukan solusi dasar awal dengan menerapkan teknik Gauss-Jordan. Lanjutkan ke langkah 2.

27

Pemrograman Linier (2)

Recommend Documents