Prodi : Teknik Informatika

Lembaga : UIN Maulana Malik Ibrahim Malang

Penyelesaian Pemrograman Linear

Program linear adalah salah satu model matematika yang digunakan untuk menyelesaikan masalah optimisasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan yang bergantung pada sejumlah variabel input.

Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut.

Dua macam fungsi Program Linear:

Masalah Maksimisasi

Maksimisasi dapat berupa memaksimalkan keuntungan atau hasil. Contoh:

PT. HARAPAN TEKSTIL memiliki sebuah pabrik yang akan 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.

Langkah-langkah:

  1. Menentukan Variabel

    X1=kain sutera

    X2=kain wol

#Menginstall Packages"lpSolve"
library(lpSolve)

Setelah kita mendefinisikan variabel keputusan, maka langkah selanjutnya adalah menuliskan secara matematis fungsi tujuan dan fungsi kendala.

  1. Fungsi tujuan

    Tujuan pabrik adalah maksimisasi keuntungan, sehingga kita dapat menuliskan fungsi tujuan secara matematis yaitu sebagai berikut :

    Zmax= 40X1 + 30X2

#Menetapkan koefisien dari fungsi tujuan
f.obj <- c(40, 30)

  1. Fungsi kendala / batasan

    Berkaitan dengan sumber daya yang digunakan, pabrik kesulitan untuk menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar dapat memperoleh keuntungan yang maksimal.

    1. Kendala yang pertama adalah pengutamaan memproduksi jenis produk. Untuk memproduksi kain sutera diperlukan bahan baku benang sutera (X1) sebanyak 2 kg dan benang wol (X2) sebanyak 3 kg. dimana maksimum penyediaan benang sutera adalah 60 kg per hari. Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis menjadi: 2X1 + 3X2 ≤ 60

    2. Seperti halnya kendala yang pertama, dapat diketahui bahwa untuk memproduksi kain wol hanya diperlukan bahan baku benang wol (X2) sebanyak 2 kg. dimana jumlah maksimum penyediaan benang wol adalah 30 kg per hari. Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis menjadi: 2X2 ≤ 30

    3. Kendala yang ketiga ada pada tenaga kerja. dalam sehari pabrik dapat memproduksi 2 kain sutera (X1) dan 1 kain wol (X2) dimana maksimum penyediaan tenaga kerja adalah 40 jam perhari. Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis menjadi: 2X1 + X2 ≤ 40

      Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah asumsi nilai X1 dan X2 tidak negatif. Artinya bahwa X1 ≥ 0 (jumlah kain sutera yang diproduksi adalah lebih besar atau sama dengan nol) X2 ≥ 0 (jumlah kain wol yang diproduksi adalah lebih besar atau sama dengan nol) Dari uraian di atas dapat dirumuskan formulasi permasalahan secara lengkap sebagai berikut :

      Fungsi tujuan :

      Maksimisasi Zmax= 40X1 + 30X2

      Fungsi kendala :

      2X1 + 3X2 ≤ 60 (benang sutera)

      2X2 ≤ 30 (benang wol)

      2X1 + X2 ≤ 40 (tenaga kerja)

      X1 ≥ 0 (kendala non negatif pertama)

      X2 ≥ 0 (kendala non negatif kedua)

#Menetapkan matriks yang sesuai dengan koefisien kendala berdasarkan baris
f.con <- matrix(c(2, 3,
                  0, 2,
                  2, 1), nrow = 3, byrow = TRUE)
#Menetapkan tanda-tanda ketidaksetaraan
f.dir <- c("<=",
           "<=",
           "<=")
#Menetapkan koefisien sisi kanan
f.rhs <- c(60,
           30,
           40)

  1. Membuat grafik

    1. 2X1 + 3 X 2=60

      X1=0, X2 =60/3 = 20

      X2=0, X1= 60/2 = 30

    2. 2X2 ≤ 30

      X2=15

    3. 2X1 + X2 ≤ 40

      X1=0, X2 = 40

      X2=0, X1= 40/2 = 20

  2. Mendapatkan solusi optimal

#Mendapatkan nilai maksimum
lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 900
#Mendapatkan variabel akhir
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 15 10
#Merubah koefisien sensitivitas
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
## [1] 20 20
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
## [1] 60 60
#Mendapat bayangan/harga ganda dari kendala dan variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
## [1]  5  0 15  0  0
#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]  4e+01 -1e+30  3e+01 -1e+30 -1e+30
#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] 7e+01 1e+30 6e+01 1e+30 1e+30

Solution

Nilai z maksimum yang dapat diperoleh saat memenuhi kendala yang diberikan adalah 900 atau keuntungan sebesar Rp 900 juta, di mana x1 = 15 dan 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 adalah 0 dan 0, masing-masing. Batas bawah batasan harga bayangan/ganda adalah 4e+01, -1e+30 dan 3e+01, sedangkan untuk variabel keputusan berturut-turut adalah -1e+30 dan -1e+30. Terakhir, batas atas batasan harga bayangan/ganda adalah 7e+01, 1e+30 dan 6e+01, sedangkan untuk variabel keputusan masing-masing adalah 1e+30 dan 1e+30.