Pengertian Linear Programming

Linear programming adalah salah satu model matematika yang digunakan untuk menyelesaikan masalah optimisasi, yaitu memaksimukan atau meminimumkan fungsi tujuan yang bergantung pada sejumlah variabel input atau metode untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear.

linear programming memiliki dua macam fungsi, yang pertama pada fungsi tujuan yakni mengarahkan analisa untuk mendeteksi tujuan perumusan masalah, dan yang kedua yakni tujuan kenda, tujuan kendala yakni untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.

# Import lpSolve package
library(lpSolve)

Package lpSolve

Paket lpSolve dari R berisi beberapa fungsi untuk menyelesaikan masalah program linier dan mendapatkan analisis statistik yang signifikan. Lp_solve tersedia secara bebas (di bawah LGPL 2) perangkat lunak untuk menyelesaikan program linear, integer, dan integer campuran. Di dalam implementasi kami menyediakan fungsi ``wrapper’’ di C dan beberapa R fungsi yang memecahkan masalah linier/bilangan bulat umum, masalah penugasan, dan masalah transportasi.

# Set coefficients of the objective function
f.obj <- c(5, 7)
 
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(1, 0,
                  2, 3,
                  1, 1), nrow = 3, byrow = TRUE)

# Set unequality signs
f.dir <- c("<=",
           "<=",
           "<=")

# Set right hand side coefficients
f.rhs <- c(16,
           19,
           8)

# Final value (z)
lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 46
# Variables final values
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 5 3
# Sensitivities
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
## [1] 4.666667 5.000000
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
## [1] 7.0 7.5
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
## [1] 0 2 1 0 0
# Duals lower and upper limits
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
## [1] -1.000000e+30  1.600000e+01  6.333333e+00 -1.000000e+30 -1.000000e+30
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
## [1] 1.0e+30 2.4e+01 9.5e+00 1.0e+30 1.0e+30

Contoh Penyelesaian Program Liniear

PT. HARAPAN TEKSTIL memiliki sebuah pabrik yang akanc memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut:

Kedua jenis produk memberikan keuntungan sebesar Rp.40.000.000,- untuk kain sutera dan Rp.30.000.000,- untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal.

# Set coefficients of the objective function
f.obj1 <- c(40, 30)
 
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con1 <- matrix(c(2, 3,
                  0, 2,
                  2, 1), nrow = 3, byrow = TRUE)

# Set unequality signs
f.dir1 <- c("<=",
           "<=",
           "<=")

# Set right hand side coefficients
f.rhs1 <- c(60,
           30,
           40)

# Final value (z)
lp("max", f.obj1, f.con1, f.dir1, f.rhs1)
## Success: the objective function is 900

Keuntungan Optimal yang diperoleh adalah Rp. 900 juta.

# Variables final values
lp("max", f.obj1, f.con1, f.dir1, f.rhs1)$solution
## [1] 15 10

Diketahui x1 = 15 dan x2 = 10 untuk memperoleh keuntungan Rp. 900 juta.

# Sensitivities
lp("max", f.obj1, f.con1, f.dir1, f.rhs1, compute.sens=TRUE)$sens.coef.from
## [1] 20 20
lp("max", f.obj1, f.con1, f.dir1, f.rhs1, compute.sens=TRUE)$sens.coef.to
## [1] 60 60
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("max", f.obj1, f.con1, f.dir1, f.rhs1, compute.sens=TRUE)$duals
## [1]  5  0 15  0  0
# Duals lower and upper limits
lp("max", f.obj1, f.con1, f.dir1, f.rhs1, compute.sens=TRUE)$duals.from
## [1]  4e+01 -1e+30  3e+01 -1e+30 -1e+30
lp("max", f.obj1, f.con1, f.dir1, f.rhs1, compute.sens=TRUE)$duals.to
## [1] 7e+01 1e+30 6e+01 1e+30 1e+30

Kesimpulan

Nilai z maksimum yang dapat diperoleh saat memenuhi kendala yang diberikan adalah 900 ( keuntungan sebesar Rp 900 juta), di mana X1=15 X2=10. Koefisien sensitivitas berubah dari 20 dan 20 menjadi 60 dan 60. Bayangan/harga ganda dari kendala adalah 5, 0 dan 15, sedangkan untuk variabel keputusan masing-masing adalah 0 dan 0. Batas bawah harga bayangan adalah 4e+01, -1e+30, dan 3e+01, sedangkan untuk variabel keputusan berturut-turut adalah -1e+30 dan -1e+30. Terakhir, batas atas harga bayangan adalah 17e+01, 1e+30, dan 6e+01, sedangkan untuk variabel keputusan masing-masing adalah 1e+30 dan 1e+30.

Referensi

Daftar Pustaka : https://towardsdatascience.com/linear-programming-in-r-444e9c199280