Metode Simpleks

MATERI OPERASI RISET

“METODE SIMPLEKS”

OLEH

KELOMPOK 2D

1.     Baiq Ayu Rukmana           (1501030405)

2.     Ummul Quro                     (1501030407)

3.     Wiaan Aelia Paramudita    (1501030417)

4.     Meri Kartika                       (1501030421)

5.     Murniati                              (151144132)

PROGRAM STUDI TADRIS MATEMATIKA

FAKULTAS TARBIYAH DAN KEGURUAN

UNIVERSITAS ISLAM NEGERI (UIN) MATARAM

2017

METODE SIMPLEKS

Definisi :

Menurut Media Anugerah Ayu (1993:35) Metode Simpleks adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linier yang didasarkan pada proses iterasi. Menurut Eddy Herjanto (1999:191) Metode Simpleks adalah suatu metode sistematis dimulai dari suatu penyelesaian yang fisibel ke pemecahan dasar fisibel lainnya, yang dilakukan berulang-ulang (iterative) sehingga tercapai suatu penyelesaian optimum.

Bentuk Standar :

Maksimalkan/Minimalkan : Z = C₁X₁ + C₂X₂ + C₃X₃ + … + C_nX_n

Fungsi pembatas:

a₁₁X₁ + a₁₂X₂ + a₁₃X₃ + … + a_1nX_n ≤ b₁

a₂₁X₁ + a₂₂X₂ + a₂₃X₃ + … + a_2nX_n ≤ b₂

. . . . . .

a_m1X₁ + a_m2X₂ + a_m3X₃ + … + a_mnX_n ≤ b_m

Beberapa ketentuan yang perlu diperhatikan, antara lain:

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

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

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 variabel (M).

5.      Fungsi kendala dengan tanda “=” harus ditambah artificial variabel (M).

Contoh Soal 1:

Maksimumkan Z = 3X₁ + 5X₂

Dengan fungsi kendala:

1) 2X₁  ≤ 8

2) 3X₂  ≤ 15

3) 6X₁ + 5X₂ ≤ 30

Langkah-langkah Penyelesaian:

1.      Mengubah fungsi tujuan dan fungsi kendala

Fungsi tujuan:

Z = 3X₁ + 5X₂ => Z - 3X₁ - 5X₂ = 0

Fungsi kendala:

1) 2X₁ ≤ 8 => 2X₁ + X₃ = 8

2) 3X₂ ≤ 15 => 3X₂ + X₄ = 15

3) 6X₁ + 5X₂ ≤ 30 => 6X₁ + 5X₂ + X₅ = 30

(X₃, X₄ dan X₅ adalah variabel slack)

2.      Menyusun persamaan-persamaan ke dalam tabel

3.      Memilih kolom kunci

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif dengan angka terbesar.

4.      Memilih baris kunci

Indeks = Nilai kanan (NK) dibagi nilai kolom kunci

Baris kunci adalah baris yang mempunyai index terkecil

5.      Mengubah nilai-nilai baris kunci

Baris baru kunci = Baris kunci dibagi angka kunci

Sehingga tabel menjadi seperti berikut:

6.      Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci (selain baris kunci) = 0

Baris baru = baris lama – (koefisien angka kolom kunci x nilai baris baru kunci)

Masukkan nilai di atas ke dalam tabel, sehingga tabel menjadi seperti berikut:

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

Diperoleh hasil: X₁ = 5/6 , X₂ = 5, Zmax = 27 ½

Contoh Soal 2:

Minimumkan Z = 3X₁ + 5X₂

Fungsi kendala:

1) 2X₁ = 8

2) 3X₂ ≤ 15

3) 6X₁ + 5X₂ ≥ 30

Penyelesaian:

Fungsi batasan:

1) 2X₁ + X₃ = 8

2) 3X₂ + X₄ = 15

3) 6X₁ + 5X₂ -X₅ + X₆ = 30

Fungsi tujuan menjadi:

Maksimumkan (-Z) = -3X₁ – 5X₂ –MX₃ – MX₆

Diubah menjadi fungsi implisit => -Z + 3X₁ + 5X₂ + MX₃ + MX₆ = 0

Nilai–nilai variabel dasar (X₃ dan X₆ ) harus = 0, maka:

Tabel :

(karena –Z= -18, maka Z=18). Penyelesaian optimal: X₁ = 4, X₂ = 6/5 dan Zmin = 18

Soal Latihan:

1.      Selesaikan program linier berikut ini dengan metode Simpleks

Maksimumkan Z = 400X1 + 300X2

Fungsi kendala/ batasan:

1) 4X₁ + 6X₂ ≤ 1200

2) 4X₁ + 2X₂ ≤ 800

3) X₁ ≤ 250

4) X₂ ≤ 300

2.      Selesaikan program linier berikut ini dengan metode Simpleks

Maksimumkan Z = 2X₁ + 3X₂ + X₃

Dengan fungsi kendala:

1) X₁ + X₂ + X₃ ≤ 9

2) 2X₁ + 3X₂ ≤ 25

3) X₂ + 2X₃ ≤ 10

4) X₁, X₂, X₃ ≥ 0

3.      Selesaikan program linier berikut ini dengan metode Simpleks

Maksimumkan Z = 2X₁ + 3X₂

Dengan fungsi kendala:

1)     2X₁  +   X₂ ≤ 4

2)     X₁ + 2X₂ ≤ 5

3)     X₁, X₂ ≥ 0

4.      Selesaikan program linier berikut ini dengan metode Simpleks

Minimumkan Z = 3X₁ + 2X₂

Fungsi batasan :

1) X₁ + 2X₂ ≥ 20

2) 3X₁ + X₂ ≥ 20

3) X₁, X₂ ≥ 0

5.      Selesaikan program linier berikut ini dengan metode Simpleks

Minimumkan Z = 40 X₁ + 20 X₂

Fungsi batasan:

1)     3 X₁ + X₂ ≥ 27

2)     X₁ + X₂ ≥ 21

3)     X₁ + 2 X₂ ≥ 30

4)     X₁, X₂ ≥ 0