Perhatikan Soal-soal Berikut

Oleh Ajar Try Purnomo

21 tayangan
Bagikan artikel

Transkrip Perhatikan Soal-soal Berikut

METODE
SIMPLEKS

PERHATIKAN SOAL-SOAL BERIKUT :

1. Mencari

x,y

tak

negatip

yang

memenuhi :
x + 2y ≤ 6
3x + 4y ≤ 12
x+y≤ 6
dan memaksimumkan f= 5x + 4y.



Manakah kendalanya ? sebutkan
bentuk kendalanya!
Ada berapa perubah ?Sebutkan !

Dapatkah soal ini diselesaikan
dengan metode grafik ?

2. Mencari

x,y,z

tak

negatip

yang

memenuhi :
x + 2y + z ≥ 6
3x + 4y ≥ 12
x + y + 5z ≥ 10
dan meminimumkan f= 5x + 4y + z.



Manakah kendalanya ? sebutkan
bentuk kendalanya!
Ada berapa perubah ?Sebutkan !

Dapatkah soal ini diselesaikan
dengan metode grafik ? jelaskan !

3. Mencari

x,y,z

tak

negatip

yang

memenuhi :
x + 2y + z ≤ 6
3x + 4y + z ≥ 12
x + y + 5z = 10
dan memaksimumkan f= 5x + 4y + z



Manakah kendalanya ? sebutkan
bentuk kendalanya!
Ada berapa perubah ?Sebutkan !

Dapatkah soal ini diselesaikan
dengan metode grafik ? jelaskan !

Kesimpulan :
Pada program linier perubah bisa 2 atau
lebih
Bentuk kendala dapat berupa
pertidaksamaan atau persamaan
Untuk menyelesaikan PL dapat
dilakukan dengan metode grafik
ataupun metode simpleks
Metode grafik dapat digunakan apbila PL
dengan 2 peubah
Metide simplekas dapat digunakan
apabila PL dengan 2 peubah atau lebih

Dari contoh di atas , kita mengetahui bahwa
ada 3 kendala utama yang dapat kita
jumpai, yaitu :
a) Kendala utama berbentuk
pertidaksamaan (≥)
b) Kendala utama berbentuk
pertidaksamaan ( ≤)
c) Kendala utama berbentuk
persamaan.
PENGANTAR
Salah satu teknik penentuan solusi optimal yang
digunakan dalam pemrograman linier adalah metode
simpleks. Penentuan solusi optimal menggunakan metode
simpleks didasarkan pada teknik eleminasi Gauss Jordan.
Penentuan solusi optimal dilakukan dengan memeriksa
titik ekstrim satu per satu dengan cara perhitungan iteratif.

Sehingga penentuan solusi optimal dengan simpleks
dilakukan tahap demi tahap yang disebut dengan iterasi.
Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).
Ada beberapa istilah yang sangat sering digunakan dalam
metode simpleks, diantaranya :
1. Iterasi adalah tahapan perhitungan dimana nilai
dalam perhitungan itu tergantung dari nilai tabel
sebelumnya.
2. Variabel non basis adalah variabel yang nilainya
diatur menjadi nol pada sembarang iterasi. Dalam
terminologi umum, jumlah variabel non basis selalu
sama dengan derajat bebas dalam sistem persamaan.
3. Variabel basis merupakan variabel yang nilainya
bukan nol pada sembarang iterasi. Pada solusi awal,
variabel basis merupakan variabel slack (jika fungsi
kendala merupakan pertidaksamaan ≤ ) atau variabel
buatan

(jika

fungsi

kendala

menggunakan

pertidaksamaan ≥ atau =). Secara umum, jumlah
variabel basis selalu sama dengan jumlah fungsi
pembatas (tanpa fungsi non negatif).
4. Solusi atau nilai kanan merupakan nilai sumber
daya pembatas yang masih tersedia. Pada solusi awal,
nilai kanan atau solusi sama dengan jumlah sumber
daya pembatas awal yang ada, karena aktivitas
belum dilaksanakan.
5. Variabel slack adalah variabel yang ditambahkan ke
model matematik kendala untuk mengkonversikan
pertidaksamaan
Penambahan



menjadi

variabel

ini

persamaan

terjadi

pada

(=).
tahap

inisialisasi. Pada solusi awal, variabel slack akan
berfungsi sebagai variabel basis.
6. Variabel surplus adalah variabel yang dikurangkan
dari

model

mengkonversikan

matematik

kendala

pertidaksamaan



untuk
menjadi

persamaan (=). Penambahan ini terjadi pada tahap

inisialisasi. Pada solusi awal, variabel surplus tidak
dapat berfungsi sebagai variabel basis.
7. Variabel buatan adalah variabel yang ditambahkan
ke model matematik kendala dengan bentuk ≥ atau =
untuk difungsikan sebagai variabel basis awal.
Penambahan

variabel

ini

terjadi

pada

tahap

inisialisasi. Variabel ini harus bernilai 0 pada solusi
optimal, karena kenyataannya variabel ini tidak ada.
Variabel hanya ada di atas kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang
memuat variabel masuk. Koefisien pada kolom ini
akn menjadi pembagi nilai kanan untuk menentukan
baris pivot (baris kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari
antara variabel basis yang memuat variabel keluar.
10.

Elemen pivot (elemen kerja) adalah elemen

yang terletak pada perpotongan kolom dan baris
pivot. Elemen pivot akan menjadi dasar perhitungan
untuk tabel simpleks berikutnya.

11.

Variabel masuk adalah variabel yang terpilih

untuk menjadi variabel basis pada iterasi berikutnya.
Variabel masuk dipilih satu dari antara variabel non
basis pada setiap iterasi. Variabel ini pada iterasi
berikutnya akan bernilai positif.
12.

Variabel keluar adalah variabel yang keluar

dari variabel basis pada iterasi berikutnya dan
digantikan oleh variabel masuk. Variabel keluar
dipilih satu dari antara variabel basis pada setiap
iiterasi. Variabel ini pada iterasi berikutnya akan
bernilai nol.
BENTUK BAKU
Sebelum

melakukan perhitungan iteratif

untuk

menentukan solusi optimal, pertama sekali bentuk umum
pemrograman linier dirubah ke dalam bentuk baku
(bentuk kanonik) terlebih dahulu. Bentuk baku dalam
metode simpleks tidak hanya mengubah persamaan

kendala ke dalam bentuk sama dengan (=), tetapi setiap
fungsi kendala harus diwakili oleh satu variabel basis
awal. Variabel basis awal menunjukkan status sumber
daya pada kondisi sebelum ada aktivitas yang dilakukan.
Dengan kata lain, variabel keputusan semuanya masih
bernilai nol. Dengan demikian, meskipun fungsi kendala
pada bentuk umum pemrograman linier sudah dalam
bentuk persamaan, fungsi kendala tersebut masih harus
tetap berubah.
Ada beberapa hal yang harus diperhatikan dalam
membuat bentuk baku, yaitu :
1. Fungsi kendala dengan pertidaksamaan ≤ dalam
bentuk umum, dirubah menjadi persamaan (=)
dengan menambahkan satu variabel slack./variabel
pengetat.

2. Fungsi kendala dengan pertidaksamaan ≥ dalam
bentuk umum, dirubah menjadi persamaan (=)
dengan mengurangkan satu variabel surplus.
3. Fungsi kendala dengan persamaan dalam benttuk
umum,ditambahkan satu artificial variabel (variabel
buatan).
Contoh:

Mencari

x,y,z

tak

negatip

yang

memenuhi :
x + 2y + z ≤ 6
3x + 4y



12

x + y + 5z ≤ 10
dan memaksimumkan f= 5x + 4y + z.
Pada contoh soal di atas kendala utamanya
adalah :

x + 2y + z ≤ 6
3x + 4y



12

x + y + 5z ≤ 10
agar dapat dimasukkan ke dalam
tabel simpleks kendala utama tersebut,
harus diubah dalam bentuk baku yaitu :
x + 2y + z + s1 =6
3x + 4y
x + y + 5z

+ s2 =12
+ s3=10

s1,s2 dan s3 dinamakan sebagai
variabel slack.
Variabel slack nilainya positip
S>0

Perhatikan untuk membuat suatu
persamaan maka pada ruas kiri harus
ditambah dengan variabel slack agar
didapatkan bentuk persamaan. Pada
awal perhitungan pada tabel simpleks
variabel salck ini merupakan variabel
basis yang nilainya nol(0).
Contoh :
Mencari

x,y,z

tak

negatip

yang

memenuhi :
x + 2y + z ≥ 6
3x + 4y ≥ 12
x + y + 5z ≥ 10
dan meminimumkan f= 5x + 4y + z.

Bagaimana membentuk
bentuk baku ?
x + 2y + z - s1

ke

dalam

=6

3x + 4y

- s2 = 12

x + y + 5z

- s3 = 10

Perhatikan untuk mengubah ke
dalam
bentuk
persamaan
harus
dikurangi dengan variabel surplus
Agar dapat dimasukkan dalam tabel
simpleks maka perlu ditambah variabel
baru, yaitu variabel buatan.
Sehingga diperoleh :
x + 2y + z - s1 +v1

=6

3x + 4y

- s2 + v2 = 12

x + y + 5z

- s3 + v3 = 10

Pada mulanya

x + 2y + z - s1 = 6
sudah berbentuk
persamaan, tetapi kita menambahkan
variabel buatan v1 dalam persamaan
tersebut, sehingga agar nilai persamaan
tersebut tetap, maka v1=0.

CATATAN : variabel buatan v=0

Pada awal tabel simpleks, variabel
buatan merupakan variabel basis.
Bagaimana kalau kendala
berbentuk persamaan ?

utama

Contoh : 2x+ 3y – 4z = 10
Untuk merubah kedalam bentuk baku,
cukup ditambah dengan variabel buatan
saja, sehingga contoh tadi menjadi :

2x+ 3y – 4z + v1= 10
Pada awal tabel simpleks, variabel
buatan merupakan variabel basis.
Latihan soal:
Ubahlah dalam bentuk baku(bentuk kanonik) untuk
kendala utama pada soal berikut :
1. Mencari x1,x2,x3 tak negative yang memenuhi
kendala
2x1 + 3x2 - x3 ≤ 10
x1 + 5x2 - 4x3 ≤ 17
-x1 + 3x2
≤ 12
Dan memaksimalkan f= 20x1 + 30x2 + 5 x3
1. Mencari x1,x2,x3 tak negative yang memenuhi
kendala
2x1 + 3x2 - x3 ≤ 10
x1 + 5x2 - 4x3 ≤ 17
-x1 + 3x2
≤ 12
Dan memaksimalkan f= 20x1 + 30x2 + 5 x3
1. Mencari x1,x2,x3 tak negative yang memenuhi
kendala
2x1 + 3x2 - x3 ≤ 10
x1 + 5x2 - 4x3 ≤ 17
-x1 + 3x2
≤ 12
Dan memaksimalkan f= 20x1 + 30x2 + 5 x3
2. Mencari x1,x2,x3 tak negative yang memenuhi
kendala
2x1 + 2x2 - x3 = 15
x1 + 5x2 - 7x3 ≤ 27
-3x1 + 3x2
≤2
Dan meminimalkan f= 100x1 + 30x2 + 50 x3

Jawab :

3. Mencari x1,x2,x3 tak negative yang memenuhi
kendala
2x1 + 6x2 - x3 ≤ 10
8x1 + 5x2 - 4x3 ≥17
-x1 + 2x2
= 12
Dan memaksimalkan f= 60x1 + 30x2 + 10 x3

Penyelesaian optimum suatu PL terdapat di antara penyelesaian layak yang tak terhingga
banyaknya. Terkait dengan mencari PO dari PL maka terdapat teorema yang berbunyi :
“Jika suatu soal PL mempunyai PO maka paling sedikit satu diantara PO tersebut pasti
penyelesaian linier basis (PLB)”.
Oleh karena itu untuk mencari PO cukup mencari pada daerah PLB nya saja yang jumlahnya
berhingga.
Langkah –langkah penyelesaian dengan metode simpleks
a.
b.
c.
d.
e.

Pilih salah satu plb
Uji apakah plb tersebut berupa penyelesaian optimum (PO)
Jika ya sudah selesai dan sudah didapatkan hasilnya.
Jika belum maka pilih plb baru yang lebih baik dari sebelumnya
Kembali ke langkah (b)

Gambaran umum :
Soal awal

Ubah ke bentuk
kanonik
Soal awal

Cek bi positip dan
tersusut gaus Jordan

Tulis dalam tabel simpleks

plb

selesai

PO

TIDAK

YA

Suku tetap (bi)
Suku tetap nilainya tidak boleh negatip,
mengapa nilai (bi) tidak boleh negatip ?
Contoh :
Misalkan kendala utama 2x + y ≤ 10
x – 3y ≤ -20
pada kendala utama di atas suku
tetap (b1=10 dan b2=-20)
diubah menjadi bentuk kanonik :
2x + y + s1 = 10
x - 3y + s2 = -20
dengan s1>0 dan s2>0
apabila x=0 dan y=0 maka berdasar ke dua
persamaan di atas diperoleh s1=10 dan s2=-20
maka disini terjadi suatu kontradiksi, yang
mengatakan bahwa s2 >0 (s2 harus positip)

Oleh karena itu nilai bi tidak boleh negatip
Nilai suku tetap (bi) tidak boleh negati
Atau dengan kata lain :
bi positip atau bi =0

FUNGSI TUJUAN
Contoh :
Mencari

x,y,z

tak

negatip

yang

memenuhi :
x + 2y + z ≤ 6
3x + 4y



12

x + y + 5z ≤ 10
dan memaksimumkan f= 5x + 4y + z.

Pada soal di atas, kita telah
merubah kendala utama menjadi :
x + 2y + z + s1= 6
3x + 4y + s2 = 12
x + y + 5z + s3 = 10
sehingga
fungsi
memaksimumkan

tujuan

f= 5x + 4y + z + 0s1 +0s2 + 0s3
mengapa koefisien s1 , s2 dan s3 nol
(0), karena fungsi tujuan awalnya
adalah f= 5x + 4y + z, dan karena s
positip maka koefisien s harus nol(0).

Secara lengkap setelah
perubahan menjadi :

dilakukan

Mencari x,y,z,s1 ,s2,s3 tak negatip yang
memenuhi :
x + 2y + z + s1= 6
3x + 4y + s2 = 12
x + y + 5z + s3 = 10
dan memaksimumkan
f= 5x + 4y + z + 0s1 +0s2 + 0s3

belum
selesai

Tabel untuk mengerjakan dengan metode simpleks adalah sebagai berikut :
ci
c1
c2
c3

cj
xi/xj
s1
s2
s3

cm

xm
zj
Zj-cj
Keterangan :

c1
c2 c3 …………..cn
x1 x2 x3 …………..xn
a11 a12 a13
a1n
a21 a22 a23
a2n

am1 am2 am3
Z1 z2
Z1-c1

amn
zn
zn-cn

Bi
b1
b2

Ri
R1
R2

bm

Rm

xj : perubah-perubah lengkap
aij : koefisien teknis
bi : suku tetap
cj : koefisien ongkos
xi : perubah yang menjadi basis dalam tabel yang ditinjau
zj : jumlah dari hasil kali ci dengan kolom aij
z : jumlah dari hasil kali ci denganm bi
zj-cj : selisih zj dengan cj
Apabila tabel belum optimum dan xk terpilih menjadi basis baku maka disusun Ri yang
diperoleh melalui Ri = bi/aik , dengan syarat aik >0 (aik positip)
Latihan Soal
Mencari x,y tak negatip yang memenuhi :
2x + 5y ≤ 600
4x + 3y ≤ 530

2x + y ≤ 240
Dan memaksimalkan f= 32x + 20y
Jawab :

Judul: Perhatikan Soal-soal Berikut

Oleh: Ajar Try Purnomo


Ikuti kami