Pemograman linier menggunakan model matematika untuk menggambarkan suatu masalah. Sifat linier di sini berarti semua fungsi matematika harus berupa fungsi linier, sedangkan kata pemrograman berarti perencanaan. Sehingga pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai tujuan yang terbaik (menurut model matematika) diantara semua kemungkinan alternatif yang ada. Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut.
- Metode Big M
Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar. salah satu contoh masalah dalam kendala fungsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif. Fungsi kendala dengan pertidaksamaan ≥ mempunyai surplus variable, tidak ada slack variables. Surplus variable tidak bisa menjadi variabel basis awal, dengan demikian harus ditambahkan satu variabel baru yang dapat berfungsi sebagai variabel basis awal.
Sebelum mencari variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala fungsional dan teknik ini disebut dengan teknik variabel artifisial. Ada pun prosedur mendapatkan BF awal pada kendala fungsional adalah sebagai berikut :
- Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack
- Tugaskan pinalty yang besar
Berilah nilai variabel artifisial dengan nilai > 0 sehingga koefisien variabel artifisial menjadi M (big m) secara simbolik yang menunjukkan bahwa variabel artifisial tersebut memiliki angka positif raksasa ( dan pengubahan atas variabel artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal disebut metode big m).
- Metode Dua Fase
Menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, dapat menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua fase. Pada dasarnya Metode dua fase (phase) sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan pemrograman linier yang memiliki bentuk yang tidak standar. Berikut ini adalah prosedur menggunakan metode dua fase :
- Inisialisasi
Menambahkan variabel-variabel artifisal pada fungsi kendala yang memiliki bentuk tidak standar. Variabel artificial ini ditambahkan pada fungsi batasan yang pada mulanya memiliki tanda (³). Hal ini digunakan agar dapat mencari solusi basic fesibel awal.
- Fase 1
Digunakan untuk mencari basic feasible awal. Pada fase 1 memiliki langkah-langkah dimana tujuannya adalah meminimalkan variabel artifisial ( Min Y= Xa)
s.t : Ax = b
X = 0
Pada fase pertama bertujuan untuk memperoleh penyelesaian yang optimum dari suatu permasalahan. Pada fase pertama fungsi tujuan selalu minimum variabel artificial, meskipun permasalahan yang ada adalah permasalahan yang maksimum. Dalam meyelesaikan pada fase pertama, yaitu membuat nilai nol dulu pada variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0 bernilai £ 0. Fase pertama dianggap telah selesai atau memperoleh penyelesaian yang optimal apabila variabel artifisial adalah merupakan variabel basis, sedangkan apabila variabel artifisial adalah variabel non basis, maka masalah dianggap tidak mempunyai penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang kedua.
- Fase 2
Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan termasuk variabel dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1.
- Metode Simpleks
Metode simpleks adalah salah satu teknik penyelesaian pemrograman linier selain menggunakan metode grafis. Metode simpleks diaplikasikan pada komputer dan metode tersebut sangat membantu untuk permasalahan pemrograman linier yang rumit karena menggunakan fungsi dan variabel yang banyak dan tak mampu diselesaikan oleh metode grafis. 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).
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 :
- Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.
- Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.
- Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).
Sumber :
http://www.academia.edu/11623031/METODE_BIG_M
http://berbagidenganmahasiswa.blogspot.co.id/2014/08/metode-2-fase.html
http://awank38.blogspot.co.id/2015/01/metode-simpleks-dalam-program-linier.html
