Manajemen Sains. Pemrograman Linier (Metode Simpleks) Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Manajemen Sains Pemrograman Linier (Metode Simpleks)

Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Komponen dasar Variabel keputusan

yang kita cari untuk ditentukan Objective (tujuan)

yaitu ingin mengoptimalkan (memaksimalkan atau meminimalkan) Constraints

yaitu solusi yang harus dicapai.

2

Teknik Informatika UMG 2011

LP metode Simpleks Mengonversi constraint yang masih dalam bentuk

pertidaksamaan menjadi persamaan menggunakan bantuan variabel slack. Nilai di sisi kanan harus non negatif. Constraint yang menggunakan tanda ≤ merupakan representasi batas ketersediaan sumber daya, dimana sisi kiri adalah representasi

penggunaan sumber daya oleh aktivitas (variabel) model. Perbedaan antara sisi kanan dan sisi kiri tanda ≤ merupakan sejumlah sumber daya yang belum digunakan atau slack. 3


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 ke sisi kanan

4


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 melewati batas minimal yang direpresentasikan sebagai surplus. Konversi dari ≥ ke = dicapai dengan mengurangi dengan variabel surplus non negatif dari sisi kiri pertidaksamaan. Misalnya, dalam kasus Ozark Farm, constraint yang menyatakan kebutuhan makanan : x1 + x2 ≥ 800 Definisikan r1 sebagai variabel surplus, constraint dapat dikonversi

menjadi persamaan berikut : x1 + x2 - r1 = 800, r1 ≥ 0

5


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 : -x1 + x2 + r1 = -3, r1 ≥ 0 Selanjutnya kedua sisi dikalikan dengan -1,

sehingga sisi kanan bernilai positif : x1 - x2 - r1 = 3

6


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

7


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

8


Langkah-langkah metode Simpleks Menentukan awal basis solusi layak 2. Memilih variabel masuk menggunakan syarat keoptimalan. Berhenti jika tidak ada lagi variabel masuk, solusi terakhir adalah solusi optimal. Jika tidak maka ke langkah 3. 3. Memilih variabel keluar menggunakan syarat kelayakan. 4. Menentukan solusi dasar yang baru menggunakan perhitungan Gauss-Jordan. Kembali ke langkah 2. 1.

9


Langkah-langkah metode Simpleks (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 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. 10


Operasi baris Gauss-Jordan Menentukan baris kunci :

1.

Mengganti nilai baris yang lain :

2.

11

Gantilah variabel keluar dalam kolom basis dengan variabel masuk Baris kunci baru = Baris kunci ÷ elemen kunci Baris baru = Baris lama – koefisien kolom kunci × Baris kunci baru


Langkah-langkah metode Simpleks (cont’d)

Variabel basis adalah variabel yang berkontribusi (mempunyai nilai) memberikan solusi yang diminta. Variabel nonbasis adalah variabel yang tidak berkontribusi (bernilai 0) dalam pemberian solusi. Inisialisasi dalam metode simpleks : x1, x2, … adalah variabel non basis s1, s2, … adalah variabel basis

12

Dalam iterasi metode simpleks, satu persatu variabel slack akan berubah menjadi variabel non basis karena keluar dari solusi dasar (variabel keluar), dan variabel keputusan akan berubah menjadi 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 harian maksimal untuk cat interior adalah 2 ton. Reddy Mikks ingin menentukan jumlah optimal (terbaik) produk antara cat interior dan exterior dengan memaksimalkan total keuntungan harian.

Produk Cat Ext Cat Int Kapasitas 13

Kebutuhan bahan baku (ton) M1 M2 6 1 4 2 24 6


Keuntungan (x1000) 5 4 Z

Program Linier pada kasus Reddy Mikks(cont’d) Konversi model Reddy Mikks menjadi :

Kendala : 6x1 + 4x2 + s1 = 24 (bahan baku M1) x1 + 2x2 + s2 = 6 (bahan baku M2) (2) -x1 + x2 + s3 = 1 (batas pasar) x2 + s4 = 2 (batas kebutuhan) (4) x1, x2, s1, s2, s3, s4 ≥ 0

(1) (3)

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 14


Program Linier pada kasus Reddy Mikks(cont’d) Basis Z s1 s2 s3 s4

15

Z 1 0 0 0 0

x1 -5 6 1 -1 0


x2 -4 4 2 1 1

s1 0 1 0 0 0

s2 0 0 1 0 0

s3 0 0 0 1 0

s4 0 0 0 0 1

Solusi 0 24 6 1 2

z-row s1-row s2-row s3-row s4-row

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

16

dapat ditingkatkan dengan meningkatkan x1 dan x2. Untuk variabel yang akan masuk sebagai variabel basis dipilih nilai variabel nonbasis yang mempunyai nilai koefisien positif terbesar. Karena fungsi tujuan dalam tabel simpleks adalah Z – 5x1 – 4x2 = 0, variabel masuk akan dikaitkan pada variabel dengan koefisien negatif terbesar dalam fungsi tujuan. Aturan ini disebut dengan syarat optimal. Mekanisme penentuan variabel keluar dari tabel simpleks dilakukan dengan menghitung rasio non negatif dari sisi kanan persamaan (kolom Solusi) pada koefisien constraint yang bersangkutan dengan variabel masuk seperti yang ditunjukkan pada tabel berikut :


Syarat Optimal dan Layak Basis s1 s2 s3 s4

Masuk Solusi Rasio x1 6 24 x1 = 24/6 = 4 minimal 1 6 x1 = 6/1 = 6 -1 1 x1 = 1/-1 = -1 (diabaikan) 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 dan

variabel keluar sebagai baris kunci. Elemen yang tepat menjadi anggota kolom kunci dan baris kunci disebut elemen kunci. Tabel akan diupdate berdasarkan baris dan kolom yang dihighlight.

17


Baris kunci dan kolom kunci Masuk ↓

Keluar

Basis

Z

x1

x2

s1

s2

s3

s4

Solusi

Z

1

-5

-4

0

0

0

0

0

s1

0

6

4

1

0

0

0

24

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

18


Baris 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 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] 19


