ms2011-modul 3-pemrograman linear-simpleks.ppt · persamaan menambahkan variabel slack ke fungsi...

Pemrograman Linier

Manajemen Sains

Pemrograman Linier

(Metode Simpleks)

Eko PrasetyoTeknik Informatika

Univ. Muhammadiyah Gresik 2011

Komponen dasar� Variabel keputusan

yang kita cari untuk ditentukan

� Objective (tujuan)

yaitu ingin mengoptimalkan (memaksimalkan atau

meminimalkan)

Teknik Informatika UMG 20112

meminimalkan)

� Constraints

yaitu solusi yang harus dicapai.

LP metode Simpleks� Mengonversi constraint yang masih dalam bentuk

pertidaksamaan menjadi persamaanmenggunakan bantuan variabel slack.

� Nilai di sisi kanan harus non negatif.

� Constraint yang menggunakan tanda ≤


� merupakan representasi batas ketersediaan

� sumber daya, dimana sisi kiri adalah representasipenggunaan sumber daya oleh aktivitas (variabel) model.

� Perbedaan antara sisi kanan dan sisi kiri tanda ≤

merupakan sejumlah sumber daya yang belumdigunakan atau slack.

Langkah-langkah awal sebelum

menggunakan metode simpleks

� Mengonversi pertidaksamaan (≤ atau ≥) menjadi persamaan

� Menambahkan variabel slack ke fungsi tujuan dengan koefisien nol

� Memindahkan komponen sisi kanan fungsi tujuan


� Memindahkan komponen sisi kanan fungsi tujuan ke sisi kanan

Mengonversi pertidaksamaan (≤ atau

≥) menjadi persamaan� Mengonversi pertidaksamaan (≤) menjadi persamaan (=), sebuah

variabel slack nonnegative ditambahkan pada sisi kiri constraint. � Kasus Reddy Mikks, constraint yang menyatakan penggunakan bahan

baku M1 diberikan oleh : 6x1 + 4x2 ≤ 24� Definisikan s1 sebagai variabel slack dari M1, maka constraint dapat

dikonversi menjadi : 6x1 + 4x2 + s1 = 24, s1 ≥ 0

� Constraint dengan tanda ≥, menyatakan batas terendah aktivitas model program linear, sehingga jumlah yang dinyatakan disisi kiri melewatibatas minimal yang direpresentasikan sebagai surplus.


batas minimal yang direpresentasikan sebagai surplus.

� Konversi dari ≥ ke = dicapai dengan mengurangi dengan variabelsurplus non negatif dari sisi kiri pertidaksamaan. Misalnya, dalam kasusOzark Farm, constraint yang menyatakan kebutuhan makanan : x1 + x2 ≥ 800

� Definisikan r1 sebagai variabel surplus, constraint dapat dikonversimenjadi persamaan berikut : x1 + x2 - r1 = 800, r1 ≥ 0

Mengonversi pertidaksamaan (≤ atau

≥) menjadi persamaan (cont’d)

� Untuk kasus dimana sisi kanan constraint bernilai negatif, maka harus dilakukan perkalian kedua sisi dengan -1 setelah langkah diatas dilakukan. Misalnya constraint : -x1 + x2 ≤ -3

� Maka bentuk persamaannya menjadi :


� Maka bentuk persamaannya menjadi :

-x1 + x2 + r1 = -3, r1 ≥ 0

� Selanjutnya kedua sisi dikalikan dengan -1, sehingga sisi kanan bernilai positif :

x1 - x2 - r1 = 3

Menambahkan variabel slack ke

fungsi tujuan dengan koefisien nol

� Pada kasus model Reddy Mikks, fungsi tujuan :

Z = 5x1 + 4x2

dengan 4 variabel slack menjadi :

Z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4


Memindahkan komponen sisi kanan

fungsi tujuan ke sisi kanan

� Pada kasus model Reddy Mikks, fungsi tujuan :

Z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4

Berubah menjadi :

Z - 5x1 - 4x2 - 0s1 - 0s2 - 0s3 - 0s4 = 0


Langkah-langkah metode Simpleks

1. Menentukan awal basis solusi layak

2. Memilih variabel masuk menggunakan syarat

keoptimalan. Berhenti jika tidak ada lagivariabel masuk, solusi terakhir adalah solusioptimal. Jika tidak maka ke langkah 3.


optimal. Jika tidak maka ke langkah 3.

3. Memilih variabel keluar menggunakan syarat

kelayakan.

4. Menentukan solusi dasar yang barumenggunakan perhitungan Gauss-Jordan. Kembali ke langkah 2.


(cont’d)

� Syarat keoptimalan (optimality condition).

� Variabel masuk dalam kasus pemaksimalan

(peminimalan) adalah variabel nonbasis yang

mempunyai koefisien negatif terbesar (pemaksimalan)

atau positif terbesar (peminimalan) dalam baris -z-row.

� Syarat optimal dicapai pada iterasi dimana semua


� Syarat optimal dicapai pada iterasi dimana semua

koefisien z-row dari variabel nonbasis tidak negatif

(pemaksimalan) atau tidak positif (peminimalan)

� Syarat kelayakan (feasibility condition).

� Untuk kedua masalah pemaksimalan dan peminimalan,

variabel keluar adalah variabel basis yang dikaitkan

dengan rasio non negatif terkecil.

Operasi baris Gauss-Jordan1. Menentukan baris kunci :

� Gantilah variabel keluar dalam kolom basis

dengan variabel masuk

� Baris kunci baru = Baris kunci ÷ elemen kunci

2. Mengganti nilai baris yang lain :


2. Mengganti nilai baris yang lain :

� Baris baru = Baris lama – koefisien kolom kunci ×

