Pemecahan Persoalan Program Linier Dengan Metode
Simpleks
Martinus koa
Universitas Negeri Timor
Program
linier merupakan metode matematika dalam mengalokasikan sumber daya yang
terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan
meminimumkan biaya. Program linier banyak diterapkan dalam masalah ekonomi industri,
militer, sosial dan lain-lain. Program linier berkaitn dengan penjelasan suatu
kasus dalam dunia nyata sebagai suatu metode matematika.
Salah
satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier
adalah metode simpleks. Penentuan solusi optimal menggunakan metode simpleks
didasarkan pada teknik eliminasi Gaus Jordan. penentuan solusi optimal
dilakukan dengan memeriksa titik ekstrim satu persatu dengan cara perhitungan
iteratif. sehingga penentuan solusi optimal dengan simpleks dilakukan dengan tahap
demi tahap yang disebut dengan iterasi.
Metode
simpleks ini adalah metode yang biasanya digunakan untuk memecahkan setiap
permasalahan pada pemrograman linier yang kombinasi variabelnya terdiri dari
tiga variabel atau lebih. Metode simplex merupakan sebuah metode lanjutan dari
metode grafik. Metode grafik tidak dapat menyelesaikan persoalan manajemen yang
memiliki variabel keputusan yang cukup besar, sehingga untuk menyelesaikannya
dibutuhkan sebuah metode yang lebih kompleks yaitu dengan menggunakan program
komputer QSB ( Quantitative System For Business) atau menggunakan metode
simplex. Dalam kenyataanya penggunaan komputer lebih efisien, akan tetapi
metode dasar yang digunakan dalam pengoperasian komputer tetap metode simplex.
Metode
simplex adalah metode yang dapat digunakan untuk menyelesaikan persoalan
manajerial yang telah diformulasikan terlebih dahulu ke dalam persamaan
matematika program linear yang mempunyai variable keputusan mulai dari lebih
besar atau sama dengan 2 (dua) sampai multivariable. Sedangkan metode grafik
hanya dapat digunalan apabila jumlah variable keputusan maksimal 2 (dua) buah.
Sehingga dapat disimpulkan bahwa suatu persoalan linear programing yang
diselesaikan dengan metode grafik juga dapat diselesaikan dengan metode
simpleks, sebaliknya suatu persoalan yang hanya bisa diselesaikan dengan metode
simplex tidak dapat diselesaikan dengan metode grafik.
Beberapa
ketentuan yang perlu diperhatikan,
antara lain:
1. Nilai kanan (NK / RHS) fungsi tujuan harus nol (0).
2. Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harusdikalikan
–1.
3. Fungsi kendala dengan tanda “≤ atau ≥” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus.
Variabel slack/ surplus disebut juga variabel dasar
Langkah-langkah yang
harus dipahami dalam menggunakan metode simpleks, yaitu:
1.
Membuat model matrix LP
2.
Merubah formulasi LP
menjadi formulasi standar
Merubah formulasi biasa
ke dalam formulasi standar harus mengikuti kaidah dasar yang berlaku, yaitu:
a.
Introduksikan variabel
baru sebagai variable dummy dengan singkatan huruf S sebagai singkatan dari
Slack (kekurangan) atau Surplus (kelebihan)
b.
Variable slack kita
introduksikan apabila kita mempunyai bentuk tanda pembatas lebih kecil atau
sama dengan (≤)
c.
Variabel surplus kita
introduksikan apabila kita mempunyai bentuk tanda pembatas lebih besar dari
atau sama dengan (≥)
3.
Menyiapkan table
simplex awal
|
|
Cj
|
|
|
|
|
|
|
|
|
Ci
|
BV
|
X1
|
X2
|
Xn
|
S1
|
S2
|
Sn
|
Bi
|
|
|
S1
|
|
|
|
|
|
|
|
|
|
S2
|
|
|
|
|
|
|
|
|
|
Sn
|
|
|
|
|
|
|
|
|
|
Zj
|
|
|
|
|
|
|
|
|
Cj-ZJ
|
|
|
|
|
|
|
|
|
Penjelasan
penggunaan tabel simplex :
a.
Kolom Baris
· Kolom
baris selalu ada dan ditempatkan di kolom paling kiri setelah Ci
· Untuk
kolom tabel awal variabel yang pertama kali kita tulis pada kolom ini adalah:
o Variabel
tambahan yang bertanda positif seperti slack variable
o Artifisial
variabel
Oleh karena itu,
surplus variabel tidak pernah kita masukan ke dalam kolom basis pada tabel awal
b.
Kolom Cj
Kolom coefisien fungsi
tujuan diletakan pada baris pertama tabel awal simplex. Angka koefisien dapat
kita lihat pada fungsi tujuan formulasi standar daro persoalan yang dihadapi.
c.
Kolom diantara kolom Cj
dan kolom paling kanan atau kolom nilai
ruas kanan
Jumlah kolom ini
bervariasi tergantung berapa jumlah variabel yang ada di dalam fungsi tujuan
formulasi standar. Oleh karena itu apabila terjadi kesalahan dalam membuat
formulasi standar maka penyelesaian persoalan dengan metode simplex juda akan
salah.
d.
Kolom nilai ruas kanan
(NRK atau Bi)
Pada kolom ini,
dituliskan nilai ruas kanan dari setiap batasan yang ada di dalam setiap
persoalan yang dihadapi.
e.
Jumlah baris
Jumlah baris di antara
baris Basic variabel dengan baris Zj tergantung dari berapa buah batasan yang
kita hadapai di dalam perseoalan.
f.
Baris Zj
Baris Zj digunakan
untuk mendapat nilai Shadow Price atau Nilai Merginal Value Product dari setiap
variabel yang kita hadapi. Angka yang akan kita tuliskan pada baris Zj ini
adalah angka hasil penjumlahan perkalian setiap koefisien dari variabel yang
tertera dalam kolom baris dengan angka-angka di dalam Matrix
g.
Baris Cj-Zj
baris ini bermanfaat
bagi kita untuk melihat kapan kita berhenti melakukan iterasi atau baris yang
dapat membantu kita menentukan apakah penyelesaian optimal telah kita capai.
4.
Memasukan nilai-nilai
dan variable dalam formulasi standar ke dalam tabel awal
5.
Melakukan proses
literasi
a.
Tentukan kunci kolom
(pivot coloum)
Caranya
adalah memilih nilai Cj-Zj yang terbesar dan positif.
b.
Tentukan kunci baris
(pivot row)
Caranya adalah memilih
dasil bagi antara NRK dengan angka-angka yang ada dalam kolom kunci, kemudian
pilih hasil bagi yang terkecil dan positif. Hasil bagi dengan nilai negative,
nol dan tak terhingga tidak dapat dijadikan sebagai kunci baris.
c.
Cari angka baru yang
terdapat pada baris kunci dengan cara membagi semua angka yang terdapat pada
baris kunci dengan angka kunci. Angka kunci adalah angka yang terdapat pada
persilangan baris kunci dengan kolom kunci.
d.
Mencari angka baru pada
baris yang lain dengan rumus:
Angka baru = nilai pada
baris lama – (perkalian koefisien pada kolom kunci dengan angka baru baris
kunci)
e.
Apabila sosialisasi
optimal belum ditemukan maka kembali ke langkah 5a di atas, sehingga nilai yang
terdapat pada baris Cj-Zj ≤ 0
6.
Menentukan apakah
penyelesaikan optimal sudah tercapai
7.
Membuat kesimpulan
jawaban
Contoh penyelesain
program linier dengan menggunakan metode simpleks
PT Yummy food memiliki sebuah pabrik yang akan
memproduksi dua jenis produk yaitu vanilla dan violette. Untuk memproduksi
kedua produk tersebut diperlukan bahan baku A, bahan baku B dan jam tenaga
kerja. Maksimum pengerjaan bahan baku A adalah 60kg per hari, bahan baku B 30kg
per hari dan tenaga kerja 40jam per hari. Kedua jenis produk memberikan
sumbangan keuntungan sebesar Rp40,00 untuk vanilla dan Rp30,00 untuk violette.
Masalah yang dihadapi adalah bagaimana menentukan jumlah unit setiap produk
yang akan diproduksi setiap hari. Kebutuhan setiap unit produk akan bahan baku
dan jam tenaga kerja dapat dilihat pada tabel berikut ini:
|
Jenis
bahan baku dan tenaga kerja
|
Kg
bahan baku dan jam tenaga kerja
|
Maksimum
Penyediaan
|
|
|
Vanilla
|
Violette
|
||
|
Bahan baku A
|
2
|
3
|
60Kg
|
|
Bahan baku B
|
-
|
2
|
30Kg
|
|
Tenaga Kerja
|
2
|
1
|
40jam
|
|
Sumbangan keuntungan
|
Rp40,00
|
Rp30,00
|
|
Penyelesaian:
Z
= Rupiah keuntungan per hari
X1 = Jumlah vanilla yang diproduksi/perhari
X2
= jumlah violette yang diproduksi/hari
Langkah
1
Formulasi
LP (bentuk standar)
Fungsi
tujuan è
Zmax = 40X1 + 30X2
Fungsi
kendala è
I. 2X1 + 3X2 ≤ 60
II. 2X2 ≤ 30
III. 2X1 + 1X2 ≤ 40
IV.
X1,X2 ≥ 0
Diubah
menjadi:
2X1
+ 3X2 + S1 + 0S2 + 0S3 = 60
2X2 + 0S1 + S2 + 0S3 = 30
2X1
+ 1X2 + 0S1 + 0S2 + S3 = 40
40X1
+ 30X2 + 0S1 + 0S2 + 0S3
C1
= 40, C2 = 30, C3 = 0, C4= 0, C5 = 0
Langkah
2
Tabel
simplex awal masalah PT Yummy Food
|
|
Cj
|
40
|
30
|
0
|
0
|
0
|
|
|
Ci
|
BV
|
X1
|
X2
|
S1
|
S2
|
S3
|
Bi
|
|
0
|
S1
|
2
|
3
|
1
|
0
|
0
|
60
|
|
0
|
S2
|
0
|
2
|
0
|
1
|
0
|
30
|
|
0
|
S3
|
2
|
1
|
0
|
0
|
1
|
40
|
|
|
Zj
|
0
|
0
|
0
|
0
|
0
|
0
|
|
Cj-ZJ
|
40
|
30
|
0
|
0
|
0
|
|
|
Langkah 3
Apakah tabel
tersebut sudah optimal?
Belum, karena
tabel optimal bila nilai yang terdapat pada baris Cj – Zj ≤ 0
Langkah 4
Penyelesaian
dengan cara iterasi
1.
Menentukan kolom kunci,
yaitu kolom yang memiliki nilai Cj-Zj terbesar yaitu kolom x1. Dengan demikian
x1 akan masuk dalam basis
2.
Menentukan baris kunci,
yaitu baris yang memiliki angka indeks terkecil dan bukan negatif. Dalam hal
ini baris s3. Dengan demikian s3 akan keluar dari basis dan tempatnya akan
digantikan oleh x1
3.
Menetukan angka kunci.
Angka kunci adalah angka yang terdapat pada persilangan kolom kunci dengan
baris kunci, dalam hal ini angka kunci = 2
4.
Mencari angka baru yang
terdapat pada baris kunci, dengan cara membagi semua angka yang terdapat pada
baris kunci dengan angka kunci
Angka
baru = 40/2, 2/2, ½, 0/2, 0/2, ½
Atau
= 20, 1, ½, 0,0 ½
5.
Mencari angka baru pada
baris lain, yaitu :
Baris
S1
Angka
lama = [ 60 2 3 1 0
0 ]
Angka
baru = [ 20 1 ½ 0 0
½] (2)
Angka
baru = [20 0 2 0 0
-1]
Baris S2
Angka
lama = [ 30 0 2 0 1
0]
Angka
baru = [ 20 1 ½ 0 0
1/2] (0)
Angka
baru = [ 30 0 2 0 1
0]
Hasil perhitungan di atas, akan nampak
pada tabel baru simplex yaitu tabel yang merupakan hasil iterasi pertama.
|
|
Cj
|
40
|
30
|
0
|
0
|
0
|
|
|
Ci
|
BV
|
X1
|
X2
|
S1
|
S2
|
S3
|
Bi
|
|
0
|
S1
|
0
|
2
|
1
|
0
|
-1
|
20
|
|
0
|
S2
|
0
|
2
|
0
|
1
|
0
|
30
|
|
40
|
X1
|
1
|
½
|
0
|
0
|
½
|
20
|
|
|
Zj
|
40
|
20
|
0
|
0
|
20
|
|
|
Cj-ZJ
|
0
|
10
|
0
|
0
|
0
|
|
|
Tabel iterasi 1 belum optimal sehingga
harus diulang langkah di atas dan akan di dapat tabel iterasi 2:
|
|
Cj
|
40
|
30
|
0
|
0
|
0
|
|
|
Ci
|
BV
|
X1
|
X2
|
S1
|
S2
|
S3
|
Bi
|
|
30
|
X1
|
0
|
1
|
½
|
0
|
-1/2
|
10
|
|
0
|
S2
|
0
|
0
|
-1
|
1
|
1
|
10
|
|
40
|
S3
|
1
|
0
|
-1/4
|
0
|
¾
|
15
|
|
|
Zj
|
40
|
30
|
5
|
0
|
15
|
|
|
Cj-ZJ
|
0
|
0
|
-5
|
0
|
-15
|
900
|
|
Solusi optimum tabel iterasi 2
menunjukan bahwa total nilai Z = 900 dengan masing-masing variabel keputusan X1
= 15 dan X2 = 10.
|
Variabel
basis
|
Koefisien
fungsi tujuan
|
Nilai
variabel basis
|
|
|
X2
|
30
|
10
|
300
|
|
S2
|
0
|
10
|
0
|
|
X1
|
40
|
15
|
600
|
|
|
|
JUMLAH
|
900
|
KESIMPULAN:
1.
Pada tabel iterasi 2
merupakan tabel akhir simplex, dengan solusi optimal adalah :
X1
(vanilla) = 15 unit
X2
(violette) = 10 unit
Z
(keuntungan) = Rp 900,00
2.
Kendala kedua (bahan
baku B) masih tersisa sebanyak 10 Kg yang ditunjukan oleh nilai S2 =10, pada
tabel optimal
3.
Kendala 1 dan 3 tidak
ada sisa (full capacity), yang ditunjukan oleh nilai S1 = S3 = 0 (variabel nonbasis). Hal ini juga dapat
dibuktikan dengan memasukan nilai S1 dan S2 ke dalam kendala 1 dan 3
Kendala
1 : 2X1 + 3X2 = 60
2
(15) + 3 (10) = 60
60 = 60
Bahan
baku yang digunakan = yang tersedia
Kendala
3 : 2X1 + 1X2 = 40
2 (15) + 1(10) = 40
40 = 40
Jam
kerja yang digunakan = yang tersedia
ANALISIS
SENSITIVITAS
Pada
metode penyelesaian masalah program linear sebelumnya, parameter-parameternya
diketahui. Tetapi di sini, konstanta aij, bi, dan Cj
diperkirakan atau dengan kata lain dapat berubah karena pengaruh suatu faktor.
Analisis sensitivitas dirancang untuk mempelajari pengaruh perubahan dalam
parameter model program linear terhadap pemecahan optimal. Tujuan akhir dari
analisis ini adalah untuk memperoleh informasi tentang pemecahan optimal yang
baru dan yang dimungkinkan dengan perhitungan yang minimal.
1. Shadow Price
Shadow Price
menyatakan berapa besarnya fungsi tujuan akan berubah jika sisi kanan fungsi
kendala ditambah satu unit. Secara umum, Shadow
Price untuk setiap kendala dapat
dinyatakan sebagai berikut.
Shadow Price
ini kita dapat lihat pada tabel optimal simpleks kolom slack variabel Zj – Cj.
2. Dampak Perubahan
Parsial Sisi Kanan Fungsi Kendala Terhadap Solusi Optimal
Perubahan
secara parsial sisi kanan fungsi kendala artinya kita menasumsikan hanya salah
satu kendala saja berubah, sedangkan kapasitas kendala yang lainnya dianggap
konstan. Kapasitas sisi kanan fungsi kendala bisa saja berubah. Pertanyaan yang
sering muncul dalam masalah ini adalah bagaimana dampak penambahan atau
pengurangan kapasitas sisi kanan fungsi kendala terhadap solusi optimal. Kita
akan menjawab pertanyaan ini dengan menggunakan “change vector”. change vector
adalah suatu angka yang mengukur perubahan nilai optimal basic variable karena
adanya penambahan satu unit sisi kanan fungsi kendala. Cange vector ini dapat kita lihat pada baris basic variable
(variabel yang berada pada kolom product mix) kolom slack variabel. Secara
matematis change vector dapat
dinyatakan sebagai berikut.
3. Dampak Perubahan
Simultan dan Rentang Perubahan Sisi Kanan Fungsi Kendala Terhadap Solusi
Optimal
Sudah
dijelaskan dampak perubahan secara parsial sisi kanan fungsi kendala terhadap
solusi optimal. Pada kenyataannya perubahan sisi kanan fungsi kendala sering
kali berubah secara simultan. Adanya perubahan dalam satu sistem diikuti oleh
perubahan sistem lainnya dalam waktu yang bersamaan.
4. Perubahan Konstanta
Sisi Kanan
Penambahan
bi pada kendala dapat terjadi dan kita ingin menentukan bagaimana
pengaruhnya terhadap kombinasi optimal. Tambahan bi itu mengubah
vektor sisi kanan pada tabel simpleks awal yaitu
Fungsi tujuan:
Maksimal
Z = C1 X1 + C2 X2 + C3 X3
Fungsi
kendala:
Vektor
pada tabel awal berubah menjadi
Tabel 1. Tabel Pivot
|
Basis
|
|
C0
|
C1
|
C2
|
C3
|
C4
|
C5
|
|
|
C0
|
P0
|
P1
|
P2
|
P3
|
P4
|
P5
|
||
|
P4
|
C4
|
b1
|
B11
|
B12
|
B13
|
B14
|
B15
|
|
|
P5
|
C5
|
b2
|
B21
|
B22
|
B23
|
B24
|
B25
|
|
|
Zj-Cij
|
|
|
|
|
|
|
|
|
Tabel 1. Merupakan
tabel standar yang digunakan untuk menyelesaikan masalah program linear dengan
metode simplekx.
Maka
Kemudian nilai b*
bergantung pada beberapa banyak b1 yang dinaikkan atau diturunkan,
dan akan menggantikan b0 pada iterasi pencapaian nilai optimal
sebelumnya. Selanjutnya analisis sensitivitas dapat dicari dengan menggunakan
program Lindo.
5. Contoh dan Penyelesaian
Analisis Sensitivitas
Sebuah
perusahaan memproduksi jaket dan tas kulit. Sebuah jaket memerlukan 8 meter
persegi kulit dan tas hanya menggunakan 3 meter persegi. Persyaratan kerja
untuk kedua produk tersebut adalah 12 jam dan 4 jam. Harga pembelian kulit
adalah $ 8 per meter persegi dan biaya tenaga kerja diperkirakan sebesar $ 15
per jam. Persediaan kulit mingguan saat ini dan tenaga kerja dibatasi sampai
1200 meter persegi dan 1800 jam. Perusahaan menjual jaket dan tas masing-masing
dengan harga $ 350 dan $ 120. Tujuannya adalah untuk menentukan jadwal produksi
yang memaksimalkan pendapatan bersih. Perusahaan sedang mempertimbangkan untuk
memperluas produksi. Berapa harga pembelian maksimal yang harus dibayar
perusahaan untuk kulit dan tenaga kerja?
Misalkan jaket = x1
dan tas x2
|
Produk
|
Kulit yang dipakai @
$ 8/meter persegi
|
Jam kerja tiap produk
@ $ 15/jam
|
|
Jaket = x1
Tas = x2
|
8m2 x $
8/m2 = $ 64
3m2 x $
8/m2 = $ 24
|
12 jam x $ 15/jam = $
180
4 jam x $ 15/jam = $
60
|
|
Persediaan
|
1200 m2 x
8/m2 = $ 9.600
|
1800 jam x $ 15/jam =
$ 27.000
|
Model matematikanya
adalah
Fungsi tujuan: maksimal
Fungsi kendala:
Ditanyakan:
Harga pembeli maksimal yang harus dibayar perusahaan untuk kulit dan tenag
kerja.
Penyelesaian:
Minimalkan:
Dengan batasan:
|
Angka kunci
|
|
Kolom kunci
|
|
Baris kunci
|
Tabel 2. Matriks awal
|
BASIS
|
C
|
c
|
-350
|
-120
|
0
|
0
|
min
|
|
P0
|
P1
|
P2
|
P3
|
P4
|
|
||
|
P3
|
0
|
9600
|
64
|
24
|
1
|
0
|
150
|
|
P4
|
0
|
27000
|
180
|
60
|
0
|
1
|
150
|
|
Zj
– Cj
|
|
0
|
350
|
120
|
0
|
0
|
|
Untuk Zj – Cj
0,
kita pilih nilai yang paling besar yaitu 350 dan
min kita pilih 150 (yang terkecil). Jadi,
pertemuan antara baris dan kolom kunci yaitu P1 = 180.
Tabel 3. Iterasi pertama
|
BASIS
|
C
|
c
|
-350
|
-120
|
0
|
0
|
min
|
|
P0
|
P1
|
P2
|
P3
|
P4
|
|||
|
P3
|
0
|
0
|
0
|
8/3
|
1
|
-16/45
|
0
|
|
P1
|
-350
|
150
|
1
|
1/3
|
0
|
1/180
|
450
|
|
Zj
– Cj
|
|
-52.500
|
0
|
10/3
|
0
|
-350/180
|
|
P1
menggantikan P4 menjadi basis sedangkan pertemuan antara basis dan
kolom kunci dijadikan 1, selanjutnya kolom kunci dijadikan nol. Karena Zj –
Cj
masih ada yang positif, kita pilih 10/3
(maksimal) sebagai kolom kunci dan
min = 0 sebagai baris kunci. Jadi,
pertemuan antara baris dan kolom kunci = 8/3 pada P2.
Tabel 4. Iterasi kedua
|
BASIS
|
C
|
c
|
-350
|
-120
|
0
|
0
|
min
|
|
P0
|
P1
|
P2
|
P3
|
P4
|
|||
|
P2
|
-120
|
0
|
0
|
1
|
3/8
|
-2/15
|
|
|
P1
|
-350
|
150
|
1
|
0
|
-1/8
|
1/120
|
|
|
Zj–
Cj
|
|
-52.500
|
0
|
0
|
-10/8
|
-450/300
|
|
Karena nilai Zj –
Cj
sudah memenuhi maka iterasi dihentikan. Jadi
kita dapatkan
karena fungsin
tujuannya mula-mula adalah maksimal, maka harus dikalikan lagi dengan dengan
(-1), diperoleh:
Maksimal
= 350(150) + 120(0)
= $ 52.500
Jadi, harga berli
maksimal yang harus dibayar perusahaan untuk kulit dan tenaga kerja adalah $
52.500.
Sumber
:
·
https://www.academia.edu/3449276/Program_Linear_dengan_Metode_Simplex
FBS – Dapatkan Bonus Deposit Sekarang Juga, bergabung sekarang juga dengan kami
BalasHapustrading forex http://fbsindonesia.co.id
-----------------
Kelebihan Broker Forex FBS
1. FBS MEMBERIKAN BONUS DEPOSIT HINGGA 100% SETIAP DEPOSIT ANDA
2. SPREAD DIMULAI DARI 0 Dan
3. DEPOSIT DAN PENARIKAN DANA MELALUI BANK LOKAL Indonesia dan banyak lagi yang lainya
Buka akun anda di http://fbsindonesia.co.id
-----------------
Jika membutuhkan bantuan hubungi kami melalui
Tlp : 085364558922
BBM : fbsid007