Program Linear

“Metode Simpleks”
Penyelesaian Metode Simpleks

Kasus Kasus Minimum

Maksimum
 METODE
SIMPLEKS
DEFINISI

Salah satu pendekatan dalam memecahkan masalah

dalam pemrograman linear yang memiliki 2 atau
lebih variable keputusan dimana dalam
menentukan kombinasi optimal dilakukan melalui
iterasi secara berulang terhadap table simpleks
sampai ditemukan nilai optimum
ALGORITMA SIMPLEKS PENGANTAR
UNTUK Mulai METODE SIMPLEK
MEMAKSIMUMKAN
 Ubah bentuk PL ke bentuk standar dengan menambahkan
variable: slack, surplus, dan artifisial
 Tambahkan koefisien dari variable-variable ini dalam fungsi objektif

Susun table simpleks awal

Perbaharui elemen dalam table

Hitung nilai zj dan cj - zj simpleks dengan menjadikan
elemen pivot adalah 1 dan lakukan
operasi baris dasar

tidak
Apakah masih ada
Selesai Solusi sudah optimal
cj – zj yang positif? Tentukan elemen pivot

ya
 Pilihlah baris kunci dengan rasio
Pilihlah kolom kunci dengan paling kecil (syarat aij > 0)
nilai cj - zj  Jika semua aij bernilai nol maka
yang paling besar solusi adalah tak terbatas dan
hentikan algoritma
ALGORITMA SIMPLEKS PENGANTAR
UNTUK MEMINIMUMKAN Mulai METODE SIMPLEK

 Ubah bentuk PL ke bentuk standar dengan menambahkan

variable: slack, surplus, dan artifisial
 Tambahkan koefisien dari variable-variable ini dalam fungsi objektif

Susun table simpleks awal

Perbaharui elemen dalam table

Hitung nilai zj dan cj - zj simpleks dengan menjadikan
elemen pivot adalah 1 dan lakukan
operasi baris dasar

tidak
Apakah masih ada
Selesai Solusi sudah optimal
cj – zj yang negatif? Tentukan elemen pivot

ya
 Pilihlah baris kunci dengan rasio
Pilihlah kolom kunci dengan paling kecil (syarat aij > 0)
nilai cj - zj  Jika semua aij bernilai nol maka
yang paling besar solusi adalah tak terbatas dan
hentikan algoritma
 PENGANTAR
ALGORITMA SIMPLEKS UNTUK METODE SIMPLEK
MEMAKSIMUMKAN
Langkah 1: merumuskan model matematika
Rumuskan permasalahan ke dalam model matematika program linear

Jika kasusnya meminimumkan maka bentuk ke dalam: min Z = max (-Z)

Pastikan setiap pembatas bi dalam keadaan nonnegative, jika kedapatan negative maka kalikan
kedua ruas dengan (-1) sehingga harus mengubah arah pertidaksamaannya.

Pastikan bentuk model program linier sudah dalam bentuk standar. Aturan konversi dapat dilihat
pada slide sebelumnya

Konversi PL bentuk umum menjadi bentuk standar

ALGORITMA SIMPLEKS UNTUK MEMAKSIMUMKAN PENGANTAR
METODE SIMPLEK
Langkah 2: menentukan solusi awal
cj c1 c2 ………. cn 0 0 …….. 0
Buatlah table awal berikut:
Koefisien Variabel Nilai variable variabel
variable dasar dasar dasar

(cB) B b x1 x2 …….. xn s1 s2 …….. sm

cB1 s1 xB1 = b1 a11 a12 …….. a1n 1 0 …….. 0

cB2 s2 xB2 = b2 a21 a22 …….. a2n 0 1 …….. 0

. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

cBm sm xBm = bm am1 am2 amn 0 0 …….. 1

Z= [Link] zj = [Link] 0 0 ….. 0 0 0 ….. 0

cj - z j c1 - z 1 c2 – z 2 cn - z n 0 0 ….. 0
 PENGANTAR
METODE SIMPLEK

Setelah terbentuk table awal, tentukan matriks basis (B) yang merupakan matriks identitas (I) karena solusi dasar feasible
dinyatakan dalam B = I

Variabel yang berkorespondensi dengan kolom matriks identitas disebut variable dasar, dan sisanya disebut variabel non-
dasar. matriks identitas merupakan koefisien variable slack atau surplus yang ditambahkan.

Baris pertama pada tabel awal simpleks menunjukkan koefisien cj variabel dalam fungsi tujuan. Nilai ini mewakili biaya (atau laba) per unit
yang terkait dengan variabel dalam fungsi tujuan dan ini digunakan untuk menentukan variabel yang akan dimasukkan ke dalam matriks
basis B.

Kolom cB mencantumkan koefisien variabel dasar saat ini dalam fungsi tujuan. Nilai ini digunakan
untuk menghitung nilai Z ketika satu unit variabel apa pun dimasukkan ke dalam solusi.

Kolom xB mewakili nilai-nilai variabel dasar dalam solusi dasar saat ini.

Angka, aij di kolom di bawah setiap variabel juga disebut substitusi (atau pertukaran koefisien) karena ini
mewakili tingkat di mana sumber daya i (i = 1, 2, . . , m) dikonsumsi oleh setiap unit dari suatu
kegiatan j ( j = 1, 2, . . , n).
 PENGANTAR
METODE SIMPLEK
Nilai zj mewakili jumlah penurunan nilai fungsi tujuan Z (atau meningkat ) jika satu
unit variabel yang diberikan ditambahkan ke solusi baru.
Nilai dalam cj – zj baris mewakili jumlah bersih kenaikan (atau penurunan) dalam
fungsi tujuan yang akan terjadi ketika satu unit variabel yang diwakili oleh kolom
dimasukkan ke dalam solusi.
cj – zj (laba bersih) = cj (laba/biaya unit masuk) – zj (total laba/biaya keluar)

dimana zj = Koefisien variabel dasar kolom × Koefisien pertukaran kolom j

Algoritma menggerakkan solusi dasar yang satu ke yang lain dengan cara:
1. Meningkatkan nilai variable nondasar
2. Menjaga nilai variable nondasar lainnya supaya nol
3. Menyesuaikan nilai variable dasar supaya memenuhi nilai kendala
 PENGANTAR
METODE SIMPLEK

Langkah 3: uji keoptimalan

Hitung nilai cj – zj untuk semua variabel non-basis. Untuk mendapatkan nilai dari z j kalikan setiap elemen di bawah kolom 'Variabel' (kolom, a j dari
matriks koefisien) dengan elemen yang sesuai dalam c B-kolom. Periksa nilai cj – zj. Tiga kasus berikut mungkin muncul:

1. Jika semua cj – zj ≤ 0 maka solusi dasar feasible adalah optimal

2. Jika setidaknya satu kolom dari matriks koefisien (yaitu a k ) yang ck – zk > 0 dan semua
elemen lainnya negatif (yaitu a ik < 0), maka terdapat solusi tak terbatas untuk masalah yang
diberikan.
3. Jika setidaknya satu c j – zj > 0, dan masing-masing kolom ini memiliki setidaknya
satu elemen positif (yaitu a ij ) untuk beberapa baris, maka ini menunjukkan bahwa
kemungkinan bisa terjadi peningkatan nilai fungsi tujuan Z
 PENGANTAR
METODE SIMPLEK

Langkah 4: menentukan variable yang masuk sebagai basis

Jika Kasus (iii) dari Langkah 3 berlaku, maka pilih variabel yang memiliki nilai cj – zj terbesar
untuk dimasukkan ke dalam solusi baru. Itu adalah,

𝑐 𝑘 − 𝑧 𝑘 = max ¿ ¿

Kolom yang akan dimasukkan disebut kolom kunci atau pivot.

Jelas, variabel seperti itu menunjukkan terbesar per unit perbaikan dalam solusi saat ini.
 PENGANTAR
METODE SIMPLEK

Langkah 5 : uji kelayakan (variable yang meninggalkan basis)

Setelah mengidentifikasi variabel menjadi variabel dasar, variabel yang akan keluar dari himpunan
variabel dasar yang ada. Untuk ini, setiap angka dalam kolom x B (yaitu nilai bi) dibagi dengan
angka yang sesuai (tetapi positif) di kolom kunci dan baris dipilih yang rasio ini non-negatif dan minimum.
Rasio ini disebut rasio penggantian (pertukaran).

Rasio ini membatasi jumlah unit variabel masuk yang dapat diperoleh dari pertukaran. Perlu dicatat bahwa:

Pembagian dengan elemen negatif atau nol dalam kolom kunci tidak diperbolehkan
Baris terpilih disebut baris kunci atau pivot dan mewakili variabel yang akan meninggalkan solusi..

Elemen yang terletak pada perpotongan baris kunci dan kolom kunci dari tabel simpleks disebut elemen kunci
atau pivot.
 PENGANTAR
METODE SIMPLEK

Langkah 6 : menemukan solusi baru

1. Jika elemen kuncinya adalah 1, maka barisnya tetap sama dalam tabel simpleks baru.

2. Jika elemen kunci selain 1, maka bagi setiap elemen dalam baris kunci (termasuk elemen
di xB-column ) oleh elemen kunci, untuk menemukan nilai baru untuk baris itu.

3. Nilai baru dari elemen di baris yang tersisa dari tabel simpleks baru dapat diperoleh dengan melakukan operasi
baris elementer pada semua baris sehingga semua elemen kecuali elemen kunci di kolom kunci adalah nol.
Dengan kata lain, untuk setiap baris selain baris kunci, dengan menggunakan rumus:

𝒃𝒂𝒓𝒊𝒔 𝒃𝒂𝒓𝒖=𝒃𝒂𝒓𝒊𝒔 𝒍𝒂𝒎𝒂 ± ( 𝒌𝒐𝒆𝒇 𝒃𝒂𝒓𝒊𝒔 𝒍𝒂𝒎𝒂 × 𝒃𝒂𝒓𝒊𝒔 𝒌𝒖𝒏𝒄𝒊 )

 PENGANTAR
METODE SIMPLEK

Langkah 7 : mengulangi langkah secara iteratif

Kembali ke Langkah 3 dan ulangi prosedur sampai semua entri di baris cj – zj

bernilai negatif atau nol.
 PENGANTAR
METODE SIMPLEK

Langkah 1: merumuskan model matematika

max 𝑍=3 𝑥 1 +5 𝑥2 + 4 𝑥 3 +0 𝑠1 +0 𝑠 2+ 0 𝑠 3

2 𝑥1 +3 𝑥 2 +𝑠 1=8
Bentuk standar 2 𝑥2 +5 𝑥 3 + 𝑠2=10 Syarat batas

3 𝑥 1+2 𝑥 2 +4 𝑥 3 +𝑠 3=15 𝑥1 , 𝑥2 , 𝑥 3 , 𝑠 1 , 𝑠2 , 𝑠 3 ≥ 0
 PENGANTAR
METODE SIMPLEK

Langkah 3: uji keoptimalan

Untuk variable non-dasar x1, x2 dan x3 maka dapat ditentukan:

𝑧 𝑗=𝑘𝑜𝑒𝑓 .𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 𝑑𝑎𝑠𝑎𝑟 ×𝑘𝑜𝑙𝑜𝑚𝑘𝑒− 𝑗

𝑧 1 =0 ( 2 ) + 0 ( 0 ) + 0 ( 3 ) =0
𝑧 2=0 ( 3 ) +0 ( 2 ) + 0 ( 2 )=0
𝑧 3=0 ( 0 ) +0 (5 ) +0 ( 4 )=0

Nilai dari variable dasar s1, s2 dan s3 diletakkan sebagai nilai solusi (x B) sedangkan sisanya sebagai variable non-dasar
yang sementara mempunyai nilai nol:
𝑍=𝑘𝑜𝑒𝑓 .𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 𝑑𝑎𝑠𝑎𝑟 ×𝑛𝑖𝑙𝑎𝑖𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 𝑑𝑎𝑠𝑎𝑟 𝑥 𝐵
¿ 𝑐 𝐵× 𝑥 𝐵
¿ 0 ( 8 ) +0 (10 ) +0 ( 15 )=0
 PENGANTAR
METODE SIMPLEK

Karena semua cj – zj >0 ( j = 1, 2, 3), solusi saat ini tidak optimal. Variabel x 2 dipilih untuk dimasuki basis karena c 2 – z2 = 5 adalah
bilangan positif terbesar, di mana semua elemennya positif. Ini berarti bahwa untuk setiap unit variabel x 2, fungsi tujuan akan meningkat
nilainya sebesar 5.
Kemudian hitung rasio dengan rasio minimum untuk menentukan baris kunci
Nilai x2- kolom adalah kolom kunci.

cj 3 5 4 0 0 0
Koefisien Variabel Nilai variable variabel Min rasio
variable dasar dasar dasar
(cB) B b x1 x2 x3 s1 s2 s3

0 s1 8 2 3 0 1 0 0 8/3
0 s2 10 0 2 5 0 1 0 5
0 s3 15 3 2 4 0 0 1 15/2

Z= 0 zj = [Link] 0 0 0 0 0 0

cj - z j 3 5 4 0 0 0
 PENGANTAR
METODE SIMPLEK

Langkah 4: menentukan variable yang masuk sebagai basis

Variabel yang akan keluar dari basis ditentukan dengan membagi nilai pada kolom x B dengan elemen
yang sesuai di kolom kunci seperti yang ditunjukkan pada tabel. Karena rasionya, 8/3 adalah minimum
pada baris 1, variabel dasar s 1 dipilih untuk meninggalkan solusi (basis).

Langkah 5 : uji kelayakan (variable yang meninggalkan basis)

Karena elemen kunci yang terlampir dalam lingkaran pada table bukan 1, bagi semua elemen baris kunci
dengan 3 untuk mendapatkan nilai baru dari elemen di baris ini. Nilai-nilai baru dari elemen di baris yang tersisa
untuk baru dapat diperoleh dengan melakukan baris dasar berikut: operasi pada semua baris sehingga
semua elemen kecuali elemen kunci 1 pada kolom kunci adalah nol.
 PENGANTAR
METODE SIMPLEK

cj 3 5 4 0 0 0
Koefisien Variabel Nilai variable variabel Min rasio
variable dasar dasar dasar
(cB) B b x1 x2 x3 s1 s2 s3

5 x2 8/3 2/3 1 0 1/3 0 0

0 s2 14/3 -4/3 0 5 -2/3 1 0 -

0 s3 29/3 5/3 0 4 -2/3 0 1 14/15

zj 10/3 5 0 5/3 0 0 29/12

cj - z j -1/3 0 4 -5/3 0 0
 PENGANTAR
CONTOH SOAL METODE SIMPLEK

Nilai Optimal

Pada hasil perhitungan table didapatkan bahwa pada baris paling bawah yaitu semua nilai cj – zj
negatif untuk variable nondasar sehingga iterasi berhenti. Nilai optimal didapatkan yaitu:

𝟕𝟔𝟓
𝒁=
𝟒𝟏
Adapun solusinya adalah:

𝟖𝟗 50 62
𝒙 𝟏= 𝑥 2= 𝑥 3=
𝟒𝟏 41 41
MARI BERLATIH
2. Diberikan masalah berikut:

Maksimumkan fungsi objektif (fungsi tujuan)

Syarat:

Tentukan masing-masing nilai maksimum dengan menggunakan

metode simpleks!
THANKS!
Selamat Mencoba

CREDITS: This presentation template was created

by Slidesgo, including icons by Flaticon, and
infographics & images by Freepik.