Baris kunci baru


(cont’d)� Variabel basis adalah variabel yang berkontribusi

(mempunyai nilai) memberikan solusi yang diminta.

� Variabel nonbasis adalah variabel yang tidakberkontribusi (bernilai 0) dalam pemberian solusi.

� Inisialisasi dalam metode simpleks :x1, x2, … adalah variabel non basis


1 2

s1, s2, … adalah variabel basis

� Dalam iterasi metode simpleks, satu persatuvariabel slack akan berubah menjadi variabel non basis karena keluar dari solusi dasar (variabelkeluar), dan variabel keputusan akan berubahmenjadi variabel basis karena masuk ke basis solusi (variabel masuk).

Program Linier pada kasus

memaksimalkan� Perusahaan Reddy Mikks memproduksi cat interior dan exterior dari

dua bahan baku, M1 dan M2.

� Tabel dibawah ini adalah informasi mengenai kebutuhan bahan baku, ketersediaan, dan keuntungannya.

� Survey pasar menunjukkan bahwa kebutuhan perhari untuk cat interior tidak boleh melebihi cat exterior lebih dari 1 ton, juga kebutuhan harianmaksimal untuk cat interior adalah 2 ton.

� Reddy Mikks ingin menentukan jumlah optimal (terbaik) produk antara


� Reddy Mikks ingin menentukan jumlah optimal (terbaik) produk antaracat interior dan exterior dengan memaksimalkan total keuntunganharian.

Produk

Kebutuhan bahan

baku (ton)Keuntungan

(x1000)M1 M2

Cat Ext 6 1 5

Cat Int 4 2 4

Kapasitas 24 6 Z

Program Linier pada kasus Reddy

Mikks(cont’d)� Konversi model Reddy Mikks menjadi :

� Kendala :

� 6x1 + 4x2 + s1 = 24 (bahan baku M1) (1)

� x1 + 2x2 + s2 = 6 (bahan baku M2) (2)

� -x1 + x2 + s3 = 1 (batas pasar) (3)

� x2 + s4 = 2 (batas kebutuhan) (4)


� x2 + s4 = 2 (batas kebutuhan) (4)

� x1, x2, s1, s2, s3, s4 ≥ 0

� Maksimalkan Z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 +0s4

� Variabel s1, s2, s3, dan s4 adalah variabel slack yang dikaitkan dengan constraint yang bersangkutan.

� Fungsi tujuan diubah menjadi :� Z - 5x1 - 4x2 - 0s1 - 0s2 - 0s3 - 0s4 = 0

Program Linier pada kasus Reddy

Mikks(cont’d)

Basis Z x1 x2 s1 s2 s3 s4 Solusi

Z 1 -5 -4 0 0 0 0 0 z-row

s1 0 6 4 1 0 0 0 24 s1-row

s2 0 1 2 0 1 0 0 6 s2-row

s3 0 -1 1 0 0 1 0 1 s3-row

s4 0 0 1 0 0 0 1 2 s4-row


s4 0 0 1 0 0 0 1 2 s4-row

Syarat Optimal dan Layak� Solusi dari fungsi Z = 5x1 + 4x2 yang ditunjukkan oleh tabel

dapat ditingkatkan dengan meningkatkan x1 dan x2.

� Untuk variabel yang akan masuk sebagai variabel basis dipilih nilai variabel nonbasis yang mempunyai nilaikoefisien positif terbesar.

� Karena fungsi tujuan dalam tabel simpleks adalah Z – 5x1– 4x2 = 0, variabel masuk akan dikaitkan pada variabel


– 4x2 = 0, variabel masuk akan dikaitkan pada variabeldengan koefisien negatif terbesar dalam fungsi tujuan.

� Aturan ini disebut dengan syarat optimal.

� Mekanisme penentuan variabel keluar dari tabel simpleksdilakukan dengan menghitung rasio non negatif dari sisikanan persamaan (kolom Solusi) pada koefisien constraint yang bersangkutan dengan variabel masuk seperti yang ditunjukkan pada tabel berikut :

Syarat Optimal dan Layak

BasisMasuk

Solusi Rasiox1

s1 6 24 x1 = 24/6 = 4 � minimal

s2 1 6 x1 = 6/1 = 6

s3 -1 1 x1 = 1/-1 = -1 (diabaikan)

s 0 2 x = 2/0 = ∞ (diabaikan)


s4 0 2 x1 = 2/0 = ∞ (diabaikan)

Kesimpulan : x1 masuk dan s1 keluar� Proses penukaran didasarkan pada operasi Gauss-Jordan.

� Operasi ini menjadikan kolom variabel masuk sebagai kolom kunci danvariabel keluar sebagai baris kunci.

� Elemen yang tepat menjadi anggota kolom kunci dan baris kuncidisebut elemen kunci.

� Tabel akan diupdate berdasarkan baris dan kolom yang dihighlight.

Baris kunci dan kolom kunci

Masuk

↓


Z 1 -5 -4 0 0 0 0 0

Keluar � s 0 6 4 1 0 0 0 24 Baris kunci


Keluar � s1 0 6 4 1 0 0 0 24 Baris kunci

s2 0 1 2 0 1 0 0 6

s3 0 -1 1 0 0 1 0 1

s4 0 0 1 0 0 0 1 2

Kolom

kunci

Operasi Gauss-Jordan untuk

menghasilkan solusi baru (iterasi 1)Baris kunci

Ganti s1 pada kolom Basis dengan x1

Baris x1 baru = Baris s1 ÷ elemen kunci= [0 6 4 1 0 0 0 24] / 6= [0 1 2/3 1/6 0 0 0 4]

Baris yang lain

