Tugas 1 RO :Metode Simpleks

Program Linear dengan Metode Simpleks

Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks. Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eliminasi Gaus Jordan. penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu persatu dengan cara perhitungan iteratif. sehingga penentuan solusi optimal dengan simpleks dilakukan dengan tahap demi tahap yang disebut dengan iterasi.

Metode simpleks ini adalah metode yang biasanya digunakan untuk memecahkan setiap permasalahan pada pemrograman linier yang kombinasi variabelnya terdiri dari tiga variabel atau lebih. Metode simplex merupakan sebuah metode lanjutan dari metode grafik. Metode grafik tidak dapat menyelesaikan persoalan manajemen yang memiliki variabel keputusan yang cukup besar, sehingga untuk menyelesaikannya dibutuhkan sebuah metode yang lebih kompleks yaitu dengan menggunakan program komputer QSB ( Quantitative System For Business) atau menggunakan metode simplex. Dalam kenyataanya penggunaan komputer lebih efisien, akan tetapi metode dasar yang digunakan dalam pengoperasian komputer tetap metode simplex.

Metode simplex adalah metode yang dapat digunakan untuk menyelesaikan persoalan manajerial yang telah diformulasikan terlebih dahulu ke dalam persamaan matematika program linear yang mempunyai variable keputusan mulai dari lebih besar atau sama dengan 2 (dua) sampai multivariable. Sedangkan metode grafik hanya dapat digunalan apabila jumlah variable keputusan maksimal 2 (dua) buah. Sehingga dapat disimpulkan bahwa suatu persoalan linear programing yang diselesaikan dengan metode grafik juga dapat diselesaikan dengan metode simpleks, sebaliknya suatu persoalan yang hanya bisa diselesaikan dengan metode simplex tidak dapat diselesaikan dengan metode grafik.

Beberapa ketentuan yang  perlu diperhatikan, antara lain:
1. Nilai kanan (NK / RHS) fungsi tujuan harus nol (0)
2. Nilai kanan (RHS) fungsi kendala harus positif, apabila negatif nilai tersebut harus dikalikan -1.
3. Fungsi kendala dengan tanda “≤ atau ≥”  harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/ surplus disebut juga variabel dasar.

Langkah-langkah yang harus dipahami dalam menggunakan metode simpleks, yaitu:

1.  Membuat model matrix LP

2.  Merubah formulasi LP menjadi formulasi standar

Merubah formulasi biasa ke dalam formulasi standar harus mengikuti kaidah dasar yang berlaku, yaitu:

1. Introduksikan variabel baru sebagai variable dummy dengan singkatan huruf S sebagai singkatan dari Slack (kekurangan) atau Surplus (kelebihan)
2. Variable slack kita introduksikan apabila kita mempunyai bentuk tanda pembatas lebih kecil atau sama dengan (≤)
3. Variabel surplus kita introduksikan apabila kita mempunyai bentuk tanda pembatas lebih besar dari atau sama dengan (≥)

    3.  Menyiapkan table simplex awal

	Cj
Ci	BV	X1	X2	Xn	S1	S2	Sn	Bi
	S1
	S2
	Sn
	Zj
Cj-ZJ

Penjelasan penggunaan tabel simplex :

a.     Kolom Baris

·         Kolom baris selalu ada dan ditempatkan di kolom paling kiri setelah Ci

·         Untuk kolom tabel awal variabel yang pertama kali kita tulis pada kolom ini adalah:

o    Variabel tambahan yang bertanda positif seperti slack variable

o    Artifisial variabel

Oleh karena itu, surplus variabel tidak pernah kita masukan ke dalam kolom basis pada tabel awal

b.     Kolom Cj

Kolom koefisien fungsi tujuan diletakan pada baris pertama tabel awal simplex. Angka koefisien dapat kita lihat pada fungsi tujuan formulasi standar daro persoalan yang dihadapi.

c.      Kolom diantara kolom Cj dan kolom  paling kanan atau kolom nilai ruas kanan

Jumlah kolom ini bervariasi tergantung berapa jumlah variabel yang ada di dalam fungsi tujuan formulasi standar. Oleh karena itu apabila terjadi kesalahan dalam membuat formulasi standar maka penyelesaian persoalan dengan metode simplex juda akan salah.