Operasi Gauss-Jordan untuk 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]

20


Tabel simpleks setelah iterasi 1 Basis Z x1 s2 s3 s4

Z 1 0 0 0 0

x1 0 1 0 0 0

x2 -2/3 2/3 4/3 5/3 1

s1 5/6 1/6 -1/6 1/6 0

s2 0 0 1 0 0

s3 0 0 0 1 0

s4 0 0 0 0 1

Solusi 20 4 2 5 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. 21


Syarat Optimal dan Layak Basis x1 s2 s3 s4

22

Masuk Solusi Rasio x2 2/3 4 x2 = 4/(2/3) = 6 4/3 2 x2 = 2/(4/3) = 3/2 minimal 5/3 5 x2 = 5/(5/3) = 3 1 2 x2 = 2/1 = 2 Kesimpulan : x2 masuk dan s2 keluar


Baris kunci dan kolom kunci

Keluar

23

Basis Z x1 s2 s3 s4

Z 1 0 0 0 0


x1 0 1 0 0 0

Masuk ↓ x2 s1 -2/3 5/6 2/3 1/6 4/3 -1/6 5/3 1/6 1 0 Kolom kunci

s2 0 0 1 0 0

s3 0 0 0 1 0

s4 0 0 0 0 1

Solusi 20 4 2 Baris kunci 5 2

Operasi Gauss-Jordan untuk menghasilkan solusi baru (iterasi 2) Baris 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 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] 24


Operasi Gauss-Jordan untuk 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] Baris s4 baru = Baris s4 – (0) × Baris x1 baru = [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] 25


Tabel simpleks setelah iterasi 2 Basis

Z

x1

x2

s1

s2

s3

s4

Solusi

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

s4

0

0

0

1/8

-3/4

0

1

1/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. 26


Hasil LP kasus Reddy Mikks Variabel keputusan x1 x2 Z

27

Nilai Rekomendasi Optimal Produksi 3 ton cat exterior 3 perhari Produksi 1.5 ton cat 3/2 interior perhari Keuntungan harian adalah 21 21(x1000)


Klasifikasi constraint

28

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 semua variabel slack memulai solusi layak awal. Model yang menggunakan tanda = dan atau ≥ tidak seperti itu. Prosedur untuk awal pemrograman linear dengan tanda = dan ≥ pada constraint adalah menggunakan variabel buatan (artificial variables) yang memainkan peranan slack diawal iterasi dan kemudian mengatur keabsahannya diakhir iterasi. Dua metode terkait adalah : metode M dan metode dua fase 29


Metode M Metode M memulai LP dalam bentuk persamaan. Jika persamaan i tidak mempunyai slack, sebuah

