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 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.

, diubah menjadi

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.

, diubah menjadi

3. Kendala yang berbentuk pertidaksamaan 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.

, diubah menjadi

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

Contoh 4.

, diubah menjadi . Selanjutnya karena pertidaksamaanya , maka perlu ditambahkan variable slack, sehingga menjadi

, diubah menjadi . Selanjutnya karena pertidaksamaanya , maka perlu ditambahkan variable surplus dan artificial, sehingga menjadi

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 :

terhadap kendala

dan tak terbatas

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

Maksimumkan :

terhadap kendala

Bentuk Baku dari formulasi diatas adalah

Maksimumkan :

terhadap kendala

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)).