MATERI 3 ( PROGRAM LINEAR METODE SIMPLEX )

PROGRAM LINEAR  (METODE SIMPLEX)

Metode simpleks digunakan untuk memecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan.

Prosedur Metode Simpleks.

1. Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

2. Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

3. Membuat Table Simpleks Awal

4. Algoritma metode simpleks

PROGRAM LINEAR : BENTUK STANDAR

1.       Ruas kanan (RK) fungsi tujuan harus nol (0)

2.       Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.

3.       Fungsi kendala dengan tanda “ ” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

4.       Fungsi kendala dengan tanda “ ” diubah ke bentuk “ ” dengan cara mengalikan dengan –1, lalu diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1, karena bertanda negatif.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standa

- Ada tiga bentuk fungsi kendala:  , ≥, dan =.

- Konversi fungsi kendala bertanda : menambahkan slack variable pada fungsi kendala tersebut.

- Untuk kendala berbentuk ‘’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.

- Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.

- Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala

LANGKAH2 METODE SIMPLEKS MASALAH MAKSIMASI

Langkah 1:
Mengubah fungsi tujuan dan kendala menjadi “bentuk standar”

Langkah 2:
Memindahkan bentuk standar ke dalam tabel.

Langkah 3:
Memilih entering & leaving Variabel

a) Pilih entering variabel di antara var. non basis yg mempuyai koefisien negatif terbesar pada persamaan / baris untuk maksimasi atau pilih koef. positif terbesar baris Z untuk minimasi.

b) Bagilah RK (kecuali pers. Z) dengan unsur yang bersesuaian pada kolom entering, hasil bagi dinyatakan sebagai Ratio

c) Pilih leaving var. diantara var. basis yang mempunyai

  Ratio terkecil, persamaan di mana leaving var. berada disebut pers. poros. Elemen poros merupakan perpotongan antara kolom entering dengan pers.poros.

d)  Susun kembali tabel Simpleks berikutnya dengan mengganti variabel leaving dengan var . Entering.

e) Tentukan persamaan poros yang baru (baris di mana entering var. menggantikan leaving var.), dengan : Pers. Poros yang baru = Pers. Poros yang lama / Elemen

f)Tentukan persamaan yang lainnya (termasuk Z) sbb. :

Pers. yang baru = Pers. yang lama – (koef. Kolom entering) x pers. poros baru

