Belajar riset operasi dengan GLPK

Halo selamat siang bagi yang sudah siang dan selamat shaum bagi yang lagi shaum. Mari kita isi lagi blog ini dalam rangka #julingeblog yang sudah beberapa hari ditinggalkan pemiliknya karena piknik dulu agar hatinya tenang kembali. halah.

risop dengan glpk

risop dengan glpk



Mumpung belum ada ide nulis tentang piknik dan kurang piknik, mari menulis tentang riset operasi saja. Sebuah mata kuliah yang pernah dikontrak ketika zaman dahulu kala waktu berstatus mahasiswa matematika.

Saya terpaksa kembali buka-buka materi ini gara-gara di kelas XI ada materi tentang Program Linear. Padahal tahun lalu materi ini nggak ada. Selamat untuk kurtilas yang bikin lieur guru dan siswanya :)).

Oke, apa itu riset operasi? Apa itu program linear? Apa hubungan keduanya? Saya sih sudah lupa istilah keduanya :D. Tapi menurut bapak Tommi Sottinen dalam bukunya Operation Research with GNU Linear Programming Kit [1], riset operasi alias operation research didefinisikan sebagai:

Operations Research (OR) is an interdisciplinary branch of applied mathematics and formal science that uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or near optimal solutions to complex problems.

Terus, program linear itu apa? Masih menuurt pak Tommi, program linear atau linear programming (LP) adalah salah satu alat yang digunakan dalam riset operasi. Kata ‘programming’ di sini tak ada sangkut pautnya dengan dunia pemrograman, tapi lebih mendekati kata ‘optimasi’.

Sementara menurut Bornok Sinaga, dkk, dalam buku Matematika kelas XI kurtilas yang tidak jelas itu, program linear didefinisikan sebagai berikut:

Masalah program linear adalah menentukan nilai x_1, x_2, ..., x_n yang memaksimumkan (atau meminimumkan) fungsi sasaran/tujuan,

z(x_1, x_2, ..., x_n) = C_1 X_1 + C_2 X_2 + ... + C_n X_n

dengan kendala/keterbatasan:
a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n (\leq,=,\geq)b_1
a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n (\leq,=,\geq)b_2
...
a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n (\leq,=,\geq)b_m
x_1 \geq 0, x_2 \geq 0, ..., x_n \geq 0

Contoh (diambil dari sini [2]):

Seorang pembuat kue mempunyai 8 kg tepung dan 2 kg gula pasir. Ia ingin membuat dua macam kue yaitu kue dadar dan kue apem. Untuk membuat kue dadar dibutuhkan 10 gram gula pasir dan 20 gram tepung sedangkan untuk membuat sebuah kue apem dibutuhkan 5 gram gula pasir dan 50 gram tepung.

Jika kue dadar dijual dengan harga Rp 300,00/buah dan kue apem dijual dengan harga Rp 500,00/buah, tentukanlah pendapatan maksimum yang dapat diperoleh pembuat kue tersebut.

Setelah dimodelkan, nantinya menjadi seperti berikut:
Misalkan x = kue dadar dan y = kue apem
Maksimalkan z(x,y) = 300x + 500y dengan kendala:
2x + 5y \leq 800
2x + y \leq 400

Karena cuma dua variabel, cara mengerjakannya kan mudah ya, cukup pakai grafik, cari daerah feasibelnya (yaitu yang saling beririsan) dan cari titik potong yang menyebabkan si z maksimum. Beres.

Tapi kan dalam dunia nyata, variabelnya tidak hanya 2 saja. Bisa saja ada 100 atau lebih. Yang beginian sudah tak mungkin mengandalkan grafik lagi. Lah, 4 variabel saja sudah nggak bisa, apalagi kalau 100 variabel kan ya? Iyain aja biar cepet.

Untuk itulah ada program alias software yang dapat membantu. Karena saya tak punya lagi aplikasi lingo (hasil bajakan), mari gunakan aplikasi legal. Salah satu aplikasi yang bisa digunakan adalah GLPK alias GNU Linear Programming Kit.

Masih dari bukunya Pak Tommi, GLPK adalah paket aplikasi yang dapat menyeleasikan masalah linear programming (LP), mixed integer programming (MIP), dan masalah yang mirip seperti itu.

