Sekarang kita akan membahas tentang Linear Programming.

Linear Programming adalah suatu model optimisasi untuk menemukan solusi optimal dengan menggunakan fungsi objektif linear dalam suatu himpunan solusi yang ditentukan oleh sistem persamaan dan ketaksamaan linear. Program linear merupakan model yang paling sederhana dalam optimisasi, namun merupakan model yang sangat berguna dalam kehidupan nyata dan efisien untuk mencari solusi optimal.

Terminologi Dasar

Dalam bagian ini, kita akan mendefinisikan dasar-dasar untuk menyelesaikan masalah pemrograman linier. Pertama, kita mendefinisikan polihedron, yang merupakan himpunan semua solusi dari suatu sistem persamaan dan ketaksamaan linear.

Misalkan kita memiliki sistem persamaan dan ketaksamaan linear seperti berikut:

A . x = b1 B . x ≤ b2

di mana A adalah matriks m1 x n dan B adalah matriks m2 x n, b adalah vektor berdimensi m1, dan d adalah vektor berdimensi m2. Himpunan semua solusi x dalam Rn yang memenuhi persamaan dan ketaksamaan di atas, yaitu

A . x = b1 B . x ≤ b2

disebut sebagai polihedron.

Contoh 153 Untuk menggambar polihedron di R2, kita menggunakan paket gMOIP di R [30]. Untuk contoh ini, kita memiliki sistem ketaksamaan linear berikut:

x1 + x2 ≤ 7 x1 + 7 - x2 ≤ 35 -x1 + x2 ≤ 3 x1 ≥ 0 x2 ≥ 0

Untuk memvisualisasikan polihedron, pertama-tama kita memuat paket gMOIP dalam R.

library(gMOIP)

Kemudian kita harus memiliki bentuk:

B . x ≤ b2

obj <-c(2,7)

Sekarang kita mendefinisikan matriks B dan vektor b2 di R.

A <-matrix(c(1,1,1,7,-1,1,-1,0,0,-1),nrow=5,
ncol =2,byrow=TRUE)
A
##      [,1] [,2]
## [1,]    1    1
## [2,]    1    7
## [3,]   -1    1
## [4,]   -1    0
## [5,]    0   -1
b <-c(7,35,3,0,0)
b
## [1]  7 35  3  0  0

Lalu kita memanggil fungsi plotPolytope() dari paket gMOIP dalam R.

plotPolytope(
A,
b,
obj,
type =rep("c",ncol(A)),
crit ="max",
faces =rep("c",ncol(A)),
plotFaces =TRUE,
plotFeasible =TRUE,
plotOptimum =FALSE,
labels ="coord"
)

Gambar 8.1 Polihedron yang didefinisikan oleh sistem ketaksamaan linear pada Contoh 153.

Linear Programming

Pemrograman linear adalah sebuah model dalam optimisasi untuk mencari solusi optimal dari sebuah fungsi linear di atas sebuah polihedron. Sebagai contoh, pertimbangkan polihedron pada Contoh 153. Misalkan kita ingin mencari solusi optimal sehingga max 2 * x1 + 7 * x2 dengan syarat :

x1 + x2 ≤ 7 x1 + 7 * x2 ≤ 35 -x1 + x2 ≤ 3 x1 ≥ 0 x2 ≥ 0

Ini adalah sebuah masalah pemrograman linear. Fungsi yang ingin kita optimalkan disebut fungsi biaya (cost function). Dalam contoh ini, fungsi linear max 2 * x1 + 7 * x2 adalah fungsi biaya.

Dengan menggunakan paket gMOIP di R, kita dapat memvisualisasikan masalah pemrograman linear di R2 dan juga mencari solusi optimal dari masalah tersebut. Sebagai contoh, pertimbangkan polihedron pada Contoh 153 dan fungsi biaya max 2 * x1 + 7 * x2.

Pertama, kita akan mendefinisikan fungsi biaya dalam R:

obj <-c(2,7)

Lalu kita panggil fungsi plotPolytope() :

Kemudian itu akan menghasilkan solusi optimal sebagai berikut: x1 = 2.33 x2 = 4.67 dan nilai optimalnya adalah 37.33. Juga menghasilkan plot seperti yang ditunjukkan dalam Gambar 8.2.

plotPolytope(
A,
b,
obj,
type =rep("c",ncol(A)),
crit ="max",
faces =rep("c",ncol(A)),
plotFaces =TRUE,
plotFeasible =TRUE,
plotOptimum =TRUE,
labels ="coord"
)

Gambar 8.2 Polihedron dan fungsi biaya untuk masalah pemrograman linear. Garis putus-putus adalah fungsi biaya linear untuk masalah tersebut dan z* adalah nilai optimal.

Practical Applications

Dalam Aplikasi Praktis, kita menggunakan paket lpSolve dalam R untuk mencari nilai optimal dan solusi optimal untuk masalah pemrograman linear dengan dataset Guinness.

