Taufiqurrahman 1

Metode Simplex Pemrograman Linear

Latar Belakang • Sulitnya menggambarkan grafik berdimensi banyak atau kombinasi lebih dari dua variabel. • Metode grafik tidak mungkin dapat dilakukan untuk menyelesaikan masalah program linear yang melibatkan lebih dari dua variable.

PROGRAM LINEAR: METODE SIMPLEX

• Dalam keadaan ini (variabel lebih dari dua) dibutuhkan metode lain yang sering disebut sebagai metode algoritma simplex. • Metode ini diperkenalkan oleh George B Dantzig pada tahun 1947. 6623 - Taufiqurrahman

Metode Simplex

Bentuk Standar

• Metode simpleks merupakan prosedur iterasi yang bergerak bertahap dan berulang.

Bentuk standar LP memiliki sifat sbb. :

• Jumlah variabel tidak terbatas

2. Ruas kanan non negatif.

• Penyelesaian masalah LP dengan metode simplex harus menggunakan bentuk standar. 6623 - Taufiqurrahman

6623 - Taufiqurrahman

3

2

1. Seluruh fungsi kendala harus berbentuk persamaan ( bertanda = ). 3. Seluruh variabel merupakan variabel non negatif. 4. Fungsi tujuan dapat berupa maksimasi atau minimasi. 6623 - Taufiqurrahman

4

1


Merubah Ke Bentuk Standar


1. Fungsi Kendala (constraint) •

•

Kendala bertanda “≤” diubah menjadi persamaan dengan menambah “Variabel Slack” pada ruas kiri fungsi kendala.

Contoh:

Contoh:

X1

+

6X2

+

6X2

≤

10

=

10

X1 Berubah Menjadi

Berubah Menjadi

X1

+

S1

X1

+

6X2

+

6X2

−

S2

≥

10

=

10

S2 ≥ 0, 0 merupakan variabel surplus.

S1 ≥ 0, merupakan variabel slack, menyatakan sumber yang tidak terpakai.


Kendala bertanda “≥” diubah menjadi persamaan dengan mengurangi suatu “Variable Surplus” pada ruas kiri fungsi kendala.

•

Ruas kanan bertanda negatif diubah menjadi positif dengan mengalikan kedua ruas dengan (–1)

•

Arah ketidaksamaan dapat berubahjika kedua ruas dikalikan (–1)

5


6


Penyelesaian Simpleks

2. Variabel

•

Metode simpleks: merupakan prosedur aljabar yang bersifat iteratif yang bergerak dengan mengikuti algoritma tertentu

•

Tahapan prosedur:

•

Jika variable Xj tidak terbatas dalam tanda, dapat dinyatakan sebagai dua variable non negatif dengan menggunakan subsitusi. Xj = Xj‘ − Xj”

•

;

1.

dimana : Xj‘ dan Xj” ≥ 0

 Identifikasi ruang solusi dengan cara merubah sebanyak:

Subsitusi dilakukan pada seluruh fungsi kendala dan fungsi tujuan.

(n – m = kolom – baris) variable, sehingga memiliki nilai nol.  Variabel bernilai nol  variable non basis,

3. Fungsi Tujuan • •

 Variabel bukan bernilai nol  variable basis.

Bentuk maksimasi = nilai negatif dari bentuk minimasi. Berlaku juga untuk sebaliknya.



Inisialisasi: mulai dari suatu titik ekstrem (0,0)

7

2.

Iteratif: bergerak menuju titik ekstrem terdekat yang lebih baik, dan ulangi untuk titik ekstrim lain.

3.

Berhenti: jika telah sampai pada titik ekstrim terbaik (titik optimum). 6623 - Taufiqurrahman

8

2


Tabel Simplex

Tabel Simplex

Basic

Z

X1

X2

X3

…

Xn

S1

S2

…

Sn

Z

1

-C1

-C2

-C3

…

-Cn

0

0

…

0

S1

0

a11

a12

a13

…

a1n

1

0

…

0

b1

S2

0

a21

a22

a23

…

a2n

0

1

…

0

b2

…

…

…

…

…

…

…

…

…

…

…

…

Sm

0

am1

am2

am3

…

amn

0

0

…

1

bn

Main Body 6623 - Taufiqurrahman

RHS

Main Body • Bidang yang berisi koefisien teknologi & kendala yang ada

Identity • Bidang yang berisi koefisien-koefisien dari variabel slack atau variabel artificial

Basic • Kolom yang berisi variabel basis yang diambil dari variabel slack/artificial pada saat iterasi pertama. Variabel-variabel ini secara bertahap akan diganti oleh variabel bukan basis pada iterasi berikutnya

