Metode Simpleks – Maksimasi (2)

Pada tulisan sebelumnya Metode Simpleks – Maksimasi (1) dibahas mengenai bagaimana mangubah formulasi program linier ke dalam Bentuk Baku atau Bentuk Kanonik. Selanjutnya pada tulisan ini akan dibahas langkah selanjutnya dalam penggunaan Metode Simpleks, yaitu membuat Tabel Simpleks Awal.

BENTUK TABEL SIMPLEKS AWAL

Pada tabel di atas terlihat bahwa terdapat kolom Variabel Dasar, yang merupakan solusi awal. Pada table simpleks awal yang berperan sebagai variable dasar adalah variable tambahan yang bernilai positif, yaitu variable slack, surplus dan artificial. Selanjutnya akan terjadi perubahan yang menjadi variable dasar dengan adanya Variable Masuk (entering variable) dan Variable Keluar (leaving variable).

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.

Hungarian : Masalah Minimisasi (Minimal)

Langkah-langkah penyelesaian dengan metoda Hungarian untuk masalah minimisasi adalah sebagai berikut :

1. Ditentukan nilai terkecil dari setiap baris, lalu mengurangkan semua nilai dalam baris tersebut dengan nilai terkecilnya.
   
2. Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan ke langkah 3,bila belum,dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kilom tersebut dikurangkan dengan nilai terkecilnya.
   
3. Ditentukan apakah terdapat n elemen nol dimana tidak ada nilai nol yang berada pada baris/kolom yang sama, dimana n adalah jumlah kolom/baris. Jika ada, maka tabel telah optimal, jika tidak, dilanjutkan ke langkah 4.

Hungarian : Masalah Maksimasi (Maksimal)

Langkah-langkah penyelesaian dengan metode Hungarian untuk masalah maksimasi adalah sebagai berikut :

1. Ditentukan nilai terbesar dari setiap baris, lalu mengurangkan semua nilai pada setiap baris dari nilai terbesarnya.
   
2. Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan ke langkah 3,bila belum,dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya.

Penugasan (Assigment Problem)

Masalah penugasan (assignment problem), seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam pemerograman linier (linear programming). Dalam masalah penugasan kita akan mendelegasikan sejumlah tugas (assignment) kepda sejumlah penerima tugas (assignee) dalam basis satu-satu. Jadi pada masalah penugasan ini diasumsikan bahwa jumlah assignment sama dengan jumlah assignee. Jadi data pokok pertama yang harus dimilki dalam menyelesaikan suatu masalah penugasan adalah assignment dan jumlah assignment.

Metode Branch and Bound

Terdapat beberapa metode untuk menghasilkan batasan-batasan khusus yang akan memaksa pemecahan optimum dari masalah program linier yang dilonggarkan untuk bergerak kearah pemecahan integer yang diinginkan. Salah satunya yang umum digunakan adalah metode Branch and Bound.

Masalah Optimasi Program Linier

Optimasi Fungsi Tanpa Kendala

Bila diberikan fungsi satu peubah : x y = (x) x , yang terdiferensialkan n+1 kali, maka lewat penderetan Taylor di sekitar x₀ dapat disimpulkan bahwa

Bila (x₀) = ¹(x₀) = … = ⁿ(x₀) = 0

                        = ⁿ⁺¹(x₀) 0

Cara Membentuk Model Program Linier

Pemerograman linear berasal dari kata pemerograman dan linear. Pemerograman disini mempunyai arti kata perencanaan dan linear ini berarti fungsi-fungsi yang digunakan merupakan fungsi linear.

Secara umum arti dari pemerograman linear adalah suatu teknik perencanan yang bersifat analitis yang analisis-analisisnya memakai model matematika, dengan tujuanmenemukan beberapa kombinasi alternative pemecahan masalah, kemudian dipilih yang terbaik diantaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai tujuan dan sasaran yang diinginkan secara optimal.