Metode Simplex

DESKRIPSI METODE SIMPLEKS

 

Metode simpleks merupakan salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier. Penentuan solusi optimal didasarkan pada teknik eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat solusi grafik) satu persatu denagan cara perhitungan interaktif. Sehingga penentuan solusi optimal dengan simpleks dilakukan dengan thap demi tahap yang disebut interasi.

Perbedaan kedua metode diatas sangat jelas, bahwa metode grafik hanya mampu digunakan untuk dua kendala saja. Namun metode simpleks mampu menyelesaikan masalah dengan lebih dari dua kendala. Itu artinya metode simpleks memiliki minimal tiga kendala didalamnya.

Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks.  Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya :

1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.
2. Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas  dalam sistem persamaan.
3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan  pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama  dengan  jumlah fungsi pembatas (tanpa fungsi non negatif).
4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas  awal yang ada, karena aktivitas belum dilaksanakan.
5. Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.
6. Variabel surplus adalah variabel yang dikurangkan  dari model matematik kendala untuk mengkonversikan  pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.
7. Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.
10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.
11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.
12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.

BENTUK BAKU

Sebelum melakukan perhitungan iteratif untuk menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah.

Ada beberapa hal yang harus diperhatikan dalam membuat  bentuk baku, yaitu :

1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.
2. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.
3. Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).

PENGAMATAN

Disebuah desa Temboro Kecamatan Karas Kabupaten Magetan, terdapat sebuah industri kecil yang dalam industrinya membuat tahu. Pak Ngalimin yang memiliki industri tersebut , pak ngalimin merintis industry tahu ini sudah cukup lama beliau menjalalani usaha ini mulai tahun 1998- sekarang berarti sekitar 14 tahun pak ngalimin menggeluti usaha tahu ini. Asal mula beliau merintis usaha ini adalah salah satunya untuk meningkatkan perekonomiannya, karena beliau dulu hanyalah seorang buruh karyawan dalam pabrik tahu juga di Surabaya selama 3 tahun. Kemudian pak ngalimin mencoba untuk memulai usaha tahu sendiri di rumahnya dengan ilmu yang di dapat dari dia bekerja sebagai buruh karyawan pabrik tahu. Setelah beliau memulai usahanya dari dengan dibantu istrinya semakin lama usaha pak ngalimin berkembang pesat dari beliau dengan dibantu istrinya sekarang pak ngalimin sudah memilki karyawan berjumlah 10 orang. Usaha yang di rintisnya semakin lama semakin berkembang meskipun ada kendala-kendala yang dihadapinya, namun pak ngalimin tetap bertahan dan berusaha agar usahanya mendapatkan untung yang maksimal.

Setiap pagi sekitar jam 4 pagi para karyawan sudah memulai membuat tahu. Setiap harinya kedelai yang dibutuhkan lebih kurang 250 kg kedelai, dengan 10 karyawan tahu yang diproduksi membutuhkan waktu 4 jam jadi sekitar jam 8 pagi tahu-tahu tersebut siap dipasarkan dan diambil para pelanggan dan diantar ke toko-toko dan warung-warung.  Setiap hari tahu-tahunya tidak sepi dari pelanggan. Banyak pelanggan yang membeli tahunya untuk dijual lagi di pasar, di toko-toko, atau di warung-warung. Tahu yang diproduksi ada 3 macam jenis tahu yaitu tahu kecil, tahu besar, tahu jumbo. Tapi yang sering dibeli sama pelanggan yaitu tahu yang berukuran besar dan jumbo, karena yang laris di pasar atau di toko yaitu tahu yang berukuran besar dan jumbo.

Pak ngalimin selalu berusaha agar pelanggan-pelangganya tidak pergi, salah satunya dengan menjaga kualitas rasa tahu tersebut. Tahu yang diproduksi ini tidak kalah enak dengan tahu yang dibuat oleh pabrik-pabrik tahu yang besar dan terkemuka, karena tahu yang dibuat ini tidak mengandung bahan-bahan kimia yang dilarang,jadi tahunya masih alami dan enak dan aman kalau dikonsumsi. Tapi tak selalu berhasil maksimal dalam pembuatan tahu, kadang bahan untuk pembuatan tahu yaitu coko kebanyakan jadi tahu yang dihasilkan kurang maksimal dan akibatnya dalam penjualan juga tidak maksimal. Ada juga pelanggan yang beli disitu setelah melihat hasil tahunya kurang maksimal pelanggan itu tidak jadi membeli dan pindah langganan , tapi pak ngalimin tidak kecewa atau bagaimana tapi beliau tetap berusaha agar pelanggan beli ditempatnya.

LAPORAN DATA

Dalam setiap hari yang Pak ngalimin memproduksi tahu kecil, besar, dan jumbo. Kedelai yang disediakan adalah jenis . Setiap tahu kecil membutuhkan 26,3kg kedelai dan 1,25 kg garam serta menbutuhkan coko 0,65 kg. Untuk membuat tahu besar membutuhkan 53,8 kg kedelai dan 4 kg garam serta membutuhkan 0,48 kg coko. Kemudian yang terakhir adalah tahu jumbo membutuhkan 65 kg kedelai dan 5,5 kg garam serta membutuhkan 0,5 kg coko. Dari pembuatan tahu  kecil didapatkan keuntungan sebesar Rp 20.000,00 , sedangkan pembuatan tahu besar keuntungan yang diperoleh yaitu sebesar Rp 35.000,00 , dan Rp 45.000,00 untuk keuntungan pembuatan tahu jumbo. Pak Ngalimin mempunyai persediaan bahan baku kedelai maksimal 250 kg dan persediaan bahan baku untuk garam sekanyak 60 kg dan coko sebanyak 20 kg. Masalahnya adalah berapa banyak tahu kecil, tahu besar, dan tahu jumbo yang akan dibuat mengingat kendala-kendala yang disebutkan diatas dan bagaimana Pak Ngalimin mampu mendapatkan untung yang sebesar- besarnya.

Berikut adalah contoh bahan baku yang akan digunakan dalam pembuatan tahu kecil, tahu besar, dan tahu jumbo :

 ANALISA DATA

Dari data diatas maka dapat di buat tabel permasalahan sebagai berikut :

Jenisbahan	Kecil	besar	jumbo	Persediaan
Kedelaigaram coko	26,3 1,25 0,65	53,8 4 0,48	65 5,5 0,5	250 60 20

Dari data maka dapat dibuat x₁ sebagai tahu kecil, x₂ sebagai tahu besar, dan x₃ sebagai tahu jimbo. Maka kendala yang harus dipenuhi yaitu sebagai berikut :

26,3 x₁ + 53,8 x₂ + 65 x₃ ≤ 250

1,25 x₁ + 4 x₂ + 5,5 x₃ ≤ 60

0,65 x₁ + 0,48 x₂ + 0,5x₃ ≤ 20

x₁ , x₂, x₃ ≥ 0

Langkah-langkah :

Mengubah fungsi tujuan dan fungsi kendala (lihat ketentuan yang harus diperhatikan).

Fungsi tujuan :

Maksimumkan Z = 20.000 x₁ + 35.000 x₂ + 45.000 x₃

Z – 20.000 x₁ – 35.000 x₂ – 45.000 x₃

Z – 20 x₁ – 35 x₂ – 45 x₃    (dalam ribu rupiah)

Fungsi kendala :

1)   26,3 x₁ + 53,8 x₂ + 65 x₃ ≤ 250

26,3 x₁ + 53,8 x₂ + 65 x₃ + sx₄ = 250

2)   1,25x₁ + 4 x₂ + 5,5 x₃ ≤ 60

1,25 x₁ + 4 x₂ + 5,5 x₃ + sx₅ = 60

3)   0,65 x₁ + 0,48 x₂ + 0,5x₃ ≤ 20

0,65 x₁ +0,48 x₂ + 0,5x₃ + sx₆ = 20

(sx₄, sx₅, dan sx₆ adalah variabel slack)

Menyusun persamaan-persamaan ke dalam tabel :

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	-20	-35	-45	0	0	0	0
SX4	0	26,3	53,8	65	1	0	0	250
SX5	0	1,25	4	5,5	0	1	0	60
SX6	0	0,65	0,48	0,5	0	0	1	20

Memilih KOLOM KUNCI

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif dengan angka terbesar.

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	-20	-35	-45	0	0	0	0
SX4	0	26,3	53,8	65	1	0	0	250
SX5	0	1,25	4	5,5	0	1	0	60
SX6	0	0,65	0,48	0,5	0	0	1	20

Memilih BARIS KUNCI dan KOLOM KUNCI

Baris kunci adalah baris yang mempunyai indeks terkecil.

Var. Dasar	Z	X1	X2	X3	X4	X5	X6	NK	Index
Z	1	-20	-35	-45	0	0	0	0
X4	0	26,3	53,8	65	1	0	0	250	3,8
X5	0	1,25	4	5,5	0	1	0	60	10,9
SX6	0	0,65	0,48	0,5	0	0	1	20	40

Angka kunci               Koefisien angka kolom kunci

• Ø
• Ø
• Ø

Mengubah nilai-nilai baris kunci  dengan cara membaginya dengan angka kolom kunci.

NBBK (Nilai Baris Baru Kunci) =

• Ø
• Ø
• Ø
• Ø
• Ø

Dari penghitungan diatas maka diperoleh nilai baris baru yaitu sebagai berikut :

[ 0      0,4      0,8     1          1,53     0          0          3,8 ]

Sehingga diperoleh tabel seperti berikut :

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	-20	-35	-45	0	0	0	0
SX5	0	1,25	4	5,5	0	1	0	60	10,9
SX6	0	0,65	0,48	0,5	0	0	1	20	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci

(selain baris kunci) = 0

Baris baru = baris lama – ( koefisien angka kolom kunci × nilai baris baru kunci ).

Baris Z

Baris lama                           [ -20     -35       -45      0          0          0         0  ]

NBBK                    -50       [ 0,4     0,8        1        1,53     0          0         3,8]  _

Baris baru                           [ 0          5       -5         76,5     0          0          190]

Baris Sx₅

Baris lama                           [ 1,25   4          5,5      0         1          0          60]

NBBK                    5,5       [ 0,4     0,8       1         1,53    0          0          3,8]  _

Baris baru                           [-0,95  -0,4      0         8,4      1         0           20,9]

Baris Sx₆

Baris lama                           [0,65    0,48     0,5       0          0          1          20]

NBBK                    0,5       [0,4      0,8       1          1,53     0          0          3,8]  _

Baris baru                           [0,45   0,08     0           8,4       0         1         18,1]

Masukan nilai diatas ke dalam tabel, sehingga tabel menjadi seperti berikut :

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	0	5	-5	76,5	0	0	190
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Karena Z masih memuat nilai negatif maka harus dilakukan kembali perbaikan – perbaikan sampai baris Z tidak memuat nilai negatif.

Memilih KOLOM KUNCI

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	0	5	-5	76,5	0	0	190
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Memilih BARIS KUNCI

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	0	5	-5	76,5	0	0	190
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Angka kunci                                        Koefisien angka kolom kunci

• Ø
• Ø
• Ø

Mengubah nilai-nilai baris kunci  dengan cara membaginya dengan angka kolom kunci.

NBBK (Nilai Baris Baru Kolom Kunci) =

• Ø
• Ø
• Ø
• Ø
• Ø

Dari penghitungan diatas maka diperoleh nilai baris baru yaitu sebagai berikut :

[ 0      0,4      0,8     1          1,53     0          0          3,8 ]

Sehingga diperoleh tabel seperti berikut :

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	0	5	-5	76,5	0	0	190
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci

(selain baris kunci) = 0

Baris baru = baris lama – ( koefisien angka kolom kunci × nilai baris baru kunci ).

Baris Z

Baris lama                           [ 0        5          -5         76,5     0          0         190]

NBBK                    -5         [ 0,4     0,8         1        1,53     0          0         3,8]  _

Baris baru                           [ 2        9            0        84,1     0          0         209]

Baris Sx₄

Baris lama                           [ -0,95   -0,4    0         8,4      1          0          20,9]

NBBK                    0          [ 0,4        0,8    1         1,53    0          0          3,8 ]  _

Baris baru                           [-0,95     -0,4   0         8,4      0          0          20,9]

Baris Sx₅

Baris lama                           [0,45   0,08     0             8,4     0           1         18,1]

NBBK                    0          [ 0,4     0,8      1            1,53   0            0        3,8 ]  _

Baris baru                           [0,45  0,08       0            8,4     0           1         18,1]

Masukkan hasil yang diperoleh ditas ke dalam tabel seperti berikut ini :

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	2	9	0	84,1	0	0	209
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Dari penghitungan diatas sudah diperoleh hasil tidak lagi ditemukan nilai negatif pada Z, maka tidak perlu lagi dilakukan penghitungan seperti diatas. Sehingga diperoleh iterasi – iterasi sebagai berikut :

Iterasi 1

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	0	5	-5	76,5	0	0	190
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Iterasi 2         Optimal

Var. Dasar	Z	X1	X2	X3	SX4	SX5	SX6	NK	Index
Z	1	2	9	0	84,1	0	0	209
SX5	0	-0,95	-0,4	0	8,4	1	0	20,9	10,9
SX6	0	0,45	0,08	0	8,4	0	1	18,1	40
X3	0	0,4	0,8	1	1,53	0	0	3,8	3,8

Dari table diatas maka diperoleh solusi optimalnya yaitu : X₃ = 3,8 dan Z_max= 209.