Pengantar
Linear Programming adalah metode untuk memaksimumkan atau meminimumkan fungsi linear dengan kendala linear tertentu. Linear Programming berguna dalam berbagai bidang seperti bisnis, ekonomi, teknik, dan lainnya, yang membutuhkan pengambilan keputusan maksimal di bawah batasan tertentu.
Contoh Kasus
PT Robotex memproduksi dua jenis mainan, White-X \((X_1)\) dan Fast Blue \((X_2)\), dengan tujuan memaksimumkan keuntungan. Kendala meliputi ketersediaan plastik, jam kerja, dan batasan produksi.
Persamaan Linear \[\text{Max } 8X_1 + 5X_2\] \[\text{dengan kendala (subject to):}\] \[2X_1 + X_2 \leq 1000 \text{ (ketersediaan plastik)}\] \[3X_1 + 4X_2 \leq 2400 \text{ (ketersediaan jam kerja)}\] \[X_1 + X_2 \leq 700 \text{ (kendala pemasaran, total produk)}\] \[X_1 - X_2 \leq 350 \text{ (selisih antar kedua produk)}\] \[X_j \geq 0, j = 1,2 \text{ (kendala tak negatif)}\]
Syntax R Untuk menyelesaikan model Pemrograman Linear di R, Anda dapat menggunakan paket
lpSolve. Berikut adalah contoh syntax:
library(lpSolve)
fungsi.tujuan <- c(8, 5) # Fungsi Objective {Max 8 X1+5 X2}
kendala <- matrix(c(2, 1, # Kendala 1: "2 X1 + X2" <= 1000
3, 4, # Kendala 2: "3 X1 + 4 X2" <= 2400
1, 1, # Kendala 3: "X1 + X2" <= 700
1, -1 # Kendala 4: "X1 - X2" <= 350
),
ncol = 2,
byrow = TRUE)
tanda <- c("<=", # Kendala 1: 2 X1 + X2 "<=" 1000
"<=", # Kendala 2: 3 X1 + 4 X2 "<=" 2400
"<=", # Kendala 3: X1 + X2 "<=" 700
"<=") # Kendala 4: X1 - X2 "<=" 350
rhs <- c(1000, # Kendala 1: 2 X1 + X2 <= "1000"
2400, # Kendala 2: 3 X1 + 4 X2 <= "2400"
700, # Kendala 3: X1 + X2 <= "700"
350) # Kendala 4: X1 - X2 <= "350"
solusi.optimal <- lp(direction = "max", # Memaksimumkan, default = 'min'
objective.in = fungsi.tujuan, # Objective Function
const.mat = kendala, # Constraints
const.dir = tanda, # Direction
const.rhs = rhs) # right-hand sides
print(solusi.optimal$solution) # Solution for each X1 X2 ## [1] 320 360print(solusi.optimal$objval) # The maximum value of the objective function## [1] 4360Sehingga, nilai \(X_1=320\) unit dan \(X_2=360\) unit merupakan solusi dari fungsi tujuan PT Robotex, dengan keuntungan maksimum yang didapat adalah \(\$4360\).
Latihan 1
Sebuah perusahaan menjual dua produk, Produk 1 dan Produk 2. Setiap ton Produk 1 membutuhkan 30 jam kerja, dan setiap ton Produk 2 membutuhkan 20 jam kerja. Perusahaan memiliki maksimum 2700 jam kerja untuk periode yang dipertimbangkan. Untuk jam mesin, setiap ton Produk 1 dan 2 membutuhkan 5 dan 10 jam mesin, masing-masing. Ada 850 jam mesin tersedia.
Setiap ton Produk 1 menghasilkan keuntungan 20 M€, sementara Produk 2 menghasilkan 60 M€ untuk setiap ton yang terjual. Karena alasan teknis, perusahaan harus memproduksi minimal 95 ton secara total antara kedua produk. Kita perlu tahu berapa ton Produk 1 dan 2 yang harus diproduksi untuk memaksimalkan total keuntungan.
Persamaan Linear:
\(P_1\): jumlah ton Produk 1 yang diproduksi
\(P_2\): jumlah ton Produk 2 yang diproduksi
Fungsi tujuan: Maksimalkan \(Z = 20P_1 + 60P_2\)
Dengan kendala:
- \(30P_1 + 20P_2 \leq 2700\) (kendala jam kerja)
- \(5P_1 + 10P_2 \leq 850\) (kendala jam mesin)
- \(P_1 + P_2 \geq 95\) (kendala produksi minimal)
- \(P_1, P_2 \geq 0\) (kendala non-negatif)
Syntax R:
fungsi.tujuan <- c(20, 60)
kendala <- matrix(c(30, 20,
5, 10,
1, 1),
ncol = 2, byrow = TRUE)
arah.kendala <- c("<=",
"<=",
">=")
rhs <- c(2700,
850,
95)
solusi <- lp(direction = "max", # Memaksimumkan, default = 'min'
objective.in = fungsi.tujuan, # Objective Function
const.mat = kendala, # Constraints
const.dir = arah.kendala, # Direction
const.rhs = rhs) # right-hand sides
print(solusi$solution)## [1] 20 75print(solusi$objval)## [1] 4900Sehingga, nilai \(P_1=20\) ton dan \(P_2=75\) ton merupakan solusi dari fungsi tujuan, dengan keuntungan maksimum yang didapat adalah \(4900 M€\).
Latihan 2
Seorang petani memiliki 10 hektar lahan yang akan ditanami dengan padi, jagung, dan kedelai. Kebutuhan modal dan tenaga kerja per minggu untuk masing-masing komoditas adalah sebagai berikut:
Padi: Modal 1.3 juta Rupiah dan 70 HOK (Hari Orang Kerja)
Jagung: Modal 0.8 juta Rupiah dan 60 HOK
Kedelai: Modal 0.6 juta Rupiah dan 45 HOK
Petani tersebut hanya memiliki modal awal 8 juta rupiah dan diperkirakan ada sebanyak 500 HOK per minggunya. Tentukan bagaimana sebaiknya petani tersebut memanfaatkan lahan secara optimal jika diketahui profit setiap hektar untuk padi, jagung, dan kedelai berturut-turut adalah 4 juta Rupiah, 3 juta Rupiah, dan 2.5 juta Rupiah.
Persamaan Linear:
\(P\): luas lahan untuk padi (dalam hektar)
\(J\): luas lahan untuk jagung (dalam hektar)
\(K\): luas lahan untuk kedelai (dalam hektar)
Fungsi tujuan: Maksimalkan \(Z = 4P + 3J + 2.5K\)
Dengan kendala:
- \(P + J + K \leq 10\) (kendala total lahan)
- \(1.3P + 0.8J + 0.6K \leq 8\) (kendala modal)
- \(70P + 60J + 45K \leq 500\) (kendala HOK)
- \(P, J, K \geq 0\) (kendala non-negatif)
Syntax R:
fungsi.tujuan <- c(4,
3,
2.5)
kendala <- matrix(c(1, 1, 1,
1.3, 0.8, 0.6,
70, 60, 45),
ncol = 3, byrow = TRUE)
arah.kendala <- c("<=",
"<=",
"<=")
rhs <- c(10,
8,
500)
solusi <- lp(direction = "max", # Memaksimumkan, default = 'min'
objective.in = fungsi.tujuan, # Objective Function
const.mat = kendala, # Constraints
const.dir = arah.kendala, # Direction
const.rhs = rhs) # right-hand sides
print(solusi$solution)## [1] 3.636364 0.000000 5.454545print(solusi$objval)## [1] 28.18182Sehingga, nilai \(P=3.636364\) ha, \(J=0\) ha, dan \(K=5.4545\) ha merupakan solusi dari fungsi tujuan, dengan keuntungan maksimum yang didapat adalah \(28.18182\) juta Rupiah.
Latihan 3
Seorang petani memiliki 10 hektar lahan yang akan ditanami padi, jagung, dan kedelai. Kebutuhan modal dan tenaga kerja per minggu dari masing-masing komoditas adalah seperti berikut: - Padi: Modal 1.3 juta Rupiah dan 70 HOK - Jagung: Modal 0.8 juta Rupiah dan 60 HOK - Kedelai: Modal 0.6 juta Rupiah dan 45 HOK
Petani tersebut hanya memiliki modal awal 8 juta rupiah dan diperkirakan ada sebanyak 500 HOK per minggunya. Tentukan bagaimana sebaiknya petani tersebut memanfaatkan lahan secara optimal jika diketahui profit setiap hektar untuk padi, jagung, dan kedelai berturut-turut adalah 4 juta Rupiah, 3 juta Rupiah, dan 2.5 juta Rupiah, serta jika diketahui jika lahan itu disewakan maka harga sewanya adalah 1 juta Rupiah per hektar.
Persamaan Linear:
\(P\): luas lahan untuk padi (dalam hektar)
\(J\): luas lahan untuk jagung (dalam hektar)
\(K\): luas lahan untuk kedelai (dalam hektar)
\(S\): luas lahan yang disewakan (dalam hektar)
Fungsi tujuan: Maksimalkan \(Z = 4P + 3J + 2.5K + S\)
Dengan kendala:
- \(P + J + K + S \leq 10\) (kendala total lahan)
- \(1.3P + 0.8J + 0.6K \leq 8\) (kendala modal)
- \(70P + 60J + 45K \leq 500\) (kendala HOK)
- \(P, J, K, S \geq 0\) (kendala non-negatif)
Syntax R:
fungsi.tujuan <- c(4,
3,
2.5,
1)
kendala <- matrix(c(1, 1, 1, 1,
1.3, 0.8, 0.6, 0,
70, 60, 45, 0),
ncol = 4, byrow = TRUE)
arah.kendala <- c("<=",
"<=",
"<=")
rhs <- c(10,
8,
500)
solusi <- lp(direction = "max", # Memaksimumkan, default = 'min'
objective.in = fungsi.tujuan, # Objective Function
const.mat = kendala, # Constraints
const.dir = arah.kendala, # Direction
const.rhs = rhs) # right-hand sides
print(solusi$solution)## [1] 3.636364 4.090909 0.000000 2.272727print(solusi$objval)## [1] 29.09091Sehingga, nilai \(P=3.636364\) ha, \(J=4.090909\) ha, \(K=0\) ha, dan \(S=2.2727\) merupakan solusi dari fungsi tujuan, dengan keuntungan maksimum yang didapat adalah \(29.09091\) juta Rupiah.
Tugas: Diskusikan Solusinya Secara Berkelompok
Kita ingin membuat model regresi linear yang berbentuk:
\[ Y = a + bX \]
Tujuan kita adalah meminimumkan jumlah dari nilai mutlak sisaan, yaitu:
\[ \min \sum_{i=1}^{n} |Y_i - a - bX_i| \]
Dimana:
\(Y_i\) adalah nilai observasi ke-i.
\(X_i\) adalah nilai prediktor ke-i.
\(a\) adalah intercept dari model regresi.
\(b\) adalah slope dari model regresi.
Kita diminta untuk menemukan nilai \(a\) dan \(b\) yang meminimalkan total nilai mutlak dari sisaan (kesalahan prediksi) antara nilai yang diamati dan nilai yang diprediksi oleh model regresi.