Dosen Pengempu : Prof. Dr. Suhartono, M.Kom

UIN Maulana Malik Ibrahim Malang - Teknik Informatika

Linear Programming

Linear Programming atau pemrograman linear adalah metode untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika yang juga dikenal dengan sebutan optimisasi matematika. Secara umum, program linear adalah sebuah teknik optimisasi untuk fungsi objektif linear, dengan beberapa persamaan linear dan pertidaksamaan linear.

Menurut Stapleton, Hanna, dan Markussen (2003), definisi linear programming adalah suatu teknik aplikasi matematika dalam menentukan pemecahan masalah yang bertujuan untuk memaksimumkan atau meminimumkan sesuatu yang dibatasi oleh batasan-batasan tertentu. Linear programming memiliki dua macam fungsi, yang pertama pada fungsi tujuan yakni mengarahkan analisa untuk mendeteksi tujuan perumusan masalah, dan yang kedua yakni tujuan kendala yang bertujuan untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.

Maksimasi

Maksimasi berupa memaksimalkan keuntungan atau hasil, seperti contoh dibawah yakni :

PT. MAKMUR JAYA TEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu stel jas dan rok. Untuk memproduksi kedua produk diperlukan bahan kain wol dan kain sutra. Satu stel jas memerlukan 3 meter kain wol dan 1 meter kain sutra. Dan untuk satu stel roknya memerlukan 2 meter kain wol dan 2 meter kain sutra. Kebutuhan setiap unit produk untuk bahan kain dapat dilihat pada tabel di bawah ini :

Pendapatan setiap stel jas dan rok yaitu Rp.120.000,00 dan Rp.75.000,00. Masalah ada pada bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal.

Cara Penyelesaian

Menentukan Variabel

  • x = Jas

  • y = Rok

Fungsi Tujuan

Tujuan pabrik ini adalah maksimisasi keuntungan, sehingga dapat dituliskan fungsi tujuan secara matematis yaitu seperti di bawah ini :

  • 120x + 75y
library(lpSolve)
# Memasukkan koefisien dari fungsi tujuan pada f.obj
f.obj <- c(120, 75)
Fungsi Kendala (Batasan)

Pabrik ini masih dalam pengembangan dan dikarenakan sumber daya bahan yang digunakan, pabrik akan kesulitan dalam menentukan jumlah unit untuk setiap jenis produk yang akan diproduksi setiap hari guna mendapatkan keuntungan yang maksimal. Beberapa kendalanya diantara lain, ada :

  1. Pengutamaan penyediaan barang jenis produk

  2. Jumlah maksimum pada bahan baku yang diperlukan untuk memproduksi jenis produk

Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah asumsi nilai x dan y tidak negatif. Artinya bahwa x ≥ 0 (jumlah jas yang diproduksi lebih besar atau sama dengan nol) y ≥ 0 (jumlah rok yang diproduksi lebih besar atau sama dengan nol). Dari pernyataan di atas dapat dirumuskan formulasi permasalahan secara lengkap seperti di bawah ini :

  • 3x + 2y ≤ 60
  • x + 2y ≤ 40
  • x ≥ 0
  • y ≥ 0
#Menetapkan matriks yang sesuai dengan koefisien kendala berdasarkan baris
f.con <- matrix(c(3, 1,
                  2, 2), nrow = 2, byrow = TRUE)
#Menetapkan tanda-tanda ketidaksetaraan
f.dir <- c("<=",
           "<=")
#Menetapkan koefisien sisi kanan
f.rhs <- c(120,
           75)
Membuat Daerah Penyelesaian

Daerah penyelesaian berupa grafik dapat digambarkan ketika telah ditemukan titik potong pada persamaan linear yang dimiliki. Oleh karena itu, di bawah ini adalah langkah-langkah mendapatkan titik potong dari persamaan tersebut.

3x + 2y ≤ 60

x + 2y ≤ 40

  • 2x ≤ 20

  • x ≤ 10

x + 2y ≤ 40

10 + 2y ≤ 40

  • 2y ≤ 30

  • y ≤ 15

Dari dua perhitungan di atas didapatkan titik potong (10,15)

Di bawah ini adalah gambar dari daerah penyelesaian berdasarkan titik potong yang didapatkan :

Mencari Titik Koordinat

  1. 3x + 2y ≤ 60

    x = 0, y = 30 didapatkan titik koordinat (0,30)

    x = 20, y = 0 didapatkan titik koordinat (20,0)

  2. x + 2y ≤ 40

    x = 0, y = 20 didapatkan titik koordinat (0,20)

    x = 40, y = 0 didapatkan titik koordinat (40,0)

Mendapatkan Solusi Optimal

Mencari Nilai Maksimum

#Mendapatkan nilai maksimum
lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 4500

Mencari Nilai Variabel Terakhir

#Mendapatkan variabel akhir
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 37.5  0.0

Mengganti Koefisien Sensivitas

#Merubah koefisien sensitivitas
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
## [1]  7.5e+01 -1.0e+30
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
## [1] 1.0e+30 1.2e+02

Mencari Harga Ganda dari Kendala dan Variabel Keputusan

#Mendapat bayangan/harga ganda dari kendala dan variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
## [1]   0  60   0 -45

Mencari Batas Bawah Harga Ganda dari Kendala dan Variabel Keputusan

#Mendapat batas bawah batasan harga bayangan/ganda dan masing masing variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
## [1] -1.00e+30  0.00e+00 -1.00e+30 -3.75e+00

Mencari Batas Atas Harga Ganda dari Kendala dan Variabel Keputusan

#Mendapat batas atas batasan harga bayangan/ganda dan masing masing variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
## [1] 1.00e+30 8.00e+01 1.00e+30 3.75e+01

Kesimpulan

Nilai akhir maksimum yang diperoleh saat memenuhi kendala yang diberikan adalah 4500 di mana x = 37.5 dan y = 0. Koefisien sensitivitas berubah dari 7.5e+01 - 1.0e+30 menjadi 1.0e+30 1.2e+02. Harga ganda dari kendala adalah 60 dan -45. Sedangkan untuk masing-masing variabel keputusan adalah 0 dan 0. Batas bawah batasan harga ganda adalah -1.00e+30 dan 0.00e+00, sedangkan untuk variabel keputusan berturut-turut adalah -1.00e+30 dan -3.75e+00. Terakhir, batas atas batasan harga ganda adalah 1.00e+30 dan 8.00e+01, sedangkan untuk variabel keputusan masing-masing adalah 1.00e+30 dan 3.75e+01.

Referensi