g) Kemudian ulangi kembali langkah 3.1. s/d 3.6 sampai kondisi optimal tercapai (semua koef.pada pers. Z sudah berharga positip atau nol untuk (maksimasi) dan berharga negatip atau nol untuk (minimasi).

CONTOH METODE SIMPLEKS MASALAH MAKSIMASI

*Maksimumkan Z = 3X1 + 5X2

*Berdasarkan kendala (constrain)           

                                (1)          2X1                                        ≤ 8

                                (2)                            3X2                       ≤ 15

                                (3)          6X1 + 5X2                             ≤ 30

                                (4)          X1 ≥ 0,  X2 ≥ 0

PEMECAHAN MASALAH

Langkah-langkah metode simpleks

Langkah 1:
Mengubah fungsi tujuan dan kendala menjadi “bentuk standar” 

Fungsi tujuan

                Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.

Fungsi kendala diubah menjadi persamaan dg menambahkan var. slack, sebagai berikut :

                (1) 2X1                  ≤ 8   menjadi      2X1         +     X3                                   =  8

                (2) 3X2                  ≤ 15 menjadi             3X2     + X4                                     = 15

                (3) 6X1 + 5X2      ≤ 30 menjadi      6X1 + 5X2                                + X5    = 30

*Variabel slack adalah variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan*

PEMECAHAN MASALAH : METODE SIMPLEKS LANJUTAN

Bentuk Standar :

Fungsi tujuan :

                                Maksimumkan Z - 3X1 - 5X2 = 0

Fungsi kendala

                (1)          2X1                  + X3                                 =  8

                (2)                      3X2                      +  X4                = 15

                (3)          6X1  +   5X2                         + X5          = 30

                (4)  X1 ,X2  ,X3  , X4 , X5 ≥  0

Langkah 2: Memindahkan bentuk standar ke dalam tabel.

Z = 3X1 + 5X2

               diubah menjadi Z - 3X1 - 5X2 + 0X3 + 0X4 + 0X5   = 0.

(1) 2X1                  ≤ 8   menjadi      2X1                  + X3                              =  8

(2) 3X2                  ≤ 15 menjadi                      3X2                 + X4               = 15

(3) 6X1 + 5X2      ≤ 30 menjadi      6X1 +     5X2                             + X5   = 30

1.     Tabel simpleks yang pertama

Variabel Basis	Z	X1	X2	X3	X4	X5	RK
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

Variabel Basis	Z	X1	X2	X3	X4	X5	RK	Ratio
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

Tabel 1. : pemilihan var. entering pada tabel pertama

Jika persamaan/baris Z (fungsi tujuan) sudah positip atau nol (ingat ini masalah maksimasi), maka solusi yang dicari sudah optimal.

Variabel Basis	Z	X1	X2	X3	X4	X5	RK	Ratio
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15	ABAIKAN
X5	0	6	5	0	0	1	30	15/3 = 5
Z								30/5 = 6
X3
X2
X5	0	0	1	0	1/3	0	15/3

                                                                                                                                                 

Tabel 1. : penentuan ratio terkecil, pers. poros, elemen poros, dan var. leaving (keluar)

Tabel 1 : menentukan pers. poros yg. Baru dan pers. yang baru lainnya

Pers. poros yang baru = Pers. poros yang lama / elemen poros

Pers.  baru = pers. lama – (elemen poros) x pers. poros yang baru

Z lama		[-3	-5	0	0	0,	0 ]
(-5)xp.baru	(-5)	[ 0	-5	0	- 5/3	0,	- 25 ]	( - )
Z baru	=	[-3	0	0	5/3	0,	25]

Pers. X5

X5 lama		[ 6	5	0	0	1,	30 ]
(5)xp.baru	(5)	[ 0	5	0	5/3	0,	25   ]	( - )
X5 baru	=	[ 6	0	0	-5/3	1,	5   ]

Tabel Simpleks 1 dan 2, terlihat koef. Pers. Z masih ada yang < 0 à blm. Optimal

Variabel Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30
Z	1	-3	0	0	5/3	0	25
X3	0	2	0	1	0	0	8
X2	0	0	1	0	1/3	0	5
X5	0	6	0	0	-5/3	1	5

Pers. yang baru

Pers. Z

Z lama		[-3	0	0	5/3	0,	25 ]
(-3)xp.baru	(-3)	[ - 3	0	0	-15/18	-3/6,	-15/6]	( - )
Z baru	=	[ 0	0	0	5/6	½,	271/2]

Pers. X3

X3 lama		[ 2	0	1	0	0,	8 ]
(2)xp.baru	(2)	[ 2	0	0	-5/9	2/6,		10/6]	( - )
X3 baru	=	0	0	1	5/9	-1/3,		61/3]

Pers. X2 tidak berubah karena koef. Enteringnya = 0

X2 lama		[ 0	1	0	1/3	0,	5 ]
(0)xp.baru	(0)	[ 1	0	0	-5/18	1/6,	5/6]	( - )
X2 baru	=	0	1	0	1/3	0,	5]

Tabel simpleks final hasil perubahan

Variabel Basis	Z	X1	X2	X3	X4	X5	RK
Z	1	0	0	0	5/6	½	271/2
X3	0	0	0	1	5/9	-1/3	61/3
X2	0	0	1	0	1/3	0	5
X1	0	1	0	0	-5/18	1/6	5/6

Koef. Pers. Z tidak ada lagi yang bernilai negatif (≥ 0). Sehingga tabel final memberikan solusi yang optimal.

Dari tabel final didapat

X1 = 5/6

X2 = 5

Zmaksimum = 27,5

                                                                                                                                                  Contoh Soal

Perusahaan Mebel Ais memproduksi lemari jenis A, B, dan C. Produk tersebut diproses melalui tiga departemen: pertukangan, pengecatan, dan penyelesaian. Setiap unit lemari A membutuhkan 3 jam tenaga kerja di departemen pertukangan, 2 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Setiap unit lemari B membutuhkan 4 jam tenaga kerja di departemen pertukangan, 5 jam tenaga kerja di departemen pengecatan, dan 2 jam tenaga kerja di departemen penyelesaian. Dan, setiap unit lemari C membutuhkan 3½ jam tenaga kerja di departemen pertukangan, 1 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Kapasitas yang tersedia pada departemen pertukangan, departemen pengecatan, dan departemen penyelesaian adalah 400 jam, 360 jam, dan 250 jam, masing-masing. Harga jual masing-masing produk adalah Rp 10 (lemari A), Rp 15 (lemari B), dan Rp 12 (lemari C). Bagaimana usul Anda dalam memproduksi lemari, agar diperoleh keuntungan yang maksimal ?