Tapi… GPLK sendiri sebenarnya bukan aplikasi yang langsung dapat digunakan. Karena ternyata GLPK adalah sebuah librari yang dapat dimanfaatkan oleh aplikasi lain untuk menyelesaikan masalah LP dan kawan-kawannya.

Karena itu, ketika mau menyelesaikan masalah LP, tidak bisa hanya dilakukan jika cuma ada GPLK saja. Harus ada aplikasi yang disebut client. Salah satunya adalah glpsol.

Untuk di lingkungan linux, cara memasang kedua aplikasi ini sangat mudah. Untuk di Fedora, cukup mengandalkan kemampuan DNF.

$ sudo dnf install glpk glpk-utils

Kita memasang dua paket, yaitu librari glpk dan paket aplikasi glpk-utils. Si glpsol itu ada di bundel glpk-utils.

Cara pakainya bagaimana? Pertama, kita harus bikin berkas model yang isinya pemodelan matematika dari masalah yang mau dipecahkan. Berkasnya ditulis dalam bahasa GNU Mathprog. Apa itu? Cari saja di internet yah.

Mari kita kembali ke contoh. Misalkan kita ingin menyelesaikan masalah kue dadar vs kue apem dengan glpk. Kita ubah pemodelan di atas menjadi bahasa GNU Mathprog dan siman hasilnya di soal.m.

var x >= 0;
var y >= 0;

maximize z: 300*x + 500*y;

subject to r:
    2*x +  y <= 400;
subject to s:
    2*x +  5*y <= 800;
end;

Setelah itu, mari kita gunakan glpk dan kawan-kawannya untuk menyelesaikan masalah kue ini.

$ glpsol -m soal.m -o jawaban.sol

Perintah itu menyuruh si glpsol untuk membaca berkas soal.m dan mencari penyelesaiannya, lalu hasilnya disimpan di berkas jawaban.sol. Namanya bebas ya, tak harus berakhiran .sol melulu.

Jika berhasil, hasilnya sebagai berikut:

Problem:    soal
Rows:       3
Columns:    2
Non-zeros:  6
Status:     OPTIMAL
Objective:  z = 95000 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B          95000                             
     2 r            NU           400                         400          62.5 
     3 s            NU           800                         800          87.5 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x            B            150             0               
     2 y            B            100             0               

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
        max.rel.err = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

Dari sana bisa dilihat bahwa nilai z maksimumnya adalah 95000 dengan x = 150 dan y = 100.

Contoh lain [3]. Misalkan kita ingin memaksimalkan Z = X_1 + 2X_2 + X_3

Kendalanya sebagai berikut:
X_1 - 2X_2 + X_3 \leq 10
X_1 + X_2 + X_3 \leq 20
2X_1 + X_2 - X_3 \leq 15
X_1, X_2, X_3 \geq 0

Kita buat pemodelannya, seperti ini:

var X1 >= 0;
var X2 >= 0;
var X3 >= 0;

maximize z: X1 + 2*X2 + X3;

subject to kendala1:
    X1 - 2*X2 + X3 <= 10;
subject to kendala2:
    X1 + X2 + X3 <= 20;
subject to kendala3:
    2*X1 + X2 - X3 <= 15;

end;

Mari kita manfaatkan kembali si glpsol.

$ glpsol -m soal2.m -o jawaban2.sol

Ini hasilnya:

Problem:    soal2
Rows:       4
Columns:    3
Non-zeros:  12
Status:     OPTIMAL
Objective:  z = 37.5 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B           37.5                             
     2 kendala1     B          -32.5                          10 
     3 kendala2     NU            20                          20           1.5 
     4 kendala3     NU            15                          15           0.5 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 X1           NL             0             0                        -1.5 
     2 X2           B           17.5             0               
     3 X3           B            2.5             0               

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
        max.rel.err = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

Dari sana bisa dilihat bahwa maksimumnya di z = 37,5 dengan X1 = 0, X2 = 17,5 dan X3 = 2,5.

Yasudah sekian saja dulu. Mudah bukan?

*sumber:
[1] http://www.uwasa.fi/~tsottine/orms1020
[2] https://bahanbelajarsekolah.blogspot.co.id/2014/10/contoh-soal-cerita-program-linear-dan-pembahasan.html
[3] http://file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/196801281994021-LUKMAN/Proglin.pdf

Ada komentar?

%d bloggers like this: