Informatics Engineering

Universitas Islam Negeri Maulana Malik Ibrahim Malang

What is Linear Programming?

Linear programming (LP) or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimisation problems involve the calculation of profit and loss. Linear programming problems are an important class of optimisation problems, that helps to find the feasible region and optimise the solution in order to have the highest or lowest value of the function.

In other words, linear programming is considered as an optimization method to maximize or minimize the objective function of the given mathematical model with the set of some requirements which are represented in the linear relationship. The main aim of the linear programming problem is to find the optimal solution.

Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions. Some of the assumptions taken while working with linear programming are:

The number of constraints should be expressed in the quantitative terms The relationship between the constraints and the objective function should be linear The linear function (i.e., objective function) is to be optimised.

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.

Maksimasi Fungsi

Maksimasi fungsi adalah cara untuk mencari nilai maksimum dari suatu fungsi.

Implementasi Pada Studi Kasus

Maksimisasi fungsi dapat berupa memaksimalkan keuntungan atau hasil, contohnya misalnya ditampilkan kasus seperti berikut :

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?

Penyelesaian dengan Maksimasi Fungsi Linear Programming

  1. Menentukan Variabel

    X1 = kain sutera

    X2 = kain wol

  2. Fungsi Tujuan

    Zmax = 40X1 + 30X2

library (lpSolve)
# Memasukkan koefisien dari fungsi tujuan pada f.obj
f.obj <- c(40, 30)

  1. Fungsi Kendala atau Batasan

    2X1 + 3X2 ≤ 60 (benang sutera)

    2X2 ≤ 30 (benang wol)

    2X1 + X2 ≤ 40 (tenaga kerja)

# Memasukkan koefiesian fungsi kendala dalam bentuk matriks 
# Dengan nrow menunjukkan banyaknya kendala yaitu 3 dan angka yang 
# diinput disusun perbaris sehingga byrow = TRUE
f.con <- matrix(c(2, 3,
                  0, 2,
                  2, 1), nrow = 3, byrow = TRUE)
# Memasukkan tanda pertidaksamaan pada setiap kendala
f.dir <- c("<=",
           "<=",
           "<=")
# Memasukkan koefisien ruas kanan
f.rhs <- c(60,
           30,
           40)
MENDAPATKAN SOLUSI OPTIMAL 
# Keuntungan Maksimum

lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 900
# Nilai Variabel agar mencapai keuntungan maksimum
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 15 10
# 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
# 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
# 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
# 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

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 , 15

variabel keputusan masing-masing adalah 0 dan 0

Batas bawah harga bayangan adalah 4e+01, -1e+30, dan 3e+01

variabel keputusan berturut-turut adalah -1e+30 dan -1e+30

Batas atas harga bayangan adalah 17e+01, 1e+30, dan 6e+01

variabel keputusan masing-masing adalah 1e+30 dan 1e+30