d.     Kolom nilai ruas kanan (NRK atau Bi)

Pada kolom ini, dituliskan nilai ruas kanan dari setiap batasan yang ada di dalam setiap persoalan yang dihadapi.

e.      Jumlah baris

Jumlah baris di antara baris Basic variabel dengan baris Zj tergantung dari berapa buah batasan yang kita hadapai di dalam perseoalan.

f.      Baris Zj

Baris Zj digunakan untuk mendapat nilai Shadow Price atau Nilai Merginal Value Product dari setiap variabel yang kita hadapi. Angka yang akan kita tuliskan pada baris Zj ini adalah angka hasil penjumlahan perkalian setiap koefisien dari variabel yang tertera dalam kolom baris dengan angka-angka di dalam Matrix

g.     Baris Cj-Zj

Baris ini bermanfaat bagi kita untuk melihat kapan kita berhenti melakukan iterasi atau baris yang dapat membantu kita menentukan apakah penyelesaian optimal telah kita capai.

4.  Memasukan nilai-nilai dan variable dalam formulasi standar ke dalam tabel awal
5.   Melakukan proses literasi

a.     Tentukan kunci kolom (pivot coloum)

Caranya adalah memilih nilai Cj-Zj yang terbesar dan positif.

b.    Tentukan kunci baris (pivot row)

Caranya adalah memilih dasil bagi antara NRK dengan angka-angka yang ada dalam kolom kunci, kemudian pilih hasil bagi yang terkecil dan positif. Hasil bagi dengan nilai negative, nol dan tak terhingga tidak dapat dijadikan sebagai kunci baris.

c.   Cari angka baru yang terdapat pada baris kunci dengan cara membagi semua angka yang terdapat pada baris kunci dengan angka kunci. Angka kunci adalah angka yang terdapat pada persilangan baris kunci dengan kolom kunci.

d.     Mencari angka baru pada baris yang lain dengan rumus:

Angka baru = nilai pada baris lama – (perkalian koefisien pada kolom kunci dengan angka baru baris kunci)

e.   Apabila sosialisasi optimal belum ditemukan maka kembali ke langkah 5a di atas, sehingga nilai yang terdapat pada baris Cj-Zj ≤ 0.

6.  Menentukan apakah penyelesaikan optimal sudah tercapai

7.  Membuat kesimpulan jawaban

Contoh penyelesain program linier dengan menggunakan metode simpleks

 PT Yummy food memiliki sebuah pabrik yang akan memproduksi dua jenis produk yaitu vanilla dan violette. Untuk memproduksi kedua produk tersebut diperlukan bahan baku A, bahan baku B dan jam tenaga kerja. Maksimum pengerjaan bahan baku A adalah 60kg per hari, bahan baku B 30kg per hari dan tenaga kerja 40jam per hari. Kedua jenis produk memberikan sumbangan keuntungan sebesar Rp40,00 untuk vanilla dan Rp30,00 untuk violette. Masalah yang dihadapi adalah bagaimana menentukan jumlah unit setiap produk yang akan diproduksi setiap hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat pada tabel berikut ini

Jenis bahan baku dan tenaga kerja	Kg bahan baku dan jam tenaga kerja		Maksimum Penyediaan
	Vanilla	Violette
Bahan baku A	2	3	60Kg
Bahan baku B	-	2	30Kg
Tenaga Kerja	2	1	40jam
Sumbangan keuntungan	Rp40,00	Rp30,00

Penyelesaian:

Z = Rupiah keuntungan per hari

X1 = Jumlah vanilla yang diproduksi/hari

X2 = jumlah violette yang diproduksi/hari

Langkah 1

