A. Metode Big M
Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar ( bentuk standar adalah memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk ≤ dan kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.
Masalah ini akan muncul bila kita akan mencari basis fesibel awal sehingga 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
a) Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack
b) 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).
B. Metode Dua Fase
Dalam menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, juga menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua phase.
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.
1. 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.
2. Fase 1
Digunakan untuk mencari basic fesibel awal. Pada fase 1 memiliki langkah-langkah dimana tujuannya adalahm 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 meyelesaiakan 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 adalah 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.
Pada fase kedua, tujuannya sama seperti fase pertama, yaitu untuk mendapatkan penyelesaian yang optimal dari suatu permasalahan yang ada. Fase dua berhenti sesuai dengan tujuan awal permasalahan.
3. Fase 2
Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan merupakan termasuk variabel dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2 ini memiliki langkah-langkah sebagai berikut:
1. Fungsi tujuan bisa memaksimalkan dan juga bisa meminimalkan tergantung pada permasalahan yang dihadapi.
2. Menggunakan fungsi batasan (s.t) dari fase 1, melakukan proses iterasi seperti biasanya dan berhenti sesuai funsi obyektif awal
C. 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.
a) Beberapa istilah dalam metode simpleks:
1. Solusi augmentasi merupakan sebuah solusi untuk variabel-variabel asli (variabel-variabel keputusan) yang telah diaugmentasi dengan nilai variabel-variabel slack yang bersesuaian.
2. Solusi titik sudut layak (corner-points feasible solution) atau CPF adalah titik perpotongan dari persamaan fungsi batasan yang memenuhi daerah fesibel.
3. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.
4. 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.
5. 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).
6. 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.
7. 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
b) Solusi basis layak (Basic Feasible Solution)
Solusi basis layak atau basic feasible solution merupakan solusi dari titik sudut layak (CPF) dimana nilai variabel-variabel asli (variabel-variabel keputusan) telah diagumentasi dengan nilai dari variabel-variabel slack yang bersesuaian.
Sifat-sifat solusi basis:
1. Setiap variabel ditunjuk sebagai variabel nonbasis atau sebagai variabel basis
2. Jumlah variabel basis sama dengan jumlah fungsi kendala (disebut persamaan). Oleh karena itu, jumlah variabel nonbasis sama dengan total jumlah variabel dikurangi jumlah fungsi kendala.
3. Variabel-variabel non basis ditetapkan sama dengan nol.
4. Nilai-nilai variabel basis ditetapkan sebagai solusi simultan dari sistem persamaan (fungsi kendala pada bentuk yang diaugmentasi)
5. Jika variabel basis memenuhi kendala nonnegatif, solusi basis adalah solusi BF.
c) Prosedur penyelesaian program linear dengan Metode Simpleks BFS
1. Formulasikan persoalan menjadi model linear
2. Tambahkan variabel Slack pada masing-masing constraint (pembatas) untuk memperoleh bentuk standar. Model ini digunakan untuk identifikasi solusi feasible awal dari pembatas bertanda lebih kecil atau sama dengan.
3. Inisialisasi : pemilihan x1 dan x2 sebagai variabel nonbasis (variabel diberi nilai nol) sebagai solusi BF awal didasarkan pada konsep semua variabel keputusan sama dengan nol sebagai solusi CPF awal. Pemilihan ini menghilangkan pekerjaan yang diperlukan untuk menyelesaikan variabel basis dari sistem pemrograman linier.
4. Uji optimalitas digunakan untuk menguji apakah variabel nonbasis menunjukkan laju perbaikan pada nilai Z jika variabel tersebut ditingkatkan nilainya dari nol (sementara ini variabel basis disesuaikan nilainya agar memenuhi sistem persamaannya). Jika laju perbaikan dari variabel tersebut positif maka solusi CPF yang bersebrangan memiliki penyelesaian lebih baik daripada CPF saat ini sehingga disimpulkan tidak optimal dan berlanjut ke langkah iterasi selanjutnya. Jika tidak ditemukan laju pergerakan ke arah positif maka solusi CPF saat ini merupakan solusi yang optimal dan prosedur pun selesai. Iterasi untuk menemukan BF yang baru dengan prosedur pencarian solusi simultan pada sistem pemrograman linier atau disebut metode eliminasi Gauss-Jordan. Kemudian melakukan uji optimalitas sampai tercapai solusi optimal.
d) Metode Simpleks Tabel
Metode simpleks adalah teknik untuk menyelesaikan program linier yang tidak mampu diselesaikan oleh metode grafis. Metode simpleks sendiri memiliki kerangka berpikir beberapa macam yaitu dengan menggunakan BFS (basis fesibel solution) dan metode simpleks dengan menggunakan tabel. Metode simpleks dengan menggunakan tabel hanya memuat tiga informasi penting yaitu koefisien pada variabel, konstanta pada ruas kanan persamaan dan variabel basis yang muncul untuk setiap persamaan.
Langkah langkah metode simpleks tabel:
1. Inisialisasi
Langkah pertama yaitu memasukkan variabel slack. Kemudian pilihlah variabel keputusan yang kemudian akan dijadikan sebagai variabel nonbasis awal. Lalu pilihlah varibel slack yang akan dijadikan sebagai variabel basis awal.
2. Uji Optimalitas
Dalam uji optimalitas, BFS saat ini dapat dikatakan optimal apabila setiap koefisien dalam baris nol adalah nonnegatif, sehingga langkah-langkah dalam metode simpleks tabel dapat selesai. Namun apabila setiap koefisien dalam baris nol adalah bukan nonnegatif, maka langkah selanjutnya adalah iterasi untuk mendapatkan BFS berikutnya.
3. Iterasi
a) Langkah 1:
Tentukanlah variabel basis yang masuk dengan memilih variabel dengan koefisien negatif yang mempunyai nilai absolut paling besar (paling negatif). Kemudian letakkanlah kotak di sekitar kolom dibawah koefisien tersebut, kolom ini sering disebut kolom sumbu atau pivot column.
b) Langkah 2:
Langkah selanjutnya yaitu dengan menentukan variabel basis yang keluar. Hal ini dapat dilakukan dengan menerapkan uji rasio minimum yaitu dengan cara:
Mengambil masing-masing koefiien dalam kolom sumbu yang positif
Membagi masing-masing angka pada ruas kanan dengan koefisien pada kolom sumbu dalam baris yang sama
tentukanlah baris mana yang mempunyai rasio yang paling kecil
variabel basis pada baris adalah variabel basis yang keluar, kemudian gantilah variabel itu dengan variabel basis yang masuk dalam kolom variabel basis tabel simpleks yang berikutnya.
Kemudian letakkanlah kota disekitar baris ini yang biasa disebut baris sumbu (pivot row) dan angka yang berada dalam baris sumbu dan kolom sumbu disebut angka sumbu (pivot number).
c) Langkah 3:
Langkah selanjutnya adalah carilah BFS baru dengan menggunakan operasi baris dasar. Hal ini dimaksudkan untuk membentuk tabel simpleks yang baru.
(drs-saukanihasan.blogspot.com/2012/06/operation-research.html)
Tidak ada komentar:
Posting Komentar