Metode Simpleks – Maksimasi (1)


Permasalahan penentuan jumlah produksi dari beberapa produk disuatu perusahaan sering dihadapi oleh manager produksi. Penentuan jumlah produksi untuk memaksimalkan keuntungan perusahaan dengan melihat keterbatasan sumber daya perusahaan tersebut dapat diselesaikan dengan menggunakan model program linier. Ada beberapa cara menyelesaikan masalah dengan model program linier, diantaranya yaitu diselesaikan dengan Metode Grafik. Secara umum metode grafik dapat memberi masukan berharga untuk program linier dan pemecahannya, tetapi metode ini hanya berlaku untuk dua variabel saja. Untuk mengatasi kesulitan ini, maka pada tahun 1947 diperkenalkan suatu metode yang dapat digunakan untuk memecahkan masalah-masalah program linier oleh George B. Dantzig yang dinamakan Metode Simpleks.

Metode simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah program linier yang didasarkan pada proses iterasi. Jadi pada prinsipinya prosedur ini diawali dengan penentuan suatu solusi awal yang secara terus-menerus diperbaiki hingga diperoleh solusi yang optimal.

Sebelum diselesaikan dengan menggunakan metode simpleks, terlebih dahulu masalah program linier harus diubah ke dalam bentuk formulasi model promram linier, yang pada umumnya berbentuk maksimasi. Setelah berbentuk suatu model formulasi program linier, maka model tersebut harus diubah terlebih dahulu ke dalam bentuk baku program linier. Setelah model berada dalam bentuk baku, maka dapat diterapkan prosedur penyelesaian dengan Metode Simpleks.

Ciri-ciri dari bentuk baku model Program Linier adalah

1. Semua kendala berupa pertidaksamaan dengan Nilai Kanan non negatif.

2. Semua variabel yang tidak terlibat dalam pertidaksamaan, dapat bernilai negatif.

3. Fungsi tujuan dapat berupa maksimum maupun minimum

Untuk memenuhi ciri-ciri tersebut, maka dibuat beberapa peraturan pengubahan bentuk yang tidak memenuhi bentuk baku ke dalam bentuk baku. Berikut langkah-langkanya :

PENGUBAHAN KE DALAM BENTUK BAKU (BENTUK KANONIK)

Pengubahan Kendala

1. Kendala yang berbentuk pertidaksamaan \leq diubah ke dalam Bentuk Kanonik dengan menambahkan suatu variable baru yang disebut Variabel Slack untuk setiap kendala. Variabel Slack ini menyatakan jumlah sumber daya yang tidak digunakan sumber daya yang diwakilinya.

Contoh 1.

2X_1 + 5X_2 \leq 10, diubah menjadi 2X_1 + 5X_2 + S_1 = 10

2.  Kendala yang sudah berbentuk persamaan juga perlu ditambahkan suatu variable yang dinamakan Variabel Artificial. Variabel ini perlu ditambahkan untuk membentuk matriks identitas pada Tabel Simpleks Awal. Pada akhir iterasi (solusi akhir), variable artificial tidak diperkenankan memiliki nilai yang tidak sama dengan nol. Jadi, apabila variable artificial mempunyai nilai tidak sama dengan nol, maka solusi yang diperoleh dinyatakan sebagai solusi yang tak layak.

Contoh 2.

2X_1 + 5X_2 = 10, diubah menjadi 2X_1 + 5X_2 + A_1 = 10

3. Kendala yang berbentuk pertidaksamaan \geq diubah ke dalam Bentuk Kanonik dengan menambahkan suatu variable baru yang disebut Variabel Surplus (negative dari Variabel Slack) dan Variabel Artificial untuk setiap kendala. Variabel Surplus perlu ditambahkan untuk mengubah kendala menjadi persamaan. Karena Variabel Surplus mempunyai koefesien -1, maka perlu ditambahkan Variabel Artificial untuk membentuk suatu matriks identitas pada pada Tabel Simpleks Awal.

Contoh 3.

2X_1 + 5X_2 \geq 10, diubah menjadi 2X_1 + 5X_2 -S_1 + A_1 = 10

4. Kendala yang mempunyai Nilai Kanan bernilai negative, diubah dengan mengalikannya dengan -1. Selanjutnya tanda pertidaksamaanya juga berubah, dari \leq menjadi \geq serta dari \geq menjadi \leq.

Contoh 4.

2X_1 + 5X_2 \leq -10, diubah menjadi -2X_1 -5X_2 \geq 10. Selanjutnya karena pertidaksamaanya \leq, maka perlu ditambahkan variable slack, sehingga menjadi -2X_1 -5X_2 + S_1 = 10

5X_1 + 8X_2 \geq -40, diubah menjadi -5X_1 -8X_2 \leq 40. Selanjutnya karena pertidaksamaanya \geq, maka perlu ditambahkan variable surplus dan artificial, sehingga menjadi -5X_1 -8X_2 -S_1 + A-1 = 40

Pengubahan Variabel

Variabel yang bernilai tak terbatas (unrestricted) berarti bahwa variable tersebut dapat bernilai positif maupun negative. Sedangkan diketahui bahwa bentuk baku program linier untuk simpleks mensyaratkan semua variable bernilai non negative sehingga untuk variable yang bernilai tak terbatas perlu diubah ke dalam bentuk variable bernilai non negative. Pengubahan tersebut dilakukan dengan cara menjadikan variable tersebut menjadi selisih dua variable yang bernilai non negative.

Contoh 5.

Maksimumkan : Z = 4000X_1 + 5000X_2

terhadap kendala

X_1 + 2X_2 \leq 40

3X_1 + 2X_2 \leq 120

X_1 \geq 0 dan X_2 tak terbatas

Agar X_2 bernilai non negative maka X_2 diganti oleh variable X_2'-X_2'', sehingga formulasi berubah menjadi.

Maksimumkan : Z = 4000X_1 + 5000X_2

terhadap kendala

X_1 + 2X_2' -2X_2'' \leq 40

3X_1 + 2X_2' -2X_2'' \leq 120

X_1, X_2', X_2'' \geq 0

Bentuk Baku dari formulasi diatas adalah

Maksimumkan : Z = 4000X_1 + 5000X_2' -5000X_2'' + 0S_1 + 0S_2

terhadap kendala

X_1 + 2X_2'-2X_2'' + S_1 = 40

3X_1 + 2X_2' -2X_2'' + S_2 = 120

X_1, X_2', X_2'', S_1, S_2 \geq 0

Setelah mengetahui bagaimana cara mengubah bentuk formulasi program linier ke dalam bentuk baku, apa langkah selanjutnya ? Selanjutnya adalah langkah awal penyelesaian Metode Simpleks, yaitu pembuatan Tabel Simpleks  Awal (baca : Metode Simpleks – Maksimasi (2)).

 

Iklan

One comment on “Metode Simpleks – Maksimasi (1)

  1. Ping-balik: Metode Simpleks – Maksimasi (2) | Math IS Beautiful

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s