Inilah Materi hingga Contoh Soal dari Metode Simpleks (+ Video Materi)

Assalamu‘alaikum wr. wb.

Halo gais, Jika sebelumnya, sudah membahas tentang Akar-akar Persamaan, sekarang kita akan membahas tentang Metode Simpleks untuk menyelesaikan dari Persamaan dan Pertidaksamaan, baik itu dalam Model Matematika maupun dalam bentuk Penyelesaian Akhir.

Ilustrasi Metode Simpleks

MATERI DAN CONTOH SOAL

Sumber Materi : Manjakan.com, Bundet.com, dan Studocu.com (Contoh Soal - PDF DOC)

Pernahkah Anda mendengar tentang Metode Simpleks? Suatu metode dimana salah satu teknik penyelesaian dalam program linear digunakan untuk pengambilan keputusan.

Selain jalur ini, metode ini juga terkait erat dengan alokasi sumber daya yang optimal. Masih belum jelas tentang Metode Simpleks? Simak penjabarannya di bawah ini.

A. Pengertian Metode Simpleks

Tabel Penyelesaian dalam Metode Simpleks

Metode simpleks adalah algoritma yang digunakan untuk menghitung dan menyimpan banyak angka dalam iterasi-iterasi, serta bermanfaat untuk pengambilan keputusan pada iterasi selanjutnya.

Metode ini digunakan untuk menyelesaikan masalah pada program linear dengan banyak pertidaksamaan dan variabel. Metode simpleks berguna untuk menyelesaikan masalah program linear setelah diubah ke dalam bentuk umum.

Untuk dapat menggunakan metode simpleks, model program linear harus diubah ke dalam bentuk umum, yang memiliki kendala berupa persamaan dan sisi kanan yang non-negatif. Fungsi tujuan dapat dimaksimalkan atau diminimalkan sesuai dengan kebutuhan.

B. Istilah-istilah dalam Metode Simpleks

Ada banyak istilah dalam metode searah. Namun hanya beberapa yang biasa digunakan. Kata benda apa yang biasa digunakan dalam istilah sumbu? Lihat pernyataan berikut.

1. Iterasi

Ada banyak istilah dalam metode simpleks, salah satunya Iterasi. Iterasi adalah tahapan perhitungan dalam metode simpleks yang bergantung pada nilai tabel sebelumnya.

2. Variabel Basis

Variabel basis adalah variabel yang memiliki nilai bukan 0 (Nol) pada setiap iterasi. Pada awalnya, variabel basis adalah variabel slack atau variabel buatan, dan jumlah nilai variabel basis hampir selalu sama dengan jumlah fungsi pembatas.

3. Variabel Non Basis

Variabel non basis adalah variabel yang nilainya selalu menjadi nol pada setiap iterasi, dan jumlah variabel non basis selalu sama dengan derajat bebas dalam sistem persamaan.

4. Solusi

Solusi atau nilai kanan adalah nilai sumber daya pembatas yang masih tersedia, dan jumlah yang dihasilkan sama dengan jumlah sumber daya pada pembatas awal yang ada sebelum aktivitas dilakukan.

5. Variabel Slack

Variabel Slack dalam Metode Simpleks digunakan untuk mengonversi pertidaksamaan menjadi persamaan, dan pada solusi awal berperan sebagai variabel basis.

Penambahan variabel bisa terjadi pada setiap tahap inisialisasi. Sedangkan pada solusi awal, variabel ini berguna sebagai variabel basis.

6. Variabel Surplus

Berbeda dengan Variabel Slack, Variabel Surplus adalah variabel yang dikurangi dari model matematik jenis kendala, dan digunakan untuk mengkonversi pertidaksamaan menjadi persamaan variabel.

Menambahkan variabel ke surplus ini terjadi selama langkah inisialisasi. Berbeda dengan variabel slack, dalam solusi asli variabel residual tidak dapat digunakan untuk variabel basis.

