tugas prolin

Nama: Mulyadi

Nim: G1D 008 018

Hal: Tugas

PROGRAM LINIER

  • Metode Simplex

Persoalan dalam kehidupan sehari-hari yang diselesaikan dengan program linier tidak selalu sederhana dan semudah sebagaimana yang diberikan pada bangku-bangku sekolah. Kesederhanaan yang dimaksud mungkin terbatas pada dua variable saja, akan tetapi bagaimana kalau dihadapkan dengan lebih dari dua variable dan banyaknya pelibatan pembatas (constraint)?. Dan sangat tidak memungkinkan jika kita menggunakan prosedur penyelesaian dengan metode grafik yang masih dalam ruang lingkup cakupannya sangat sempit. Oleh karena itu, prosedur yang mampu menjawabnya hanyalah prosedur yang mempunyai cakupan luas, yaitu metode simplex, kelebihannya selain itu, juga mampu membuat tangga lompatan dalam bidang riset dan sangat banyak diterapkan dalam berbagai applikasi computer.

(sigma dari j=1 _n)aijXj>=bi………………….1

(sigma dari j=1 _n)aijXj<=bi…………………..2

(sigma dari j=1 _n)aijXj=bi……………….….3

Dari ke-3 kendala tersebut, dan fungsi kendala yang masih berbentuk pertidaksamaan harus diubah dalam bentuk persamaan biasa dengan ketentuan sebagai berikut.

jika berbentuk seperti ini, maka ditambahkan variable pengetat misal “si”, maka persamaan akan menjadi
dan jika berbentuk  maka ditambahkan variable pengetat “(–si)”, maka persamaan menjadi .

Persamaan fungsi kendala utama yang telah ditambahkan variable pengetat biasa disebut persamaan bentuk kanonik.

Jika menemukan fungsi kendala utama kurang dari maka logikanya untuk membuat sama maka tentunya ditambahkan dengan sesuatu, dan sebaliknya jika fungsi kendalanya lebih besar dari maka dikurangi variable hingga sama.

Dari pengenalan diatas dapat disusun algoritma program linier dengan metode simplex

Langkah 1 Mengubah fungsi kendala/batasan dalam bentuk kanonik

Langkah 2 Mengubah fungsi tujuan dengan memaksimumkan atau meminimumkan menjadi persamaan dengan me nolkan fungsi tujuan, misal z=x1+x2+0s1+0s2 menjadi z-x1-x2-0s1-0s2=0

Langkah 3 Membuat table simplex

Langkah 4 Menentukan kolom kunci dengan memilih z yang paling negative untuk maksimasi dan sebaliknya untuk minimasi

Langkah 5 Menentukan baris kunci dengan mengambil indeks positif terkecil setelah bi dengan kolom kunci

Langkah 6 Menentukan angka kunci yang merupakan perpotongan dari kolom dan baris kunci

Langkah 7 Operasi Baris Elementer (OBE) untuk memaksimasi atau meminimasi

Langkah 8 Jika belum maksimasi atau minimasi maka langkah 4-7 diulang kembali hingga tercapai optimum

Langkah 9 Maksimasi ditandai denganz>=0dan minimasi  z<=0

Agar benar-benar dipahami secara keseluruhan maka telaah contoh dibawah ini dengan seksama.

Misal pada suatu perusahaan tas didapatkan datanya berupa

Fungsi tujuan untuk memaksimalkan perolehan pendapat, yaitu:

Max. Z = 3X1 + 2X2

2X1 + 2X2    800

2X1 + 3.3X2  1000

1X1 + 0.5X2  300

2X1 + 1.5X2 <= 650

Solusi

Langkah 1 mengubah dalam bentuk kanonik

2X1 + 2X2   + S1                         =800

2X1 + 3.3X2       + S2                  =1000

1X1 + 0.5X2             +S3 =300

2X1 + 1.5X2                   +S4       = 650

Langkah 2. memaksimumkan fungsi tujuan

Z = 3X1 + 2X2+0S1+0S2+0S3+0S4

Z -3X1 – 2X2-0S1-0S2-0S3-0S4=0

Langkah 3 mengxisi tabel simple