Baris z baru = Baris z – (-5) × Baris x baru


Baris z baru = Baris z – (-5) × Baris x1 baru= [1 -5 -4 0 0 0 0 0] – (-5) × [0 1 2/3 1/6 0 0 0 4]= [1 -5 -4 0 0 0 0 0] – [0 -5 -10/3 -5/6 0 0 0 -20]= [1 0 -2/3 5/6 0 0 0 20]

Baris s2 baru = Baris s2 – (1) × Baris x1 baru= [0 1 2 0 1 0 0 6] – (1) × [0 1 2/3 1/6 0 0 0 4]= [0 1 2 0 1 0 0 6] – [0 1 2/3 1/6 0 0 0 4]= [0 0 4/3 -1/6 1 0 0 2]


menghasilkan solusi baru (cont’d)

Baris s3 baru = Baris s3 – (-1) × Baris x1 baru

= [0 -1 1 0 0 1 0 1] – (-1) × [0 1 2/3 1/6 0 0 0 4]

= [0 -1 1 0 0 1 0 1] – [0 -1 -2/3 -1/6 0 0 0 -4]

= [0 0 5/3 1/6 0 1 0 5]

Baris s4 baru = Baris s4 – (0) × Baris x1 baru



= [0 0 1 0 0 0 1 2] – (0) × [0 1 2/3 1/6 0 0 0 4]

= [0 0 1 0 0 0 1 2] – [0 0 0 0 0 0 0 0]

= [0 0 1 0 0 0 1 2]

Tabel simpleks setelah iterasi 1


Z 1 0 -2/3 5/6 0 0 0 20

x1 0 1 2/3 1/6 0 0 0 4

s2 0 0 4/3 -1/6 1 0 0 2

s3 0 0 5/3 1/6 0 1 0 5

s4 0 0 1 0 0 0 1 2


s4 0 0 1 0 0 0 1 2

� Fungsi tujuan Z = 20.

� Dicari lagi variabel masuk pada baris Z (fungsi tujuan) yang mempunyai koefisien negatif terbesar, ditemukan x2 dengan koefisien -2/3 sebagai variabel masuk.

� Syarat optimal ditunjukkan bahwa x2 adalah variabel masuk.

Syarat Optimal dan Layak

BasisMasuk

Solusi Rasiox2

x1 2/3 4 x2 = 4/(2/3) = 6

s2 4/3 2 x2 = 2/(4/3) = 3/2 � minimal

s 5/3 5 x = 5/(5/3) = 3


s3 5/3 5 x2 = 5/(5/3) = 3

s4 1 2 x2 = 2/1 = 2

Kesimpulan : x2 masuk dan s2 keluar

Baris kunci dan kolom kunci

Masuk

↓


Z 1 0 -2/3 5/6 0 0 0 20

x1 0 1 2/3 1/6 0 0 0 4

Keluar � s2 0 0 4/3 -1/6 1 0 0 2 Baris kunci


Keluar � s2 0 0 4/3 -1/6 1 0 0 2 Baris kunci

s3 0 0 5/3 1/6 0 1 0 5

s4 0 0 1 0 0 0 1 2

Kolom

kunci



Ganti s2 pada kolom Basis dengan x2

Baris x2 baru = Baris s2 ÷ elemen kunci

= [0 0 4/3 -1/6 1 0 0 2] / (4/3)

= [0 0 1 -1/8 3/4 0 0 3/2]

Baris yang lain

Baris z baru = Baris z – (-2/3) × Baris x baru


Baris z baru = Baris z – (-2/3) × Baris x2 baru

= [1 0 -2/3 5/6 0 0 0 20] – (-2/3) × [0 0 1 -1/8 3/4 0 0 3/2]

= [1 0 -2/3 5/6 0 0 0 20] – [0 0 -2/3 1/12 -1/2 0 0 -1]

= [1 0 0 ¾ ½ 0 0 21]

Baris x1 baru = Baris x1 – (2/3) × Baris x2 baru

= [0 1 2/3 1/6 0 0 0 4] – (2/3) × [0 0 1 -1/8 3/4 0 0 3/2]

= [0 1 2/3 1/6 0 0 0 4] – [0 0 2/3 -1/12 1/2 0 0 1]

= [0 1 0 1/4 -1/2 0 0 3]


menghasilkan solusi baru (iterasi 2)

Baris s3 baru = Baris s3 – (5/3) × Baris x1 baru

= [0 0 5/3 1/6 0 1 0 5] – (5/3) × [0 0 1 -1/8 3/4 0 0 3/2]

= [0 0 5/3 1/6 0 1 0 5] – [0 0 5/3 -5/24 5/4 0 0 5/2]

= [0 0 0 3/8 -5/4 1 0 5/2]


= [0 0 0 3/8 -5/4 1 0 5/2]


= [0 0 1 0 0 0 1 2] – (1) × [0 0 1 -1/8 3/4 0 0 3/2]

= [0 0 1 0 0 0 1 2] – [0 0 1 -1/8 3/4 0 0 3/2]

= [0 0 0 1/8 -3/4 0 1 1/2]

Tabel simpleks setelah iterasi 2


Z 1 0 0 ¾ ½ 0 0 21

x1 0 1 0 ¼ -1/2 0 0 3

x2 0 0 1 -1/8 ¾ 0 0 3/2

s3 0 0 0 3/8 -5/4 1 0 5/2


� Berdasarkan pada syarat optimal, tidak ada dalam koefisien z-row yang variabel nonbasis (s1

dan s2) nilainya negatif.

� Sehingga tabel diatas sudah mencapai optimal.

s3 0 0 0 3/8 -5/4 1 0 5/2

s4 0 0 0 1/8 -3/4 0 1 1/2

