Metode Simpleks

Metode ini merupakan salah satu cara lain untuk menyelesaikan masalah optimasi dalam
pemrograman linear. Metode simpleks digunakan ketika terdapat lebih dari atau 2 variabel
keputusan.
Konsep kunci dalam Metode Simpleks:
1. Fungsi Tujuan (Objective Function): merupakan persamaan matematika untuk tujuan
maksimasi atau minimasi contoh : 𝑍 = 5𝑥 + 7𝑦 atau 𝑍 = 4𝑥1 + 9𝑥2.
2. Variabel Keputusan (Decision Variables): variabel yang nilainya ingin kita cari untuk
mencapai keputusan. Misalkan 𝑥1 , 𝑥2 … . 𝑥𝑛 (terdapat minimal dua atau lebih dari dua
variabel).
3. Batasan/ Kendala (Constraints): serangkaian persamaan atau pertidaksamaan yang membatasi
nilai variabel keputusan. Contoh: 𝑥1 ≤ 3 atau 𝑥1 + 𝑥2 ≥ 7.
4. Daerah Layak (Feasible Region): Area grafis yang berisi semua kondisi nilai variabel
keputusan yang memenuhi semua batasan. Solusi optimal selalu berada di salah satu titik
sudut dari daerah ini.
5. Variabel Slack, Variabel Surplus, dan Variabel Buatan
6. Tabel Simpleks (Simplex Tableau): Representasi matriks yang digunakan untuk perhitungan
secara sistematis.

Berikut adalah langkah-langkah dalam pengerjaan Metode Simpleks:

1. Formulasi Masalah: Memodelkan masalah ke dalam bentuk matematis yang terdiri dari fungsi
tujuan dan batasan-batasan.
2. Standardisasi: Ubah pertidaksamaan batasan menjadi persamaan dengan menambahkan
variabel slack atau mengurangi variabel surplus.
3. Membuat Tabel Awal: Susun semua koefisien dari fungsi tujuan dan batasan ke dalam sebuah
matriks yang disebut Tabel Simpleks Awal.
4. Iterasi (Pengulangan)
• Pilih Kolom Pivot: Tentukan variabel mana yang akan masuk ke dalam solusi untuk
meningkatkan nilai fungsi tujuan. Kolom dengan nilai negatif terbesar di baris fungsi
tujuan.
• Pilih Baris Pivot: Tentukan variabel mana yang akan keluar dari solusi. Hitung rasio
antara nilai di kolom solusi dengan nilai di kolom pivot. Baris dengan rasio positif terkecil
itulah yang dipilih.
• Operasi Baris: Lakukan operasi baris untuk memperbarui tabel, sehingga variabel yang
masuk memiliki koefisien 1 di baris pivotnya dan 0 di baris lainnya.
5. Cek Optimasi: Ulangi langkah ke-4 sampai tidak ada lagi nilai negatif di baris fungsi tujuan.
Jika sudah tidak ada, berarti solusi optimal telah tercapai.
6. Interpretasi Hasil: Baca nilai variabel keputusan dan nilai optimal dari fungsi tujuan pada tabel
akhir.
SOAL 1
Seorang petani memiliki lahan seluas 100 hektar. Ia ingin menanam dua jenis tanaman yaitu
Jagung dan Kedelai. Setiap hektar Jagung dan Kedelai masing-masing memberikan keuntungan
sebesar $40 dan $30. Sumber daya yang tersedia sangat terbatas. Total pupuk yang tersedia 240
kg. Jagung membutuhkan 3 kg per hektar, dan Kedelai membutuhkan 2 kg per hektar.
Keseluruhan lahan yang tersedia adalah 100 hektar. Berapa hektar Jagung dan Kedelai yang harus
ditanam untuk memperoleh keuntungan maksimal?

