Optimisasi Statistika - Linear Programming

Video Pembelajaran - P8

Video Pembelajaran dapat diakses melalui link berikut : https://ipb.link/materiopstat

Pengantar Linear Programming (LP)

Linear Programming (LP) adalah teknik optimasi yang bertujuan untuk mencari solusi optimal dari sebuah fungsi tujuan (objective function) yang bersifat linear, dengan beberapa batasan berupa kendala (constraints). Solusi ini sering digunakan dalam berbagai bidang seperti:

Manajemen dan Bisnis: Untuk pengelolaan sumber daya yang terbatas seperti bahan baku, tenaga kerja, atau waktu.
Ekonomi: Untuk menganalisis biaya produksi, efisiensi, dan keuntungan.
Logistik: Perencanaan distribusi atau pengelolaan rantai pasokan.
Teknik: Untuk perencanaan sistem dan alokasi sumber daya yang efisien.

Komponen Utama dalam LP

Fungsi Tujuan (Objective Function):
Ini adalah fungsi yang ingin kita optimalkan (maksimalkan atau minimalkan). Secara umum, bentuknya:
\[ Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n \]
di mana $Z$ adalah nilai fungsi tujuan, dan $x_1, x_2, \ldots, x_n$ adalah variabel keputusan.
Kendala (Constraints):
Kendala adalah batasan yang harus dipenuhi, biasanya terkait dengan sumber daya. Bentuknya:
\[ a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 \]
di mana $b_1$ adalah batas maksimum sumber daya.
Kendala Non-negatif:
Variabel keputusan $x_1, x_2, \ldots, x_n$ tidak bisa bernilai negatif. Dengan kata lain,
\[ x_j \geq 0 \quad \text{untuk } j = 1, 2, \ldots, n \]

Contoh Kasus

PT Robotex memproduksi dua jenis mainan:
- White-X ($X_1$)
- Fast Blue ($X_2$)

Tujuan perusahaan adalah memaksimalkan keuntungan dengan batasan sumber daya seperti plastik, jam kerja, dan batasan produksi.

Fungsi Tujuan dan Kendala

Fungsi Tujuan:
Maksimalkan keuntungan:
\[ \text{Max } Z = 8X_1 + 5X_2 \]
di mana:
- $X_1$: jumlah unit White-X yang diproduksi.
- $X_2$: jumlah unit Fast Blue yang diproduksi.
Kendala:
- Ketersediaan plastik:
  \[ 2X_1 + X_2 \leq 1000 \]
- Ketersediaan jam kerja:
  \[ 3X_1 + 4X_2 \leq 2400 \]
- Kapasitas produksi total:
  \[ X_1 + X_2 \leq 700 \]
- Selisih produksi antar produk:
  \[ X_1 - X_2 \leq 350 \]
- Non-negatif:
  \[ X_1, X_2 \geq 0 \]

Penyelesaian dengan R

Penyelesaian model LP dapat dilakukan menggunakan pustaka lpSolve dalam R. Berikut adalah kode lengkapnya:

# Memuat library lpSolve
library(lpSolve)

# Fungsi tujuan
fungsi.tujuan <- c(8, 5) # Koefisien dalam fungsi tujuan Z = 8X1 + 5X2

# Matriks kendala
kendala <- matrix(c(2, 1,   # Plastik
                    3, 4,   # Jam kerja
                    1, 1,   # Produksi total
                    1, -1), # Selisih produksi
                  ncol = 2, byrow = TRUE)

# Arah kendala
tanda <- c("<=", "<=", "<=", "<=")

# Batas kanan kendala
rhs <- c(1000, 2400, 700, 350)

# Menyelesaikan dengan lpSolve
solusi.optimal <- lp(direction = "max", 
                     objective.in = fungsi.tujuan, 
                     const.mat = kendala, 
                     const.dir = tanda, 
                     const.rhs = rhs)

# Output solusi optimal
print(solusi.optimal$solution) # Hasil optimal untuk X1 dan X2

## [1] 320 360

print(solusi.optimal$objval)   # Nilai fungsi tujuan optimal

## [1] 4360

Hasil Perhitungan:

Solusi optimal:
\[ X_1 = 320, \quad X_2 = 360 \]
Nilai fungsi tujuan maksimum:
\[ Z = 8(320) + 5(360) = 4360 \]

Ini berarti PT Robotex sebaiknya memproduksi 320 unit White-X dan 360 unit Fast Blue untuk mendapatkan keuntungan maksimum sebesar $4360.

Latihan 1: Perusahaan dengan 2 Produk

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.

Deskripsi Masalah

Sebuah perusahaan memproduksi dua jenis produk, yaitu:
- Produk 1 ($P_1$)
- Produk 2 ($P_2$)