Formulasi LP (bentuk standar

Fungsi tujuan       :   Zmax = 40X1 + 30X2

Fungsi kendala     :   I.  2X1 + 3X2 ≤ 60

                            II.  2X2 ≤ 30

                            III. 2X1 + 1X2 ≤ 40

                            IV. X1,X2 ≥ 0

Diubah menjadi:

2X1 + 3X2 + S1 + 0S2 + 0S3 = 60

           2X2 + 0S1 + S2 + 0S3 = 30

2X1 + 1X2 + 0S1 + 0S2 + S3 = 40

40X1 + 30X2 + 0S1 + 0S2 + 0S3

C1 = 40, C2 = 30, C3 = 0, C4= 0, C5 = 0 

Langkah 2

Tabel simplex awal masalah PT Yummy Food

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
0	S1	2	3	1	0	0	60
0	S2	0	2	0	1	0	30
0	S3	2	1	0	0	1	40
	Zj	0	0	0	0	0	0
Cj-ZJ		40	30	0	0	0

Langkah 3

Apakah tabel tersebut sudah optimal?

Belum, karena tabel optimal bila nilai yang terdapat pada baris Cj – Zj ≤ 0

Langkah 4

Penyelesaian dengan cara iterasi

1.     Menentukan kolom kunci, yaitu kolom yang memiliki nilai Cj-Zj terbesar yaitu kolom x1. Dengan demikian x1 akan masuk dalam basis

2.      Menentukan baris kunci, yaitu baris yang memiliki angka indeks terkecil dan bukan negatif. Dalam hal ini baris s3. Dengan demikian s3 akan keluar dari basis dan tempatnya akan digantikan oleh x1

3.    Menetukan angka kunci. Angka kunci adalah angka yang terdapat pada persilangan kolom kunci dengan baris kunci, dalam hal ini angka kunci = 2

4.   Mencari angka baru yang terdapat pada baris kunci, dengan cara membagi semua angka yang terdapat pada baris kunci dengan angka kunci

     Angka baru = 40/2, 2/2, ½, 0/2, 0/2, ½ ; atau = 20, 1, ½, 0,0 ½

5.      Mencari angka baru pada baris lain, yaitu :

     Baris S1

            Angka lama                       = [ 60 2 3 1 0 0 ]

            Angka baru                        = [ 20 1 ½ 0 0 ½] (2)

            Angka baru                        = [20 0 2 0 0 -1]

Baris S2

           Angka lama                       = [ 30 0 2 0 1 0]

           Angka baru                        = [ 20 1 ½ 0 0 1/2] (0)

           Angka baru                        = [ 30 0 2 0 1 0]

Hasil perhitungan di atas, akan nampak pada tabel baru simplex yaitu tabel yang merupakan hasil iterasi pertama.

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
0	S1	0	2	1	0	-1	20
0	S2	0	2	0	1	0	30
40	X1	1	½	0	0	½	20
	Zj	40	20	0	0	20
Cj-ZJ		0	10	0	0	0

Tabel iterasi 1 belum optimal sehingga harus diulang langkah di atas dan akan di dapat tabel iterasi 2:

	Cj	40	30	0	0	0
Ci	BV	X1	X2	S1	S2	S3	Bi
30	X1	0	1	½	0	-1/2	10
0	S2	0	0	-1	1	1	10
40	S3	1	0	-1/4	0	¾	15
	Zj	40	30	5	0	15
Cj-ZJ		0	0	-5	0	-15	900

Solusi optimum tabel iterasi 2 menunjukan bahwa total nilai Z = 900 dengan masing-masing variabel keputusan X1 = 15 dan X2 = 10.

Variabel basis	Koefisien fungsi tujuan	Nilai variabel basis
X2	30	10	300
S2	0	10	0
X1	40	15	600
		JUMLAH	900

KESIMPULAN

1.      Pada tabel iterasi 2 merupakan tabel akhir simplex, dengan solusi optimal adalah :

X1 (vanilla)                 = 15 unit

X2 (violette)                = 10 unit

Z (keuntungan)           = Rp 900,00

2.     Kendala kedua (bahan baku B) masih tersisa sebanyak 10 Kg yang ditunjukan oleh nilai S2 =10, pada tabel optimal

3.    Kendala 1 dan 3 tidak ada sisa (full capacity), yang ditunjukan oleh nilai S1 = S3 = 0 (variabel nonbasis). Hal ini juga dapat dibuktikan dengan memasukan nilai S1 dan S2 ke dalam kendala 1 dan 3.

       Kendala 1 :           2X1 + 3X2 = 60

2 (15) + 3 (10) = 60

                                                60 = 60

Bahan baku yang digunakan = yang tersedia

Kendala 3 :             2X1 + 1X2 = 40

                                    2 (15) + 1(10) = 40

                                                40 = 40

            Jam kerja yang digunakan = yang tersedia

Sumber :

http://martinkoa.blogspot.co.id/2016/05/operasi-riset-program-linear-dengan.html