Identity 9


10

Algoritma Simpleks

Algoritma Simple Simplexx

1. Ubah fungsi tujuan ke dalam bentuk implisit. 2. Masukkan semua nilai ke dalam tabel simplex. 3. Tentukan kolom kunci (variable keputusan) yang masuk sebagai variable basis (entering variable). ⤷ Kolom kunci adalah nilai Zj dengan nilai negatif terbesar (untuk maksimasi). 4. Tentukan baris kunci: untuk menentukan variable yang akan keluar dari baris kunci (leaving variable). ⤷ Kriteria: Nilai positif terkecil dari: nilai kanan/nilai pada kolom kunci. ⤷ Angka kunci : nilai pada perpotongan baris kunci dan kolom kunci

5. Susun tabel simpleks baru, untuk menentukan solusi yang baru gunakan metode (Elementary Row Operation, Gauss Jordan Elimination), dengan cara: Ubah nilai pada baris kunci sehingga EV memiliki nilai 0 dan 1 pada baris lainnya.




11

Nilai baris kunci baru = nilai baris kunci yang lama dibagi angka kunci 6. Ubah nilai pada baris selain baris kunci Nilai baris baru = nilai baris lama dikurangi dengan hasil perkalian angka pada kolom kunci dengan baris kunci yang baru 7. Ulangi langkah diatas sampai tidak terdapat nilai negatif pada baris Z. ⤷ Iterasi berhenti jika tabel sudah optimal, jika: • semua nilai pada baris Z bernilai positif atau nol (untuk maksimasi) • bernilai negatif atau nol (untuk minimasi) 12

3


Ketentuan Metode Simplex

Contoh #5 – 1

1.

Nilai kanan (NK/RHS) fungsi tujuan harus nol (0).

2.

Nilai kanan (NK/RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikalikan (–1).

• Fungsi tujuan: Maksimalkan Z = 3x1 + 5x2

3.

Fungsi kendala dengan tanda “≤” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut juga variabel dasar.

4.

Fungsi kendala dengan tanda “≥” diubah ke bentuk “≤” dengan cara mengalikan dengan (–1), lalu diubah ke bentuk persamaan dengan ditambahkan variabel slack. Kemudian karena RHS-nya negatif, dikalikan lagi dengan (–1) dan ditambah artificial variable (M).

5.

Fungsi kendala dengan tanda “=” harus ditambah artificial variable (M). 6623 - Taufiqurrahman

• Fungsi Kendala: 1) 2x1 ≤ 8 2) 3x2 ≤ 15 3) 6x1 + 5x2 ≤ 30

13


14

Penyelesaian Simplex (Langkah 1)


1. Mengubah fungsi tujuan dan fungsi kendala (lihat ketentuan metode simplex simplex)).

2. Menyusun persamaan persamaan--persamaan ke dalam tabel simplex simplex..

• Fungsi tujuan: Z = 3x1 + 5x2

Var. Dsr

Z

x1

x2

s1

s2

s3

NK

Z

1

−3

−5

0

0

0

0

s1

0

2

0

1

0

0

8

s2

0

0

3

0

1

0

15

s3

0

6

5

0

0

1

30

⇨ Z − 3x1 − 5x2 = 0

Index

• Fungsi kendala: 1) 2x1 2)

≤8 3x2 ≤ 15

3) 6x1 + 5x2 ≤ 30

⇨ 2x1 ⇨

+ s1 3x2

⇨ 6x1 + 5x2

=8 + s2

= 15 + s3 = 30

Catatan: s1, s2, dan s3 adalah variabel slack. 6623 - Taufiqurrahman


15


16

4




3. Memilih kolom kunci (yaitu kolom yang mempunyai nilai pada baris Z (fungsi tujuan) yang bernilai negatif (−) dengan angka terbesar terbesar)).

4. Memilih baris kunci (yaitu baris yang mempunyai nilai index terkecil) terkecil).. Perhitungan index adalah sbb sbb.. : Index terkecil

Nilai negatif terbesar

Var. Dsr

Z

x1

x2

s1

s2

s3

NK

0

Z

1

−3

−5

0

0

0

0

0

8

s1

0

2

0

1

0

0

8

∼

1

0

15

s2

0

0

3

0

1

0

15

5

0

1

30

s3

0

6

5

0

0

1

30

6

Var. Dsr

Z

x1

x2

s1

s2

s3

NK

Z

1

−3

−5

0

0

0

s1

0

2

0

1

0

s2

0

0

3

0

s3

0

6

5

0

Index


17

Pada langkah 5, S2 akan berubah menjadi X2

Angka kunci

Index

Koefisien angka kolom kunci (KAAK)


18



5. Mengubah nilai nilai--nilai baris kunci (dengan cara membaginya dengan angka kunci kunci)). Angka kunci merupakan nilai yang posisinya berada pada perpotongan antara kolom kunci dengan baris kunci

6. Membuat baris baru dengan mengubah nilai nilai--nilai baris (selain baris kunci) sehingga nilai nilai--nilai kolom kunci = 0, dengan mengikuti perhitungan sbb sbb.. :

Var. Dsr

Z

x1

x2

s1

s2

s3

NK

Z

1

−3

−5

0

0

0

0

s1

0

2

0

1

0

0

8

∼

x2

0

0

1

0

1/3

0

5

s3

0

6

5

0

0

1

30



NBBK = Nilai baris baru kunci

Index

5

Baris Z Baris lama [ −3 NBBK −5 [ 0

−5 1

0 0 0 0 1/3 0

0 ] 5 ]

6

Baris baru

0

0 5/3 0

25

•

19

−3


20

5


Penyelesaian Simplex (Langkah 6) •

•

Baris s1 Baris lama NBBK

[ 2 0[ 0

0 1

1 0 0 0 1/3 0

8 ] 5 ]

Baris baru

2

0

1

8

0

0

Penyelesaian Simplex (Langkah 6) Masukkan nilai baris baru Z, s1, dan s3 ke dalam tabel, sehingga tabel menjadi seperti berikut: Var. Dsr

Z

x1

x2

s1

s2

s3

NK

Z

1

−3

0

0

5/3

0

25

Baris s3 Baris lama NBBK

s1

0

2

0

1

0

0

8

[ 6 5[ 0

5 1

0 0 1 0 1/3 0

30 ] 5 ]

x2

0

0

1

0

1/3

0

5

Baris baru

6

0

0 −5/3 1

5

s3

0

6

0

0

−5/3

1

5


21


Hasil dari langkah 3 dan langkah 4 : Var. Dsr

Z

x1

x2

s1

s2

s3

NK

Z

1

−3

0

0

5/3

0

25

s1

0

2

0

1

0

0

8

4

x2

0

0

1

0

1/3

0

5

∼

s3

0

6

0

0

−5/3

1

5

5/6


22


7. Melanjutkan perbaikan-perbaikan (langkah 3-6) sampai baris Z tidak ada nilai negatif.



Index

Index

23

Hasil dari langkah 5 dan langkah 6 : Var. Dsr

Z

x1

x2

s1

s2

s3

Z

1

0

0

0

5/6

1/2 27½

s1

0

0

0

1

5/9

−1/3

6⅓

x2

0

0

1

0

1/3

0

5

x1

0

1

0

0

−5/18 1/6

NK

Index Zmax

5/6

Karena nilai Z sudah tidak ada yang (−), maka sudah dapat diperoleh hasil solusi optimum, yaitu: x1 = 5/6 ; x2 = 5 ; Zmax = 27½ 6623 - Taufiqurrahman

24

6


Penyimpangan Bentuk Standar (Kendala =)

Langkah Solusi Kendala (=) .... 1

• Fungsi kendala dengan tanda (=)  Ditambahkan variabel buatan (M) pada fungsi tujuan

• Nilai setiap variabel dasar (s3) harus sebesar 0, sehingga fungsi tujuan harus dikurangi dengan M dan dikalikan dengan baris batasan yang bersangkutan (kendala 3). Nilai baris Z sebagai berikut :

• Contoh : Fungsi Kendala: 1) 2x1 ≤8 2) 3x2 ≤ 15 3) 6x1 + 5x2 = 30 Fungsi Tujuan: Z = 3x1 + 5x2

 2x1 + s1  3x2 + s2  6x1 + 5x2 + s3

=8 = 15 = 30

Baris Z −3

−5

0 0 M

0

]

M [ 0

6

5

0 0 1

30

]

1 (−6M−3) (−5M−5) 0 0 0 (−30M)  Z − 3x1 + 5x2

+ Ms3 = 30


25



26


• Iterasi 0:

• Iterasi 1:

VD

Z

Z

1

s1

0

2

s2

0

s3

0

x1

x2

s1

s2

s3

NK

0

0

0

(−30M)

0

1

0

0

8

4

0

3

0

1

0

15

6

5

0

0

1

30

s2

s3

NK

0

0

(−6M+12)

(−6M−3) (−5M−5)

VD

Z

x1

Z

1

0

x1

0

1

0

1/2

0

0

4

s2

0

0

3

0

1

0

15

s3

0

0

5

0

0

1

6

x2

s1

(−5M−5) (3M+3/2)



[ 1

Index

VD

Z

x1

x2

s1

s2

s3

NK

Z

1

0

0

−3/2

0

M+1

18

x1

0

1

0

1/2

0

0

4

8

∼

s2

0

0

0

9/5

1

−3/5

19/3

5/27

5

x2

0

0

1

−3/5

0

1/5

6/5

−2

Index

Index

VD

Z

x1

x2

s1

s2

s3

NK

Index

Z

1

0

0

0

5/6

M+12

27 1/2

Zmax

x1

0

1

0

0

−5/18

1/6

5/6

x1

5

s1

0

0

0

1

5/9

−1/3

6 1/3

6/5

x2

0

0

1

0

1/3

0

5

∼

27


x2 28

7


Penyimpangan Bentuk Standar (Fungsi Tujuan Meminimalkan)

Langkah Solusi Kendala (=) .... 4 • Jadi solusi optimum dari permasalah adalah:  x1

= 5/6

 x2

=5

• Fungsi tujuan : Minimasi – Soal minimisasi harus diubah menjadi maksimisasi dengan cara mengganti tanda positif dan negatif pada fungsi tujuan. • Contoh : Fungsi Tujuan: Minimumkan Z = 3x1 + 5x2

 Zmax = 27 1/2

Fungsi Kendala: 1) 2x1 =8 2) 3x2 ≤ 15 3) 6x1 + 5x2 ≥ 30 6623 - Taufiqurrahman

29


30

Langkah Solusi Fungsi Tujuan Meminimalkan .. 1

Langkah Solusi Fungsi Tujuan Meminimalkan .. 2

• Fungsi kendala: 1) 2x1 = 8 ⇨ 2x1 + s1 =8 2) 3x2 ≤ 15 ⇨ 3x2 + s2 = 15 3) 6x1 + 5x2 ≥ 30 ⇨ 6x1 + 5x2 − s3+ s4 = 30

• Nilai setiap variabel dasar (s1 dan s4) harus = 0, maka: Baris Z

Catatan: s1, s2, dan s4 adalah variabel slack, sedangkan s3 adalah variabel surplus.

[ −1

3

5

M 0

0

M

0

]

−M [ 0

2

0

1 0

0

0

8

]

−M [ 0

6

5

0 0 −1

1

30

]

1 (−8M+3) (−5M+5) 0 0

• Fungsi tujuan menjadi:

M

0 (−38M)

Maksimumkan (−Z) = −3x1 − 5x2 − Ms1 − Ms4  menjadi fungsi implisit  −Z + 3x1 + 5x2 + Ms1 + Ms4 = 0 6623 - Taufiqurrahman


31


32

8


Langkah Solusi Fungsi Tujuan Meminimalkan .. 3 • Iterasi 0: VD

Z

Langkah Solusi Fungsi Tujuan Meminimalkan .. 5 • Iterasi 0:

x1

x2

(−8M+3) (−5M+5)

s1

s2

s3

s4

NK

Index

VD

Z

x1

x2

s1

s2

s3

s4

NK

Z

−1

0

0

M

0

(−38M)

Z

−1

0

0

(M+3/2)

0

1

s1

0

2

0

1

0

0

0

8

4

x1

0

1

0

1/2

0

0

s2

0

0

3

0

1

0

0

15

∼

s2

0

0

1

9/5

1

3/5

−3/5 5 2/5

s3

0

6

5

0

0

−1

1

30

5

x2

0

0

1

−3/5

0

−1/5

1/5

VD

Z

x1

Z

−1

3

x2

x1

0

1

0

s2

0

0

3

s3

0

0

5

s1

s2

s3

s4

NK

0

M

0

(−6M−12)

½

0

0

0

4

0

1

0

0

15

5

−3

0

−1

1

6

6/5

(−5M+5) (4M−3/2)

Index ∼


33

M+1 (−18) 0

4 6/5

Index Zmin x1 x2

• Karena (–Z) = (−18), maka Z = 18 • Penyelesaian telah mencapai solusi optimum:  x1 =4;  x2 = 6/5 ;  Zmin = 18 6623 - Taufiqurrahman

34


36

Tugas • Buat menjadi 3 kelompok. (Di absen ada 39 org, jadi maksimal tiap kelompok berjumlah 13 org). • Soal lihat di hybrid learning atau http://taufiqurrahman.blog.esaunggul.ac.id

di

blog:

• Jawaban dibuat dalam power point dan dikirm ke email: [email protected] dan di cc. ke: [email protected] • Waktu pengiriman, maksimal 1 hari sebelum pertemuan ke-7 (tgl. 26 Maret 2012), pkl. 16.00 wib. 6623 - Taufiqurrahman


35

9

Taufiqurrahman 1

Recommend Documents