variabel buatan ri ditambahkan untuk membentuk solusi awal yang menyerupai semua basis solusi awal. Karena variabel buatan bukan bagian dari model asli LP, kehadirannya memberikan pelanggaran yang sangat berat dalam fungsi tujuan Maka pemaksaan variabel buatan agar bernilai nol harus dilakukan. Hal ini akan terjadi dalam kasus jika masalah mempunyai solusi yang layak. 30


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 = - M, dalam masalah memaksimalkan   M, dalam masalah meminimalkan

31


Contoh Kasus Minimalkan Z = 4x1 + x2 Constraint : 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1, x2 ≥ 0

32


Penyelesaian

Menggunakan r1 sebagai variabel surplus dalam constraint kedua dan s1 sebagai slack dalam constraint ketiga, bentuk persamaan masalah menjadi :

Constraint :

33

=3 =6 =4

Minimalkan Z = 4x1 + x2 + MR1 + MR2

Constraint :

3x1 + x2 4x1 + 3x2 – r1 x1 + 2x2 + s1 x1, x2, r1, s1 ≥ 0

Persamaan ketiga mempunyai variabel slack yaitu s1, tetapi persamaan pertama dan kedua tidak. Maka tambahkan variabel buatan R1 dan R2 dalam persamaan pertama dan kedua dan melanggar fungsi tujuan dengan MR1 + MR2 (karena meminimalkan). Hasil LP menjadi :

Minimalkan Z = 4x1 + x2

3x1 + x2 4x1 + 3x2 – r1 x1 + 2x2 + s1 x1, x2, r1, s1, R1, R2 ≥ 0

+ R1 = 3 + R2 = 6 =4

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. 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 34


Perubahan pada tabel simpleks Basis Z R1 R2 s1

x1 -4 3 4 1

x2 -1 1 3 2

r1 0 0 -1 0

R1 -100 1 0 0

R3 -100 0 1 0

s1 0 0 0 1

Solusi 0 3 6 4

Dalam tabel, x1 = x2 = r1 = 0, yang merupakan solusi basis awal

R1 = 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 R2 mempunyai koefisien nonzero (-100, -100) dalam z-row (bandingkan dengan semua solusi awal slack pada contoh sebelumnya) dimana koefisien z-row dari slack adalah nol. 35


Menghilangkan inkonsistensi Mensubstitusi R1 dan R2 dalam z-row menggunakan

persamaan constraint yang tepat. Elemen bernilai 1 yang dihighlight dalam R1-row dan R2row, perkalian setiap R1-row dan R2-row oleh 100 dan menambahkan jumlahnya ke z-row akan mensubstitusi R1 dan R2 dalam baris obyektif. 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]

36


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

s1

1

2

0

0

0

1

4

Dari tabel diatas, dapat dipastikan bahwa nilai

Z=900, konsisten/tepat dengan nilai solusi layak awal : R1 = 3, R2 = 6, dan s1 = 4. 37


Penentuan variabel masuk dan keluar Basis

Masuk x1

Solusi

Rasio

R1

3

3

x1 = 3/3 = 1 minimal

R2

4

6

x1 = 6/4 = 3/2

s1

1

4

x1 = 4/1 = 4

Kesimpulan : x1 masuk dan R1 keluar

Nilai rasio positif terkecil menjadi baris kunci dan

kolom pada fungsi tujuan dengan koefisien positif terbesar menjadi kolom kunci. 38


Kolom dan baris kunci yang terpilih (iterasi 1) Masuk ↓ Basis Z Keluar R1 R2 s1

39

x1 696 3 4 1 Kolom kunci


x2 r1 R1 R3 s1 399 -100 0 0 0 1 0 1 0 0 3 2

-1 0

0 0

1 0

0 1

Solusi 900 3 6 4

Baris kunci

Operasi Gauss-Jordan untuk menghasilkan solusi baru (iterasi 1) Baris 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 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] 40


Operasi Gauss-Jordan untuk 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 :

Basis x1 x2 r1 R1 R3 s1 Solusi Z 0 167 -100 -232 0 0 204 x1 1 1/3 0 1/3 0 0 1 0 5/3 -1 -4/3 1 0 2 R2 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 (fungsi tujuan) yang mempunyai koefisien positif terbesar, ditemukan x2 dengan koefisien 167 sebagai variabel masuk. 41


Penentuan variabel masuk dan keluar Basis

Masuk x2

Solusi

Rasio

x1

1/3

1

x2 = 1/(1/3) = 3

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

42


Kolom dan baris kunci yang terpilih (iterasi 2) Masuk ↓