Dv X1 X2 S1 S2 S3 S4 bi
Z -3 -2 0 0 0 0 0
S1 2 2 1 0 0 0 800
S2 2 3.3 0 1 0 0 1000
S3 1 0.5 0 0 1 0 300
S4 2 1.5 0 0 0 1 650

Langkah 4 menentukan kolom kunci, yaitu pada kolom x1

Dv X1 X2 S1 S2 S3 S4 bi
Z -3 -2 0 0 0 0 0
S1 2 2 1 0 0 0 800
S2 2 3.3 0 1 0 0 1000
S3 1 0.5 0 0 1 0 300
S4 2 1.5 0 0 0 1 650

Langkah 5 menentukan baris kunci, yaitu baris pada s3

Dv X1 X2 S1 S2 S3 S4 bi index
Z -3 -2 0 0 0 0 0 0
S1 2 2 1 0 0 0 800 400
S2 2 3.3 0 1 0 0 1000 500
S3 1 0.5 0 0 1 0 300 300
S4 2 1.5 0 0 0 1 650 325

Langkah 6 menentukan angka kunci, yaitu 1 pada baris di s3

Dv X1 X2 S1 S2 S3 S4 bi
Z -3 -2 0 0 0 0 0
S1 2 2 1 0 0 0 800
S2 2 3.3 0 1 0 0 1000
S3 1 0.5 0 0 1 0 300
S4 2 1.5 0 0 0 1 650

Langkah 7 operasi OBE

Dv X1 X2 S1 S2 S3 S4 bi
Z 0 -0.5 0 0 3 0 900
S1 0 1 1 0 -2 0 200
S2 0 2.3 0 1 -2 0 400
S3 1 0.5 0 0 1 0 300
S4 0 0.5 0 0 -2 1 50

Langkah 8 operasi OBE yang kedua

Dv X1 X2 S1 S2 S3 S4 bi
Z 0 0 0 0 -1 -1 950
S1 0 0 1 0 2 -2 100
S2 0 0 0 1 7.2 -4.6 170
S3 1 0 0 0 3 -1 250
S4 0 1 0 0 -4 2 100

Langkah 9 karena pada OBE ke-2 sudah maksimaum, maka

Karena  z>=0pada OBE yang ke-2 maka titik optimum sudah bisa terlihat dengan…

X1=250

X2=100

S1=100

S2=170

Zmax=950

Interpretasi Solusi Optimal

Dari baris evaluasi neto tidak lagi ditemukan nilai positif yang berarti

solusi yang diperoleh sudah maksimum, yaitu X1 = 250, X2 = 100 dan nilai

fungsi tujuan Zj = 950 ( dalam puluhan ribu rupiah)

Dari tabel tersebut diketahui S1 = 100 dan S2 = 170 yang berarti waktu

kerja pada bagian pemotongan masih tersisa (slack) 100 jam sedangkan sisa

waktu pada bagian penjahitan adalah 170 jam. Pada bagian lainnya

(penyelesaian, pemeriksaan & pengepakan) seluruh waktu kerja sudah habis

digunakan.

Merujuk kembali pada gambar terdahulu diketahui bahwa solusi optimal

bergerak mulai dari titik ekstem 1 dengan solusi awal X1=0, X2=0, S1=800,

S2=1000, S3=300, S4=650 dan menghasilkan nilai fungsi tujuan nol. Pada

iterasi pertama variabel X1 memasuki basis dan mengakibatkan variabel S3

menjadi non basic variabel. Solusi basic kedua berada pada titik ekstem 2

yaitu X1=300, X2=0, S1=200, S2=400, S3=0, dan S4=50 serta menghasilkan

nilai 900 pada fungsi tujuan. Pada iterasi selanjutnya X2 memasuki basis

mendorong S4 untuk keluar. Hal ini menyebabkan solusi bergerak kearah sumbu

X2 menuju titik ekstem 3. Pada titik ini solusi yang didapat sudah optimum

yaitu X1=250, X2=100, S1=100, S2=170, S3=0 dan S4=0 sedangkan nilai fungsi tujuan maksimum yaitu 950.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: