PROGRAM LINEAR DENGAN

METODE SIMPLEX

Bahan Kuliah
Fakultas : Ilmu Komputer
Program Studi : Teknik Informatika
Tahun Akademik : Ganjil 2012/2013
Kode - Nama Mata Kuliah : CCR314 Riset Operasional
Pertemuan : 4 (On-Line)
Dosen : Taufiqur Rachman, ST., MT

UNIVERSITAS ESA UNGGUL

Jl. Arjuna Utara No.9, Tol Tomang, Kebon Jeruk
Jakarta Barat 11510, Telepon: 021 5674223

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

 PROGRAM LINEAR DENGAN METODE SIMPLEX

PENDAHULUAN
Metode simpleks ini adalah suatu prosedur aljabar yang bukan
secara
grafik untuk mencari nilai optimal dari fungsi tujuan dalam masalah-
masalah
optimisasi yang terkendala. Metode simpleks merupakan sebuah
metode
lanjutan dari metode grafik. Metode grafik tidak dapat menyelesaikan perso
alan
manajemen yang memiliki variable keputusan cukup besar, sehingga
untuk
menyelesaikannya dibutuhkan sebuah metode yang lebih kompleks yaitu den
gan
menggunakan program komputer atau menggunakan metode simpleks.
Dalam
kenyataannya penggunaan komputer lebih efisien, akan tetapi metode
dasar
yang digunakan dalam pengoperasian komputer tetap metode simpleks.
Penyelesaian pemrograman linear dengan menggunakan
dengan
pendekatan grafik, hanya dapat dilakukan jika perusahaan hanya mem
iliki 2
variabel saja (atau biasanya didalam contoh soal berarti hanya menghasil
kan 2
macam produk saja). Oleh karena itu digunakan pendekatan yang kita
sebut
metode simpleks untuk memecahkan masalah yang memiliki variabel lebih
dari
dua. Namun demikian metode simpleks juga dapat diterapkan
unuk
memecahkan masalah yang menggunakan dua variabel.
Penyelesaian secara manual program linear dengan metode si
mpleks
tetap menghendaki kesungguhan kita dalam pengembangan keahlian form
ulasi
pemrograman linear. Dengan mempelajari mekanisme dari metode sim
pleks,
informasi yang diperoleh tidak hanya solusi optimal saja, melainka
n juga
interpretasi ekonomi dan informasi untuk mengadakan analisa sensitivitas.
 Metode simpleks merupakan pengembangan metode aljabar yang
hanya
menguji sebagian dari jumlah solusi basis dalam bentuk tabel. Tabel si
mpleks
hanya menggambarkan masalah linear program dalam bentuk koefisien
saja,
baik koefisien fungsi tujuan maupun koefisien setiap kendala.

PENGERTIAN
Metode Simpleks adalah metode yang dapat digunakan
untuk
menyelesaikan persoalan manajerial yang telah diformulasikan terlebih d
ahulu
ke dalam persamaan matematika program linear yang mempunyai Va
riabel
Keputusan mulai dari lebih besar atau sama dengan 2 (dua)
sampai
multivariabel.
Sebagai pembanding, Metode Grafik hanya dapat kita gunakan a
pabila
jumlah variable keputusan maksimal 2 (dua) buah. Sehingga dapat ju
ga kita
katakan bahwa apabila suatu persoalan Linear Programming dap
at kita
selesaikan dengan Metode Simpleks. Sebaliknya suatu persoalan yang
hanya
bisa diselesaikan dengan Metode Simpleks tidak dapat kita selesaikan d
engan
Metode Grafik.
Dalam metode ini, model kita ubah kedalam bentuk suat
u tabel,
kemudian dilakukan langkah-langkah matematis kedalam tabel t
ersebut.

2 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Langkah-langkah matematis ini pada dasarnya merupakan replikasi

proses
pemindahan dari suatu titik ekstrim ke titik ekstrim lainnya pada batas d
aerah
solusi. Akan tetapi tidak seperti metode grafik, dimana kita dapat
dengan
mudah mencari titik terbaik diantara semua titik solusi, metode s
impleks
bergerak dari satu solusi ke solusi yang lebih baik sampai solusi optimal did
apat.
Untuk mencari nilai optimum dengan menggunakan metode simple
ks ini
dilakukan proses pengulangan (iterasi) dimulai dari penyelesaian dasar
awal
yang layak (feasible) hingga penyelesaian dasar akhir yang layak di mana
nilai
dari fungsi tujuan telah optimum. Dalam hal ini proses pengulangan (
iterasi)
tidak dapat dilakukan lagi.

PERSYARATAN METODE SIMPLEKS

Terdapat tiga persyaratan untuk memecahkan masalah pemrog
raman
linier dengan menggunakan metode simpleks, yaitu:
1. Semua kendala pertidaksamaan harus dinyatakan sebagai persamaan.
2. Sisi kanan (the right side) dari sebuah kendala tidak boleh ada yang neg
atif.
3. Nilai kanan (NK/RHS) fungsi tujuan harus nol (0).
4. Semua variabel dibatasi pada nilai-nilai non-negatif.
Ketiga persyaratan ini akan dijelaskan secara terperinci
pada
pembahasan berikut ini.
Dengan memerhatikan Persyaratan 1, kebanyakan
masalah
pemrograman linier mengandung kendala-kendala yang
berbentuk
pertidaksamaan linier. Sebelum kita pecahkan dengan metode si
mpleks,
pertidaksamaan linier ini harus dinyatakan kembali sebagai persamaan
linier.
Perubahan (transformasi) dari pertidaksamaan linier ke persamaan
linier
bervariasi, tergantung pada sifat pertidaksamaan linier tersebut.
Jadi,
persyaratan 1 ini akan terdapat 3 tanda yang mungkin pada kendala, yaitu:
(a) Persyaratan 1 untuk tanda lebih kecil dari atau sama dengan ()
 Untuk setiap kendala yang mempunyai tanda lebih kecil daripada atau s
ama
dengan () harus ditambahkan dengan variabel slack non-negatif di
sisi kiri
kendala. Variabel ini berfungsi untuk menyeimbangkan kedua
sisi
persamaan.
Contoh:
Misalkan, tiga persamaan berikut, di mana kendala-kendalanya adalah:
2X1 + 3X2 24 dimana:
2X1 + X2 76 X1 = jumlah komputer yang dihasilkan
X1 + 4X2 27 X1 = jumlah radio yang dihasilkan

Asumsi bahwa ketiga kendala menunjukkan keterbatasan jam tenaga

kerja
yang tersedia di tiga departemen, koefisien pada variabel-variabel te
rsebut
menunjukkan jumlah jam kerja yang dibutuhkan untuk memproduksi s
etiap

3 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

unit produk, dan sisi kanan dari kendala sama dengan jumlah jam
tenaga
kerja yang tersedia disetiap departemen.
Perubahan dari kendala-kendala ini adalah dengan menambahkan va
riabel
slack pada sisi kiri di setiap kendala. Atau, ketiga kendala tersebut
ditulis
kembali sebagai berikut:
2X1 + 3X2 + S1 = 24
2X1 + X2 + S2 = 76
X1 + 4X2 + S3 = 27

Variabel slack SL1, SL2, dan SL3 dalam masalah ini menunjukkan jumla
h jam
tenaga kerja (sumber daya) vang tidak digunakan di setiap departemen
I, II,
dan III secara berturut-turut. Misalnya, jika X1 = 4 dan X2 = 2, in
i berarti
 perusahaan hanya memproduksikan 4 unit komputer dan 2 unit
radio.
Apabila nilai-nilai ini disubstitusikan ke dalam tiga kendala, kita
peroleh:
2(4) + 3(2) + S1 = 24 (Dept. I)
2(4) + 1(2) + S2 = 76 (Dept. II)
1(4) + 4(2) + S3 = 27 (Dept. III)

Atau:
14 + S1 = 24 (Dept. I)
10 + S2 = 76 (Dept. II)
12 + S3 = 27 (Dept. III)

Atau:
S1 = 10 (Dept I) ; S2 = 6 (Dept II) ; S3 = 15 (Dept III)
Perhitungan di atas, mengartikan bahwa jika kita hanya mempr
oduksi
X1= 4 dan X2= 2, maka jumlah jam tenaga kerja di departemen
I hanya
menggunakan 14 jam tenaga kerja, di departemen II hanya menggunak
an 10
jam tenaga kerja, dan di departemen III hanya menggunakan 12 jam t
enaga
kerja. Variabel slack S1= 10 mengartikan bahwa di departemen I terdap
at 10
jam tenaga kerja yang tidak digunakan; S2= 6 mengartikan b
ahwa di
departemen II terdapat 6 jam tenaga kerja yang tidak digunakan; dan S
3= 15
mengartikan bahwa di departemen III terdapat 15 jam tenaga kerj
a yang
tidak digunakan.
Perhatikan bahwa variabel slack menjadi variabel tambahan dalam mas
alah
ini dan diperlakukan seperti variabel-variabel lainnya. Dan ini sesuai
dengan
persyaratan ke-3, yaitu semua variabel tidak bisa bernilai negatif.

(b)Persyaratan 1 untuk tanda lebih besar dari atau sama dengan ()

Untuk setiap kendala yang mempunyai tanda lebih besar dari atau
sama
dengan () harus dikurangkan dengan variabel surplus non-negatif
di sisi
 kiri kendala. Variabel ini bertindak sama dengan variabel slac
k yaitu

4 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

menjaga kedua sisi persamaan seimbang. Selain mengurangkan v

ariabel
surplus, harus ditambahkan lagi dengan variabel buatan
(artificial
variable) di sisi kiri kendala.
Variabel buatan ini tidak mempunyai arti yang nyata (real) dalam m
asalah
ini, variabel ini hanya berfungsi memberikan kemudahan untuk m
emulai
penyelesaian awal dari metode simpleks.
Contoh:
Misalkan, pada kendala bagian penggilingan bahwa produk A memer
lukan
waktu 30 menit dan produk B memerlukan waktu 15 menit, dan waktu
yang
tersedia paling sedikit 900 menit. Ini berarti dapat ditulis kembali menja
di:
30X1 + 15X2 900

Sebelum kita memecahkan dengan metode simpleks, pertidaksama

an ini
harus diubah ke dalam bentuk persamaan seperti:
30X1 + 15X2 S1 + S2 = 900

Jika X1= 25 dan X2= 30, variabel surplus S1 harus sama dengan 3
00 agar
seimbang kedua sisi persamaan, dengan asumsi S2= 0. Interpreta
si dari
variabel surplus S1 adalah bahwa kombinasi produksi dari 25 unit pro
duk A
dan 30 unit produk B melebihi kebutuhan minimum dengan 300 menit.

(c) Persyaratan 1 untuk tanda sama dengan (=)

Untuk setiap kendala yang mempunyai tanda sama dengan (=),
harus
 ditambahkan dengan variabel buatan (artificial variable) di s
isi kiri
kendala.
Contoh:
Ubahlah kendala-kendala berikut ini ke dalam bentuk stand
ar yang
diperlukan oleh metode simpleks.
2X1 + 3X2 150
3X1 + 4X2 240
X1 + 2X2 = 100

Penyelesaian:
Kendala-kendala ini diubah meniadi:
2X1 + 3X2 + S1 =
150
2X1 + X2 S2 + S3 =
240
X1 + 4X2 + S4 =

V.D Z X1 X2 X3 Xn S1 S2 Sn NK
Z 1 -C1 -C2 -C3 -Cn 0 0 0
S1 0 a11 a12 a13 a1n 1 0 0 b1
S2 0 a21 a22 a23 a2n 0 1 0 b2

Sm 0 am1 am2 am3 amn 0 0 1 bn
100
X1 ; X2 ; S1 ; S2 ; S3 ; S4 0

5 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Perhatikan bahwa setiap variabel tambahan berupa: variabel

slack,
 surplus, dan buatan (artificial) ditetapkan dengan subscript (ditulis ag
ak
ke bawah) yang berhubungan dengan jumlah kendala.

Persyaratan 2 dari metode simpleks menyatakan bahwa sisi kanan

dari
suatu kendala persamaan tidak boleh bernilai negatif. Jika sebuah
kendala
bernilai negatif di sisi kanan, kendala dapat dikalikan dengan (1
) untuk
membuat sisi kanan positif.
Contoh:
Jika kendala-kendala adalah:
X1 + 5X2 150 dan 2X1 + 3X2 175

maka bila dikalikan dengan (1) akan menghasilkan:

X1 5X2 150 dan 2X1 3X2 175

Perhatikan bahwa tanda pertidaksamaan pada setiap kendala ber

ubah.
Hal ini dikarenakan bahwa tanda pertidaksamaan telah dikalikan denga
n (1).
Jadi, jika tanda pertidaksamaan akan berubah dari tanda menjadi
atau
sebaliknya menjadi .

Persyaratan 3 dari metode simpleks menyatakan bahwa nilai

kanan
(NK/RHS) fungsi tujuan harus nol (0).
Contoh:
Fungsi Tujuan: Maksimumkan Z = 3X1 + 2X2 ; di ubah menjadi Z 3X1 2
X2 = 0

Persyaratan 4 dari metode simpleks menyatakan bahwa semua vari

abel
dibatasi pada nilai-nilai non-negatif. Untuk variabel-variabel yang b
ernilai
negatif terdapat metode-metode khusus dalam penyelesaiannya. Akan
tetapi
dalam pembahasan buku ini kita tidak akan menguji metode ini. Hanya var
iabel
slack, surplus, dan buatan yang dibatasi oleh nilai non-negatif ya
ng akan
 dibahas dalam buku ini.

6 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Keterangan:
Kolom berwarna kuning merupakan kolom basic, yang berisi v
ariabel
basis/variabel dasar yang diambil dari variabel slack/surplus/artificial
pada
saat iterasi pertama. Variabel-variabel ini secara bertahap akan diganti
oleh
variabel bukan basis pada iterasi berikutnya.
Kolom berwarna biru merupakan kolom main body, yaitu bidang yang
berisi
koefisien sumber daya/teknologi & kendala yang ada.

V.D Z X1 X2 S1 S2 S3 NK
Z 1 3 5 0 0 0 0 Kolom berwarna hi
S1 0 2 0 1 0 0 8 jau merupakan kol
S2 0 0 3 0 1 0 15 om identity, yaitu
S3 0 6 5 0 0 1 30 bidang yang berisi
koefisien-
koefisien dari variabel slack/surplus/artificial.

ALGORITMA SIMPLEKS
Untuk mencari nilai optimal dari suatu pemrograman linear
TABEL SIMPLEKS
dengan
menggunakan metode simpleks, terdapat langkah-langkah/algoritma
untuk
penyelesaiannya.
Dengan menggunakan contoh berikut ini, akan dijabarkan
langkah
penyelesaian program linear dengan menggunakan metode simpleks.
Contoh:
 Fungsi tujuan:
Maksimalkan Z = 3X1 + 5X2
Fungsi kendala:
1) 2X1 8
2) 3X2 15
3) 6X1 + 5X2 30
Langkah Penyelesaian:
1) Ubah fungsi tujuan dan fungsi kendala ke dalam bentuk standar/implisit
.
Fungsi tujuan: Z 3X1 5X2 =
0
Fungsi kendala: 1) 2X1 + S1 =
8
2) 3X2 + S2 =
15
3) 6X1 + 5X2 + S3 =
30
 7 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

tujuan) yang bernilai negatif () dengan angka terbesar.

V.D Z X1 X2 S1 S2 S3 NK 3) Tentukan kolo
m kunci (variabe
Z 1 3 5 0 0 0 0 l keputusan) yan
S1 0 2 0 1 0 0 8 g masuk sebagai
variabel
S2 0 0 3 0 1 0 15 basis (entering v
ariable).
S3 0 6 5 0 0 1 30
Kolom kunci a
dalah kolom yang mempunyai nilai pada baris Z (fungsi
Keterangan:

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 3 5 0 0 0 0
S1 0 2 0 1 0 0 8 ~
S2 0 0 3 0 1 0 15 5
S3 0 6 5 0 0 1 30 6

Kolom berwarna kuning (kolom X2) dipilih sebagai kolom kunci.

4) Tentukan baris kunci, untuk menentukan variabel yang akan kelu

ar dari
baris kunci (leaving variable).
Baris kunci adalah baris dengan nilai indeks positif terkecil,
dengan
perhitungan indeks sebagai berikut.
Nilai kanan (NK)
Indeks =
Nilai setiap baris pada kolom kunci

2) Susun semua nilai ke dalam tabel simplex.

 Indeks pada baris Z tidak perlu dihitung.
Indeks pada baris S1 diperoleh dari 8 dibagi 0 = ~.
Indeks pada baris S2 diperoleh dari 15 dibagi 3 = 5.
Indeks pada baris S3 diperoleh dari 30 dibagi 5 = 6.

Dari
[Link] simpleks
Z X1padaXlangkah
2 S1 4) diperoleh:
S2 S3 NK Indeks
Z 1 3 5 0 0 0 0 Baris ber
S1 0 2 0 1 0 0 8 ~ warna hij
S2 0 0 3 0 1 0 15 5 au (baris
S3 0 6 5 0 0 1 30 6 S2) dipili
h sebagai
V.D
baris kunci.
Angka Z
kunci X1
adalah 3X(angka
2 S1dengan
S2 warna NK
S3 text Indeks
merah).
Z 1 3 5 0 0 0 0
5) Mengubah
S1 0 nilai-nilai
2 0 pada1 baris0 kunci,
0 dengan
8 cara~ membaginya
dengan
X2 0 0 1 0 1/3 0 5 5
angka kunci.
S3 0 6 5 0 0 1 30 6

8 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Angka kunci merupakan nilai yang posisinya berada pada perpo

tongan
antara kolom kunci dengan baris kunci.
Nilai pada baris kunci lama
Nilai baris baru kunci =
Keterangan: Angka kunci

Variabel kolom kunci (variabel X2) akan menggantikan temp

at dari
 variabel baris kunci (variabel S2), perhatikan sel yang berwarna mera
h.
[Link] mencari
X1 nilai
X2 barsi
S1 kunci
S2 maka
S3 nilai-nilai
NK pada baris ku
Indeks
nci (sel
Zyang 1berwarna
3 hijau)
5 akan
0 di bagi
0 dengan
0 0
angka kunci (=3, angka de
ngan
S1 0 2 0 1 0 0 8 ~
text merah)
X2 0 0 1 0 1/3 0 5 5
S3 0 6 5 0 0 1 30 6

Nilai baris baru kunci adalah yang diberi warna biru.

6) Membuat baris baru dengan mengubah nilai-nilai baris (selain baris

Dari penjelasan tersebut, diperoleh nilai baris kunci baru sebagai berikut.
kunci)

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 3 0 0 5/3 0 25
S1 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
S3 0 6 0 0 5/3 1 5
sehingga nilai-nilai kolom kunci = 0, dengan mengikuti perhitungan s
Keterangan:
ebagai
berikut:
Nilai baris baru = Nilai baris lama (KAKK NBBK)
Dimana:
KAKK = Koefisien Angka Kolom Kunci (nilai setiap baris kolom
kunci)
NBBK = Nilai Baris Baru Kunci

Dari tabel simpleks langkah sebelumnya telah diketahui KAAK dan

NBBK,
seperti yang tertera dalam tabel berikut.
Keterangan:

NBBK (nilai baris baru kunci) adalah yang diberi warna biru.
KAKK (koefisien angka kolom kunci) adalah yang diberi warna
kuning.

Dari penjelasan tersebut diperoleh:

Baris baru Z
Baris lama 3 5 0 0 0 0
KAKK NBBK 5 [ 0 1 0 1/3 0 5 ]
Baris baru Z 3 0 0 5/3 0 25

Baris baru S1
Baris lama 2 0 1 0 0 8
KAKK NBBK 0 [ 0 1 0 1/3 0 5 ]
Baris baru S1 2 0 1 0 0 8

Baris baru S3
Baris lama 6 5 0 0 1 30
KAKK NBBK 5 [ 0 1 0 1/3 0 5 ]
Baris baru S3 6 0 0 5/3 1 5

Masukkan nilai baris baru Z, S1, dan S3 ke dalam tabel simpleks, s

ehingga
 Z (baris fungsi tujuan).

10 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z
7) Ulangi 3 diatas
1langkah 0 (langkah
0 5/33 0
6 atau25 disebut iterasi), samp
Langkah
ai tidak 3 dan 4
S1 0 2 0 1 0 0 8 4
terdapat nilai negatif pada baris Z (baris fungsi tujuan).
X2
Catatan:0 0 1 0 1/3 0 5
S3
Iterasi 0
berhenti6jika tabel
0 0
sudah 5/3
optimal, 1jika: 5 5/6

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 0 0 0 5/6 1/2 27 1 /2
Semua nil
S1 0 0 0 1 5/9 1/3 6
Keterangan: ai pada b
X2 0 0 1 0 1/3 0 5
aris Z ber
X1 0 1 0 0 5/18 1/6 5/6
nilai posit
if atau nol (untuk maksimasi).
Bernilai negatif atau nol (untuk minimasi).

Hasil iterasi 2:

menjadi seperti berikut:

Kolom berwarna kuning (kolom X1) dipilih sebagai kolom kunci.

Baris berwarna hijau (baris S2) dipilih sebagai baris kunci.

Keterangan: Solusi belum optimal karena masih ada nilai negatif pada baris
 Karena nilai pada baris Z (baris fungsi tujuan) sudah tidak
ada yang
bernilai negatif, maka solusi optimal sudah diperoleh.
Nilai solusi optimal dapat dilihat pada kolom NK (yang berwarna m
erah).
Nilai solusi optimal yaitu:
Zmaks = 271/2 ; X1 = 5/6 ; X2 = 5

KENDALA DENGAN TANDA SAMA DENGAN (=)

Fungsi kendala dengan tanda sama dengan (=), ditambahkan v
ariabel
buatan (artificial variable/M) pada fungsi tujuan.

V.D Z X1 X2 S1 S2 S3 NK
Z 1 (6M3) (5M5) 0 0 0 (30M)
Langkah
S1 50 dan 6 2 0 1 0 0 8
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30

11 / 17
Universitas Esa Unggul Jakarta, 2012

Keterangan:
Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Contoh:
Fungsi tujuan:
Maksimalkan Z = 3X1 + 5X2
Fungsi kendala:
1) 2X1 8
2) 3X2 15
3) 6X1 + 5X2 = 30
Langkah Penyelesaian:
1) Ubah fungsi tujuan dan fungsi kendala ke dalam bentuk standar/implisit
.

Fungsi kendala: 1) 2X1 + S1 =

8
2) 3X2 + S2 =
15
3) 6X1 + 5X2 + S3 =
30
Fungsi tujuan: Z 3X1 5X2 + MS3 =
0

Dikarenakan fungsi kendala ada yang beranda sama dengan (=), mak
a nilai
setiap variabel dasar S3 (kendala yang bertanda sama dengan/=
) harus
sebesar 0, sehingga baris Z (baris fungsi tujuan) harus dikurangi den
gan M
dan dikalikan dengan baris batasan yang bersangkutan (kendala 3). Sehi
ngga
nilai baris Z sebagai berikut:
Baris Z baru:

1 3 5 0 0 M 0
M [ 0 6 5 0 0 1 30 ]
1 (6M3) (5M5) 0 0 0 30M

2) Susun semua nilai ke dalam tabel simplex, dan lakukan iteras

i sesuai
V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 (6M3) (5M5) 0 0 0 (30M)
S1 0 2 0 1 0 0 8 4
S2 0 0 3 0 1 0 15
S3 0 6 5 0 0 1 30 5

V.D
Materi Z
#4 CCR314 XOperasional
Riset 1 X2 S1 S2 S3 NK
12 / 17Indeks
Universitas Esa Unggul Jakarta, 2012
Z 1 0 (5M5) (3M+3/2) 0 0 (6M+12)
X1 0 1 0 1/2 0 0 4
S2 0 0 3 0 1 0 15 5
S3 0 0 5 0 0 1 6 6/5

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 0 0 3/2 0 M+1 18
X1 0 1 0 1/2 0 0 4 8
S2 0 0 0 9/5 1 3/5 19/3 5/27
X2 0 0 1 3/5 0 1/5 6/5 2

V.D Z X1 X2 S1 S2 S3 NK Indeks
Z 1 0 0 0 5/6 M+12 27 1 /2
X1 0 1 0 0 5/18 1/6 5/6
S2 0 0 0 1 5/9 1/3 61 / 3
X2 0 0 1 0 1/3 0 5

langkah 2 7 penyelesaian meteode simpleks.

Iterasi
6623 0:
Taufiqur Rachman

Kolom berwarna kuning (kolom X1) dipilih sebagai kolom kunci.

Baris berwarna hijau (baris S1) dipilih sebagai baris kunci.

Keterangan:
Kolom berwarna kuning (kolom X2) dipilih sebagai kolom kunci.
Baris berwarna hijau (baris S3) dipilih sebagai baris kunci.

Iterasi 1:

Kolom berwarna kuning (kolom S1) dipilih sebagai kolom kunci.

Baris berwarna hijau (baris S2) dipilih sebagai baris kunci.

Keterangan:
13 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Iterasi 2:
Keterangan:
Karena nilai pada baris Z (baris fungsi tujuan) sudah tidak ada ya
ng bernilai
negatif, maka solusi optimal sudah diperoleh.
Nilai solusi optimal dapat dilihat pada kolom NK (yang berwarna
merah).
Nilai solusi optimal yaitu:
Keterangan:
Zmaks = 27 ; X1 = 5/6 ; X2 = 5

FUNGSI TUJUAN MEMINIMALKAN

Hasil dari iterasi 2: fungsi tujuan meminimalkan atau permasalahan/soal m
Untuk
inimisasi,
terlebih dahulu fungsi tujuan diubah menjadi maksimisasi d
engan cara
mengganti tanda positif dan negatif pada fungsi tujuan.
Contoh:
Fungsi tujuan:
 Minimalkan Z = 3X1 + 5X2
Fungsi kendala:
1) 2X1 = 8
2) 3X2 15
3) 6X1 + 5X2 30

Langkah Penyelesaian:
1) Ubah fungsi tujuan dan fungsi kendala ke dalam bentuk standar/im
plisit.
Perhatikan pada soal, pada fungsi kendala terdapat kendala den
gan tanda
sama dengan (=) dan kendala dengan tanda lebih besar sama
dengan ().
Maka bentuk fungsi kendala akan menjadi:
Fungsi kendala: 1) 2X1 + S1
= 8
2) 3X2 + S2
= 15
3) 6X1 + 5X2 S3
+ S4 = 30

Catatan:
Untuk fungsi kendala 1) yang bertanda sama denga
n (=), maka
ditambahkan varibel slack pada ruas kiri kendala (S1), d
an variabel
artificial (M) pada fungsi tujuan (MS1).
Untuk fungsi kendala 2) yang bertanda lebih kecil sama dengan
(), maka
ditambahkan varibel slack pada ruas kiri kendala (S2).
Untuk fungsi kendala 3) yang bertanda lebih besar sama dengan
(), maka
dikurangi variabel surplus (S3) dan ditambah buatan (S4) pad
a ruas kiri
kendala, serta ditambah variabel artificial (M) pada fungsi tujuan
(MS4).
 14 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Dari kendala yang ada, maka bentuk fungsi tujuan menjadi:

Minimalkan Z = 3X1 + 5X2 + MS1 + MS4

Untuk fungsi tujuan meminimalkan, maka fungsi tujuan diuba

h menjadi
maksimisasi dengan cara mengganti tanda positif dan negatif p
ada fungsi
tujuan, sehingga menjadi:
Maksimalkan (Z) = 3X1 5X2 MS1 MS4

Dalam bentuk standar/implisit, fungsi tujuan menjadi:

V.D Z X1 X2 S1 S2 S3 S4 NK
Z 1 (8M+3) (5M+5) 0 0 M 0 (38M)
S1 0 2 0 1 0 0 0 8
S2 0 0 3 0 1 0 0 15
V.D
S3 Z
0 X61 X52 S01 S02 S3
1 S14 NK
30 Indeks
Z 1 (8M+3) (5M+5) 0 0 M 0 (38M)
S1 0 2 Z 0+ 3X1 1+ 5X2 0 + MS10 + MS04 = 0 8 4
SKarena
2 0 variabel
0 3
S1 dan 0
S4 adalah 1
variabel 0artificial,
0 maka15
nilai
S3 setiap
0 6 5 0 0 1 1 30 5
variabel dasar S1 dan S4 harus = 0, sehingga baris Z (baris fu
ngsi tujuan)
harus dikurangi dengan (M) dan dikalikan dengan baris ba
tasan yang
bersangkutan (kendala 1 dan 3). Sehingga nilai baris Z sebagai berik
ut:
Baris Z baru:
1 3 5 M 0 0 M 0
M [ 0 2 0 1 0 0 0 8
]
M [ 0 6 5 0 0 1 1 30
]
1 (8M+3) (5M+5) 0 0 M 0
(38M)
 2) Susun semua nilai ke dalam tabel simplex, dan lakukan it
Iterasi 1:
erasi sesuai
V.D Z X1 X2 S1 S2 S3 S4 NK Indeks
Z 1 3 (5M+5) (4M3/2) 0 M 0 (6M12)
X1 0 1 0 0 0 0 4
S2 0 0 3 0 1 0 0 15 5
S3 0 0 5 3 0 1 1 6 6/5
Keterangan:
V.D Z X1 X2 S1 S2 S3 S4 NK
Z 1 0 0 (M+3/2) 0 1 M+1 (18)
X1 0 1 0 1/2 0 0 0 4
S2 0 0 1 9/5 1 3/5 3/5 5 2/5
S3 0 0 1 3/5 0 1/5 1/5 6/5

15 / 17
Kolom berwarna kuning (kolom X1) dipilih sebagai kolo
m kunci.
langkah
2 Baris berwarna hijau
7 penyelesaian (barissimpleks.
meteode S1) dipilih sebagai baris kun
ci.

Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional

6623 Taufiqur Rachman

Iterasi 0:

Kolom berwarna kuning (kolom X1) dipilih sebagai kolom kunci.

Keterangan:
Baris berwarna hijau (baris S1) dipilih sebagai baris kunci.
 Karena (Z) = (18), maka Z = 18, maka penyelesaian telah men
capai solusi
optimal, dengan solusi optimal X1 = 4 ; X2 = 6/5 ; Zmin = 18.

Hasil dari iterasi 1:

REFERENSI
Noer. Bustanul Arifin, 2010, Belajar Mudah Riset Operasional, ANDI.
Sitinjak. Tumpal JR, Riset Operasi, Graha Ilmu, 2006
Taylor III. Bernard W, Manajemen Sains, Salemba Empat, 2008
Wijaya. Andi, Pengantar Riset Operasi, Mitra Wacana Media, 2012

Keterangan:

16 / 17
Universitas Esa Unggul Jakarta, 2012

Materi #4 CCR314 Riset Operasional 6623 Taufiqur Rachman

Tugas On-line 1

Kerjakan soal dibawah ini dengan metode simpleks hingga mencapai

solusi
optimal.
1. Fungsi tujuan:
 Maksimalkan Z = 40X1 + 50X2

Fungsi kendala:
1) X1 + 2X2 40
2) 4X1 + 3X2 120
Non-negatif X1 ; X2 0

2. Fungsi tujuan:
Minimalkan Z = 6X1 + 3X2

Fungsi kendala:
1) 2X1 + 4X2 16
2) 4X1 + 3X2 24
Non-negatif X1 ; X2 0

Cara menjawab:
a) Jawaban ditulis dengan tangan pada kertas A4
b) Buat softcopy/file jawaban tulis tangan tersebut (bisa di scan, foto, dll).
c) Kirimkan softcopy/file tersebut pada hybrid learning di Tugas O
n-line 1
pertemuan ke-4, paling lambat Rabu, 24 Oktober 2012, pkl. 19.00 wib.
d) Jawaban tulis tangan pada kertas A4 tersebut di kumpulkan pada perte
muan
ke-5 mata kuliah Riset Operasional (Minggu, 28 Oktober 2012).

### Selamat Mengerjakan ###

17 / 17
Universitas Esa Unggul Jakarta, 2012