Pertama, seperti yang kita bahas dalam Bagian 1.3, kita mengatur masalah ini sebagai sistem persamaan linear dan ketaksamaan linear. Untuk situs produksi, kita mengasosiasikan angka 1 dengan Achimota dan angka 2 dengan Kaasi. Untuk distributor, kita mengasosiasikan angka 1 dengan FTA, 2 dengan RICKY, 3 dengan OBIBAJK, 4 dengan KADOM, 5 dengan NAATO, 6 dengan LESK, 7 dengan DCEE, 8 dengan JOEMAN, dan 9 dengan KBOA. Kemudian, kita mengassign variabel-variabel yang ditunjukkan dalam tabel 2x9 berikut ini:

library(magick)
## Linking to ImageMagick 6.9.12.3
## Enabled features: cairo, freetype, fftw, ghostscript, heic, lcms, pango, raw, rsvg, webp
## Disabled features: fontconfig, x11
imgshow <- image_read("tablePA.png")
plot(imgshow)

di mana Xij untuk i = 1; 2 dan j = 1; 2; …; 9 adalah jumlah bir dari situs produksi i ke distributor j. Ini dapat ditulis sebagai sistem persamaan linear dan ketaksamaan sebagai berikut:

x11 + x12 + … + x19 = 1298 x21 + x22 + … + x29 = 1948 x11 + x21 = 465 x12 + x22 = 605 x13 + x23 = 451 x14 + x24 = 338 x15 + x25 = 260 x16 + x26 = 183 x17 + x27 = 282 x18 + x28 = 127 x19 + x29 = 535

untuk semua variabel Xij dengan Xij ≥ 0. Selain itu, koefisien untuk fungsi biaya dapat ditemukan dalam Tabel 8.2. Fungsi biaya tersebut adalah:

39:99 . x11 + 126:27 . x12 + 102:70 . x13 + 81:68 . x14 + 38:81 . x15 +71:99 . x16 + 31:21 . x17 + 22:28 . x18 + 321:04 . x19 + 145:36 . x21 +33:82 . x22 + 154:05 . x23 + 64:19 . x24 + 87:90 . x25 + 107:98 . x26 +65:45 . x27 + 39:08 . x28 + 167:38 . x29:

Dalam masalah ini, kita ingin meminimalkan fungsi biaya di atas politop yang didefinisikan oleh sistem persamaan linear dan ketaksamaan.

Di R, pertama-tama kita mendefinisikan matriks dan vektor untuk mendefinisikan politop menggunakan fungsi diag() dan therbind():

Tetapi sebelumnya, install dan muat dulu package lpSolve sebelum mendefiniskan,

library(lpSolve)
A <-matrix(c(1,1,1,1,1,1,1,1,1,0,
0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,
0 ,0,0,1,1,1,1,1,1,1,1,1,1,0,
0 ,0,0,0,0,0,0,1,0,0,0,0,0,0,
0 ,0,0,1,0,0,0,0,0,0,0,0,1,0,
0 ,0,0,0,0,0,0,0,1,0,0,0,0,0,
0 ,0,0,1,0,0,0,0,0,0,0,0,0,1,
0 ,0,0,0,0,0,0,0,1,0,0,0,0,0,
0 ,0,0,0,1,0,0,0,0,0,0,0,0,1,
0 ,0,0,0,0,0,0,0,0,1,0,0,0,0,
0 ,0,0,0,1,0,0,0,0,0,0,0,0,0,
1 ,0,0,0,0,0,0,0,0,1,0,0,0,0,
0 ,0,0,0,0,1,0,0,0,0,0,0,0,0,
1 ,0,0,0,0,0,0,0,0,0,1,0,0,0,
0 ,0,0,0,0,1),nrow=11,ncol=18,byrow=TRUE)
f.con <-rbind(A,diag(18))

Kemudian kita mendefinisikan vektor untuk sisi kanan sistem persamaan dan ketaksamaan:

f.rhs <-c(1298,1948,465,605,451,338,260,183,282,127,535,
0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)

Selanjutnya, kita mendefinisikan fungsi biaya dan persamaan atau ketaksamaan:

f.obj <-c(39.99,126.27,102.70,81.68,38.81,71.99,
31.21, 22.28,321.04,145.36,33.82,154.05,64.19,
87.90, 107.98,65.45,39.08,167.38)
f.dir <-c("=","=","=","=","=","=","=","=","=","=","=",
">=", ">=",">=",">=",">=",">=",">=",">=",">=",">=",
">=", ">=",">=",">=",">=",">=",">=",">=")

Kemudian kita menggunakan fungsi lp() dari paket lpSolve untuk mencari solusi optimal dan nilai optimal:

Sol <-lp("min",f.obj,f.con,f.dir,f.rhs)

Argumen pertama dari fungsi lp() harus berisi “min” untuk masalah kita karena kita sedang meminimalkan fungsi biaya di atas politop.

Untuk melihat nilai optimalnya, kita mengetik “Sol$objval”. Kemudian R akan mengembalikan:

Sol$objval
## [1] 245498.9

Jika kita ingin mencari solusi optimal, maka kita mengetik “Sol$solution” di R:

Sol$solution
##  [1] 465   0 451   0 260 122   0   0   0   0 605   0 338   0  61 282 127 535

Nah, sekian dulu pembahasan mengenai Linear Programming pada kali ini.