Hasil LP kasus Reddy Mikks

Variabel

keputusan

Nilai

OptimalRekomendasi

x1 3Produksi 3 ton cat exterior

perhari

Produksi 1.5 ton cat


x2 3/2Produksi 1.5 ton cat

interior perhari

Z 21Keuntungan harian adalah

21(x1000)

Klasifikasi constraint

Sumber daya Nilai slack Status

Bahan baku M1 s1 = 0 Scarce

Bahan baku M2 s2 = 0 Scarce


Batas pasar s3 = 5/2 Abundant

Batas kebutuhan s4 = 1/2 Abundant

Solusi Awal Buatan� PL yang constraintnya menggunakan tanda ≤ dengan

nilai non negatif disisi kanan menyebabkan semuavariabel slack memulai solusi layak awal.

� Model yang menggunakan tanda = dan atau ≥ tidakseperti itu.

� Prosedur untuk awal pemrograman linear dengan


� Prosedur untuk awal pemrograman linear dengantanda = dan ≥ pada constraint adalah menggunakanvariabel buatan (artificial variables) yang memainkan peranan slack diawal iterasi dankemudian mengatur keabsahannya diakhir iterasi.

� Dua metode terkait adalah : metode M dan metodedua fase

Metode M� Metode M memulai LP dalam bentuk persamaan.

� Jika persamaan i tidak mempunyai slack, sebuahvariabel buatan ri ditambahkan untuk membentuksolusi awal yang menyerupai semua basis solusiawal.

� Karena variabel buatan bukan bagian dari model asli


� Karena variabel buatan bukan bagian dari model asliLP, kehadirannya memberikan pelanggaran yang sangat berat dalam fungsi tujuan

� Maka pemaksaan variabel buatan agar bernilai nolharus dilakukan.

� Hal ini akan terjadi dalam kasus jika masalahmempunyai solusi yang layak.

Aturan pelanggaran pada variabel

buatan

� Diberikan M, nilai positif yang cukup besar (secara matematis M � ∞), koefisien tujuan variabel buatan merepresentasikan pelanggaran (penalty) yang tepat jika :

� Koefisien obyektif variabel buatan =


� Koefisien obyektif variabel buatan =

anmeminimalkmasalah dalam M,

kanmemaksimalmasalah dalam M,-

Contoh Kasus� Minimalkan Z = 4x1 + x2

� Constraint :

� 3x1 + x2 = 3

� 4x1 + 3x2 ≥ 6

� x + 2x ≤ 4


� x1 + 2x2 ≤ 4

� x1, x2 ≥ 0

Penyelesaian� Menggunakan r1 sebagai variabel surplus dalam constraint kedua dan s1 sebagai slack

dalam constraint ketiga, bentuk persamaan masalah menjadi :� Minimalkan Z = 4x1 + x2

� Constraint :� 3x1 + x2 = 3

� 4x1 + 3x2 – r1 = 6

� x1 + 2x2 + s1 = 4

� x1, x2, r1, s1 ≥ 0

� Persamaan ketiga mempunyai variabel slack yaitu s1, tetapi persamaan pertama dan keduatidak.


tidak.

� Maka tambahkan variabel buatan R1 dan R2 dalam persamaan pertama dan kedua danmelanggar fungsi tujuan dengan MR1 + MR2 (karena meminimalkan).

� Hasil LP menjadi :� Minimalkan Z = 4x1 + x2 + MR1 + MR2

� Constraint :� 3x1 + x2 + R1 = 3

� 4x1 + 3x2 – r1 + R2 = 6

� x1 + 2x2 + s1 = 4

� x1, x2, r1, s1, R1, R2 ≥ 0

� Solusi basis awal diberikan oleh (R1, R2, s1) = (3,6,4).

Nilai M� Nilai M sebaiknya cukup besar yang relative

terhadap koefisien obyektif yang asli sehingga dapat bertindak sebagai pelanggaran yang memaksakan variabel buatan pada level nol dalam solusi optimal.


dalam solusi optimal.

� Tetapi nilai M juga tidak boleh terlalu besar karena bisa membawa hasil tak terhingga.

� Dalam kasus contoh ini, nilai koefisien obyektif x1

dan x2 adalah 4 dan 1, maka cukup beralasan jika M = 100

Perubahan pada tabel simpleksBasis x1 x2 r1 R1 R3 s1 Solusi

Z -4 -1 0 -100 -100 0 0

R1 3 1 0 1 0 0 3

R2 4 3 -1 0 1 0 6

s1 1 2 0 0 0 1 4


� Dalam tabel, x1 = x2 = r1 = 0, yang merupakan solusi basis awalR1 = 3, R2 = 6, dan s1 = 4.

� Solusi ini berarti Z = 100 (3) + 100 (6) = 900 (seharusnya 0, seperti sisi kanan z-row yang tampak ditabel).

� Ketidakkonsistenan ini muncul dari fakta bahwa R1 dan R2mempunyai koefisien nonzero (-100, -100) dalam z-row (bandingkan dengan semua solusi awal slack pada contohsebelumnya) dimana koefisien z-row dari slack adalah nol.

Menghilangkan inkonsistensi� Mensubstitusi R1 dan R2 dalam z-row menggunakan

persamaan constraint yang tepat.

� Elemen bernilai 1 yang dihighlight dalam R1-row dan R2-row, perkalian setiap R1-row dan R2-row oleh 100 danmenambahkan jumlahnya ke z-row akan mensubstitusi R1dan R2 dalam baris obyektif.

� Sehingga :


� Sehingga :Z-row baru = Z-row lama + (100 × R1-row + 100 × R2-row)Z-row baru = [-4 -1 0 -100 -100 0 0] + (100 × [3 1 0 1 0 0 3] +

100 × [4 3 -1 0 1 0 6])Z-row baru = [-4 -1 0 -100 -100 0 0] + ([300 100 0 100 0 0 300] +

[400 300 -100 0 100 0 600])Z-row baru = [-4 -1 0 -100 -100 0 0] + [700 400 -100 100 100 0

900]Z-row baru = [696 399 -100 0 0 0 900]

Perubahan pada tabel simpleks

setelah substitusi

Basis x1 x2 r1 R1 R3 s1 Solusi

Z 696 399 -100 0 0 0 900

R1 3 1 0 1 0 0 3

R2 4 3 -1 0 1 0 6


� Dari tabel diatas, dapat dipastikan bahwa nilai Z=900, konsisten/tepat dengan nilai solusi layak awal : R1 = 3, R2 = 6, dan s1 = 4.

R2 4 3 -1 0 1 0 6

s1 1 2 0 0 0 1 4

Penentuan variabel masuk dan

keluar

BasisMasuk

Solusi Rasiox1

R1 3 3 x1 = 3/3 = 1 � minimal

R2 4 6 x1 = 6/4 = 3/2

s 1 4 x = 4/1 = 4


� Nilai rasio positif terkecil menjadi baris kunci dan kolom pada fungsi tujuan dengan koefisien positif terbesar menjadi kolom kunci.

s1 1 4 x1 = 4/1 = 4

Kesimpulan : x1 masuk dan R1 keluar

Kolom dan baris kunci yang terpilih

(iterasi 1)

Masuk

↓


Z 696 399 -100 0 0 0 900

Keluar � R1 3 1 0 1 0 0 3 Baris


Keluar � R1 3 1 0 1 0 0 3 Baris

kunci

R2 4 3 -1 0 1 0 6

s1 1 2 0 0 0 1 4

Kolom

kunci



Ganti R1 pada kolom Basis dengan x1

Baris x1 baru = Baris R1 ÷ elemen kunci

= [3 1 0 1 0 0 3] / 3

= [1 1/3 0 1/3 0 0 1]

Baris yang lain

Baris z baru = Baris z – (696) × Baris x baru


Baris z baru = Baris z – (696) × Baris x1 baru

= [696 399 -100 0 0 0 900] – (696) × [1 1/3 0 1/3 0 0 1]

= [696 399 -100 0 0 0 900] – [696 232 0 232 0 0 696]

= [0 167 -100 -232 0 0 204]

Baris R2 baru = Baris R2 – (4) × Baris x1 baru

= [4 3 -1 0 1 0 6] – (4) × [1 1/3 0 1/3 0 0 1]

= [4 3 -1 0 1 0 6] – [4 4/3 0 4/3 0 0 4]

= [0 5/3 -1 -4/3 1 0 2]


menghasilkan solusi baru (iterasi 1)Baris s1 baru = Baris s1 – (1) × Baris x1 baru

= [1 2 0 0 0 1 4] – (1) × [1 1/3 0 1/3 0 0 1]

= [1 2 0 0 0 1 4] – [1 1/3 0 1/3 0 0 1]

= [0 5/3 0 -1/3 0 1 3]

Solusi baru adalah (x1, R2, s1) dan tabel simpleks berubah menjadi :




Z 0 167 -100 -232 0 0 204

x1 1 1/3 0 1/3 0 0 1

R2 0 5/3 -1 -4/3 1 0 2

s1 0 5/3 0 -1/3 0 1 3

• Dari tabel diatas, terlihat bahwa fungsi tujuan Z = 204.

• Selanjutnya dicari lagi variabel masuk pada baris Z (fungsitujuan) yang mempunyai koefisien positif terbesar, ditemukan x2

dengan koefisien 167 sebagai variabel masuk.


keluar

BasisMasuk

Solusi Rasiox2

x1 1/3 1 x2 = 1/(1/3) = 3

R 5/3 2 x = 2/(5/3) = 6/5 � minimal


R2 5/3 2 x2 = 2/(5/3) = 6/5 � minimal

s1 5/3 3 x2 = 3/(5/3) = 9/5

Kesimpulan : x2 masuk dan R2 keluar

Kolom dan baris kunci yang terpilih

(iterasi 2)

Masuk

↓


Z 0 167 -100 -232 0 0 204

x1 1 1/3 0 1/3 0 0 1


x1 1 1/3 0 1/3 0 0 1

Keluar � R2 0 5/3 -1 -4/3 1 0 2 Baris kunci

s1 0 5/3 0 -1/3 0 1 3

Kolom

kunci



Ganti R2 pada kolom Basis dengan x2

Baris x2 baru = Baris R2 ÷ elemen kunci

= [0 5/3 -1 -4/3 1 0 2] / (5/3)

= [0 1 -3/5 -4/5 3/5 0 6/5]

Baris yang lain




= [0 167 -100 -232 0 0 204] – (167) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [0 167 -100 -232 0 0 204] – [0 167 -501/5 -668/5 501/5 0 1002/5]

= [0 0 1/5 -492/5 -501/5 0 18/5]

Baris x1 baru = Baris x1 – (1/3) × Baris x2 baru

= [1 1/3 0 1/3 0 0 1] – (1/3) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [1 1/3 0 1/3 0 0 1] – [0 1/3 -1/5 -4/15 3/15 0 6/15]

= [1 0 1/5 3/5 -3/15 0 3/5]


menghasilkan solusi baru (iterasi 1)Baris s1 baru = Baris s1 – (1) × Baris x2 baru

= [0 5/3 0 -1/3 0 1 3] – (5/3) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [0 5/3 0 -1/3 0 1 3] – [0 5/3 -1 -4/3 1 0 -2]

= [0 0 1 1 -1 1 5]

Solusi baru adalah (x1, x2, s1) dan tabel simpleks berubah menjadi :




Z 0 0 1/5 -492/5 -501/5 0 18/5

x1 1 0 1/5 3/5 -3/5 0 3/5

x2 0 1 -3/5 -4/5 3/5 0 6/5

s1 0 0 1 1 -1 1 5


keluar� Dari tabel diatas, terlihat bahwa fungsi tujuan Z = 18/5.

� Selanjutnya dicari lagi variabel masuk pada baris Z (fungsitujuan) yang mempunyai koefisien positif terbesar, ditemukan r1dengan koefisien 1/5 sebagai variabel masuk. Syarat optimal ditunjukkan bahwa r1 adalah variabel masuk

BasisMasuk

Solusi Rasior1


r1

x1 1/5 3/5 r1 = (3/5)/(1/5) = 3 � minimal

x2 -3/5 6/5 r1 = (6/5)/(-3/5) = -2 (diabaikan)

s1 1 5 r1 = 5/1 = 5

Kesimpulan : tidak ada syarat kelayakan yang memenuhi

� Dari tabel diatas, terlihat bahwa rasio minimal terdapat padavariabel basis x1 dan ini adalah variabel keputusan.

� Sehingga tidak ada lagi syarat kelayakan yang dapat dilakukandan tabel simpleks diatas adalah yang paling optimal.

Metode dua fase� Dalam metode M, penggunaan penalty M,

dimana didefinisikan nilainya harus relative besarterhadap koefisien obyektif actual dari model, dapat menghasilkan kisaran error yang dapatmelemahkan akurasi perhitungan simpleks.

� Metode dua fase mengurangi kelemahan ini


� Metode dua fase mengurangi kelemahan inidengan menghilangkan konstanta M.

� Metode ini menyelesaikan kasus LP dalam duafase : � Fase I berusaha untuk mencari solusi layak awal,

� dan jika ditemukan, maka Fase II dijalankan untukmenyelesaikan masalah aslinya.

Langkah-langkah metode dua fase� Fase I

� Kondisikan masalah dalam bentuk persamaan, dantambahkan variabel buatan yang diperlukan padaconstraint (seperti metode M) untuk mengaman basis solusi awal.

� Cari solusi basis dari persamaan yang didapatkan itu, tanpa memandang LP adalah memaksimalkan atau


tanpa memandang LP adalah memaksimalkan ataumeminimalkan, selalu meminimalkan jumlah darivariabel buatan.

� Jika nilai minimum penjumlahan adalah positif, masalahLP tidak mempunyai solusi layak, sehingga merupakanakhir proses. Jika tidak, lanjutkan ke fase II.

� Fase II� Gunakan solusi layak dari fase I sebagai basis solusi

awal layak pada masalah yang sesungguhnya.

Mengacu pada contoh di metode M

� Minimalkan Z = 4x1 + x2

� Constraint :

� 3x1 + x2 = 3

� 4x1 + 3x2 ≥ 6

� x + 2x ≤ 4


� x1 + 2x2 ≤ 4

� x1, x2 ≥ 0

Penyelesaian� Menggunakan r1 sebagai variabel surplus dalam

constraint kedua dan s1 sebagai slack dalam constraint ketiga, bentuk persamaan masalah menjadi :




� Constraint :

� 3x1 + x2 = 3

� 4x1 + 3x2 – r1 = 6

� x1 + 2x2 + s1 = 4

� x1, x2, r1, s1 ≥ 0

Penyelesaian dengan metode dua

fase – Fase I� Minimalkan R = R1 + R2

� Kendala :� 3x1 + x2 + R1 = 3� 4x1 + 3x2 – r1 + R2 = 6� x1 + 2x2 + s1 = 4� x1, x2, r1, s1, R1, R2 ≥ 0

� Tabel simpleksnya tampak sebagai berikut :


� Tabel simpleksnya tampak sebagai berikut :


R 0 0 0 -1 -1 0 0

R1 3 1 0 1 0 0 3

R2 4 3 -1 0 1 0 6

s1 1 2 0 0 0 1 4


fase – Fase I (cont’d)� Dengan metode M, R1 dan R2 disubstitusikan dalam R-

row dengan menggunakan perhitungan :R-row baru = R-row lama + (1 × R1-row + 1 × R2-row)R-row baru = [0 0 0 -1 -1 0 0] + (1 × [3 1 0 1 0 0 3] + 1 × [4 3 -1 0

1 0 6])R-row baru = [0 0 0 -1 -1 0 0] + ([3 1 0 1 0 0 3] + [4 3 -1 0 1 0 6])R-row baru = [0 0 0 -1 -1 0 0] + [7 4 -1 1 1 0 9]


R-row baru = [0 0 0 -1 -1 0 0] + [7 4 -1 1 1 0 9]R-row baru = [7 4 -1 0 0 0 9]

� Tabel simpleks berubah menjadi :


R 7 4 -1 0 0 0 9

R1 3 1 0 1 0 0 3

R2 4 3 -1 0 1 0 6

s1 1 2 0 0 0 1 4


fase – Fase I (cont’d)



fase – Fase I (cont’d)� x1 terpilih sebagai kolom kunci (memenuhi syarat optimal

meminimalkan karena mempunyai koefisien positifterbesar).

� Perhitungan rasio dan syarat kelayakan ditampilkan dalamtabel dibawah ini :

Basis x1 x2 r1 R1 R3 s1 Solus Rasio


i

R 7 4 -1 0 0 0 9

R1 3 1 0 1 0 0 3 3/3 = 1 �

minimal