Setiap produk membutuhkan sumber daya berikut:
- Produk 1: 30 jam kerja dan 5 jam mesin per ton.
- Produk 2: 20 jam kerja dan 10 jam mesin per ton.

Batasan sumber daya:
1. Maksimum jam kerja: 2700 jam.
2. Maksimum jam mesin: 850 jam.
3. Produksi total minimal: 95 ton.

Keuntungan:
- Produk 1 menghasilkan 20 M€ per ton.
- Produk 2 menghasilkan 60 M€ per ton.

Model Linear Programming

Fungsi Tujuan:

\[ \text{Max } Z = 20P_1 + 60P_2 \]

Kendala:

Jam kerja:
\[ 30P_1 + 20P_2 \leq 2700 \]
Jam mesin:
\[ 5P_1 + 10P_2 \leq 850 \]
Produksi total minimal:
\[ P_1 + P_2 \geq 95 \]
Non-negatif:
\[ P_1, P_2 \geq 0 \]

Penyelesaian dengan R

Kode berikut menggunakan pustaka lpSolve untuk menyelesaikan model ini:

# Fungsi tujuan
fungsi.tujuan <- c(20, 60)

# Matriks kendala
kendala <- matrix(c(30, 20,   # Kendala jam kerja
                    5, 10,    # Kendala jam mesin
                    1, 1),    # Produksi total minimal
                  ncol = 2, byrow = TRUE)

# Arah kendala
arah.kendala <- c("<=", "<=", ">=")

# Batas kanan kendala
rhs <- c(2700, 850, 95)

# Penyelesaian dengan lpSolve
solusi <- lp(direction = "max", 
             objective.in = fungsi.tujuan, 
             const.mat = kendala, 
             const.dir = arah.kendala, 
             const.rhs = rhs)

# Output solusi optimal
print(solusi$solution) # Hasil optimal untuk P1 dan P2

## [1] 20 75

print(solusi$objval)   # Nilai fungsi tujuan optimal

## [1] 4900

Hasil Perhitungan:

Solusi optimal:
\[ P_1 = 20, \quad P_2 = 75 \]
Nilai fungsi tujuan maksimum:
\[ Z = 20(20) + 60(75) = 4900 \, \text{M€} \]

Interpretasi Hasil:
- Perusahaan sebaiknya memproduksi 20 ton Produk 1 dan 75 ton Produk 2 untuk mendapatkan keuntungan maksimum sebesar 4900 M€.
- Kedua kendala sumber daya (jam kerja dan jam mesin) digunakan secara optimal.

Latihan 2: Pemanfaatan Lahan oleh Petani

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.

Deskripsi Masalah

Seorang petani memiliki 10 hektar lahan yang dapat ditanami tiga jenis komoditas:
1. Padi ($P$): Profit 4 juta/hektar, modal 1.3 juta, tenaga kerja 70 HOK/hektar.
2. Jagung ($J$): Profit 3 juta/hektar, modal 0.8 juta, tenaga kerja 60 HOK/hektar.
3. Kedelai ($K$): Profit 2.5 juta/hektar, modal 0.6 juta, tenaga kerja 45 HOK/hektar.

Sumber daya terbatas:
1. Modal maksimum: 8 juta.
2. Tenaga kerja maksimum: 500 HOK.
3. Luas total lahan: 10 hektar.

Model Linear Programming

Fungsi Tujuan:

\[ \text{Max } Z = 4P + 3J + 2.5K \]

Kendala:

Luas lahan total:
\[ P + J + K \leq 10 \]
Modal:
\[ 1.3P + 0.8J + 0.6K \leq 8 \]
Tenaga kerja:
\[ 70P + 60J + 45K \leq 500 \]
Non-negatif:
\[ P, J, K \geq 0 \]

Penyelesaian dengan R

Kode berikut menyelesaikan masalah menggunakan pustaka lpSolve:

# Fungsi tujuan
fungsi.tujuan <- c(4, 3, 2.5)

# Matriks kendala
kendala <- matrix(c(1, 1, 1,    # Kendala luas total
                    1.3, 0.8, 0.6, # Kendala modal
                    70, 60, 45),   # Kendala tenaga kerja
                  ncol = 3, byrow = TRUE)

# Arah kendala
arah.kendala <- c("<=", "<=", "<=")

# Batas kanan kendala
rhs <- c(10, 8, 500)

# Penyelesaian dengan lpSolve
solusi <- lp(direction = "max", 
             objective.in = fungsi.tujuan, 
             const.mat = kendala, 
             const.dir = arah.kendala, 
             const.rhs = rhs)

# Output solusi optimal
print(solusi$solution) # Hasil optimal untuk P, J, K

## [1] 3.636364 0.000000 5.454545

print(solusi$objval)   # Nilai fungsi tujuan optimal

## [1] 28.18182

Hasil Perhitungan:

Solusi optimal:
\[ P = 3.636 \, \text{ha}, \quad J = 0 \, \text{ha}, \quad K = 5.454 \, \text{ha} \]
Nilai fungsi tujuan maksimum:
\[ Z = 4(3.636) + 2.5(5.454) = 28.182 \, \text{juta Rupiah} \]

Interpretasi Hasil:
- Petani sebaiknya menanam padi di 3.636 hektar dan kedelai di 5.454 hektar, serta tidak menanam jagung sama sekali.
- Dengan strategi ini, keuntungan maksimum yang diperoleh adalah 28.182 juta Rupiah.

Latihan 3: Menyewakan Lahan Petani

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 sebagai 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

Deskripsi Masalah

Seorang petani memiliki 10 hektar lahan yang dapat dimanfaatkan untuk tiga komoditas atau disewakan:
1. Padi ($P$): Profit 4 juta/hektar, modal 1.3 juta, tenaga kerja 70 HOK/hektar.
2. Jagung ($J$): Profit 3 juta/hektar, modal 0.8 juta, tenaga kerja 60 HOK/hektar.
3. Kedelai ($K$): Profit 2.5 juta/hektar, modal 0.6 juta, tenaga kerja 45 HOK/hektar.
4. Sewa ($S$): Harga sewa 1 juta/hektar.

Kendala sumber daya:
1. Modal maksimum: 8 juta.
2. Tenaga kerja maksimum: 500 HOK.
3. Luas total lahan: 10 hektar.

Model Linear Programming

Fungsi Tujuan:

\[ \text{Max } Z = 4P + 3J + 2.5K + S \]

Kendala:

Luas total lahan:
\[ P + J + K + S \leq 10 \]
Modal:
\[ 1.3P + 0.8J + 0.6K \leq 8 \]
Tenaga kerja:
\[ 70P + 60J + 45K \leq 500 \]
Non-negatif:
\[ P, J, K, S \geq 0 \]

Penyelesaian dengan R

Kode berikut menyelesaikan masalah menggunakan pustaka lpSolve:

# Fungsi tujuan
fungsi.tujuan <- c(4, 3, 2.5, 1) # Koefisien dalam Z = 4P + 3J + 2.5K + S

# Matriks kendala
kendala <- matrix(c(1, 1, 1, 1,    # Kendala luas total
                    1.3, 0.8, 0.6, 0, # Kendala modal
                    70, 60, 45, 0),   # Kendala tenaga kerja
                  ncol = 4, byrow = TRUE)

# Arah kendala
arah.kendala <- c("<=", "<=", "<=")

# Batas kanan kendala
rhs <- c(10, 8, 500)

# Penyelesaian dengan lpSolve
solusi <- lp(direction = "max", 
             objective.in = fungsi.tujuan, 
             const.mat = kendala, 
             const.dir = arah.kendala, 
             const.rhs = rhs)

# Output solusi optimal
print(solusi$solution) # Hasil optimal untuk P, J, K, S

## [1] 3.636364 4.090909 0.000000 2.272727

print(solusi$objval)   # Nilai fungsi tujuan optimal

## [1] 29.09091

Hasil Perhitungan:

Solusi optimal:
\[ P = 3.636 \, \text{ha}, \quad J = 4.091 \, \text{ha}, \quad K = 0 \, \text{ha}, \quad S = 2.273 \, \text{ha} \]
Nilai fungsi tujuan maksimum:
\[ Z = 4(3.636) + 3(4.091) + 1(2.273) = 29.091 \, \text{juta Rupiah} \]

Interpretasi Hasil:

Petani sebaiknya:
- Menanam padi di 3.636 hektar.
- Menanam jagung di 4.091 hektar.
- Tidak menanam kedelai sama sekali.
- Menyewakan 2.273 hektar lahan.
Strategi ini memberikan keuntungan maksimum sebesar 29.091 juta Rupiah.

Kesimpulan dari Semua Latihan

Latihan 1 (Perusahaan 2 Produk):
Perusahaan memproduksi 20 ton Produk 1 dan 75 ton Produk 2, dengan keuntungan maksimum 4900 M€.
Latihan 2 (Pemanfaatan Lahan):
Petani memanfaatkan 3.636 hektar untuk padi dan 5.454 hektar untuk kedelai, dengan keuntungan maksimum 28.182 juta Rupiah.
Latihan 3 (Menyewakan Lahan):
Petani memanfaatkan 3.636 hektar untuk padi, 4.091 hektar untuk jagung, dan 2.273 hektar disewakan, dengan keuntungan maksimum 29.091 juta Rupiah.