Mata Kuliah : Linear Algebra (C)

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

Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Fakultas : Sains dan Teknologi

Jurusan : Teknik Informatika

NIM : 210605110034

Linear Programming

pemrograman linier adalah metode untuk mengoptimalkan operasi dengan beberapa kendala. Tujuan utama dari program linier adalah untuk memaksimalkan atau meminimalkan nilai numerik. Ini terdiri dari fungsi linier yang dikenai kendala dalam bentuk persamaan linier atau dalam bentuk pertidaksamaan. Pemrograman linier dianggap sebagai teknik penting yang digunakan untuk menemukan pemanfaatan sumber daya yang optimal. Istilah “pemrograman linier” terdiri dari dua kata sebagai linier dan pemrograman. Kata “linier” mendefinisikan hubungan antara banyak variabel dengan derajat satu. Kata “pemrograman” mendefinisikan proses pemilihan solusi terbaik dari berbagai alternatif.

Pemrograman linier (LP) atau Optimasi Linier dapat didefinisikan sebagai masalah memaksimalkan atau meminimalkan fungsi linier yang dikenai kendala linier. Kendala tersebut dapat berupa persamaan atau ketidaksetaraan. Masalah optimasi melibatkan perhitungan keuntungan dan kerugian. Masalah pemrograman linier adalah kelas penting dari masalah optimasi, yang membantu menemukan wilayah yang layak dan mengoptimalkan solusi untuk memiliki nilai fungsi tertinggi atau terendah.

Dengan kata lain, pemrograman linier dianggap sebagai metode optimasi untuk memaksimalkan atau meminimalkan fungsi tujuan dari model matematika yang diberikan dengan himpunan beberapa persyaratan yang diwakili dalam hubungan linier. Tujuan utama dari masalah program linier adalah untuk menemukan solusi optimal.

Pemrograman linier adalah metode untuk mempertimbangkan ketidaksetaraan yang berbeda yang relevan dengan situasi dan menghitung nilai terbaik yang diperlukan untuk diperoleh dalam kondisi tersebut. Beberapa asumsi yang diambil saat bekerja dengan pemrograman linier adalah:

Komponen Pemrograman Linear

  • Variabel Keputusan

  • Kendala

  • Data

  • Fungsi Tujuan

Karakteristik Pemrograman Linier

  • Kendala – Batasan harus dinyatakan dalam bentuk matematika, mengenai sumber daya.

  • Fungsi Tujuan - Dalam suatu masalah, fungsi tujuan harus ditentukan secara kuantitatif.

  • Linearitas – Hubungan antara dua atau lebih variabel dalam fungsi harus linier. Artinya derajat variabelnya adalah satu.

  • Keterbatasan – Harus ada angka input dan output yang terbatas dan tidak terbatas. Dalam kasus, jika fungsi memiliki faktor tak hingga, solusi optimal tidak layak.

  • Non-negatif – Nilai variabel harus positif atau nol. Seharusnya tidak menjadi nilai negatif.

  • Variabel Keputusan – Variabel keputusan akan menentukan output. Ini memberikan solusi akhir dari masalah. Untuk masalah apapun, langkah pertama adalah mengidentifikasi variabel keputusan.

Masalah Pemrograman Linier

Masalah Pemrograman Linier (Linear Programming Problems) adalah masalah yang berkaitan dengan mencari nilai optimal dari fungsi linier yang diberikan. Nilai optimal dapat berupa nilai maksimum atau nilai minimum. Di sini, fungsi linier yang diberikan dianggap sebagai fungsi tujuan. Fungsi tujuan dapat berisi beberapa variabel, yang tunduk pada kondisi dan harus memenuhi himpunan pertidaksamaan linier yang disebut kendala linier. Masalah program linier dapat digunakan untuk mendapatkan solusi optimal untuk skenario berikut, seperti masalah manufaktur, masalah transportasi, masalah alokasi dan sebagainya.

Metode untuk Memecahkan Masalah Pemrograman Linier

Masalah pemrograman linier dapat diselesaikan dengan menggunakan metode yang berbeda, seperti metode grafis, metode simpleks, atau dengan menggunakan alat seperti R, pemecah terbuka dll. Ada dua teknik terpenting yang disebut metode simpleks dan metode grafis dalam rinci.

Contoh Membangun Linear Programming Solve

Dan di sini kita akan membuat sebuah solusi Linear Programming dalam R dengan menggunakan lpSolve (Linear Programming Solve). Berikut merupakan langkah-langkah untuk membangun Linear Programming Solve:

# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c()
# Set matrix corresponding to coefficients of constraints by rows
f.con <- matrix(c(), nrow = , byrow = TRUE)
# Set unequality/equality signs
f.dir <- c(“<=”, “>=”, “=”)
# Set right hand side coefficients
f.rhs <- c()
# Final value (z)
lp(“max”, f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp(“max”, f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp(“max”, f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)$sens.coef.from
lp(“max”, f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp(“max”, f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)$duals
# Duals lower and upper limits
lp(“max”, f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)$duals.from
lp(“max”, f.obj, f.con, f.dir, f.rhs, compute.sens = TRUE)$duals.to

Menginstall Packages "lpSolve"

Packages lpSolve dari R berisi beberapa fungsi untuk menyelesaikan masalah program linier dan mendapatkan analisis statistik yang signifikan.

# Import lpSolve package
library(lpSolve)

Menetapkan koefisien dari fungsi tujuan

f.obj <- c(5, 7)

Menetapkan matriks yang sesuai dengan koefisien kendala berdasarkan baris

# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(1, 0,
                  2, 3,
                  1, 1), nrow = 3, byrow = TRUE)

Menetapkan tanda-tanda ketidaksetaraan

f.dir <- c("<=",
           "<=",
           "<=")

Menetapkan koefisien sisi kanan

f.rhs <- c(16,
           19,
           8)

Mendapatkan nilai maksimum

# Final value (z)
lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 46

Mendapatkan variabel akhir

lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 5 3

Merubah koefisien sensitivitas

lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
## [1] 4.666667 5.000000
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
## [1] 7.0 7.5

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 2 1 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] -1.000000e+30  1.600000e+01  6.333333e+00 -1.000000e+30 -1.000000e+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] 1.0e+30 2.4e+01 9.5e+00 1.0e+30 1.0e+30

Solution

Nilai z maksimum yang dapat diperoleh saat memenuhi kendala yang diberikan adalah 46, di mana x1 = 5 dan x2 = 3. Koefisien sensitivitas berubah dari 4,667 dan 5,0 menjadi 7,0 dan 7,5. Bayangan/harga ganda dari kendala adalah 0, 2 dan 1, sedangkan untuk variabel keputusan adalah 0 dan 0, masing-masing. Batas bawah batasan harga bayangan/ganda adalah -1.0e+30, 1.6e+01 dan 6.3e+00, sedangkan untuk variabel keputusan berturut-turut adalah -1.0e+30 dan -1.0e+30. Terakhir, batas atas batasan harga bayangan/ganda adalah 1.0e+30, 2.4e+01 dan 9.5e+00, sedangkan untuk variabel keputusan masing-masing adalah 1.0e+30 dan 1.0e+30.