Label

Senin, 14 Mei 2012

Linier Programming Bentuk Non Standart Metode Simpleks


Linier Programming Bentuk Non Standart Metode Simpleks

1.1       Menyelesaikan Persoalan LP dengan pembatas bertanda ≥ dan atau =
                 Ciri – ciri berbentuk non standart :
·         Fungsi Kendala biasanya berbentuk = atau dengan ≥
·         Fungsi Tujuan juga dapat berbentuk Maksimisasi danMinimisasi
·         Non Standart Fungsi Kendala
1.      ≤ + Si
2.      = + Si
3.      ≥ - Si
Dalam membicarakan mengenai metode simpleks, kita telah menggunakan variable slock sebagai solusi basis awal sedemikian sehingga masing – masing merupakan ruas kanan yang berharga positif pada masing – masing persamaan. Sekarang perhatikan untuk kasus yang persamaan pembatasnya tidak lagi bertanda (≤) tetapi (=) atau (≥). Untuk kasus yang persamaan pembatasnya bertanda (=), daerah fisibelnya hanya berupa segmen garis sehingga kita tidak dapat memperoleh solusi fisibel basis awal karena tidak ada variable slack yang dapat digunakan sebagai variable baris awalnya.

1.2 Tekhnik Dua fase
                 Dengan digunakannya konstanta M yang merupakan bilangan positif yang sangat besar sebagai penalty, maka bisa terjadi kesalahan perhitungan, terutama apabila perhitungan itu dilakukan dengan menggunakan computer. Kesalahan itu bisa terjadi karena koefisien fungsi tujuan relative sangat kecil dibandingkan dengan harga M, sehingga computer akan memperlakukannya sebagai koefisien yang berharga Nol. Sebagai contoh, apabila pada persoalan tekhnik M diatas ditetapkan harga M = 100.000, maka koefisien X1 dan X2 pada fungsi tujuannya menjadi ( 300.000 – 3 ) dan ( 400.000 – 5 ).   
                 Kesulitan ini bisa dikurangi dengan menggunakan tekhnik dua fase. Disini konstanta M dihilangkan dengan cara menyelesaikan persoalan dalam dua fase ( dua tingkatan ) sebagai berikut :
Fase 1 :
Fase ini digunakan untuk menguji apakah persoalan yang kita hadapi memiliki solusi fisibel atau tidak. Pada fase ini fungsi tujuan semula diganti dengan meminimumkan jumklah variable artifisialnya. Jika nilai minimum fungsi tujuan baru ini berharga nol ( artinya seluruh variable artifisia berharga nol ), berate persoalan memiliki solusi fisibel, lanjutkan ke fase dua. Tetapi, jika nilai minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki solusi fisibel. STOP.

Fase 2 :
Gunakan solusi basis optimum dari fase 1 sebagai solusi awal bagi persoalan semula. Dalam hal ini ubahlah bentuk fungsi tujuan fase 1 dengan mengembalikannya pada fungsi tujuan persoalan semula. Pemecahan persoalan dilakukan seperti biasa.


1.3 Untuk menyelesaikan Persoalan Program Linier dengan Metode Simpleks untuk fungsi tujuan
Memaksimumkan dan meminimumkan caranya berbeda.
Model matematika dari Permasalahan Program Linier dapat dinyatakan dalam bentuk Sistem
Persamaan Linier (AX = B) sebagai berikut :
*) Fungsi Tujuan (Z = CX):
Z = C1 C2 _ Cn 
*) Fungsi Kendala (AX atau B):
Berikut ini langkah-langkah penyelesaian Persoalan Program Linier fungsi tujuan memaksimumkan
dengan Metode Simpleks.
1.      Mengubah semua kendala ke Bentuk Kanonik (yang semula menggunakan tanda pertidaksamaan menjadi persamaan) dengan menambah perubah (variabel) Slack S. Perubah-perubah slack yang da dimasukkan (ditambahkan) ke fungsi sasaran dan diberi koefisien 0.
2.      Apakah dalam matriks A = [aij] (pada fungsi kendala) sudah terbentuk Matriks Identitas (In) ?

2.1 Apabila dalam matriks A sudah terbentuk Matriks Identitas maka disusun tabel awal
simpleks sebagai berikut :
Cj C1 C2 ... Cn 0 0 ... –M ….
Ci Xj X1 X2 ... Xn S1 S2 ... V1 …… bi Ri Xi
Z2 ... Zn ... ...
Zj - Cj Z1-C1 Z2-C2 …. Zn-Cn

Keterangan :
*) Baris Cj diisi dengan para koefisien Fungsi Tujuan (sasaran)
*) Baris Xj diisi dengan nama-nama perubah (variabel) yang ada.
*) Kolom Xi diisi dengan nama-nama perubah yang menjadi basis (variabel yang
menyusun matriks Identitas) .
*) Kolom Ci diisi dengan para koefisien perubah yang menjadi basis
*) Kolom bi diisi dengan para konstanta fungsi kendala (Nilai Sebelah Kanan/NSK).
*) Baris Zj diisi dengan rumus Zj = ij
 (aik = elemen-elemen yang berada dalam kolom
kunci, dan Ri dihitung hanya untuk aik _ 0)
Selanjutnya dilanjutkan ke langkah 3,