Diketahui:
𝑍 = 40𝑥1 + 30𝑥2 , Maksimasi
Batasan:
1. 3𝑥1 + 2𝑥2 ≤ 240 (batasan pupuk)
2. 𝑥1 + 𝑥2 ≤ 100 (batasan lahan)
3. 𝑥1 , 𝑥2 ≥ 0 (batasan non-negative)
Penyelesaian:
1) Standarisasi (menambah variabel slack 𝑠1 , 𝑠2 )
Fungsi Tujuan: 𝑍 − 40𝑥1 − 30𝑥2 = 0
Batasan:
1. 3𝑥1 + 2𝑥2 + 𝑆1 = 240
2. 𝑥1 + 𝑥2 + 𝑆2 = 100

2) Tabel Simpleks Awal

Basis x1 x2 s1 s2 Solusi
Z -40 -30 0 0 0
s1 3 2 1 0 240
s2 1 1 0 1 100

3) Iterasi Pertama
1) Pilih Kolom Pivot : Pilih nilai negatif terbesar di baris Z
𝑆𝑜𝑙𝑢𝑠𝑖
2) Pilih Baris Pivot : Pilih nilai rasio terkecil. Rasio: 𝐾𝑜𝑙𝑜𝑚 𝑃𝑖𝑣𝑜𝑡
3) Nilai Pivot : pertemuan kolom 𝑥1 dan 𝑠1 adalah 3
Basis x1 x2 s1 s2 Solusi Rasio
Z -40 -30 0 0 0
s1 3 2 1 0 240 80
s2 1 1 0 1 100 100
Ket:
Kolom: dari atas ke bawah, Baris: dari kiri ke kanan
Kolom 𝑥1 merupakan kolom pivot karena bernilai -40 (negatif terbesar)
Baris 𝑠1 merupakan baris pivot karena memiliki rasio terkecil (80)
4) Buat Tabel Baru: 𝑥1 menggantikan 𝑠1 . Buat Elemen pivot menjadi1 (bagi garis
𝑠1 dengan 3 (nilai pivot)) dan nol kan nilai lain di kolom pivot.
 Basis x1 x2 s1 s2 Solusi
Z 0 -10/3 40/3 0 3200
x1 1 2/3 1/3 0 80
s2 0 1/3 -1/3 1 20
Tabel baru setelah Iterasi Pertama

4) Iterasi Kedua
10
Karena masih ada nilai negatif di Z (- 3 ), maka iterasi masih perlu dilakukan.
Basis x1 x2 s1 s2 Solusi Rasio

Z 0 -10/3 40/3 0 3200

x1 1 2/3 1/3 0 80 120

s2 0 1/3 -1/3 1 20 60

1) Pilih Kolom Pivot: Kolom 𝑥2 adadlah kolom pivot (karena memiliki nilai negatif pada
baris Z-nya.
2) Pilih Baris Pivot: 𝑠2 adalah baris pivot karena memiliki nilai rasio terkecil (60)
3) Nilai Pivot : Nilainya 1/3
4) Buat Tabel Baru: 𝑥2 masuk menggantikan baris 𝑠2
 Basis x1 x2 s1 s2 Solusi
Z 0 0 10 10 3400
x1 1 0 1 -2 40
x2 0 1 -1 3 60
Tabel baru setelah iterasi kedua. Sudah tidak ada nilai negatif di baris Z.

5) Interpretasi Hasil
Semua nilai di baris Z sudah positif atau nol, artinya solusi optimal sudah tercapai, dengan:
• Z = 3400: Keuntungan maksimal yang bisa didapat adalah $3400
• 𝑥1 = 40: Petani harus menanam 40 hektar Jagung.
• 𝑥2 = 60: Petani harus menanam 60 hektar Kedelai.
SOAL 2

Sebuah peternakan ingin membuat pakan ternak dengan biaya serendah mungkin, namun harus
memenuhi kebutuhan nutrisi minimum. Ada dua jenis bahan baku yaitu Bahan A dan Bahan B
dengan biaya masing-masing adalah $2 dan $3.

Kebutuhan nutrisi minimum adalah:

• Protein: Campuran harus mengandung minimal 12 unit. Bahan A menyumbang 4 unit/kg,

Bahan B 2 unit/kg.
• Vitamin: Campuran harus mengandung minimal 9 unit. Bahan A menyumbang 1 unit/kg,
Bahan B 3 unit/kg.

Tentukan komposisi campuran (kg Bahan A dan B) untuk biaya minimal.

Penyelesaian:

Diketahui:

𝑍 = 2𝑥1 + 3𝑥2 , Minimasi

Batasan:

1. 4𝑥1 + 2𝑥2 ≥ 12
2. 𝑥1 + 3𝑥2 ≥ 9
3. 𝑥1 , 𝑥2 ≥ 0

Langkah 1 Standarissi

1) Urangkan variable surplus (s) untuk mengubah menjadi persamaan.

• 4𝑥1 + 2𝑥2 − 𝑠1 = 12
• 𝑥1 + 3𝑥2 − 𝑠2 = 9

2) Tambahkan Variabel Buatan (A)

• 4𝑥1 + 2𝑥2 − 𝑠1 + 𝐴1 = 12
• 𝑥1 + 3𝑥2 − 𝑠2 + 𝐴2 = 9

3) Terapkan Metode Big M pada fungsi Tujuan:

• 𝑍 = 2𝑥1 + 3𝑥2 + 𝑀𝐴1 + 𝑀𝐴2

4) Siapkan Fungsi tujuan untuk tabel simpleks awal: Hilangkan variabel A

a) Dari Batasan, dapat diketahui:

• 𝐴1 = 12 − 4𝑥1 − 2𝑥2 + 𝑠1
• 𝐴2 = 9 − 𝑥1 − 3𝑥2 + 𝑠2

b) Substitusi ke fungsi Z:

• 𝑍 = 2𝑥1 + 3𝑥2 + 𝑀(12 − 4𝑥1 − 2𝑥2 + 𝑠1 ) + 𝑀(9 − 𝑥1 − 3𝑥2 + 𝑠2 )

c) Siapkan baris C untuk tabel dengan memindahkan semua variable ke sisi kiri

• 𝑍 + (5𝑀 − 2)𝑥1 + (5𝑀 − 3)𝑥2 − 𝑀𝑠1 − 𝑀𝑠2 = 21𝑀

Langkah 2

Tabel Awal Simpleks

Basis X1 X2 S1 S2 A1 A2 Solusi Rasio
Z 5M-2 5M-3 -M -M 0 0 21M
A1 4 2 -1 0 1 0 12 3
A2 1 3 0 -1 0 1 9 9

Langkah 3

Iterasi Pertama
Basis X1 X2 S1 S2 A2 Solusi Rasio
Z 0 (5M-4)/2 (M-2)/4 -M 0 6M+6
X1 1 0,5 -0,25 0 0 3 6
A2 0 2,5 0,25 -1 1 6 2,4

Langkah 4

Iterasi Kedua
Basis X1 X2 S1 S2 Solusi
Z 0 0 -0,3 0,8 10,8
X1 1 0 -0,3 0,2 1,8
X2 0 1 0,1 -0,4 2,4

Di iterasi yang kedua ini sudah tidak ada lagi nilai positif di baris Z, artinya Solusi optimal sudah
tercapai.
Langkah 5

Interpretasi Hasil

Biaya minimal untuk membuat pakan Adalah $10,8 dengan membutuhkan bahan A sebanyak 1,8
kg dan bahan B sebanyak 2,4 kg.

SOAL 3

Sebuah pabrik membutuhkan dua jenis komponen X dan Y dari dua supplier A dan B. Biaya per
unit dari Supplier A adalah $10, sedangkan Supplier B adalah $12. Kebutuhan minimum sebagai
berikut:

Supplier A Supplier B Kebutuhan Minimum

Komponen X 2 Unit 3 Unit 60 Unit
Komponen Y 4 Unit 2 Unit 80 Unit

Berapa banyak unit yang harus dibeli dari setiap supplier untuk memenuhi kebutuhan dengan biaya
minimal?

Fungsi Tujuan
𝑍 = 10𝑥1 + 12𝑥2

Fungsi Batasan
1. 2𝑥1 + 3𝑥2 ≥ 60
2. 4𝑥1 + 2𝑥1 ≥ 80
3. 𝑥1 , 𝑥2 ≥ 0

Langkah 1 Standarisasi

Fungsi Batasan (Menambahkan Variabel Surplus 𝑠1 , 𝑠2 dan Variabel Buatan 𝐴1, 𝐴2 )