7. Variabel Buatan Metode Simpleks

Variabel buatan dalam metode simpleks adalah variabel buatan yang ditambahkan ke dalam model matematika jenis kendala. Bentuk variabel buatan biasanya berupa ≥ atau =. Variabel buatan berfungsi sebagai variabel untuk basis awal pada tahap inisialisasi.

Variabel buatan ditambahkan pada tahap inisialisasi dan harus bernilai 0 pada solusi optimal. Hal ini karena variabel buatan sebenarnya tidak ada dalam kenyataannya, hanya ada dalam model matematika.

8. Kolom Pivot

Kolom pivot dalam metode simpleks juga disebut kolom kerja. Kolom kerja bertugas untuk memuat nilai dari variabel yang masuk. Nilai koefisien pada kolom kerja akan menjadi pembagi nilai kanan. Kolom pivot sangat berguna untuk menentukan baris pivot atau baris kerja.

9. Baris Pivot

Baris pivot juga dikenal sebagai baris kerja dalam metode simpleks. Baris kerja adalah baris yang ada dalam metode simpleks dan berisi variabel basis yang memuat variabel keluar.

10. Elemen Pivot

Elemen pivot juga disebut elemen kerja. Elemen pivot terletak pada potongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan dalam tabel simpleks selanjutnya.

11. Variabel Masuk

Variabel masuk adalah variabel non basis yang dipilih sebagai basis pada iterasi selanjutnya. Pada setiap iterasi, salah satu variabel non basis dipilih sebagai variabel masuk.

12. Variabel keluar

Variabel keluar adalah variabel basis pada iterasi sebelumnya yang digantikan oleh variabel masuk pada iterasi selanjutnya dalam metode simpleks.

C. Tahapan-tahapan pada Metode Simpleks

Setiap metode pasti memiliki cara yang wajib dipatuhi agar hasil penelitian akurat. Seperti metode simpleks. Metode ini juga memiliki langkah-langkah yang harus diikuti, antara lain :

1. Periksa Tabel Layak Atau Tidak

Tahapan awal dalam metode simpleks adalah memeriksa kelayakan tabel simpleks berdasarkan solusi yang dihasilkan. Jika solusi negatif, maka tabel dianggap tidak layak dan tidak dapat diteruskan lebih lanjut.

2. Tentukan Kolom Pivot

Langkah kedua adalah menentukan kolom pivot berdasarkan koefisien fungsi tujuan. Untuk maksimisasi, kolom pivot adalah kolom dengan koefisien negatif.

Sedangkan untuk minimisasi adalah kolom dengan koefisien positif terbesar. Kemudian, kolom pivot yang ditandai ditarik ke atas untuk menghasilkan variabel keluar.

3. Menentukan Baris Pivot Simpleks

Tahapan ketiga menentukan baris pivot. Tahap yang dikerjakan baris pivot dalam sesi ini ditentukan seusai pembagian nilai solusi dengan nilai kolom pivot yang pas. Saat menentukan baris pivot, nilai negatif dan 0 pada kolom pivot tidak harus dilihat. Itu artinya nilai negatif atau 0 tidak ikut menjadi pembagi.

Baris pivot memiliki rasio pembagian paling kecil. Pada saat baris pivot ditarik ke kiri, hasilnya akan menunjukkan variabel keluar. Jika dalam rasio pembagi terkecil hasilnya lebih dari satu, pilihlah satu secara acak atau sembarang.

4. Tentukan Elemen Pivot Simpleks

Langkah keempat adalah menentukan elemen pivot, yaitu elemen yang terletak di dalam potongan kolom dan baris pivot.

5. Bentuk Tabel Simpleks Baru

Kelima, membentuk tabel simpleks baru. Tabel simpleks baru ini dibentuk saat pertama kali menghitung nilai baris pivot yang baru. Baris pivot yang baru juga merupakan baris pivot yang lama kemudian dibagi dengan elemen pivot.