2.2 Jika belum terbentuk matriks identitas, maka matriks identitas ditimbulkan (dimunculkan)
dengan menambah perubah semu dan diberi notasi (V). Perubah semu yang ada dimasukan
di fungsi sasaran, sedangkan koefisien dari variabel semu pada fungsi sasaran diberi nilai (-
M), dengan M adalah bilangan yang cukup besar. Dilanjutkan ke langkah 2.1
3. Penelitian terhadap nilai Zj - Cj. (Tabel sudah maksimum jika semua Zj - Cj 0).
3.1 Jika untuk semua Zj - Cj 0 dilanjutkan ke langkah 4,
3.2 Jika ada Zj - Cj < 0, maka dibuat tabel baru dengan cara sebagai berikut :
3.2.1 Menentukan kolom kunci yaitu memilih nilai Zj - Cj yang terkecil (Min{ Zj - Cj}.
Sebut dengan Zk - Ck maka kolom ke-k disebut kolom kunci.
3.2.2 Pada kolom ke-k dilakukan pemeriksaan terhadap nilai aik.
3.2.2.1 Jika untuk semua aik negatif maka jawab tidak terbatas
(Unbounded).
3.2.2.2 Jika terdapat aik yang positif hitung nilai Ri, (untuk aik yang positif
saja) kemudian dilanjutkan ke langkah 3.2.3,
3.2.3    Menentukan baris kunci, yaitu dengan memilih nilai Ri yang terkecil (diantara
yang positif) Min{ Ri}, namakan Rr, maka baris ke-r disebut baris kunci.
3.2.4    Kemudian disusun tabel baru sebagai berikut (dimulai dari baris kunci baru):
3.2.4.1             Untuk elemen baris r baru = elemen baris r lama dibagi ark , atau
3..2.4.2            Untuk elemen baris i yang lain,
elemen baris i baru = elemen baris i lama - (aik x elemen baris r baru)
atau a ij a ij (a ik xa rj )
Kemudian tentukan lagi nilai Xi, Ci, Zj , Zj - Cj. Kembali ke langkah 3.
4. Apakah pada tabel terakhir terdapat nilai Vk yang positip ?
4.1 Jika ada nilai Vk yang positif maka soal asli tidak fisibel (Infeasible Solution).
4.2 Jika tidak ada nilai Vk yang positif maka akan diperoleh penyelesaian yang maksimum.
1.4 Kendala Berlambang ≥

Di soal-soal sebelumnya, kita selalu berurusan dengan kendala yang berlambang . Kendala dengan lambang dapat dengan mudah dijadikan "=" dengan penambahan satu variabel Slack.

Sebagai contoh:

dapat diubah menjadi:
dimana

Akan tetapi, untuk kendala yang berlambang , cara yang sama tidak dapat digunakan. Perhatikan contoh di bawah.

mungkin kalian pikir, kendala di atas bisa diubah menjadi seperti berikut:
dimana
(di sini, S disebut sebagai variabel Surplus, bukan Slack)
Kelihatannya sih benar.. Namun, solusi awal simplex selalu dimulai dari titik (0,0). Artinya, ketika dan , maka akan bernilai negatif, sehingga akan melanggar syarat nonnegativitas..

Jadi, bagaimana cara agar syarat nonnegativitas ini tidak dilanggar?
Ans: Salah satu caranya adalah dengan membuat suatu VARIABEL ARTIFICIAL yang berfungsi untuk menampung nilai RHS untuk sementara. Variabel ini untuk selanjutnya harus di-nol-kan, agar variabel Slack dapat memainkan peranannya.

Dengan demikian, yang benar adalah sebagai berikut:

dapat diubah menjadi:
dimana DAN harus di-nol-kan

Kita dapat mengecek kebenarannya, dengan memasukkan dan , maka sekarang akan bernilai nol dan .

Nah, bagaimana cara kita membuat VARIABEL ARTIFICIAL menjadi nol?
Ans: Di fungsi objektif tambahkan HAMBATAN variabel ini dengan konstanta yang sangat besar sekali.. Konstanta ini kita beri simbol .. (Teknik ini sering disebut dengan teknik M)


Sebagai contoh:
1.
Jika adalah fungsi maksimum, tambahkan di ruas yang berlawanan
2.
Jika adalah fungsi minimum, tambahkan di ruas yang berlawanan
dimana M adalah bilangan yang sangat besar sekali (bisa kalian anggap sebagai 999999)
Jika ada kendala, maka definisikan kembali dimana




Tidak ada komentar:

Poskan Komentar