• 2𝑥1 + 3𝑥2 − 𝑠1 + 𝐴1 = 60
• 4𝑥1 + 2𝑥1 − 𝑠2 + 𝐴2 = 80

Fungsi Tujuan (penalti Big M)

𝑍 = 10𝑥1 + 12𝑥2 + 𝑀𝐴1 + 𝑀𝐴2

Siapkan Fungsi Tujuan untuk Tabel Awal Simpleks: Hilangkan Variabel Buatan (A)

Dari batasan diketahui:

• 𝐴1 = 60 − 2𝑥1 − 3𝑥2 + 𝑠1
• 𝐴2 = 80 − 4𝑥1 − 2𝑥2 + 𝑠2

Substitusikan 𝐴1 dan 𝐴2 ke fungsi Z

• 𝑍 = 10𝑥1 + 12𝑥2 + 𝑀𝐴1 + 𝑀𝐴2
• 𝑍 = 10𝑥1 + 12𝑥2 + 𝑀(60 − 2𝑥1 − 3𝑥2 + 𝑠1 ) + 𝑀(80 − 4𝑥1 − 2𝑥2 + 𝑠2 )
• 𝑍 = (10 − 6𝑀)𝑥1 + (12 − 5𝑀)𝑥2 + 𝑀𝑠1 + 𝑀𝑠2 + 140𝑀

Untuk tabel awal simpleks fungsi tujuan menjadi:

𝑍 + (6𝑀 − 10)𝑥1 + (5𝑀 − 12)𝑥2 − 𝑀𝑠1 − 𝑀𝑠2 = 140𝑀

Langkah 2: Tabel Awal Simpleks

Basis x1 x2 s1 s2 A1 A2 Solusi
Z 6M-10 5M-12 (M) (M) 0 0 140M
A1 2 3 -1 0 1 0 60
A2 4 2 0 -1 0 1 80

Langkah 2: Iterasi Pertama

1) Pilih Kolom Pivot : Pada baris Z (tabel awal simpleks) pilih variabel 𝑥 yang memiliki nilai
positif terbesar
2) Pilih Baris Pivot:
𝑁𝑖𝑙𝑎𝑖 𝐾𝑜𝑙𝑜𝑚 𝑆𝑜𝑙𝑢𝑠𝑖
Pilih Baris (selain baris Z) yang memiliki nilai rasio terkecil 𝑅𝑎𝑠𝑖𝑜 = 𝑁𝑖𝑎𝑙𝑖 𝐾𝑜𝑙𝑜𝑚 𝑃𝑖𝑣𝑜𝑡
3) Nilai Pivot: Nilai yang terdapat pada persilangan Kolom Pivot dan Baris Pivot

Basis x1 x2 s1 s2 A1 A2 Solusi Rasio

Z 6M-10 5M-12 -M -M 0 0 140M
A1 2 3 -1 0 1 0 60 30
A2 4 2 0 -1 0 1 80 20

Tabel iterasi pertama:

Basis x1 x2 s1 s2 A1 Solusi
Z 0 2M-7 -M (M-5)/2 0 20M+200
A1 0 2 -1 ½ 1 20
x1 1 1/2 0 -1/4 0 20
• Baris A2 keluar digantikan oleh x1
• Nilai baris x1:

• Karena Baris A2 keluar, maka kolom A2 dihilangkan

• Nilai Baris Z:

• Nilai Baris A1:

Langkah 2: Iterasi kedua

Basis x1 x2 s1 s2 A1 Solusi Rasio

Z 0 2M-7 -M (M-5)/2 0 20M+200
A1 0 2 -1 1/2 1 20 10
x1 1 1/2 0 -1/4 0 20 40

Basis x1 x1 s1 s2 Solusi
Z 0 0 -3M/2 -3/4 270
x2 0 1 -1/2 1/4 10
x1 1 0 1/4 -3/8 15

Langkah 3: Interpretasi Hasil

Biaya minimal yang dikeluarkan adalah $270 dengan Jumlah 15 unit dipasok dari Supplier A dan
10 unit dari Supplier B.