Selanjutnya Baris yang baru lainnya merupakan hasil dari pengurangan nilai kolom pivot baris yang bersangkutan. Lalu, hasilnya tersebut dikali dengan baris pivot baru di dalam satu kolom dengan baris lamanya yang letaknya ada pada kolom yang sama.

D. Penyelesaian Metode Simpleks

Ada beberapa Tahapan dalam menyelesaikan Metode Simpleks, yaitu :

1. Mengubah Fungsi Tujuan dan Batasannya

Diubah menjadi fungsi implisit, artinya semua  digeser ke kiri.

Fungsi Tujuan :

 menjadi 

Fungsi Batasan :

Karena fungsi batasan berupa pertidaksamaan, maka cara merubahnya kebentuk implisit adalah dengan menambahkan Slack Variabel.

 menjadi 

 menjadi 

2. Menyusun Persamaan Ke Dalam Tabel

| Variabel Dasar | z | x1  | x2  | x3 | x4 | NK |
|----------------|---|-----|-----|----|----|----|
| z              | 1 | -25 | -25 | 0  | 0  | 0  |
| x3             | 0 | 3   | 2   | 1  | 0  | 6  |
| x4             | 0 | 2   | 4   | 0  | 1  | 8  |

3. Memilih Kolom Kunci

Pada baris Z terdapat dua nilai (-) yang sama besarnya, jadi harus dipilih salah satunya, dan itu bebas. Pada kasus ini saya pilih -25 di kolom x1.

4. Memilih Baris Kunci

Sebelum menentukan baris kunci, terlebih dahulu menghitung index variabel dasarnya, kecuali baris Z. Sehingga diperoleh hasil sebagai berikut :

5. Mengubah Nilai-nilai Baris Kunci

Didapat nilai kunci = 3.

6. Mengubah nilai-nilai selain baris kunci

Maka diperoleh hasil :

Tabel pertama (putih) nilai lama dan tabel kedua (berwarna) nilai baru,

7. Re-Optimasi

Dikarenakan baris Z pada tabel ke dua (berwarna) masih terdapat nilai negatif (-), maka diperlukan lagi optimasi dengan cara mengulangi langkah 3 s/d. 6.

Tabel optimasi ke 1.

| Variabel Dasar | z | x1 | x2    | x3   | x4 | NK | Indeks |
|----------------|---|----|-------|------|----|----|--------|
| z              | 1 | 0  | -25/3 | 25/3 | 0  | 50 |        |
| x1             | 0 | 1  | 2/3   | 1/3  | 0  | 2  |        |
| x4             | 0 | 0  | 8/3   | -2/3 | 1  | 4  |        |

1.) Memilih Kolom Kunci

2.) Memilih Baris Kunci

3.) Mengubah Nilai-nilai Baris Kunci

4.) Mengubah nilai-nilai selain baris kunci

Tabel yang diperoleh dari tabel pertama sampai dengan perbaikan/perubahan terakhir :

Karena pada baris fungsi tujuan (Z) sudah tidak ada yang bernilai negatif (-), maka sudah dianggap optimal dengan nilai x1 = 1, x2 = 3/2 dan Z max  = 125/2.

E. Contoh Soal Metode Simpleks

1. Selesaikan linear program berikut ini dengan metode simpleks. 

Maksimum Z = 60X₁ + 80X₂

Kendala :

• X₁ + 1,5X₂ ≤ 4.000
• 2X₁ + X₂ ≤ 4.000
• X₁, X₂ ≥ 0

Jawaban :

2. Selesaikan linear program berikut ini dengan metode simpleks. 

Maksimum Z = 4X + 3X 1 2

Kendala :

• X₁ + 0,6X ≤ 30 2
• 2X₁ ≤ 25
• X₂ ≤ 20
• X₁, X₂ ≥ 0

Jawaban :