R2 4 3 -1 0 1 0 6 6/4 = 1.5

s1 1 2 0 0 0 1 4 4/1 = 4


fase – Fase I (cont’d)� R1 menjadi variabel keluar dan x1 menjadi variabel

masuk.

� Perubahan pada tiap baris dengan Operasi Gauss-Jordan untuk menghasilkan solusi baru� Baris kunci

� Ganti R1 pada kolom Basis dengan x1

� Baris x baru = Baris R ÷ elemen kunci


� Baris x1 baru = Baris R1 ÷ elemen kunci= [3 1 0 1 0 0 3] / 3= [1 1/3 0 1/3 0 0 1]

� Baris yang lain� Baris R baru = Baris R – (7) × Baris x1 baru

= [7 4 -1 0 0 0 9] – (7) × [1 1/3 0 1/3 0 0 1]= [7 4 -1 0 0 0 9] – [7 7/3 0 7/3 0 0 7]= [0 5/3 -1 -7/3 0 0 2]


fase – Fase I (cont’d)� Baris R2 baru = Baris R2 – (4) × Baris x1 baru

= [4 3 -1 0 1 0 6] – (4) × [1 1/3 0 1/3 0 0 1]= [4 3 -1 0 1 0 6] – [4 4/3 0 4/3 0 0 4]= [0 5/3 -1 -4/3 1 0 2]

� Baris s1 baru = Baris s1 – (1) × Baris x1 baru= [1 2 0 0 0 1 4] – (1) × [1 1/3 0 1/3 0 0 1]= [1 2 0 0 0 1 4] – [1 1/3 0 1/3 0 0 1]= [0 5/3 0 -1/3 0 1 3]


= [0 5/3 0 -1/3 0 1 3]

� Perubahan tabel simpleks menjadi :


R 0 5/3 -1 -7/3 0 0 2

x1 1 1/3 0 1/3 0 0 1

R2 0 5/3 -1 -4/3 1 0 2

s1 0 5/3 0 -1/3 0 1 3


fase – Fase I (cont’d)� x2 terpilih sebagai kolom kunci (memenuhi syarat optimal

meminimalkan karena mempunyai koefisien positif terbesar).

� Perhitungan rasio dan syarat kelayakan ditampilkan dalam tabeldibawah ini :

Basis x1 x2 r1 R1 R3 s1 Solusi Rasio

R 0 5/3 -1 -7/3 0 0 2


R 0 5/3 -1 -7/3 0 0 2

x1 1 1/3 0 1/3 0 0 1 1/(1/3) = 3

R2 0 5/3 -1 -4/3 1 0 2 2/(5/3) = 1.2 �

minimal

s1 0 5/3 0 -1/3 0 1 3 3/(5/6) = 3.6

� Dari tabel tersebut, R2 menjadi variabel keluar dan x2 menjadivariabel masuk.



� Operasi Gauss-Jordan untuk menghasilkan solusibaru

� Baris kunci� Ganti R2 pada kolom Basis dengan x2

� Baris x2 baru = Baris R2 ÷ elemen kunci


2 2

= [0 5/3 -1 -4/3 1 0 2] / (5/3)

= [0 1 -3/5 -4/5 3/5 0 6/5]

� Baris yang lain� Baris R baru = Baris R – (5/3) × Baris x2 baru

= [0 5/3 -1 -7/3 0 0 2] – (5/3) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [0 5/3 -1 -7/3 0 0 2] – [0 5/3 -1 -4/3 1 0 2]

= [0 0 0 -1 -1 0 0]


fase – Fase I (cont’d)� Baris x1 baru = Baris x1 – (1/3) × Baris x2 baru

= [1 1/3 0 1/3 0 0 1] – (1/3) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [1 1/3 0 1/3 0 0 1] – [0 1/3 -1/5 -4/15 1/5 0 2/5]

= [1 0 1/5 3/5 -1/5 0 3/5]

� Baris s1 baru = Baris s1 – (5/3) × Baris x2 baru= [0 5/3 0 -1/3 0 1 3] – (5/3) × [0 1 -3/5 -4/5 3/5 0 6/5]


= [0 5/3 0 -1/3 0 1 3] – (5/3) × [0 1 -3/5 -4/5 3/5 0 6/5]

= [0 5/3 0 -1/3 0 1 3] – [0 5/3 -1 -4/3 1 0 2]

= [0 0 1 1 -1 1 1]





R 0 0 0 -1 -1 0 0

x1 1 0 1/5 3/5 -1/5 0 3/5

x2 0 1 -3/5 -4/5 3/5 0 6/5

s1 0 0 1 1 -1 1 1


� Tidak ada syarat optimal yang ditemui pada tabel (tidak adakoefisien positif terbesar di z-row).

� Sehingga untuk fase I selesai dan mencapai optimal.

� Karena minimal R = 0. Fase I menghasilkan basis solusi optimal x1 = 3/5 dan x2 = 6/5 dan s1 = 1.

� Pada titik ini, variabel buatan telah mecapai tujuan, dan kitadapat menghilangkan kolom tersebut dari tabel dan dilanjutkanke fase II.

s1 0 0 1 1 -1 1 1


fase – Fase II

� Setelah penghapusan kolom variabel buatan, masalah asli menjadi :


� Constraint :

� x1 + 1/5 r1 = 3/5


� x1 + 1/5 r1 = 3/5

� x2 – 3/5 r1 = 6/5

� r1 + s1 = 1

� x1, x2, r1, s1 ≥ 0


fase – Fase II (cont’d)Basis x1 x2 r1 s1 Solusi

Z -4 -1 0 0 0

x1 1 0 1/5 0 3/5

x2 0 1 -3/5 0 6/5

s1 0 0 1 1 1