Keluar

Basis

x1

x2

Z

0

167

x1

1

1/3

0

1/3

R2

0

5/3

-1

s1

0

5/3

0

Kolom kunci

43


r1

R1

R 3 s1

-100 -232 0

Solusi

0

204

0

0

1

-4/3

1

0

2

-1/3

0

1

3

Baris kunci

Operasi Gauss-Jordan untuk menghasilkan solusi baru (iterasi 1) Baris 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 Baris z baru = Baris z – (167) × Baris x2 baru = [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]

44


Operasi Gauss-Jordan untuk 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 :

45

Basis

x1

x2

r1

Z

0

0

1/5

x1

1

0

1/5

3/5

x2

0

1

-3/5

s1

0

0

1


R1

R3

s1

Solusi

0

18/5

-3/5

0

3/5

-4/5

3/5

0

6/5

1

-1

1

5

-492/5 -501/5

Penentuan variabel masuk dan keluar Dari tabel diatas, terlihat bahwa fungsi tujuan Z = 18/5. Selanjutnya dicari lagi variabel masuk pada baris Z (fungsi

tujuan) yang mempunyai koefisien positif terbesar, ditemukan r1 dengan koefisien 1/5 sebagai variabel masuk. Syarat optimal ditunjukkan bahwa r1 adalah variabel masuk

Masuk Solusi Rasio 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 pada variabel basis x1 dan ini adalah variabel keputusan. Sehingga tidak ada lagi syarat kelayakan yang dapat dilakukan dan tabel simpleks diatas adalah yang paling optimal. Basis

46


Metode dua fase Dalam metode M, penggunaan penalty M,

dimana didefinisikan nilainya harus relative besar terhadap koefisien obyektif actual dari model, dapat menghasilkan kisaran error yang dapat melemahkan akurasi perhitungan simpleks. Metode dua fase mengurangi kelemahan ini dengan menghilangkan konstanta M. Metode ini menyelesaikan kasus LP dalam dua fase : Fase I berusaha untuk mencari solusi layak awal, dan jika ditemukan, maka Fase II dijalankan untuk

menyelesaikan masalah aslinya. 47


Langkah-langkah metode dua fase Fase I Kondisikan masalah dalam bentuk persamaan, dan

tambahkan variabel buatan yang diperlukan pada constraint (seperti metode M) untuk mengaman basis solusi awal. Cari solusi basis dari persamaan yang didapatkan itu, tanpa memandang LP adalah memaksimalkan atau meminimalkan, selalu meminimalkan jumlah dari variabel buatan. Jika nilai minimum penjumlahan adalah positif, masalah LP tidak mempunyai solusi layak, sehingga merupakan akhir proses. Jika tidak, lanjutkan ke fase II. Fase II Gunakan solusi layak dari fase I sebagai basis solusi

awal layak pada masalah yang sesungguhnya.

48


Mengacu pada contoh di metode M Minimalkan Z = 4x1 + x2 Constraint : 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1, x2 ≥ 0

49


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 x1 + 2x2

+ s1 x1, x2, r1, s1 ≥ 0 50


=6 =4

Penyelesaian dengan metode dua fase – Fase I Minimalkan R = R1 + R2 Kendala : 3x1 + x2 + R1 =3 4x1 + 3x2 – r1 + R2 x1 + 2x2 + s1 x1, x2, r1, s1, R1, R2 ≥ 0 Tabel simpleksnya tampak sebagai berikut :

Basis R R1 R2 s1 51

x1 0 3 4 1

x2 0 1 3 2


r1 0 0 -1 0

R1 -1 1 0 0

R3 -1 0 1 0

=6 =4

s1 0 0 0 1

Solusi 0 3 6 4

Penyelesaian dengan metode dua 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 = [7 4 -1 0 0 0 9] Tabel simpleks berubah menjadi :

Basis R R1 R2 s1 52

x1 7 3 4 1

x2 4 1 3 2


r1 -1 0 -1 0

R1 0 1 0 0

R3 0 0 1 0

s1 0 0 0 1

Solusi 9 3 6 4

Penyelesaian dengan metode dua fase – Fase I (cont’d)

53


Penyelesaian dengan metode dua fase – Fase I (cont’d) x1 terpilih sebagai kolom kunci (memenuhi syarat optimal

meminimalkan karena mempunyai koefisien positif terbesar). Perhitungan rasio dan syarat kelayakan ditampilkan dalam tabel dibawah ini :

54

Basis

x1

x2

r1

R1

R3

s1

R

7

4

-1

0

0

0

R1

3

1

0

1

0

0

3

R2

4

3

-1

0

1

0

6

3/3 = 1 minimal 6/4 = 1.5

s1

1

2

0

0

0

1

4

4/1 = 4


Solus Rasio i 9

Penyelesaian dengan metode dua fase – Fase I (cont’d) R1 menjadi variabel keluar dan x1 menjadi variabel

masuk. Perubahan pada tiap baris dengan Operasi GaussJordan untuk menghasilkan solusi baru Baris 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 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]

55


Penyelesaian dengan metode dua 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] Perubahan tabel simpleks menjadi :

Basis R x1 R2 s1 56

x1 0 1 0 0

x2 5/3 1/3 5/3 5/3


r1 -1 0 -1 0

R1 -7/3 1/3 -4/3 -1/3

R3 0 0 1 0

s1 0 0 0 1

Solusi 2 1 2 3

Penyelesaian dengan metode dua 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 tabel dibawah ini : Basis R x1 R2

x1 0 1 0

x2 5/3 1/3 5/3

r1 -1 0 -1

R1 -7/3 1/3 -4/3

R3 0 0 1

s1 0 0 0

s1

0

5/3

0

-1/3

0

1

Solusi Rasio 2 1 1/(1/3) = 3 2 2/(5/3) = 1.2 minimal 3 3/(5/6) = 3.6

Dari tabel tersebut, R2 menjadi variabel keluar dan x2 menjadi

variabel masuk.

57


Penyelesaian dengan metode dua fase – Fase I (cont’d) Operasi Gauss-Jordan untuk menghasilkan solusi

baru Baris 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 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] 58


Penyelesaian dengan metode dua 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] – [0 5/3 -1 -4/3 1 0 2] = [0 0 1 1 -1 1 1]

Perubahan tabel simpleks menjadi :

59


Penyelesaian dengan metode dua fase – Fase I (cont’d) Basis

x1

x2

r1

R1

R3

s1

Solusi

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 ada

koefisien 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 kita dapat menghilangkan kolom tersebut dari tabel dan dilanjutkan ke fase II. 60


Penyelesaian dengan metode dua fase – Fase II Setelah penghapusan kolom variabel buatan,

masalah asli menjadi : Minimalkan Z = 4x1 + x2

Constraint : x1 + 1/5 r1 = 3/5 x2 – 3/5 r1 = 6/5 r1 + s1 = 1 x1, x2, r1, s1 ≥ 0

61


Penyelesaian dengan metode dua fase – Fase II (cont’d) Basis Z x1 x2 s1

x1 -4 1 0 0

x2 -1 0 1 0

r1 0 1/5 -3/5 1

s1 0 0 0 1

Solusi 0 3/5 6/5 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 : 62


Penyelesaian dengan metode dua 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

s1

0

0

1

1

1

Kasusnya adalah meminimalkan, sehingga dicari koefisien

variabel dalam z-row yang mempunyai nilai positif terbesar. Didapatkan r1 bernilai positif terbesar, sehingga menjadi kolom kunci (memenuhi syarat optimal meminimalkan karena mempunyai koefisien positif terbesar) 63



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

x2

0

1

-3/5

0

6/5

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

s1

0

0

1

1

1

1/1 = 1 minimal

s1 menjadi variabel keluar dan r1 menjadi variabel

masuk

64


Penyelesaian dengan metode dua fase – Fase II (cont’d) Operasi Gauss-Jordan untuk menghasilkan solusi

baru Baris kunci Ganti s1 pada kolom Basis dengan r1 Baris r1 baru = Baris s1 ÷ elemen kunci = [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] 65


Penyelesaian dengan metode dua fase – Fase II (cont’d) 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 = [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]

Perubahan tabel simpleks menjadi :

66



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

r1

0

0

1

1

1

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 67


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

bisa dilakukan ketika semua variabel buatan tersebut sudah menjadi variabel nonbasis. Jika satu atau lebih variabel buatan adalah basis (pada level nol) di akhir fase I, maka langkah tambahan berikut ini harus dilakukan untuk menghilangkannya sebelum masuk ke fase II Langkah 1 Pilih variabel buatan nol untuk meninggalkan basis solusi dan

rangcanglah 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.

68


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 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

69


Manajemen Sains. Pemrograman Linier (Metode Simpleks) Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011

Recommend Documents