� Karena variabel basis x1 dan x2 mempunyai koefisien nonzero dalam z-row, keduanya harus disubstitusikan menggunakan perhitungan berikut:Z-row baru = Z-row lama + (4 × x1-row + 1 × x2-row)Z-row baru = [-4 -1 0 0 0] + (4 × [1 0 1/5 0 12/5] + 1 × [0 1 -3/5 0 6/5])Z-row baru = [-4 -1 0 0 0] + ([4 0 4/5 0 12/5] + [0 1 -3/5 0 6/5])Z-row baru = [-4 -1 0 0 0] + [4 1 1/5 0 18/5]Z-row baru = [0 0 1/5 0 18/5]

� Inisial tabel simpleks di fase II menjadi :


fase – Fase II (cont’d)

Basis x1 x2 r1 s1 Solusi

Z 0 0 1/5 0 18/5

x1 1 0 1/5 0 3/5

x2 0 1 -3/5 0 6/5

s 0 0 1 1 1


� Kasusnya adalah meminimalkan, sehingga dicari koefisienvariabel dalam z-row yang mempunyai nilai positifterbesar.

� Didapatkan r1 bernilai positif terbesar, sehingga menjadikolom kunci (memenuhi syarat optimal meminimalkankarena mempunyai koefisien positif terbesar)

s1 0 0 1 1 1



Basis x1 x2 r1 s1 Solusi Rasio

Z 0 0 1/5 0 18/5

x1 1 0 1/5 0 3/5 (3/5)/(1/5) = 3

x 0 1 -3/5 0 6/5 (6/5)/(-3/5) = -2 (diabaikan)


� s1 menjadi variabel keluar dan r1 menjadi variabel masuk

x2 0 1 -3/5 0 6/5 (6/5)/(-3/5) = -2 (diabaikan)

s1 0 0 1 1 1 1/1 = 1 � minimal



� Operasi Gauss-Jordan untuk menghasilkan solusibaru

� Baris kunci� Ganti s1 pada kolom Basis dengan r1

� Baris r1 baru = Baris s1 ÷ elemen kunci


1 1

= [0 0 1 1 1] / 1

= [0 0 1 1 1]

� Baris yang lain� Baris Z baru = Baris Z – (1/5) × Baris r1 baru

= [0 0 1/5 0 18/5] – (1/5) × [0 0 1 1 1]

= [0 0 1/5 0 18/5] – [0 0 1/5 1/5 1/5]

= [0 0 0 -1/5 17/5]



� Baris x1 baru = Baris x1 – (1/5) × Baris r1 baru= [1 0 1/5 0 3/5] – (1/5) × [0 0 1 1 1]

= [1 0 1/5 0 3/5] – [0 0 1/5 1/5 1/5]

= [1 0 0 -1/5 2/5]

� Baris x2 baru = Baris x2 – (-3/5) × Baris r1 baru


2 2 1

= [0 1 -3/5 0 6/5] – (-3/5) × [0 0 1 1 1]

= [0 1 -3/5 0 6/5] – [0 0 -3/5 -3/5 -3/5]

= [0 1 0 3/5 9/5]




Basis x1 x2 r1 s1 Solusi

Z 0 0 0 -1/5 17/5

x1 1 0 0 -1/5 2/5

x2 0 1 0 3/5 9/5


� Solusi baru adalah (x1, x2, r1) dan tabel simpleks dan memberikan nlai x1 dan x2 yang optimal yaitu masing-masing 2/5 dan 9/5

x2 0 1 0 3/5 9/5

r1 0 0 1 1 1

Hal-hal yang perlu diperhatikan� Penghilangan variabel buatan dan kolomnya diakhir fase I hanya

bisa dilakukan ketika semua variabel buatan tersebut sudahmenjadi variabel nonbasis.

� Jika satu atau lebih variabel buatan adalah basis (pada level nol) di akhir fase I, maka langkah tambahan berikut ini harusdilakukan untuk menghilangkannya sebelum masuk ke fase II

� Langkah 1� Pilih variabel buatan nol untuk meninggalkan basis solusi dan


� Pilih variabel buatan nol untuk meninggalkan basis solusi danrangcanglah baris sebagai baris kunci.

� Variabel masuk bisa sembarang variabel nonbasis (non buatan) dengan koefisien nonzero (positif atau negatif) dalam baris kunci. Lakukan iterasi simpleks.

� Langkah 2� Hilangkan kolom variabel buatan (yang baru saja keluar) dari

tabel. � Jika semua variabel buatan nol telah dikeluarkan, lanjutkan ke

fase II. Jika tidak, kembali ke langkah 1.

Tugas� Baca Modul 4 Analisis Sensitivitas

� Kerjakan soal Modul 3 :� Kelompok 1 : 3.2 dan 3.6(a)� Kelompok 2 : 3.3 dan 3.6(b)� Kelompok 3 : 3.4 dan 3.6(c)� Kelompok 4 : 3.7 dan 3.6(d)� Kelompok 5 : 3.8 dan 3.1(a)� Kelompok 6 : 3.5(a) dan 3.1(b)


� Kelompok 6 : 3.5(a) dan 3.1(b)� Kelompok 7 : 3.5(c) dan 3.1(c)� Kelompok 8 : 3.5(d) dan 3.1(d)� Kelompok 9 : 3.5(b) dan 3.5(e)

� Pengerjaan :� Satu kelompok berisi maksimal 5 orang� Ditulis tangan pada kertas folio bergaris oleh masing-masing anggota� Dikumpulkan pada pertemuan berikutnya

ms2011-modul 3-pemrograman linear-simpleks.ppt · persamaan menambahkan variabel slack ke fungsi...

Documents